From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Diophantine equation question Date: 18 Nov 1998 21:35:10 GMT "Roger Lipsett" writes: > I'm trying to find integral solutions to the equation > z^^2 = 2*x^^4 + 4*x^^3 + 2*x^^2 + 1 > I have one solution (x=3, z=17). All the solutions are small (z^2 = 1, 9, or 289). This equation describes an Elliptic Curve; that is, if we seek solutions (x,z) among the complex numbers, the solution set will be a 1-holed torus (with proper attention paid to points at infinity). Arithmetically, elliptic curves present two problems: to find the rational points, and to find the integral points. The former question is usually considered easier, but in cases like this one, the two may be studied more or less in tandem by Fermat's method of descent. The feature making this study possible with rational integers is that the quartic has a 2-group for a Galois group the quartic may be expressed as a composite Q1 o Q2 of quadratics the corresponding elliptic curve has 2-torsion the curve in Weierstrass form involves a cubic with a rational root (all these characterizations are roughly equivalent). I won't give the most general procedures here; Richard Bumby's pointer > For a survey of methods that might be tried, see "How to > solve a Diophantine equation --- a number theoretic excursion" by > R. J. Stroeker in Amer. Math. Monthly, 91 (1974), 385--392. is a good one for more information. (Bumby was too polite to point out that this article grew out of his prodding the author to solve just such a problem!) Stroeker is part of a small crowd of researchers who have facilitated this kind of probe. Further information about elliptic curves is at index/14H52.html The basic process in the descent procedure is to present the curve with a pair of quadratic equations, find a parameterization of the solution set of one of them, and use this to reduce the original problem to a finite set of other pairs of quadratic equations. It is indeed a "reduction" since the other pairs are often easily seen to have no solution, and when they do have solutions these are "smaller" than the solutions to the original. There are reasons why this procedure must fail in some cases, but for "nice" curves we can use this to find all rational points and at least reduce the search for integral points to a better-understood kind of problem (a Thue equation); actually descent can be used all by itself for integral solutions but requires more patience. Here it seems easier to let Maple do the dirty work of finding the finitely-many solutions to each Thue equation. We begin by recasting the original problem z^2 = 2*x^4 + 4*x^3 + 2*x^2 + 1 first as (z-1) (z+1) = 2 (x^2+x)^2, and then as a set of equations X Y = 2 Z^2 , Z = x^2+x , and Y-X=2 First note that integral solutions to the first equation are parameterized as (X,Y,Z) = ( r*u^2, r*2v^2, r*uv ) where we may take (u,v) to be any relatively prime pair of integers, and any rational r making these expressions integral. This is the common form of parameterized solutions to any integral quadratic equation. Note that there are few choices for the denominator of r=p/q: it must divide both u^2 and 2v^2, so since gcd(u,v)=1, this q | 2. Indeed, we may alternately parameterize the integral solutions to XY=2Z^2 as the images of the _two_ parameterizations (X,Y,Z) = r*(u^2, 2v^2, uv) (X,Y,Z) = r*(2w^2, v^2, wv) with _integer_ r and coprime (u,v) resp. (v,w). With the first parameterization our equations become (reorganizing slightly): r*(2v^2-u^2) = 2 4ruv + 1 = s^2 which limits us to r in {1, -1, 2, -2}. Thus we seek integer solutions to any of these sets of equations (with u,v coprime) : (2v^2-u^2) = 2 4uv + 1 = s^2 (2v^2-u^2) = -2 -4uv + 1 = s^2 (2v^2-u^2) = 1 8uv + 1 = s^2 (2v^2-u^2) = -1 -8uv + 1 = s^2 The second parameterization leads to another four sets, involving (v,w,s), but these reduce to the same four sets upon substituting {v=-u, w=v}. The next trick is to note that in each of these cases, a linear combination of the two equations is another homogeneous quadratic in three variables. That is, the variables must in particular satisfy (*) 2v^2-u^2+8uv - 2s^2 = 0 in the first case, and similar equations in the other cases. (We will treat those other three cases briefly at the end.) We can parameterize the set of solutions to (*), too. The technique is well-known: divide by s^2, find a rational point (u/s,v/s) (say, (0,-1) ), parameterize points on the plane conic via slopes of lines through this point, then clear denominators. I get the parameterization (u,v,s) = r*(4ab+8b^2, 2a^2+b^2, 2a^2+8ab-b^2) in this way. There is again a restriction on the possible denominators q of r, since q must divide 4ab+8b^2 and 2a^2+b^2, and hence any integral linear combination. Such a combination is the resultant of these two polynomials of a, namely 144b^2; likewise the resultant of these, viewed as polynomials in b, is 144a^2, so gcd(a,b)=1 implies q | 144. (But note e.g. that 2|q => 2|b, and then 4|q => 2|a too, contradiction.) So we obtain six integer parameterizations satisfying (*): (u,v,s) = (4ab+8b^2, 2a^2+b^2, 2a^2+8ab-b^2) (u,v,s) = (4bc, 3b^2-8bc+6c^2, -3b^2+6c^2) (a=-2b+3c) (u,v,s) = (4bd, b^2-8bd+18d^2, -b^2+18d^2) (a=-2b+9d) (u,v,s) = (4ae+16e^2, a^2+2e^2, a^2+8ae-4e^2) (b=2e) (u,v,s) = (4ec, 6e^2-8ec+3c^2, -6e^2+3c^2) (a=-4e+3c, b=2e) (u,v,s) = (4ed, 2e^2-8ed+9d^2, -2e^2+9d^2) (a=-4e+9d, b=2e) where we drop the common integer factor r since we want gcd(u,v)=1; the complete solution now allows only r= +- 1 (which is irrelevant below). Now, each of these solves (*), which we obtained as a linear combination of (2v^2-u^2) = 2 4uv + 1 = s^2 But we only have a solution to this pair if, say, the second is satisfied. Substituting in our parameterizations we see the remaining condition is that s^2-4uv = 1, i.e., one of these must equal 1: -4*a^4+4*a^2*b^2+32*a*b^3+31*b^4 -9*b^4+48*b^3*c-92*b^2*c^2+96*b*c^3-36*c^4 -b^4+16*b^3*d-92*b^2*d^2+288*b*d^3-324*d^4 -a^4+4*a^2*e^2+64*a*e^3+124*e^4 -9*c^4+48*c^3*e-92*c^2*e^2+96*c*e^3-36*e^4 -81*d^4+144*d^3*e-92*d^2*e^2+32*d*e^3-4*e^4 The second and fifth of these are impossible, as is seen by reducing modulo 16. This is an important feature of the use of descent to determine rational (and integral) points on an elliptic curve: we use p-adic restrictions on these descendant curves to show that the original curve has no points (of a certain type, perhaps) -- even though there may have been no p-adic constraints on the original curve. The other four are possible and indeed each has a +/- pair of trivial solutions (variables in {0,1,-1}). However, we can search for other solutions effectively. These are Thue equations: homogeneous irreducible polynomials in two variables of degree greater than 3, set equal to a constant. It's fairly easy to convince yourself each has at most a finite number of solutions. Better, recent work has shown that it is possible to find all those solutions effectively. Roughly speaking, the reason this succeeds is that a solution (a,b) to the first equation, say, would determine a rational number x=a/b which makes -4x^4+4x^2+32x+31 too small: this is an irreducible quartic equation, and so its roots cannot be approximated by rational numbers a/b with an error less than about 1/b^2, whereas a solution to the Thue equation gives an error roughly 1/b^4; hence there are only finitely many such solutions. Maple has a Thue solver. It does not seem to have the complete algorithm -- it searches only as far as solutions with variables up to 10 digits or so -- but I have no real doubt that these solution sets are complete. Thus with Maple we determine that the only solutions to the previous quartics are the trivial ones. Actually it's easy to ask Maple to find all solutions to |-4a^4+4a^2b^2+32ab^3+31b^4| <= 324, which handles all 6 subcases at once. Working backwards, we find the only solutions to (2v^2-u^2) = 2 4uv + 1 = s^2 to be (u,v) = (0,1) or (4,3) (or their negatives). These correspond, respectively, to (X,Y,Z) = (0,2,0) and (16, 18, 12), and finally to (x,z) = (0,1) or (-1,1), and to (3,17) or (-4,17). We are one-quarter done! But the other three cases can be done more speedily. For example our fourth case (in which the first gcd r was -2) was (2v^2-u^2) = -1 -8uv + 1 = s^2 from which we deduce an equation corresponding to (*): 2v^2-u^2+8uv+s^2=0 which admits a parameterization (u,v,s)=(p/q)(2a^2+b^2, -2a(-b+4a), 2a^2+8ab-b^2) We must have p=+-1 by coprimality and q | 72 by integrality. Substituting into s^2+8uv=1 gives then the Thue equation 4 3 2 2 4 2 -124 a + 64 a b - 4 a b + b = q Maple found 73 pairs (a,b) making the quartic at most 72^2 in absolute value; the only pairs making the quartic a perfect square are (a,b)= (0,0), (0,1), (1,2), (1,4), (1,-5) and their negatives. These lead to (u,v,s)=(1,0,-1), (3,-2,7), (1,0,1), (3,-2,-7), respectively, which in turn give (X,Y,Z)=(-2,0,0), (-18,-16,12), (-2,0,0), (-18,-16,12) and (x,z)=(-1,-1), (3,-17), (0,-1), (-4,-17) -- exactly the negatives of the solutions in the previous paragraph. From our second case (first gcd r=-1) (2v^2-u^2) = -2 -4uv + 1 = s^2 we get an equation corresponding to (*): 2v^2-u^2+8uv+2s^2=0 whose integer points we parameterize with (u,v,s) = (p/q)(4a^2+10b^2+4ab, -14a^2+b^2+4ab, 6a^2-3b^2+24ab) in which q | 11664 and p=+-1 if we wish relative primality. Then s^2+4uv=1 requires 4 3 2 2 3 4 2 -188 a + 128 a b + 60 a b + 32 a b + 49 b = q . Now, 2|q is only possible if b is even; then 4|q would imply a is also even, a contradiction. If 3|q then we discover a=b mod 3; but writing a=b+3d then shows gcd(u,v) to be a multiple of 9, so by coprimality we need 9|q. Further, no coprime combination of b and d allows 27|u. Thus only |q|=1, 2, 9, 18 are possible. Maple reports the solutions (a,b) = (1,1) and (1,-2) and their negatives, giving (u,v,s)=(2,-1,3) and (2,-1,-3), then (X,Y,Z)=(-4, -2, 2) for both, then (x,z)=(1, -3) and (-2,-3). From our third case (first gcd r=2) (2v^2-u^2) = 1 8uv + 1 = s^2 we deduce the equation 2v^2-u^2+8uv-s^2=0 which we parameterize with (u,v,s)=(p/q)(2a^2-4ab-7b^2, -10a^2+2ab-b^2, 6a^2+24ab-3b^2) again with q|11664 and p=+-1, now with the constraint s^2-8uv=1: 4 3 2 2 3 4 2 196 a - 64 a b + 60 a b - 64 a b - 47 b = q As in the previous paragraph we reason |q|=1,2,9, or 18, use Maple to find solutions (a,b)=(1,1) or (1,-2), then (u,v,s)=(1,1,-3) or (1,1,3), then (X,Y,Z)=(2,4,4), then (x,z)=(-2,3) or (1,3). SO! Our complete list of integral solutions comes from just the three values z^2 = 1, 9, or 289: these correspond respectively to z={+-1}, {+-3}, {+-17} and to x={0,-1}, {1,-2}, {3,-4}. dave