Гипотеза Эрдеша – Штрауса
Гипотеза Эрдеша -Штрауса является недоказанным утверждением в теории чисел . Гипотеза состоит в том, что для любого целого числа то есть 2 или более, существуют целые положительные числа , , и для чего Другими словами, число можно записать как сумму трех положительных единичных дробей .
Гипотеза названа в честь Пауля Эрдеша и Эрнста Г. Штрауса , которые сформулировали ее в 1948 году, но она связана с гораздо более древней математикой; суммы единичных дробей, подобные той, что в этой задаче, известны как египетские дроби из-за их использования в древнеегипетской математике . Гипотеза Эрдеша-Штрауса — одна из многих гипотез Эрдеша и одна из многих нерешённых проблем математики, касающихся диофантовых уравнений .
решение неизвестно Хотя для всех значений n , бесконечно многие значения в определенных бесконечных арифметических прогрессиях имеют простые формулы для своего решения, и пропуск этих известных значений может ускорить поиск контрпримеров . Кроме того, при таком поиске необходимо учитывать только значения это простые числа , потому что любой составной контрпример будет иметь меньший контрпример среди своих простых множителей . Компьютерные поиски подтвердили истинность гипотезы до .
Если гипотезу переформулировать, чтобы допустить отрицательные доли единицы, то известно, что она верна. Также изучались обобщения гипотезы на дроби с числителем 5 и больше.
Предыстория и история
[ редактировать ]Когда рациональное число разлагается в сумму единичных дробей, это разложение называется египетской дробью . Этот способ записи дробей восходит к математике Древнего Египта , в которой дроби записывались таким образом, а не в более современной вульгарной форме дробей. с числителем и знаменатель . Египтяне составили таблицы египетских дробей для единичных дробей, умноженных на два, - чисел, которые в современных обозначениях будут записываться , такие как таблица Математического Папируса Ринда ; в этих таблицах в большинстве расширений используются два или три термина. [ 1 ] Эти таблицы были необходимы, поскольку очевидное расширение было запрещено: египтяне требовали, чтобы все дроби в египетской дроби отличались друг от друга. То же самое требование, чтобы все дроби были разными, иногда налагается в гипотезе Эрдеша – Штрауса, но это не имеет существенного значения для проблемы, поскольку для любое решение где доли единицы не различны, можно преобразовать в решение, в котором все они различны; см. ниже . [ 2 ]
Хотя египтяне не всегда находили разложения, в которых использовалось как можно меньше терминов, более поздние математики заинтересовались вопросом о том, как мало терминов необходимо. Каждая фракция имеет расширение не более термины, поэтому, в частности требуется не более двух терминов, требуется не более трех терминов, и требуется не более четырех терминов. Для , всегда необходимы два члена, и для , иногда требуются три члена, поэтому для обоих этих числителей известно максимальное количество членов, которые могут потребоваться. Однако для , неизвестно, нужны ли иногда четыре члена или можно ли выразить все дроби вида использование только трех долей единицы; это гипотеза Эрдеша – Штрауса. Таким образом, гипотеза охватывает первый неизвестный случай более общего вопроса — проблемы нахождения для всех максимальное количество членов, необходимых в разложении дробей . [ 1 ]
Один из способов найти короткие (но не всегда кратчайшие) разложения использует жадный алгоритм египетских дробей , впервые описанный в 1202 году Фибоначчи в его книге Liber Abaci . Этот метод выбирает одну долю единицы за раз, на каждом этапе выбирая максимально возможную долю единицы, которая не приведет к тому, что расширенная сумма превысит целевое число. После каждого шага числитель дроби, которую еще предстоит разложить, уменьшается, поэтому общее количество шагов никогда не может превышать начальный числитель. [ 1 ] но иногда он меньше. Например, когда оно применяется к , жадный алгоритм будет использовать два термина всякий раз, когда равно 2 по модулю 3, но существует двучленное разложение всякий раз, когда имеет коэффициент 2 по модулю 3, более слабое условие. Для чисел вида , жадный алгоритм будет производить разложение на четыре члена всякий раз, когда равно 1 по модулю 4, а в противном случае — разложение с меньшим количеством членов. [ 3 ] Таким образом, другой способ перефразировать гипотезу Эрдеша – Штрауса спрашивает, существует ли другой метод получения египетских дробей, использующий меньшее максимальное количество членов для чисел. . [ 1 ]
Гипотеза Эрдеша-Штрауса была сформулирована в 1948 году Полом Эрдешем и Эрнстом Г. Штраусом и опубликована Эрдешем (1950) . Ричард Облат также опубликовал раннюю работу по этой гипотезе, статью, написанную в 1948 году и опубликованную в 1950 году, в которой он расширил более ранние расчеты Штрауса и Гарольда Н. Шапиро, чтобы проверить гипотезу для всех . [ 4 ]
Формулировка
[ редактировать ]Гипотеза утверждает, что для любого целого числа , существуют целые положительные числа , , и такой, что Например, для , есть два решения:
Умножение обеих частей уравнения к приводит к эквивалентной полиномиальной форме для проблемы. [ 5 ]
Различные единицы измерения
[ редактировать ]Некоторые исследователи дополнительно требуют, чтобы целые числа , , и отличаться друг от друга, как это сделали бы египтяне, в то время как другие допускают их равенство. [ 1 ] Для , не имеет значения, должны ли они быть различными: если существует решение с любыми тремя целыми числами, то существует решение с различными целыми числами. [ 2 ] Это связано с тем, что две идентичные дробные единицы можно заменить с помощью одного из следующих двух расширений: (в зависимости от того, имеет ли повторяющаяся дробь четный или нечетный знаменатель), и эту замену можно повторять до тех пор, пока не останется повторяющихся дробей. [ 6 ] Для , однако единственными решениями являются перестановки . [ 1 ]
Решения для отрицательных чисел
[ редактировать ]Гипотеза Эрдеша-Штрауса требует, чтобы все три , , и быть позитивным. Это требование существенно для сложности задачи. Даже без этого расслабления гипотеза Эрдеша – Штрауса сложна только для нечетных значений , и если бы были разрешены отрицательные значения, то проблема могла бы быть решена для каждого нечетного по следующей формуле: [ 7 ]
Результаты вычислений
[ редактировать ]Если гипотеза ложна, ее можно доказать, просто найдя число который не имеет трехчленного представления. Чтобы проверить это, различные авторы провели грубый поиск контрпримеров к этой гипотезе. [ 8 ] Поиски такого типа подтвердили, что гипотеза верна для всех до . [ 9 ]
В таких поисках необходимо искать только расширения цифр. где является простым числом . Это потому, что всякий раз, когда имеет трехчленное разложение, так же как и для всех положительных целых чисел . Чтобы найти решение для , просто разделите все доли единицы раствора на к : Если были контрпримером к гипотезе, для составного числа , каждый простой фактор из также привел бы контрпример это было бы найдено раньше при грубом поиске. Поэтому проверка существования решения для составных чисел избыточна и может быть пропущена при поиске. Кроме того, известные модульные тождества для гипотезы (см. ниже ) могут ускорить этот поиск, пропуская другие значения, которые, как известно, имеют решение. Например, жадный алгоритм находит расширение с тремя или меньшим количеством членов для каждого числа. где не является 1 по модулю 4, поэтому при поиске необходимо проверять только значения, равные 1 по модулю 4. Один из способов добиться прогресса в этой проблеме — собрать больше модульных идентификаторов, что позволит компьютерному поиску достичь более высоких пределов с меньшим количеством тестов. [ 9 ]
Количество различных решений задачи проблема, как функция , также был найден при компьютерном поиске небольших и, кажется, растет несколько нерегулярно с . Начиная с , количество различных решений с разными знаменателями равно
Даже для большего иногда решений может быть относительно мало; например, существует только семь различных решений для .
Теоретические результаты
[ редактировать ]В форме , полиномиальное уравнение с целыми переменными, гипотеза Эрдеша – Штрауса является примером диофантового уравнения . Принцип Хассе для диофантовых уравнений предполагает, что эти уравнения следует изучать с помощью модульной арифметики . Если полиномиальное уравнение имеет решение в целых числах, то, взяв это решение по модулю , для любого целого числа , дает решение по модулю- арифметика. В обратном направлении, если уравнение имеет решение по модулю для каждой первичной силы , то в некоторых случаях можно соединить эти модульные решения, используя методы, связанные с китайской теоремой об остатках , и получить решение в целых числах. Способность принципа Хассе решать некоторые проблемы ограничена препятствием Манина , но для гипотезы Эрдеша-Штрауса этого препятствия не существует. [ 10 ]
На первый взгляд этот принцип не имеет большого смысла для гипотезы Эрдеша-Штрауса. Для каждого , уравнение легко разрешимо по модулю любого простого числа или простой степени, но, похоже, нет способа соединить эти решения вместе, чтобы получить положительное целое решение уравнения. Тем не менее, модульная арифметика и тождества, основанные на модульной арифметике, оказались очень важным инструментом в изучении гипотезы. [ 11 ]
Модульная идентичность
[ редактировать ]Для значений удовлетворяя определенным отношениям конгруэнтности , можно найти расширение для автоматически как экземпляр полиномиального тождества. Например, всякий раз, когда равно 2 по модулю 3, имеет расширение Здесь каждый из трех знаменателей , , и представляет собой полином от , и каждый является целым числом всякий раз, когда равно 2 по модулю 3. Жадный алгоритм для египетских дробей находит решение в трех или меньшем количестве членов всякий раз, когда не является 1 или 17 по модулю 24, а случай 17 по модулю 24 покрывается соотношением 2 по модулю 3, поэтому единственные значения для которых эти два метода не находят разложения в три или меньше членов, являются теми, которые соответствуют 1 по модулю 24. [ 12 ]
Полиномиальные тождества, перечисленные Морделлом (1967), дают трехчленные египетские дроби для в любое время является одним из:
- 2 мод 3 (вверху),
- 3 против 4,
- 2 или 3 мод 5,
- 3, 5 или 6 по модулю 7 или
- 5 против 8.
Комбинации личностей Морделла могут быть использованы для расширения для всех за исключением, возможно, тех, которые равны 1, 121, 169, 289, 361 или 529 по модулю 840. Наименьшее простое число, которое не покрывают эти тождества, - 1009. Комбинируя более крупные классы модульных тождеств, Уэбб и другие показали, что естественная плотность потенциала контрпримеров к гипотезе равно нулю: в качестве параметра стремится к бесконечности, доля значений в интервале . которые могут быть контрпримерами, в пределе стремятся к нулю. [ 13 ]
Отсутствие личностей
[ редактировать ]Если бы можно было найти решения, подобные приведенным выше, для достаточного количества различных модулей, образующих полную покрывающую систему сравнений, проблема была бы решена. Однако, как показал Морделл (1967) , полиномиальное тождество, обеспечивающее решение для значений соответствующий против может существовать только тогда, когда не соответствует квадрату по модулю . (Более формально, такая идентичность может существовать только тогда, когда не является квадратичным вычетом по модулю .) Например, 2 не является квадратным по модулю 3, поэтому результат Морделла допускает существование тождества для конгруэнтно 2 по модулю 3. Однако 1 является квадратом по модулю 3 (равным квадрату как 1, так и 2 по модулю 3), поэтому не может быть одинакового тождества для всех значений которые соответствуют 1 модулю 3. В более общем смысле, поскольку 1 является квадратным модификатором для всех , не может быть полной покрывающей системы модульных тождеств для всех , потому что 1 всегда будет открыта. [ 14 ]
Несмотря на результат Морделла, ограничивающий форму модульных тождеств для этой задачи, все еще есть некоторая надежда использовать модульные тождества для доказательства гипотезы Эрдеша – Штрауса. Никакое простое число не может быть квадратом, поэтому по теореме Хассе-Минковского всякий раз, когда является простым, существует большее простое число такой, что не является квадратичным вычетом по модулю . Одним из возможных подходов к доказательству гипотезы может быть найти для каждого простого числа большее простое число и сравнение, решающее проблема для соответствующий против . Если бы это можно было сделать, никакого премьера могло бы быть контрпримером к этой гипотезе, и эта гипотеза была бы верной. [ 12 ]
Количество решений
[ редактировать ]Эльшольц и Тао (2013) показали, что среднее количество решений задачи задача (усреднена по простым числам до ) ограничена сверху полилогарифмически по . Для некоторых других диофантовых задач существование решения можно продемонстрировать с помощью асимптотических нижних границ числа решений, но лучше всего это работает, когда число решений растет хотя бы полиномиально, поэтому более медленная скорость роста результата Эльшольца и Тао делает доказательство такого типа менее вероятно. Эльшольц и Тао классифицируют решения в зависимости от того, одно или два из них , , или делится на ; для премьер-министра , это единственные возможности, хотя (в среднем) большинство решений для композита бывают других типов. Их доказательство использует теорему Бомбьери–Виноградова , теорему Брюна–Титчмарша и систему модульных тождеств, справедливых, когда соответствует или модуль , где и любые два взаимно простых положительных целых числа и любой нечетный фактор . Например, установка дает одну из личностей Морделла, действительную, когда это 3 мод 4. [ 15 ]
Обобщения
[ редактировать ]Как и в случае с дробями вида , было высказано предположение, что каждая дробь (для ) можно выразить как сумму трех положительных единичных дробей. Обобщенная версия гипотезы утверждает, что для любого положительного , все дроби, кроме конечного числа может быть выражена как сумма трех положительных единичных дробей. Гипотеза о дробях была сделана Вацлавом Серпинским в статье 1956 года, в которой полная гипотеза была приписана ученику Серпинского Анджею Шинцелю . [ 16 ]
Даже если обобщенная гипотеза неверна при любом фиксированном значении , то число дробей с в диапазоне от 1 до не имеющие трехчленных разложений, должны расти только сублинейно в зависимости от . [ 13 ] В частности, если сама гипотеза Эрдеша–Штрауса (случай ) неверно, то число контрпримеров растет лишь сублинейно. Еще сильнее для любого фиксированного , только сублинейное число значений им нужно более двух членов в разложении египетской дроби. [ 17 ] Обобщенная версия гипотезы эквивалентна утверждению, что число нерасширяемых дробей не просто сублинейно, но и ограничено.
Когда - нечетное число . По аналогии с проблемой нечетных жадных разложений египетских дробей можно задаться вопросом о решении в котором , , и — различные положительные нечетные числа. Известно, что решения этого уравнения всегда существуют для случая k = 3 . [ 18 ]
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Jump up to: а б с д и ж Грэм (2013) .
- ^ Jump up to: а б Эппштейн (1995) , раздел разрешения конфликтов .
- ^ Эппштейн (1995) .
- ^ Облат (1950) ; Эльшольц и Тао (2013)
- ^ См., например, Sander (1994) для более простой диофантовой формулировки, использующей более конкретные предположения о том, какой из , , и делятся на .
- ^ См «Разрешение конфликтов» . раздел Эппштейна (1995) , где представлено доказательство того, что тесно связанный процесс замены (с другим разложением для четных знаменателей, которое уменьшает количество дробей) всегда заканчивается неповторяющимся разложением.
- ^ Джарома (2004) .
- ^ Облат (1950) ; Розати (1954) ; Поцелуй (1959) ; Бернштейн (1962) ; Ямамото (1965) ; Терзи (1971) ; Йолленстен (1976) ; Коциреас (1999) .
- ^ Jump up to: а б Соль (2014) .
- ^ Брайт и Логран (2020) .
- ^ Эльшольц и Тао (2013) .
- ^ Jump up to: а б Ионаску и Уилсон (2011) .
- ^ Jump up to: а б Уэбб (1970) ; Воан (1970) ; Ли (1981) ; Ян (1982) ; Ахмади и Блейхер (1998) ; Эльшольц (2001) .
- ^ Морделл (1967) .
- ^ О количестве решений 4/p = 1/n_1 + 1/n_2 + 1/n_3 , Теренс Тао , «Что нового», 7 июля 2011 г.; Подсчет количества решений уравнения Эрдеша-Штрауса на долях единицы , Теренс Тао , 31 июля 2011 г.
- ^ Серпинский (1956) ; Воан (1970) .
- ^ Хофмайстер и Столл (1985) .
- ^ Шинцель (1956) ; Сурьянараяна и Рао (1965) ; Хагедорн (2000) .
Ссылки
[ редактировать ]- Ахмади, Миннесота; Блейхер, Миннесота (1998), «О гипотезах Эрдеша, Штрауса и Серпинского о египетских дробях», Международный журнал математических и статистических наук , 7 (2): 169–185, MR 1666363 .
- Бернштейн, Леон (1962), "О решении диофантова уравнения , особенно в случае ", Журнал чистой и прикладной математики (на немецком языке), 211 : 1–10, doi : 10.1515/crll.1962.211.1 , MR 0142508 , S2CID 118098315 .
- Брайт, Мартин; Логран, Дэниел (2020), «Препятствие Брауэра-Манина для поверхностей Эрдеша-Штрауса», Бюллетень Лондонского математического общества , 52 (4): 746–761, arXiv : 1908.02526 , doi : 10.1112/blms.12374 , MR 4171399 , S2CID 218959757 .
- Эльшольц, Кристиан (2001), "Суммы единицы измерения», Transactions of the American Mathematical Society , 353 (8): 3209–3227, doi : 10.1090/S0002-9947-01-02782-9 , MR 1828604 .
- Эльшольц, Кристиан; Тао, Теренс (2013), «Подсчет количества решений уравнения Эрдеша – Штрауса в долях единицы» (PDF) , Журнал Австралийского математического общества , 94 (1): 50–105, arXiv : 1107.1010 , doi : 10.1017 /S1446788712000468 , МР 3101397 , S2CID 17233943 .
- Эппштейн, Дэвид (1995), «Десять алгоритмов для египетских дробей», Mathematica в образовании и исследованиях , 4 (2): 5–15 . См., в частности, «Маленькие числители». раздел
- Эрдеш, Пол (1950), «Аз о целочисленных решениях уравнения (Об одном диофантовом уравнении)» (PDF) , Матем. Лапок. (на венгерском языке), 1 : 192–210, MR 0043117 .
- Грэм, Рональд Л. (2013), «Пол Эрдеш и египетские фракции» (PDF) , в Ловасе, Ласло ; Ружа, Имре З. ; Сос, Вера Т. (ред.), Столетие Эрдеша , Математические исследования Общества Боляи, том. 25, Будапешт: Математическое общество Яноша Бойяи , стр. 289–309, дои : 10.1007/978-3-642-39286-3_9 , МР 3203600
- Гай, Ричард К. (2004), Нерешенные проблемы теории чисел (3-е изд.), Springer Verlag , стр. D11, ISBN 0-387-20860-7 .
- Хагедорн, Томас Р. (2000), «Доказательство гипотезы о египетских дробях», American Mathematical Monthly , 107 (1), Mathematical Association of America: 62–63, doi : 10.2307/2589381 , JSTOR 2589381 , MR 1745572 .
- Хофмайстер, Герд; Столл, Питер (1985), «Заметки о египетских дробях», Журнал чистой и прикладной математики , 362 : 141–145, MR 0809971 .
- Ионаску, Ойген Дж.; Уилсон, Эндрю (2011), «О гипотезе Эрдеша-Штрауса», Румынский обзор чистой и прикладной математики , 56 (1): 21–30, arXiv : 1001.1100 , MR 2848047 .
- Джарома, Джон Х. (2004), «О расширении на три египетские дроби» , Математический крест , 30 (1): 36–37 .
- Джолленстен, Ральф В. (1976), «Заметки о египетской проблеме», Труды Седьмой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Университет штата Луизиана, Батон-Руж, Луизиана, 1976) , Congressus Numerantium, том. XVII, Виннипег, Ман.: Utilitas Math., стр. 351–364, MR 0429735 .
- Кисс, Эрнест (1959), «Некоторые замечания по диофантовому уравнению», акад. RP Ромин Фил. Клужский конный завод. Серк. Мачта. (на румынском языке), 10 : 59–62, MR 0125069 .
- Коциреас, Илиас (1999), «Гипотеза Эрдеша-Штрауса о египетских дробях», Пол Эрдеш и его математика (Будапешт, 1999) , Будапешт: Янош Больяи Математика. Соц., стр. 140–144, МР 1901903 .
- Ли, Деланг (1981), «Об уравнении ", Журнал теории чисел , 13 (4): 485–494, doi : 10.1016/0022-314X(81)90039-1 , MR 0642923 .
- Морделл, Луи Дж. (1967), Диофантовые уравнения , Academic Press, стр. 287–290 .
- Облат, Ричард (1950), «О диофантовом уравнении ", Mathesis (на французском языке), 59 : 308–316, MR 0038999 ,
М. Штраус [sic] проверил гипотезу М. Эрдеша для любого значения n < 5000 и М. Шапиро для n < 20 000. Наши теоремы дают решение для любого числа < 106.128
. - Розати, Луиджи Антонио (1954), «О диофантовом уравнении ", Boll. Un. Mat. Ital. (3) (на итальянском языке), 9 : 59–63, MR 0060526 .
- Салез, Серж Э. (2014), Гипотеза Эрдеша-Штрауса Новые модульные уравнения и проверка , arXiv : 1406.6307 , Bibcode : 2014arXiv1406.6307S
- Сандер, JW (1994), «На и полумерное сито Иванца», Journal of Number Theory , 46 (2): 123–136, doi : 10.1006/jnth.1994.1008 , MR 1269248 .
- Шинцель, Андре (1956), «О некоторых свойствах чисел». И , Или est un nombre impair», Mathesis (на французском языке), 65 : 219–222, MR 0080683 .
- Серпинский, Вацлав (1956), «О разложении рациональных чисел на простые дроби», Mathesis (на французском языке), 65 : 16–32, MR 0078385 . Перепечатано с дополнительными аннотациями в Серпинский, Вацлав (1974), Избранные произведения , т. I, Варшава: PWN — Польские научные издания, стр. 169–184, МР 0414302 .
- Сурьянараяна, Д.; Рао, Н. Венкатешвара (1965), «О статье Андре Шинцеля», J. Indian Math. Соц. , Новая серия, 29 : 165–167, МР 0202659 .
- Терци, Д.Г. (1971), «О гипотезе Эрдеша-Штрауса», Nordisk Tidskr. Обработка информации (BIT) , 11 (2): 212–216, doi : 10.1007/BF01934370 , MR 0297703 , S2CID 124845157 .
- Воган, Р.К. (1970), «К проблеме Эрдеша, Штрауса и Шинзеля», Mathematika , 17 (2): 193–198, doi : 10.1112/S0025579300002886 , MR 0289409
- Уэбб, Уильям А. (1970), «О », Proceedings of the American Mathematical Society , 25 (3), American Mathematical Society: 578–584, doi : 10.2307/2036647 , JSTOR 2036647 , MR 0256984 .
- Ямамото, Коичи (1965), «О диофантовом уравнении », Мемуары естественного факультета Университета Кюсю. Серия А. Математика , 19 :37–47, doi : 10.2206/kyushumfs.19.37 , MR 0177945 .
- Ян, Сюнь Цянь (1982), «Заметка о », Proceedings of the American Mathematical Society , 85 (4): 496–498, doi : 10.2307/2044050 , JSTOR 2044050 , MR 0660589 .