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

Гіпотеза Заремби — твердження теорії чисел про подання нескоротних дробів через неперервні дроби: існує абсолютна стала $\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$.

Гіпотезу висунув 1972 року Станіслав Заремба-молодший. Головний прорив у її дослідженні пов'язаний із працею Бургена і Конторовича 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.