# Erdős–Moser equation

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$^1$ + 2$^1$ = 3$^1$, and Paul Erdős conjectured that no further solutions exist. Any further solutions must have m > 10$^{109}$.
Throughout this article, p refers exclusively to prime numbers.

## Constraints on solutions

In 1953, Leo Moser proved that, in any further solutions,
* k is even,
* p | (m − 1) implies (p − 1) | k,
* p | (m + 1) implies (p − 1) | k,
* p | (2m + 1) implies (p − 1) | k,
* m − 1 is squarefree,
* m + 1 is either squarefree or 4 times an odd squarefree number,
* 2m − 1 is squarefree,
* 2m + 1 is squarefree,
* $\sum _{p|(m-1)}{\frac {m-1}{p}}\equiv -1{\pmod {m-1}},$
* $\sum _{p|(m+1)}{\frac {m+1}{p}}\equiv -2{\pmod {m+1}}\quad {\text{(if }}m+1{\text{ is even)}},$
* $\sum _{p|(2m-1)}{\frac {2m-1}{p}}\equiv -2{\pmod {2m-1}},$
* $\sum _{p|(2m+1)}{\frac {2m+1}{p}}\equiv -4{\pmod {2m+1}},$ and
* m > 10$^{106}$.
In 1966, it was additionally shown that
* 6 ≤ k + 2 < m < 3 (k + 1) / 2, and
* m – 1 cannot be prime.
In 1994, it was shown that
* lcm(1,2,…,200) divides k,
* m ≡ 3 (mod 2$^{ord2(k)+3}$), where ord$_2$(n) is the 2-adic valuation of n; equivalently, ord$_2$(m − 3) = ord$_2$(k) + 3,
* for any odd prime p divding m, we have k ≢ 0, 2 (mod p − 1),
* 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$^{:§4}$ that k must be a multiple of 2$^3$ · 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$^{427}$.
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
* m ≡ 3 (mod 8) and m ≡ ±1 (mod 3), and
* (m$^2$ – 1) (4m$^2$ – 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 nth 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
which upon multiplying by p yields
    $p+m-1\equiv 0{\pmod {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)}\left(1+{\frac {m-1}{p}}\right)\equiv 0{\pmod {m-1}}.$
Expanding out the product yields
    $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
    $1+\sum _{p|(m-1)}{\frac {m-1}{p}}\equiv 0{\pmod {m-1}}.$
Dividing out the modulus yields
Similar reasoning yields the congruences
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
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\leq x}{\frac {1}{p}}<3.16$, then $M>\prod _{p\leq x}p$. In Moser's original paper, bounds on the prime-counting function are used to observe that
    $\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$^{106}$ 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}}\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$^{106}$.
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}$.$^{:Thm2}$

## 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.$^{:§1¶2}$
The sum S$_k$(m) = 1$^k$ + 2$^k$ + ⋯ + (m – 1)$^k$ is the upper Riemann sum corresponding to the integral ∫$_0$$^{m−1}$x$^k$dx{\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
    $S_{k}(m)>\int _{0}^{m-1}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
Similarly, S$_k$(m) is the lower Riemann sum corresponding to the integral ∫$_1$$^m$x$^k$dx{\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
    $S_{k}(m)\leq \int _{1}^{m}x^{k}\;\mathrm {d} x.$
By hypothesis, S$_k$(m) = m$^k$, so
    $m^{k}\leq {\frac {m^{k+1}-1}{k+1}}<{\frac {m^{k+1}}{k+1}},$
and so
Applying this to (7) yields
    ${\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
    ${\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:$^{:Lemat4}$
Let r be a positive integer. Then the binomial theorem yields
    $(\ell +1)^{r+1}=\sum _{i=0}^{r+1}{\binom {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}{\binom {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}{\binom {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}{\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 _{i=2}^{r+1}{\binom {r+1}{i}}S_{r+1-i}(m)$
Taking r = k yields
    $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
    $m^{k+1}=1+(k+1)m^{k}+\sum _{i=2}^{k+1}{\binom {k+1}{i}}S_{k+1-i}(m)$
Since the RHS is positive, we must therefore have
Returning to (9) and taking r = k − 1 yields
    $m^{k}=1+k\cdot S_{k-1}(m)+\sum _{i=2}^{k}{\binom {k}{i}}S_{k-i}(m)$
    $m^{k}=1+\sum _{s=1}^{k}{\binom {k}{s}}S_{k-s}(m).$
Substituting this into (10) to eliminate m$^k$ yields
    $\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
    $\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)$
    $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)$
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}\left({\frac {k+1}{s+1}}-1\right){\binom {k}{s}}S_{k-s}(k+2)$
    $0=\sum _{s=1}^{k}{\frac {k-s}{s+1}}{\binom {k}{s}}S_{k-s}(k+2)$
    $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)$
    $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
    $k+2<m.$
We therefore observe that the left-hand side of (12) is positive, so
Since k > 1, the sequence $\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,
    $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}\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
for k > 8 and 0 < y < 1.
The Erdős–Moser equation is equivalent to
    $1=\sum _{j=1}^{m-1}\left(1-{\frac {j}{m}}\right)^{k}.$
Applying (14) to each term in this sum yields
    ${\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 $T_{n}=\sum _{j=1}^{m-1}j^{n}z^{j}$ and z = e$^{−k/m}$. Further manipulation eventually yields
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)\quad {\text{as }}m\rightarrow \infty ;$
therefore c = ln(2). We therefore have
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)\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
    ${\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$^3$) must be bounded effectively. To that end, we define the function
    $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
and we further have
    ${\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
    ${\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$^9$, we have
    $\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
    $0<\ln(2)-{\frac {2k}{2m-3}}<{\frac {0.0111}{(2m-3)^{2}}}.$
Recalling that Moser showed that indeed m > 10$^9$, 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$^{109}$.