Erdős–Moser equation explained

In number theory, the Erdős–Moser equation is

1 ^{k+2} ^{k+ … +(m-1)} ^{k=m} ^{k,} where and are restricted to the positive integers—that is, it is considered as a Diophantine equation. The only known solution is, and Paul Erdős conjectured that no further solutions exist. Any further solutions must have .

Some care must be taken when comparing research papers on this equation, because some articles express it in the form instead.

Throughout this article, refers exclusively to prime numbers.

Constraints on solutions

In 1953, Leo Moser proved that, in any further solutions,

1. is even,
2. implies,
3. implies,
4. implies,
5. is squarefree,
6. is either squarefree or 4 times an odd squarefree number,
7. is squarefree,
8. is squarefree,

\sum _{p|(m-1)} (m -1)/(p) \equiv -1 \pmod{m -1 }, \sum _{p|(m+1)} (m +1)/(p) \equiv -2 \pmod{m +1 } (if m +1 iseven) , \sum _{p|(2m-1)} (2 m -1)/(p) \equiv -2 \pmod{ 2 m -1 }, \sum _{p|(2m+1)} (2 m +1)/(p) \equiv -4 \pmod{ 2 m +1 }, and

1. .

In 1966, it was additionally shown that

1. , and
2. cannot be prime.

In 1994, it was shown that

1. divides,
2. , where is the 2-adic valuation of ; equivalently,,
3. for any odd prime divding, we have,
4. any prime factor of must be irregular and > 10000.

In 1999, Moser's method was refined to show that .

In 2002, it was shown that must be a multiple of, where the symbol indicates the primorial; that is, is the product of all prime numbers . This number exceeds .

In 2009, it was shown that must be a convergent of ; in what the authors of that paper call "one of very few instances where a large scale computation of a numerical constant has an application", it was then determined that .

In 2010, it was shown that

1. and, and
2. has at least 4,990,906 prime factors, none of which are repeated.

The number 4,990,906 arises from the fact that where is the ^th prime number.

Moser's method

First, let be a prime factor of . Leo Moser showed that this implies that divides and thatwhich upon multiplying by yields

p + m - 1 \equiv 0 \pmod{p ^{2}.} This in turn implies that must be squarefree. Furthermore, since nontrivial solutions have and since all squarefree numbers in this range must have at least one odd prime factor, the assumption that divides implies that must be even.

One congruence of the form exists for each prime factor of . Multiplying all of them together yields

\prod _{p|(m-1)} \left( 1 + (m -1)/(p) \right) \equiv 0 \pmod{m -1 }. Expanding out the product yields1 + \sum _{p|(m-1)} (m -1)/(p) + ( higher-orderterms ) \equiv 0 \pmod{m -1 }, where the higher-order terms are products of multiple factors of the form, with different values of in each factor. These terms are all divisible by, so they all drop out of the congruence, yielding1 + \sum _{p|(m-1)} (m -1)/(p) \equiv 0 \pmod{m -1 }. Dividing out the modulus yieldsSimilar reasoning yields the congruences

The congruences,,, and are quite restrictive; for example, the only values of which satisfy are 3, 7, and 43, and these are ruled out by .

We now split into two cases: either is even, or it is odd.

In the case that is even, adding the left-hand sides of the congruences,,, and must yield an integer, and this integer must be at least 4. Furthermore, the Euclidean algorithm shows that no prime can divide more than one of the numbers in the set, and that 2 and 3 can divide at most two of these numbers. Letting, we then haveSince there are no nontrivial solutions with, the part of the LHS of outside the sigma cannot exceed ; we therefore have

\sum _{p|M} (1)/(p) > 3 . 16 . Therefore, if \sum _{p} (1)/(p) < 3 . 16 , then M > \prod _{p} p . In Moser's original paper, bounds on the prime-counting function are used to observe that\sum _{p \leq 10 ^{7}} (1)/(p) < 3 . 16 . Therefore, must exceed the product of the first 10,000,000 primes. This in turn implies that in this case.

In the case that is odd, we cannot use, so instead of we obtain

(1)/(m -1) + (2)/(2 m -1) + (4)/(2 m +1) + \sum _{p|N} (1)/(p) \geq 3 - (1)/(3) = 2 . 666 ..., where . On the surface, this appears to be a weaker condition than, but since is odd, the prime 2 cannot appear on the greater side of this inequality, and it turns out to be a stronger restriction on than the other case.

Therefore any nontrivial solutions have .

In 1999, this method was refined by using computers to replace the prime-counting estimates with exact computations; this yielded the bound .

Bounding the ratio

Let . Then the Erdős–Moser equation becomes .

Method 1: Integral comparisons

By comparing the sum to definite integrals of the function, one can obtain the bounds .

The sum is the upper Riemann sum corresponding to the integral $\backslash int\_0^\; x^k\; \backslash ,\; \backslash mathrmx$ in which the interval has been partitioned on the integer values of, so we have

S _{k(m)} > \int ^{m -1} _{0} x ^{k} d x. By hypothesis,, som ^{k} > ((m -1 ) ^{k+1})/(k +1) , which leads toSimilarly, is the lower Riemann sum corresponding to the integral $\backslash int\_1^m\; x^k\; \backslash ,\; \backslash mathrmx$ in which the interval has been partitioned on the integer values of, so we haveS _{k(m)} \leq \int ^{m} _{1} x ^{k} d x. By hypothesis,, som ^{k} \leq (m ^{k+1} -1)/(k +1) < (m ^{k+1})/(k +1) , and soApplying this to yields(m)/(k +1) < \left( 1 + (1)/(m -1) \right) ^{m} = \left( 1 + (1)/(m -1) \right) ^{m-1} ⋅ \left( (m)/(m -1) \right) < e ⋅ (m)/(m -1) . Computation shows that there are no nontrivial solutions with, so we have(m)/(k +1) < e ⋅ (11)/(11-1) < 3 . Combining this with yields, as desired.

Method 2: Algebraic manipulations

The upper bound can be reduced to using an algebraic method:

Let be a positive integer. Then the binomial theorem yields

(\ell + 1 ) ^{r+1} = \sum ^{r +1} _{i =0} \binom{r +1 }{i} \ell ^{r+1-i} . Summing over yields\sum ^{m -1} _{\ell =1} (\ell + 1 ) ^{r+1} = \sum ^{m -1} _{\ell =1} \left( \sum ^{r +1} _{i =0} \binom{r +1 }{i} \ell ^{r+1-i} \right). Reindexing on the left and rearranging on the right yields\sum ^{m} _{\ell =2} \ell ^{r+1} = \sum ^{r +1} _{i =0} \binom{r +1 }{i} \sum ^{m -1} _{\ell =1} \ell ^{r+1-i} \sum ^{m} _{\ell =1} \ell ^{r+1} = 1 + \sum ^{r +1} _{i =0} \binom{r +1 }{i} S _{r+1-i} (m) S _{r+1} (m +1 ) - S _{r+1} (m) = 1 + (r +1 ) S _{r} (m) + \sum ^{r +1} _{i =2} \binom{r +1 }{i} S _{r+1-i} (m) Taking yieldsm ^{k+1} = 1 + (k +1 ) S _{k} (m) + \sum ^{k +1} _{i =2} \binom{k +1 }{i} S _{k+1-i} (m). By hypothesis,, som ^{k+1} = 1 + (k +1 ) m ^{k} + \sum ^{k +1} _{i =2} \binom{k +1 }{i} S _{k+1-i} (m) Since the RHS is positive, we must therefore haveReturning to and taking yieldsm ^{k} = 1 + k ⋅ S _{k-1} (m) + \sum ^{k} _{i =2} \binom{k}{i} S _{k-i} (m) m ^{k} = 1 + \sum ^{k} _{s =1} \binom{k}{s} S _{k-s} (m). Substituting this into to eliminate yields\left( 1 + \sum ^{k} _{s =1} \binom{k}{s} S _{k-s} (m) \right) ( m - (k +1 ) ) = 1 + \sum ^{k +1} _{i =2} \binom{k +1 }{i} S _{k+1-i} (m). Reindexing the sum on the right with the substitution yields\left( 1 + \sum ^{k} _{s =1} \binom{k}{s} S _{k-s} (m) \right) ( m - (k +1 ) ) = 1 + \sum ^{k} _{s =1} \binom{k +1 }{s +1 } S _{k-s} (m) m - (k +1 ) + ( m - (k +1 ) ) \sum ^{k} _{s =1} \binom{k}{s} S _{k-s} (m) = 1 + \sum ^{k} _{s =1} (k +1)/(s +1) \binom{k}{s} S _{k-s} (m) We already know from that . This leaves open the possibility that ; however, substituting this into yields0 = \sum ^{k} _{s =1} \left( (k +1)/(s +1) - 1 \right) \binom{k}{s} S _{k-s} (k +2 ) 0 = \sum ^{k} _{s =1} (k - s)/(s +1) \binom{k}{s} S _{k-s} (k +2 ) 0 = (k - k)/(k +1) \binom{k}{k} S _{k-k} (k +2 ) + \sum ^{k -1} _{s =1} (k - s)/(s +1) \binom{k}{s} S _{k-s} (k +2 ) 0 = 0 + \sum ^{k -1} _{s =1} (k - s)/(s +1) \binom{k}{s} S _{k-s} (k +2 ), which is impossible for, since the sum contains only positive terms. Therefore any nontrivial solutions must have ; combining this with yieldsk + 2 < m. We therefore observe that the left-hand side of is positive, soSince, the sequence \left\{ (k +1 )/(s +1 ) - m + (k +1 ) \right\} ^{inf ty} _{s =1} is decreasing. This and together imply that its first term (the term with) must be positive: if it were not, then every term in the sum would be nonpositive, and therefore so would the sum itself. Thus,0 < (k +1)/(1+1) - m + (k +1 ), which yieldsm < (3)/(2) ⋅ (k +1 ) and therefore(m)/(k +1) < (3)/(2) , as desired.

Continued fractions

Any potential solutions to the equation must arise from the continued fraction of the natural logarithm of 2: specifically, must be a convergent of that number.

By expanding the Taylor series of about, one finds

( 1 - y) ^{k} = e ^{-ky} \left( 1 - (k)/(2) y ^{2} - (k)/(3) y ^{3} + (k(k -2 ))/(8) y ^{4} + (k( 5 k -6 ))/(30) y ^{5} + O(y ^{6)} \right) as y → 0 . More elaborate analysis sharpens this tofor and .

The Erdős–Moser equation is equivalent to

1 = \sum ^{m -1} _{j =1} \left( 1 - (j)/(m) \right) ^{k.} Applying to each term in this sum yields\begin{align} T _{0} - (k)/(2 m ^{2}) T _{2} - (k)/(3 m ^{3}) T _{3} + (k(k -2 ))/(8 m ^{4}) T _{4} + (k( 5 k -6 ))/(30 m ^{5}) T _{5} - (k ^{3})/(6 m ^{6}) T _{6} \\ < \sum ^{m -1} _{j =1} \left( 1 - (j)/(m) \right) ^{k} < T _{0} - (k)/(2 m ^{2}) T _{2} - (k)/(3 m ^{3}) T _{3} + (k(k -2 ))/(8 m ^{4}) T _{4} + (k ^{2})/(2 m ^{5}) T _{5, \end{align}} where T _{n} = \sum ^{m -1} _{j =1} j ^{n} z ^{j} and . Further manipulation eventually yieldsWe already know that is bounded as ; making the ansatz, and therefore, and substituting it into yields1 - (1)/(e ^{c} -1) = O\left( (1)/(m) \right) as m → inf ty; therefore . We therefore haveand so(1)/(z) = e ^{k/m} = 2 + (2 a)/(m) + (a ^{2+2b})/(m ^{2}) + O\left( (1)/(m ^{3}) \right) as m → inf ty. Substituting these formulas into yields and . Putting these into yields(k)/(m) = ln ( 2 ) \left( 1 - (3)/(2 m) - ((25)/(- 3ln ( 2 ) 12))/(m ^{2}) + O\left( (1)/(m ^{3}) \right) \right) as m → inf ty. The term must be bounded effectively. To that end, we define the functionF(x, λ ) = \left.\left( 1 - (1)/(t -1) + (x λ)/(2) (t + t ^{2})/((t -1 ) ^{3}) + (x ^{2λ})/(3) (t +4 t ^{2+t} ^{3})/((t -1 ) ^{4}) - (x ^{2λ(λ-2x)})/(8) (t +11 t ^{2+11t} ^{3+t} ^{4})/((t -1 ) ^{5}) \right) \right\vert _{t = e ^{λ}} . The inequality then takes the formand we further have\begin{align} F(x, ln ( 2 ) ( 1 - \tfrac{ 3 }{ 2 }x \phantom{ - 0 . 004 x ^{2}))} &> \phantom{ - } 0 . 005 \phantom{ 15 }x ^{2} - 100 x ^{3} and \\ F(x, ln ( 2 ) ( 1 - \tfrac{ 3 }{ 2 }x - 0 . 004 x ^{2))} &< -0 . 00015 x ^{2} + 100 x ^{3 \end{align}} for . Therefore\begin{align} F \left( (1)/(m) , ln ( 2 ) \left( 1 - (3)/(2 m) \phantom{ - (0 . 004)/(m ^{2}) } \right) \right) &> \phantom{ - } (110000)/(m ^{3}) for m > 2202 ⋅ 10 ^{4} and \\ F \left( (1)/(m) , ln ( 2 ) \left( 1 - (3)/(2 m) - (0 . 004)/(m ^{2}) \right) \right) &< - (110000)/(m ^{3}) for m > \phantom{ 0 } 734 ⋅ 10 ^{6. \end{align}} Comparing these with then shows that, for, we haveln ( 2 ) \left( 1 - (3)/(2 m) - (0 . 004)/(m ^{2}) \right) < (k)/(m) < ln ( 2 ) \left( 1 - (3)/(2 m) \right), and therefore0 < ln ( 2 ) - (2 k)/(2 m -3) < (0 . 0111)/(( 2 m -3 ) ^{2}) . Recalling that Moser showed that indeed, and then invoking Legendre's theorem on continued fractions, finally proves that must be a convergent to . Leveraging this result, 31 billion decimal digits of can be used to exclude any nontrivial solutions below .

See also

• List of conjectures by Paul Erdős
• List of things named after Paul Erdős
• List of unsolved problems in mathematics
• Sums of powers