Erdős–Moser equation

Unsolved problem in mathematics:

Does the Erdős–Moser equation have solutions other than 1¹+2¹=3¹?

(more unsolved problems in mathematics)

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

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

where m and k are restricted to the positive integers—that is, it is considered as a Diophantine equation. The only known solution is 1¹ + 2¹ = 3¹, and Paul Erdős conjectured that no further solutions exist. Any further solutions must have m > 10¹⁰⁹. Some care must be taken when comparing research papers on this equation, because some articles express it in the form 1^k + 2^k + ⋯ + m^k = (m + 1)^k instead. Throughout this article, p refers exclusively to prime numbers.

Constraints on solutions

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

1. k is even,
2. p | (m − 1) implies (p − 1) | k,
3. p | (m + 1) implies (p − 1) | k,
4. p | (2m + 1) implies (p − 1) | k,
5. m − 1 is squarefree,
6. m + 1 is either squarefree or 4 times an odd squarefree number,
7. 2m − 1 is squarefree,
8. 2m + 1 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. m > 10¹⁰⁶.

In 1966, it was additionally shown that

1. 6 ≤ k + 2 < m < 3 (k + 1) / 2, and
2. m – 1 cannot be prime.

In 1994, it was shown that

1. lcm(1,2,…,200) divides k,
2. m ≡ 3 (mod 2^{ord₂(k) + 3}), where ord₂(n) is the 2-adic valuation of n; equivalently, ord₂(m − 3) = ord₂(k) + 3,
3. for any odd prime p divding m, we have k ≢ 0, 2 (mod p − 1),
4. any prime factor of m must be irregular and > 10000.

In 1999, Moser's method was refined to show that m > 1.485 × 10^9,321,155. In 2002, it was shown that k must be a multiple of 2³ · 3# · 5# · 7# · 19# · 1000#, where the symbol # indicates the primorial; that is, n# is the product of all prime numbers ≤ n. This number exceeds 5.7462 × 10⁴²⁷. In 2009, it was shown that 2k / (2m – 3) must be a convergent of ln(2); 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 m > 2.7139 × 10^{1,667,658,416}. In 2010, it was shown that

1. m ≡ 3 (mod 8) and m ≡ ±1 (mod 3), and
2. (m² – 1) (4m² – 1) / 12 has at least 4,990,906 prime factors, none of which are repeated.

The number 4,990,906 arises from the fact that ∑^4990905
_n=1 ⁠1/p_n⁠ < ⁠19/6⁠ < ∑^4990906
_n=1 ⁠1/p_n⁠, where p_n is the n^th prime number.

Moser's method

First, let p be a prime factor of m − 1. Leo Moser showed that this implies that p − 1 divides k and that

$1+\frac{m-1}{p}\equiv 0(\mathrm{mod}p),$

(1)

which upon multiplying by p yields

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

This in turn implies that m − 1 must be squarefree. Furthermore, since nontrivial solutions have m − 1 > 2 and since all squarefree numbers in this range must have at least one odd prime factor, the assumption that p − 1 divides k implies that k must be even. One congruence of the form (1) exists for each prime factor p of m − 1. 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 (m − 1) / p, with different values of p in each factor. These terms are all divisible by m − 1, 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

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

(2)

Similar reasoning yields the congruences

$\frac{2}{m+1}+\sum _{p|(m+1)}\frac{1}{p}\equiv 0(\mathrm{mod}1)\text{(if }m+1\text{ is even)},$

(3)

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

(4)

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

(5)

The congruences (2), (3), (4), and (5) are quite restrictive; for example, the only values of m < 1000 which satisfy (2) are 3, 7, and 43, and these are ruled out by (4). We now split into two cases: either m + 1 is even, or it is odd. In the case that m + 1 is even, adding the left-hand sides of the congruences (2), (3), (4), and (5) must yield an integer, and this integer must be at least 4. Furthermore, the Euclidean algorithm shows that no prime p > 3 can divide more than one of the numbers in the set {m − 1, m + 1, 2m − 1, 2m + 1}, and that 2 and 3 can divide at most two of these numbers. Letting M = (m − 1) (m + 1) (2m − 1) (2m + 1), we then have

$\frac{1}{m-1}+\frac{2}{m+1}+\frac{2}{2m-1}+\frac{4}{2m+1}+\sum _{p|M}\frac{1}{p}\ge 4-\frac{1}{2}-\frac{1}{3}=3.1666....$

(6)

Since there are no nontrivial solutions with m < 1000, the part of the LHS of (6) outside the sigma cannot exceed 0.006; we therefore have

$\sum _{p|M}\frac{1}{p}>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}<3.16.$

Therefore, M must exceed the product of the first 10,000,000 primes. This in turn implies that m > 10¹⁰⁶ in this case. In the case that m + 1 is odd, we cannot use (3), so instead of (6) 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}=2.666...,$

where N = (m − 1) (2m − 1) (2m + 1). On the surface, this appears to be a weaker condition than (6), but since m + 1 is odd, the prime 2 cannot appear on the greater side of this inequality, and it turns out to be a stronger restriction on m than the other case. Therefore any nontrivial solutions have m > 10¹⁰⁶. In 1999, this method was refined by using computers to replace the prime-counting estimates with exact computations; this yielded the bound m > 1.485 × 10^9,321,155.

Bounding the ratio m / (k + 1)

Let S_k(m) = 1^k + 2^k + ⋯ + (m – 1)^k. Then the Erdős–Moser equation becomes S_k(m) = m^k.

Method 1: Integral comparisons

By comparing the sum S_k(m) to definite integrals of the function x^k, one can obtain the bounds 1 < m / (k + 1) < 3. The sum S_k(m) = 1^k + 2^k + ⋯ + (m – 1)^k 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 x, so we have

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

By hypothesis, S_k(m) = m^k, so

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

which leads to

$\frac{m}{k+1}<{(1+\frac{1}{m-1})}^{k+1}.$

(7)

Similarly, S_k(m) 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 x, so we have

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

By hypothesis, S_k(m) = m^k, so

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

and so

$k+1<m.$

(8)

Applying this to (7) 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 m ≤ 10, so we have

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

Combining this with (8) yields 1 < m / (k + 1) < 3, as desired.

Method 2: Algebraic manipulations

The upper bound m / (k + 1) < 3 can be reduced to m / (k + 1) < 3/2 using an algebraic method: Let r 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 ℓ 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)$

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

(9)

Taking r = k 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, S_k = m^k, so

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

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

(10)

Since the RHS is positive, we must therefore have

$k+1<m.$

(11)

Returning to (9) and taking r = k − 1 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 (10) to eliminate m^k 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 i = s + 1 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)$

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

(12)

We already know from (11) that k + 1 < m. This leaves open the possibility that m = k + 2; however, substituting this into (12) 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 k > 1, since the sum contains only positive terms. Therefore any nontrivial solutions must have m ≠ k + 2; combining this with (11) yields

$k+2<m.$

We therefore observe that the left-hand side of (12) is positive, so

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

(13)

Since k > 1, the sequence ${\{(k+1)/(s+1)-m+(k+1)\}}_{s=1}^{\mathrm{\infty }}$ is decreasing. This and (13) together imply that its first term (the term with s = 1) 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, 2k / (2m − 3) must be a convergent of that number. By expanding the Taylor series of (1 − y)^k e^ky about y = 0, 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

$\begin{array}{r}{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-\frac{k^3}{6}{y}^6)\\ <(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^2}{2}{y}^5)\end{array}$

(14)

for k > 8 and 0 < y < 1. The Erdős–Moser equation is equivalent to

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

Applying (14) to each term in this sum yields

$\begin{array}{r}{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 z = e^−k/m. Further manipulation eventually yields

$|1-\frac{z}{1-z}+\frac{k}{2m^2}\frac{z^2+z}{(1-z{)}^3}+\frac{k}{3m^3}\frac{z^3+4z^2+z}{(1-z{)}^4}-\frac{k(k-2)}{8m^4}\frac{z^4+11z^3+11z^2+z}{(1-z{)}^5}|<\frac{110000}{m^3}.$

(15)

We already know that k/m is bounded as m → ∞; making the ansatz k/m = c + O(1/m), and therefore z = e^−c + O(1/m), and substituting it into (15) yields

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

therefore c = ln(2). We therefore have

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

(16)

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 (15) yields a = −3 ln(2) / 2 and b = (3 ln(2) − 25/12) ln(2). Putting these into (16) 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 O(1/m³) 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 (15) then takes the form

$\left|F(\frac{1}{m},\frac{k}{m})\right|<\frac{110000}{m^3},$

(17)

and we further have

$\begin{array}{rl}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 x ≤ 0.01. Therefore

$\begin{array}{rl}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 (17) then shows that, for m > 10⁹, 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 m > 10⁹, and then invoking Legendre's theorem on continued fractions, finally proves that 2k / (2m – 3) must be a convergent to ln(2). Leveraging this result, 31 billion decimal digits of ln(2) can be used to exclude any nontrivial solutions below 10¹⁰⁹.

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