Need help with non-linear Diophantine

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Need help with non-linear Diophantine

Postby Cradarc » Mon Mar 28, 2016 12:34 am UTC

I'm trying to solve the following system over integers a,b,c,d:

c+b = a*d
c*b = a2 - d


There are only two equations for four unknowns, so I expect to have two degrees of freedom in the solution.
However the only solutions I've found so far is: {a = any integer, b = a3, c = 0, d = a2}, which only has one degree of freedom.

I would appreciate some help/tips regarding how to find more solutions or prove the only solutions are of that form. This is not homework. someone gave me this problem because they couldn't solve it.
This is a block of text that can be added to posts you make. There is a 300 character limit.

pex
Posts: 10
Joined: Mon Mar 28, 2016 3:51 am UTC

Re: Need help with non-linear Diophantine

Postby pex » Mon Mar 28, 2016 4:09 am UTC

I believe the general statement is "nonlinear Diophantine equations are hard".

Let k be an arbitrary integer. The solution family that you found is (a,b,c,d) = (k, k3, 0, k2); a couple of others are (0, k, -k, k2) and (k3, k, k5-k, k2), as well as (obviously) the same things with b and c swapped. I suppose there must be even more families, but haven't really looked into it yet.

Interestingly, the only solutions that I have encountered where d is not a square all have d=-5. Some solutions are
(-1, 2, 3, -5)
(-2, 1, 9, -5)
(-3, 1, 14, -5)
(-9, 2, 43, -5)
(-14, 3, 67, -5)
(-43, 9, 206, -5)
(-67, 14, 321, -5)
(-206, 43, 987, -5)
(-321, 67, 1538, -5)
(-987, 206, 4729, -5)
(-1538, 321, 7369, -5)
and of course, for every (a,b,c,d), there are also (a,c,b,d), (-a,-b,-c,d), and (-a,-c,-b,d). There seems to be a pattern among the solutions for d=-5 (if a number shows up as b or c, it also appears as a in another solution), but I haven't bothered proving this yet. Such chains of solutions are not uncommon in Diophantine equations, though.

In general, you want to find a and d such that M2 = (ad)2 - 4a2 + 4d is a perfect square; the corresponding b and c are (ad ± M) / 2. I do not know of a generic way to find such solutions, but then again, there is much that I don't know about Diophantine equations.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Need help with non-linear Diophantine

Postby Cauchy » Mon Mar 28, 2016 6:16 am UTC

c+b = a*d
c*b = a^2 - d

c = ad - b

(ad - b)b = a^2 - d

abd - b^2 = a^2 - d
abd + d = a^2 + b^2
d(ab+1) = a^2 + b^2

So ab+1 divides a^2 + b^2.

I'm pretty sure I've seen "Find all pairs of integers (m, n) such that (m^2+n^2)/(mn+1) is an integer" as an Olympiad-level problem before, but I can't remember what the solution is. Using a, b, and d instead from our equations earlier, my recollection is that the answer involves fixing a value for d, and then noting that the equation abd - b^2 = a^2 - d, i.e. a^2 + b^2 - abd - d = 0 is a quadratic in both a and b. So, given a solution (a_0, b_0), Vieta's formula gives us that (b_0d - a_0, b_0) and (a_0, a_0d - b_0) are also both solutions. So solutions to the equation are connected together in infinite sequences using these two transformations alternatingly. Then there was an infinite descent argument which demonstrated that every such solution reduced via these transformations to a solution which had one of the integers be 0, which in turn gave us all solutions as (a,0) and (0,b), and their repeated transformations.

So that would be a family of solutions with two degrees of freedom: the starting value that's paired with 0, and the number of times the transformations are applied.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

pex
Posts: 10
Joined: Mon Mar 28, 2016 3:51 am UTC

Re: Need help with non-linear Diophantine

Postby pex » Mon Mar 28, 2016 8:24 am UTC

While my previous post was in the moderation queue, I noticed the same transformations mentioned by Cauchy: if (a,b,c,d) is a solution, then so are (b, bd-a, a, d) and (c, a, cd-a, d). This still doesn't help us understand for which values of d solutions exist, however.

So far I have only found solutions where d is either a square or -5. It seems that all of them can indeed be generated using the above transformations, starting from (0, k, -k, k2) or (-1, 2, 3, -5). I have no proof that this is the case, nor any intuition for what is special about d=-5 in this context.

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Need help with non-linear Diophantine

Postby Cradarc » Mon Mar 28, 2016 7:40 pm UTC

Thank you both for the help! Looks like I'm in over my head on this problem. You guys offered much need insight.

Cauchy, the reformulation you mentioned was indeed an IMO problem. In fact, it showed up on Wikipedia's Vieta Jumping page!
The IMO problem only asked for a proof that d is a perfect square though. It's interesting how Pex found a solution for d = -5. Does that mean the proof is flawed?
This is a block of text that can be added to posts you make. There is a 300 character limit.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Need help with non-linear Diophantine

Postby Cauchy » Mon Mar 28, 2016 11:10 pm UTC

Cradarc wrote:Thank you both for the help! Looks like I'm in over my head on this problem. You guys offered much need insight.

Cauchy, the reformulation you mentioned was indeed an IMO problem. In fact, it showed up on Wikipedia's Vieta Jumping page!
The IMO problem only asked for a proof that d is a perfect square though. It's interesting how Pex found a solution for d = -5. Does that mean the proof is flawed?


a and b are positive integers in the problem listed on that page. d = -5 requires one of a and b to be negative.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

pex
Posts: 10
Joined: Mon Mar 28, 2016 3:51 am UTC

Re: Need help with non-linear Diophantine

Postby pex » Tue Mar 29, 2016 2:15 am UTC

[rambling]
Long and boring case bashing (mod 8) seems to indicate that the only non-square d for which there might be solutions are d = 3-8k, for positive integers k. Warning: this result is based on lots of ugly scribbling which I don't feel like typing up since I feel there ought to be a more elegant solution, so it might well be wrong. This would leave us with d=-5 (infinitely many solutions, as we've seen before), d=-13 (which I could rule out based on an ad hoc argument mod 5), d=-21 (which my modular arithmetic fails to rule out, but I haven't found a solution either), and then the untested d=-29, d=-37, etc.

If my ability to manipulate quadratic residues is to be trusted (and I'm not too sure of that), 2-d = 8k-1 must have an odd number of prime factors, all of which are -1 (mod 8), and 6-d = 8k-5 must also have an odd number of prime factors, all of which are +3 (mod 8). This would still allow solutions with d=-21 to exist, but it would rule out -29, -37, -45, -53, -61, -69; the next one that could work is then d=-77, followed by d=-101.
[/rambling]

Update: mod 5 considerations rule out any d that is 2 or 3 mod 5. Remaining candidates for d are -5, -21, -29, and any negative number that differs from one of those by a multiple of 40. Numerical search still hasn't turned up anything with d≠-5.

Paradoxica
Posts: 35
Joined: Wed Apr 09, 2014 1:33 am UTC

Re: Need help with non-linear Diophantine

Postby Paradoxica » Tue Apr 05, 2016 8:55 am UTC

pex wrote:[rambling]
Long and boring case bashing (mod 8) seems to indicate that the only non-square d for which there might be solutions are d = 3-8k, for positive integers k. Warning: this result is based on lots of ugly scribbling which I don't feel like typing up since I feel there ought to be a more elegant solution, so it might well be wrong. This would leave us with d=-5 (infinitely many solutions, as we've seen before), d=-13 (which I could rule out based on an ad hoc argument mod 5), d=-21 (which my modular arithmetic fails to rule out, but I haven't found a solution either), and then the untested d=-29, d=-37, etc.

If my ability to manipulate quadratic residues is to be trusted (and I'm not too sure of that), 2-d = 8k-1 must have an odd number of prime factors, all of which are -1 (mod 8), and 6-d = 8k-5 must also have an odd number of prime factors, all of which are +3 (mod 8). This would still allow solutions with d=-21 to exist, but it would rule out -29, -37, -45, -53, -61, -69; the next one that could work is then d=-77, followed by d=-101.
[/rambling]

Update: mod 5 considerations rule out any d that is 2 or 3 mod 5. Remaining candidates for d are -5, -21, -29, and any negative number that differs from one of those by a multiple of 40. Numerical search still hasn't turned up anything with d≠-5.


You probably missed something when bashing mod 8.

(-10,-1000,0,100) is a solution to the equation.
GENERATION -705 - 992 i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

pex
Posts: 10
Joined: Mon Mar 28, 2016 3:51 am UTC

Re: Need help with non-linear Diophantine

Postby pex » Tue Apr 05, 2016 1:01 pm UTC

I am not near my notes (not even sure if they haven't been recycled yet), but as I recall, the bashing did involve some quadratic residues, modulo (stuff that is only positive for negative d). That is, I was explicitly looking for negative d only, since the case of positive d was completely settled by Vieta jumping.

For what it's worth, I killed my numerical search after a couple of days, with no solutions for any -5 > d > -1 500 000. But never trust quick and dirty programmers with big integers, of course.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26767
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Need help with non-linear Diophantine

Postby gmalivuk » Tue Apr 05, 2016 9:38 pm UTC

Paradoxica wrote:
pex wrote:Long and boring case bashing (mod 8) seems to indicate that the only non-square d for which there might be solutions are d = 3-8k, for positive integers k.


You probably missed something when bashing mod 8.

(-10,-1000,0,100) is a solution to the equation.
And? That was already included earlier with (k, k3,0,k2).
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Paradoxica
Posts: 35
Joined: Wed Apr 09, 2014 1:33 am UTC

Re: Need help with non-linear Diophantine

Postby Paradoxica » Tue Apr 05, 2016 10:26 pm UTC

gmalivuk wrote:
Paradoxica wrote:
pex wrote:Long and boring case bashing (mod 8) seems to indicate that the only non-square d for which there might be solutions are d = 3-8k, for positive integers k.


You probably missed something when bashing mod 8.

(-10,-1000,0,100) is a solution to the equation.
And? That was already included earlier with (k, k3,0,k2).


Ah, ok, must have missed that when skimming through.

As for some legitimate progress, I have attempted the following:

c = ad-b

b(ad-b) = a^2 -d

adb - b^2 = a^2 - d

a^2 +adb + b^2 = d

This is obviously a General Pell Equation in a and b.

I think we can do something from here, but I know little about Pell equations, so I'll let someone else carry on from here.
GENERATION -705 - 992 i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests