Русская Википедия:Гипотеза Эрдёша — Штрауса

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

<math>\frac4n = \frac1x + \frac1y + \frac1z</math>.

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

Перебором на компьютере проверено выполнение гипотезы для всех чисел вплоть до <math>n \leqslant 10^{14}</math>[2], но доказательство для всех <math>n</math> остаётся по состоянию Шаблон:На открытой проблемой.

Ограничения

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

<math>\frac45=\frac12+\frac14+\frac1{20}=\frac12+\frac15+\frac1{10}</math>.

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

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

История

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

Жадный алгоритм для египетских дробей, описанный впервые в 1202 году Фибоначчи в его книге абака, находит разложение, в котором каждый последующий член является наибольшей аликвотной дробью, не превосходящей остаток представления (исходную дробь, минус уже вычисленные члены). Для дробей вида 2/n или 3/n жадный алгоритм использует максимум два или три члена соответственно. Можно показать, что число вида 3/n имеет разложение на две дроби в том и только в том случае, когда n имеет множитель, сравнимый с 2 по модулю 3, и требуется три дроби в остальных разложениях[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)[4]. Являясь алгебраическим уравнением с целыми переменными, уравнение служит примером диофантова уравнения. Шаблон:Не переведено 5 для диофантовых уравнений утверждает, что целочисленное решение диофантова уравнения можно получить в виде комбинации целочисленных решений по модулю всех возможных простых чисел. Принцип мало что даёт для гипотезы Эрдёша — Штрауса, поскольку уравнение 4xyz = n(xy + xz + yz) легко разрешимо для любого сравнения по любому простому модулю. Тем не менее, модульная арифметика является важным средством для изучения гипотезы.

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

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

Здесь каждый из трёх знаменателей 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).

Если бы можно было найти решение как выше для другого модуля и тем самым образовать полную покрывающую систему сравнений, задача была бы решена. Однако как показал МорделлШаблон:Sfn, уравнения, обеспечивающие решение для 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 к бесконечности[5].

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

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

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

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

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

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

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

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

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

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

<math>\frac{4}{4k+1} = \frac{1}{k} - \frac{1}{k(4k+1)}</math>

и

<math>\frac{4}{4k-1} = \frac{1}{k} + \frac{1}{k(4k-1)}.</math>

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

<math>\frac{4}{n}=\frac{1}{(n-1)/2}+\frac{1}{(n+1)/2}-\frac{1}{n(n-1)(n+1)/4}.</math>

Обобщения

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

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

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

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Harvnb. Самой ранней публикацией считается Шаблон:Harvnb
  2. ↑ 2,0 2,1 Шаблон:СтатьяШаблон:Недоступная ссылка
  3. ↑ Шаблон:Harvnb
  4. ↑ См., например, Шаблон:Harvnb для простой формулировки в виде диофантовых уравнений при предположениях, какое из чисел x, y или z делится n.
  5. ↑ 5,0 5,1 Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb.
  6. ↑ Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb.
  7. ↑ Шаблон:OEIS
  8. ↑ On the number of solutions to 4/p = 1/n_1 + 1/n_2 + 1/n_3 Шаблон:Wayback, Terence Tao, «What’s new», July 7, 2011.
  9. ↑ Шаблон:Harvnb.
  10. ↑ Шаблон:Harvnb; Шаблон:Harvnb.
  11. ↑ Шаблон:Harvnb.
  12. ↑ Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Гипотеза_Эрдёша_—_Штрауса&oldid=9555270