Erdős–Straus conjecture

The Erdős–Straus conjecture states that for all integers "n" ≥ 2, the rational number 4/"n" can be expressed as the sum of three unit fractions. That is, there exist positive integers "x", "y", and "z" such that :$frac4n\; =\; frac1x\; +\; frac1y\; +\; frac1z.$The sum of these unit fractions is an Egyptian fraction representation of the number 4/"n". For instance, for "n" = 1801, there exists a solution with "x" = 451, "y" = 295364, and "z" = 3249004::$frac4\{1801\}\; =\; frac1\{451\}\; +\; frac1\{295364\}\; +\; frac1\{3249004\}.$

If we multiply both sides of this equation by "nxyz" we find an equivalent form 4"xyz"="n"("xy"+"xz"+"yz") for the problem as a Diophantine equation. The restriction that "x", "y", and "z" be positive is essential to the difficulty of the problem, for if negative values were allowed the problem could be solved trivially via one of the two identities 4/(4"k"+1) = 1/"k" - 1/"k"(4"k"+1) and 4/(4"k"-1) = 1/"k" + 1/"k"(4"k"-1).

If "n" is a composite number, "n" = "pq", then an expansion for 4/"n" could be found immediately from an expansion for 4/"p" or 4/"q". Therefore, if a counterexample to the Erdős–Straus conjecture exists, the smallest "n" forming a counterexample would have to be a prime number.

Paul Erdős and Ernst G. Straus formulated the conjecture in 1948 (see, e.g., Elsholtz) but the earliest published reference to it appears to be a 1950 paper of Erdős.

Modular identities

The Hasse principle for Diophantine equations asserts that, to solve such an equation over the integers, we should combine solutions obtained modulo each possible prime number. On the face of it this principle makes little sense for the Erdős–Straus conjecture, as the equation 4"xyz"="n"("xy"+"xz"+"yz") is easily solvable modulo any prime. Nevertheless, modular identities have proven a very important tool in the study of the conjecture.

For values of "n" satisfying certain congruence relations, we can find an expansion for 4/"n" automatically as an instance of a polynomial identity. For instance, whenever "n" ≡ 2 (mod 3), the equation is solvable, because 4/(3"x"+2) = 1/(3"x"+2) + 1/("x"+1) + 1/("x"+1)(3"x"+2) for all "x", and plugging in "x" = ("n"-2)/3 gives the desired expansion for 4/"n". A greedy algorithm finds a solution in three or fewer terms whenever "n" is not 1 or 17 (mod 24), and the n ≡ 17 (mod 24) case is covered by the 2 (mod 3) relation, so the only values of "n" for which these two methods do not find expansions in three or fewer terms are those congruent to 1 (mod 24).

If we could find sufficiently many such congruences to cover all values of "n", the problem would be solved. However, as Mordell showed, an identity of this form for values of "n" congruent to "r" mod "p" can exist only when "r" is not a quadratic residue modulo "p". Mordell lists identities of this form for any "n" that is 2 mod 3 (above), 3 mod 4, 5 mod 8, 2 or 3 mod 5, or 3, 5, or 6 mod 7, covering all the numbers that are not quadratic residues for those bases. However, for larger bases, not all nonresidues are known to be covered by relations of this type.

From Mordell's identities one can conclude that there exists a solution for all "n" except possibly those that are 1, 121, 169, 289, 361, or 529 modulo 840. 1009 is the smallest prime of this form. By combining larger classes of modular identities, Webb and others showed that the fraction of "n" in the interval [1,"N"] that can be counterexamples to the conjecture tends to zero in the limit as "N" goes to infinity.

Despite Mordell's result limiting the form these congruence identities can take, there is still some hope of using modular identities to prove the Erdős–Straus conjecture. No prime number can be a square, so by the Hasse-Minkowski theorem, whenever "p" is prime, there exists a larger prime "q" such that "p" is not a quadratic residue modulo "q". One possible approach to proving the conjecture would be to find for each prime "p" a larger prime "q" and a congruence solving the 4/"n" problem for "n" ≡ "p" (mod "q"); if this could be done, no prime "p" could be a counterexample to the conjecture and the conjecture would be true.

Computational verification

Various authors have used computers to perform brute-force searches for counterexamples to the conjecture. These searches can be greatly sped up by considering only prime numbers that are not covered by known congruence relations. Searches of this type by Allan Swett confirmed that the conjecture is true for all "n" up to 10¹⁴. [http://math.uindy.edu/swett/esc.htm]

The number of distinct solutions to the 4/"n" problem, as a function of "n", has also been found by computer searches for small "n" and appears to grow somewhat irregularly with "n". Starting with "n" = 3, the numbers of distinct solutions with distinct denominators are:1, 1, 2, 5, 5, 6, 4, 9, 7, 15, 4, 14, 33, 22, 4, 21, 9, ... OEIS | id = A073101.Even for larger "n" there can be relatively few solutions; for instance there are only seven distinct solutions for "n" = 73.

Generalizations

A generalized version of the conjecture due to Wacław Sierpiński states that, for any positive "k" there exists a number "N" such that, for all "n" ≥ "N", there exists a solution in positive integers to "k"/"n" = 1/"x" + 1/"y" + 1/"z".

Hagedorn proved a related conjecture of R. H. Hardin and Neil Sloane that, for odd positive "n", the equation 3/"n" = 1/"x" + 1/"y" + 1/"z" is always solvable with "x", "y", and "z" distinct, odd, and positive.

See also

* Conjectures by Erdős

References

*citation
last = Elsholtz | first = Christian
title = Sums of "k" unit fractions
journal = Transactions of the American Mathematical Society
volume = 353
issue = 8
pages = 3209–3227
year = 2001
id = MathSciNet | id = 1828604
doi = 10.1090/S0002-9947-01-02782-9.

*citation
last = Erdős | first = Paul
authorlink = Paul Erdős
title = Az 1/"x"₁ + 1/"x"₂ + ... + 1/"x"_n = a/b egyenlet egész számú megoldásairól (On a Diophantine Equation)
journal = Mat. Lapok.
volume = 1
pages = 192–210
year = 1950
id = MathSciNet | id = 0043117.

*citation
authorlink = Richard K. Guy | last = Guy | first = Richard K.
title = Unsolved Problems in Number Theory
edition = 3rd
publisher = Springer Verlag
year = 2004
isbn = 0-387-20860-7
pages = D11 .

*citation
last = Hagedorn | first = Thomas R.
title = A proof of a conjecture on Egyptian fractions
journal = American Mathematical Monthly
volume = 107
pages = 62–63
year = 2000
id = MathSciNet | id = 1745572
doi = 10.2307/2589381.

*citation
last = Li | first = D. L.
title = Equation 4/"n" = 1/"x" + 1/"y" + 1/"z"
journal = Journal of Number Theory
volume = 13
issue = 4
pages = 485–494
year = 1981
id = MathSciNet | id = 0642923
doi = 10.1016/0022-314X(81)90039-1.

*citation
last = Mordell | first = Louis J.
authorlink = Louis Mordell
title = Diophantine Equations
publisher = Academic Press
date = 1967
pages = 287–290.

*citation
last = Sierpiński | first = Wacław
authorlink = Wacław Sierpiński
title = A Selection of Problems in the Theory of Numbers
publisher = Pergamon Press
date = 1964
pages = 113.

*citation
last = Webb | first = William A.
title = On 4/"n" = 1/"x" + 1/"y" + 1/"z"
journal = Proceedings of the American Mathematical Society
volume = 25
issue = 3
pages = 578–584
year = 1970
id = MathSciNet | id = 0256984
url = http://www.jstor.org/stable/2036647.

External links

*cite web
author = Swett, Allan
title = The Erdos-Straus Conjecture
url = http://math.uindy.edu/swett/esc.htm
accessdate = 2006-09-09

* cite web
author = Weisstein, Eric W
authorlink = Eric W. Weisstein
title = Erdos-Straus Conjecture
publisher = MathWorld–A Wolfram Web Resource
url = http://mathworld.wolfram.com/Erdos-StrausConjecture.html
accessdate = 2006-09-09