# approximating algebraic numbers with linear recurrences

Linear recurrences can be used to obtain rational approximations for real algebraic numbers. Suppose that $\rho$ is the root of a polynomial $p(x)=\sum_{k=0}^{n}c_{k}x^{k}$ with rational coefficients $c_{k}$ and further assume that the roots of $p$ are distinct and that all the other roots of $p$ are strictly smaller in absolute value than $\rho$.

Consider the recursion

 $\sum_{k=0}^{n}c_{k}a_{m+k}=0.$

As discussed in the parent entry, the solution of this recurrence is

 $a_{m}=\sum_{k=1}^{n}b_{k}r_{k}^{m},$

where $r_{1},\ldots,r_{n}$ are the roots of $p$ — let us agree that $r_{1}=\rho$ — and the $b_{k}$’s are determined by the initial conditions of the recurrence. If $b_{1}\neq 0$, we have

 ${a_{m+1}\over a_{m}}={b_{1}\rho^{m+1}+\sum_{k=2}^{n}b_{k}r_{k}^{m+1}\over b_{1% }\rho^{m}+\sum_{k=1}^{n}b_{k}r_{k}^{m}}=\rho{1+\sum_{k=2}^{n}\left({b_{k}\over b% _{1}}\right)\left({r_{k}\over\rho}\right)^{m+1}\over 1+\sum_{k=2}^{n}\left({b_% {k}\over b_{1}}\right)\left({r_{k}\over\rho}\right)^{m}}.$

Because $|\frac{r_{k}}{\rho}|<1$ when $k>1$, we have $\lim_{m\to\infty}(r_{k}/\rho)^{m}=0$, and hence

 $\lim_{m\to\infty}{a_{m+1}\over a_{m}}=\rho.$

To illustrate this method, we will compute the square root of two. Now, we cannot use the equation $x^{2}-2=0$ because it has two roots, $+\sqrt{2}$ and $-\sqrt{2}$, which are equal in absolute value. So what we shall do instead is to use the equation $(x-1)^{2}=2$, or $x^{2}-2x-3=0$, whose roots are $1-\sqrt{2}$ and $1+\sqrt{2}$. Since $|1+\sqrt{2}|>|1-\sqrt{2}|$, we can use our method to approximate the larger of these roots, namely $1+\sqrt{2}$; to approximate $\sqrt{2}$, we subtract $1$ from our answer. The recursion we should use is

 $a_{m+2}-2a_{m+1}-a_{m}=0$

or, moving terms around,

 $a_{m+2}=2a_{m+1}+a_{m}.$

If we choose $b_{1}=-b_{2}=1/(2\sqrt{2})$, then we have

 $\displaystyle a_{0}$ $\displaystyle=b_{1}\left(1+\sqrt{2}\right)^{0}+b_{2}\left(1-\sqrt{2}\right)^{0% }=b_{1}+b_{2}=0$ $\displaystyle a_{1}$ $\displaystyle=b_{1}\left(1+\sqrt{2}\right)^{1}+b_{2}\left(1-\sqrt{2}\right)^{1% }=b_{1}+b_{2}+(b_{1}-b_{2})\sqrt{2}=1.$

Starting with these values, we obtain the following sequence:

 $\displaystyle a_{0}$ $\displaystyle=0$ $\displaystyle a_{1}$ $\displaystyle=1$ $\displaystyle a_{2}$ $\displaystyle=2$ $\displaystyle a_{3}$ $\displaystyle=5$ $\displaystyle a_{4}$ $\displaystyle=12$ $\displaystyle a_{5}$ $\displaystyle=29$ $\displaystyle a_{6}$ $\displaystyle=70$ $\displaystyle a_{7}$ $\displaystyle=169$ $\displaystyle a_{8}$ $\displaystyle=408$ $\displaystyle a_{9}$ $\displaystyle=985$ $\displaystyle a_{10}$ $\displaystyle=2738$ $\displaystyle a_{11}$ $\displaystyle=5741$ $\displaystyle a_{12}$ $\displaystyle=13860$

Therefore, as our approximations to $\sqrt{2}$, we have

 $1,\frac{3}{2},\frac{7}{5},\frac{17}{12},\frac{41}{29},\frac{99}{70},\frac{239}% {169},\frac{577}{408},\frac{1753}{985},\frac{3003}{2738},\frac{8119}{5741}.$

By making suitable transformations, one can compute all the roots of a polynomial using this technique. A way to do this is to start with a rational number $h$ which is closer to the desired root than to the other roots, then make a change of variable $x=1/(y+h)$.

As an example, we shall examine the roots of $x^{3}+9x+1$. Approximating the polynomial by leaving off the constant term, we guess that the roots are close to $0$, $+3i$, and $-3i$. Since the two complex roots are conjugates, it suffices to find one of them.

To look for the root near $0$, we make the change of variable $x=1/y$ to obtain $y^{3}+9y^{2}+1=0$, which gives the recursion $a_{k+3}+9a_{k+2}+a_{k}=0$. Picking some initial values, this recursion gives us the sequence

 $0,0,1,-9,81,-738,6723,-61236,557766,-5090401,\ldots,$

whence we obtain the approximations

 $-\frac{1}{9},-\frac{1}{9},-\frac{81}{738},-\frac{738}{6723},-\frac{6723}{61236% },-\frac{61236}{557766},-\frac{557766}{5090401},\ldots.$

To look for the root near $3i$, we make the change of variable $x=1/(y+3i)$ to obtain $y^{3}+(9+9i)y^{2}+(-27+54i)y+82-27i=0$, which gives the recursion

 $a_{k+3}+(9+9i)a_{k+2}+(-27+54i)a_{k+1}+(82-27i)a_{k}=0.$

Picking some initial values, this recursion gives us the sequence

 $0,\,0,\,1,\,-9-9i,\,27+108i,\,-82-945i,\,-225+11196i,\,44415-127953i,\ldots,$
Title approximating algebraic numbers with linear recurrences ApproximatingAlgebraicNumbersWithLinearRecurrences 2013-03-22 16:53:03 2013-03-22 16:53:03 rspuzio (6075) rspuzio (6075) 16 rspuzio (6075) Definition msc 11B37