User:LucasBrown/EMEq

This is a development page for Erdős–Moser equation.

Unsolved problem in mathematics:

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

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 $11 + 2 1 = 3 1$ , 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 109$ .^[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 + \dots + m k = (m + 1) k$ instead.

Constraints on solutions edit

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

$p | (m - 1)$ implies $(p - 1) | k$ ,
$m - 1$ is squarefree,
$k$ is even,
$\sum _{p|(m-1)}{\frac {m-1}{p}}\equiv -1{\pmod {m-1}},$
$p | (m + 1)$ implies $(p - 1) | k$ ,
$m + 1$ is either squarefree or 4 times an odd squarefree number,
$\sum _{p|(m+1)}{\frac {m+1}{p}}\equiv -2{\pmod {m+1}},$
$2 m - 1$ is squarefree,
$\sum _{p|(2m-1)}{\frac {2m-1}{p}}\equiv -2{\pmod {2m-1}},$
$p | (2 m + 1)$ implies $(p - 1) | k$ ,
$2 m + 1$ is squarefree,
$\sum _{p|(2m+1)}{\frac {2m+1}{p}}\equiv -4{\pmod {2m-1}},$ and
$m > 10 106$ .

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

$6 \leq k + 2 < m < 3 (k + 1) / 2$ , and
$m - 1$ cannot be prime.

In 1994, it was shown that^[4]

$lcm(1,2,\dots,200)$ divides $k$ ,
$ord 2 (m - 3) = ord 2 (k) + 3$ , where $ord 2 (n)$ is the 2-adic valuation of $n$ ,
for any prime $p$ divding $m$ , we have $k ≢ 0, 2 (mod p - 1)$ ,
$m \equiv 3 (mod 8)$ , and
any prime factor of $m$ must be irregular and > 10000.

In 1999, Moser's method was refined to show that $m > 1.485 \times 10 9,321,155$ .^[5]

In 2002, it was shown^[6] that $k$ must be a multiple of $23 \cdot 3# \cdot 5# \cdot 7# \cdot 19# \cdot 1000#$ , where the symbol $#$ indicates the primorial; that is, $n #$ is the product of all prime numbers $\leq n$ . This number exceeds $5.7462 \times 10 427$ .

In 2009, it was shown that $2 k / (2 m - 3)$ must be a convergent of $ln(2)$ ; in what the authors of that paper call “one of the very few instances where a large scale computation of a numerical constant has an application”, it was then determined that $m > 2.7139 \times 10 1,667,658,416$ .^[1]

In 2010, it was shown that^[7]

$k$ is even,
$m \equiv 3 (mod 8)$ and $m \equiv \pm1 (mod 3)$ ,
$m - 1$ , $(m + 1) / 2$ , $2 m - 1$ , and $2 m + 1$ are all squarefree,
if the prime number $p$ divides at least one of the numbers from the previous line, then $p - 1$ divides $k$ , and
$(m 2 - 1) (4 m 2 - 1) / 12$ has at least 4,990,906 prime factors, none of which are repeated.

This number 4,990,906 arises from the fact that $\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 edit

TODO

Bounding the ratio $m / (k + 1)$ edit

Let $S k (m) = 1 k + 2 k + \dots + (m - 1) k$ . Then the Erdős–Moser equation becomes $S k (m) = m k$ .

The sum $S k (m) = 1 k + 2 k + \dots + (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

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

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

(1)

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

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

k+1<m.

(2)

Applying this to (1) 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 \leq 10$ , so we have

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

Combining this with (2) yields $1 < m / (k + 1) < 3$ . A more elaborate analysis along these lines brings the upper bound down to $3/2$ .^[2]

Continued fractions edit

This section follows the exposition in ^[1].

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

{\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}}

(3)

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 (3) 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

\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}}}.

(4)

We already know that $k / m$ is bounded as $m \to \infty$ ; making the ansatz $k / m = c + O (1/ m)$ , and therefore $z = e - c + O (1/ m)$ , and substituting it into (4) 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

{\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 ,

(5)

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 (4) yields $a = -3 ln(2) / 2$ and $b = (3 ln(2) - 25/12) ln(2)$ . Putting these into (5) 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 (4) then takes the form

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

(6)

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 \leq 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 (6) 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^[3] that indeed $m > 10 9$ , and then invoking Legendre's theorem on continued fractions, finally proves that $2 k / (2 m - 3)$ must be a convergent to $ln(2)$ .

General TODOs edit

TODO: Find links for ^[3].

TODO: What level of thesis is ^[6] for?

TODO: Find a way to cite ^[8].

Carlitz's article on Staudt-Clausen: ^[9]

References edit

^ ^a ^b ^c Gallot, Yves; Moree, Pieter; Zudilin, Wadim (2010). "The Erdős–Moser Equation $1 k + 2 k + \dots + (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 $1 n + ... + m n = (m + 1) n \cdot 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 Moser, Leo (1953). "On the Diophantine Equation $1 k + 2 k + ... + (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 $1 k + 2 k + \dots + (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.
^ 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.
^ ^a ^b 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 $1 k + 2 k + \dots + (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.
^ Moree, Pieter (2011-04-01). "A Top Hat for Moser's Four Mathemagical Rabbits". American Mathematical Monthly. 118 (4): 364–370. arXiv:1011.2956. doi:10.4169/amer.math.monthly.118.04.364. ISSN 0002-9890 – via JSTOR.
^ Carlitz, Leonard (1961-01-01). "The Staudt-Clausen Theorem". Mathematics Magazine. 34 (3): 131–146. doi:10.2307/2688488. eISSN 1930-0980. ISSN 0025-570X. JSTOR 2688488 – via JSTOR.

Cite error: A list-defined reference named "urbanowicz1988" is not used in the content (see the help page).

[gallot2010-1] Gallot, Yves; Moree, Pieter; Zudilin, Wadim (2010). "The Erdős–Moser Equation $1 k + 2 k + \dots + (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.

[krzysztofek1966-2] Krzysztofek, Bronisław (1966). "O Rówaniu $1 n + ... + m n = (m + 1) n \cdot 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.

[moser1953-3] Moser, Leo (1953). "On the Diophantine Equation $1 k + 2 k + ... + (m - 1) k = m k$ ". Scripta Mathematica. 19: 84–88.

[moree1994-4] Moree, Pieter; te Riele, Herman; Urbanowicz, Jerzy (1994). "Divisibility Properties of Integers $x$ , $k$ Satisfying $1 k + 2 k + \dots + (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.

[butske1999-5] 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.

[kellner2002-6] 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.

[moree2013-7] Moree, Pieter (2013-10-01). "Moser's mathemagical work on the equation $1 k + 2 k + \dots + (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.

[moree2011-8] Moree, Pieter (2011-04-01). "A Top Hat for Moser's Four Mathemagical Rabbits". American Mathematical Monthly. 118 (4): 364–370. arXiv:1011.2956. doi:10.4169/amer.math.monthly.118.04.364. ISSN 0002-9890 – via JSTOR.

[carlitz1961-9] Carlitz, Leonard (1961-01-01). "The Staudt-Clausen Theorem". Mathematics Magazine. 34 (3): 131–146. doi:10.2307/2688488. eISSN 1930-0980. ISSN 0025-570X. JSTOR 2688488 – via JSTOR.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]