Гипотеза Зарембы

• Непрерывная дробь (или цепная дробь) — конечное или бесконечное математическое выражение вида

  ${\displaystyle [a_{0};a_{1},a_{2},a_{3},\cdots ]=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+\ldots }}}}}},}$ где ${\displaystyle a_{0}}$ есть целое число, а все остальные ${\displaystyle a_{n}}$ — натуральные числа (положительные целые)^[5].

• Погрешность аппроксимации — числовая мера отклонения приближенных данных, функций или математических моделей от их точных или исходных значений.
• Численное интегрирование (историческое название: (численная) квадратура) — вычисление значения определённого интеграла (как правило, приближённое). Под численным интегрированием понимают набор численных методов для нахождения значения определённого интеграла.
• Теория диофантовых приближений — раздел теории чисел, изучающий приближения вещественных чисел рациональными.
• Размерность Хаусдорфа, или хаусдорфова размерность — естественный способ определить размерность подмножества в метрическом пространстве.
• Функция Эйлера — мультипликативная арифметическая функция, значение которой равно количеству натуральных чисел, меньших либо равных и взаимно простых с ним.
• Подходящая дробь для цепной дроби ${\displaystyle x=[a_{0};a_{1},a_{2},a_{3},\ldots ]}$ — конечная цепная дробь ${\displaystyle [a_{0};a_{1},\ldots ,a_{n}]}$, значение которой есть некоторое рациональное число ${\displaystyle p_{n}/q_{n}}$.
• Дискретное преобразование Фурье (в англоязычной литературе DFT, Discrete Fourier Transform) — одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале.
• Тригонометрическая сумма — конечная сумма комплексных чисел, геометрически соответствующих векторам на единичной окружности.

Исторически гипотеза возникла в связи с поиском оптимального способа численного интегрирования в духе метода Монте-Карло. Через ограничение на неполные частные Заремба оценивал характеристику решётки, описывающую минимальную удалённость её точек от центра координат^[6]. Ряд советских математиков также задумывались об этой гипотезе в связи с численным интегрированием, но в печатном виде её нигде не заявляли^[7].

Сама постановка задачи связана с диофантовыми приближениями. Для приближения произвольного вещественного числа ${\displaystyle \alpha }$ дробью ${\displaystyle {\frac {p}{q}}}$ каноническим мерилом качества считается число ${\displaystyle c}$, для которого ${\displaystyle {\Bigg \vert }{\alpha -{\frac {p}{q}}}{\Bigg \vert }={\frac {1}{cq^{2}}}}$ (чем больше ${\displaystyle c}$, тем лучше приближение). Известно, что рациональные ${\displaystyle \alpha }$ лучше всего приближаются своими подходящими дробями ${\displaystyle {\frac {p_{n}}{q_{n}}}}$, для которых известна оценка ${\displaystyle {\Bigg \vert }{\alpha -{\frac {p_{n}}{q_{n}}}}{\Bigg \vert }\leqslant {\frac {1}{q_{n}q_{n+1}}}}$. Поскольку ${\displaystyle q_{n+1}<(a_{n}+1)q_{n}}$, то при наличии безусловной оценки ${\displaystyle a_{n}\leqslant \Lambda }$ предыдущая оценка не может быть лучше, чем ${\displaystyle {\Bigg \vert }{\alpha -{\frac {p_{n}}{q_{n}}}}{\Bigg \vert }\leqslant {\frac {1}{(\Lambda +1)q_{n}^{2}}}}$. Легко получить и аналогичную (с точностью до константы) оценку снизу, поэтому гипотеза Зарембы — это в точности утверждение о существовании несократимых плохо приближаемых дробей с любым знаменателем^[8].

Часто рассматривается более общий вопрос^[9]: как зависят свойства ${\displaystyle {\mathcal {D}}_{\mathcal {A}}}$ (множества знаменателей ${\displaystyle q}$, для которых существуют несократимые дроби ${\displaystyle {\frac {a}{q}}=[a_{1},\dots ,a_{s}]}$ с условием ${\displaystyle a_{i}\in {\mathcal {A}}}$ для всех ${\displaystyle i=1,\dots ,s}$) от алфавита (конечного множества натуральных чисел)? В частности, для каких ${\displaystyle {\mathcal {A}}}$ множество ${\displaystyle {\mathcal {D}}_{\mathcal {A}}}$ содержит почти все или все достаточно большие ${\displaystyle q}$?

Хенсли в 1996 году рассмотрел связь ограничений на неполные частные с хаусдорфовой размерностью соответствующих дробей, и выдвинул гипотезу, которая впоследствии была опровергнута^[10]:

Множество ${\displaystyle {\mathcal {D}}_{\mathcal {A}}}$ содержит все достаточно большие числа тогда и только тогда, когда ${\displaystyle \dim _{H}({\mathfrak {C}}_{\mathcal {A}})>{\frac {1}{2}}}$ (${\displaystyle {\mathfrak {C}}_{\mathcal {A}}}$ — множество дробей из интервала ${\displaystyle (0;1)}$, все неполные частные которых лежат в алфавите ${\displaystyle {\mathcal {A}}}$, ${\displaystyle \dim _{H}}$ — хаусдорфова размерность.

Контпример^[11] построен для алфавита ${\displaystyle {\mathcal {A}}=\{2,4,6,8,10\}}$: известно, что ${\displaystyle \dim _{H}({\mathfrak {C}}_{\mathcal {A}})\approx 0{,}517}$, но в то же время ${\displaystyle 4k+3\not \in {\mathcal {D}}_{\mathcal {A}}}$.

Бургейн и Конторович предложили более слабую форму этой гипотезы, связанную со знаменателями ${\displaystyle d}$, на которые наложены дополнительные ограничения. При этом они доказали её плотностную версию для более сильного ограничения, чем ${\displaystyle {\frac {1}{2}}}$^[12].

Вопрос вычисления хаусдорфовой размерности для алфавитов вида ${\displaystyle {\mathcal {A}}=\{1,\dots ,N\}}$ рассматривался в теории диофантовых приближений задолго до гипотезы Зарембы и, видимо, берёт начало с работы 1928 года^[13]. В статье, где была предложена гипотеза, Хенсли описал общий алгоритм с полиномиальным временем работы, основанный на следующем результате^[14]: для заданного алфавита ${\displaystyle {\mathcal {A}}}$ значение ${\displaystyle \dim _{H}({\mathfrak {C}}_{\mathcal {A}})}$ можно вычислить с точностью ${\displaystyle 2^{-N}}$ всего за ${\displaystyle O(N^{7})}$ операций.

Существует гипотеза, что множество значений таких размерностей ${\displaystyle \{\dim _{H}({\mathfrak {C}}_{\mathcal {A}}):|{\mathcal {A}}|\leqslant \infty \}}$ всюду плотно. Из компьютерных вычислений известно, что расстояние между его соседними элементами по крайней мере не меньше ${\displaystyle {\frac {1}{50}}}$^[15].

Для алфавитов из подряд идущих чисел Хенсли получил оценку:

${\displaystyle \dim _{H}({\mathfrak {C}}_{\{1,\dots ,N\}})=1-{\frac {6}{\pi ^{2}N}}-{\frac {72\log N}{\pi ^{4}N^{2}}}+O\left({\frac {1}{N^{2}}}\right)}$.

В частности, установлено, что:

${\displaystyle \lim \limits _{N\to \infty }{\dim _{H}({\mathfrak {C}}_{\{1,\dots ,N\}})}=1}$.

Этот факт существенно использовался в доказательстве центрального результата Бургейна и Конторовича^[16].

Нидеррейтер доказал гипотезу для степеней двойки и степеней тройки при ${\displaystyle \Lambda =3}$ и для степеней пятёрки при ${\displaystyle \Lambda =4}$^[17].

Рукавишникова, развивая простой результат Коробова, показала существование для любого ${\displaystyle q}$ дроби ${\displaystyle {\frac {a}{q}}=[a_{1},\dots ,a_{s}]}$ с условием ${\displaystyle a_{i}<\varphi (q)\log q,\ i=1,\dots ,s}$, где ${\displaystyle \varphi (q)}$ — функция Эйлера^[18].

Наиболее сильным и общим является результат Бургейна и Конторовича:

${\displaystyle |{\mathcal {D}}_{\{1,\dots ,50\}}\cap [1;N]|=N-o(N)}$,

то есть что гипотеза Зарембы с параметром ${\displaystyle \Lambda =50}$ верна для почти всех чисел. Их результат касался не только этого алфавита, но и любого другого с условием ${\displaystyle \dim({\mathfrak {C}}_{\mathcal {A}})>0{,}98397}$^[19]. Впоследствии их результат был улучшен для ${\displaystyle \Lambda =5}$ и остаточного члена ${\displaystyle N^{-c}}$, где ${\displaystyle c>0}$ — константа^[20].

Для более слабых ограничений тот же метод позволяет показать, что множество ${\displaystyle {\mathcal {D}}_{\mathcal {A}}}$ имеет положительную плотностью. В частности, из дальнейших улучшений известно, что это верно когда ${\displaystyle \dim({\mathfrak {C}}_{\mathcal {A}})>0.25({\sqrt {17}}-1)\approx 0.7807...}$, в том числе для ${\displaystyle {\mathcal {A}}=\{1,2,3,4\}}$^[21].

Хенсли показал, что если ${\displaystyle \dim _{H}({\mathfrak {C}}_{\mathcal {A}})=\delta }$, то ${\displaystyle |{\mathcal {D}}_{\mathcal {A}}\cap [1;N]|\gg N^{\delta }}$. Позже Бургейн и Конторович улучшили это неравенство до показателя ${\displaystyle \delta +{\frac {(2\delta -1)(1-\delta )}{5-\delta }}-o(1)}$ вместо ${\displaystyle \delta }$.^[22] Для отдельных интервалов значений ${\displaystyle \delta }$ позже были получены более сильные оценки. В частности, известно, что ${\displaystyle |{\mathcal {D}}_{\{1,2,3,5\}}\cap [1;N]|\gg N^{0.99}}$ и что при ${\displaystyle \delta \to {\frac {{\sqrt {40}}-4}{3}}\approx 0.7748...}$ показатель степени стремится к единице^[23].

Общее число дробей над тем или иным алфавитом со знаменателями, не превышающими ${\displaystyle N}$, с точностью до константы равно ${\displaystyle N^{2\delta }}$^[24].

Хенсли обнаружил, что знаменатели дробей, удовлетворяющих гипотезе Зарембы, равномерно распределены (с учётом кратности) по любому модулю^[25]. Из этого, в частности, следует существование таких дробей со знаменателями, равными нулю (и любому другому значению) по тому или иному модулю.

Следствие из результата Хенсли (1994): для любого ${\displaystyle \Lambda \geq 2}$ существует функция ${\displaystyle q=q_{\Lambda }(n)\equiv 0{\pmod {n}}}$ такая, что для любого ${\displaystyle n}$: существует несократимая дробь ${\displaystyle {\frac {a}{q}}}$, неполные частные которых ограничены ${\displaystyle \Lambda }$.

При ${\displaystyle q_{\Lambda }(n)=n}$ это утверждение было бы эквивалентно гипотезе Зарембы. Позже для простых ${\displaystyle n}$ были получены оценки скорости роста ${\displaystyle q_{\Lambda }(n)}$ в экстремальных случаях:

• для некоторой константы ${\displaystyle c}$ верно, что ${\displaystyle q_{2}(n)=O(n^{c})}$^[26];

• для любого ${\displaystyle \varepsilon >0}$ существует достаточно большое ${\displaystyle \Lambda }$ такое, что ${\displaystyle q_{\Lambda }(n)=O(n^{1+\varepsilon })}$^[27].

Современные методы, восходящие к статье Бургейна и Конторовича, рассматривают гипотезу Зарембы на языке матриц размера 2x2 и изучают соответствующие свойства матричных групп. Благодаря соотношению подходящих дробей разложение ${\displaystyle {\frac {a}{q}}=[a_{1},\dots ,a_{s}]}$ может быть записано как произведение матриц:

${\displaystyle {\begin{pmatrix}*&a\\*&q\end{pmatrix}}={\begin{pmatrix}0&1\\1&a_{1}\end{pmatrix}}{\begin{pmatrix}0&1\\1&a_{2}\end{pmatrix}}\dots {\begin{pmatrix}0&1\\1&a_{s}\end{pmatrix}}\ }$,

где звёздочками в первой матрице закрыты числа, значение которых не существенно.

Руководствуясь этим, изучается группа, порождённая матрицами вида:

${\displaystyle {\begin{pmatrix}0&1\\1&a\end{pmatrix}}{\begin{pmatrix}0&1\\1&a'\end{pmatrix}},\ a,a'\in {\mathcal {A}}}$,

на наличие в ней матриц с тем или иным значением в нижней правой позиции. Для анализа распределения таких значений используются тригонометрические суммы, а именно — специальные аналоги коэффициентов Фурье^[28].

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

Дискуссии сфокусированы вокруг новых методов, развивающих идеи Бургена-Конторовича, включая применение кругового метода Харди-Литтлвуда и теории операторов переноса. Новейшие достижения в теории расширений для групп матриц позволяют значительно расширить теоретические рамки и подтверждать гипотезу для более широких классов целых чисел, включая полиномиальные последовательности. Тем не менее, математическое сообщество сходится во мнении, что снижение этой константы (или доказательство в строгой формулировке для абсолютного ${\displaystyle M=5}$) потребует принципиально новых математических идей^{[29][30][31][32]}.