The Erdős–Straus conjecture is an unproven statement in number theory. The conjecture is that, for every integer 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 fractions.
The conjecture is named after Paul Erdős 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 equations.
Although a solution is not known for all values of n, infinitely many values in certain infinite arithmetic progressions have simple formulas for their solution, and skipping these known values can speed up searches for counterexamples. Additionally, these searches need only consider values of that are prime numbers, because any composite counterexample would have a smaller counterexample among its prime factors. 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.
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 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. [1] 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. [2]
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 . [1]
One way to find short (but not always shortest) expansions uses the greedy algorithm for Egyptian fractions, first described in 1202 by Fibonacci in his book Liber Abaci . 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, [1] 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. [3] 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 . [1]
The Erdős–Straus conjecture was formulated in 1948 by Paul Erdős and Ernst G. Straus, and published by Erdős (1950). 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 . [4]
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 form for the problem. [5]
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. [1] 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. [2] 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. [6] For , however, the only solutions are permutations of . [1]
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: [7]
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 searches for counterexamples to the conjecture. [8] Searches of this type have confirmed that the conjecture is true for all up to . [9]
In such searches, it is only necessary to look for expansions for numbers where is a prime number. 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 to the conjecture, for a composite number , every prime factor 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) 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. [9]
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 .
In the form , a polynomial equation with integer variables, the Erdős–Straus conjecture is an example of a Diophantine equation. The Hasse principle for Diophantine equations suggests that these equations should be studied using modular arithmetic. If a 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 , then in some cases it is possible to piece together these modular solutions, using methods related to the Chinese remainder theorem, 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. [10]
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. [11]
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 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. [12]
Polynomial identities listed by Mordell (1967) provide three-term Egyptian fractions for whenever is one of:
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 of potential counterexamples to the conjecture is zero: as a parameter goes to infinity, the fraction of values in the interval . that could be counterexamples tends to zero in the limit. [13]
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 congruent to mod can exist only when is not congruent to a square modulo . (More formally, this kind of identity can exist only when is not a quadratic residue modulo .) For instance, 2 is a non-square mod 3, so Mordell's result allows the existence of an identity for 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 that are congruent to 1 mod 3. More generally, as 1 is a square mod for all , there can be no complete covering system of modular identities for all , because 1 will always be uncovered. [14]
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 is prime, there exists a larger prime such that is not a quadratic residue modulo . One possible approach to proving the conjecture would be to find for each prime a larger prime and a congruence solving the problem for congruent to mod . If this could be done, no prime could be a counterexample to the conjecture and the conjecture would be true. [12]
Elsholtz & Tao (2013) showed that the average number of solutions to the problem (averaged over the prime numbers up to ) is upper bounded polylogarithmically in . 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 , , or is divisible by ; for prime , these are the only possibilities, although (on average) most solutions for composite are of other types. Their proof uses the Bombieri–Vinogradov theorem, the Brun–Titchmarsh theorem, and a system of modular identities, valid when is congruent to or modulo , where and are any two coprime positive integers and is any odd factor of . For instance, setting gives one of Mordell's identities, valid when is 3 mod 4. [15]
As with fractions of the form , it has been conjectured that every fraction (for ) can be expressed as a sum of three positive unit fractions. A generalized version of the conjecture states that, for any positive , all but finitely many fractions can be expressed as a sum of three positive unit fractions. The conjecture for fractions was made by Wacław Sierpiński in a 1956 paper, which went on to credit the full conjecture to Sierpiński's student Andrzej Schinzel. [16]
Even if the generalized conjecture is false for any fixed value of , then the number of fractions with in the range from 1 to that do not have three-term expansions must grow only sublinearly as a function of . [13] In particular, if the Erdős–Straus conjecture itself (the case ) is false, then the number of counterexamples grows only sublinearly. Even more strongly, for any fixed , only a sublinear number of values of need more than two terms in their Egyptian fraction expansions. [17] The generalized version of the conjecture is equivalent to the statement that the number of unexpandable fractions is not just sublinear but bounded.
When is an odd number, by analogy to the problem of odd greedy expansions for Egyptian fractions, one may ask for solutions to in which , , and are distinct positive odd numbers. Solutions to this equation are known to always exist for the case in which k = 3. [18]
In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:
The Collatz conjecture is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1. It concerns sequences of integers in which each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence. The conjecture has been shown to hold for all positive integers up to 2.95×1020, but no general proof has been found.
In number theory, given a prime number p, the p-adic numbers form an extension of the rational numbers which is distinct from the real numbers, though with some similar properties; p-adic numbers can be written in a form similar to decimals, but with digits based on a prime number p rather than ten, and extending to the left rather than to the right.
In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:
In number theory, the study of Diophantine approximation deals with the approximation of real numbers by rational numbers. It is named after Diophantus of Alexandria.
In mathematics, a quadratic irrational number is an irrational number that is the solution to some quadratic equation with rational coefficients which is irreducible over the rational numbers. Since fractions in the coefficients of a quadratic equation can be cleared by multiplying both sides by their least common denominator, a quadratic irrational is an irrational root of some quadratic equation with integer coefficients. The quadratic irrational numbers, a subset of the complex numbers, are algebraic numbers of degree 2, and can therefore be expressed as
In number theory, a Wieferich prime is a prime number p such that p2 divides 2p − 1 − 1, therefore connecting these primes with Fermat's little theorem, which states that every odd prime p divides 2p − 1 − 1. Wieferich primes were first described by Arthur Wieferich in 1909 in works pertaining to Fermat's Last Theorem, at which time both of Fermat's theorems were already well known to mathematicians.
An Egyptian fraction is a finite sum of distinct unit fractions, such as 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 other. The value of an expression of this type is a positive rational number ; for instance the Egyptian fraction above sums to . Every positive rational number can be represented by an Egyptian fraction. Sums of this type, and similar sums also including and as summands, were used as a serious notation for rational numbers by the ancient Egyptians, and continued to be used by other civilizations into medieval times. In modern mathematical notation, Egyptian fractions have been superseded by vulgar fractions and decimal notation. However, Egyptian fractions continue to be an object of study in modern number theory and recreational mathematics, as well as in modern historical studies of ancient mathematics.
A powerful number is a positive integer m such that for every prime number p dividing m, p2 also divides m. Equivalently, a powerful number is the product of a square and a cube, that is, a number m of the form m = a2b3, where a and b are positive integers. Powerful numbers are also known as squareful, square-full, or 2-full. Paul Erdős and George Szekeres studied such numbers and Solomon W. Golomb named such numbers powerful.
One half is the irreducible fraction resulting from dividing one (1) by two (2), or the fraction resulting from dividing any number by its double.
A unit fraction is a positive fraction with one as its numerator, 1/n. 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 an object is divided into equal parts, each part is a unit fraction of the whole.
In mathematics, a confluent hypergeometric function is a solution of a confluent hypergeometric equation, which is a degenerate form of a hypergeometric differential equation where two of the three regular singularities merge into an irregular singularity. The term confluent refers to the merging of singular points of families of differential equations; confluere is Latin for "to flow together". There are several common standard forms of confluent hypergeometric functions:
In algebraic number theory, a fundamental unit is a generator for the unit group of the ring of integers of a number field, when that group has rank 1. Dirichlet's unit theorem shows that the unit group has rank 1 exactly when the number field is a real quadratic field, a complex cubic field, or a totally imaginary quartic field. When the unit group has rank ≥ 1, a basis of it modulo its torsion is called a fundamental system of units. Some authors use the term fundamental unit to mean any element of a fundamental system of units, not restricting to the case of rank 1.
In number theory, Sylvester's sequence is an integer sequence in which each term is the product of the previous terms, plus one. Its first few terms are
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 of distinct unit fractions, such as 5/6 = 1/2 + 1/3. As the name indicates, these representations have been used as long ago as ancient Egypt, but the first published systematic method for constructing such expansions was described in 1202 in the Liber Abaci of Leonardo of Pisa (Fibonacci). It is called a greedy algorithm because at each step the algorithm chooses greedily the largest possible unit fraction that can be used in any representation of the remaining fraction.
In mathematics and statistics, sums of powers occur in a number of contexts:
In number theory, the optic equation is an equation that requires the sum of the reciprocals of two positive integers a and b to equal the reciprocal of a third positive integer c:
In recreational mathematics, rope-burning puzzles are a class of mathematical puzzle in which one is given lengths of rope, fuse cord, or shoelace that each burn for a given amount of time, and matches to set them on fire, and must use them to measure a non-unit amount of time. The fusible numbers are defined as the amounts of time that can be measured in this way.
M. Strauss [sic] a vérifié l'hypothèse de M. Erdős pour toute valeur de n < 5.000, et M. Shapiro pour n < 20.000. Nos théorèmes donnent la solution pour tout nombre < 106.128.