TR-2001-25
Simultaneous Diophantine Approximation with Excluded Prime
Daniel Stefankovic. 30 June, 2001.
Communicated by Laszlo Babai.
Abstract
Given real numbers $\al_1,\dots,\al_n$, a simultaneous diophantine $\eps$-approximation is a sequence of integers $P_1,\dots,P_n,Q$ such that $Q>0$ and for all $j\in\{1,\dots,n\}$, $|Q\al_j-P_j|\leq\eps$. A simultaneous diophantine approximation is said to exclude the prime $p$ if $Q$ is not divisible by $p$. Given real numbers $\al_1,\dots,\al_n$, a prime $p$ and $\eps>0$ we show that at least one of the following holds \begin{description} \item[(a)] there is a simultaneous diophantine $\eps$-approximation which excludes $p$, or \item[(b)] there exist $a_1,\dots,a_n\in\intg$ such that $\sum a_j\al_j=1/p+t,\ t\in\intg$ and $\sum |a_j|\leq n^{3/2}/\eps$. \end{description} Note that in case (b) the $a_j$ witness that there is no simultaneous diophantine $\eps/(n^{3/2}p)$-approximation excluding $p$.We generalize the result to simultaneous diophantine $\eps$-approximations excluding several primes.
We also consider the algorithmic problem of finding, in polynomial time, a simultaneous diophantine $\eps$-approximation excluding a set of primes.
Original Document
The original document is available in Postscript (uploaded 30 June, 2001 by Dustin Mitchell).
Additional Document Formats
The document is also available in DVI (uploaded 30 June, 2001 by Dustin Mitchell) and PDF (uploaded 30 June, 2001 by Dustin Mitchell).
NOTE: The author warrants that these additional documents are identical with the originial to the extent permitted by the translation between the various formats. However, the webmaster has made no effort to verify this claim. If the authenticity of the document is an issue, please always refer to the "Original document." If you find significant alterations, please report to webmaster@cs.uchicago.edu.