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

Гипотеза Зарембы — утверждение теории чисел о представлениях несократимых дробей через цепные дроби: существует абсолютная константа [math]\displaystyle{ \Lambda }[/math] со следующим свойством: для любого [math]\displaystyle{ q \geqslant 2 }[/math] существует [math]\displaystyle{ a \lt q }[/math] такое, что [math]\displaystyle{ (a,q) = 1 }[/math] и для разложения:

[math]\displaystyle{ \frac{a}{q} = [a_1,a_2,\dots,a_n] = \cfrac{1}{a_1 + \cfrac{1}{a_2 + \frac{1}{\dots + \frac{1}{a_s}}}} }[/math]

выполняются неравенства:

[math]\displaystyle{ a_i \leqslant \Lambda,\ i=1,\dots,s }[/math].

В наиболее сильной формулировке фигурирует значение [math]\displaystyle{ \Lambda=5 }[/math] для произвольного [math]\displaystyle{ q }[/math] и значение [math]\displaystyle{ \Lambda=3 }[/math] для достаточно больших [math]\displaystyle{ q }[/math]..

Гипотезу выдвинул Станислав Заремба-младший (польск. Stanisław Krystyn Zaremba) в 1972 году. Главный прорыв в её исследовании связан с работой Бургейна и Конторовича (нем. Alex Kontorovich) 2014 года, в которой слабый вариант гипотезы доказан для почти всех чисел. Впоследствии их результаты многократно улучшались.

Мотивация

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

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

Обобщения

«Алфавиты» значений неполных частных

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

Гипотеза Хенсли

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

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

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

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

Вычисление хаусдорфовой размерности

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

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

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

[math]\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) }[/math].

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

[math]\displaystyle{ \lim \limits_{N \to \infty} {\dim_H(\mathfrak{C}_{\{ 1,\dots,N \}})} = 1 }[/math].

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

Продвижения

Слабые точные результаты

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

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

Плотностные результаты

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

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

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

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

Оценки с хаусдорфовой размерностью

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

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

Модулярная версия

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

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

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

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

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

Методы исследования

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

[math]\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}\ }[/math],

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

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

[math]\displaystyle{ \begin{pmatrix} 0 & 1 \\ 1 & a \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & a' \end{pmatrix},\ a, a' \in {\mathcal A} }[/math],

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

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

Литература

• I. J. Good. The fractional dimensional theory of continued fractions (англ.) // Mathematical Proceedings of the Cambridge Philosophical Society. — 1941. — Vol. 37, iss. 3. — P. 199–228.
• Н. М. Коробов. Теоретико-числовые методы в приближённом анализе. — М.: Физматгиз, 1963. — 224 с.
• H. Niederreiter. Quasi-Monte Carlo methods and pseudo-random numbers (англ.) // Bull. Amer. Math. Soc.. — 1978. — Vol. 84, iss. 6. — P. 957–1041.
• I. Borosh & H. Niederreiter. Optimal multipliers for pseudo-random number generation by the linear congruential method (англ.) // BIT Numerical Mathematics. — 1983. — Vol. 23. — P. 65–74.
• H. Niederreiter. Dyadic fractions with small partial quotients (англ.) // Monatshefte für Mathematik. — 1986. — Vol. 101. — P. 309–315.
• D. Hensley. The distribution mod [math]\displaystyle{ n }[/math] of fractions with bounded partial quotients (англ.) // Pacific Journal of Mathematics. — 1994. — Vol. 166, iss. 1. — P. 43–54.
• D. Hensley. A Polynomial Time Algorithm for the Hausdorff Dimension of Continued Fraction Cantor Sets (англ.) // Journal of Number Theory. — 1996. — Vol. 58, iss. 1. — P. 9–45.
• O. Jenkinson. On the density of Hausdorff dimensions of bounded type continued fraction sets: the Texan conjecture (англ.) // Stochastics and Dynamics. — 2004. — Vol. 4, iss. 1. — P. 63–76.
• N. G. Moshchevitin. On some open problems in Diophantine approximation (англ.). — 2012. — arXiv:1202.4539v5.
• J. Bourgain, A. Kontorovich. On Zaremba’s Conjecture (англ.) // Annals of Mathematics. — 2014. — Vol. 180. — P. 137–196. — arXiv:1107.3776v2.
• И. Д. Кан, Д. А. Фроленков. Усиление теоремы Бургейна–Конторовича (рус.) // Известия РАН. — 2014. — Т. 78, вып. 2. — С. 87–144.
• И. Д. Кан. Усиление теоремы Бургейна–Конторовича. V (рус.) // Труды Математического института имени В. А. Стеклова. — 2017. — Т. 296. — С. 133–139.
• M. Magee, H. Oh, D. Winter. Uniform congruence counting for Schottky semigroups in [math]\displaystyle{ SL_2({\mathbb Z}) }[/math] (англ.) // Journal für die reine und angewandte Mathematik (Crelles Journal). — 2019. — Vol. 2019, iss. 753. — P. 89–135. — arXiv:1601.03705.
• N. G. Moshchevitin, I. D. Shkredov. On a modular form of Zaremba’s conjecture (англ.). — 2019. — arXiv:1911.07487.
• И. Д. Кан. Усиление одной теоремы Бургейна – Конторовича (рус.) // Дальневосточный математический журнал. — 2020. — Т. 20, вып. 2. — С. 164–190.
• I. D. Shkredov. Growth in Chevalley groups relatively to parabolic subgroups and some applications (англ.). — 2020. — arXiv:2003.12785.