Rational Approximation

Given a real number or a rational with large integers r, how can we approximate this by a rational with small integers?

Let’s recall the Euclidean algorithm to find \gcd(a,b) via the following example:

\gcd(209, 171)
209 = 171 \cdot 1 + 38
\gcd(171, 38)
171 = 38 \cdot 4 + 19
\gcd(38, 19) = 19

In general, for a = b \cdot q + r, we use \gcd(a,b) = \gcd(b,r), which is much faster than factorization!

To see this algorithm in another setting, we recall continued fractions. For this, we will consider the example of approximating e by a rational.

e = 2 + 0.71828\dots = 2 + (e-2)
= 2 + \frac{1}{1 + \frac{3-e}{e-2}}
= 2 + \frac{1}{1 + \frac{1}{2 + \frac{3e-8}{3-e}}}
= 2, 2 + \frac{1}{1}, 2 + \frac{1}{1 + \frac{1}{2}}, \dots
= 2, 3, 2\frac{2}{3}, \dots

Theorem 1.
For any integer B>0, the best rational approximation of any real r using denominator at most B is given by a continued fraction approximation of r.

r = a_0 \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \frac{1}{a_4 + \dots}}}}

The theorem will follow from the next lemma.

Lemma 2.
(1)
p_{k+1} = a_{k}p_{k} + p_{k-1}
q_{k+1} = a_{k}q_{k} + q_{k-1}
p_{-1} = 0, p_{0} = 1, q_{-1} = 1, q_{0} = 0

(2)
p_{k}q_{k+1}-p_{k+1}q_{k} = (-1)^{k} \implies |\frac{p_k}{q_k} - \frac{p_{k+1}}{q_{k+1}}| = \frac{1}{q_{k}q_{k+1}}

(3)
\forall r, \forall B \geq b, \exists unique \frac{a}{b} such that |r - \frac{a}{b}| < \frac{1}{2bB}

(4)
\frac{a}{b} from (3) is given by some \frac{p_k}{q_k}

Proof.
(1) is left as homework.

(2) is by substitution. Note that r - \frac{p_k}{q_k} alternates in sign and converges.

(3)\ \exists \frac{a_1}{b_1}, \frac{a_2}{b_2} with b_1, b_2 \leq B
|\frac{a_1}{b_1} - \frac{a_2}{b_2}| \leq |\frac{a_1}{b_1}-r| + |\frac{a_2}{b_2}-r| < \frac{1}{2b_{1}B} + \frac{1}{2b_{2}B} \leq \frac{1}{b_{1}b_{2}}
But for any two \frac{a_1}{b_1} \neq \frac{a_2}{b_2},
|\frac{a_1}{b_1} - \frac{a_2}{b_2}| \geq |\frac{a_{1}b{2} - a_{2}b{1}}{b_{1}b_{2}}| \geq \frac{1}{b_{1}b_{2}}, where we reach a contradiction.

(4) Suppose \exists \frac{a}{b} \neq \frac{p_k}{q_k} such that |\frac{a}{b}-r| < \frac{1}{2bB}
For $latex q_k \leq B |\frac{a}{b}-r| \geq \min(|\frac{a}{b} – \frac{p_k}{q_k}|, |\frac{a}{b}-\frac{p_{k+1}}{q_{k+1}}|)$
\frac{1}{2bB} \geq \frac{1}{bq_{k+1}}
\implies q_{k+1} > 2B
So,
|r-\frac{p_k}{q_k}| \leq \frac{1}{q_{k}q_{k+1}} < \frac{1}{2q_{k}B}
But such a solution is unique!

We will now use lemma 2 to complete our algorithm for solving Ax=b exactly. Recall we have \bar{x} where A\bar{x} = b\ (mod\ p^m). For each x_i, our goal is to find c_i, d such that
dx_i = c_{i}\ (mod\ p^m)
Then, A\frac{c}{d} = b since \|Ac\|, \|b\| << p^m.

Lemma 3.
Suppose \exists integers f,g such that |f|,|g|<\frac{1}{2}\sqrt{h} and gs = f\ (mod\ h).
Let the continued fraction approximations of \frac{s}{h} be \frac{w_1}{v_1} \dots \frac{w_k}{v_k} \dots and define u_i = v_{i}s - w_{i}h.
Let k be the smallest integer such that |u_k| \leq \sqrt{h}. Then, \frac{f}{g} = \frac{u_k}{v_k}.

This lemma solves our problem. We can quickly convert \bar{x} to a rational solution via the continued fraction approximations of \frac{x_i}{p^m} and finding the corresponding \frac{u_k}{v_k}.

Proof.
Note that \{w_i\},\{v_i\} are increasing while |u_i| is decreasing (why?). Let f = gs - th. Then,
|\frac{s}{h} - \frac{t}{g}| = |\frac{f}{hg}| = |\frac{fg}{hg^2}| < \frac{1}{2g^2}

By Lemma 2, \frac{t}{g} must be some \frac{w_j}{v_j}.
\implies |u_j| \leq |f| \leq \frac{1}{2}\sqrt{h}, so j \geq k, since u_j is decreasing.

But u_{j}v_{k}-u_{k}v_{j} = (v_{j}s-w_{j}h)v_k - (v_{k}s-w_{k}h)v_j = (-w_{j}v_k + w_{k}v_j)h = 0\ (mod\ h) and |u_{j}v_{k}-u_{k}v_{j}| \leq (|u_j|+|u_k|)|v_j| \leq (\frac{1}{2}\sqrt{h} + \sqrt{h})\frac{1}{2}\sqrt{h} < h.

\implies u_{j}v_{k}=u_{k}v_{j} i.e. j=k and \frac{f}{g} = \frac{u_k}{v_k}.

Advertisements