Аппроксимационная теорема Дирихле

В чисел теории теорема Дирихле о диофантовом приближении , также называемая аппроксимационной теоремой Дирихле , утверждает, что для любых действительных чисел $\alpha$ и $N$, с $1\leq N$, существуют целые числа $p$ и $q$ такой, что $1\leq q\leq N$ и

$\left|q\alpha -p\right|\leq {\frac {1}{\lfloor N\rfloor +1}}<{\frac {1}{N}}.$

Здесь $\lfloor N\rfloor$ представляет собой часть целую $N$. Это фундаментальный результат диофантова аппроксимации , показывающий, что любое действительное число имеет последовательность хороших рациональных приближений: фактически непосредственным следствием является то, что для данного иррационального α неравенство

$0<\left|\alpha -{\frac {p}{q}}\right|<{\frac {1}{q^{2}}}$

удовлетворяется бесконечно многими целыми числами p и q . Это показывает, что любое иррациональное число имеет меру иррациональности не менее 2.

Теорема Туэ–Зигеля–Рота гласит, что для алгебраических иррациональных чисел показатель степени 2 в следствии аппроксимационной теоремы Дирихле — это лучшее, что мы можем сделать: такие числа не могут быть аппроксимированы никаким показателем степени, большим 2. Теорема Туэ–Зигеля–Рота Теорема Рота использует передовые методы теории чисел, но многие более простые числа, такие как золотое сечение, $(1+{\sqrt {5}})/2$ Гораздо легче проверить, что она неприблизима за пределами показателя 2.

Одновременная версия

Одновременная версия аппроксимационной теоремы Дирихле утверждает, что данные действительные числа $\alpha _{1},\ldots ,\alpha _{d}$ и натуральное число $N$ тогда есть целые числа $p_{1},\ldots ,p_{d},q\in \mathbb {Z} ,1\leq q\leq N$ такой, что $\left|\alpha _{i}-{\frac {p_{i}}{q}}\right|\leq {\frac {1}{qN^{1/d}}}.$

Метод доказательства

Доказательство по принципу «ячейки».

Эта теорема является следствием принципа «ячейки» . Питер Густав Лежен Дирихле, доказавший этот результат, использовал тот же принцип в других контекстах (например, уравнение Пелла ) и, назвав этот принцип (на немецком языке), популяризировал его использование, хотя его статус в учебниках появился позже. Метод распространяется на одновременное приближение.

Схема доказательства : Пусть $\alpha$ быть иррациональным числом и $n$ быть целым числом. Для каждого $k=0,1,...,N$ мы можем написать $k\alpha =m_{k}+x_{k}$ такой, что $m_{k}$ является целым числом и $0\leq x_{k}<1$. Можно разделить интервал $[0,1)$ в $N$ меньшие интервалы измерения ${\frac {1}{N}}$. Теперь у нас есть $N+1$ цифры $x_{0},x_{1},...,x_{N}$ и $N$ интервалы. Следовательно, по принципу «ячейки» как минимум два из них находятся в одном и том же интервале. Мы можем назвать их $x_{i},x_{j}$ такой, что $i<j$. Сейчас:

$|(j-i)\alpha -(m_{j}-m_{i})|=|j\alpha -m_{j}-(i\alpha -m_{i})|=|x_{j}-x_{i}|<{\frac {1}{N}}$

Разделив обе части на $j-i$ приведет к:

$\left|\alpha -{\frac {m_{j}-m_{i}}{j-i}}\right|<{\frac {1}{(j-i)N}}\leq {\frac {1}{\left(j-i\right)^{2}}}$

И мы доказали теорему.

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

Другое простое доказательство аппроксимационной теоремы Дирихле основано на теореме Минковского, примененной к множеству

$S=\left\{(x,y)\in \mathbb {R} ^{2}:-N-{\frac {1}{2}}\leq x\leq N+{\frac {1}{2}},\vert \alpha x-y\vert \leq {\frac {1}{N}}\right\}.$

Поскольку объем $S$ больше, чем $4$, теорема Минковского устанавливает существование нетривиальной точки с целыми координатами. Это доказательство естественным образом распространяется на одновременные приближения, рассматривая множество

$S=\left\{(x,y_{1},\dots ,y_{d})\in \mathbb {R} ^{1+d}:-N-{\frac {1}{2}}\leq x\leq N+{\frac {1}{2}},|\alpha _{i}x-y_{i}|\leq {\frac {1}{N^{1/d}}}\right\}.$

Связанные теоремы

Теорема Лежандра о цепных дробях

См. Также: Непрерывная дробь

В своем «Essai sur la theorie des nombres» (1798) Адриен-Мари Лежандр выводит необходимое и достаточное условие того, что рациональное число сходится к непрерывной дроби данного действительного числа. Следствием этого критерия, часто называемого теоремой Лежандра при изучении цепных дробей, является следующее:

Теорема . Если α — действительное число, а p , q — положительные целые числа такие, что $\left|\alpha -{\frac {p}{q}}\right|<{\frac {1}{2q^{2}}}$, то p / q является подходящей дробью цепной дроби α .

показывать Доказательство

Proof. We follow the proof given in An Introduction to the Theory of Numbers by G. H. Hardy and E. M. Wright. Suppose α, p, q are such that $\left|\alpha -{\frac {p}{q}}\right|<{\frac {1}{2q^{2}}}$, and assume that α > p/q. Then we may write $\alpha -{\frac {p}{q}}={\frac {\theta }{q^{2}}}$, where 0 < θ < 1/2. We write p/q as a finite continued fraction [a0; a1, ..., an], where due to the fact that each rational number has two distinct representations as finite continued fractions differing in length by one (namely, one where an = 1 and one where an ≠ 1), we may choose n to be even. (In the case where α < p/q, we would choose n to be odd.) Let p0/q0, ..., pn/qn = p/q be the convergents of this continued fraction expansion. Set $\omega :={\frac {1}{\theta }}-{\frac {q_{n-1}}{q_{n}}}$, so that $\theta ={\frac {q_{n}}{q_{n-1}+\omega q_{n}}}$ and thus,$$\alpha ={\frac {p}{q}}+{\frac {\theta }{q^{2}}}={\frac {p_{n}}{q_{n}}}+{\frac {1}{q_{n}(q_{n-1}+\omega q_{n})}}={\frac {(p_{n}q_{n-1}+1)+\omega p_{n}q_{n}}{q_{n}(q_{n-1}+\omega q_{n})}}={\frac {p_{n-1}q_{n}+\omega p_{n}q_{n}}{q_{n}(q_{n-1}+\omega q_{n})}}={\frac {p_{n-1}+\omega p_{n}}{q_{n-1}+\omega q_{n}}},$$ where we have used the fact that pn-1 qn - pn qn-1 = (-1)n and that n is even. Now, this equation implies that α = [a0; a1, ..., an, ω]. Since the fact that 0 < θ < 1/2 implies that ω > 1, we conclude that the continued fraction expansion of α must be [a0; a1, ..., an, b0, b1, ...], where [b0; b1, ...] is the continued fraction expansion of ω, and therefore that pn/qn = p/q is a convergent of the continued fraction of α.

Эта теорема лежит в основе атаки Винера — полиномиального использования криптографического протокола RSA , которое может произойти из-за необдуманного выбора открытого и закрытого ключей (в частности, эта атака успешна, если простые факторы открытого ключа n = pq удовлетворяют p < q < 2 p и закрытый ключ d меньше (1/3) n ^1/4 ).

См. также

• Теорема Дирихле об арифметических прогрессиях
• Теорема Гурвица (теория чисел)
• Хайльброннский набор
• Теорема Кронекера (обобщение теоремы Дирихле)

Ссылки

• Шмидт, Вольфганг М (1980). Диофантово приближение . Конспект лекций по математике. Том. 785. Спрингер. дои : 10.1007/978-3-540-38645-2 . ISBN  978-3-540-38645-2 .
• Шмидт, Вольфганг М. (1991). Диофантовые приближения и диофантовы уравнения . Серия книг «Конспекты лекций по математике». Том. 1467. Спрингер. дои : 10.1007/BFb0098246 . ISBN  978-3-540-47374-9 . S2CID   118143570 .

Внешние ссылки

• Теорема аппроксимации Дирихле в PlanetMath .