Диофатновы приближения. Цепные дроби

Подробней про цепные дроби можно почитать в книге Хинчина А.Я. "Цепные дроби".

Пусть дано иррациональное число $\alpha$. Хочется найти "хорошие" его приближения рациональными числами.

Очевидно, для любого $q$ можно найти такое $p$, что выполнено неравенство $\left|\alpha - \frac{p}{q}\right| < \frac1q$.

Оказывается, верно более сильное утверждение.

Теорема (Дирихле). Пусть $\alpha \notin \mathbb {Q}$. Тогда $\exists$ бесконечно много несократимых дробей $\frac{p}{q}\colon$ $\left|\alpha - \frac{p}{q}\right| < \frac1{q^2}$.

$\blacktriangle$
Возьмём произвольное число $Q\in \mathbb {N}$. Разобьём отрезок $[0, 1]$ на $Q$ равных частей. Рассмотрим числа $\{ \alpha x\}$, где $x = 1, \ldots , Q+1$. Очевидно, найдутся числа $x_1 > x_2$ такие, что $|\{ \alpha x_1\} - \{ \alpha x_2\} | \leqslant \frac1Q \iff$
$|\alpha x_1 - [\alpha x_1] - \alpha x_2 + [\alpha x_2]| \leqslant \frac1Q \iff$
$|\alpha (x_1 - x_2) - ([\alpha x_1] - [\alpha x_2])| = |\alpha q - p| \leqslant \frac1Q \Rightarrow$
$\left|\alpha - \frac{p}{q}\right| \leqslant \frac1{qQ} \leqslant \frac1{q^2}$, т.к. $q = x_1 - x_2 \leqslant Q$.

Итак, мы нашли числа $p_1, q_1\colon \left| \alpha - \frac{p_1}{q_1} \right| \leqslant \frac1{q_1^2}$.

Возьмём новое число $Q \in \mathbb {N}\colon \frac1Q < \left| \alpha - \frac{p_1}{q_1} \right|$. Дальше, точно так же найдём $p_2, q_2\colon$

$\left| \alpha - \frac{p_2}{q_2} \right| \leqslant \frac1{q_2Q} \leqslant \frac1{q_2^2}$, $\frac1{q_2Q} < \left| \alpha - \frac{p_1}{q_1} \right|$.

Продолжая процесс, находим бесконечно много таких приближений.
$\blacksquare$

Такие приближения называются диофантовыми.

Что нужно потребовать от $\alpha$, чтобы получить $\left| \alpha - \frac{p}{q} \right| < \psi (q)$?

Цепные дроби

Пусть $a_1, \ldots, a_ n\in \mathbb {N}$.

$a_0 + \frac1{a_1 + \frac1{a_2 + \frac{\ldots }{ \frac1{a_ n}}}} =: [a_0, a_1, \ldots , a_ n] = \alpha \in \mathbb {Q}$. $a_ i$ — элементы цепной дроби (неполные частные).

Давайте запишем рациональное число $\alpha$ в некотором каноническом виде. Сделаем это индукцией по длине цепной дроби.

$[a_0] = \frac{a_0}{1}$. Допустим, мы научились записывать цепные дроби длины $\leqslant n$. Рассмотрим $[a_0, a_1, \ldots , a_ n] = a_0 + \frac1{[a_1, \ldots , a_ n] = \frac{p'}{q'}} = \frac{a_0 p' + q'}{p'}$. (Канонические числитель/знаменатель).

Дробь $[a_0, \ldots , a_ k]$ будем называть $k$-й подходящей дробью.

Утверждение. $\forall k\geqslant 2\colon$ $p_ k = a_ k p_{k-1} + p_{k-2}$, $q_ k = a_ k q_{k-1} + q_{k-2}$.

$\blacktriangle$
Докажем по индукции.

База: $k=2$. $[a_0, a_1, a_2]$. $[a_0] = \frac{a_0}{1}$,

$[a_0, a_1] = a_0 + \frac1{[a_1]} = \frac{a_0a_1 + 1 = p_1}{a_1 = q_1}$,

$[a_0, a_1, a_2] = a_0 + \frac1{[a_1, a_2]} = a_0 + \frac1{\frac{a_1a_2 + 1}{a_2}} = a_0 + \frac{a_2}{a_1a_2 + 1} = \frac{a_0a_1a_2 + a_2 + a_0}{a_1a_2 + 1} = \frac{p_2}{q_2}$.

$p_2 = a_0a_1a_2 + a_0 + a_2 = a_2(a_0 a_1 + 1) + a_0$.

Шаг индукции: Рассмотрим $[a_0, a_1, \ldots , a_ k]$ и $[a_1, a_2, \ldots , a_ k] = \frac{p_ k'}{q_ k'}$.

$[a_0, \ldots , a_ k] = a_0 + \frac1{[a_1, \ldots , a_ k]}$.

$\frac{p_ k}{q_ k} = \frac{a_0p_ k' + q_ k'}{p_ k'}$, т.е. $p_ k = a_0 p_ k' + q_ k'$, $q_ k = p_ k'$.

$p_ k' = a_ k p_{k-1}' + p_{k-2}'$, $q_ k' = a_ k q_{k-1}' + q_{k-2}'$.

$p_ k = a_0(a_ k p_{k-1}' + p_{k-2}') + (a_ k q_{k-1}' + q_{k-2}') = a_ k(a_0 p_{k-1}' + q_{k-1}') + a_0{p_{k-2}' + q_{k-2}'} =$ $a_ k p_{k-1} + p_{k-2}$.

Для $q_ k$ аналогично.
$\blacksquare$

$p_ k = a_ k p_{k-1} + p_{k-2} |\cdot q_{k-1}$,

$q_ k = a_ k q_{k-1} + q_{k-2} |\cdot p_{k-1}$.

$p_ k q_{k-1} - q_ k p_{k-1} = p_{k-2} q_{k-1} - p_{k-1} q_{k-2}$.

$p_1 q_0 - q_1 p_0 = (a_0 a_1 + 1)\cdot 1 - a_1 a_0 = 1$.

Следствие 1. $p_ k q_{k-1} - q_ k p_{k-1} = (-1)^{k+1}$.

Следствие из Следствия 1. Подходящие дроби несократимы, $(p_ k, q_ k) = 1$.

Следствие 2.

$p_ k = a_ k p_{k-1} + p_{k-2} |\cdot q_{k-2}$,

$q_ k = a_ k q_{k-1} + q_{k-2} |\cdot p_{k-2}$.

$p_ k q_{k-2} - q_ k p_{k-2} = a_ k (p_{k-1} q_{k-2} - p_{k-2} q_{k-1}) = (-1)^ k a_ k$.

Следствия 1 и 2 $\Rightarrow$ $\frac{p_ k}{q_ k} - \frac{p_{k-1}}{q_{k-1}} = \frac{(-1)^{k+1}}{q_ k q_{k-1}}$, $\frac{p_ k}{q_ k} - \frac{p_{k-2}}{q_{k-2}} = \frac{(-1)^ k a_ k}{q_ k q_{k-2}}$.

Дроби с чётными номерами возрастают, но при это меньше дробей с нечётными номерами, дроби с нечётными номерами убывают.

Бесконечные цепные дроби.

$a_0 + \frac1{a_1 + \frac1{a_2 + \frac1{\ddots }}} = [a_0, a_1, \ldots , a_ n, \ldots ] = \alpha$, если $\lim \limits _{n\to \infty } [a_0, \ldots , a_ n] = \alpha$.

Наоборот, пусть $\alpha \in \mathbb {R}_+$.

$\alpha = [\alpha ] + \{ \alpha \} = [\alpha ] + \frac1{\frac1{\{ \alpha \} }} = [\alpha ] + \frac1{ \left[\frac1{\{ \alpha \} }\right] +\left\{ \frac1{ \{ \alpha \} }\right\} } = \ldots = [a_0, \ldots , a_ n, \ldots ]$.

$\left| \alpha - \frac{p_{n-1}}{q_{n-1}} \right| \leqslant \left| \frac{p_ n}{q_ n} - \frac{p_{n-1}}{q_{n-1}} \right| =$ $\left| \frac{p_ n q_{n-1} - p_{n-1}q_ n}{q_ n q_{n-1}} \right| = \frac1{q_ n q_{n-1}} \leqslant \frac1{q_{n-1}^2}$, т.к $q_{n-1} \leqslant q_ n$.

Замечание. На самом деле $\left| \alpha - \frac{p_ n}{q_ n} \right| \leqslant \frac1{\sqrt 5 q_ n^2}$.

Рассмотрим произвольную функцию $\psi (q)\to \infty$ при $q\to \infty$. Скажем, что число $\alpha$ допускает диофантово приближение с точностью $\psi$, если существует бесконечно много несократимых дробей $\frac{p}{q}\colon$ $\left| \alpha - \frac{p}{q} \right| \leqslant \frac1{\psi (q)}$.

Теорема. $\forall \psi \ \exists \alpha$, которое допускает диофантово приближение с точностью $\psi$.

$\blacktriangle$
Давайте строить число $\alpha$ в виде бесконечной цепной дроби. Допустим, уже выбраны неполные частные $a_0, a_1, \ldots , a_ n$. Тогда корректно определены подходящие дроби $\frac{p_0}{q_0}, \ldots , \frac{p_ n}{q_ n}$. Мы знаем, что каким бы ни оказалось в итоге $\alpha$, $\left| \alpha - \frac{p_{n}}{q_{n}} \right| \leqslant \frac1{q_ n q_{n+1}} = \frac1{q_ n(a_{n+1} q_ n + q_{n-1})} \leqslant \frac1{q_ n a_{n+1}}$. Возьмём $a_{n+1}$ таким, чтобы выполнялось $q_ n a_{n+1} > \psi (q_ n)$. Тогда $\left| \alpha - \frac{p_{n}}{q_{n}} \right| \leqslant \frac1{\psi (q_ n)}$.
$\blacksquare$

Вывод. Чем быстрее растут неполные частные числа, записанного в виде бесконечной цепной дроби, тем лучше это число приближается рациональными дробями.

Пусть $\alpha _0 = [1, 1, \ldots ] = 1 + \frac1{[1, 1, \ldots ]}$.

Тогда $\alpha _0 = 1 + \frac1{\alpha _0} \Rightarrow \alpha _0^2 - \alpha _0 - 1 = 0 \Rightarrow \alpha _0 = \varphi = \frac{1 + \sqrt 5}{2}$ — "хуже всех приближается рациональным дробями". Более формально, верна следующая теорема:

Теорема (б/д). $\forall \varepsilon >0\colon \left| \alpha _0 - \frac{p}{q} \right| \leqslant \frac{1}{(\sqrt 5 + \varepsilon )q^2}$ имеет лишь конечное число решений в несократимых $\frac{p}{q}$.

Определение. Цепная дробь называется периодической, если $[a_0, \ldots , a_ k, \overline{a_{k+1}, \ldots , a_{m}}]$.

Утверждение. Если дробь периодическая, то соответствующее число является корнем некоторого квадратного уравнения.

$\blacktriangle$
$\alpha := [\overline{a_{k+1}, \ldots , a_{m}}]$.

$\alpha = a_{k+1} + \frac1{a_{k+2} + \frac1{a_ m + \frac{\ddots 1}\alpha }} = \frac{c_1\alpha + c_2}{b_1\alpha + b_2}$.

$\beta = a_0 + \frac1{a_1 + \frac1{a_ k + \frac{\ddots 1}\alpha }}$
$\blacksquare$

Теорема (б/д). Дробь периодическая $\iff$ соответствующее число является квадратичной иррациональностью.

Проблема (открытая). Что будет, если $\alpha$ — кубическая иррациональность.

Определение. Число называется алгебраическим, если оно является корнем некоторого многочлена с рациональными коэффициентами. Число называется алгебраическим порядка $k$, если многочлен минимально степени, корнем которого служит это число, имеет степень $k$.

Определение. Число называется трансцендентным, если оно не является алгебраическим.

$e, \pi , e^\pi$ — трансцендентны.

$e + \pi , e-\pi , e\pi$ — неизвестно.

Теорема (Лиувилль). Пусть $\alpha$ — алгебраическое число степени $n$. Тогда $\exists c = c(\alpha )$, что неравенство $\left| \alpha -\frac{p}{q} \right| \leqslant \frac{c}{q^ n}$ неразрешимо для рациональных $\frac{p}{q}$.

Возьмём такое $\alpha$, что для бесконечно многих $\frac{p}{q}$ выполнено $\left| \alpha -\frac{p}{q} \right| \leqslant \frac1{e^ q} =: \frac1{\psi (q)}$.
Тогда $\alpha$ — трансцендентно.

Доказательство: Предположим, что $\alpha$ алгебраическое $n$-ой степени. Тогда по т. Лиувилля $\forall p, q \left| \alpha -\frac{p}{q} \right| > \frac{c}{q^ n}$. Однако мы знаем, что $\left| \alpha -\frac{p}{q} \right| \leqslant \frac1{e^ q}$ для бесконечно многих $p, q \Rightarrow$ $\alpha$ — трансцендентное.

Интересные факты б/д.

Теорема (Гельфанд). Пусть $\alpha , \beta$ — такие комплексные алгебраические числа, что $\alpha \notin \{ 0, 1\} , \beta$ — иррациональное ($i$ — иррациональное). Тогда $\alpha ^\beta$ — трансцендентно.

Следствие. $e^\pi$ — трансцендентно.

$\blacktriangle$
Предположим $e^\pi$ — алгебраическое, $\alpha := e^\pi , \beta := i$. Тогда $\alpha ^\beta = e^{\pi i} = -1$ — трансцендентно. 
$\blacksquare$

Мы знаем, что $\left| \alpha -\frac{p}{q} \right| \leqslant \frac1{\sqrt 5 q^2}$, но $\exists \alpha \colon \left| \alpha -\frac{p}{q} \right| > \frac1{(\sqrt 5+\varepsilon )q^2}$.

Если выкинуть все такие числа, то будет верна оценка $\left| \alpha -\frac{p}{q} \right| \leqslant \frac1{\sqrt 8 q^2}$. Затем будет $\frac{5}{\sqrt {220}}$.

Последовательность $\sqrt 5, \sqrt 8, \frac{\sqrt {220}}5, \ldots \to 3$. Эта последовательность называется лучём Холла.

Гипотеза Заремба (Бахвалова-Коробова). Для любого $p$ существует $a\in \{ 1, 2, \ldots , p-1\}$ такое, что все неполные частные дроби $\frac{a}{p}$ не превосходят 5.

Геометрия чисел

Теорема (Минковский). Пусть $\Omega \subset \mathbb {R}^ n$. Пусть $\Omega$ выпукла (т.е. $\forall \bar x, \bar y \in \Omega \colon$ отрезок $\bar x\bar y\in \Omega$), $\Omega$ симметрична относительно начала координат, Vol $\Omega > 2^ n$. Тогда $\Omega$ содержит нетривиальную целую точку.

$\blacktriangle$
$\mathbb {Z}^ n$ — все целые точки в $\mathbb {R}^ n$. Рассмотрим $\frac1p\mathbb {Z}^ n, p\in \mathbb {N}$.

$N_ p := |\Omega \cap \frac1p\mathbb {Z}^ n|$.

$\frac{N_ p}{p^ n} \to \mathop {\mathrm{Vol}} \Omega > 2^ n$.

Значит, $\exists p\in \mathbb {N}\colon \frac{N_ p}{p^ n} > 2^ n$. $N_ p > (2p)^ n$.

Пусть $a = (\frac{a_1}{p}, \ldots , \frac{a_ n}{p}), b = (\frac{b_1}{p}, \ldots , \frac{b_ n}{p}) \in \frac1p\mathbb {Z}^ p$.

Скажем, что $a\equiv b$, если $\forall i\ a_ i\equiv b_ i\ (2p)$.

Всего различных точек $(2p)^ n$.

По принципу Дирихле, $\exists a, b\in \Omega \cap \frac1p\mathbb {Z}^ n\colon a\equiv b$, но $a\neq b$.

Рассмотрим точку $\frac{a-b}{2}$ $b\in \Omega \Rightarrow -b\in \Omega \Rightarrow$ $\frac{a-b}{2}\in \Omega$, $\frac{a-b}{2}\neq 0$. $\frac{a-b}{2} = \left( \frac{a_1-b_1}{2p}, \ldots , \frac{a_ n-b_ n}{2p} \right)$.
$\blacksquare$

Теорема (дополненная Минковского). То же самое + $\Omega$ — замкнута, $\mathop {\mathrm{Vol}} \Omega \geqslant 2^ n$.

Доказательство т. Дирихле через т. Минковского.

Рассмотрим $Q\in \mathbb {N}$. Рассмотрим $\Omega = \{ (x, y)\in \mathbb {R}^2\colon |\alpha x-y|\leqslant \frac1Q, |x|\leqslant Q\}$. Это параллелограмм, одна из сторон параллельна прямой $y=\alpha x$. Он замкнут, выпуклый, симметричен, его площадь равна 4.

Тогда в нём есть точка с целыми координатам $(p, q)$, $|q| \leqslant Q, |\alpha q-p|\leqslant \frac1Q$.

$\left| \alpha -\frac{p}{q} \right| \leqslant \frac1{qQ} \leqslant \frac1{q^2}$.

Определение. Пусть в $\mathbb {R}^ n$ дан какой-то базис $\bar e_1, \ldots , \bar e_ n$, который порождает всё пространство. Тогда множество $\Lambda = \{ \bar x = a_1\bar e_1 + \ldots + a_ n\bar e_ n, a_ i\in \mathbb {Z}\}$ называется решёткой.

$\det \Lambda$ — объём (неориентированный) ячейки решётки.

Теорема (Минковского для произвольных решёток). Пусть $\Lambda \subset \mathbb {R}^ n, \Omega \subset \mathbb {R}^ n\colon$ выпукла, центрально симметрична, её объём больше $2^ n\det \Lambda$. Тогда $(\Omega \cap \Lambda ) \backslash \{ 0\} \neq \varnothing$.

Критический определитель $\Delta (\Omega ) := \inf \{ \det \Lambda \colon (\Omega \cap \Lambda )\backslash \{ 0\} =\varnothing \}$.

Эквивалентная формулировка для произвольных решёток. $\Omega$ — выпукла, симметрична. Тогда $\frac{\mathop {\mathrm{Vol}} \Omega }{\Delta (\Omega )} \leqslant 2^ n$.

Предположим, что $\frac{\mathop {\mathrm{Vol}} \Omega }{\Delta (\Omega )}>2^ n \Rightarrow$ $\mathop {\mathrm{Vol}} \Omega > 2^ n\Delta (\Omega ) \Rightarrow$ $\exists \Lambda \colon (\Omega \cap \Lambda )\backslash \{ 0\} = \varnothing$ и $\mathop {\mathrm{Vol}} \Omega > 2^ n\det \Lambda$. Противоречие.

Теорема (б/д, Минковский-Главка, 1945). Пусть $\Omega$ измеримо, тогда $\frac{\mathop {\mathrm{Vol}} \Omega }{\Delta (\Omega )}\geqslant 1$.

Оценка улучшена с $1$ до $cn, c>0$.

Задача. Найти объём $n$-мерного октаэдра ($\{ \bar x\colon |x_1| +\ldots + |x_ n| \leqslant 1\}$).