Диофатновы приближения. Цепные дроби
Подробней про цепные дроби можно почитать в книге Хинчина А.Я. "Цепные дроби".
Пусть дано иррациональное число $\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\} $).