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}$ .

Like this:

Related