Continued fractions

2 Real continued fractions and rational approximations

Given a real number \(r\), there is a unique way to write as a (possibly finite) simple continued fraction \([a_0,\dots ]\) such that each \(a_i\) an integer, \(a_i\) nonnegative for \(i>0\), and \(a_i = 0 \implies a_j=0\) if \(j>i\). Indeed, \(a_0\) must be \(\floor *{r}\). If \(r\) is not an integer, \([a_1,\dots ]\) must be equal to \(\frac 1 {r-\floor *r}\), which is positive and strictly greater than \(1\). Thus each of the next \(a_i\) will be nonnegative, and if one of them is zero, the rest are \(0\) as well, as this happens only when one step gives an integer. The fact that the euclidean algorithm terminates shows that one of them is zero iff \(r\) is a rational number. This particular continued fraction will be called

the continued fraction of the real number \(r\). If \(r\) is irrational, the convergents will converge to \(r\). First observe that by the construction of the \(a_i\) the \(k^{th}\) partial convergent is an underestimate of \(r\) if \(k\) is even, and an overestimate otherwise. Now by the magic box, if \(r_k = \frac {b_k}{c_k}\) is the \(k^{th}\) partial convergent, then \(\frac {b_k}{c_k}-\frac {b_{k+1}}{c_{k+1}} = \frac {\pm 1}{c_kc_{k+1}}\). if the \(a_i\) are eventually \(0\), then one of the convergents is the rational number, so the convergents converge, and by the remark about over and underestimating \(r\), they must converge to \(r\). We see in particular that any sequence \(a_k\) satisfying the conditions will determine a unique real number.

The partial convergents of \(r\) are really good approximations of it. Namely, note that \(|\frac {b_k}{c_k}-r| = |r_k-r| \leq |r_k-r_{k+1}| \leq \frac 1 {c_kc_{k+1}} \leq \frac 1{c_k^2}\). This is a surprisingly good approximation, considering that we might expect the best rational approximation of \(r\) with denominator \(c_k\) to have error at most \(\frac 1 {2c_k}\).

Let \(F_k\) denote the Farey sequence of rational numbers between \(0\) and \(1\) with denominator less than or equal to \(k\). We will write all fractions in their reduced form.

Lemma 2.1. If \(\frac {a}{b}\) is right before \(\frac {c}{d}\) in the \(F_k\). then \(ad-bc = -1\). If \(\frac {a}{b}, \frac {c}{d}\) are consecutive, and \(\frac {p}{q}\) is any rational between them, then \(\frac {p}{q} = \frac {k_1a+k_2c}{k_1b+k_2d}\) for some positive \(k_1,k_2\). If there is one rational number in \(F_k\) between \(\frac {a}{b}\) and \(\frac {c}{d}\), then it is given by \(\frac {a+c}{b+d}\). If the determinant \(ad-bc = \pm 1\), then \(\frac {a}{b},\frac {c}{d}\) are neighbors in the Farey sequence \(F_{b+d-1}\) and the rationals between them in reduced form are \(\frac {k_1a+k_2c}{k_1b+k_2d}\) where \((k_1,k_2) = 1\). The determinant is \(1\) iff the two rationals are consecutive in some \(F_k\).

Proof. It is clearly negative. Consider the parallelogram generated by \((a,b),(c,d)\). The region between the ray generated by \((a,b)\) and \((c,d)\) can canonically be tiled with these parallelograms. If \((a,b)\) are right next to each other, then the triangle between \((0,0),(a,b),(c,d)\) can have no interior points so the triangle has area \(\frac 1 2\), and hence the parallelogram has area \(1\), which proves the first result. We can tile the region between the rays generated by \((a,b),(c,d)\) with these parallelograms to get the second result. Suppose \(\frac {e}{f}\) is the only thing between \(\frac {a}{b},\frac {c}{d}\) in the Farey sequence. If \((a+c,b+d)\) lied strictly in the interior of the region between the rays generated by \((e,f)\), and one of \((a,b),(c,d)\) (WLOG \((a,b)\)), we can subtract \((a,b)\) from it to get that \((c,d)\) lies in the region between the rays, which is impossible. Thus it must lie on the ray generated by \((e,f)\). The next statement follows from the tiling by parallelograms again, and the last statement follows from the second last. □

Lemma 2.2. Each convergent of a real number is closer than the last.

Proof. Write \(r = [a_0,\dots ,a_n,b_n]\), where \(a_n\) agree with the continued fraction for \(r\). Then if \(\frac {b_n}{c_n}\) are the usual convergents of \(r\), one computes \(|r-\frac {b_n}{c_n}| = \frac {1}{c_n(c_nb_n+c_{n-1})}\). We compute \(|r-\frac {b_{n+1}}{c_{n+1}}| = \frac {b_n-\floor {b_n}}{c_{n+1}(c_nb_n+c_{n-1})}\), which is clearly smaller. □

Theorem 2.3. If \(r_k = \frac {b_k}{c_k}\) are the convergents of \(r\), \(k>0\), then they are best approximation of \(r\) with denominator at most \(c_{k}+c_{k-1}-1\).

Proof. Since \(k>0\) we can assume WLOG \(r\) is between \(0\) and \(1\). Then this follows from the lemma about the Farey sequences, and the facts that the determinant between \(r_k\) and \(r_{k-1}\) is \(\pm 1\), and that \(r_k\) is the better approximation. □

There is another sense in which we can ask that the continued fraction be a good approximation of \(r\). Namely we can say that \(\frac {p}{q}\) is a good approximation if \(|qr-p|\) is small. Our bounds from before show that if \(\frac {b_k}{c_k}\) are the convergents of \(r\), then \(|c_kr-b_k| < \frac {1}{c_{k+1}}\). We should note that the proof of Lemma 2.2 actually shows:

Lemma 2.4. \(|c_kr-b_k|>|c_{k+1}r-b_{k+1}|\).

Thus the convergents get closer in this sense as well.

Theorem 2.5. \(\frac {p}{q}\) is a reduced convergent of \(r\) with \(q \geq c_1\) iff for all different \(\frac {a}{b}\) with \(b\leq q\), \(|qr-p|<|br-a|\).

Proof. The case when \(b =q\) is covered from the statement about Farey sequences. If \(b\) is not the denominator of a convergent, let \(c_k < b<c_{k+1}\). We can interpret the statement as with Farey sequences by observing that \(|qr-p|\) is the horizontal distance from the point \((p,q)\) to the line \((cr,c)\). If \((a,b)\) lies outside the area between the rays generated by \((b_k,c_k)\) and \((b_{k-1},c_{k-1})\), then it certainly cannot be closer to the line \((c\alpha ,c)\) than either of them. If it is inside, then by Lemma 2.1, \((a,b)\) is a positive linear combination of \((b_k,c_{k})\) and \((b_{k-1},c_{k-1})\), with coefficients \(i_1,i_2\). Note that \(c_{k+1}\) is when \(i_1 = 1\) and \(i_2 = a_{k+1}\), and it is defined so that \(i_1=1\) and \(i_2 = a_{k+1}-1\) lies on the same side of the line \((cr,c)\) as \((b_{k-1},c_{k-1})\). Thus the closest \((a,b)\) could get to the line is \((b_{k-1}+(a_{k+1}-1)b_k,c_{k-1}+(a_{k+1}-1)c_k)\). But since \((b_{k+1},c_{k+1}),(b_{k},c_k)\) lie on different sides of the line, we have \(|r(b_{k-1}+(a_{k+1}-1)b_k)-(c_{k-1}+(a_{k+1}-1)c_k)| = |r b_{k+1}-c_{k+1}|+|r_{b_k}-c_{k}|\), giving the result. □

Proposition 2.6. An irrational \(r\) has infinitely many rational approximations \(\frac p q\) with error less than \(\frac 1 {2q^2}\). Every such rational number is a convergent. For any \(\ee ,c>0\), A rational number has finitely many approximations \(\frac p q\) with error at most \(\frac c {q^{1+\ee }}\).

Proof. The inequality holds for at least one out of every two convergents. Otherwise, we have \(\frac {1}{c_kc_{k+1}} = |\frac {b_{k}}{c_k}-\frac {b_{k+1}}{c_{k+1}}|\geq \frac {1}{2c_{k}^2}+ \frac {1}{2c_{k+1}^2}\), which cannot be an equality as \(c_k < c_{k+1}\). Conversely, if the inequality is satisfied for \(\frac {a}{b}\), then we will show that \(\frac {a}{b}\) satisfies the theorem above. Let \(\frac {c}{d}\) be any different reduced fraction which is closer in the sense of the above theorem. Then \(\frac {1}{bd} \leq |\frac {a}{b}-\frac {c}{d}| \leq |\frac {a}{b} -r| + |\frac {c}{d}-r|\leq \frac {1}{2b^2}+\frac {1}{2bd}\), which implies \(b<d\).

For the last statement, if our rational number is \(\frac a b\) and we want \(|\frac a b - \frac p q| \leq \frac c {q^{1+\ee }}\). WLOG we can assume \(\frac p q \leq \frac a b\), \(a,q>0\). Then \(aq^{1+\ee }-pq^{\ee }b \leq b\), so \(q\) is bounded, and takes finitely many values. \(p\) does as well. □

Let’s define some notation. If \(x,y \in \RR \), we can say that \(x \to y\) if \(y = \frac {1}{x-\floor {x}}\), and \(x \twoheadrightarrow y\) if \(x \to x_1 \to x_2 \to \dots y\). Clearly if \(x = [c_0,\dots ],y = [c'_0,\dots ]\) are the continued fractions, then \(x \to y\) iff \(c'_i = c_{i+1}\).

Lemma 2.7. \(\exists x\) such that \(x \to y\) iff \(y>1\).

Proof. Then if \(x \to y\), this is clear, and conversely, we can let \(x\) be \(\frac {1}{y}+n\) for any \(n\). □