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

В чисел теории теорема Дирихле о диофантовом приближении , также называемая аппроксимационной теоремой Дирихле , утверждает, что для любых действительных чисел $\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}}}.$ ^{[ нужна ссылка ]}

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

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

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

Схема доказательства : Пусть $\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) Адриен-Мари Лежандр выводит необходимое и достаточное условие того, что рациональное число сходится к непрерывной дроби данного действительного числа. ^{[ 3 ]} Следствием этого критерия, часто называемого теоремой Лежандра при изучении цепных дробей, является следующее: ^{[ 4 ]}

Теорема . Если α — действительное число, а 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.^[5]

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 [a₀; a₁, ..., a_n], 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 a_n = 1 and one where a_n ≠ 1), we may choose n to be even. (In the case where α < p/q, we would choose n to be odd.)

Let p₀/q₀, ..., p_n/q_n = 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 p_n_-1 q_n - p_n q_n_-1 = (-1)ⁿ and that n is even.

Now, this equation implies that α = [a₀; a₁, ..., a_n, ω]. Since the fact that 0 < θ < 1/2 implies that ω > 1, we conclude that the continued fraction expansion of α must be [a₀; a₁, ..., a_n, b₀, b₁, ...], where [b₀; b₁, ...] is the continued fraction expansion of ω, and therefore that p_n/q_n = p/q is a convergent of the continued fraction of α.

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

См. также

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

Примечания

^ http://jeff560.tripod.com/p.html для ряда исторических ссылок.
^ «Теорема Дирихле» , Математическая энциклопедия , EMS Press , 2001 [1994]
^ Лежандр, Адриен-Мари (1798). Очерк теории чисел (на французском языке). Париж: Дюпра. стр. 27–29.
^ Барболози, Доминик; Ягер, Хендрик (1994). «Об одной теореме Лежандра в теории цепных дробей» . Journal de Théorie des Nombres de Bordeaux . 6 (1): 81–94 – через JSTOR.
^ Харди, штат Джорджия ; Райт, Э.М. (1938). Введение в теорию чисел . Лондон: Издательство Оксфордского университета . стр. 140–141, 153.
^ Винер, Майкл Дж. (1990). «Криптоанализ коротких секретных показателей RSA» . Транзакции IEEE по теории информации . 36 (3): 553–558 – через IEEE.

Ссылки

Шмидт, Вольфганг М (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 .

[1] ttp://jeff560.tripod.com/p.html для ряда исторических ссылок.

[2] «Теорема Дирихле» , Математическая энциклопедия , EMS Press , 2001 [1994]

[3] Лежандр, Адриен-Мари (1798). Очерк теории чисел (на французском языке). Париж: Дюпра. стр. 27–29.

[4] Барболози, Доминик; Ягер, Хендрик (1994). «Об одной теореме Лежандра в теории цепных дробей» . Journal de Théorie des Nombres de Bordeaux . 6 (1): 81–94 – через JSTOR.

[5] Харди, штат Джорджия ; Райт, Э.М. (1938). Введение в теорию чисел . Лондон: Издательство Оксфордского университета . стр. 140–141, 153.

[6] Винер, Майкл Дж. (1990). «Криптоанализ коротких секретных показателей RSA» . Транзакции IEEE по теории информации . 36 (3): 553–558 – через IEEE.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[5]

[ 6 ]