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

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

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

Мотивація

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

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

Узагальнення

«Абетки» значень неповних часток

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

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

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

Обчислення гаусдорфової розмірності

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

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

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

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

Просування

Слабкі точні результати

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

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

Щільнісні результати

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

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

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

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

Оцінки з гаусдорфовою розмірністю

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

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

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

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

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

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

Методи дослідження

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

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

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

Див. також

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

Примітки

1. Згідно з загальною теорією неперервних дробів, такий розклад єдиний.
2. Borosh, Niederreiter, 1983, с. 69
3. Niederreiter, 1978, с. 988—989, див. також опис поняття «good lattice points» на с. 986
4. Кан, Фроленков, 2014, с. 88
5. Коробов, 1963, с. 25, лема 5
6. Bourgain, Kontorovich, 2014, розділ 1
7. Hensley, 1996, гіпотеза 3
8. Bourgain, Kontorovich, 2014, див. гіпотезу 1.3 та коментар після неї
9. Bourgain, Kontorovich, 2014, гіпотеза 1.7, теорема 1.8
10. Див. другий абзац у Good, 1941
11. Hensley, 1996, теорема 3
12. Jenkinson, 2004, див. огляд обчислювальних результатів у розділі 4, а результат про щільність розподілу значень ${\displaystyle \dim _{H}({\mathfrak {C}}_{\mathcal {A}})}$ у розділі 5
13. Bourgain, Kontorovich, 2014, зауваження 1.11
14. Niederreiter, 1986.
15. Moshchevitin, 2012, с. 23, розділ 5.1
16. Bourgain, Kontorovich, 2014, зауваження 1.20
17. Magee, Oh, Winter, 2019, с. 92.
18. Кан, 2017.
19. Bourgain, Kontorovich, 2014, зауваження 1.15, теорема 1.23
20. Кан, 2020, див. там само огляд результатів для інших значень ${\displaystyle \delta }$
21. Bourgain, Kontorovich, 2014, зауваження 1.13
22. Hensley, 1994, с. 54, наслідок 3.
23. Moshchevitin, Shkredov, 2019, теорема 2
24. Shkredov, 2020, теорема 5
25. Bourgain, Kontorovich, 2014

Література

• 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.