Diophantine equation 1ᵏ + 2ᵏ + … + (m – 1)ᵏ = mᵏ
Unsolved problem in mathematics :
Does the Erdős–Moser equation have solutions other than 11 +21 =31 ?
In number theory , the Erdős–Moser equation is
1 k + 2 k + ⋯ + ( m − 1 ) k = m k , {\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 11 + 21 = 31 , 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 > 10109 .[1]
Some care must be taken when comparing research papers on this equation, because some articles[2] study it in the form 1k + 2k + ⋯ + mk = (m + 1)k instead.
Throughout this article, p refers exclusively to prime numbers .
Constraints on solutions [ edit ] In 1953, Leo Moser proved that, in any further solutions,[3]
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, ∑ p | ( m − 1 ) m − 1 p ≡ − 1 ( mod m − 1 ) , {\displaystyle \sum _{p|(m-1)}{\frac {m-1}{p}}\equiv -1{\pmod {m-1}},} ∑ p | ( m + 1 ) m + 1 p ≡ − 2 ( mod m + 1 ) , {\displaystyle \sum _{p|(m+1)}{\frac {m+1}{p}}\equiv -2{\pmod {m+1}},} ∑ p | ( 2 m − 1 ) 2 m − 1 p ≡ − 2 ( mod 2 m − 1 ) , {\displaystyle \sum _{p|(2m-1)}{\frac {2m-1}{p}}\equiv -2{\pmod {2m-1}},} ∑ p | ( 2 m + 1 ) 2 m + 1 p ≡ − 4 ( mod 2 m + 1 ) , {\displaystyle \sum _{p|(2m+1)}{\frac {2m+1}{p}}\equiv -4{\pmod {2m+1}},} and m > 10106 . In 1966, it was additionally shown that[2]
6 ≤ k + 2 < m < 3 (k + 1) / 2 , and m – 1 cannot be prime. In 1994, it was shown that[4]
lcm(1,2,…,200) divides k , m ≡ 3 (mod 2ord2 (k ) + 3 ) , where ord2 (n ) is the 2-adic valuation of n ; equivalently, ord2 (m − 3) = ord2 (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 × 109,321,155 .[5]
In 2002, it was shown[6] : §4 that k must be a multiple of 23 · 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 × 10427 .
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 × 101,667,658,416 .[1]
In 2010, it was shown that[7]
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 n th prime number.
Moser's method [ edit ] First, let p be a prime factor of m − 1 . Leo Moser showed[3] that this implies that p − 1 divides k and that
1 + m − 1 p ≡ 0 ( mod p ) , {\displaystyle 1+{\frac {m-1}{p}}\equiv 0{\pmod {p}},} (1 )
which upon multiplying by p yields
p + m − 1 ≡ 0 ( mod p 2 ) . {\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
∏ p | ( m − 1 ) ( 1 + m − 1 p ) ≡ 0 ( mod m − 1 ) . {\displaystyle \prod _{p|(m-1)}\left(1+{\frac {m-1}{p}}\right)\equiv 0{\pmod {m-1}}.} Expanding out the product yields
1 + ∑ p | ( m − 1 ) m − 1 p + ( higher-order terms ) ≡ 0 ( mod m − 1 ) , {\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
1 + ∑ p | ( m − 1 ) m − 1 p ≡ 0 ( mod m − 1 ) . {\displaystyle 1+\sum _{p|(m-1)}{\frac {m-1}{p}}\equiv 0{\pmod {m-1}}.} Dividing out the modulus yields
1 m − 1 + ∑ p | ( m − 1 ) 1 p ≡ 0 ( mod 1 ) . {\displaystyle {\frac {1}{m-1}}+\sum _{p|(m-1)}{\frac {1}{p}}\equiv 0{\pmod {1}}.} (2 )
Similar reasoning yields the congruences
2 m + 1 + ∑ p | ( m + 1 ) 1 p ≡ 0 ( mod 1 ) (if m + 1 is even) , {\displaystyle {\frac {2}{m+1}}+\sum _{p|(m+1)}{\frac {1}{p}}\equiv 0{\pmod {1}}\quad {\text{(if }}m+1{\text{ is even)}},} (3 )
2 2 m − 1 + ∑ p | ( 2 m − 1 ) 1 p ≡ 0 ( mod 1 ) , and {\displaystyle {\frac {2}{2m-1}}+\sum _{p|(2m-1)}{\frac {1}{p}}\equiv 0{\pmod {1}},\quad {\text{and}}} (4 )
4 2 m + 1 + ∑ p | ( 2 m + 1 ) 1 p ≡ 0 ( mod 1 ) . {\displaystyle {\frac {4}{2m+1}}+\sum _{p|(2m+1)}{\frac {1}{p}}\equiv 0{\pmod {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
1 m − 1 + 2 m + 1 + 2 2 m − 1 + 4 2 m + 1 + ∑ p | M 1 p ≥ 4 − 1 2 − 1 3 = 3.1666.... {\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
∑ p | M 1 p > 3.16. {\displaystyle \sum _{p|M}{\frac {1}{p}}>3.16.} Therefore, if ∑ p ≤ x 1 p < 3.16 {\displaystyle \sum _{p\leq x}{\frac {1}{p}}<3.16} , then M > ∏ p ≤ x p {\displaystyle M>\prod _{p\leq x}p} . In Moser's original paper [3] , bounds on the prime-counting function are used to observe that
∑ p ≤ 10 7 1 p < 3.16. {\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 > 10106 in this case.
In the case that m + 1 is odd, we cannot use (3 ), so instead of (6 ) we obtain
1 m − 1 + 2 2 m − 1 + 4 2 m + 1 + ∑ p | N 1 p ≥ 3 − 1 3 = 2.666... , {\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 > 10106 .
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 × 109,321,155 .[5] : Thm 2
Bounding the ratio m / (k + 1) [ edit ] Let S k (m ) = 1k + 2k + ⋯ + (m – 1)k . Then the Erdős–Moser equation becomes S k (m ) = m k .
Method 1: Integral comparisons [ edit ] 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] : §1¶2
The sum S k (m ) = 1k + 2k + ⋯ + (m – 1)k is the upper Riemann sum corresponding to the integral ∫ 0 m − 1 x k d x {\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 ) > ∫ 0 m − 1 x k d x . {\displaystyle S_{k}(m)>\int _{0}^{m-1}x^{k}\;\mathrm {d} x.} By hypothesis, S k (m ) = m k , so
m k > ( m − 1 ) k + 1 k + 1 , {\displaystyle m^{k}>{\frac {(m-1)^{k+1}}{k+1}},} which leads to
m k + 1 < ( 1 + 1 m − 1 ) k + 1 . {\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 ∫ 1 m x k d x {\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 ) ≤ ∫ 1 m x k d x . {\displaystyle S_{k}(m)\leq \int _{1}^{m}x^{k}\;\mathrm {d} x.} By hypothesis, S k (m ) = m k , so
m k ≤ m k + 1 − 1 k + 1 < m k + 1 k + 1 , {\displaystyle m^{k}\leq {\frac {m^{k+1}-1}{k+1}}<{\frac {m^{k+1}}{k+1}},} and so
k + 1 < m . {\displaystyle k+1<m.} (8 )
Applying this to (7 ) yields
m k + 1 < ( 1 + 1 m − 1 ) m = ( 1 + 1 m − 1 ) m − 1 ⋅ ( m m − 1 ) < e ⋅ m m − 1 . {\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
m k + 1 < e ⋅ 11 11 − 1 < 3. {\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 [ edit ] The upper bound m / (k + 1) < 3 can be reduced to m / (k + 1) < 3/2 using an algebraic method first published in [2] : Lemat 4 .
Let r be a positive integer. Then the binomial theorem yields
( ℓ + 1 ) r + 1 = ∑ i = 0 r + 1 ( r + 1 i ) ℓ r + 1 − i . {\displaystyle (\ell +1)^{r+1}=\sum _{i=0}^{r+1}{\binom {r+1}{i}}\ell ^{r+1-i}.} Summing over ℓ yields
∑ ℓ = 1 m − 1 ( ℓ + 1 ) r + 1 = ∑ ℓ = 1 m − 1 ( ∑ i = 0 r + 1 ( r + 1 i ) ℓ r + 1 − i ) . {\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
∑ ℓ = 2 m ℓ r + 1 = ∑ i = 0 r + 1 ( r + 1 i ) ∑ ℓ = 1 m − 1 ℓ r + 1 − i {\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}} ∑ ℓ = 1 m ℓ r + 1 = 1 + ∑ i = 0 r + 1 ( r + 1 i ) S r + 1 − i ( m ) {\displaystyle \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 ) + ∑ i = 2 r + 1 ( 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)} m r + 1 = 1 + ( r + 1 ) S r ( m ) + ∑ i = 2 r + 1 ( 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
m k + 1 = 1 + ( k + 1 ) S k ( m ) + ∑ i = 2 k + 1 ( k + 1 i ) S k + 1 − i ( m ) . {\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
m k + 1 = 1 + ( k + 1 ) m k + ∑ i = 2 k + 1 ( k + 1 i ) S k + 1 − i ( m ) {\displaystyle m^{k+1}=1+(k+1)m^{k}+\sum _{i=2}^{k+1}{\binom {k+1}{i}}S_{k+1-i}(m)} m k ( m − ( k + 1 ) ) = 1 + ∑ i = 2 k + 1 ( 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
k + 1 < m . {\displaystyle k+1<m.} (11 )
Returning to (9 ) and taking r = k − 1 yields
m k = 1 + k ⋅ S k − 1 ( m ) + ∑ i = 2 k ( k i ) S k − i ( m ) {\displaystyle m^{k}=1+k\cdot S_{k-1}(m)+\sum _{i=2}^{k}{\binom {k}{i}}S_{k-i}(m)} m k = 1 + ∑ s = 1 k ( k s ) S k − s ( 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
( 1 + ∑ s = 1 k ( k s ) S k − s ( m ) ) ( m − ( k + 1 ) ) = 1 + ∑ i = 2 k + 1 ( k + 1 i ) S k + 1 − i ( m ) . {\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
( 1 + ∑ s = 1 k ( k s ) S k − s ( m ) ) ( m − ( k + 1 ) ) = 1 + ∑ s = 1 k ( k + 1 s + 1 ) S k − s ( m ) {\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)} m − ( k + 1 ) + ( m − ( k + 1 ) ) ∑ s = 1 k ( k s ) S k − s ( m ) = 1 + ∑ s = 1 k k + 1 s + 1 ( k s ) 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)} m − k − 2 = ∑ s = 1 k ( k + 1 s + 1 − m + ( k + 1 ) ) ( 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
0 = ∑ s = 1 k ( k + 1 s + 1 − 1 ) ( k s ) S k − s ( k + 2 ) {\displaystyle 0=\sum _{s=1}^{k}\left({\frac {k+1}{s+1}}-1\right){\binom {k}{s}}S_{k-s}(k+2)} 0 = ∑ s = 1 k k − s s + 1 ( 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)} 0 = k − k k + 1 ( k k ) S k − k ( k + 2 ) + ∑ s = 1 k − 1 k − s s + 1 ( 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)} 0 = 0 + ∑ s = 1 k − 1 k − s s + 1 ( 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
k + 2 < m . {\displaystyle k+2<m.} We therefore observe that the left-hand side of (12 ) is positive, so
0 < ∑ s = 1 k ( k + 1 s + 1 − m + ( k + 1 ) ) ( k s ) S k − s ( m ) . {\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 { ( k + 1 ) / ( s + 1 ) − m + ( k + 1 ) } s = 1 ∞ {\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,
0 < k + 1 1 + 1 − m + ( k + 1 ) , {\displaystyle 0<{\frac {k+1}{1+1}}-m+(k+1),} which yields
m < 3 2 ⋅ ( k + 1 ) {\displaystyle m<{\frac {3}{2}}\cdot (k+1)} and therefore
m k + 1 < 3 2 , {\displaystyle {\frac {m}{k+1}}<{\frac {3}{2}},} as desired.
Continued fractions [ edit ] 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
( 1 − y ) k = e − k y ( 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 ) ) as y → 0. {\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
e − k y ( 1 − k 2 y 2 − k 3 y 3 + k ( k − 2 ) 8 y 4 + k ( 5 k − 6 ) 30 y 5 − k 3 6 y 6 ) < ( 1 − y ) k < e − k y ( 1 − k 2 y 2 − k 3 y 3 + k ( k − 2 ) 8 y 4 + k 2 2 y 5 ) {\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
1 = ∑ j = 1 m − 1 ( 1 − j m ) k . {\displaystyle 1=\sum _{j=1}^{m-1}\left(1-{\frac {j}{m}}\right)^{k}.} Applying (14 ) to each term in this sum yields
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 < ∑ j = 1 m − 1 ( 1 − j m ) 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 , {\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 T n = ∑ j = 1 m − 1 j n z j {\displaystyle T_{n}=\sum _{j=1}^{m-1}j^{n}z^{j}} and z = e −k /m . Further manipulation eventually yields
| 1 − z 1 − z + k 2 m 2 z 2 + z ( 1 − z ) 3 + k 3 m 3 z 3 + 4 z 2 + z ( 1 − z ) 4 − k ( k − 2 ) 8 m 4 z 4 + 11 z 3 + 11 z 2 + z ( 1 − z ) 5 | < 110000 m 3 . {\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
1 − 1 e c − 1 = O ( 1 m ) as m → ∞ ; {\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
k m = ln ( 2 ) + a m + b m 2 + O ( 1 m 3 ) as m → ∞ , {\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
1 z = e k / m = 2 + 2 a m + a 2 + 2 b m 2 + O ( 1 m 3 ) as m → ∞ . {\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
k m = ln ( 2 ) ( 1 − 3 2 m − 25 12 − 3 ln ( 2 ) m 2 + O ( 1 m 3 ) ) as m → ∞ . {\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 3 ) must be bounded effectively . To that end, we define the function
F ( x , λ ) = ( 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 λ ( λ − 2 x ) 8 t + 11 t 2 + 11 t 3 + t 4 ( t − 1 ) 5 ) | t = e λ . {\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
| F ( 1 m , k m ) | < 110000 m 3 , {\displaystyle \left\vert F\left({\frac {1}{m}},{\frac {k}{m}}\right)\right\vert <{\frac {110000}{m^{3}}},} (17 )
and we further have
F ( x , ln ( 2 ) ( 1 − 3 2 x − 0.004 x 2 ) ) > − 0.005 15 x 2 − 100 x 3 and F ( x , ln ( 2 ) ( 1 − 3 2 x − 0.004 x 2 ) ) < − 0.00015 x 2 + 100 x 3 {\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
F ( 1 m , ln ( 2 ) ( 1 − 3 2 m − 0.004 m 2 ) ) > − 110000 m 3 for m > 2202 ⋅ 10 4 and F ( 1 m , ln ( 2 ) ( 1 − 3 2 m − 0.004 m 2 ) ) < − 110000 m 3 for m > 0 734 ⋅ 10 6 . {\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 > 109 , we have
ln ( 2 ) ( 1 − 3 2 m − 0.004 m 2 ) < k m < ln ( 2 ) ( 1 − 3 2 m ) , {\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
0 < ln ( 2 ) − 2 k 2 m − 3 < 0.0111 ( 2 m − 3 ) 2 . {\displaystyle 0<\ln(2)-{\frac {2k}{2m-3}}<{\frac {0.0111}{(2m-3)^{2}}}.} Recalling that Moser showed[3] that indeed m > 109 , 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 10109 .
References [ edit ] ^ a b c d e Gallot, Yves; Moree, Pieter; Zudilin, Wadim (2010). "The Erdős–Moser Equation 1k + 2k + ⋯ + (m – 1)k = m k Revisited Using Continued Fractions" (PDF) . Mathematics of Computation . 80 : 1221–1237. arXiv :0907.1356 . doi :10.1090/S0025-5718-2010-02439-1 . S2CID 16305654 . Archived from the original on 2024-05-08. Retrieved 2017-03-20 . ^ a b c Krzysztofek, Bronisław (1966). "O Rówaniu 1n + ... + m n = (m + 1)n ·k " (PDF) . Zeszyty Naukowe Wyżsej Szkoły Pedagogicznej w Katowicach—Sekcja Matematyki (in Polish). 5 : 47–54. Archived from the original (PDF) on 2024-05-13. Retrieved 2024-05-13 . ^ a b c d Moser, Leo (1953). "On the Diophantine Equation 1k + 2k + ... + (m – 1)k = m k ". Scripta Mathematica . 19 : 84–88. ^ Moree, Pieter; te Riele, Herman ; Urbanowicz, Jerzy (1994). "Divisibility Properties of Integers x , k Satisfying 1k + 2k + ⋯ + (x – 1)k = x k " (PDF) . Mathematics of Computation . 63 : 799–815. doi :10.1090/s0025-5718-1994-1257577-1 . Archived from the original on 2024-05-08. Retrieved 2017-03-20 . ^ a b Butske, William; Jaje, Lynda M.; Mayernik, Daniel R. (1999). "The Equation Σp |N 1/p + 1/N = 1 , Pseudoperfect Numbers, and Partially Weighted Graphs" (PDF) . Mathematics of Computation . 69 : 407–420. doi :10.1090/s0025-5718-99-01088-1 . Archived from the original on 2024-05-08. Retrieved 2017-03-20 . ^ Kellner, Bernd Christian (2002). Über irreguläre Paare höherer Ordnungen (PDF) (Thesis) (in German). University of Göttingen . Archived from the original (PDF) on 2024-03-12. Retrieved 2024-03-12 . ^ Moree, Pieter (2013-10-01). "Moser's mathemagical work on the equation 1k + 2k + ⋯ + (m – 1)k = m k " . Rocky Mountain Journal of Mathematics . 43 (5): 1707–1737. arXiv :1011.2940 . doi :10.1216/RMJ-2013-43-5-1707 . ISSN 0035-7596 . Archived from the original on 2024-05-08. Retrieved 2024-05-08 – via Project Euclid .