Джеймс Тэнтон разбрасывается задачками по теории чисел с той же щедростью, с которой Джон Д. Рокфеллер раздавал десятицентовики. Я уже писал об одной из задач Тэнтона. Спустя несколько недель моё внимание привлёк этот твит о факториалах и квадратах и уже не давал мне покоя:


«4!+1 = 25, квадрат числа. 5!+1 = 121, тоже квадрат числа. Можете привести ещё один пример? Ещё два примера?»

С помощью ручки и бумаги легко показать, что $$ не подходит. Факториал $$ — это $$; прибавив $$, получим число $$, которое не является квадратом. (Оно раскладывается на множители как $$.) С другой стороны, $$ равно $$, а прибавив $$, мы получим $$, что равно $$. Это даёт нам очень милое уравнение:

$$

Продолжив далее, мы выясним, что $$, $$ и $$ не являются квадратами чисел. Но чтобы продолжить поиск, нам требуется механизированная помощь. Вот функция на Julia, выполняющая очевидную работу — вычисление последовательных факториалов и проверку, являются ли они на $$ меньше квадрата:

function search_fac_sqr(maxn)
  fac = big(1)                      # большие целые нужны для n > 20
  for n in 1:maxn
    fac *= n                        # инкрементный факториал
    r = isqrt(fac + 1)              # округление sqrt в меньшую сторону
    if r * r == fac + 1
      println(n, "! + 1 = ", r, "^2 = ", r^2)
    end
  end
  println("Вот и всё, ребята!")
end

Вооружившись этим инструментом, давайте проверим $$ для всех $$ от $$ до $$. Вот, что сообщает нам программа:

search_fac_sqr(100)
4! + 1 = 5^2 = 25
5! + 1 = 11^2 = 121
7! + 1 = 71^2 = 5041
Вот и всё, ребята!

Это те же три случая, которые мы уже обнаружили с помощью ручки и бумаги — и в списке больше ничего нет. Другими словами, среди всех значений $$ вплоть до $$ только $$, $$ и $$ дают квадраты чисел. Когда я продолжил поиск до $$, то получил точно такой же результат. Аналогично получилось с $$ и $$. Стоит упомянуть, что факториал $$ — довольно большое число из $$ десятичных разрядов. На этом этапе поисков я начал выдыхаться; больше того, я начал терять надежду. Когда $$ последовательным значениям $$ не удаётся получить единственный квадрат, сложно продолжать надеяться, что успех может ждать нас за углом. Тем не менее, я продолжал упорствовать. Я добрался до $$, факториал которого содержит $$ десятичных разрядов. Во всём множестве не попалось больше ни одного квадрата.

Что мы можем извлечь из этого доказательства — или его отсутствия? Являются ли 4, 5 и 7 единственными значениями $$, которые на $$ квадрата целого числа? Или где-то на числовой прямой ещё есть такие случаи, возможно, прямо после моего интервала? Может ли их быть бесконечно много? И если это так, где они? Если их нет, то почему?

---

На мой вкус, самым удовлетворительным способом разрешения этих вопросов будет нахождение некоего принципа теории чисел, гарантирующего, что $$ для $$. Мне не удалось найти такого принципа, но в мечтах я могу примерно представить, как может выглядеть доказательство. Допустим, мы избавимся от части формулы "$$", и начнём поиск целых чисел, таких что $$. Выясняется, что у этого уравнения есть только одно решение, при $$. Не стоит отягощать свой ноутбук поиском бо?льших решений — есть простое доказательство того, что их не существует. В любом квадрате целого числа все простые делители должны присутствовать чётное количество раз, например как в $$. В факториале по крайней мере один простой делитель — самый большой — всегда присутствует только один раз. (Если вы не понимаете, почему, прочитайте постулат Бертрана/теорему Чебышева.)

Разумеется, когда мы снова подставляем "$$" в формулу, то вся цепочка рассуждений разваливается на части. В общем случае, разложение на множители $$ и $$ совершенно отличается. Но возможно существует какое-то другое свойство $$, вступающее в конфликт с квадратностью. Оно может быть как-то связано с классами конгруэнции или с квадратными остатками. Из определения факториала мы знаем, что $$ делится на все положительные целые числа, меньшие или равные $$, а это значит, что $$ не может делиться ни на одно из этих чисел (за исключением $$). Это наблюдение исключает определённые типы квадратов, а именно те, у которых в разложени на множители присутствуют малые простые числа. Но для всех $$ квадратный корень $$ значительно превосходит $$, поэтому есть достаточно места для бо?льших делителей, как это происходит в случае $$.

Вот ещё один путь, который стоит исследовать. Десятичное представление любого большого факториала заканчивается строкой из $$, созданной как произведения $$ и $$ среди делителей числа. Таким образом, $$ должно выглядеть как

$$

где $$ обозначает любую десятичную цифру, а последующий ряд из $$ заканчивается единственной $$. Можем ли мы найти способ доказать, что число в таком виде никогда не бывает квадратом? Ну, если бы последняя цифра отличалась бы от $$, $$ или $$, то доказательство было бы простым, но многие квадраты заканчиваются на $$, например, $$ $$. Если и есть какое-то алгебраическое соображение, показывающее, что $$ не может быть квадратом, то оно более тонкое.

Всё вышесказанное — это выдуманная математика. Я смешал несколько ингредиентов, которые должны превратиться во вкусное тесто, но понятия не имею, как испечь пирог. Возможно, кто-то ещё поможет мне с рецептом. Тем временем, я хочу развлечься с альтернативной гипотезой: ничто не мешает $$ быть квадратом, кроме невероятности.

---

Паттерн, наблюдаемый в задаче $$ — несколько соответствий среди наименьших элементов последовательностей, а затем ни одного совпадения во многих тысячах элементов — не уникален для факториалов и квадратов. Другие пары последовательностей демонстрируют похожее поведение. Треугольные числа, начинающиеся с $$, задаются формулой $$. Если мы будем искать факториалы, которые тоже являются треугольными, то получим $$, затем $$ и наконец $$. Больше никаких примеров до $$ не встречается.

А как насчёт факториалов, которые на $$ меньше треугольного числа, удовлетворяющих уравнению $$? Я знаю единственный такой случай: $$. Немного расширив поиск, я обнаружил, что $$ треугольно для $$, после чего снова нет никаких совпадений до $$.

Для другого эксперимента мы можем вернуться к квадратам чисел и отказаться от факториалов, заменив их вечно популярным рядом Фибоначчи $$, задаваемым рекурсией $$, где $$. Ещё с 1960-х было известно, что $$ и $$ — единственные положительные целы числа, одновременно являющиеся числами Фибоначчи и квадратами целых чисел. Поискав числа Фибоначчи, которые на $$ меньше квадрата, я выяснил, что $$ и $$, и других случаев не встречается до $$.

Мы можем сделать то же самое с числами Каталана, $$, ещё одним рядом с огромным фанатским клубом. Я выяснил, что среди чисел Каталана нет других квадратов, кроме $$ вплоть до $$; я не знаю, доказал ли кто-нибудь, что их не существует. Поиск случаев, при которых $$, тоже не даёт результатов, но есть несколько соответствий с низкими значениями для $$ при $$.

Нахождение похожего поведения во всех этих различных последовательностях, на мой взгляд, меняет сложность задачи. Если мы обнаружим какое-то таинственное особое свойство $$, объясняющее, почему оно никогда не соответствует квадратам (при больших значениях $$), нужно ли нам будет заново изобретать другой механизм для чисел Фибоначчи и ещё один для чисел Каталана? Не кажется ли более убедительным, что за всеми этими наблюдениями скрывается единственная общая причина?

Но эта причина не может быть слишком общей. Это не тот случай, когда можно взять любые две числовые последовательности и ожидать увидеть тот же паттерн в их пересечениях. Рассмотрим факториалы и простые числа. По самой природе факториалов, ни один из них, кроме 2! = 2, не может быть простым числом, но нет очевидных причин тому, что $$ не может быть простым числом. И действительно, для $$ простыми являются девять значений $$. Расширив границы поиска до $$, мы найдём ещё семь. Вот полное множество известных чисел, для которых $$ является простым:

$$

С увеличением $$ они встречаются всё реже, но при этом нет признаков резкого предела, как в рассмотренных ранее случаях. Продолжается ли этот ряд беспредельно? Это кажется логичной гипотезой. (Подробную информацию об этой последовательности, в том числе и справочные материалы, см. на странице факториальных простых Криса Колдуэлла.)

---

Мой вопрос таков: можем ли мы воспринимать эти любопытные паттерны как чистую случайность? Значения $$ образуют бесконечную последовательность целых чисел, распределённых по всех числовой прямой, плотно расположенных возле начала, но становящихся чрезвычайно разреженными при увеличении $$. Значения $$ образуют ещё одну бесконечную последовательность, тоже с уменьшающеся плотностью, хотя и не с таким резким спадом. Возможно, факториалы совпадают с квадратами среди самых малых целых чисел, просто потому, что этих целых недостаточно, чтобы «разгуляться», и некоторым из них приходится выполнять двойную работу. Но в обширных открытых пространствах числовой прямой факториал может блуждать годами — возможно, вечно — так и не встретившись с квадратом.

Позвольте мне изложить эту идею более чётко. Поскольку $$ не может быть квадратом, то мы знаем, что оно находится где-то между двумя квадратами; расположение на числовой прямой выглядит как $$. Расстояние между конечными точками этого интервала равно $$. Теперь выберем из интервала случайное число $$ и спросим, справедливо ли $$. Этому условию должно удовлетворять ровно одно значение $$, то есть вероятность совпадения равна $$, или приблизительно $$. Поскольку $$ растёт очень быстро, эта вероятность мгновенно стремится к нулю при увеличении $$. На графике ниже это показано фиолетовой линией. Заметьте, что к $$ фиолетовая кривая почти достигла $$.



Зелёная кривая обозначает вероятность совпадения между числами Фибоначчи и квадратами; форма похожа, однако она «ныряет» с «обрыва» чуть позже. Кривая Фибоначчи-квадратов приближенно равна отрицательной показательной функции: вероятность пропорциональна $$, где $$. Кривая факториал-квадратов ещё резче, потому что функция факториала суперэкспоненциальна: $$ растёт быстрее, чем $$, при любом постоянном $$.

Синяя кривая, фиксирующая вероятность совпадений между факториалами и простыми числами, имеет совершенно другую форму. В окрестности $$ среднее расстояние между последовательными простыми числами приблизительно равно $$, который растёт немного быстрее, чем сама $$ и намного медленее, чем $$. Вероятность совпадения между факториалами и простыми числами примерно равна $$. Непрерывная синяя кривая соответствует этой плавной аппроксимации. Синие точки, разбросанные рядом с линией, являются значениями вероятностей на основании настоящих расстояний между последовательными простыми числами.

---

Что можно сделать с этими кривыми? Допустимо ли применить теорию вероятностей к этим абсолютно детерминированным последовательностям чисел? Точно я не знаю. Прежде чем ставить этот вопрос напрямую, я предпочту сделать несколько шагов назад и рассмотреть более простую модель, в которой вероятность имеет полное право на использование.

Давайте позаимствуем одну из знаменитых урн Якоба Бернулли, в которой достаточно места для хранения бесконечного количества мячей для пинг-понга. Начнём с одного чёрного и одного белого мяча в урне, затем будем тянуть мячи случайным образом. Очевидно, что вероятность выбора чёрного равна $$. Положим выбранный мяч обратно в урну, а также добавим ещё один белый мяч. Теперь там три мяча и только один из них чёрный, так что вероятность вытягивания чёрного равна $$. Добавим четвёртый мяч, и вероятность чёрного падает до $$. Продолжая таким же образом, мы получим, что вероятность чёрного на $$-ном вытягивании должна быть равна $$.

Если мы будем продолжать эту процедуру бесконечно — всегда выбирать случайный мяч, возвращать его назад и добавлять ещё один белый мяч — то какова вероятность того, что мы хотя бы раз увидим чёрный мяч? Проще будет ответить на следствие из этого вопроса — вычислить вероятность никогда не увидеть чёрный мяч. Это бесконечное произведение $$, или:

$$

Если $$ стремится к бесконечности, произведение стремится к нулю. Другими словами, в бесконечной серии попыток вероятность никогда не вытащить чёрный мяч равна $$; это значит, что вероятность встретить чёрный хотя бы раз равна $$. («Вероятность $$» — это не совсем то же самое, что «определённость», но невероятно близко.)

Давайте теперь поставим другой эксперимент. Снова начнём с одного чёрного и одного белого мячей, но после первого цикла вытаскивания-возврата добавим два белых мяча, затем четыре белых, и так далее, так, что общее число мячей в урне на этапе $$ равна $$; на протяжении этого процесса все мячи, кроме одного, будут белыми. Теперь вероятность никогда не увидеть чёрный мяч равна $$, или:

$$

Это произведение не стремится к нулю, вне зависимости от величины $$. Также не стремится оно и к $$. Произведение сходится к константе с приблизительным значением $$. Это странно, не так ли? Даже при бесконечной серии вытаскиваний из урны мы не можем быть уверенными, появится ли чёрный шар, или нет.

Эти два эксперимента с урнами не соотносятся напрямую ни с одной из описанных выше задач соответствия; они просто иллюстрируют диапазон возможных результатов. Но мы можем создать процесс с урной, который имитирует вероятностный подход к задаче факториалов и квадратов. На $$-ном этапе урна содержит $$ мячей, только один из которых является чёрным. Вероятность никогда не увидеть чёрный мяч даже при бесконечной серии попыток равна

$$

Это выражение сходится к значению, приблизительно равному $$. Из этого следует, что вероятность увидеть чёрный мяч хотя бы раз равна $$, или $$. (Нет, это число не является $$, хотя и близко к нему.)

Процесс с урной, напоминающий задачу факториалов и простых чисел, даёт довольно отличающийся результат. Здесь число мячей в урне на этапе $$ равно $$, снова только с одним чёрным мячом. Бесконечное произведение, управляющее суммарной вероятностью, равно

$$

При численном доказательстве похоже, что это выражение стремится к нулю при стремлении $$ к бесконечности (хотя я не уверен в этом на сто процентов). Если оно действительно стремится к $$, до дополнительная вероятность того, что чёрный мяч рано или поздно появится, должна быть равна $$.

Некоторые из этих результатов заставили меня чувствовать себя одураченным, и даже немного раздражённым. Можете называть меня старомодным, но я всегда думал, что бесконечного количества бросков кости должно быть достаточно, чтобы устранить всякие сомнения в том, появится паттерн, или нет. В жестоком свете бесконечности, сказал бы я, всё является или запрещённым, или обязательным; когда $$ стремится к бесконечности, вероятность или стремится к $$, или стремится к $$. Но очевидно, что это не так. В модели урны с факториалами вероятность никогда не увидеть чёрный мяч не равна ни $$, ни $$ и находится где-то рядом с $$. Что же это означает? Как я должен удостовериться в правильности числа или даже проверить его первые несколько цифр? Выполнения бесконечной серии попыток недостаточно; необходимо собрать статистически значимую выборку бесконечных экспериментов. Для точного результата нужно провести бесконечную серию бесконечных экспериментов. Увы.

---

Модель с урной естественным образом соотносится с рандомизированной версией задачи факториалов-квадратов, в которой мы смотрим на $$ и выбираем случайное $$ из соответствующего интервала значений. А как насчёт исходной задачи $$? В этом случае нет случайной переменной, а потому нет смысла выполнять множество экспериментов для каждого значения $$. Система детерминирована. Для каждого $$ факториал $$ имеет точное значение и оно близко, или не близко к квадрату целого числа. Здесь нет никаких «может быть».

Тем не менее, есть обходной путь, способный добавить сюда вероятности. Чтобы сделать это, мы должны предположить, что факториалы и квадраты составляют своего рода эргодическую систему, в которой наблюдение за цепочкой событий в течение долгого периода времени аналогично наблюдению за множеством более коротких цепочек. Предположим, что факториалы и квадраты не связаны с их расположением на числовой прямой — что когда факториал оказывается между двумя квадратами, то расстояние до большего квадрата можно считать случайной переменной и каждое возможное расстояние имеет одинаковую вероятность. Если придерживаться этого предположения, то вместо рассмотрения одного значения $$ и проверки множества случайных значений $$ мы можем взять единственное значение $$ (а именно $$) и рассмотреть $$ для множества значений $$.

Аргументированно ли такое эргодическое предположение? Не совсем. Известно, что некоторые расстояния между $$ и $$ более вероятны, чем другие, а некоторые расстояния невозможны вообще. Однако эмпирическое свидетельство показывает, что такие отклонения должны быть незначительными. На графике ниже показано распределение расстояний между факториалом и следующим бо?льшим квадратом для первых $$ значений $$. Расстояния нормализованы в интервале $$ и классифицированы на $$ столбцов. Очевидных признаков смещения незаметно. Вычисление среднего и стандартного отклонения тех же $$ относительных расстояний даёт в результате значения в пределах $$ процента от тех, которые ожидаются при однородном случайном распределении. (Ожидаемые значения равны $$ и $$.)



Если такой вероятностный подход можно воспринимать всерьёз, то я могу сделать некоторые численные суждения о перспективах нахождения большого факториала, соседствующего с квадратом целого числа. Как упомянуто выше, общая вероятность того, что одно или несколько значений $$ равны квадратам, примерно равна $$. Таким образом, мы не должны слишком удивляться, что известно уже три таких случая, а именно примеры с $$, $$ и $$. Теперь мы можем применить тот же метод к вычислению вероятности нахождения хотя бы ещё одного случая с $$. Давайте сделаем вопрос более общим: «Независимо от того, видели ли мы квадраты среди первых $$ значений $$, каковы шансы, что мы увидим их после?» Чтобы ответить на этот вопрос, мы можем просто убрать первые $$ элементов из бесконечного произведения:

$$

При $$ ответ примерно равен $$. При $$ примерно равен $$. Мы спускаемся вниз по резкому склону фиолетовой кривой.

С практической точки зрения, дальнейшие поиски ещё одной пары факториала-квадрата не выглядят многообещающим способом траты времени и циклов процессора. Вероятность успеха быстро снижается до смехотворно малых чисел, типа $$. И тем не менее, с математической точки зрения, вероятность никогда не исчезает. Убирание конечного количества членов из передней части бесконечного произведения не может изменить её свойства сходимости. Если исходное произведение сходилось к ненулевому значению, так же себя будет вести и укороченная версия. Таким образом, мы попали в каньон максимального разочарования, в котором нет реалистичного способа найти награду, но вероятности всё равно говорят нам, что она может существовать.

---

Я завершу это неуклюжее эссе рассмотрением ещё одного примера (сильно заблаговременного). Предположим, мы применяем вероятностные рассуждения к поиску куба, который на $$ меньше квадрата. Если мы будем рассматривать точные соответствия между кубами и квадратами, то их довольно много — это шестые степени: $$. Но целые решения уравнения $$ не так часты. Один из примеров с низкими значениями найти легко: $$, но когда после $$ и $$ мы можем ожидать увидеть последовательные куб и квадрат?

Вероятностный подход предполагает, что у нас есть причины для оптимизма. По сравнению с факториалами и числами Фибоначчи, кубы растут гораздо медленнее; их скорость полиномиальна, а не экспоненциальна и не суперэкспоненциальна. В результате вероятность нахождения куба на заданном расстоянии от квадрата снижается гораздо менее резко, чем это происходит для $$ или $$. На графике ниже $$ — это оранжевая кривая.



Заметьте, что оранжевая кривая лежит прямо под синей, которая представляет вероятность того, что $$ находится рядом с простым числом. Близость этих двух кривых позволяет предположить, что две задачи — факториалы, соседние с простыми числами, кубы, соседние с квадратами — могут принадлежать к одному классу. Мы уже знаем, что факториал-простые возникают снова и снова, возможно до бесконечности. Эта аналогия приводит нас к догадке: возможно, совпадения кубов-квадратов тоже ничем не ограничено. Если мы продолжим наблюдать, то увидим ещё много их, кроме $$ и $$.

Но такая догадка совершенно неверна. Эта задача имеет очень давнюю историю. В 1844 году Эжен Каталан предположил, что $$ и $$ являются единственными последовательными степенными значениями среди целых чисел; это предположение окончательно доказал в 2004 году Преда Михайлеску. Особый случай квадратов и кубов решил ещё Эйлер в восемнадцатом веке. Таким образом, вероятности здесь ни при чём.

Все рассмотренные в статье вопросы относятся к категории диофантова анализа — исследованиям уравнений, решениями которых должны быть целые числа. Эта область математики печально известна задачами, которые легко поставить, но сложно решить. Гипотеза Каталана является одним из самых знаменитых примеров, вместе с великой теоремой Ферма. Когда диофантовы задачи окончательно решаются, доказательства обычно очень неэлементарны, в них используются изощрённые инструменты из глубоких областей математики — алгебраическая геометрия в доказательстве великой теоремы Ферма Эндрю Уайлса и Ричарда Тейлора, круговые поля в доказательстве Михайлеску гипотезы Каталана. Насколько мне известно, теория вероятностей не играла центральной роли ни в одном из таких доказательств.

Когда я начал бороться с этими вопросами несколько недель назад, я не ожидал, что найду конкретное решение. И мои ожидания полностью оправдались! На самом деле, в моей голове ситуация стала ещё более запутанной, чем вначале. Осознание того, что даже бесконечная серия экспериментов необязательно даст ответы на некоторые вопросы, глубоко меня расстраивает, и заставляет задаться вопросом, насколько хорошо я в действительности понимаю теорию вероятностей. Но вряд ли такая ситуация редка в математике. Думаю, мне уже стоит к этому привыкнуть.

Обновление: благодаря ещё одной подсказке Тэнтона я понял, что эта задача имеет долгую историю и даже название: задача Брокара, по имени Анри Брокара, выпустившего публикации о ней в 1876 и 1885 годах. Рамануджан упоминал её в 1913 году. Эрдёш предположил, что решений больше нет. Мариус Оверхольт связал её с abc-гипотезой. Брюс Берндт и Уильям Голуэй выяснили, что решений нет до $$. Всё это я узнал из статьи о задаче Брокара в Википедии. В этой статье также упоминается, что решения называются броуновскими числами [прим. пер.: происхождение названия неизвестно, непонятно, связаны ли они с Робертом Броуном].

Так что мне ещё есть, что почитать.