Erdős–Moser equation

Template:Short description Template:Unsolved In number theory, the Erdős–Moser equation is

$1^k+2^k+\cdots +(m-1{)}^k=m^k,$

where Template:Mvar and Template:Mvar are restricted to the positive integers—that is, it is considered as a Diophantine equation. The only known solution is Template:Math, and Paul Erdős conjectured that no further solutions exist. Any further solutions must have Template:Math.

Throughout this article, Template:Mvar refers exclusively to prime numbers.

Constraints on solutions

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

1. Template:Mvar is even,
2. Template:Math implies Template:Math,
3. Template:Math implies Template:Math,
4. Template:Math implies Template:Math,
5. Template:Math is squarefree,
6. Template:Math is either squarefree or 4 times an odd squarefree number,
7. Template:Math is squarefree,
8. Template:Math is squarefree,
9. $\sum _{p|(m-1)}\frac{m-1}{p}\equiv -1(\mathrm{mod}m-1),$
10. $\sum _{p|(m+1)}\frac{m+1}{p}\equiv -2(\mathrm{mod}m+1)\text{(if }m+1\text{ is even)},$
11. $\sum _{p|(2m-1)}\frac{2m-1}{p}\equiv -2(\mathrm{mod}2m-1),$
12. $\sum _{p|(2m+1)}\frac{2m+1}{p}\equiv -4(\mathrm{mod}2m+1),$ and
13. Template:Math.

In 1966, it was additionally shown that

1. Template:Math, and
2. Template:Math cannot be prime.

In 1994, it was shown that

1. [[Least common multiple|Template:Math]] divides Template:Mvar,
2. Template:Math, where Template:Math is the 2-adic valuation of Template:Mvar; equivalently, Template:Math,
3. for any odd prime Template:Mvar dividing Template:Mvar, we have Template:Math,
4. any prime factor of Template:Mvar must be irregular and > 10000.

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

In 2002, it was shownTemplate:R that Template:Mvar must be a multiple of Template:Math, where the symbol Template:Mvar indicates the primorial; that is, Template:Math is the product of all prime numbers Template:Math. This number exceeds Template:Math.

In 2009, it was shown that Template:Math must be a convergent of [[Natural logarithm of 2|Template:Math]]; 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 Template:Math.

In 2010, it was shown that

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

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

Moser's method

First, let Template:Mvar be a prime factor of Template:Math. Leo Moser showed that this implies that Template:Math divides Template:Mvar and that Template:NumBlk which upon multiplying by Template:Mvar yields

$p+m-1\equiv 0(\mathrm{mod}{p}^2).$

This in turn implies that Template:Math must be squarefree. Furthermore, since nontrivial solutions have Template:Math and since all squarefree numbers in this range must have at least one odd prime factor, the assumption that Template:Math divides Template:Mvar implies that Template:Mvar must be even.

One congruence of the form (Template:EquationNote) exists for each prime factor Template:Mvar of Template:Math. Multiplying all of them together yields

$\prod _{p|(m-1)}(1+\frac{m-1}{p})\equiv 0(\mathrm{mod}m-1).$

Expanding out the product yields

$1+\sum _{p|(m-1)}\frac{m-1}{p}+(\text{higher-order terms})\equiv 0(\mathrm{mod}m-1),$

where the higher-order terms are products of multiple factors of the form Template:Math, with different values of Template:Mvar in each factor. These terms are all divisible by Template:Math, so they all drop out of the congruence, yielding

$1+\sum _{p|(m-1)}\frac{m-1}{p}\equiv 0(\mathrm{mod}m-1).$

Dividing out the modulus yields Template:NumBlk Similar reasoning yields the congruences Template:NumBlk Template:NumBlk Template:NumBlk

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

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

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

$\sum _{p|M}\frac{1}{p}>\mathrm{3.16.}$

Therefore, if $\sum _{p\le x}\frac{1}{p}<3.16$, then $M>\prod _{p\le x}p$. In Moser's original paper, bounds on the prime-counting function are used to observe that

$\sum _{p\le 10^7}\frac{1}{p}<\mathrm{3.16.}$

Therefore, Template:Mvar must exceed the product of the first 10,000,000 primes. This in turn implies that Template:Math in this case.

In the case that Template:Math is odd, we cannot use (Template:EquationNote), so instead of (Template:EquationNote) we obtain

$\frac{1}{m-1}+\frac{2}{2m-1}+\frac{4}{2m+1}+\sum _{p|N}\frac{1}{p}\ge 3-\frac{1}{3}=\mathrm{2.666...},$

where Template:Math. On the surface, this appears to be a weaker condition than (Template:EquationNote), but since Template:Math is odd, the prime 2 cannot appear on the greater side of this inequality, and it turns out to be a stronger restriction on Template:Mvar than the other case.

Therefore, any nontrivial solutions have Template:Math.

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

Bounding the ratio Template:Math

Let Template:Math. Then the Erdős–Moser equation becomes Template:Math.

Method 1: Integral comparisons

By comparing the sum Template:Math to definite integrals of the function Template:Math, one can obtain the bounds Template:Math.Template:R

The sum Template:Math is the upper Riemann sum corresponding to the integral ${\int }_0^{m-1}{x}^k\mathrm{d}x$ in which the interval has been partitioned on the integer values of Template:Mvar, so we have

$S_k(m)>{\int }_0^{m-1}{x}^k\mathrm{d}x.$

By hypothesis, Template:Math, so

$m^k>\frac{(m-1{)}^{k+1}}{k+1},$

which leads to Template:NumBlk Similarly, Template:Math is the lower Riemann sum corresponding to the integral ${\int }_1^m{x}^k\mathrm{d}x$ in which the interval has been partitioned on the integer values of Template:Mvar, so we have

$S_k(m)\le {\int }_1^m{x}^k\mathrm{d}x.$

By hypothesis, Template:Math, so

$m^k\le \frac{m^{k+1}-1}{k+1}<\frac{m^{k+1}}{k+1},$

and so Template:NumBlk Applying this to (Template:EquationNote) yields

$\frac{m}{k+1}<{(1+\frac{1}{m-1})}^m={(1+\frac{1}{m-1})}^{m-1}\cdot \left(\frac{m}{m-1}\right)<e\cdot \frac{m}{m-1}.$

Computation shows that there are no nontrivial solutions with Template:Math, so we have

$\frac{m}{k+1}<e\cdot \frac{11}{11-1}<3.$

Combining this with (Template:EquationNote) yields Template:Math, as desired.

Method 2: Algebraic manipulations

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

Let Template:Mvar be a positive integer. Then the binomial theorem yields

$(\ell +1{)}^{r+1}=\sum _{i=0}^{r+1}(\genfrac{}{}{0ex}{}{r+1}{i}){\ell }^{r+1-i}.$

Summing over Template:Mvar yields

$\sum _{\ell =1}^{m-1}(\ell +1{)}^{r+1}=\sum _{\ell =1}^{m-1}\left(\sum _{i=0}^{r+1}(\genfrac{}{}{0ex}{}{r+1}{i}){\ell }^{r+1-i}\right).$

Reindexing on the left and rearranging on the right yields

$\sum _{\ell =2}^m{\ell }^{r+1}=\sum _{i=0}^{r+1}(\genfrac{}{}{0ex}{}{r+1}{i})\sum _{\ell =1}^{m-1}{\ell }^{r+1-i}$

$\sum _{\ell =1}^m{\ell }^{r+1}=1+\sum _{i=0}^{r+1}(\genfrac{}{}{0ex}{}{r+1}{i})S_{r+1-i}(m)$

$S_{r+1}(m+1)-S_{r+1}(m)=1+(r+1)S_r(m)+\sum _{i=2}^{r+1}(\genfrac{}{}{0ex}{}{r+1}{i})S_{r+1-i}(m)$

Template:NumBlk Taking Template:Math yields

$m^{k+1}=1+(k+1)S_k(m)+\sum _{i=2}^{k+1}(\genfrac{}{}{0ex}{}{k+1}{i})S_{k+1-i}(m).$

By hypothesis, Template:Math, so

$m^{k+1}=1+(k+1)m^k+\sum _{i=2}^{k+1}(\genfrac{}{}{0ex}{}{k+1}{i})S_{k+1-i}(m)$

Template:NumBlk Since the RHS is positive, we must therefore have Template:NumBlk Returning to (Template:EquationNote) and taking Template:Math yields

$m^k=1+k\cdot S_{k-1}(m)+\sum _{i=2}^k(\genfrac{}{}{0ex}{}{k}{i})S_{k-i}(m)$

$m^k=1+\sum _{s=1}^k(\genfrac{}{}{0ex}{}{k}{s})S_{k-s}(m).$

Substituting this into (Template:EquationNote) to eliminate Template:Math yields

$(1+\sum _{s=1}^k(\genfrac{}{}{0ex}{}{k}{s})S_{k-s}(m))(m-(k+1))=1+\sum _{i=2}^{k+1}(\genfrac{}{}{0ex}{}{k+1}{i})S_{k+1-i}(m).$

Reindexing the sum on the right with the substitution Template:Math yields

$(1+\sum _{s=1}^k(\genfrac{}{}{0ex}{}{k}{s})S_{k-s}(m))(m-(k+1))=1+\sum _{s=1}^k(\genfrac{}{}{0ex}{}{k+1}{s+1})S_{k-s}(m)$

$m-(k+1)+(m-(k+1))\sum _{s=1}^k(\genfrac{}{}{0ex}{}{k}{s})S_{k-s}(m)=1+\sum _{s=1}^k\frac{k+1}{s+1}(\genfrac{}{}{0ex}{}{k}{s})S_{k-s}(m)$

Template:NumBlk We already know from (Template:EquationNote) that Template:Math. This leaves open the possibility that Template:Math; however, substituting this into (Template:EquationNote) yields

$0=\sum _{s=1}^k(\frac{k+1}{s+1}-1)(\genfrac{}{}{0ex}{}{k}{s})S_{k-s}(k+2)$

$0=\sum _{s=1}^k\frac{k-s}{s+1}(\genfrac{}{}{0ex}{}{k}{s})S_{k-s}(k+2)$

$0=\frac{k-k}{k+1}(\genfrac{}{}{0ex}{}{k}{k})S_{k-k}(k+2)+\sum _{s=1}^{k-1}\frac{k-s}{s+1}(\genfrac{}{}{0ex}{}{k}{s})S_{k-s}(k+2)$

$0=0+\sum _{s=1}^{k-1}\frac{k-s}{s+1}(\genfrac{}{}{0ex}{}{k}{s})S_{k-s}(k+2),$

which is impossible for Template:Math, since the sum contains only positive terms. Therefore, any nontrivial solutions must have Template:Math; combining this with (Template:EquationNote) yields

$k+2<m.$

We therefore observe that the left-hand side of (Template:EquationNote) is positive, so Template:NumBlk Since Template:Math, the sequence ${\{(k+1)/(s+1)-m+(k+1)\}}_{s=1}^{\mathrm{\infty }}$ is decreasing. This and (Template:EquationNote) together imply that its first term (the term with Template:Math) 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<\frac{k+1}{1+1}-m+(k+1),$

which yields

$m<\frac{3}{2}\cdot (k+1)$

and therefore

$\frac{m}{k+1}<\frac{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, Template:Math must be a convergent of that number.

By expanding the Taylor series of Template:Math about Template:Math, one finds

$(1-y{)}^k=e^{-ky}(1-\frac{k}{2}{y}^2-\frac{k}{3}{y}^3+\frac{k(k-2)}{8}{y}^4+\frac{k(5k-6)}{30}{y}^5+O(y^6))\text{as }y\to 0.$

More elaborate analysis sharpens this to Template:NumBlk for Template:Math and Template:Math.

The Erdős–Moser equation is equivalent to

$1=\sum _{j=1}^{m-1}{(1-\frac{j}{m})}^k.$

Applying (Template:EquationNote) to each term in this sum yields

$\begin{array}{c}{T}_0-\frac{k}{2m^2}{T}_2-\frac{k}{3m^3}{T}_3+\frac{k(k-2)}{8m^4}{T}_4+\frac{k(5k-6)}{30m^5}{T}_5-\frac{k^3}{6m^6}{T}_6\\ <\sum _{j=1}^{m-1}{(1-\frac{j}{m})}^k<T_0-\frac{k}{2m^2}{T}_2-\frac{k}{3m^3}{T}_3+\frac{k(k-2)}{8m^4}{T}_4+\frac{k^2}{2m^5}{T}_5,\end{array}$

where $T_n=\sum _{j=1}^{m-1}{j}^n{z}^j$ and Template:Math. Further manipulation eventually yields Template:NumBlk We already know that Template:Math is bounded as Template:Math; making the ansatz Template:Math, and therefore Template:Math, and substituting it into (Template:EquationNote) yields

$1-\frac{1}{e^c-1}=O\left(\frac{1}{m}\right)\text{as }m\to \mathrm{\infty };$

therefore Template:Math. We therefore have Template:NumBlk and so

$\frac{1}{z}=e^{k/m}=2+\frac{2a}{m}+\frac{a^2+2b}{m^2}+O\left(\frac{1}{m^3}\right)\text{as }m\to \mathrm{\infty }.$

Substituting these formulas into (Template:EquationNote) yields Template:Math and Template:Math. Putting these into (Template:EquationNote) yields

$\frac{k}{m}=\ln (2)(1-\frac{3}{2m}-\frac{\frac{25}{12}-3\ln (2)}{m^2}+O\left(\frac{1}{m^3}\right))\text{as }m\to \mathrm{\infty }.$

The term Template:Math must be bounded effectively. To that end, we define the function

$F(x,\lambda )={(1-\frac{1}{t-1}+\frac{x\lambda }{2}\frac{t+t^2}{(t-1{)}^3}+\frac{x^2\lambda }{3}\frac{t+4t^2+t^3}{(t-1{)}^4}-\frac{x^2\lambda (\lambda -2x)}{8}\frac{t+11t^2+11t^3+t^4}{(t-1{)}^5})|}_{t=e^{\lambda }}.$

The inequality (Template:EquationNote) then takes the form Template:NumBlk and we further have

$\begin{array}{cc}F(x,\ln (2)(1-\frac{3}{2}x\phantom{-0.004x^2}))& >\phantom{-}0.005\phantom{15}{x}^2-100x^3\text{and}\\ F(x,\ln (2)(1-\frac{3}{2}x-0.004x^2))& <-0.00015x^2+100x^3\end{array}$

for Template:Math. Therefore

$\begin{array}{cc}F(\frac{1}{m},\ln (2)(1-\frac{3}{2m}\phantom{-\frac{0.004}{m^2}}))& >\phantom{-}\frac{110000}{m^3}\text{for }m>2202\cdot 10^4\text{and}\\ F(\frac{1}{m},\ln (2)(1-\frac{3}{2m}-\frac{0.004}{m^2}))& <-\frac{110000}{m^3}\text{for }m>\phantom{0}734\cdot 10^6.\end{array}$

Comparing these with (Template:EquationNote) then shows that, for Template:Math, we have

$\ln (2)(1-\frac{3}{2m}-\frac{0.004}{m^2})<\frac{k}{m}<\ln (2)(1-\frac{3}{2m}),$

and therefore

$0<\ln (2)-\frac{2k}{2m-3}<\frac{0.0111}{(2m-3{)}^2}.$

Recalling that Moser showed that indeed Template:Math, and then invoking Legendre's theorem on continued fractions, finally proves that Template:Math must be a convergent to Template:Math. Leveraging this result, 31 billion decimal digits of Template:Math can be used to exclude any nontrivial solutions below Template:Math.

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
• Template:Annotated link