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