From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: Diophantine problem Date: 27 Nov 1999 11:03:50 GMT Newsgroups: sci.math Keywords: arithmetic progression of four terms nearly square In article <383cf8e8@news.uia.ac.be>, Johan.Vervloet wrote: >I'm looking for all integers m, n and t such that > >t^2((m^2 + n^2)^2 + 8mn(m^2 - n^2)) - 4 > >the square is of another integer. I don't have a full solution but I can "reduce" the problem a little and make some comments about solutions, actually finding some non-trivial ones in the process (probably infinitely many, in fact). I'd like to know how the question arose. First let me replace some of the variables of the problem with others which will be smaller in general: Lemma. For an integer X, the predicate P(X) = "There is an integer t such that t^2*X-4 is the square is of another integer" implies the predicates Q(X) = "X>0, no prime factor of X is = 3 mod 4, and 16 does not divide X" and R(X) = "There are integers a, b with gcd(a,b)<=2 and X = a^2+b^2" (It may well be that R(X) is actually equivalent to P(X). I feel like I'm missing something obvious. I _can_ give a condition equivalent to P(X) involving the prime factorization of X, but I suspect it's not optimally phrased.) Proof. If t^2*X=4+v^2 then modulo each odd prime divisor p of X we have (v/2)^2 = -1 mod p, so that (Z/pZ)^* has an element v/2 of order 4, and hence 4 | (p-1). If 16 | X then v^2=12 mod 16, which is not true of any integer v. The statement X>0 is clear. So P(X) => Q(X). (Nearly the same argument shows R(X)=>Q(X).) Assume Q(X); then X = 2^f * Prod(p_k^e_k) with the product over primes =1 mod 4. It is well known that each such p_k may be written as a sum of two squares; equivalently, p_k = (a_k + i b_k)(a_k - i b_k) in the ring Z[i] of Gaussian integers. Then X is, up to a unit, the product of (1+i)^f * Prod( (a_k + i b_k)^e_k ) = a + b i, say, and its complex conjugate, i.e. X = a^2+b^2. (The possibility X=-(a^2+b^2) is excluded by the positivity assumption.) If a (rational) prime p divided both a and b, it would divide that product (1+i)^f * Prod( (a_k + i b_k)^e_k ), and so, since Z[i] is a Euclidean domain, would have to decompose in this ring into a product of primes among these factors. But primes p=3 mod 4 stay prime in Z[i] (and so are not equal to any of these primes) and primes = 1 mod 4 split into two complex conjugate prime factors, at most one of which is used in this factorization, contradiction. It is possible that 2|a and 2|b but if 4|a and 4|b then 16 | X , another contradiction. So Q(X) => R(X). Actually R(X) is equivalent to a weaker (?) statement than P(X), namely P'(X) = "There is a positive integer t such that t*X-4 is the square is of another integer". (Notice the "t^2" is gone, but still, P' => R as above.) Indeed if X = (a +bi)(a-bi), then simply choose integers r,s with a r - b s = d := gcd(a,b) <= 2, and then note (r+si)(a+bi) = d + (a s + b r) i so that we may set t = (2/d)^2 (r + s i)(r - s i). Moreoever, this value of t is nearly the only one which will serve: all other choices arise from similar (r' + s' i) = (r + s i) + n (b + a i). (There is the additional flexibility of choosing from among the finitely-many factorizations X = (a+bi)(a-bi), but an examination of the prime factorizations of t X = (2+vi)(2-vi) shows that this will then exhaust the set of possible values of t.) So the full predicate which is equivalent to P(X) is rather wordy: there must be a decomposition X = a^2+b^2 with low gcd and an integer n for which a certain Pellian equation can be solved (one which states that (r' + s' i) = (r + s i) + n (b + a i) is the square of some x + y i ). I haven't looked at the details yet. Let us now return to the original problem. With the Lemma in mind, it is necessary, and perhaps close to sufficient, to solve the Diophantine problem (*) (m^2 + n^2)^2 + 8mn(m^2 - n^2) = a^2+b^2 with additional provisos including gcd(a,b) <= 2. Now, this is a single equation, inhomogeneous but of degree 4, in four unknowns. As such, it describes a 3-dimensional variety in affine 4-space, on which we may look for integer points. I must confess up front that I don't think very much is known about this kind of situation in general. We have a very good understanding of where to find integer points on _curves_ (often only finitely many exist) but surfaces and 3-folds are another matter. It's probably better to scale by, say, n^4; then we're looking for _rational_ points on the (elliptic) surface (x^2 + 1)^2 + 8x(x^2 - 1) = y^2+z^2 where x = m/n, y=a/n^2, z=b/n^2. We can use known information about integral and rational points on embedded subvarieties to study solutions to (*) of special types. For example, if we hold m and n fixed (i.e., intersect the 3-fold with a 2-plane in 4-space to get a curve) we get a rational curve on which we can locate the finitely many integral points which may exist (and, if there are any, easily parameterize the infinitely many rational points). For instance, taking m=8, n=-1 we need a^2+b^2=193; the only solutions are {a,b}={7,12} (up to sign). So this solves (*) completely in this case. Does it solve the original equation? We need to see whether there really is a t or not. We have (7+12i)(7+4i)= 1 + 112 i, but 7+4i is not a square; on the other hand, blindly following some calculations with maple I find (7+4i) - 113787856328029660*(12+7i) = (328128896 -1213722723 i)^2 so taking t to be (2/d=2)*(the norm of this complex number) ought to work. And indeed, 3161582841433427090^2 * 193 = 4 + 43922112542619448536^2. I suppose this isn't the smallest possible t but I didn't really look. Alternatively, we may hold a and b fixed (e.g. taking a=2 is a good idea!) and look for solutions (m,n) to (*). This is then known as a Thue equation (a homogeneous, irreducible, binary form set equal to a constant). It is known that there are only finitely many solutions to this for a fixed a^2+b^2, and indeed they can be found fairly readily with software. Indeed, one may simultaneously solve many of these by solving the "norm inequalities" |F(m,n)| <= C . For example, there are no solutions to (*) with a^2+b^2 <= 200 except those with |m|, |n| <= 2 or {|m|,|n|}={1,8} (the case considered in the last paragraph). Finally, we may hold, say, n and b fixed, or more precisely the ratio z=b/n^2. In that case, x=m/n and y= a/n^2 will be coordinates of rational points on the related variety (**) x^4 - 8 x^3 + 2 x^2 + 8 x + (1 - z^2) = y^2 which describes an elliptic curve. This time for each fixed z we might obtain infinitely many rational points, each giving a distinct integer solution to (*). For example, when z=0 we have a curve with only 8 (torsion) points; the solutions to (**) have |x|, |y| in {0,1,2}, meaning that the only primitive solutions to (*) with b=0 are those with (m,n)=(+-1, +-2) or (0, +-1). Taking z=1, however, gives a curve of rank 1 (and no torsion), meaning that there are infinitely many solutions to the equation (m^2 + n^2)^2 + 8mn(m^2 - n^2) = a^2 + (n^2)^2 A few small ones have x = m/n = -4/7, 49/48, -4608/3745, ... Or we may build on some previous solutions, e.g. with b=7, n=-1; this leads to the curve (**) with z=7, which turns out to have rank 2 (again, no torsion); some small points are those with x = m/n = -8 (of course), 28/13, 97/48, 124/37, 183/22, -871/70, ... I don't know if it helps, really, to note that (*) asks for rational integers which are both norms from a certain small subgroup of a quartic extension field, and at the same time norms from the ring of Gaussian integers. (Probably this idea can be used to create more solutions, but is of limited use in showing these are the only solutions.) No known mechanism will let you find all the rational points on elliptic surfaces, and indeed I don't know offhand of _any_ elliptic surface in which all rational points are known except for example cases in which there are no rational points at all (because of a local obstruction, say). So I would be surprised to see a complete solution to the original problem. dave ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: Diophantine problem Date: 28 Nov 1999 07:53:43 GMT Newsgroups: sci.math I should correct some undue optimism I expressed in a previous post. Recall that in article <383cf8e8@news.uia.ac.be>, Johan.Vervloet wrote: >I'm looking for all integers m, n and t such that > >t^2((m^2 + n^2)^2 + 8mn(m^2 - n^2)) - 4 > >the square is of another integer. In response, in article <81odqm$dgi$1@gannett.math.niu.edu>, I wrote: >Lemma. For an integer X, the predicate > P(X) = "There is an integer t such that t^2*X-4 is > the square is of another integer" >implies the predicates > Q(X) = "X>0, no prime factor of X is = 3 mod 4, and 16 does not divide X" >and > R(X) = "There are integers a, b with gcd(a,b)<=2 and X = a^2+b^2" > >(It may well be that R(X) is actually equivalent to P(X). Well, it's not. For some integers X for which Q(X) and R(X) hold, P(X) fails to hold. Easy example: any X which is a perfect square! Duh! But there is something else going on which is more complicated. The predicate P(X) states that the equation v^2 - X*t^2 = -4 is solvable, i.e. that -4 is in the image of the norm map from Z[sqrt(X)] to Z. As I showed in the previous post, the conditions Q(X) and R(X) are necessary, but they turn out not to be sufficient, as is seen from examples like X = 5*41, 13*17, 5*61, and 13*29. (I checked all other odd X up to 500 and in those cases Q(X) => P(X).) I can't even state a reasonable sufficient condition to allow concluding P(X) from R(X). So when I said, >Let us now return to the original problem. With the Lemma in mind, it is >necessary, and perhaps close to sufficient, to solve the Diophantine problem >(*) (m^2 + n^2)^2 + 8mn(m^2 - n^2) = a^2+b^2 >with additional provisos including gcd(a,b) <= 2. I was correct, but perhaps misleading with the "close to sufficient" bit. Separately, it turns out I went a bit overboard here: >For instance, taking >m=8, n=-1 we need a^2+b^2=193; the only solutions are {a,b}={7,12} >(up to sign). So this solves (*) completely in this case. Does it solve >the original equation? We need to see whether there really is a t or not. [...] >And indeed, 3161582841433427090^2 * 193 = 4 + 43922112542619448536^2. >I suppose this isn't the smallest possible t but I didn't really look. Now I looked. The minimal t is 896073208080. The other small values of X which arise, for which R(X) holds, also make P(X) true. Indeed, the quartic polynomial F(m,n) only takes on a few such values: X = 1, 4, 73, 193, 241, 292, 409, 601, ..., thus extending this remark: >there are no solutions to (*) with a^2+b^2 <= 200 except those with >|m|, |n| <= 2 or {|m|,|n|}={1,8} (the case considered in the last paragraph). The new list uses |m|, |n| <= 3 except for {|m|,|n|}={4,5}, {1,8}, {10,13}. In each case we can make t^2*X - 4 a square, using these (minimal) t 2, 1, 250, 896073208080, 9148450, 125, 11068353370, 11378061539690, ... respectively. I have no proof that I will _always_ be able to find a t, however, as we consider successively larger values of X. >Finally, we may hold, say, n and b fixed, or more precisely the >ratio z=b/n^2. In that case, x=m/n and y= a/n^2 will be coordinates of >rational points on the related variety >(**) x^4 - 8 x^3 + 2 x^2 + 8 x + (1 - z^2) = y^2 >which describes an elliptic curve. This time for each fixed z we might >obtain infinitely many rational points, each giving a distinct integer >solution to (*). > >Taking z=1, however, gives a curve of rank 1 (and no torsion), meaning >that there are infinitely many solutions to the equation > (m^2 + n^2)^2 + 8mn(m^2 - n^2) = a^2 + (n^2)^2 >A few small ones have x = m/n = -4/7, 49/48, -4608/3745, ... So I have a good description of infinitely many pairs (m,n) here, but now I don't really know that P(X) is true for each such X = F(m,n) (even though R(X) is true by construction). Well, the first few look OK: taking m=-4, n=7 we find the smallest value for t is t = 439983535637249526856848515197636089653704644999715721438498210 and taking m=49, n=48 requires a t at least as large as the huge 133276534761602333459678214788926840783154888736484688444077451122550285484\ 49987217645055409760093576566773998462439667130810036889496868117184038\ 17800890070052892113581113062543222738791828021290967787175329919941865\ 32906238991694983243441133139637102675782960638809422054296278532564762\ 74225314676497842824525777376490873741347207761280573051215902126545015\ 605176237894003138 I haven't yet determined whether or not the Pellian equation corresponding to m=-4608, n=3745 is even solvable at all... A final remark: the elliptic surface described by (**) has infinitely many rational points. Typically, but not always, that means there is a rational curve in the surface. In other words, it is reasonable to hope for solutions to (**) with x, y, and z being rational functions of another variable. I haven't tried to find such a one, but it might be instructive to have one. dave ============================================================================== From: jpr2718@aol.com Subject: Re: Diophantine problem Date: Sun, 28 Nov 1999 13:18:26 GMT Newsgroups: sci.math In article <383cf8e8@news.uia.ac.be>, jvvloet@uia.ua.ac.be (Johan.Vervloet) wrote: > I'm looking for all integers m, n and t such that > t^2((m^2 + n^2)^2 + 8mn(m^2 - n^2)) - 4 > the square is of another integer. > Is there a way to simplify the problem ? Let d = d(m, n) = (m^2 + n^2)^2 + 8mn(m^2 - n^2). Then the equation in question can be written z^2 - d*(t^2) = -4, a form of Pell's equation. As d(m, n) = d(n, -m) = d(-n, m) = d(-m, -n), and d(km, kn) = (k^4)*d (m, n), any solution is associated with a solution with m and n nonnegative and relatively prime. Also, d(2r+1, 2s+1) = 4*d(r+s+1, r- s), we can take one of m or n to be even. We must have d > = 4, else z^2 < 0. Note that m < n is possible. For a given m and n, the continued fraction method can be used to determine whether z^2 - d*(t^2) = -4 has solutions. Essentially, if m and n are reduced as above, so d is congruent to 1 modulo 4, then there are solutions exactly when the continued fraction expansion of (1 + sqrt (d))/2 has an odd period. As there are no known a priori methods for determining whether z^2 - d*t^2 = -4 has solutions for a given d (although many special cases are known), it seems unlikely there will be an easy way to parameterize solutions to the equation in question. [Dave Rusin has given some necessary conditions, but they are not sufficient. For example, d=34 meets Rusin's conditions P and Q, but the equation z^2-34t^2=-4 does not have solutions.] So, one can generate all solutions by searching on m, n relatively prime, positive integers, with one of m, n even, so that d(m, n) >= 4, and looking for solutions to z^2 - d*(t^2) = -4 (and then treating the case m=1, n=0). Also note a relationship between your equation and arithmetic progressions whose first three terms are squares. Three-term arithmetic progressions of relatively prime squares , a^2, b^2, c^2 can be parameterized by a=abs(m^2-n^2-2mn), b=m^2+n^2, c=m^2-n^2+2mn, where m and n are relatively prime, and exactly one is even. [To see this, note that a and c have the same parity, and ((c-a)/2)^2 + ((c+a)/2)^2 = b^2, so take (c-a)/2 = m^2-n^2 and (c+a)/2 = 2mn, or vice versa, and b=m^2+n^2.] The difference between terms is 4mn(m^2-n^2), so the fourth term of such a progression is (m^2+n^2)^2 + 8mn(m^2-n^2). The original equation is essentially asking for an arithmetic progression so that the first three terms are squares and the fourth term is 4 more than a square. John Robertson Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: Dave Rusin Subject: Embeded curve Date: Mon, 29 Nov 1999 01:23:04 -0600 (CST) Newsgroups: [missing] To: rusin@math.niu.edu It is easy to find a rational curve in the elliptic surfaces Q(x)=y^2+z^2 where Q is a monic quartic. Simply complete the square to write Q(x)=(q(x))^2 + L(x) where q is a monic quadratic; then we may take x = L^(-1)(z^2) and y = q(x) = q(L^(-1)(z^2)) to parameterize a solution by the parameter z. Adjusting the free parameter a bit in this case we are led to the solution x = 3 u^2 - 1 , y = 9 u^4 + 18 u^2 - 2, z = 12 u. This gives a family of solutions to F(m,n) = a^2+b^2 in integers: for arbitrary (coprime) (p, q) take m = 3p^2 + q^2, n = q^2, a = 12 p q^3, b = 9 p^4 + 18 p^2q^2 - 2 q^4. This leads to an X = 81 p^8 + 324 p^6 q^2 + 288 p^4 q^4 + 72 p^2 q^6 + 4 q^8 which is the sum of two squares, but for which it's not clear that v^2 - X t^2 = -4 is solvable. (It often is, for small pairs of coprime p,q, removing a common factor of 3 if 3|q; but e.g. p=5, q=3 (?) gives X=1149649, for which the Pell equation is insoluble.) dave