From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: 4/N=(1/x)+(1/y)+(1/z): Solution Progress [LONG] Date: 1 Jul 1999 08:58:44 GMT The recent set of posts about the 4/N problem suggests it might be appropriate to show how to obtain parametric solutions for many families of values of N. Unfortunately these can't be used to resolve the problem completely, but it's instructive to push the methods to their limits. The problem, again, is this: show that for every positive integer N there are positive integers x,y,z with 4/N = 1/x + 1/y + 1/z. See section D11 of "Unsolved Problems in Number Theory", R. Guy. See also recent posts by David Eppstein and others. All the parametric solutions I have seen implicitly use the following procedure: given any solution {P,Q,R} in the polynomial ring Q[X] to the equation (*) 1/X = 1/P + 1/Q + 1/R we obtain a collection of formulas 4/N = 1/(P(N)/4) + 1/(Q(N)/4) + 1/(R(N)/4) which solve the 4/N problem in integers whenever N is such that the three denominators are integral. For specific P,Q,R they will indeed be integral if N belongs to one of a few congruence classes modulo the least common multiple of the denominators of P/4, Q/4, and R/4. For example, from the identity 1/X = 1/(X+1) + 1/(2X^2+2X) + 1/(2X^2+2X) we obtain a solution to the 4/N problem for any N with (N+1)/4, (N^2+N)/2, (N^2+N)/2 all integral, that is, for any N=3 mod 4. So the 4/N problem leads to a sort of "Diophantine" problem in the principal ideal ring Q[X]. The purpose of this post is to list the solutions to this latter problem. Theorem. The complete set of solutions in Q[X] to the equation (*) is that either {P,Q,R} = {X, F, -F} for any polynomial F in Q[X], or else {P,Q,R} is in one of the following 2-parameter families of triples: 1. { a X, b X, (ab/(ab-a-b)) X } 2. { a X, (a/(a-1)) (X+c), (a/c/(a-1)) X (X+c) } 3. { a (X+c), (a/(a-1)) (X+c), (1/c) X (X+c) } 4. { (1-c/d) (X+c), (1-d/c) (X+d), (1/(cd)) X (X+c) (X+d) } 5. { X+c, a X (X+c), (a/(ac-1)) X (X+c) } 6. { X+c, (1/d) X (X+d), (1/(c-d)) (X+c) (X+d) } 7. { X+c, (1/c) X (X+c+d), (1/(cd)) X (X+c) (X+c+d) } 8. { X+c, (1/c) X (X+c+d), (1/(cd)) X (X+c) (X+c+d) } 9. { X+c, (1/c) (X^2 + cX + d), (1/(cd)) X (X+c) (X^2 + cX + d) } In each case the parameters a,b,c,d may be any rational numbers not making the numerators nor denominators of any of the three expressions vanish. Note that there is no reason to expect a priori that P, Q, R need be of low degree nor that they factor into linear factors, but these statements turn out almost always to be true. We can even sketch the proof of this result. Let's first warm up with a simpler proposition: Prop. The solutions in Q[X] to (**) 1/X = 1/P + 1/Q are precisely those in the two one-parameter families {P,Q} = A. { a X, (a/(a-1)) X } B. { X+c, (1/c) X (X+c) }. Proof: It is easily checked that these P,Q do give solutions. Conversely, view any other solutions as rational functions on the Riemann sphere; without loss of generality assume deg(P) <= deg(Q). Setting X = 1/Y gives Y = Y^deg(P) / P'(Y) + Y^deg(Q) / Q'(Y) for certain polynomials P', Q' not vanishing at the origin. Then comparing the Taylor series of both sides as Y=0 we see deg(P)=1 : P is linear. If Q is also linear, then comparing the poles on both sides of (**) shows P and Q are scalar multiples of X giving formula (A). IF instead Q is not linear, then the Taylor series argument shows P is monic, so that (**) reads 1/X = 1/(X+c) + 1/Q for some c, necessarily nonzero. Solve for Q to get formula (B). This proves the proposition. The main theorem may be proved similarly; naturally there will be many separate cases. As in the proof of the proposition, we see P (say) is linear, and monic unless there is another linear polynomial (Q or R). If P = X, then 1/Q + 1/R = 0, giving the degenerate case. If P = aX for any other multiplier a, we combine terms and scale (1/X - 1/P) = 1/Q + 1/R to reduce to the situation of the Proposition, from which we deduce solutions (1) and (2). Otherwise, P = a(X+c) for some nonzero c. Note that if then Q and R are both linear as well, then by comparing poles at X =0 in (*) we see one of P, Q, or R must be a scalar multiple of X, reducing to the previous two short paragraphs. So we may assume at least R is nonlinear, and if Q is linear, it is not a multiple of X. Now, if Q is linear and has the same root as P, then we may combine terms in (*) to obtain a solution { k*(X+c), R } to 1/X = 1/(k(X+c)) + 1/R for some suitable k; comparing to the Proposition we see k=1 and R = X (X+c)/c , which yields solution (3). If Q is any other linear polynomial it has the form Q = b (X+d) for some d different from 0 and c. This time, counting poles in (*) shows R must be a scalar multiple of X (X+c) (X+d). Clearing denominators in (*) and then comparing coefficients of powers of X leads to solution (4). So in the remainder we may assume only P is linear; the Taylor argument forces it to be X+c for some nonzero c. We conclude from (***) 1/X - 1/(X+c) = 1/Q + 1/R that there are poles at X=0 and X=-c on the right side. We consider two cases: either there is a polynomial among {Q,R} which vanishes at both these places, or else Q (say) vanishes at X=0 and R vanishes at X=-c, but neither polynomial with both roots. The latter case is actually easier. Writing Q = X S and R = (X+c) T, equation (***) becomes (1/X) (1 - 1/S) = (1/(X+c)) (1 + 1/T ) Our premises force S and T to have the same poles, so write S = b T for some constant b and solve for T. Reorganizing somewhat leads to (5). In the last case we have Q = X (X+c) S for some polynomial S. Clearing some denominators in (***) shows c - 1/S = X (X+c)/R and the usual comparison of poles shows R = d S F for some constant d where F is one of the polynomials 1, X, X+c, X(X+c). In each case, substitute for R in (***) and solve for S; we obtain solutions (9), (7), (8), (6) respectively. This completes the proof of the main theorem. For applications to the integral 4/N problem, it seems the favored identity is (2): for any rational a and c except a=0, a=1, c=0 we have 4/N = 1/x + 1/y + 1/z where x = (a/4) N, y = (a/4)/(a-1) (N+c), and z = (a/4)/c/(a-1) N (N+c). Now, we need x,y, and z integral; we would like to choose a,c to make these x,y,z integral for as many N as possible. For example, we try a = 4 a' for some integer a' so that x=a'N is integral. Writing c = m/n in lowest terms we see from the formulas for y and z that it is best if a' is itself divisible by m and n, say a' = k m n. Then x = (k m n) N, y = (k m) (n N + m)/(4kmn-1), and z=(k n) N (nN+m)/(4kmn-1) are all integral for those N with n N + m divisible by 4 k m n - 1. Stated a little differently, we have many infinite families of solutions to the 4/N problem: Corollary: for any positive integers n,m,k we know the 4/N problem is solvable for all N congruent to -m/n mod 4 k m n - 1. For example (taking k=m=n=1) the problem is solvable for all N=-1 mod 3. One method of verifying the 4/N problem is then simply to test small combinations n,m,k to see whether (n N + m) = 0 mod (4nmk - 1). This process is really quite amazingly effective. I ran a short Maple program to test whether or not this is true for small N. Now, some identities of the sorts already discussed are sufficient to handle N = 3,5,7 mod 8, as well as deducing a solution for composite N from a solution from a prime factor. Thus it is sufficient to check the conjecture for primes N = 1 mod 8. It is hard to fail! Without using any of the other eight polynomial identities, and without trying to eke more out of identity (2) than we have already done, we find that very large values of N are proven possible by very small values of n,m,k. Indeed, here's what I found by machine. For any N, loop over small integers n,m,k to find a combination with N = -m/n mod 4 k m n - 1; try them in order of increasing n+m+k. Let us simply note the values of N where this expression reaches a new high (again, limited to prime N = 1 mod 8); here are the leaders: N n+m+k 17 3 73 4 193 5 1201 7 2521 8 3049 9 3361 11 26041 12 33289 14 66889 16 167521 18 833281 23 950401 35 50370049 39 53865529 41 169257001 42 255844681 46 (Yes, m*n*k would be a better measure than m+n+k but the programming loop works a tad faster this way...) For example we can verify the 4/N conjecture for any N up to 50 million by simply looping over at worst a few thousand iterations: for n to 33 do for m to 34-n do for k to 35-n-m do if ((n*N+m) mod (4*k*m*n-1))=0 then print(n,m,k) fi:od:od:od: and making sure there's at least one answer reported. Of course for larger N we may have to adjust the search bounds (and in any event this search routine isn't maximally efficient), but no failures have been found for primes up to about 10^12. It strikes me as really odd that not only can solutions always (?) be found, but that they can be found with x,y,z such simple linear combinations of 1 and N. It is easy to speculate that this mechanism could be extended to give a real proof of the 4/N conjecture. This enthusiasm must be tempered by the observation that the test loop shown above _does_ fail for some N. Indeed, Schinzel has proved that if N is a perfect square, NONE of the solutions of the main theorem can be used to derive a solution to 4/N=1/x+1/y+1/z [Secondhand report -- I haven't seen his paper.] Interestingly, the perfect squares seem to be nearly the only counter- examples, but not quite. One may show there are no k,m,n for which 288n+m is a multiple of 4kmn-1 and it appears to be true (I haven't pursued it completely) that this is also a problem when N=336 or N=4545. (David M Einstein mentioned these in a recent post.) AFAIK no more such N have been found, nor is there a proof that no more exist. (A few other N require rather large k,m,n -- at least compared to what one might expect given the data for primes = 1 mod 24; try N=330, N=1302, N=19602, N=180310, N=743799, ...) Conclusion: Parametric solutions are fun and effective but if you want to prove the 4/N conjecture you'll need something else besides classes of polynomial solutions; they're all "known". dave