Dirichlet's approximation theorem

<h2 id="simultaneous-version">Simultaneous version</h2>
The simultaneous version of the Dirichlet's approximation theorem states that given real numbers 
 
 
 
 
 α
 
 1
 
 
 ,
 …
 ,
 
 α
 
 d
 
 
 
 
 {\displaystyle \alpha _{1},\ldots ,\alpha _{d}}
 
 and a natural number 
 
 
 
 N
 
 
 {\displaystyle N}
 
 then there are integers 
 
 
 
 
 p
 
 1
 
 
 ,
 …
 ,
 
 p
 
 d
 
 
 ,
 q
 ∈
 
 Z
 
 ,
 1
 ≤
 q
 ≤
 
 N
 
 d
 
 
 
 
 {\displaystyle p_{1},\ldots ,p_{d},q\in \mathbb {Z} ,1\leq q\leq N^{d}}
 
 such that 
 
 
 
 
 |
 
 
 α
 
 i
 
 
 −
 
 
 
 p
 
 i
 
 
 q
 
 
 
 |
 
 ≤
 
 
 1
 
 q
 N
 
 
 
 .
 
 
 {\displaystyle \left|\alpha _{i}-{\frac {p_{i}}{q}}\right|\leq {\frac {1}{qN}}.}
 
<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>

<h2 id="method-of-proof">Method of proof</h2>
<h3>Proof by the pigeonhole principle</h3>
This theorem is a consequence of the <a href="/facts/Pigeonhole_principle/hDks9p4n">pigeonhole principle</a>. <a href="/facts/Peter_Gustav_Lejeune_Dirichlet/b5UIU7Uy">Peter Gustav Lejeune Dirichlet</a> who proved the result used the same principle in other contexts (for example, the <a href="/facts/Pell_equation/n0ul61eQ">Pell equation</a>) and by naming the principle (in German) popularized its use, though its status in textbook terms comes later.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> The method extends to simultaneous approximation.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
Proof outline: Let 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
 be an irrational number and 
 
 
 
 N
 
 
 {\displaystyle N}
 
 be an integer. For every 
 
 
 
 k
 =
 0
 ,
 1
 ,
 .
 .
 .
 ,
 N
 
 
 {\displaystyle k=0,1,...,N}
 
 we can write 
 
 
 
 k
 α
 =
 
 m
 
 k
 
 
 +
 
 x
 
 k
 
 
 
 
 {\displaystyle k\alpha =m_{k}+x_{k}}
 
 such that 
 
 
 
 
 m
 
 k
 
 
 
 
 {\displaystyle m_{k}}
 
 is an integer and 
 
 
 
 0
 ≤
 
 x
 
 k
 
 
 <
 1
 
 
 {\displaystyle 0\leq x_{k}<1}
 
.
One can divide the interval 
 
 
 
 [
 0
 ,
 1
 )
 
 
 {\displaystyle [0,1)}
 
 into 
 
 
 
 N
 
 
 {\displaystyle N}
 
 smaller intervals of measure 
 
 
 
 
 
 1
 N
 
 
 
 
 {\displaystyle {\frac {1}{N}}}
 
. Now, we have 
 
 
 
 N
 +
 1
 
 
 {\displaystyle N+1}
 
 numbers 
 
 
 
 
 x
 
 0
 
 
 ,
 
 x
 
 1
 
 
 ,
 .
 .
 .
 ,
 
 x
 
 N
 
 
 
 
 {\displaystyle x_{0},x_{1},...,x_{N}}
 
 and 
 
 
 
 N
 
 
 {\displaystyle 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
 
 
 
 
 {\displaystyle x_{i},x_{j}}
 
 such that 
 
 
 
 i
 <
 j
 
 
 {\displaystyle i<j}
 
. Now:

|
 
 (
 j
 −
 i
 )
 α
 −
 (
 
 m
 
 j
 
 
 −
 
 m
 
 i
 
 
 )
 
 |
 
 =
 
 |
 
 j
 α
 −
 
 m
 
 j
 
 
 −
 (
 i
 α
 −
 
 m
 
 i
 
 
 )
 
 |
 
 =
 
 |
 
 
 x
 
 j
 
 
 −
 
 x
 
 i
 
 
 
 |
 
 <
 
 
 1
 N
 
 
 
 
 {\displaystyle |(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
 
 
 {\displaystyle j-i}
 
 will result in:

|
 
 α
 −
 
 
 
 
 m
 
 j
 
 
 −
 
 m
 
 i
 
 
 
 
 j
 −
 i
 
 
 
 
 |
 
 <
 
 
 1
 
 (
 j
 −
 i
 )
 N
 
 
 
 ≤
 
 
 1
 
 
 (
 
 j
 −
 i
 
 )
 
 
 2
 
 
 
 
 
 
 {\displaystyle \left|\alpha -{\frac {m_{j}-m_{i}}{j-i}}\right|<{\frac {1}{(j-i)N}}\leq {\frac {1}{\left(j-i\right)^{2}}}}

And we proved the theorem.

<h3>Proof by Minkowski's theorem</h3>
Another simple proof of the Dirichlet's approximation theorem is based on <a href="/facts/Minkowski%2527s_theorem/G2A8J5k6">Minkowski's theorem</a> applied to the set

S
        =
        
          {
          
            (
            x
            ,
            y
            )
            ∈
            
              
                R
              
              
                2
              
            
            :
            −
            N
            −
            
              
                1
                2
              
            
            ≤
            x
            ≤
            N
            +
            
              
                1
                2
              
            
            ,
            |
            α
            x
            −
            y
            |
            ≤
            
              
                1
                N
              
            
          
          }
        
        .
      
    
    {\displaystyle 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\}.}

Since the volume of 
 
 
 
 S
 
 
 {\displaystyle S}
 
 is greater than 
 
 
 
 4
 
 
 {\displaystyle 4}
 
, <a href="/facts/Minkowski%2527s_theorem/G2A8J5k6">Minkowski's theorem</a> establishes the existence of a non-trivial point with integral coordinates. This proof extends naturally to simultaneous approximations by considering the set

S
        =
        
          {
          
            (
            x
            ,
            
              y
              
                1
              
            
            ,
            …
            ,
            
              y
              
                d
              
            
            )
            ∈
            
              
                R
              
              
                1
                +
                d
              
            
            :
            −
            N
            −
            
              
                1
                2
              
            
            ≤
            x
            ≤
            N
            +
            
              
                1
                2
              
            
            ,
            
              |
            
            
              α
              
                i
              
            
            x
            −
            
              y
              
                i
              
            
            
              |
            
            ≤
            
              
                1
                
                  N
                  
                    1
                    
                      /
                    
                    d
                  
                
              
            
          
          }
        
        .
      
    
    {\displaystyle 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\}.}

<h2 id="related-theorems">Related theorems</h2>
<h3>Legendre's theorem on continued fractions</h3>
See also: <a href="/facts/Simple_continued_fraction/Wg1cMPxN">Simple continued fraction</a>
In his Essai sur la théorie des nombres (1798), <a href="/facts/Adrien-Marie_Legendre/2a7CAolM">Adrien-Marie Legendre</a> derives a necessary and sufficient condition for a rational number to be a convergent of the <a href="/facts/Simple_continued_fraction/Wg1cMPxN">simple continued fraction</a> of a given real number.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> A consequence of this criterion, often called Legendre's theorem within the study of continued fractions, is as follows:<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
Theorem. If α is a real number and p, q are positive integers such that 
 
 
 
 
 |
 
 α
 −
 
 
 p
 q
 
 
 
 |
 
 <
 
 
 1
 
 2
 
 q
 
 2
 
 
 
 
 
 
 
 {\displaystyle \left|\alpha -{\frac {p}{q}}\right|<{\frac {1}{2q^{2}}}}
 
, then p/q is a convergent of the continued fraction of α.

<table><tbody><tr><th>Proof</th></tr><tr><td>Proof. We follow the proof given in <a href="/facts/An_Introduction_to_the_Theory_of_Numbers/YNc01PUg">An Introduction to the Theory of Numbers</a> by <a href="/facts/G._H._Hardy/zBkDLb05">G. H. Hardy</a> and <a href="/facts/E._M._Wright/SS01ywc2">E. M. Wright</a>.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>Suppose α, p, q are such that | α − p q | < 1 2 q 2 {\displaystyle \left|\alpha -{\frac {p}{q}}\right|<{\frac {1}{2q^{2}}}} , and assume that α > p/q. Then we may write α − p q = θ q 2 {\displaystyle \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 ω := 1 θ − q n − 1 q n {\displaystyle \omega :={\frac {1}{\theta }}-{\frac {q_{n-1}}{q_{n}}}} , so that θ = q n q n − 1 + ω q n {\displaystyle \theta ={\frac {q_{n}}{q_{n-1}+\omega q_{n}}}} and thus, α = p q + θ q 2 = p n q n + 1 q n ( q n − 1 + ω q n ) = ( p n q n − 1 + 1 ) + ω p n q n q n ( q n − 1 + ω q n ) = p n − 1 q n + ω p n q n q n ( q n − 1 + ω q n ) = p n − 1 + ω p n q n − 1 + ω q n , {\displaystyle \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 α.</td></tr></tbody></table>
This theorem forms the basis for <a href="/facts/Wiener%2527s_attack/KNGgdNme">Wiener's attack</a>, a polynomial-time exploit of the <a href="/facts/RSA_(cryptosystem)/XTzyfHuq">RSA cryptographic protocol</a> 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)n1/4).<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Dirichlet%2527s_theorem_on_arithmetic_progressions/yFyJaE2d">Dirichlet's theorem on arithmetic progressions</a></li>
<li><a href="/facts/Hurwitz%2527s_theorem_(number_theory)/3A5n9xgF">Hurwitz's theorem (number theory)</a></li>
<li><a href="/facts/Heilbronn_set/uEtQ1Vu7">Heilbronn set</a></li>
<li><a href="/facts/Kronecker%2527s_theorem/Fbtxu3G8">Kronecker's theorem</a> (generalization of Dirichlet's theorem)</li></ul>
<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/Wolfgang_M._Schmidt/5uFcNFt5">Schmidt, Wolfgang M</a> (1980). Diophantine Approximation. Lecture Notes in Mathematics. Vol. 785. Springer. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-540-38645-2">10.1007/978-3-540-38645-2</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-38645-2.</li>
<li>Schmidt, Wolfgang M. (1991). Diophantine Approximations and Diophantine Equations. Lecture Notes in Mathematics book series. Vol. 1467. Springer. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBFb0098246">10.1007/BFb0098246</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-47374-9. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:118143570">118143570</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://planetmath.org/DirichletsApproximationTheorem">Dirichlet's Approximation Theorem</a> at <a href="/facts/PlanetMath/wphPCtLf">PlanetMath</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Schmidt, p. 27 Theorem 1A <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">http://jeff560.tripod.com/p.html for a number of historical references. <a href="http://jeff560.tripod.com/p.html" target="_blank">http://jeff560.tripod.com/p.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">"Dirichlet theorem", Encyclopedia of Mathematics, EMS Press, 2001 [1994] <a href="https://www.encyclopediaofmath.org/index.php?title=Dirichlet_theorem" target="_blank">https://www.encyclopediaofmath.org/index.php?title=Dirichlet_theorem</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Legendre, Adrien-Marie (1798). Essai sur la théorie des nombres (in French). Paris: Duprat. pp. 27–29. <a href="/wiki/Adrien-Marie_Legendre" target="_blank">/wiki/Adrien-Marie_Legendre</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Barbolosi, Dominique; Jager, Hendrik (1994). "On a theorem of Legendre in the theory of continued fractions". Journal de Théorie des Nombres de Bordeaux. 6 (1): 81–94. doi:10.5802/jtnb.106. JSTOR 26273940. <a href="https://www.jstor.org/stable/26273940" target="_blank">https://www.jstor.org/stable/26273940</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Hardy, G. H.; Wright, E. M. (1938). An Introduction to the Theory of Numbers. London: Oxford University Press. pp. 140–141, 153. <a href="/wiki/G._H._Hardy" target="_blank">/wiki/G._H._Hardy</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Wiener, Michael J. (1990). "Cryptanalysis of short RSA secret exponents". IEEE Transactions on Information Theory. 36 (3): 553–558. doi:10.1109/18.54902 – via IEEE. <a href="https://ieeexplore.ieee.org/document/54902" target="_blank">https://ieeexplore.ieee.org/document/54902</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
</ol>

Dirichlet's approximation theorem open-in-new

Dirichlet's approximation theorem