Teorema de aproximación de Dirichlet

Este teorema es consecuencia del principio del palomar . Peter Gustav Lejeune Dirichlet, quien demostró el resultado, utilizó el mismo principio en otros contextos (por ejemplo, la ecuación de Pell ) y, al nombrar el principio (en alemán), popularizó su uso, aunque su estatus en los libros de texto llegó más tarde. ^{[ 2 ]} El método se extiende a la aproximación simultánea. ^{[ 3 ]}

Esquema de la demostración : Sea${\displaystyle \alpha }$ser un número irracional y${\displaystyle N}$sea ​​un número entero. Para cada${\displaystyle k=0,1,...,N}$podemos escribir${\displaystyle k\alpha =m_{k}+x_{k}}$de tal manera que${\displaystyle m_{k}}$es un número entero y${\displaystyle 0\leq x_{k}<1}$Se puede dividir el intervalo${\displaystyle [0,1)}$en${\displaystyle N}$intervalos de medida más pequeños${\displaystyle {\frac {1}{N}}}$Ahora tenemos${\displaystyle N+1}$números${\displaystyle x_{0},x_{1},...,x_{N}}$y${\displaystyle N}$intervalos. Por lo tanto, según el principio del palomar, al menos dos de ellos están en el mismo intervalo. Podemos llamarlos${\displaystyle x_{i},x_{j}}$de tal manera que${\displaystyle i<j}$. Ahora:

${\displaystyle |(j-i)\alpha -(m_{j}-m_{i})|=|j\alpha -m_{j}-(i\alpha -m_{i})|=|x_{j}-x_{i}|<{\frac {1}{N}}}$

Dividiendo ambos lados por${\displaystyle j-i}$dará como resultado:

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

Y demostramos el teorema.

Otra demostración sencilla del teorema de aproximación de Dirichlet se basa en el teorema de Minkowski aplicado al conjunto

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

Dado que el volumen de${\displaystyle S}$es mayor que${\displaystyle 4}$El teorema de Minkowski establece la existencia de un punto no trivial con coordenadas enteras. Esta demostración se extiende naturalmente a aproximaciones simultáneas al considerar el conjunto

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

En su Ensayo sobre la teoría de los nombres (1798), Adrien-Marie Legendre deduce una condición necesaria y suficiente para que un número racional sea convergente de la fracción continua simple de un número real dado. ^{[ 4 ]} Una consecuencia de este criterio, a menudo llamado teorema de Legendre dentro del estudio de las fracciones continuas, es la siguiente: ^{[ 5 ]}

Teorema . Si α es un número real y p , q son enteros positivos tales que${\displaystyle \left|\alpha -{\frac {p}{q}}\right|<{\frac {1}{2q^{2}}}}$, entonces p / q es una convergente de la fracción continua de α .

Este teorema constituye la base del ataque de Wiener , una explotación en tiempo polinomial del protocolo criptográfico RSA que puede ocurrir por una elección imprudente de claves públicas y privadas (específicamente, este ataque tiene éxito si los factores primos de la clave pública n = pq satisfacen p < q < 2p y la clave privada d es menor que (1/3) n ^1/4 ). ^{[ 7 ]}