Гипотеза Эрдёша — Штрауса (Inhkmy[g |j;~og — Omjgrvg)

Гипотеза Эрдёша — Штрауса — теоретико-числовая гипотеза, согласно которой для всех целых чисел $n\geqslant 2$ рациональное число $4/n$ может быть представлено в виде суммы трёх аликвотных дробей (дробей с единицей в числителе), то есть существует три положительных целых числа $x$, $y$ и $z$, таких что:

${\frac {4}{n}}={\frac {1}{x}}+{\frac {1}{y}}+{\frac {1}{z}}$.

Сформулирована в 1948 году Палом Эрдёшом и Эрнстом Штраусом.

Перебором на компьютере проверено выполнение гипотезы для всех чисел вплоть до $n\leqslant 10^{14}$, но доказательство для всех $n$ остаётся по состоянию на 2015 год открытой проблемой.

Ограничения

Целые $x$, $y$ и $z$ не обязательно должны быть различными, но если они различны, то образуют египетскую дробь представления числа $4/n$. Например, для $n=5$ существует два решения:

${\frac {4}{5}}={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{20}}={\frac {1}{2}}+{\frac {1}{5}}+{\frac {1}{10}}$.

Ограничение на положительность чисел $x$, $y$ и $z$ существенно, поскольку, если бы были разрешены отрицательные числа, задача стала бы тривиальной. Также если $n$ является составным $n=pq$, то решение для $4/n$ можно найти немедленно из решений для $4/p$ или $4/q$. По этой причине наименьшее $n$ в контрпримере, если таковой существует, должно быть простым числом и должно быть сравнимо с членом одной из шести бесконечных арифметических прогрессий по модулю 840.

При $n\geqslant 4$ не имеет значения, требуется ли, чтобы все три числа $x$, $y$ и $z$ отличались или нет — если существует решение для каких-либо трёх целых $x$, $y$ и $z$, то существует и решение с различными значениями. Однако для случая $n=2$ существует единственное решение $4/2=1/2+1/2+1/1$ с точностью до перестановки членов суммы.

История

Поиск разложения рациональных чисел в суммы аликвотных дробей восходит к математикам древнего Египта, где египетские дроби использовались для обозначения дробных величин. Египтяне придумали таблицы, такие как таблица 2/n из папируса Ахмеса, содержащая разложения дробей вида 2/n, большинство из которых содержат два или три члена. Египетские дроби, обычно, содержат дополнительное ограничение, что все дроби должны быть различными, но для гипотезы Эрдёша — Штрауса это не имеет значения — если 4/n можно представить в виде не более трёх аликвотных дробей, это число можно также представить в виде суммы не более трёх различных аликвотных дробей.

Жадный алгоритм для египетских дробей, описанный впервые в 1202 году Фибоначчи в его книге абака, находит разложение, в котором каждый последующий член является наибольшей аликвотной дробью, не превосходящей остаток представления (исходную дробь, минус уже вычисленные члены). Для дробей вида 2/n или 3/n жадный алгоритм использует максимум два или три члена соответственно. Можно показать, что число вида 3/n имеет разложение на две дроби в том и только в том случае, когда n имеет множитель, сравнимый с 2 по модулю 3, и требуется три дроби в остальных разложениях.

Таким образом, для числителей 2 и 3 вопрос, сколько потребуется членов в сумме египетской дроби, полностью решён, а дроби вида 4/n являются первым случаем, для которого необходимое число членов суммы остаётся неизвестным. Жадный алгоритм даёт суммы из двух, трёх или четырёх членов, в зависимости от значения n по модулю 4. Если n сравнимо с 1 по модулю 4, жадный алгоритм даёт разложение на четыре дроби. Таким образом, в худшем случае, разложение 4/n должно иметь три или четыре члена. Гипотеза Эрдёша — Штрауса утверждает, что в этом случае, как и для числителя 3, максимальное необходимое число членов разложения равно трём.

Сравнение по модулю

Умножение обеих сторон равенства 4/n = 1/x + 1/y + 1/z на nxyz приводит к равенству 4xyz = n(xy + xz + yz). Являясь алгебраическим уравнением с целыми переменными, уравнение служит примером диофантова уравнения. Принцип Хассе для диофантовых уравнений утверждает, что целочисленное решение диофантова уравнения можно получить в виде комбинации целочисленных решений по модулю всех возможных простых чисел. Принцип мало что даёт для гипотезы Эрдёша — Штрауса, поскольку уравнение 4xyz = n(xy + xz + yz) легко разрешимо для любого сравнения по любому простому модулю. Тем не менее, модульная арифметика является важным средством для изучения гипотезы.

Для значения n, удовлетворяющего некоторым сравнениям, можно найти разложение для 4/n непосредственно из уравнения. Например, при n ≡ 2 (mod 3), 4/n имеет разложение

${\frac {4}{n}}={\frac {1}{n}}+{\frac {1}{(n-2)/3+1}}+{\frac {1}{n((n-2)/3+1)}}.$

Здесь каждый из трёх знаменателей n, (n − 2)/3 + 1 и n((n − 2)/3 + 1) является многочленом от n и каждый будет целым числом при n ≡ 2 (mod 3). Жадный алгоритм для египетских дробей находит решение из трёх или меньше членов, если n не равно 1 или 17 (mod 24), но случай n ≡ 17 (mod 24) покрывается случаем 2 (mod 3), так что единственный случай, для которого оба метода не дают разложения в три и менее членов, это случай n ≡ 1 (mod 24).

Если бы можно было найти решение как выше для другого модуля и тем самым образовать полную покрывающую систему сравнений, задача была бы решена. Однако как показал Морделл, уравнения, обеспечивающие решение для n, сравнимого с r по модулю p, могут существовать только для r, не являющихся квадратичным вычетом по модулю p. Например, 2 не является квадратичным вычетом по модулю 3, так что существование тождества для переменных n, сравнимых с 2 по модулю 3, не противоречит результату Морделла, а вот 1 является квадратичным вычетом по модулю 3, так что не может существовать аналогичного тождества для значений n, которые сравнимы с 1 по модулю 3.

Морделл перечислил тождества, обеспечивающие разложение 4/n на три дроби для случаев n ≡ 2 (mod 3) (как выше), ≡ 3 (mod 4), ≡ 5 (mod 8), ≡ 2 или 3 (mod 5), ≡ 3, 5, или 6 (mod 7). Эти тождества перекрывают все случаи, при которых числа не являются квадратичными вычетами по указанным базисам. Однако для больших базисов известны не все неквадратичные вычеты, которые можно покрыть отношениями этого вида. Из тождеств Морделла можно получить, что существуют решения для всех n, возможно, за исключением 1, 121, 169, 289, 361, или 529 по модулю 840. 1009 — это наименьшее простое число, которое не покрывается системой сравнений. Комбинируя тождества с большими модулями, Уебб (Webb) (и другие) показал, что число дробей со знаменателем в интервале [1,N], которые могли бы служить контрпримером гипотезе, стремится к нулю при стремлении N к бесконечности.

Вопреки результатам Морделла, ограничивающим использование тождеств, есть некоторая надежда на использование модульной арифметики для доказательства гипотезы. Никакое простое число не может быть квадратом, так что по теореме Хассе — Минковского, если p — простое, то существует большее простое q, такое что p не является квадратичным вычетом по модулю q. Один из подходов к доказательству теоремы — найти для каждого простого p большее простое q и сравнение, решающее 4/n задачу для n ≡ p (mod q). Если бы это удалось, было бы доказано, что никакое простое не будет контпримером, а потому гипотеза была бы доказана.

Вычислительная проверка

Различные авторы осуществляли прямой поиск контрпримера. Эти поиски можно сильно ускорить, если рассматривать только простые числа, которые не покрываются известными уравнениями сравнения по модулю. Поиски, совершённые Аланом Светтом (Allan Swett) привели к выводу, что гипотеза верна для всех n вплоть до 10¹⁴.

Число решений

Число различных решений задачи для 4/n, как функции от n, также было найдено компьютерным поиском для малых n и оказалось, что функция растёт несколько нерегулярно. Начиная с n = 3 число различных решений с различными знаменателями равно:

1, 1, 2, 5, 5, 6, 4, 9, 7, 15, 4, 14, 33, 22, 4, 21, 9, ….

Даже для больших n встречаются случаи с относительно небольшим числом решений. Так, для n = 73 существует только семь решений.

Эльсгольц и Тао показали, что среднее число решений задачи разложения 4/n (усреднённое по числу простых чисел вплоть до n) ограничено сверху полилогарифмически от n. Для некоторых других диофантовых задач можно доказать, что решение существует путём нахождения асимптотической нижней границы числа решений, но доказательство такого рода существует, в основном, для задач с полиномиальным ростом числа решений, так что результат Эльсгольца и Тао делают такую возможность маловероятной. Доказательство Эльсгольца и Тао границы числа решений опирается на теорему Бомбьери — Виноградова, теорему Бруна — Тичмарша, и систему модульных равенств, верных при n, сравнимом с −c или −1/c по модулю 4ab, где a и b — два взаимно простых положительных целых числа, а c — любой нечётный множитель a + b. Например, полагая a = b = 1 получим одно из тождеств Морделла, верного при n ≡ 3(mod 4).

Решения в отрицательных числах

Ограничение положительности $x$, $y$ и $z$ является существенным. При допущении отрицательных чисел решение можно получить тривиально посредством следующих двух тождеств:

${\frac {4}{4k+1}}={\frac {1}{k}}-{\frac {1}{k(4k+1)}}$

и

${\frac {4}{4k-1}}={\frac {1}{k}}+{\frac {1}{k(4k-1)}}.$

Для нечётных n существует решение, содержащее три члена, один из которых отрицателен:

${\frac {4}{n}}={\frac {1}{(n-1)/2}}+{\frac {1}{(n+1)/2}}-{\frac {1}{n(n-1)(n+1)/4}}.$

Обобщения

Обобщенная версия гипотезы гласит, что для любого положительного k существует число N такое, что для любых n ≥ N существует решение в целых положительных числах уравнения k/n = 1/x + 1/y + 1/z. Версия этой гипотезы для k = 5 высказана Вацлавом Серпинским, а полная версия гипотезы принадлежит Анджею Шинцелю.

Даже если обобщённая гипотеза неверна для некоторого значения k, число дробей для k/n с n в интервале от 1 до N, не имеющих разложение с тремя членами, должно расти сублинейно как функция от N. В частности, если гипотеза Эрдёша — Штрауса сама по себе (случай k = 4) неверна, то число контрпримеров растёт лишь сублинейно. Даже сильнее, для любого фиксированного k, только сублинейное число значений n требует более чем двух членов в разложении на египетскую дробь. Обобщённая версия гипотезы эквивалентна утверждению, что число неразложимых дробей не просто сублинейно, а ограничено.

Если n нечётно, то по аналогии с задачей разложения на нечётные египетские дроби, можно спросить о решениях k/n = 1/x + 1/y + 1/z, в которых x, y и z являются различными положительными нечётными числами. Известно, что решения в этом случае всегда существуют для k = 3.

Литература

• M. H. Ahmadi, M. N. Bleicher. On the conjectures of Erdős and Straus, and Sierpiński on Egyptian fractions // International Journal of Mathematical and Statistical Sciences. — 1998. — Т. 7, вып. 2. — С. 169—185.
• Leon Bernstein. Zur Lösung der diophantischen Gleichung m/n = 1/x + 1/y + 1/z, insbesondere im Fall m = 4 (Немецкий) // Journal für die Reine und Angewandte Mathematik. — 1962. — Т. 211. — С. 1—10.
• Christian Elsholtz. Sums of k unit fractions // Transactions of the American Mathematical Society. — 2001. — Т. 353, вып. 8. — С. 3209—3227. — doi:10.1090/S0002-9947-01-02782-9.
• Christian Elsholtz, Terence Tao. Counting the number of solutions to the Erdős–Straus equation on unit fractions. — 2011. — arXiv:1107.1010.
• David Eppstein. Ten algorithms for Egyptian fractions // Mathematica in Education and Research. — 1995. — Т. 4, вып. 2. — С. 5—15.
• Paul Erdős. Az 1/x₁ + 1/x₂ + ... + 1/x_n = a/b egyenlet egész számú megoldásairól (On a Diophantine Equation) (венг.) // Mat. Lapok. — 1950. — Т. 1. — С. 192—210.
• Richard K. Guy. Unsolved Problems in Number Theory. — Springer Verlag, 2004. — С. D11. — ISBN 0-387-20860-7.
• Thomas R. Hagedorn. A proof of a conjecture on Egyptian fractions // American Mathematical Monthly. — Mathematical Association of America, 2000. — Т. 107, вып. 1. — С. 62—63. — doi:10.2307/2589381. — .
• Gerd Hofmeister, Peter Stoll. Note on Egyptian fractions // Journal für die Reine und Angewandte Mathematik. — 1985. — Т. 362. — С. 141—145.
• John H. Jaroma. On expanding 4/n into three Egyptian fractions // Crux Mathematicorum. — 2004. — Т. 30, вып. 1. — С. 36—37.
• Ralph W. Jollensten. Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976). — Winnipeg, Man.: Utilitas Math., 1976. — Т. XVII. — С. 351—364. — (Congressus Numerantium).
• Ernest Kiss. Quelques remarques sur une équation diophantienne (Румынский) // Acad. R. P. Romîne Fil. Cluj Stud. Cerc. Mat.. — 1959. — Т. 10. — С. 59—62.
• Ilias Kotsireas. Paul Erdős and his mathematics (Budapest, 1999). — Budapest: János Bolyai Math. Soc, 1999. — С. 140—144.
• De Lang Li. Equation 4/n = 1/x + 1/y + 1/z // Journal of Number Theory. — 1981. — Т. 13, вып. 4. — С. 485—494. — doi:10.1016/0022-314X(81)90039-1.
• Louis Mordell. Diophantine Equations. — Academic Press, 1967. — С. 287—290.
• Richard Obláth. Sur l'équation diophantienne 4/n = 1/x₁ + 1/x₂ + 1/x₃ (Французский) // Mathesis. — 1950. — Т. 59. — С. 308—316.
• Luigi Antonio Rosati. Sull'equazione diofantea 4/n = 1/x₁ + 1/x₂ + 1/x₃ (Итальянский) // Boll. Un. Mat. Ital. (3). — 1954. — Т. 9. — С. 59—63.
• J. W. Sander. On 4/n = 1/x + 1/y + 1/z and Iwaniec' half-dimensional sieve // Journal of Number Theory. — 1994. — Т. 46, вып. 2. — С. 123—136. — doi:10.1006/jnth.1994.1008.
• Andrzej Schinzel. Sur quelques propriétés des nombres 3/n et 4/n, où n est un nombre impair (Французский) // Mathesis. — 1956. — Т. 65. — С. 219—222.
• Wacław Sierpiński. Sur les décompositions de nombres rationnels en fractions primaires (Французский) // Mathesis. — 1956. — Т. 65. — С. 16—32.
• D. Suryanarayana, N. Venkateswara Rao. On a paper of André Schinzel // J. Indian Math. Soc. (N.S.). — 1965. — Т. 29. — С. 165—167.
• D. G. Terzi. On a conjecture by Erdős-Straus // Nordisk Tidskr. Informationsbehandling (BIT). — 1971. — Т. 11, вып. 2. — С. 212—216. — doi:10.1007/BF01934370.
• R. C. Vaughan. On a problem of Erdős, Straus and Schinzel // Mathematika. — 1970. — Т. 17, вып. 02. — С. 193—198. — doi:10.1112/S0025579300002886.
• William A. Webb. On 4/n = 1/x + 1/y + 1/z // Proceedings of the American Mathematical Society. — American Mathematical Society, 1970. — Т. 25, вып. 3. — С. 578—584. — doi:10.2307/2036647. — .
• Koichi Yamamoto. On the Diophantine equation 4/n = 1/x + 1/y + 1/z // Memoirs of the Faculty of Science. Kyushu University. Series A. Mathematics. — 1965. — Т. 19. — С. 37—47. — doi:10.2206/kyushumfs.19.37.
• Xun Qian Yang. A note on 4/n = 1/x + 1/y + 1/z // Proceedings of the American Mathematical Society. — 1982. — Т. 85, вып. 4. — С. 496—498. — doi:10.2307/2044050. — .

Ссылки

• Weisstein, Eric W. Erdos-Straus Conjecture (англ.) на сайте Wolfram MathWorld.
• Counting the number of solutions to the Erdös-Straus equation on unit fractions Архивная копия от 31 октября 2014 на Wayback Machine, Terence Tao, July 31, 2011.