Easiest way to find the polynomial satisfied by a continued fraction representation

Question

Given a repeating simple continued fraction $x = [a_{0};a_{1}, \ldots]$, what is the easiest way to find the (quadratic) polynomial satisfied by it? Certainly, you can just do it by hand. For example, the number $x = [\overline{2}]$ satisfies the equation $x = 2 + \frac{1}{x}$, which is straightforward to manipulate into a quadratic. What I am looking for is a formula - a direct way to write down the polynomial without having to do the calculation. I can't seem to find a reference for this, but I suspect it exists somewhere. Thanks!

Answer 1

For a purely periodic cf of even length there is a sort of answer. For a "partial quotient" $a_i = \delta$ we are given the two by two matrix $$ \left( \begin{array}{cc} 0 & 1 \\ 1 & \delta \end{array} \right) $$ Notice that the determinant is $-1.$ The product of an even number of these ( each new one goes on the right) gives a product with determinant $+1.$ Call this $P.$ The quadratic form you want has Hessian matrix $H,$ currently not known. The relation is $$ P^T H P = H; $$ we call $P$ an automorphism matrix.

In the other direction, given a quadratic form $f(x,y) = A x^2 + B xy + C y^2$ with Hessian matrix $H,$ many number theory books show how to use the (smallest positive) solution of $\tau^2 - \Delta \sigma^2 = 4$ to construct $P,$ where $\Delta = B^2 - 4 AC $ is positive but not a square.

My favorite book on this is Binary Quadratic Forms by Duncan A. Buell.

Answer 2

I don't think it can be done.

Say the periodic part of $x=[0; a_1,\dots]$ is $a_1,\dots,a_n$. Then you have $x=[0; a_1,\dots,a_n,x]$. By the usual formulas with the $p_j$ and the $q_j$, you can manipulate this into $x=(ax+b)/(cx+d)$ for some integers $a,b,c,d$, and then solve the quadratic. I doubt you can do any better than this, in general.

Answer 3

I think I've come up with a roughly satisfying answer. As Gerry Myerson pointed out, if we can write $x = [\overline{a_{1}; a_{2}, \ldots a_{n}}]$, (i.e. assuming the expansion for $x$ is purely periodic) then we can also write $x = [a_{1};a_{2}, \ldots a_{n},x]$. That means, by the usual recurrence relation of the convergents, $x = \frac{xp_{n} + p_{n-1}}{xq_{n} + q_{n-1}}$. This gives a relatively simple equation to solve, regardless of how large $n$ is. However, there is a determinant formula for the convergents of a continued fraction (http://mathworld.wolfram.com/Convergent.html). Specifically, $p_{n}$ is the determinant of the tridiagonal matrix $\left| \begin{matrix} a_{1} & -1 & 0 & \ldots \\ 1 & a_{2} & -1 & \ldots \\ 0 & 1 & a_{3} & \ldots \\ \ldots & \ldots & \ldots & \ldots \end{matrix} \right|$. You can combine these to give a reasonably closed formula for the equation satisfied by $x$.

Edit: Corrected thanks to the comment below - this seems to work directly only for pure periodic continued fractions. I can see one other very special case:

If $x = [a_{1};\overline{a_{2}}]$ and $[a_{2};\overline{a_{2}}]$ is a root of $f(t)$, then $x$ is a root of $f(t-a_{1}+a_{2})$. But I don't immediately see how to generalize past that special case.