# 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).