Searching for an inhomogeneous diophantine approximation algorithm - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T04:51:22Z http://mathoverflow.net/feeds/question/70035 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70035/searching-for-an-inhomogeneous-diophantine-approximation-algorithm Searching for an inhomogeneous diophantine approximation algorithm Keenan Pepper 2011-07-11T17:57:13Z 2011-07-16T03:35:19Z <p>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| &lt; \epsilon$?</p> <p>Note that if the restriction that $a$ and $b$ be coprime is lifted, the problem becomes very simple. One possible algorithm is:</p> <ul> <li>Find $a_1$ and $b_1$ such that $0 &lt; a_1 x + b_1 y &lt; \epsilon$ using the extended Euclidean algorithm.</li> <li>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.</li> </ul> <p>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.</p> http://mathoverflow.net/questions/70035/searching-for-an-inhomogeneous-diophantine-approximation-algorithm/70150#70150 Answer by SJR for Searching for an inhomogeneous diophantine approximation algorithm SJR 2011-07-12T17:00:09Z 2011-07-16T03:35:19Z <p>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.</p> <p>Furthermore, it will simplify matters to divide the inequality in the first sentence by $x$.</p> <p>With this in mind, I'll give a proof of the following assertion:</p> <p>Let <code>$\epsilon&gt;0$.</code> Suppose $a$ is irrational and $b$ is any real number. Then there are coprime integers $x$ and $y$ such that $|ax-y-b|&lt;\epsilon$.</p> <p>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. </p> <p>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|&lt;1/q^2$.</p> <p>The latter inequality implies that for some real number $\delta$ with $|\delta|&lt;1$, </p> <p>$$a=\frac{p}{q}+\frac{\delta}{q^2}.$$ </p> <p>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. </p> <p>Let $t$ be the largest prime not larger than $bq$. Then by Bertrand's Postulate <code>$t\le bq&lt;2t$</code>. From this we deduce the following chain of inequalities: <code>$$t/q\le b&lt;2t/q\le t/q+b.$$</code> It follows that for some $\gamma$ with <code>$0\le \gamma &lt;b$</code>, $$b=\frac{t}{q}+\frac{\gamma}{q}.$$</p> <p>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|.$$</p> <p>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|.$$</p> <p>Therefore to complete the proof it is enough to choose $q, x, y$ such that</p> <p>(1) $x$ and $y$ are coprime.</p> <p>(2) $\displaystyle\frac{px-t}{q}-y=0$, or equivalently $px-qy=t$.</p> <p>(3) $\displaystyle\left|\frac{\delta x}{q^2}-\frac{\gamma}{q}\right|&lt;\epsilon$.</p> <p>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 <code>$x_0,\,y_0$</code> with $x_0$ in the interval $[0,q)$. </p> <p>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$. </p> <p>It follows that for any convergent $p/q$ for the continued fraction expansion of $a$, there are coprime integer solutions <code>$x,\,y$</code> 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|&lt;\frac{2}{q}+\frac{b}{q}.$$</p> <p>Therefore, finally, if we choose $q$ so large that $\frac{2}{q}+\frac{b}{q}&lt;\epsilon$, then Conditions (1) (2) and (3) are satisfied, and the proof is complete.</p>