Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Note that this question was also posted to m.se two days ago, math.stackexchange.com/questions/50556 It is also related to math.stackexchange.com/questions/46100 –  Gerry Myerson Jul 12 '11 at 0:44
    
Not fond of the imperative. –  Will Jagy Jul 12 '11 at 4:25
    
I don't see how it's specifically related to math.stackexchange.com/questions/46100 . There's nothing in there about the coefficients being coprime. –  Keenan Pepper Jul 12 '11 at 5:09
    
It is true that Shreevatsa's solution to 46100 does not discuss coprimality of coefficients. It does give a way to find $a$ and $b$ that is, I think, not the same as your way, and there is some leeway in it which may (or may not) steer you toward the coprime solution you want. Anyway, I think anyone who wants to solve your problem could do worse than to look closely at 46100 and at the section of Ed Burger's book cited by Shreevatsa. –  Gerry Myerson Jul 12 '11 at 5:43
add comment

1 Answer

up vote 3 down vote accepted

The problem isn't really about 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.

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.

share|improve this answer
    
Yes, that's what I was looking for! Not sure why you changed all the variable names, but the last part is what I was missing: it proves that once you've found a good enough continued fraction convergent p/q you can just stick with that; it's not necessary to try different p,q values in order to find a solution that's both coprime and accurate enough (which I had feared might be the case). –  Keenan Pepper Jul 12 '11 at 17:42
    
I think at a couple of points you've got $\delta/q^2$ where you want $x\delta/q^2$. So I think you need to produce a bound on $x$. –  Gerry Myerson Jul 13 '11 at 0:47
    
Still worried - $1/x\lt1/q$ gives no upper bound on $x$ nor on $x\delta/q^2$ so I'm not seeing where the $2/q$ comes from. –  Gerry Myerson Jul 13 '11 at 11:54
1  
I would change one paragraph to put a minus in where you have a plus, and add at the end of the paragraph for clarity that you can then have a coprime solution (x, y) with 0<x<2q, as well as referencing (0,2q) in the following paragraph. The rest looks blessworthy to me. Gerhard "Email Me About System Design" Paseman, 2011.07.13 –  Gerhard Paseman Jul 14 '11 at 1:31
    
@Gerry: I've done a second rewrite, which makes good sense to me. If you come back to this, please tell me what you think. Thanks again for your comments. –  SJR Jul 14 '11 at 2:02
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.