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

Гіпотеза Заремби — твердження теорії чисел про подання нескоротних дробів через неперервні дроби: існує абсолютна стала ${\displaystyle \Lambda }$ з такою властивістю: для будь-якого ${\displaystyle q\geqslant 2}$ існує ${\displaystyle a<q}$ таке, що ${\displaystyle (a,q)=1}$ і для розкладу^[1]:

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

виконуються нерівності:

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

У найсильнішому формулюванні фігурує значення ${\displaystyle \Lambda =5}$ для довільного ${\displaystyle q}$ та значення ${\displaystyle \Lambda =3}$ для досить великих ${\displaystyle q}$^[2].

Гіпотезу висунув 1972 року Станіслав Заремба-молодший^[pl]. Головний прорив у її дослідженні пов'язаний із працею Бургена і Конторовича^[de] 2014 року, в якій слабкий варіант гіпотези доведено для багатьох чисел. Згодом їх результати багато разів покращували.

Історично гіпотеза виникла у зв'язку з пошуком оптимального способу чисельного інтегрування на зразок методу Монте-Карло. Через обмеження на неповні частки Заремба оцінював характеристику ґратки, що описує найменшу віддаленість її точок від початку координат^[3]. Низка радянських математиків також замислювалися про цю гіпотезу у зв'язку з чисельним інтегруванням, але в друкованому вигляді її ніде не заявляли^[4].

Сама постановка задачі пов'язана з діофантовими наближеннями. Для наближення довільного дійсного числа ${\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}}}}$. Легко отримати й аналогічну (з точністю до сталої) оцінку знизу, тому гіпотеза Заремби — це точно твердження про існування нескоротних погано наближуваних дробів з будь-яким знаменником^[5].

Часто розглядають загальніше питання^[6]: як залежать властивості ${\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 року розглянув зв'язок обмежень на неповні частки з гаусдорфовою розмірністю відповідних дробів, і висунув гіпотезу, яку згодом спростовано^[7]:

Множина ${\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}}$ — гаусдорфова розмірність.

Контприклад^[8] побудовано для абетки ${\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}}}$^[9].

Питання обчислення гаусдорфової розмірності для абеток вигляду ${\displaystyle {\mathcal {A}}=\{1,\dots ,N\}}$ розглядалося в теорії діофантових наближень задовго до гіпотези Заремби і, мабуть, бере початок із роботи 1928 року^[10]. У статті, де запропоновано гіпотезу, Генслі описав загальний алгоритм із поліноміальним часом роботи, заснований на такому результаті^[11]: для заданого алфавіту ${\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}}}$^[12].

Для абеток із послідовних чисел Генслі отримав оцінку:

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

Цей факт суттєво використовувався в доведенні центрального результату Бургена та Конторовича^[13].

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

Рукавишнікова, розвиваючи простий результат Коробова, показала існування для будь-кого ${\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)}$ — функція Ейлера^[15].

Найсильнішим і найзагальнішим є результат Бургена та Конторовича:

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

тобто що гіпотеза Заремби з параметром ${\displaystyle \Lambda =50}$ правильна для майже всіх чисел. Їхній результат стосувався не лише цієї абетки, але й будь-якої іншої з умовою ${\displaystyle \dim({\mathfrak {C}}_{\mathcal {A}})>0{,}98397}$^[16]. Згодом їхній результат покращено для ${\displaystyle \Lambda =5}$ та залишкового члена ${\displaystyle N^{-c}}$, де ${\displaystyle c>0}$ — стала^[17].

Для слабших обмежень той самий метод дозволяє показати, що множина ${\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\}}$^[18].

Генслі показав, що якщо ${\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 }$^[19]. Для окремих інтервалів значень ${\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...}$ показник степеня прямує до одиниці^[20].

Загальна кількість дробів над тією чи іншою абеткою зі знаменниками, що не перевищують ${\displaystyle N}$, з точністю до сталої дорівнює ${\displaystyle N^{2\delta }}$^[21].

Генслі виявив, що знаменники дробів, які задовольняють гіпотезі Заремби, рівномірно розподілені (з урахуванням кратності) за будь-яким модулем^[22]. З цього, зокрема, випливає існування таких дробів зі знаменниками, рівними нулю (і будь-якому іншому значенню) за тим чи іншим модулем.

Наслідок результату Генслі (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})}$^[23];

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

Сучасні методи, що сягають статті Бургена й Конторовича, розглядають гіпотезу Заремби мовою матриць розміру 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}}}$ ,

на наявність у ній матриць з тим чи іншим значенням у нижній правій позиції. Для аналізу розподілу таких значень використовують тригонометричні суми, а саме спеціальні аналоги коефіцієнтів Фур'є^[25].

Використання такого інструментарію, а також робота фактично з множинами добутків (де елементи множини — матриці) надає задачі арифметико-комбінаторного характеру.

• Обмежені неповні частки

• 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 ${\displaystyle 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 ${\displaystyle 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.