Erdős–Moser equation

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

${\displaystyle 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. As of 2024, the problem remains open, but it has been shown that any further solutions must have m > 10¹⁰⁹.^[1]

Some care must be taken when comparing research papers on this equation, because some articles^[2] study it in the form 1^k + 2^k + ⋯ + m^k = (m + 1)^k instead.

Constraints on solutions

In 1953, Leo Moser proved that, in any further solutions,^[3]

1. p | (m − 1) implies (p − 1) | k,
2. m − 1 is squarefree,
3. k is even,
4. ${\displaystyle \sum _{p|(m-1)}{\frac {m-1}{p}}\equiv -1{\pmod {m-1}},}$
5. p | (m + 1) implies (p − 1) | k,
6. m + 1 is either squarefree or 4 times an odd squarefree number,
7. ${\displaystyle \sum _{p|(m+1)}{\frac {m+1}{p}}\equiv -2{\pmod {m+1}},}$
8. 2m − 1 is squarefree,
9. ${\displaystyle \sum _{p|(2m-1)}{\frac {2m-1}{p}}\equiv -2{\pmod {2m-1}},}$
10. p | (2m + 1) implies (p − 1) | k,
11. 2m + 1 is squarefree,
12. ${\displaystyle \sum _{p|(2m+1)}{\frac {2m+1}{p}}\equiv -4{\pmod {2m+1}},}$ and
13. m > 10¹⁰⁶.

In 1966, it was additionally shown that^[2]

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

In 1994, it was shown that^[4]

1. lcm(1,2,…,200) divides k,
2. ord₂(m − 3) = ord₂(k) + 3, where ord₂(n) is the 2-adic valuation of n,
3. for any prime p divding m, we have k ≢ 0, 2 (mod p − 1),
4. m ≡ 3 (mod 8), and
5. 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.^[5]

In 2002, it was shown^[6] 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}.^[1]

In 2010, it was shown that^[7]

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 ${\displaystyle \sum _{n=1}^{4990905}{\frac {1}{p_{n}}}<{\frac {19}{6}}<\sum _{i=1}^{4990906}{\frac {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^[3] that this implies that p − 1 divides k and that

${\displaystyle 1+{\frac {m-1}{p}}\equiv 0{\pmod {p}},}$

(1)

which upon multiplying by p yields

${\displaystyle p+m-1\equiv 0{\pmod {p^{2}}}.}$

This in turn implies that m − 1 must be squarefree. Furthermore, it is easily checked that, in any nontrivial solutions, m − 1 > 2; since all squarefree numbers in this range must have at least one odd prime factor, the fact 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

${\displaystyle \prod _{p|(m-1)}\left(1+{\frac {m-1}{p}}\right)\equiv 0{\pmod {m-1}}.}$

Expanding out the product yields

${\displaystyle 1+\sum _{p|(m-1)}{\frac {m-1}{p}}+({\text{higher-order terms}})\equiv 0{\pmod {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

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

Dividing out the modulus yields

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

(2)

Similar reasoning yields the congruences

${\displaystyle {\frac {2}{m+1}}+\sum _{p|(m+1)}{\frac {1}{p}}\equiv 0{\pmod {1}},}$

(3)

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

(4)

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

(5)

The validity of (3) relies on m + 1 being even.

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

${\displaystyle {\frac {1}{m-1}}+{\frac {2}{m+1}}+{\frac {2}{2m-1}}+{\frac {4}{2m+1}}+\sum _{p|M}{\frac {1}{p}}\geq 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

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

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

${\displaystyle \sum _{p\leq 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

${\displaystyle {\frac {1}{m-1}}+{\frac {2}{2m-1}}+{\frac {4}{2m+1}}+\sum _{p|N}{\frac {1}{p}}\geq 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.^[5]

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 ${\textstyle \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

${\displaystyle S_{k}(m)>\int _{0}^{m-1}x^{k}\;\mathrm {d} x.}$

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

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

which leads to

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

(7)

Similarly, S_k(m) is the lower Riemann sum corresponding to the integral ${\textstyle \int _{1}^{m}x^{k}\,\mathrm {d} x}$ in which the interval has been partitioned on the integer values of x, so we have

${\displaystyle S_{k}(m)\leq \int _{1}^{m}x^{k}\;\mathrm {d} x.}$

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

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

and so

${\displaystyle k+1<m.}$

(8)

Applying this to (7) yields

${\displaystyle {\frac {m}{k+1}}<\left(1+{\frac {1}{m-1}}\right)^{m}=\left(1+{\frac {1}{m-1}}\right)^{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

${\displaystyle {\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 first published in ^[2].

Let r be a positive integer. Then the binomial theorem yields

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

Summing over ℓ yields

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

Reindexing on the left and rearranging on the right yields

${\displaystyle \sum _{\ell =2}^{m}\ell ^{r+1}=\sum _{i=0}^{r+1}{\binom {r+1}{i}}\sum _{\ell =1}^{m-1}\ell ^{r+1-i}}$

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

${\displaystyle S_{r+1}(m+1)-S_{r+1}(m)=1+(r+1)S_{r}(m)+\sum _{i=2}^{r+1}{\binom {r+1}{i}}S_{r+1-i}(m)}$

${\displaystyle m^{r+1}=1+(r+1)S_{r}(m)+\sum _{i=2}^{r+1}{\binom {r+1}{i}}S_{r+1-i}(m).}$

(9)

Taking r = k yields

${\displaystyle m^{k+1}=1+(k+1)S_{k}(m)+\sum _{i=2}^{k+1}{\binom {k+1}{i}}S_{k+1-i}(m).}$

By hypothesis, S_k = m^k, so

${\displaystyle m^{k+1}=1+(k+1)m^{k}+\sum _{i=2}^{k+1}{\binom {k+1}{i}}S_{k+1-i}(m)}$

${\displaystyle m^{k}(m-(k+1))=1+\sum _{i=2}^{k+1}{\binom {k+1}{i}}S_{k+1-i}(m).}$

(10)

Since the RHS is positive, we must therefore have

${\displaystyle k+1<m.}$

(11)

Returning to (9) and taking r = k − 1 yields

${\displaystyle m^{k}=1+k\cdot S_{k-1}(m)+\sum _{i=2}^{k}{\binom {k}{i}}S_{k-i}(m)}$

${\displaystyle m^{k}=1+\sum _{s=1}^{k}{\binom {k}{s}}S_{k-s}(m).}$

Substituting this into (10) to eliminate m^k yields

${\displaystyle \left(1+\sum _{s=1}^{k}{\binom {k}{s}}S_{k-s}(m)\right)(m-(k+1))=1+\sum _{i=2}^{k+1}{\binom {k+1}{i}}S_{k+1-i}(m).}$

Reindexing the sum on the right with the substitution i = s + 1 yields

${\displaystyle \left(1+\sum _{s=1}^{k}{\binom {k}{s}}S_{k-s}(m)\right)(m-(k+1))=1+\sum _{s=1}^{k}{\binom {k+1}{s+1}}S_{k-s}(m)}$

${\displaystyle m-(k+1)+(m-(k+1))\sum _{s=1}^{k}{\binom {k}{s}}S_{k-s}(m)=1+\sum _{s=1}^{k}{\frac {k+1}{s+1}}{\binom {k}{s}}S_{k-s}(m)}$

${\displaystyle m-k-2=\sum _{s=1}^{k}\left({\frac {k+1}{s+1}}-m+(k+1)\right){\binom {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

${\displaystyle 0=\sum _{s=1}^{k}\left({\frac {k+1}{s+1}}-1\right){\binom {k}{s}}S_{k-s}(k+2)}$

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

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

${\displaystyle 0=0+\sum _{s=1}^{k-1}{\frac {k-s}{s+1}}{\binom {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

${\displaystyle k+2<m.}$

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

${\displaystyle 0<\sum _{s=1}^{k}\left({\frac {k+1}{s+1}}-m+(k+1)\right){\binom {k}{s}}S_{k-s}(m).}$

(13)

Since k > 1, the sequence ${\displaystyle \left\{(k+1)/(s+1)-m+(k+1)\right\}_{s=1}^{\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,

${\displaystyle 0<{\frac {k+1}{1+1}}-m+(k+1),}$

which yields

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

and therefore

${\displaystyle {\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.^[1]

By expanding the Taylor series of (1 − y)^k e^ky about y = 0, one finds

${\displaystyle (1-y)^{k}=e^{-ky}\left(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})\right)\quad {\text{as }}y\rightarrow 0.}$

More elaborate analysis sharpens this to

${\displaystyle {\begin{aligned}e^{-ky}\left(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}\right)\\<(1-y)^{k}<e^{-ky}\left(1-{\frac {k}{2}}y^{2}-{\frac {k}{3}}y^{3}+{\frac {k(k-2)}{8}}y^{4}+{\frac {k^{2}}{2}}y^{5}\right)\end{aligned}}}$

(14)

for k > 8 and 0 < y < 1.

The Erdős–Moser equation is equivalent to

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

Applying (14) to each term in this sum yields

${\displaystyle {\begin{aligned}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}\qquad \qquad \\<\sum _{j=1}^{m-1}\left(1-{\frac {j}{m}}\right)^{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{aligned}}}$

where ${\displaystyle T_{n}=\sum _{j=1}^{m-1}j^{n}z^{j}}$ and z = e^−k/m. Further manipulation eventually yields

${\displaystyle \left\vert 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}}}\right\vert <{\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

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

therefore c = ln(2). We therefore have

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

(16)

and so

${\displaystyle {\frac {1}{z}}=e^{k/m}=2+{\frac {2a}{m}}+{\frac {a^{2}+2b}{m^{2}}}+O\left({\frac {1}{m^{3}}}\right)\quad {\text{as }}m\rightarrow \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

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

The term O(1/m³) must be bounded effectively. To that end, we define the function

${\displaystyle F(x,\lambda )=\left.\left(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}}}\right)\right\vert _{t=e^{\lambda }}.}$

The inequality (15) then takes the form

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

(17)

and we further have

${\displaystyle {\begin{aligned}F(x,\ln(2)(1-{\tfrac {3}{2}}x\,{\phantom {-\;0.004x^{2}}}))&>{\phantom {-}}0.005{\phantom {15}}x^{2}-100x^{3}\quad {\text{and}}\\F(x,\ln(2)(1-{\tfrac {3}{2}}x-0.004x^{2}))&<-0.00015x^{2}+100x^{3}\end{aligned}}}$

for x ≤ 0.01. Therefore

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

Comparing these with (17) then shows that, for m > 10⁹, we have

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

and therefore

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

Recalling that Moser showed^[3] 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, the authors of ^[1] used 31 billion decimal digits of ln(2) to exclude any nontrivial solutions below 10¹⁰⁹.

References