Erdős–Straus conjecture

The Erdős–Straus conjecture is an unproven statement in number theory, according to which every fraction ${\displaystyle 4/n}$ can be written as a sum of three positive unit fractions ${\displaystyle 1/x+1/y+1/z}$. It is named after Paul Erdős and Ernst G. Straus, who formulated the conjecture in 1948,^[1] but it is connected to much more ancient mathematics: sums of unit fractions, like the one in this problem, are known as Egyptian fractions, because of their use in ancient Egyptian mathematics. The Erdős–Straus conjecture is one of many conjectures by Erdős, and one of many unsolved problems in mathematics concerning Diophantine equations.

Although a solution is not known for all values of n, solutions are known for infinitely many values, and these known values can be used to speed up searches for counterexamples. For instance, these searches need only consider values of ${\displaystyle n}$ that are prime numbers, because if ${\displaystyle n}$ is a composite number, ${\displaystyle n=pq}$, then an expansion for ${\displaystyle 4/n}$ could be found from an expansion for ${\displaystyle 4/p}$ or ${\displaystyle 4/q}$. Additionally, the values of ${\displaystyle n}$ that belong to certain infinite arithmetic progressions have solutions given by simple formulas, although these progressions cannot contain any square numbers. Combining the ideas of factorization and progressions shows that, if a counterexample to the Erdős–Straus conjecture exists, the smallest ${\displaystyle n}$ forming a counterexample must be a prime number congruent to one of six values modulo 840.^[2] Computer searches have verified the truth of the conjecture up to ${\displaystyle n\leq 10^{17}}$,^[3] but proving it for all ${\displaystyle n}$ remains an open problem.

The restriction that the three unit fractions be positive is essential to the difficulty of the problem, for if negative values were allowed the problem could always be solved.

Formulation[]

More formally, the conjecture states that, for every integer ${\displaystyle n\geq 2}$, there exist positive integers ${\displaystyle x}$, ${\displaystyle y}$, and ${\displaystyle z}$ such that

For instance, for ${\displaystyle n=5}$, there are two solutions:

The conjecture was formulated in 1948 by Paul Erdős and Ernst G. Straus, and published by Erdős (1950); another paper on the problem, by Obláth (1950), was also originally submitted in 1948.^[4]

Some researchers additionally require these integers to be distinct from each other, while others allow them to be equal.^[5] For ${\displaystyle n\geq 3}$, it does not matter whether they are required to be distinct: if there exists a solution with any three integers ${\displaystyle x}$, ${\displaystyle y}$, and ${\displaystyle z}$ then there exists a solution with distinct integers.^[6] For ${\displaystyle n=2}$, however, the only solutions are permutations of ${\displaystyle {\tfrac {4}{2}}={\tfrac {1}{2}}+{\tfrac {1}{2}}+{\tfrac {1}{1}}}$. When ${\displaystyle x}$, ${\displaystyle y}$, and ${\displaystyle z}$ are distinct then these unit fractions form an Egyptian fraction representation of the number ${\displaystyle {\tfrac {4}{n}}}$.^[5]

Background[]

The search for expansions of rational numbers as sums of unit fractions dates to the mathematics of ancient Egypt, in which Egyptian fraction expansions of this type were used as a notation for recording fractional quantities. The Egyptians produced tables such as the Rhind Mathematical Papyrus table of expansions of fractions of the form ${\displaystyle {\tfrac {2}{n}}}$, most of which use either two or three terms.^[5] Egyptian fractions typically have an additional constraint, that all of the unit fractions be distinct from each other, but for the purposes of the Erdős–Straus conjecture this makes no difference: if ${\displaystyle {\tfrac {4}{n}}}$ can be expressed as a sum of three unit fractions, for ${\displaystyle n>2}$, it can also be expressed as a sum of three distinct unit fractions by repeatedly replacing any duplicated fraction by one of the following two expansions,

(according to whether the repeated fraction has an even or odd denominator) until no duplicate fractions remain.^[7]

The greedy algorithm for Egyptian fractions, first described in 1202 by Fibonacci in his book Liber Abaci, finds an expansion in which each successive term is the largest unit fraction that is no larger than the remaining number to be represented. For fractions of the form ${\displaystyle {\tfrac {2}{n}}}$ or ${\displaystyle {\tfrac {3}{n}}}$, the greedy algorithm uses at most two or three terms respectively.^[5] A number of the form ${\displaystyle {\tfrac {3}{n}}}$ has a two-term expansion if and only if ${\displaystyle n}$ has a factor congruent to 2 modulo 3, and requires three terms in any expansion otherwise. Thus, for the numerators 2 and 3, the question of how many terms are needed in an Egyptian fraction is completely settled, and fractions of the form ${\displaystyle {\tfrac {4}{n}}}$ are the first case in which the worst-case length of an expansion remains unknown. The greedy algorithm produces expansions of length two, three, or four depending on the value of ${\displaystyle n}$ modulo 4; when ${\displaystyle n}$ is congruent to 1 modulo 4, the greedy algorithm produces four-term expansions. Therefore, the worst-case length of an Egyptian fraction of ${\displaystyle {\tfrac {4}{n}}}$ must be either three or four. The Erd��s–Straus conjecture states that, in this case, as in the case for the numerator 3, the maximum number of terms in an expansion is three.^[8]

Modular identities[]

Multiplying both sides of the equation ${\displaystyle {\tfrac {4}{n}}={\tfrac {1}{x}}+{\tfrac {1}{y}}+{\tfrac {1}{z}}}$ by ${\displaystyle nxyz}$ leads to an equivalent form ${\displaystyle 4xyz=n(xy+xz+yz)}$ for the problem.^[9] As a polynomial equation with integer variables, this is an example of a Diophantine equation. The Hasse principle for Diophantine equations asserts that an integer solution of a Diophantine equation should be formed by combining 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 ${\displaystyle 4xyz=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.^[4] The power of the Hasse principle to solve some problems is limited by the Manin obstruction, but for the Erdős–Straus conjecture this obstruction does not exist.^[10]

For values of ${\displaystyle n}$ satisfying certain congruence relations, one can find an expansion for ${\displaystyle {\tfrac {4}{n}}}$ automatically as an instance of a polynomial identity. For instance, whenever ${\displaystyle n}$ is 2 modulo 3, ${\displaystyle {\tfrac {4}{n}}}$ has the expansion

Here each of the three denominators ${\displaystyle n}$, ${\displaystyle (n+1)/3}$, and ${\displaystyle n(n+1)/3}$ is a polynomial of ${\displaystyle n}$, and each is an integer whenever ${\displaystyle n}$ is 2 modulo 3. The greedy algorithm for Egyptian fractions finds a solution in three or fewer terms whenever ${\displaystyle n}$ is not 1 or 17 mod 24, and the 17 mod 24 case is covered by the 2 mod 3 relation, so the only values of ${\displaystyle n}$ for which these two methods do not find expansions in three or fewer terms are those congruent to 1 mod 24.^[11]

If it were possible to find solutions such as the ones above for enough different moduli, forming a complete covering system of congruences, the problem would be solved. However, as Mordell (1967) showed, a polynomial identity that provides a solution for values of ${\displaystyle n}$ congruent to ${\displaystyle r}$ mod ${\displaystyle p}$ can exist only when ${\displaystyle r}$ is not a square modulo ${\displaystyle p}$ (more formally, if ${\displaystyle r}$ is not a quadratic residue modulo ${\displaystyle p}$). For instance, 2 is a non-square mod 3, so Mordell's result allows the existence of an identity for ${\displaystyle n}$ congruent to 2 mod 3. However, 1 is a square mod 3 (equal to the square of both 1 and 2 mod 3), so there can be no similar identity for all values of ${\displaystyle n}$ that are congruent to 1 mod 3. More generally, as 1 is a square mod ${\displaystyle n}$ for all ${\displaystyle n>1}$, there can be no complete covering system of modular identities for all ${\displaystyle n}$.^[12]

Polynomial identities listed by Mordell provide three-term Egyptian fractions for ${\displaystyle {\tfrac {4}{n}}}$ whenever ${\displaystyle n}$ is one of:

• 2 mod 3 (above),
• 3 mod 4,
• 2 or 3 mod 5,
• 3, 5, or 6 mod 7, or
• 5 mod 8.

For each modulus 3, 4, 5, 7, or 8, these identities cover all non-squares. However, for larger moduli, some non-squares are also left uncovered by the known identities. Combinations of Mordell's identities can be used to expand ${\displaystyle {\tfrac {4}{n}}}$ for all ${\displaystyle n}$. except possibly those that are 1, 121, 169, 289, 361, or 529 mod 840. The smallest prime that these identities do not cover is 1009. By combining larger classes of modular identities, Webb and others showed that the natural density of potential counterexamples to the conjecture is zero: as a parameter ${\displaystyle N}$. goes to infinity, the fraction of values in the interval ${\displaystyle [1,N]}$. that could be counterexamples tends to zero in the limit.^[13]

Despite Mordell's result limiting the form of modular identities for this problem, 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 ${\displaystyle p}$ is prime, there exists a larger prime ${\displaystyle q}$ such that ${\displaystyle p}$ is not a quadratic residue modulo ${\displaystyle q}$. One possible approach to proving the conjecture would be to find for each prime ${\displaystyle p}$ a larger prime ${\displaystyle q}$ and a congruence solving the ${\displaystyle {\tfrac {4}{n}}}$ problem for ${\displaystyle n}$ congruent to ${\displaystyle p}$ mod ${\displaystyle q}$. If this could be done, no prime ${\displaystyle p}$ could be a counterexample to the conjecture and the conjecture would be true.^[11]

Computational verification[]

Various authors have performed 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.^[14] Searches of this type have confirmed that the conjecture is true for all ${\displaystyle n}$ up to ${\displaystyle 10^{17}}$.^[3]

The number of solutions[]

The number of distinct solutions to the ${\displaystyle {\tfrac {4}{n}}}$ problem, as a function of ${\displaystyle n}$, has also been found by computer searches for small ${\displaystyle n}$ and appears to grow somewhat irregularly with ${\displaystyle n}$. Starting with ${\displaystyle n=3}$, the numbers of distinct solutions with distinct denominators are

Even for larger ${\displaystyle n}$ there can be relatively few solutions; for instance there are only seven distinct solutions for ${\displaystyle n=73}$.

Elsholtz & Tao (2013) have shown that the average number of solutions to the ${\displaystyle {\tfrac {4}{n}}}$ problem (averaged over the prime numbers up to ${\displaystyle n}$) is upper bounded polylogarithmically in ${\displaystyle n}$. For some other Diophantine problems, the existence of a solution can be demonstrated through asymptotic lower bounds on the number of solutions, but this works best when the number of solutions grows at least polynomially, so the slower growth rate of Elsholtz and Tao's result makes a proof of this type less likely. Elsholtz and Tao classify solutions according to whether one or two of ${\displaystyle x}$, ${\displaystyle y}$, or ${\displaystyle z}$ is divisible by ${\displaystyle n}$; for prime ${\displaystyle n}$, these are the only possibilities, although (on average) most solutions for composite ${\displaystyle n}$ are of other types. Their proof uses the Bombieri–Vinogradov theorem, the Brun–Titchmarsh theorem, and a system of modular identities, valid when ${\displaystyle n}$ is congruent to ${\displaystyle -c}$ or ${\displaystyle -{\tfrac {1}{c}}}$ modulo ${\displaystyle 4ab}$, where ${\displaystyle a}$ and ${\displaystyle b}$ are any two coprime positive integers and ${\displaystyle c}$ is any odd factor of ${\displaystyle a+b}$. For instance, setting ${\displaystyle a=b=1}$ gives one of Mordell's identities, valid when ${\displaystyle n}$ is 3 mod 4.^[15]

Negative-number solutions[]

The restriction that ${\displaystyle x}$, ${\displaystyle y}$, and ${\displaystyle 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

and

Alternatively, for any odd ${\displaystyle n}$, a three-term solution with one negative term is possible:^[16]

Generalizations[]

A generalized version of the conjecture states that, for any positive ${\displaystyle k}$ there exists a number ${\displaystyle N}$ such that, for all ${\displaystyle n\geq N}$, there exists a solution in positive integers to ${\displaystyle {\tfrac {k}{n}}={\tfrac {1}{x}}+{\tfrac {1}{y}}+{\tfrac {1}{z}}}$. The version of this conjecture for ${\displaystyle k=5}$ was made by Wacław Sierpiński, and the full conjecture is due to Andrzej Schinzel.^[17]

Even if the generalized conjecture is false for any fixed value of ${\displaystyle k}$, then the number of fractions ${\displaystyle {\tfrac {k}{n}}}$ with ${\displaystyle n}$ in the range from 1 to ${\displaystyle N}$ that do not have three-term expansions must grow only sublinearly as a function of ${\displaystyle N}$.^[13] In particular, if the Erdős–Straus conjecture itself (the case ${\displaystyle k=4}$) is false, then the number of counterexamples grows only sublinearly. Even more strongly, for any fixed ${\displaystyle k}$, only a sublinear number of values of ${\displaystyle n}$ need more than two terms in their Egyptian fraction expansions.^[18] The generalized version of the conjecture is equivalent to the statement that the number of unexpandable fractions is not just sublinear but bounded.

When ${\displaystyle n}$ is an odd number, by analogy to the problem of odd greedy expansions for Egyptian fractions, one may ask for solutions to ${\displaystyle {\tfrac {k}{n}}={\tfrac {1}{x}}+{\tfrac {1}{y}}+{\tfrac {1}{z}}}$ in which ${\displaystyle x}$, ${\displaystyle y}$, and ${\displaystyle z}$ are distinct positive odd numbers. Solutions to this equation are known to always exist for the case in which k = 3.^[19]

See also[]

• List of sums of reciprocals

Notes[]

References[]

External links[]

• Counting the number of solutions to the Erdös-Straus equation on unit fractions, Terence Tao, July 31, 2011.