Уравнение Эрдеша–Мозера

Нерешенная задача по математике :

Имеет ли уравнение Эрдёша–Мозера решения, отличные от

11 +2 1 =3 1

(еще нерешенные проблемы по математике)

В теории чисел уравнение Эрдёша –Мозера имеет вид

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

где $m$ и $k$ ограничены положительными целыми числами — то есть, оно рассматривается как диофантово уравнение . Единственное известное решение — $11 + 2 1 = 3 1$ , и Пол Эрдёш предположил, что других решений не существует. Любые другие решения должны иметь $m > 10 109$ . ^[1]

При сравнении научных работ по этому уравнению следует проявлять определенную осторожность, поскольку в некоторых статьях ^[2] оно представлено в виде $1 k + 2 k + \dots + m k = (m + 1) k$ .

В этой статье $p$ относится исключительно к простым числам .

Ограничения на решения

В 1953 году Лео Мозер доказал, что в любых дальнейших решениях ^[3]

$k$ четное,
$p | (m - 1)$ подразумевает $(p - 1) | k$ ,
$p | (m + 1)$ подразумевает $(p - 1) | k$ ,
$p | (2 m + 1)$ подразумевает $(p - 1) | k$ ,
$m - 1$ — бесквадратный ,
$m + 1$ либо бесквадратное число, либо 4 раза нечетное бесквадратное число,
$2 м - 1$ — бесквадратный,
$2 m + 1$ — бесквадратный,
$\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{(если }}m+1{\text{ четно)}},$
$\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}},$ и
$м > 10 106$ .

В 1966 году было дополнительно показано, что ^[2]

$6 \leq k + 2 < m < 3 (k + 1) / 2$ , и
$m - 1$ не может быть простым числом.

В 1994 году было показано, что ^[4]

$lcm(1,2,\dots,200)$ делит $k$ ,
$m \equiv 3 (mod 2$ $ord$ $2$ $($ $k$ $)$ $+ 3$ $)$ , где $ord 2 (n)$ — это 2-адическая оценка n; эквивалентно, $ord$ $2$ $($ $m$ $- 3) = ord$ $2$ $($ $k$ $) + 3$ ,
для любого нечетного простого числа $p,$ делящего $m$ , имеем $k ≢ 0, 2 (mod p - 1)$ ,
любой простой множитель числа $m$ должен быть неправильным и > 10000.

В 1999 году метод Мозера был усовершенствован, чтобы показать, что $m > 1,485 \times 10 9 321 155$ . ^[5]

В 2002 году было показано ^[6]^{: §4} , что $k$ должно быть кратно $23 \cdot 3# \cdot 5# \cdot 7# \cdot 19# \cdot 1000#$ , где символ $#$ указывает на ипримориал ; то есть $n #$ является произведением всех простых чисел $\leq n$ . Это число превышает $5,7462 \times 10 427$ .

В 2009 году было показано, что $2 k / (2 m - 3)$ должно быть сходящимся числом $ln(2)$ ; авторы этой статьи называют это «одним из очень немногих случаев, когда крупномасштабное вычисление числовой константы имеет применение», и тогда было определено, что $m > 2,7139 \times 10 1 667 658 416$ . ^[1]

В 2010 году было показано, что ^[7]

$m \equiv 3 (mod 8)$ и $m \equiv \pm1 (mod 3)$ , и
$(m 2 - 1) (4 m 2 - 1) / 12$ имеет не менее 4 990 906 простых множителей, ни один из которых не повторяется.

Число 4 990 906 возникает из-за того, что $∑4990905 н =1 .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠1/п н⁠ < ⁠19/6⁠ < ∑4990906 н =1 ⁠1/п н⁠ ,$ где $p n —$ $n$ -е^{простое} число.

Метод Мозера

Сначала пусть $p$ будет простым множителем $m - 1.$ Лео Мозер показал ^[3] , что это означает, что $p - 1$ делит $k$ и что

что при умножении на $p$ дает

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

Это, в свою очередь, подразумевает, что $m - 1$ должно быть бесквадратным . Кроме того, поскольку нетривиальные решения имеют $m - 1 > 2$ и поскольку все бесквадратные числа в этом диапазоне должны иметь по крайней мере один нечетный простой множитель, предположение о том, что $p - 1$ делит $k,$ подразумевает, что $k$ должно быть четным.

Одно сравнение вида ( 1 ) существует для каждого простого множителя $p$ числа $m - 1.$ Перемножение их всех вместе дает

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

Расширение выхода продукции

1+\sum _{p|(m-1)}{\frac {m-1}{p}}+({\text{члены более высокого порядка}})\equiv 0{\pmod {m-1}},

где члены более высокого порядка являются произведениями нескольких множителей вида $(m - 1) / p$ , с различными значениями $p$ в каждом множителе. Все эти члены делятся на $m - 1$ , поэтому они все выпадают из сравнения, что дает

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

Разделив модуль, получаем

Аналогичные рассуждения приводят к сравнениям

Сравнения ( 2 ), ( 3 ), ( 4 ) и ( 5 ) весьма ограничительны; например, единственными значениями $m < 1000$ , которые удовлетворяют ( 2 ), являются 3, 7 и 43, а они исключаются согласно ( 4 ).

Теперь разделимся на два случая: либо $m + 1$ четное, либо m + 1 нечетное.

В случае, когда $m + 1$ четно, сложение левых частей сравнений ( 2 ), ( 3 ), ( 4 ) и ( 5 ) должно дать целое число, и это целое число должно быть не меньше 4. Более того, алгоритм Евклида показывает, что никакое простое число $p > 3$ не может делить более одного из чисел в наборе ${m - 1, m + 1, 2 m - 1, 2 m + 1}$ , и что 2 и 3 могут делить не более двух из этих чисел. Полагая $M = (m - 1) (m + 1) (2 m - 1) (2 m + 1)$ , мы тогда имеем

$Поскольку нетривиальных решений с m < 1000$ не существует , часть левой части уравнения ( 6 ) вне сигмы не может превышать $0,006$ ; следовательно, имеем

\sum _{p|M}{\frac {1}{p}}>3,16.

Следовательно, если , то . В оригинальной статье Мозера ^[3] границы функции подсчета простых чисел используются для наблюдения того, что $\sum _{p\leq x}{\frac {1}{p}}<3.16$ $M>\prod _{p\leq x}p$

\sum _{p\leq 10^{7}}{\frac {1}{p}}<3,16.

Следовательно, $M$ должно превышать произведение первых 10 000 000 простых чисел. Это, в свою очередь, означает, что $m > 10 106$ в этом случае.

В случае, если $m + 1$ нечетно, мы не можем использовать ( 3 ), поэтому вместо ( 6 ) получаем

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

где $N = (m - 1) (2 m - 1) (2 m + 1)$ . На первый взгляд это кажется более слабым условием, чем ( 6 ), но поскольку $m + 1$ нечетно, простое число 2 не может появиться на большей стороне этого неравенства, и это оказывается более сильным ограничением на $m,$ чем другой случай.

Поэтому любые нетривиальные решения имеют $m > 10 106$ .

В 1999 году этот метод был усовершенствован с помощью компьютеров, которые заменили оценки подсчета простых чисел точными вычислениями; это дало оценку $m > 1,485 \times 10 9 321 155$ . ^[5]^{: Теория 2}

Ограничение соотношениям / ( к + 1)

Пусть $S k (m) = 1 k + 2 k + \dots + (m - 1) k$ . Тогда уравнение Эрдёша–Мозера принимает вид $S k (m) = m k$ .

Метод 1: Интегральные сравнения

Сравнивая сумму $S k (m)$ с определенными интегралами функции $x k$ , можно получить оценки $1 < m / (k + 1) < 3$ . ^[1]^{: §1¶2}

Сумма $S k (m) = 1 k + 2 k + \dots + (m - 1) k$ является верхней суммой Римана, соответствующей интегралу , в котором интервал был разделен на целые значения $x$ , поэтому мы имеем ${\textstyle \int _{0}^{m-1}x^{k}\,\mathrm {d} x}$

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

По предположению, $S k (m) = m k$ , поэтому

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

что приводит к

Аналогично, $S k (m)$ — нижняя сумма Римана, соответствующая интегралу , в котором интервал был разделен на целые значения $x$ , поэтому мы имеем ${\textstyle \int _{1}^{m}x^{k}\,\mathrm {d} x}$

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

По предположению, $S k (m) = m k$ , поэтому

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

и так

Применяем это к ( 7 ) получаем

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

$Расчет показывает, что нетривиальных решений при m \leq 10$ не существует , поэтому имеем

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

Объединяя это с ( 8 ), получаем $1 < m / (k + 1) < 3$ , как и требовалось.

Метод 2: Алгебраические преобразования

Верхнюю границу $m / (k + 1) < 3$ можно уменьшить до $m / (k + 1) < 3/2$ с помощью алгебраического метода: ^[2]^{: Лемат 4}

Пусть $r$ — положительное целое число. Тогда биномиальная теорема дает

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

Суммирование по $ℓ$ дает

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

Переиндексация слева и перестановка справа дает

\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)

Принимая $r = k,$ получаем

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

По предположению, $S k = m k$ , поэтому

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

Поскольку RHS положительный, мы должны иметь

Возвращаясь к ( 9 ) и принимая $r = k - 1,$ получаем

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).

Подставляя это в ( 10 ), чтобы исключить $m k$ , получаем

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

Переиндексация суммы справа с заменой $i = s + 1$ дает

\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)

Мы уже знаем из ( 11 ), что $k + 1 < m$ . Это оставляет открытой возможность, что $m = k + 2$ ; однако, подстановка этого в ( 12 ) дает

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),

что невозможно для $k > 1$ , так как сумма содержит только положительные члены. Поэтому любые нетривиальные решения должны иметь $m \neq k + 2$ ; объединение этого с ( 11 ) дает

k+2<m.

Поэтому мы видим, что левая часть ( 12 ) положительна, поэтому

Поскольку $k > 1$ , последовательность убывает. Это и ( 13 ) вместе подразумевают, что ее первый член (член с $s$ $= 1$ ) должен быть положительным: если бы это было не так, то каждый член в сумме был бы неположительным, и, следовательно, таковой была бы и сама сумма. Таким образом, $\left\{(k+1)/(s+1)-m+(k+1)\right\}_{s=1}^{\infty }$

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

что дает

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

и поэтому

{\frac {m}{k+1}}<{\frac {3}{2}},

по желанию.

Непрерывные дроби

Любые потенциальные решения уравнения должны возникать из непрерывной дроби натурального логарифма числа 2 : в частности, $2 k / (2 m - 3)$ должно быть подходящей дробью этого числа. ^[1]

Разлагая ряд Тейлора функции $(1 - y) k e ky$ относительно $y = 0$ , находим

(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.

Более подробный анализ заостряет это внимание

для $k > 8$ и $0 < y < 1$ .

Уравнение Эрдеша–Мозера эквивалентно

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

Применяя ( 14 ) к каждому члену этой суммы, получаем

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

где и $z$ $=$ $e$ $-$ $k$ $/$ $m$ . Дальнейшие манипуляции в конечном итоге дают $T_{n}=\sum _{j=1}^{m-1}j^{n}z^{j}$

Мы уже знаем, что $k / m$ ограничено при $m \to \infty$ ; делая анзац $k / m = c + O (1/ m)$ , и, следовательно, $z = e - c + O (1/ m)$ , и подставляя его в ( 15 ), получаем

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

следовательно $c = ln(2)$ . Следовательно, мы имеем

и так

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

Подстановка этих формул в ( 15 ) дает $a = -3 ln(2) / 2$ и $b = (3 ln(2) - 25/12) ln(2)$ . Подстановка их в ( 16 ) дает

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

Член $O (1/ m 3)$ должен быть ограничен эффективно . Для этого определим функцию

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

Тогда неравенство ( 15 ) принимает вид

и у нас есть еще

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

для $x \leq 0,01$ . Поэтому

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

Сравнение их с ( 17 ) показывает, что для $m > 10 9$ мы имеем

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

и поэтому

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

Вспоминая, что Мозер показал ^[3] , что действительно $m > 10 9$ , а затем, используя теорему Лежандра о непрерывных дробях , наконец, доказывает, что $2 k / (2 m - 3)$ должно быть сходящимся к $ln(2)$ . Используя этот результат, 31 миллиард десятичных цифр $ln(2)$ можно использовать для исключения любых нетривиальных решений ниже $10109$ . ^[1]

Смотрите также

Ссылки

^ abcde Галло, Ив; Мори, Питер; Зудилин, Вадим (2010). «Уравнение Эрдёша–Мозера 1k + 2k + ⋯ + (m – 1)k = mk, пересмотренное с использованием непрерывных дробей» (PDF) . Математика вычислений . 80 : 1221–1237. arXiv : 0907.1356 . doi : 10.1090/S0025-5718-2010-02439-1 . S2CID 16305654. Архивировано из оригинала 2024-05-08 . Получено 2017-03-20 .
^ abc Кшиштофек, Бронислав (1966). «O Rówaniu 1n + ... + mn = (m + 1)n·k» (PDF) . Zeszyty Naukowe Wyżsey Szkoły Pedagogicznej w Katowicach – Sekcja Matematyki (на польском языке). 5 : 47–54. Архивировано из оригинала (PDF) 13 мая 2024 г. Проверено 13 мая 2024 г.
^ abcd Мозер, Лео (1953). «О диофантовом уравнении $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 1k + 2k + ⋯ + (x – 1)k = xk» (PDF) . Mathematics of Computation . 63 : 799–815. doi : 10.1090/s0025-5718-1994-1257577-1 . Архивировано из оригинала 2024-05-08 . Получено 2017-03-20 .
^ ab Батске, Уильям; Джадже, Линда М.; Майерник, Дэниел Р. (1999). "Уравнение Σp|N 1/p + 1/N = 1, псевдосовершенные числа и частично взвешенные графы" (PDF) . Математика вычислений . 69 : 407–420. doi : 10.1090/s0025-5718-99-01088-1 . Архивировано из оригинала 2024-05-08 . Получено 2017-03-20 .
^ Келлнер, Бернд Кристиан (2002). Über нерегулярный Paare höherer Ordnungen (PDF) (Диссертация) (на немецком языке). Геттингенский университет . Архивировано из оригинала (PDF) 12 марта 2024 г. Проверено 12 марта 2024 г.
^ Moree, Pieter (2013-10-01). «Математическая работа Мозера по уравнению 1k + 2k + ⋯ + (m – 1)k = mk». Rocky Mountain Journal of Mathematics . 43 (5): 1707–1737. arXiv : 1011.2940 . doi : 10.1216/RMJ-2013-43-5-1707 . ISSN 0035-7596.