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