Dirichlet's approximation theorem

In number theory, Dirichlet's theorem on Diophantine approximation, also called Dirichlet's approximation theorem, states that for any real numbers $\alpha$ and $N$ , with $1 \leq N$ , there exist integers $p$ and $q$ such that $1 \leq q \leq N$ and

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

Here $\lfloor N\rfloor$ represents the integer part of $N$ .

This is a fundamental 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

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

is satisfied by infinitely many integers p and q. This shows that any irrational number has irrationality measure at least 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 $(1+\sqrt{5})/2$ can be much more easily verified to be inapproximable beyond exponent 2.

Simultaneous version

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

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.http://jeff560.tripod.com/p.html for a number of historical references. The method extends to simultaneous approximation.{{Springer|id=d/d032940|title=Dirichlet theorem}}

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

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

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

Dividing both sides by $j-i$ will result in:

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

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

: $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\}.$

Since the volume of $S$ is greater than $4$ , 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

: $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\}.$

Related theorems

= Legendre's theorem on continued fractions =

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.{{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}} A consequence of this criterion, often called Legendre's theorem within the study of continued fractions, is as follows:{{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 }}

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

Proof. We follow the proof given in An Introduction to the Theory of Numbers by G. H. Hardy and E. M. Wright.{{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}}

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₋₁ 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 α.

This theorem forms the basis for Wiener's attack, a polynomial-time exploit of the 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 < 2p and the private key d is less than (1/3)n^1/4).{{cite journal|last=Wiener|first=Michael J.|date=1990|title=Cryptanalysis of short RSA secret exponents|url=https://ieeexplore.ieee.org/document/54902|journal=IEEE Transactions on Information Theory|volume=36|issue=3|pages=553–558|doi=10.1109/18.54902 |via=IEEE}}

Notes

References

{{cite book |authorlink=Wolfgang M. Schmidt |first=Wolfgang M |last=Schmidt |title=Diophantine Approximation |publisher=Springer |series=Lecture Notes in Mathematics |volume=785 |year=1980 |isbn=978-3-540-38645-2 |doi=10.1007/978-3-540-38645-2}}
{{cite book |first=Wolfgang M. |last=Schmidt |title=Diophantine Approximations and Diophantine Equations |publisher=Springer |series=Lecture Notes in Mathematics book series |volume=1467 |year=1991 |isbn=978-3-540-47374-9 |doi=10.1007/BFb0098246|s2cid=118143570 }}

External links

{{PlanetMath|urlname=DirichletsApproximationTheorem|title=Dirichlet's Approximation Theorem}}

Category:Diophantine approximation

Category:Theorems in number theory