Algorithm generalizing continued fractions for non-quadratic algebraic numbers

The continued fraction algorithm generates an integer sequence which terminates for a rational number, is periodic for the roots of irreducible integer quadratics, and is non-periodic for other algebraic numbers. This sequence uniquely determines the number in a useful way, e.g. one can compute convergents and solve Diophantine equations.

Does there exist a corresponding algorithm for, say, roots of irreducible cubics which has similar properties? What about other algebraic numbers? What is known about this? Or to save people time, what phrase should I google to find out the answer?

• Er, what is the difference between the Euclidean algorithm and the “continued fraction algorithm”? I thought they were the same. Nov 9 '09 at 21:26
• You should be more careful about what you want to say: the continued-fraction algorithm generates a periodic integer sequence for all quadratic irrationalities, not just for "square roots". So, I'll take it that you are asking whether there is an algorithm that generates a periodic sequence for algebraic numbers of degree 3 (or should it be "3 and lower"?) but for no other numbers. Nov 9 '09 at 21:46

One generalization is to the theory of sails. If $A$ is an $n\times n$ integer matrix whose eigenvalues are all real, positive, irrational and distinct, a collection of $n$ suitable eigenvectors spans a polyhedral cone which is invariant under $A$. The convex hull of the set of integer lattice points in this cone is a polyhedron, and the vertices of this polyhedron are the best'' integral approximations to the eigenvectors. Also see Arnold, e.g.

MR1704965 (2000h:11012) Arnold, V. I.(RS-AOS) Higher-dimensional continued fractions. (English, Russian summary) J. Moser at 70 (Russian). Regul. Chaotic Dyn. 3 (1998), no. 3, 10--17.

Suppose that r is a positive real number with no nontrivial positive real Galois conjugates. This case includes the case of nth roots of integers. Then it is not difficult to work out the continued fraction of r algorithmically.

Suppose that f(x) is the minimal polynomial of r. The greatest integer of r (which is a_0) is just the largest integer n such that f(n) is negative. Then it's easy to work out the minimal polynomial of 1/(r-a_0) using the fact that the minimal polynomial of the reciprocal is given by reversing the coefficients. Furthermore, 1/(r-a_0) again has the same property as r (no nontrivial positive real Galois conjugates). Now compute a_1 as the largest integer such that f(a_1) is negative. Wash, rinse, repeat.

• I edited the question for wording, so I may have misrepresented it, but I think the intent of the question was whether an analogue of continued fraction representation existed that had e.g. periodicity or other special properties analogous to the periodicity property of the continued fraction for quadratic irrationals. Mar 10 '10 at 5:03
• Moreover, if x is ANY irrational positive real number, you can find rational numbers $(p/q, p'/q')$ so that $p/q < x < p'/q'$, $p'q-p q'=1$ and there is no other Galois conjugate of x in the interval $(p/q, p'/q')$. (Just take a fine enough Farey sequence.) Then $y:=(qx-p)/(p'-q'x)$ is a positive real number none of whose Galois conjugates are positive reals. It is "easy" to recover the continued fraction of x from that of y. Mar 10 '10 at 14:23

I'm surprised that no one has mentioned the Jacobi-Perron algorithm. One might see, for example, Hendy and Jeans, The Jacobi-Perron algorithm in integer form, Math Comp 36 (1981) 565-574, or Tamura and Yasutomi, A new multidimensional continued fraction algorithm, Math Comp 78 (2009) 2209-2222.

I found this:

...it's always possible to construct a linear recurring sequence of integers s, s1, s,... such that any specified algebraic number is approached by some function of the ratio of successive terms s[n+1]/s[n].

see the following:

http://mathpages.com/home/kmath434.htm

It is worth to note, that there are simple patterns among them, for example continued fraction for arithmetic series: $S(p/q) = [p+q; p+2q, p+3q, p+4q, \dots] = \frac{I_{p/q}(2/q)}{I_{1+p/q}(2/q)}$ where $I_{n}(x)$ is the modified Bessel function of the first kind.