Dirichlet's approximation theorem: Difference between revisions

Revision as of 15:33, 19 January 2025

Latest revision as of 15:35, 25 August 2025

(6 intermediate revisions by 5 users not shown)

Line 7:

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

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

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

Line 15:

==Simultaneous version==

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^d</math> such that <math>\left|\alpha_i-\frac{p_i}q \right| \le \frac1{qN^{1/d}}.</math><ref>Schmidt, p. 27 Theorem 1A1B</ref>

==Method of proof==

Line 22:

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>nN</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>.

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:

Line 58:

{{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|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}}</ref>

==See also==