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

Гипотеза Зарембы — утверждение теории чисел о представлениях несократимых дробей через непрерывные дроби: существует абсолютная константа $\Lambda$ со следующим свойством: для любого $q\geqslant 2$ существует $a<q$ такое, что $(a,q)=1$ и для разложения:

${\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}}}}}}}}}$

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

$a_{i}\leqslant \Lambda ,\ i=1,\dots ,s$.

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

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

Мотивация

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

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

Обобщения

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

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

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

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

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

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

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

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

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

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

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

$\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)$.

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

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

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

Продвижения

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

Нидеррейтер доказал гипотезу для степеней двойки и степеней тройки при $\Lambda =3$ и для степеней пятёрки при $\Lambda =4$.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\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}}\$,

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

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

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

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

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

Литература

• 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 $n$ 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 $SL_{2}({\mathbb {Z} })$ (англ.) // 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.