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

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

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

Див. також

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