Quadratic Irrationals, Continued Fractions, Pell’s Equation..

Quadratic irrational are solutions to quadratic equations with integer coefficients.

Continued fractions: Expansion of the form
$\displaystyle \left[a_{0} ; a_{1}, a_{2}, a_{3}, \dots\right]=\large{a_{0}+\cfrac{1}{a_{1}+\cfrac{1}{a_{2}+\cfrac{1}{a_{3}+\cdots}}} }$

$\displaystyle [1,2]=1+\cfrac{1}{2}=\cfrac{3}{2}$
$\displaystyle \cfrac{172}{51}=[3,2,1,2,6]=3+\cfrac{1}{2+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{6}}}}$

$\displaystyle \pi=[3 ; 7,15,1,292,1,1,1,2,1,3,1, \dots]=3+\cfrac{1}{7+\cfrac{1}{15+\cfrac{1}{1+\cfrac{1}{292+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{1+\cfrac{1}{3+\cfrac{1}{1+\ddots}}}}}}}}}}}$

$\displaystyle \begin{aligned} \left[a_{0}, a_{1}, \ldots, a_{m-1}, a_{m}\right] &=\left[a_{0}, a_{1}, \ldots, a_{m-2}, a_{m-1}+\frac{1}{a_{m}}\right] \\ &=a_{0}+\frac{1}{\left[a_{1}, \ldots, a_{m}\right]} \\ &=\left[a_{0},\left[a_{1}, \ldots, a_{m}\right]\right] \end{aligned}$

If $\displaystyle x=\left[a_{0} ; a_{1}, a_{2}, a_{3}, \dots\right],$ then $\displaystyle \cfrac{1}{x}=\left[0 ;a_0, a_{1}, a_{2}, a_{3}, \dots\right].$

Relation to GL_2 (invertible integers matrices):

$\displaystyle \begin{aligned}&p_{-1}=1, \quad p_{0}=a_{0}, \quad p_{1}=a_{1} p_{0}+p_{-1}=a_{1} a_{0}+1, \quad p_{n}=a_{n} p_{n-1}+p_{n-2} \\&q_{-1}=0, \quad q_{0}=1, \quad q_{1}=a_{1} q_{0}+q_{-1}=a_{1}, \quad q_{n}=a_{n} q_{n-1}+q_{n-2}\end{aligned}$

$\displaystyle \left[a_{0} ; a_{1}, \ldots, a_{n-1}, z\right]=\frac{z p_{n-1}+p_{n-2}}{z q_{n-1}+q_{n-2}}$

$\displaystyle \left[a_{0}, \ldots, a_{n}\right]=\frac{p_{n}}{q_{n}}$

$\displaystyle \begin{aligned} \left[a_{0}, \ldots, a_{n}\right] &=\left[a_{0}, \ldots, a_{n-2}, a_{n-1}+\frac{1}{a_{n}}\right] \\ &=\frac{\left(a_{n-1}+\frac{1}{a_{n}}\right) p_{n-2}+p_{n-3}}{\left(a_{n-1}+\frac{1}{a_{n}}\right) q_{n-2}+q_{n-3}} \\ &=\frac{\left(a_{n-1} a_{n}+1\right) p_{n-2}+a_{n} p_{n-3}}{\left(a_{n-1} a_{n}+1\right) q_{n-2}+a_{n} q_{n-3}} \\ &=\frac{a_{n}\left(a_{n-1} p_{n-2}+p_{n-3}\right)+p_{n-2}}{a_{n}\left(a_{n-1} q_{n-2}+q_{n-3}\right)+q_{n-2}} \\ &=\frac{a_{n} p_{n-1}+p_{n-2}}{a_{n} q_{n-1}+q_{n-2}}=\frac{p_{n}}{q_{n}} \end{aligned}$

$\displaystyle \frac{a}{b}=a_{0}+\frac{1}{a_{1}+\frac{1}{a_{2}+\frac{1}{\cdots \frac{1}{a_{n}}}}}=:\left[a_{0} ; a_{1}, \ldots, a_{n}\right]$

$\displaystyle \left(\begin{array}{c} a \\ b \end{array}\right)=\left(\begin{array}{cc} a_{0} & 1 \\ 1 & 0 \end{array}\right)\left(\begin{array}{cc} a_{1} & 1 \\ 1 & 0 \end{array}\right) \dots\left(\begin{array}{cc} a_{n} & 1 \\ 1 & 0 \end{array}\right)\left(\begin{array}{l} 1 \\ 0 \end{array}\right)$

$\displaystyle \left(\begin{array}{ll} p_{n} & q_{n-1} \\ q_{n} & q_{n-1} \end{array}\right)=\left(\begin{array}{cc} a_{0} & 1 \\ 1 & 0 \end{array}\right)\left(\begin{array}{cc} a_{1} & 1 \\ 1 & 0 \end{array}\right) \cdots\left(\begin{array}{cc} a_{n} & 1 \\ 1 & 0 \end{array}\right)$

$\displaystyle \left|\begin{array}{ll} p_{n} & p_{n-1} \\ q_{n} & q_{n-1} \end{array}\right| =(-1)^{n-1}$

$\displaystyle \frac{p_{n}}{q_{n}}-\frac{p_{n-1}}{q_{n-1}}=(-1)^{n-1} \cdot \frac{1}{q_{n} q_{n-1}}$

$\displaystyle \left|\begin{array}{ll} p_{n} & p_{n-2} \\ q_{n} & q_{n-2} \end{array}\right| =(-1)^{n}a_n$

$\displaystyle \frac{p_{n}}{q_{n}}-\frac{p_{n-2}}{q_{n-2}}=(-1)^{n} \cdot \frac{a_n}{q_{n} q_{n-2}}$

Quadratic Irrationals and periodic continued fractions:

$\displaystyle \cfrac{1+\sqrt{5}}{2}=1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cdots}}}}}$

$\displaystyle x=[\overline{1,2}]=1+\cfrac{1}{2+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{1+\cdots}}}}$

$\displaystyle x=1+\frac{1}{2+x}$

Theorem: An infinite integral continued fraction is periodic if and only if it represents a quadratic irrational.

Proof:

$\displaystyle \implies$ (Easy)

$\displaystyle x=\left[a_{0}, a_{1}, \dots, a_{n}, \overline{a_{n+1}, \dots, a_{n+h}}\right]$

$\displaystyle \alpha=\left[a_{n+1}, a_{n+2}, \ldots\right]$

$\displaystyle \alpha=\left[a_{n+1}, \ldots, a_{n+h}, \alpha\right]$

$\displaystyle \alpha=\frac{\alpha p_{n+h}+p_{n+h-1}}{\alpha q_{n+h}+q_{n+h-1}}$

Multiplying it out, we see $\displaystyle \alpha$ satisfies a quadratic equation. Similarly we have
$\displaystyle x=a_{0}+\frac{1}{a_{1}+\frac{1}{a_{2}+\cdots+\alpha}}$ which also satisfies a quadratic.

$\displaystyle (\Longleftarrow)$ (Lagrange)

$\displaystyle x_{n}=\left[a_{n}, a_{n+1}, \ldots\right]$

$\displaystyle x=\left[a_{0}, a_{1}, \dots, a_{n-1}, x_{n}\right]$

$\displaystyle x=\frac{x_{n} p_{n}+p_{n-1}}{x_{n} q_{n}+q_{n-1}}$

Assume that we have $\displaystyle a x^{2}+b x+c=0 .$
Substitute the above equation to get,

$\displaystyle A_{n} x_{n}^{2}+B_{n} x_{n}+C_{n}=0$

(Symmetric Square representation!)

$\displaystyle \begin{aligned} A_{n} &=a p_{n-1}^{2}+b p_{n-1} q_{n-1}+c q_{n-1}^{2} \\ B_{n} &=2 a p_{n-1} p_{n-2}+b\left(p_{n-1} q_{n-2}+p_{n-2} q_{n-1}\right)+2 c q_{n-1} q_{n-2} \\ C_{n} &=a p_{n-2}^{2}+b p_{n-2} q_{n-2}+c p_{n-2}^{2} \end{aligned}$

$\displaystyle B^{2}-4 A_{n} C_{n}=\left(b^{2}-4 a c\right)\left(p_{n-1} q_{n-2}-q_{n-1} p_{n-2}\right)^{2}=b^{2}-4 a c$

$\displaystyle \left|x-\frac{p_{n-1}}{q_{n-1}}\right|<\frac{1}{q_{n} q_{n-1}}$

$\displaystyle p_{n-1}=x q_{n-1}+\frac{\delta}{q_{n-1}} \quad \text { with }|\delta|<1$

$\displaystyle \begin{aligned} A_{n} &=a\left(x q_{n-1}+\frac{\delta}{q_{n-1}}\right)^{2}+b\left(x q_{n-1}+\frac{\delta}{q_{n-1}}\right) q_{n-1}+c q_{n-1}^{2} \\ &=\left(a x^{2}+b x+c\right) q_{n-1}^{2}+2 a x\delta+a \frac{\delta^{2}}{q_{n-1}^{2}}+b \delta \\ &=2 a x\delta+a \frac{\delta^{2}}{q_{n-1}^{2}}+b \delta \end{aligned}$

$\displaystyle \left|A_{n}\right|=\left|2 a x \delta+a \frac{\delta^{2}}{q_{n-1}^{2}}+b \delta\right|<2|a x|+|a|+|b|$

$\displaystyle \left|C_{n}\right|=\left|A_{n-1}\right|$

$\displaystyle \left|B_{n}\right|=\sqrt{b^{2}-4\left(a c-A_{n} C_{n}\right)}$

All the shifts satisfy quadratic polynomials with bounded coefficients, hence only finitely many possibilities for the shifts. Some two of them have to be equal- Hence periodic!

——————–

What kind of quadratic irrational have purely periodic continued frations (no initial non- periodic string)? Answer: Reduced ${ x >1}$ and the conjugate ${-1<\bar x<0}$

Purely periodic implies reduced is easy to see from the following:
${\alpha=\frac{\alpha p_{n}+p_{n-1}}{\alpha q_{n}+q_{n-1}}}$
${\alpha^{2} q_{n}+\alpha\left(q_{n-1}-p_{n}\right)-p_{n-1}=0}$
${\alpha=\frac{\left(p_{n}-q_{n-1}\right)+\sqrt{\left(p_{n}-q_{n-1}\right)^{2}+4 q_{n} p_{n-1}}}{2 q_{n}}>0}$
${\bar{\alpha}=\frac{\left(p_{n}-q_{n-1}\right)-\sqrt{\left(p_{n}-q_{n-1}\right)^{2}+4 q_{n} p_{n-1}}}{2 q_{n}}<0}$

Theorem: If ${\alpha}$ is a reduced quadratic irrational, then the continued fraction for ${\alpha}$ is purely periodic.

$\displaystyle \alpha=\left[a_{0} ; a_{1}, \ldots, a_{n}, \cdots\right]$

All the shifts

$\displaystyle \alpha_k=\left[a_{k} ; a_{k+1}, \ldots, a_{k+n}, \cdots\right]$

are also reduced.

But it’s easy to see that the number of reduced quadratic irrationals are bounded (in terms of D), hence the sequence is periodic. But to get the full periodicity, use the conditions for reduced quadratics, to get more and more periodicity-eventually getting fully periodic.

For ${\zeta}$ a reduced quadratic irrational, and ${\eta}$ it’s conjugate, we have

$\displaystyle \begin{aligned} \zeta &=[\overline{a_{0} ; a_{1}, a_{2}, \ldots, a_{m-1}}] \\ \frac{-1}{\eta} &=[\overline{a_{m-1} ; a_{m-2}, a_{m-3}, \ldots, a_{0}}] \end{aligned}$

Pell’s equation:

$\displaystyle X^2-DY^2=1$

How does the continued fraction of $\displaystyle \sqrt{D}$ look? How are the solutions to the Pell’s equations related to the continued fractions and the convergents?

$\displaystyle a_0 = [\sqrt{D}]$

$\displaystyle a_0+\sqrt D=\left[2 a_{0}, a_{1}, a_{2}, \ldots\right]=[\overline{2 a_{0}, a_{1}, a_{2}, \ldots, a_{n-1}}]$ is reduced and hence purely periodic.

Therefore $\displaystyle \sqrt{D}=\left[a_{0}, \overline{a_{1}, \ldots, a_{n-1}, 2 a_{0}}\right]$ is the form of the continued fraction.

In fact, we see that

$\displaystyle \sqrt{D}=\left[a_{0} ; \overline{a_{1}, a_{2}, \ldots, a_{2}, a_{1}, 2 a_{0}}\right]$

So the repeating part of the continued fraction is a palindromic block (except the last digit).

$\displaystyle \sqrt{D}=\left[a_{0}, a_{1}, a_{2}, \ldots, a_{k n-1}, x_{k n}\right]$

$\displaystyle x_{k n}=\left[2 a_{0}, \overline{a_{1}, a_{2}, \ldots, a_{n}}\right]=a_{0}+\sqrt{d}$

$\displaystyle \sqrt{D}=\frac{x_{k n} p_{k n-1}+p_{k n-2}}{x_{k n} q_{k n-1}+q_{k n-2}}$

$\displaystyle \sqrt{D}\left(a_{0} a_{k n-1}+q_{k n-2}-p_{k n-1}\right)=a_{0} p_{k n-1}+p_{k n-2}-D q_{k n-1}$

$\displaystyle a_{0} a_{k n-1}+q_{k n-2}=p_{k n-1}, \quad \text { and } \quad a_{0} p_{k n-1}+p_{k n-2}=d q_{k n-1}$

$\displaystyle p_{k n-1}^{2}-d q_{k n-1}^{2}=p_{k n-1} q_{k n-2}-q_{k n-1} p_{k n-2} =(-1)^{kn-2} = (-1)^{kn}$

Therefore convergents in the continued fraction expansion of $\displaystyle \sqrt{D}$ give solutions to Pell’s equation.

Algorithm to compute continued fraction expansion for $\displaystyle \sqrt{D}$ :

$\displaystyle \begin{aligned} &m_{0}=0\\ &d_{0}=1\\ &a_{0}=\lfloor\sqrt{D}\rfloor\\ &m_{n+1}=d_{n} a_{n}-m_{n}\\ &d_{n+1}=\frac{D-m_{n+1}^{2}}{d_{n}}\\ &a_{n+1}=\left\lfloor\frac{\sqrt{D}+m_{n+1}}{d_{n+1}}\right\rfloor=\left\lfloor\frac{a_{0}+m_{n+1}}{d_{n+1}}\right\rfloor \end{aligned}$

Share this:

Related

Leave a comment Cancel reply