Dirichlet's approximation theorem: Difference between revisions

Revision as of 19:48, 31 August 2014

Latest revision as of 15:35, 25 August 2025

(47 intermediate revisions by 37 users not shown)

Line 1:

{{short description|Concept in number theory}}

In [[number theory]], '''Dirichlet's theorem on [[Diophantine approximation]]''', also called '''Dirichlet's approximation theorem''', states that for any [[real numbernumbers]] α<math> \alpha </math> and any<math> [[positiveN integer]]</math>, with <math> 1 \leq ''N'' </math>, there existsexist integers ''<math> p'' </math> and ''<math> q'' </math> such that <math> 1 ≤\leq ''q'' ≤\leq ''N'' </math> and

:<math> \left | q \alpha -p \right | \leleq \frac{1}{\lfloor N\rfloor+1} < \frac{1}{N}. </math>

Here <math> \lfloor N\rfloor </math> represents the [[integer part]] of <math> N </math>.

This is a foundationalfundamental result in [[Diophantine approximation]], showing that any real number has a sequence of good rational approximations: in fact an immediate consequence is that for a given irrational α, the inequality

:<math> \left | \alpha -\frac{p}{q} \right | < \frac{1}{q^2} </math>

is satisfied by infinitely many integers ''p'' and ''q''. This corollary also shows that theany [[Thue–Siegel–Rothirrational theorem]],number a result in the other direction, provides essentially the tightest possible bound, in the sense that the limits on rational approximation ofhas [[algebraicirrationality numbermeasure#irrationality_exponent|irrationality exponent]]s cannot be improved by lowering the exponent 2 + &epsilon;at beyondleast 2.

The [[Thue–Siegel–Roth theorem]] says that, for algebraic irrational numbers, the exponent of 2 in the corollary to Dirichlet’s approximation theorem is the best we can do: such numbers cannot be approximated by any exponent greater than 2. The Thue–Siegel–Roth theorem uses advanced techniques of number theory, but many simpler numbers such as the [[golden ratio]] <math>(1+\sqrt{5})/2</math> can be much more easily verified to be inapproximable beyond exponent 2.

==Simultaneous Version==

==Simultaneous Versionversion==

The simultaneous version of the Dirichlet's approximation theorem states that given real numbers <math>\alpha_1, ..., \alpha_d</math> and a natural number <math>N</math> then there are integers <math>p_1, ..., p_d, q\in\Z,1\le q\leq N</math> such that <math>\left|\alpha_i-\frac{p_i}q\right|\le\frac1{qN^{1/d}}.</math>

The simultaneous version of the Dirichlet's approximation theorem states that given real numbers <math>\alpha_1, ...\ldots, \alpha_d</math> and a natural number <math>N</math> then there are integers <math>p_1, ...\ldots, p_d, q\in\Z,1\le q\leq N</math> such that <math>\left|\alpha_i-\frac{p_i}q \right| \le \frac1{qN^{1/d}}.</math><ref>Schmidt, p. 27 Theorem 1B</ref>

==Method of proof==

===Proof by the pigeonhole principle===

This theorem is a consequence of the [[pigeonhole principle]]. [[Peter Gustav Lejeune Dirichlet]] who proved the result used the same principle in other contexts (for example, the [[Pell equation]]) and by naming the principle (in German) popularized its use, though its status in textbook terms comes later.<ref>http://jeff560.tripod.com/p.html for a number of historical references.</ref> The method extends to simultaneous approximation.<ref>{{Springer|id=d/d032940|title=Dirichlet theorem}}</ref>

'''Proof outline''': Let <math>\alpha</math> be an irrational number and <math>N</math> be an integer. For every <math>k=0, 1, ..., N</math> we can write <math>k\alpha=m_k + x_k</math> such that <math>m_k</math> is an integer and <math>0\le x_k <1</math>.

Another simple proof of the Dirichlet's approximation theorem is based on [[Minkowski's theorem|Minkowski's Theorem]] applied to the set <math>S = \{ (x,y) \in \R^2; -N-\frac{1}{2} \leq x \leq N+\frac{1}{2}, \vert \alpha x - y \vert \leq \frac{1}{N} \} </math>. Since the volume of <math>S</math> is greater than <math>4</math>, [[Minkowski's theorem|Minkowski's Theorem]] establishes the existence of a non-trivial point with integral coordinates. This proof extends naturally to simultaneous approximations by considering the set: <math>S = \{ (x,y_1, \dots, y_d) \in \R^{1+d}; -N-\frac{1}{2} \le x \le N+\frac{1}{2}, |\alpha x - y_i| \le \frac{1}{N^{1/d}} \} </math>.

One can divide the interval <math>[0, 1)</math> into <math>N</math> smaller intervals of measure <math>\frac{1}{N}</math>. Now, we have <math>N+1</math> numbers <math>x_0,x_1,...,x_N</math> and <math>N</math> intervals. Therefore, by the pigeonhole principle, at least two of them are in the same interval. We can call those <math>x_i,x_j</math> such that <math>i < j</math>. Now:

: <math>|(j-i)\alpha-(m_j-m_i)|=|j\alpha-m_j-(i\alpha-m_i)|=|x_j-x_i|< \frac{1}{N}</math>

Dividing both sides by <math>j-i</math> will result in:

: <math>\left|\alpha-\frac{m_j-m_i}{j-i}\right|< \frac{1}{(j-i)N}\le \frac{1}{\left(j-i\right)^2}</math>

And we proved the theorem.

===Proof by Minkowski's theorem===

Another simple proof of the Dirichlet's approximation theorem is based on [[Minkowski's theorem]] applied to the set

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

Since the volume of <math>S</math> is greater than <math>4</math>, [[Minkowski's theorem]] establishes the existence of a non-trivial point with integral coordinates. This proof extends naturally to simultaneous approximations by considering the set

: <math>S = \left\{ (x,y_1, \dots, y_d) \in \R^{1+d} : -N-\frac{1}{2} \le x \le N+\frac{1}{2}, |\alpha_i x - y_i| \le \frac{1}{N^{1/d}} \right\}. </math>

== Related theorems ==

=== Legendre's theorem on continued fractions ===

{{see also|Simple continued fraction}}

In his ''Essai sur la théorie des nombres'' (1798), [[Adrien-Marie Legendre]] derives a necessary and sufficient condition for a rational number to be a convergent of the [[simple continued fraction]] of a given real number.<ref>{{cite book|last=Legendre|first=Adrien-Marie|author-link=Adrien-Marie Legendre|title=Essai sur la théorie des nombres|date=1798|publisher=Duprat|___location=Paris|publication-date=1798|pages=27–29|language=fr}}</ref> A consequence of this criterion, often called '''Legendre's theorem''' within the study of continued fractions, is as follows:<ref>{{cite journal|last1=Barbolosi|first1=Dominique|last2=Jager|first2=Hendrik|date=1994|title=On a theorem of Legendre in the theory of continued fractions|url=https://www.jstor.org/stable/26273940|journal=[[Journal de Théorie des Nombres de Bordeaux]]|volume=6|issue=1|pages=81–94|doi=10.5802/jtnb.106 |jstor=26273940 }}</ref>

'''Theorem'''. If ''α'' is a real number and ''p'', ''q'' are positive integers such that <math>\left|\alpha - \frac{p}{q}\right| < \frac{1}{2q^2}</math>, then ''p''/''q'' is a convergent of the continued fraction of ''α''.

{{collapse top|title = Proof}}

'''Proof'''. We follow the proof given in ''[[An Introduction to the Theory of Numbers]]'' by [[G. H. Hardy]] and [[E. M. Wright]].<ref>{{cite book|last1=Hardy|first1=G. H.|author-link1=G. H. Hardy|last2=Wright|first2=E. M.|author-link2=E. M. Wright|title=An Introduction to the Theory of Numbers|title-link=An Introduction to the Theory of Numbers|publisher=[[Oxford University Press]]|year=1938|isbn=|___location=London|publication-date=1938|pages=140–141, 153|language=en}}</ref>

Suppose ''α'', ''p'', ''q'' are such that <math>\left|\alpha - \frac{p}{q}\right| < \frac{1}{2q^2}</math>, and assume that ''α'' > ''p''/''q''. Then we may write <math>\alpha - \frac{p}{q} = \frac{\theta}{q^2}</math>, 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 <math>\omega := \frac{1}{\theta} - \frac{q_{n-1}}{q_n}</math>, so that <math>\theta = \frac{q_n}{q_{n-1} + \omega q_n}</math> and thus,<math display="block">\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}, </math> where we have used the fact that ''p_n''₋₁ ''q_n'' - ''p_n'' ''q_n''₋₁ = (-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 ''α''.

{{collapse bottom}}

This theorem forms the basis for [[Wiener's attack]], a polynomial-time exploit of the [[RSA (cryptosystem)|RSA cryptographic protocol]] that can occur for an injudicious choice of public and private keys (specifically, this attack succeeds if the prime factors of the public key ''n'' = ''pq'' satisfy ''p'' < ''q'' < 2''p'' and the private key ''d'' is less than (1/3)''n''^1/4).<ref>{{cite journal|last=Wiener|first=Michael J.|date=1990|title=Cryptanalysis of short RSA secret exponents|journal=[[IEEE Transactions on Information Theory]]|volume=36|issue=3|pages=553–558|doi=10.1109/18.54902 }}</ref>

==See also==

*[[Dirichlet's theorem on arithmetic progressions]]

*[[Hurwitz's theorem (number theory)]]

*[[Heilbronn set]]

*[[Kronecker's theorem]] (generalization of Dirichlet's theorem)

==Notes==

Line 26 ⟶ 70:

==References==

*{{cite [[book |authorlink=Wolfgang M. Schmidt]]. ''|first=Wolfgang M |last=Schmidt |title=Diophantine approximation''.Approximation |publisher=Springer |series=Lecture Notes in Mathematics |volume=785. Springer. (|year=1980 [1996|isbn=978-3-540-38645-2 with minor corrections])|doi=10.1007/978-3-540-38645-2}}

*{{cite book |first=Wolfgang M. |last=Schmidt.'' |title=Diophantine approximationsApproximations and Diophantine equations'',Equations |publisher=Springer |series=Lecture Notes in Mathematics, Springerbook Verlagseries |volume=1467 |year=1991 |isbn=978-3-540-47374-9 |doi=10.1007/BFb0098246|s2cid=118143570 2000}}

==External links==