Searching for an inhomogeneous diophantine approximation algorithm

2011-07-11T17:57:13Z

Given two nonzero real numbers $x$ and $y$ such that $y/x$ is irrational, a real number $z$ to be approximated, and a tolerance $\epsilon$, what is an algorithm that will provide coprime integers $a$ and $b$ such that $|ax + by - z| < \epsilon$?

Note that if the restriction that $a$ and $b$ be coprime is lifted, the problem becomes very simple. One possible algorithm is:

Find $a_1$ and $b_1$ such that $0 < a_1 x + b_1 y < \epsilon$ using the extended Euclidean algorithm.
Let $\displaystyle a = a_1 \left[ \frac{z}{a_1 x + b_1 y} \right]$ and $\displaystyle b = b_1 \left[ \frac{z}{a_1 x + b_1 y} \right],\,$ where $[\cdot]$ is the nearest integer function.

However, the integers $a$ and $b$ provided by this algorithm are usually not coprime. I'm looking for an algorithm that produces the same kind of approximation but guarantees that $a$ and $b$ are coprime.

Answer by SJR for Searching for an inhomogeneous diophantine approximation algorithm

2011-07-12T17:00:09Z

The question can be clarified a bit. The difficulty has nothing to do with the existence of algorithms: The required coprime integers $a$ and $b$ can be found by a systematic search if they exist at all, assuming any reasonable interpretation of the word Given in the first sentence of the question.

Furthermore, it will simplify matters to divide the inequality in the first sentence by $x$.

With this in mind, I'll give a proof of the following assertion:

Let $\epsilon>0$. Suppose $a$ is irrational and $b$ is any real number. Then there are coprime integers $x$ and $y$ such that $|ax-y-b|<\epsilon$.

Proof: The proof has undergone a major rewrite, thanks to Gerry Myerson's helpful comments. The argument extends a similar result (not mentioning coprimality) proved in Khinchin's book on continued fractions, which is a good reference for the basic facts I'll use here.

Let $p/q$ be a convergent (to be specified later) of the continued fraction expansion of $a$. Then it is well known (see Khinchin) that $p$ and $q$ are coprime, and moreover that $|a-p/q|<1/q^2$.

The latter inequality implies that for some real number $\delta$ with $|\delta|<1$,

$$a=\frac{p}{q}+\frac{\delta}{q^2}.$$

We will now produce a peculiar-looking estimate for $b$, the reason for which will become apparent shortly. Note that without loss of generality we can and will take $b$ to be positive.

Let $t$ be the largest prime not larger than $bq$. Then by Bertrand's Postulate $t\le bq<2t$ . From this we deduce the following chain of inequalities: $$t/q\le b<2t/q\le t/q+b.$$ It follows that for some $\gamma$ with $0\le \gamma <b$ , $$b=\frac{t}{q}+\frac{\gamma}{q}.$$

Thus, for any integers $x$ and $y$, we have the equality $$|ax-y-b|=\left|\left(\frac{p}{q}+\frac{\delta}{q^2}\right)x-y-\left(\frac{t}{q}+\frac{\gamma}{q}\right)\right|.$$

The right hand side can be rewritten as $$\left|\frac{px-t}{q}-y +\frac{\delta x}{q^2}-\frac{\gamma}{q}\right|,$$ and the latter is at most $$\left|\frac{px-t}{q}-y\right| +\left|\frac{\delta x}{q^2}-\frac{\gamma}{q}\right|.$$

Therefore to complete the proof it is enough to choose $q, x, y$ such that

(1) $x$ and $y$ are coprime.

(2) $\displaystyle\frac{px-t}{q}-y=0$, or equivalently $px-qy=t$.

(3) $\displaystyle\left|\frac{\delta x}{q^2}-\frac{\gamma}{q}\right|<\epsilon$.

Now since $p$ and $q$ are coprime, the equation $px-qy=t$ has integer solutions, say $x=x_0$ and $y=y_0$. For every integer $z$ there are additional solutions $x=x_0+qz$ and $y=y_0+pz$. Therefore we can choose solutions $x_0,\,y_0$ with $x_0$ in the interval $[0,q)$.

If $x_0$ and $y_0$ are not relatively prime, then since $px_0+qy_0=t$, and since $t$ is prime, it follows that $t$ is the only possible common factor. But if $t$ is in fact a common factor, then $x_0+q$ and $y_0+p$ must be relatively prime, because $t$ is likewise the only possible common factor of $x_0+q$ and $y_0+p$: But $t$ cannot divide these two integers lest $t$ divide both $p$ and $q$.

It follows that for any convergent $p/q$ for the continued fraction expansion of $a$, there are coprime integer solutions $x,\,y$ of the equation $px-qy=t$, with $x$ in the interval $[0,2q)$. For any such $x$, we have $$\left|\frac{\delta x}{q^2}-\frac{\gamma}{q}\right|<\frac{2}{q}+\frac{b}{q}.$$

Therefore, finally, if we choose $q$ so large that $\frac{2}{q}+\frac{b}{q}<\epsilon$, then Conditions (1) (2) and (3) are satisfied, and the proof is complete.

Searching for an inhomogeneous diophantine approximation algorithm - MathOverflow

Searching for an inhomogeneous diophantine approximation algorithm

Answer by SJR for Searching for an inhomogeneous diophantine approximation algorithm