HOME

TheInfoList



OR:

The Erdős–Straus conjecture is an unproven statement in
number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
. The conjecture is that, for every
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
n that is greater than or equal to 2, there exist positive integers x, y, and z for which \frac=\frac+\frac+\frac. In other words, the number 4/n can be written as a sum of three positive
unit fraction A unit fraction is a positive fraction with one as its numerator, 1/. It is the multiplicative inverse (reciprocal) of the denominator of the fraction, which must be a positive natural number. Examples are 1/1, 1/2, 1/3, 1/4, 1/5, etc. When a ...
s. The conjecture is named after
Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
and Ernst G. Straus, who formulated it in 1948, 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 equation ''Diophantine'' means pertaining to the ancient Greek mathematician Diophantus. A number of concepts bear this name: *Diophantine approximation In number theory, the study of Diophantine approximation deals with the approximation of real n ...
s. Although a solution is not known for all values of , infinitely many values in certain infinite
arithmetic progression An arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference from any succeeding term to its preceding term remains constant throughout the sequence. The constant difference is called common difference of that ...
s have simple formulas for their solution, and skipping these known values can speed up searches for
counterexample A counterexample is any exception to a generalization. In logic a counterexample disproves the generalization, and does so rigorously in the fields of mathematics and philosophy. For example, the fact that "student John Smith is not lazy" is a c ...
s. Additionally, these searches need only consider values of n that are
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
s, because any composite counterexample would have a smaller counterexample among its
prime factor A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s. Computer searches have verified the truth of the conjecture up to n\le 10^. If the conjecture is reframed to allow negative unit fractions, then it is known to be true. Generalizations of the conjecture to fractions with numerator 5 or larger have also been studied.


Background and history

When a rational number is expanded into a sum of unit fractions, the expansion is called an Egyptian fraction. This way of writing fractions dates to the mathematics of ancient Egypt, in which fractions were written this way instead of in the more modern vulgar fraction form \tfrac with a numerator a and denominator b. The Egyptians produced tables of Egyptian fractions for unit fractions multiplied by two, the numbers that in modern notation would be written \tfrac, such as the Rhind Mathematical Papyrus table; in these tables, most of these expansions use either two or three terms. These tables were needed, because the obvious expansion \tfrac2n=\tfrac1n+\tfrac1n was not allowed: the Egyptians required all of the fractions in an Egyptian fraction to be different from each other. This same requirement, that all fractions be different, is sometimes imposed in the Erdős–Straus conjecture, but it makes no significant difference to the problem, because for n>2 any solution to \tfrac4n=\tfrac1x+\tfrac1y+\tfrac1z where the unit fractions are not distinct can be converted into a solution where they are all distinct; see below. Although the Egyptians did not always find expansions using as few terms as possible, later mathematicians have been interested in the question of how few terms are needed. Every fraction \tfrac has an expansion of at most a terms, so in particular \tfrac needs at most two terms, \tfrac needs at most three terms, and \tfrac needs at most four terms. For \tfrac, two terms are always needed, and for \tfrac, three terms are sometimes needed, so for both of these numerators, the maximum number of terms that might be needed is known. However, for \tfrac, it is unknown whether four terms are sometimes needed, or whether it is possible to express all fractions of the form \tfrac using only three unit fractions; this is the Erdős–Straus conjecture. Thus, the conjecture covers the first unknown case of a more general question, the problem of finding for all a the maximum number of terms needed in expansions for fractions \tfrac. One way to find short (but not always shortest) expansions uses the
greedy algorithm for Egyptian fractions In mathematics, the greedy algorithm for Egyptian fractions is a greedy algorithm, first described by Fibonacci, for transforming rational numbers into Egyptian fractions. An Egyptian fraction is a representation of an irreducible fraction as a s ...
, first described in 1202 by
Fibonacci Leonardo Bonacci ( – ), commonly known as Fibonacci, was an Italians, Italian mathematician from the Republic of Pisa, considered to be "the most talented Western mathematician of the Middle Ages". The name he is commonly called, ''Fibonacci ...
in his book ''
Liber Abaci The or (Latin for "The Book of Calculation") was a 1202 Latin work on arithmetic by Leonardo of Pisa, posthumously known as Fibonacci. It is primarily famous for introducing both base-10 positional notation and the symbols known as Arabic n ...
''. This method chooses one unit fraction at a time, at each step choosing the largest possible unit fraction that would not cause the expanded sum to exceed the target number. After each step, the numerator of the fraction that still remains to be expanded decreases, so the total number of steps can never exceed the starting numerator, but sometimes it is smaller. For example, when it is applied to \tfrac3n, the greedy algorithm will use two terms whenever n is 2 modulo 3, but there exists a two-term expansion whenever n has a factor that is 2 modulo 3, a weaker condition. For numbers of the form \tfrac, the greedy algorithm will produce a four-term expansion whenever n is 1 modulo 4, and an expansion with fewer terms otherwise. Thus, another way of rephrasing the Erdős–Straus conjecture asks whether there exists another method for producing Egyptian fractions, using a smaller maximum number of terms for the numbers \tfrac. The Erdős–Straus conjecture was formulated in 1948 by
Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
and Ernst G. Straus, and published by . Richard Obláth also published an early work on the conjecture, a paper written in 1948 and published in 1950, in which he extended earlier calculations of Straus and Harold N. Shapiro in order to verify the conjecture for all n\le 10^.


Formulation

The conjecture states that, for every integer n\ge 2, there exist positive integers x, y, and z such that \frac4n = \frac1x + \frac1y + \frac1z. For instance, for n=5, there are two solutions: \frac45=\frac12+\frac14+\frac1=\frac12+\frac15+\frac1. Multiplying both sides of the equation \tfrac4n=\tfrac1x+\tfrac1y+\tfrac1z by nxyz leads to an equivalent
polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
form 4xyz=n(xy+xz+yz) for the problem.


Distinct unit fractions

Some researchers additionally require that the integers x, y, and z be distinct from each other, as the Egyptians would have, while others allow them to be equal. For n\ge 3, it does not matter whether they are required to be distinct: if there exists a solution with any three integers, then there exists a solution with distinct integers.
conflict resolution section
This is because two identical unit fractions can be replaced through one of the following two expansions: \begin \frac+\frac &\Rightarrow \frac+\frac\\ \frac+\frac &\Rightarrow \frac+\frac\\ \end (according to whether the repeated fraction has an even or odd denominator) and this replacement can be repeated until no duplicate fractions remain. For n=2, however, the only solutions are permutations of \tfrac42=\tfrac12+\tfrac12+\tfrac11.


Negative-number solutions

The Erdős–Straus conjecture requires that all three of x, y, and z be positive. This requirement is essential to the difficulty of the problem. Even without this relaxation, the Erdős–Straus conjecture is difficult only for odd values of n, and if negative values were allowed then the problem could be solved for every odd n by the following formula: \frac=\frac+\frac-\frac.


Computational results

If the conjecture is false, it could be proven false simply by finding a number \tfrac4n that has no three-term representation. In order to check this, various authors have performed
brute-force search In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of Iteration#Computing, systematically checking all possible candida ...
es for counterexamples to the conjecture. Searches of this type have confirmed that the conjecture is true for all n up to 10^. In such searches, it is only necessary to look for expansions for numbers \tfrac4n where n is a
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
. This is because, whenever \tfrac4n has a three-term expansion, so does \tfrac4 for all positive integers m. To find a solution for \tfrac4, just divide all of the unit fractions in the solution for \tfrac4n by m: \frac=\frac+\frac+\frac \ \Rightarrow\ \frac=\frac+\frac+\frac. If \tfrac4n were a
counterexample A counterexample is any exception to a generalization. In logic a counterexample disproves the generalization, and does so rigorously in the fields of mathematics and philosophy. For example, the fact that "student John Smith is not lazy" is a c ...
to the conjecture, for a
composite number A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Accordingly it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime numb ...
n, every
prime factor A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
p of n would also provide a counterexample \tfrac4p that would have been found earlier by the brute-force search. Therefore, checking the existence of a solution for composite numbers is redundant, and can be skipped by the search. Additionally, the known modular identities for the conjecture (see below) can speed these searches by skipping over other values known to have a solution. For instance, the greedy algorithm finds an expansion with three or fewer terms for every number \tfrac4n where n is not 1 modulo 4, so the searches only need to test values that are 1 modulo 4. One way to make progress on this problem is to collect more modular identities, allowing computer searches to reach higher limits with fewer tests. The number of distinct solutions to the \tfrac4n 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 Even for larger n there can sometimes be relatively few solutions; for instance there are only seven distinct solutions for n=73.


Theoretical results

In the form 4xyz=n(xy+xz+yz), a
polynomial equation In mathematics, an algebraic equation or polynomial equation is an equation of the form P = 0, where ''P'' is a polynomial with coefficients in some field (mathematics), field, often the field of the rational numbers. For example, x^5-3x+1=0 is a ...
with integer variables, the Erdős–Straus conjecture is an example of a
Diophantine equation ''Diophantine'' means pertaining to the ancient Greek mathematician Diophantus. A number of concepts bear this name: *Diophantine approximation In number theory, the study of Diophantine approximation deals with the approximation of real n ...
. The Hasse principle for Diophantine equations suggests that these equations should be studied using
modular arithmetic In mathematics, modular arithmetic is a system of arithmetic operations for integers, other than the usual ones from elementary arithmetic, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to mo ...
. If a polynomial equation has a solution in the integers, then taking this solution modulo q, for any integer q, provides a solution in modulo-q arithmetic. In the other direction, if an equation has a solution modulo q for every
prime power In mathematics, a prime power is a positive integer which is a positive integer power of a single prime number. For example: , and are prime powers, while , and are not. The sequence of prime powers begins: 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 1 ...
q, then in some cases it is possible to piece together these modular solutions, using methods related to the
Chinese remainder theorem In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...
, to get a solution in the integers. 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. On the face of it this principle makes little sense for the Erdős–Straus conjecture. For every n, the equation 4xyz=n(xy+xz+yz) is easily solvable modulo any prime, or prime power, but there appears to be no way to piece those solutions together to get a positive integer solution to the equation. Nevertheless, modular arithmetic, and identities based on modular arithmetic, have proven a very important tool in the study of the conjecture.


Modular identities

For values of n satisfying certain congruence relations, one can find an expansion for \tfrac4n automatically as an instance of a polynomial identity. For instance, whenever n is 2 modulo 3, \tfrac4n has the expansion \frac = \frac + \frac + \frac. Here each of the three denominators n, (n+1)/3, and n(n+1)/3 is a polynomial of n, and each is an integer whenever n is 2 modulo 3. The
greedy algorithm for Egyptian fractions In mathematics, the greedy algorithm for Egyptian fractions is a greedy algorithm, first described by Fibonacci, for transforming rational numbers into Egyptian fractions. An Egyptian fraction is a representation of an irreducible fraction as a s ...
finds a solution in three or fewer terms whenever 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 n for which these two methods do not find expansions in three or fewer terms are those congruent to 1 mod 24. Polynomial identities listed by provide three-term Egyptian fractions for \tfrac4n whenever 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. Combinations of Mordell's identities can be used to expand \tfrac4n for all 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 N goes to infinity, the fraction of values in the interval ,N/math>. that could be counterexamples tends to zero in the limit.


Nonexistence of identities

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 showed, a polynomial identity that provides a solution for values of n congruent to r mod p can exist only when r is not congruent to a square modulo p. (More formally, this kind of identity can exist only when r is not a
quadratic residue In number theory, an integer ''q'' is a quadratic residue modulo operation, modulo ''n'' if it is Congruence relation, congruent to a Square number, perfect square modulo ''n''; that is, if there exists an integer ''x'' such that :x^2\equiv q \pm ...
modulo p.) For instance, 2 is a non-square mod 3, so Mordell's result allows the existence of an identity for 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 n that are congruent to 1 mod 3. More generally, as 1 is a square mod n for all n>1, there can be no complete covering system of modular identities for all n, because 1 will always be uncovered. 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 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 \tfrac4n problem for n congruent to p mod q. If this could be done, no prime p could be a counterexample to the conjecture and the conjecture would be true.


The number of solutions

showed that the average number of solutions to the \tfrac4n problem (averaged over the prime numbers up to n) is
upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is every element of . Dually, a lower bound or minorant of is defined to be an element of that is less ...
ed polylogarithmically in n. For some other Diophantine problems, the existence of a solution can be demonstrated through
asymptotic In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates Limit of a function#Limits at infinity, tends to infinity. In pro ...
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 x, y, or z is divisible by n; for prime n, these are the only possibilities, although (on average) most solutions for composite n are of other types. Their proof uses the Bombieri–Vinogradov theorem, the Brun–Titchmarsh theorem, and a system of modular identities, valid when n is congruent to -c or -\tfrac1c modulo 4ab, where a and b are any two
coprime In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equiv ...
positive integers and c is any odd factor of a+b. For instance, setting a=b=1 gives one of Mordell's identities, valid when n is 3 mod 4.


Generalizations

As with fractions of the form \tfrac4n, it has been conjectured that every fraction \tfrac5n (for n>1) can be expressed as a sum of three positive unit fractions. A generalized version of the conjecture states that, for any positive k, all but finitely many fractions \tfrac can be expressed as a sum of three positive unit fractions. The conjecture for fractions \tfrac5n was made by
Wacław Sierpiński Wacław Franciszek Sierpiński (; 14 March 1882 – 21 October 1969) was a Polish mathematician. He was known for contributions to set theory (research on the axiom of choice and the continuum hypothesis), number theory, theory of functions ...
in a 1956 paper, which went on to credit the full conjecture to Sierpiński's student Andrzej Schinzel. Even if the generalized conjecture is false for any fixed value of k, then the number of fractions \tfrac with n in the range from 1 to N that do not have three-term expansions must grow only sublinearly as a function of N.; ; ; ; ; . In particular, if the Erdős–Straus conjecture itself (the case k=4) is false, then the number of counterexamples grows only sublinearly. Even more strongly, for any fixed k, only a sublinear number of values of n need more than two terms in their Egyptian fraction expansions. The generalized version of the conjecture is equivalent to the statement that the number of unexpandable fractions is not just sublinear but finite. When n is an
odd number In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is divisible by 2, and odd if it is not.. For example, −4, 0, and 82 are even numbers, while −3, 5, 23, and 69 are odd numbers. The ...
, by analogy to the problem of
odd greedy expansion In number theory, the odd greedy expansion problem asks whether a greedy algorithm for finding Egyptian fractions with odd denominators always succeeds. It is an open problem. Description An Egyptian fraction represents a given rational number a ...
s for Egyptian fractions, one may ask for solutions to \tfrac=\tfrac1x+\tfrac1y+\tfrac1z in which x, y, and z are distinct positive odd numbers. Solutions to this equation are known to always exist for the case in which .; ; .


See also

* List of sums of reciprocals


Notes


References

*. *. *. *. *. *. See in particular th
"Small numerators"
section *. * *. *. *. *. *. *. *. *. *. *. *. *. * *. *. *. Reprinted with additional annotations in . *. *. * *. *. *. {{DEFAULTSORT:Erdos-Straus conjecture Conjectures Unsolved problems in number theory Egyptian fractions Diophantine equations Straus conjecture