\documentclass[a4paper,12pt]{article} \begin{document} \parindent=0pt \begin{center} CONTINUED FRACTIONS BEST APPROXIMATIONS \end{center} $\frac{a}{b}$ is said to be a best approximation to $\alpha\ (\alpha\in Z\ b\in N)$ if $$\left|\alpha-\frac{p}{q}\right|<\left|\alpha-\frac{a}{b} \right|\Rightarrow q>b.$$ We now prove that the convergents to an (irrational) number give a sequence of best approximations. Note that as in the previous result, we often investigate $|q\alpha-p|$ rather than $\left|\alpha-\frac{p}{q}\right|$. Inequalities involving the former are often a bit stronger the those involving the latter. %page 21 Theorem If $|q\alpha-p|<|q_n\alpha-p_n|,\ n>0$ where $\frac{p_n}{q_n}$ is a convergent of the continued fraction for $\alpha$, then $q>q_n$. Proof Assume that $|q\alpha-p|0)$. Consider the equations \begin{eqnarray*} x.p_n+y.p_{n+1}&=&p\\ x.q_n+y.q_{n+1}=q \end{eqnarray*} $p_nq_{n+1}-p_{n+1}q_n=(-1)^n$, so this pair of equations has integer solutions $x,y$. Now $y=0\Rightarrow p=xp_n\ q=xq_n,\ x\neq0$ and so $|q\alpha-p|=|x||q_n\alpha-p_n|\geq|q_n\alpha-p_n|$ If $x=0$ then $y\neq0$ and $q=yq_n$ which contradicts $q\leq q_n$. So $x$ and $y$ are non-zero. We now show that $x$ and $y$ are of opposite sign. $$00$ $x$ and $y$ cant both be $>0$ otherwise $>q_{n+1}$ Now $q_n\alpha-p_n$ and $q_{n+1}|alpha-p_{n+1}$ have opposite signs, since the convergents alternate either side of $\alpha$, so $x(q_n\alpha-p_n)$ and $y(q_{n+1}\alpha-p_{n+1})$ have the same sign. %page 22 Also $$q\alpha-p=x(q_n\alpha-p_n)+y(q_{n+1}\alpha-p_{n+1})$$ so \begin{eqnarray*} |q\alpha-p|&=&|x(q_n\alpha-p_n)|+|y(q_{n+1}\alpha-p_{n+1})|\\ &>&|x(q_n\alpha-p_n)|\geq|q_n\alpha-p_n| \end{eqnarray*} This contradiction proves the theorem. This proof goes back to Legendre, and is quoted in Perron. Now $\left|\alpha-\frac{p}{q}\right|<\left|\alpha-\frac{p_n}{q_n}\right|$ and$q\leq q_n$ multiplying the inequalities $$\Rightarrow |q\alpha-p|<|q_n\alpha-p_n|\Rightarrow q>q_n$$ So the convergents are the best approximations to $\alpha$. But how good are they? Now we have already seen the equation $$\alpha-\frac{p_n}{q_n}=\frac{(-1)^n}{q_n(\alpha_{n+1}q_n+q_{n-1})}$$ so $$\left|alpha-\frac{p_n}{q_n}\right|=\frac{1}{q_n(\alpha_{n+1}q_n +q_{n-1})}\leq\frac{1}{q_n(a_{n+1}q_n+q_{n-1})}=\frac{1}{q_nq_{n+1}} <\frac{1}{q_n^2}$$ We already know from Dirichlet's theorem that an irrati0onal $\alpha$ has infinitely many rational approximations $\frac{p}{q}$ satisfying $\left|\alpha-\frac{p}{q}\right|<\frac{1}{q^2}$. The sequence of convergents supplies such a set. %page 23 This does not give them all however. E.g. consider rational approximations to $\frac{779}{207}$ The convergents are $$3,\ 4,\ \frac{15}{4},\ \frac{64}{17},\ \frac{143}{38},\ \frac{779}{207}.$$ \begin{eqnarray*} \frac{779}{207}-\frac{79}{21}&=&\frac{6}{4347}\approx1.38\times10^{-3}\\ \frac{1}{21^2}&\approx&2.27\times10^{-3} \end{eqnarray*} However, notice that $\frac{79}{21}=\frac{15+64}{4+17}$ I shall not pursue this, but instead show that if $\left|\alpha-\frac{p}{q}\right|<\frac{1}{2q^2}\ (p,q)=1$ then $\frac{p}{q}$ is one of the convergents of the continued fraction for $\alpha$. Proof Suppose not. Then $q_n\leq q\leq q_{n+1}$ determines an integer $n$, and $|q\alpha-\phi|<|q_n\alpha-p_n|$ is impossible. ( The earlier theorem can be improved to $q\geq q_{n+1}$) so $|q_n\alpha-p_n|\leq|q\alpha-p|<\frac{1}{2q}$ i.e $\left|\alpha-\frac{p_n}{q_n}\right|Z<\frac{1}{2qq_n}$ Now \begin{eqnarray*} \frac{1}{qq_n}&\leq&\frac{|qp_n-pq_n|}{qq_n}\textrm{ (even if }q=q_n\ \frac{p}{q}\neq\frac{p_n}{q_n})\\ &=&\left|\frac{p_n}{q_n}-\frac{p}{q}\right|\\ &\leq&\left|\alpha-\frac{p_n}{q_n}\right|+\left|\alpha-\frac{p}{q} \right|\\ &<&\frac{1}{2qq_n}+\frac{1}{2q^2}\\ \frac{1}{2qq_n}&<&\frac{1}{2q^2} \end{eqnarray*} so $qq_n$. Even in this case $$0<\frac{p_1}{q_1}-x=1-\frac{1}{1+}\frac{1}{a_2+}<1- \frac{a_2}{a_2+1}\leq\frac{1}{2}$$ so the theorem is still true. Further, of any three successive convergents, at least one satisfies $\left|\alpha-\frac{p}{q}\right|<\frac{1}{q^2\sqrt{5}}$ Proof %page 25 $$\left|\alpha-\frac{p_n}{q_n}\right|=\frac{1}{q_n(\alpha_{n+1} q_n+q_{n-1})}=\frac{1}{q_n^2\left(\alpha_{n+1}+\frac{q_{n-1}}{q_n} \right)}$$ Now suppose that $$\alpha_i+\frac{q_{i-2}}{q_{i-1}}\leq\sqrt{5}\textrm{ for }i=n-1,n,n+1$$ Then $$\alpha_{n-1}=a_{n-1}+\frac{1}{\alpha_n}\textrm{ and }\frac{q_{n-1}}{q_{n-2}}=a_{n-1}+\frac{q_{n-3}}{q_{n-2}}$$ so $$\frac{1}{\alpha_n}+\frac{q_{n-1}}{q_{n-2}}=\alpha_{n-1}+ \frac{q_{n-3}}{q_{n-2}}\leq\sqrt{5}$$ by assumption and \begin{eqnarray*} 1&=&\alpha_n\frac{1}{\alpha_n}\leq\left(\sqrt{5}+\frac{q_{n -2}}{q_{n-1}}\right)\left(\sqrt{5}-\frac{q_{n-1}}{q_{n-2}} \right)\\ &=&5+1-\sqrt{5}\left(\frac{q_{n-2}}{q_{n-1}}+\frac{q_{n-1}}{ q_{n-2}}\right) \end{eqnarray*} giving $\frac{q_{n-2}}{q_{n-1}}+\frac{q_{n-1}}{q_{n-2}}\leq\sqrt{5}$ In fact since LHS is rational we have strictly less then, so \begin{eqnarray*} \left(\frac{q_{n-1}}{q_{n-1}}\right)^2-\left(\frac{q_{n-2}}{ q_{n-1}}\right)\sqrt{5}+1&<&0\\ \left(\frac{q_{n-2}}{q_{n-1}}-\frac{1}{2}\sqrt{5}\right)^2&<& \frac{1}{4}\textrm{ i.e.}\\ \frac{q_{n-2}}{q_{n-1}}&>&\frac{1}{2}(\sqrt{5}-1) \end{eqnarray*} This has used $i=n-1,n$. Using $1=n,n+1$ gives $$\frac{q_{n-1}}{q_n}>\frac{1}{2}(\sqrt{5}-1)$$ Now $q_n=a_nq_{n-1}+q_{n-2}$ $$a_n=\frac{q_n}{q_{n-1}}-\frac{q_{n-2}}{q_{n-1}}< \frac{2}{\sqrt{ 5}-1}-\frac{1}{2}(\sqrt{5}-1)=1$$ $a_n<1$ is a contradiction. %page 26 Now let $\alpha=\frac{1}{2}(\sqrt{5}-1)=[0,1,1,1,\ldots]$ Suppose that there are an infinite number of solutions of $$\left|\alpha-\frac{p}{q}\right|<\frac{1}{Aq^2}\ A>\sqrt{5}$$ $\alpha=\frac{p}{q}+\frac{\delta}{q^2}$ where $|\delta|<\frac{1}{A}<\frac{1}{\sqrt{5}}$ Then $\frac{\delta}{q}=q\alpha-p$ and $$\frac{\delta}{q}-\frac{1}{2}q\sqrt{5}=q\left( \frac{1}{2}\sqrt{5}-1\right)-p-\frac{1}{2}q\sqrt{5} =-\frac{1}{2}q-p$$ so $$\left(\frac{\delta}{q}\right)^2-\delta\sqrt{5}+ \frac{5}{4}q^2=\left(\frac{1}{2}q+p\right)^2$$ so $$\left(\frac{\delta}{q}\right)^2-\delta\sqrt{5}=p^2pq-q^2$$ when $q$ is large, since $|\delta|\sqrt{5}<1$ the LHS is between $-1$ and +1 whereas RHS is an integer. So $p^2+pq-q^2=0$ i.e.$(2p+q)^2=5q^2$ which is impossible for integers $p$ and $q$. So $\frac{1}{\sqrt{5}}$ is the best possible. This establishes Hurwitz theorem. %page 27 We now investigate for which numbers $\sqrt{5}$ is best possible. It turns out that the criterion is that these numbers should end in an infinite tail of 1's. We generalise this. Definition Two irrational numbers $\alpha$ and $\beta$ are equivalent if they have the same tail to their continued fraction, in the sense that $\alpha=[a_0;a_1,\ldots,a_k,c_0,c_1c_2\ldots]$ $\beta=[b_0;b_1,\ldots,b_j,c_0,c_1,c_2\ldots]$ Theorem Two irrational numbers $\alpha$ and $\beta$ are equivalent if and only if there exist integers $a,b,c,d$ with $ad-bc=\pm1$ such that $$\alpha=\frac{A\beta+B}{C\beta+D}$$ Lemma if $x=\frac{P\xi+R}{Q\xi+S}$ where $\xi>1,\ PS-RQ=\pm1$, and $Q>S>0$ then $\frac{r}{S}$ and $\frac{P}{Q}$ are two consecutive convergents to the continued function for $x$. If $\frac{R}{S}$ is the $(n-1)$th, $\frac{P}{Q}$ is the $n$th and $\xi$ is the $(n-1)$th complete quotient. Proof $$\frac{P}{Q}=[a_0,a_1,\ldots,a_n]=\frac{p_n}{q_n}$$ $n$ can be even or odd. Choose it so that $PS-QR=(-1)^{n-1}$ %page 28 $(p,q)=1$ so $P=p_n\ Q=q_n$ so $p_nS-q_nR=(-1)^{n-1}=p_nq_{n-1}-p_{n-1}q_n$ so $p_n(S-q_{n-1})=q_n(R-p_{n-1})$ so $q_n|S-q_{n-1}$ since $(p_n,q_n)=1$. Now \begin{eqnarray*} q_n&=&Q>S>0\\ q_n&\geq&q_{n-1}>0\textrm{ so }\\ q_n&>&| S-q_{n-1}| \end{eqnarray*} Hence $S-q_{n-1}=0$ and so $R-p_{n-1}=0$ thus $\frac{R}{S}=\frac{p_{n-1}}{q_{n-1}}$ and $x=\frac{p_n\xi+p_{n-1}}{q_n\xi+q_{n-1}}$ i.e. \begin{eqnarray*} x&=&[a_0,a_1,\ldots,a_n,\xi]\\ &=&[a_0,a_1,\ldots a_n,c_0,c_1] \end{eqnarray*} where$\xi=[c_0;c_1,c_2\ldots]$ and $c_0\neq0$ as $\xi>1$ and so $\xi$ is the $n+1$th complete quotient. Proof of theorem Suppose $\alpha=[a_0,\ldots a_k,c_0,c_1\ldots]=[a_0,\ldots a_k,w]$ $\beta=[b_0,\ldots b_j,c_o,c_1\ldots]=[b_0,\ldots b_j,w]$ then $$\alpha=\frac{p_kw+p_{k-1}}{q_kw+q_{k-1}}\hspace{1.5cm}p_kq_{k-1} -p_{k-1}q_k=\pm1$$ $$\beta=\frac{p_j'w+p_{j-1}'}{q_j'w+q_{j-1}'}\hspace{1.5cm}p_j' q'_{j-1}-p'_{j-1}q;_j=\pm1$$ %page 29 eliminating $w$ will give $$\alpha=\frac{A\beta+B}{C\beta+D}\textrm{ where }AD-BC=\pm1.$$ Now suppose $$\alpha=\frac{A\beta+B}{C\beta+D}\ AD-BC=\pm1$$ assume w.l.o.g. $C\beta+D>0$. Let $\beta=[b_0,\ldots b_{k-1}\beta_k]=\frac{p_{k-1}\beta_k+p_{k-2}}{q_{k-1}\beta_k+q_{k- 2}}$ substituting fo $\beta$ in $\alpha=\frac{A\beta+B}{C\beta+D}$ gives $$\alpha=\frac{P\beta_K+R}{q\beta_k+s}$$ where \begin{eqnarray*} P&=&Ap_{k-1}+Bq_{k-1}\\ R&=&Ap_{k-2}+Bq_{k-2}\\ Q&=&Cp_{k-1}+Dq_{k-1}\\ S&=&Cp_{k-2}+Dq_{k-2} \end{eqnarray*} So $P,Q,R,S\in Z$ and $$PS_QR=(AD-BC)(p_{k-1}q_{k-2}-p_{k-1}q_{k-1})=\pm1$$ Now $\left|\beta-\frac{p_{k-1}}{q_{k-1}}\right|<\frac{1}{q_{k-1}^2}$ and $\left|\beta-\frac{p_{k-2}}{q_{k-2}}\right|<\frac{1}{q_{k-2}^2}$ so $$p_{k-1}=q_{k-1}\beta+\frac{\varepsilon}{q_{k-1}};p_{k-1}=q_{k-1} \beta+\frac{\varepsilon'}{q_{k-1}}$$ where $|\varepsilon|<1$ and $|\varepsilon'|<1$. %page 30 So \begin{eqnarray*} Q&=& (C\beta+D) q_{k-1}+ \frac{C\varepsilon}{q_{k-1}} \\ S&=&(C\beta+D)q_{k-2}+\frac{C\varepsilon'}{q_{k-2}} \end{eqnarray*} Now $C\beta+D>0$ and $q_{k-1}>q_{k-1}$ also $q_n\rightarrow\infty$ as $n\rightarrow\infty$. So provided $k$ is sufficiently large, $Q>S>0$ For such $k,\ \alpha=\frac{P\beta_k+R}{Q\beta_k+S}\ PS-QR=\pm1, Q>S>0$ so $\beta_k$ is a complete quotient in the continued fraction for $\alpha$ by the lemma thus $\alpha=[a_0;a_1,\ldots a_m,b_k,b_{k+1}\ldots]$ i.e. $\alpha$ is equivalent to $\beta$. We now define the Markov constant of an irrational number $\alpha$ by $$M(\alpha)=sup\left\{\lambda:\left|\alpha-\frac{p}{q}\right|< \frac{1}{\lambda q^2}\textrm{ has infinitely many solutions }\frac{p}{q}\right\}$$ So Huzwitz theorem says $\forall\alpha\ M(\alpha\geq \sqrt{5}$ and $M\left(\frac{1+\sqrt{5}}{2}\right)=\sqrt{5}$. We now extend this : %page 31 Theorem If $\alpha$ is equivalent to $\beta$ then $M(\alpha)=M(\beta)$. If $\alpha$ is not equivalent to $\frac{1+\sqrt{5}}{2}$ then $M(\alpha)\geq\sqrt{8}$. If $\alpha$ is equivalent to $1+\sqrt{2}$ then $M(\alpha)=\sqrt{8}$. Proof Recall that \begin{eqnarray*} \left|\alpha-\frac{p_k}{q_k}\right|&=&\frac{1}{q_k(q_k\alpha_{k+1}+q_{k-1})}\\ &=&\frac{1}{q_k^2\left(\alpha_{k+1}+\frac{q_{k-1}}{q_k}\right)} \end{eqnarray*} Thus $$M(\alpha)=\lim_{k\to\infty}sup\left(\alpha_{k+1}+\frac{q_{k-1}}{q_k}\right)$$ Recall from the discussion of symmetric continued fractions that $$\frac{q_k}{q_{k-1}}=[a_k;a_{k-1},\ldots a_1]$$ so $$\frac{q_{k-1}}{q_k}=[0;a_ka_{k-1}\ldots a_1]$$ so $$M(\alpha)=\lim_{k\to\infty}sup\left([0;a_k,a_{k-1},\ldots a_1]+\alpha_{k+1}\right)$$ Now if $\alpha$ is equivalent to $\beta$ then $\beta_j=\alpha_k$ and $b_j=a_k$ for all sufficiently large $k$ and $j$ for which $j-k$ has a suitable fixed value $h$. %page 32 If the convergents of $\beta$ are $\frac{P_j}{Q_j}$ then for $j$ and $k$ differing by $h$, the continued fractions for $\frac{q_{k-1}}{q_k}$ and $\frac{Q_{j-1}}{Q_j}$ have rhe same partial quotients at the beginning, and the length of agreement can be made large by making $j$ and $k$ sufficiently large. Suppose $\frac{q_{k-1}}{q_k}$ and $\frac{Q_{j-1}}{Q_j}$ agree in the first $l_1$ partial quotients, and denote the common convergents by $\frac{r_i}{s_i}\ (i=0,\ldots l)$ so $$\frac{q_{k-1}}{q_k}=\frac{r_{l-1}x_l+r_{l-2}}{s_{l-1}x_l+s_{l-2}}$$ and $$\frac{Q_{j-1}}{Q_{j}}=\frac{r_{l-1}y_l+r_{l-2}}{s_{l-1}y_l+s_{l-2}}$$ Then $[x_l]=[y_l]=$ common $l+1$th partial quotient so $|x_l-y_l|\leq1$. Then we have $$\left|\frac{q_{k-1}}{q_k}-\frac{Q_{j-1}}{Q_j}\right|=\frac{|x_l-y_l|}{ (s_{l-1}x_l+s_{l-2})(s_{l-1}y_l+s_{l-1})}\leq\frac{1}{s_{l-1}^2}$$ Now provided $j$ and $k$ are large enough, we have $$\left|\frac{q_{k-1}}{q_k}-\frac{Q_{j-1}}{Q_j}\right|<\varepsilon$$ since $s_{l-1}\geq(l-1)$th term in Fibonacci sequence. %page 33 Also for large $j,k\ \alpha_k=\beta_j$, so $$\left(\alpha_k+\frac{q_{k-1}}{q_k}\right)-\left(\beta_j+\frac{Q_{j-1 }}{Q_j}\right)=\frac{q_{k-1}}{q_k}-\frac{Q_{j-1}}{Q_j}\to0\textrm{ as }j,k\to\infty,\ j-k=h $$ Thus $M(\alpha)=M(\beta)$ If $\alpha$ is not equivalent to $\frac{\sqrt{5}+1}{2}$ then infinitely many of the $a_k$ are $\geq2$. If $a_k\geq3$ for infinitely many $k$ then \begin{eqnarray*} M(\alpha)&=&\lim sup\left(\alpha_{k+1}+\frac{q_{k-1}}{q_k}\right)\\ &\geq&\lim sup(a_{k+1})\geq3 \end{eqnarray*} So suppose that the $a_k$ contain only 1's and 2's from some point on. Case I $a_k=2$ from some point on. Then $\alpha$ is equivalent to $1+\sqrt{2}=[2;2,2,\ldots]$ \begin{eqnarray*} M(\alpha)&=&\lim sup\left(\alpha_{k+1}+\frac{q_{k-1}}{q_k}\right)\\ \alpha_{k+1}&=&[2;2,\ldots]=1+\sqrt{2}\\ \frac{q_{k-1}}{q_k}&=&[0;\underbrace{2,2,\ldots}_{k \textrm{ times}}]\to\frac{1}{1+\sqrt{2}}\textrm{ as }k\to\infty \end{eqnarray*} So $M(\alpha)=1+\sqrt{2}+\frac{1}{1+\sqrt{2}}=\sqrt{8}$ Case II Suppose thee are infinitely many 1's and 2's. %page 34 Then there are infinitely many $k$ such that $a_k=1$ and $a_{k+1}=2$, so \begin{eqnarray*} \alpha_{k+1}&=& 2+\frac{1}{a_{k+2}+}\frac{1}{a_{k+3}}\geq2+\frac{1}{2+\frac{1}{1}}=\frac{7}{3}\\ \frac{q_{k-1}}{q_k}&=& \frac{1}{a_k+}\frac{1}{a_{k-1}+}\ldots\geq\frac{1}{1+\frac{1}{a_{k-1}}}\geq\frac{1}{1+\frac{1}{1}}=\frac{1}{2} \end{eqnarray*} So $M(\alpha)\geq\frac{7}{3}+\frac{1}{2}=\frac{17}{6}>\sqrt{8}$ Note: This shows that if $\alpha\not\sim1+\sqrt{2}$ then $M(\alpha)\geq\frac{17}{6}$. Theorem There are uncountably many $\alpha$ with $M(\alpha)=3$ Proof Let $\alpha=[\underbrace{1;1,1,\ldots1}_{r_1},2,2,\underbrace{1,1,\ldots1 }_{r_2},2,2,\underbrace{1,1,\ldots1}_{r_3},2,2,1,\ldots]\ r_1