МатематикаПрепринтТеория2 мин чтения

БЕСКОНЕЧНЫЙ СПИСОК ИЗ ШЕСТИ ЧИСЕЛ, КОТОРЫЙ НИКОГДА НЕ УРАВНОВЕШИВАЕТСЯ

Запишите последовательность целых чисел, одно за другим. Теперь поищите два соседних блока одинаковой длины и с одинаковой суммой. В 1 4 2 3 блоки 1 4 и 2 3 оба состоят из двух чисел и оба дают в сумме 5: математики называют такую пару аддитивным квадратом.

Может ли бесконечная последовательность, записанная с помощью конечного набора чисел, избежать всех аддитивных квадратов — навсегда? Этот вопрос в разных формах ставился с 1972 года: Жюстеном (Justin), затем Брауном (Brown) и Фридманом (Freedman) в 1987 году, Пирилло (Pirillo) и Варриккьо (Varricchio) в 1994-м, Хальбайзеном (Halbeisen) и Хунгербюлером (Hungerbühler) в 2000-м. Браун и Фридман даже высказали противоположную гипотезу: что любая последовательность положительных целых чисел, остающаяся ниже некоторой границы, обязана содержать такой квадрат. Новая заметка называет это «задачей, открытой более 50 лет».

Шесть чисел, которые никогда не уравновешиваются

Джеффри Шаллит (Jeffrey Shallit) из Школы компьютерных наук (School of Computer Science) Университета Ватерлоо в Канаде теперь выписывает явную бесконечную последовательность, которая использует ровно шесть чисел и не содержит ни одного аддитивного квадрата.

Шесть «букв» совсем не малы. При D = 2⁵⁸, L = 2 · 85¹¹, H = 2D + 1 и U = L³ + 1 они таковы:

1, U + 1, U + 2, U + L + 1, U + L² + 1 и (H + 2)U + 1.

Мало только первое из них. В работе дано правило, позволяющее найти число на любой позиции, вместе с проверками: число 1 впервые встречается на позиции 1 152 921 504 466 744 130, если считать с нуля.

Как устроено доказательство

Построение состоит из двух шагов.

  1. Вспомогательная последовательность. Начните с одного числа и снова и снова заменяйте каждое число блоком из 2⁶⁰ чисел. Блоки устроены так, что если бы эта последовательность содержала аддитивный квадрат, она содержала бы и квадрат в 2⁶⁰ раз короче. Возьмите самый короткий из имеющихся квадратов: тогда должен был бы существовать ещё более короткий. Это противоречие показывает, что квадратов нет вовсе.
  2. Код из шести чисел. Затем вспомогательную последовательность кодируют шестью числами с помощью четырёхсимвольного шаблона, найденного Пелтомяки (Peltomäki) и Уайтлендом (Whiteland), который сам построен на подстановке из 85 символов, принадлежащей Вейкко Керянену (Veikko Keränen). Огромные промежутки между шестью числами делают каждую сумму читаемой, как цифры в системе счисления с очень большим основанием: любой квадрат в итоговой последовательности выдал бы квадрат во вспомогательной.

Четыре, пять или шесть?

Неизвестно, является ли шесть минимумом. Другой вид повторения, абелев квадрат, — это блок, за которым следует его перемешанная копия, например 1 2 3 3 1 2. Две его половины содержат одни и те же числа, поэтому у них всегда одинаковая сумма: каждый абелев квадрат — это также и аддитивный квадрат. Всего с тремя разными числами абелевых квадратов избежать нельзя — значит, нужно не меньше четырёх чисел. Поэтому наилучший размер — 4, 5 или 6. «Остаётся определить, какой из вариантов верен», — так заканчивается статья.

Написано машиной, подписано Джеффри Шаллитом

Заметка завершается разделом «Statement of AI Usage» («Заявление об использовании ИИ»): «Эта статья почти целиком написана GPT 6.2 Astra». Вводный материал, ссылки и обсуждение добавлены Шаллитом, который пишет: «Я несу полную ответственность за корректность». Компьютерная проверка построения, написанная на языке Lean и повторно запускаемая одной командой, выложена в интернет — «также построенная GPT 6.2 Astra». Заметка занимает восемь страниц и ещё не прошла рецензирование.