The Erdős–Straus conjecture is an
unproven statement in
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777â ...
. The conjecture is that, for every
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
that is 2 or more, there exist positive integers
,
, and
for which
In other words, the number
can be written as a sum of three positive
unit fraction
A unit fraction is a rational number written as a fraction where the numerator is one and the denominator is a positive integer. A unit fraction is therefore the reciprocal of a positive integer, 1/''n''. Examples are 1/1, 1/2, 1/3, 1/4, 1/5, et ...
s.
The conjecture is named after
Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 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 ...
and
Ernst G. Straus
Ernst Gabor Straus (February 25, 1922 – July 12, 1983) was a German-American mathematician of Jewish origin who helped found the theories of Euclidean Ramsey theory and of the arithmetic properties of analytic functions. His extensive list of co ...
, 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 fraction
An Egyptian fraction is a finite sum of distinct unit fractions, such as
\frac+\frac+\frac.
That is, each fraction in the expression has a numerator equal to 1 and a denominator that is a positive integer, and all the denominators differ from each ...
s, because of their use in
ancient Egyptian mathematics
Ancient Egyptian mathematics is the mathematics that was developed and used in Ancient Egypt 3000 to c. , from the Old Kingdom of Egypt until roughly the beginning of Hellenistic Egypt. The ancient Egyptians utilized Egyptian numerals, a numeral ...
. The Erdős–Straus conjecture is one of many
conjectures by Erdős, and one of many unsolved problems in mathematics concerning
Diophantine equation
In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a c ...
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 between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...
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 "John Smith is not a lazy student" is a ...
s. Additionally, these searches need only consider values of
that are
prime number
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, 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
.
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
An Egyptian fraction is a finite sum of distinct unit fractions, such as
\frac+\frac+\frac.
That is, each fraction in the expression has a numerator equal to 1 and a denominator that is a positive integer, and all the denominators differ from each ...
. 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
A fraction (from la, fractus, "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, a fraction describes how many parts of a certain size there are, for example, one-half, eight ...
form
with a numerator
and denominator
. The Egyptians produced tables of Egyptian fractions for unit fractions multiplied by two, the numbers that in modern notation would be written
, 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
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
any solution to
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 has an expansion of at most terms, so in particular needs at most two terms, needs at most three terms, and needs at most four terms. For , two terms are always needed, and for , three terms are sometimes needed, so for both of these numerators, the maximum number of terms that might be needed is known. However, for , it is unknown whether four terms are sometimes needed, or whether it is possible to express all fractions of the form 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 the maximum number of terms needed in expansions for fractions .
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 sum ...
, first described in 1202 by Fibonacci
Fibonacci (; also , ; – ), also known as Leonardo Bonacci, Leonardo of Pisa, or Leonardo Bigollo Pisano ('Leonardo the Traveller from Pisa'), was an Italian mathematician from the Republic of Pisa, considered to be "the most talented Western ...
in his book ''Liber Abaci
''Liber Abaci'' (also spelled as ''Liber Abbaci''; "The Book of Calculation") is a historic 1202 Latin manuscript on arithmetic by Leonardo of Pisa, posthumously known as Fibonacci.
''Liber Abaci'' was among the first Western books to describe ...
''. 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 , the greedy algorithm will use two terms whenever is 2 modulo 3, but there exists a two-term expansion whenever has a factor that is 2 modulo 3, a weaker condition. For numbers of the form , the greedy algorithm will produce a four-term expansion whenever 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 .
The Erdős–Straus conjecture was formulated in 1948 by Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 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 ...
and Ernst G. Straus
Ernst Gabor Straus (February 25, 1922 – July 12, 1983) was a German-American mathematician of Jewish origin who helped found the theories of Euclidean Ramsey theory and of the arithmetic properties of analytic functions. His extensive list of co ...
, 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 .
Formulation
The conjecture states that, for every integer , there exist positive integers , , and such that
For instance, for , there are two solutions:
Multiplying both sides of the equation by leads to an equivalent polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
form for the problem.
Distinct unit fractions
Some researchers additionally require that the integers , , and be distinct from each other, as the Egyptians would have, while others allow them to be equal. For , 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:
(according to whether the repeated fraction has an even or odd denominator) and this replacement can be repeated until no duplicate fractions remain. For , however, the only solutions are permutations of .
Negative-number solutions
The Erdős–Straus conjecture requires that all three of , , and 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 , and if negative values were allowed then the problem could be solved for every odd by the following formula:
Computational results
If the conjecture is false, it could be proven false simply by finding a number 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 systematically enumerating all possible candidates for the soluti ...
es for counterexamples to the conjecture. Searches of this type have confirmed that the conjecture is true for all up to .
In such searches, it is only necessary to look for expansions for numbers where is a prime number
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 ...
. This is because, whenever has a three-term expansion, so does for all positive integers . To find a solution for , just divide all of the unit fractions in the solution for by :
If 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 "John Smith is not a lazy student" is a ...
to the conjecture, for a composite number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
, 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 ...
of would also provide a counterexample 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
Below may refer to:
*Earth
*Ground (disambiguation)
*Soil
*Floor
*Bottom (disambiguation)
Bottom may refer to:
Anatomy and sex
* Bottom (BDSM), the partner in a BDSM who takes the passive, receiving, or obedient role, to that of the top or ...
) 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 where 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 problem, as a function of , has also been found by computer searches for small and appears to grow somewhat irregularly with . Starting with , the numbers of distinct solutions with distinct denominators are
Even for larger there can sometimes be relatively few solutions; for instance there are only seven distinct solutions for .
Theoretical results
In the form , 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, often the field of the rational numbers. For many authors, the term ''algebraic equation' ...
with integer variables, the Erdős–Straus conjecture is an example of a Diophantine equation
In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a c ...
. The Hasse principle In mathematics, Helmut Hasse's local–global principle, also known as the Hasse principle, is the idea that one can find an integer solution to an equation by using the Chinese remainder theorem to piece together solutions modulo powers of eac ...
for Diophantine equations suggests that these equations should be studied using modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book ...
. If an polynomial equation has a solution in the integers, then taking this solution modulo , for any integer , provides a solution in modulo- arithmetic. In the other direction, if an equation has a solution modulo 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, 17 ...
, 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 , the equation 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 satisfying certain congruence relations, one can find an expansion for automatically as an instance of a polynomial identity. For instance, whenever is 2 modulo 3, has the expansion
Here each of the three denominators , , and is a polynomial of , and each is an integer whenever 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 sum ...
finds a solution in three or fewer terms whenever 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 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 whenever 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 for all 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 In number theory, natural density (also referred to as asymptotic density or arithmetic density) is one method to measure how "large" a subset of the set of natural numbers is. It relies chiefly on the probability of encountering members of the de ...
of potential counterexamples to the conjecture is zero: as a parameter goes to infinity, the fraction of values in the interval