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
Canonical name	ApproximatingAlgebraicNumbersWithLinearRecurrences
Date of creation	2013-03-22 16:53:03
Last modified on	2013-03-22 16:53:03
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	16
Author	rspuzio (6075)
Entry type	Definition
Classification	msc 11B37