Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
Er, what is the difference between the Euclidean algorithm and the “continued fraction algorithm”? I thought they were the same. –  Harald Hanche-Olsen Nov 9 '09 at 21:26
3  
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. –  fedja Nov 9 '09 at 21:46

5 Answers 5

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.

share|improve this answer

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.

share|improve this answer
1  
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. –  Qiaochu Yuan Mar 10 '10 at 5:03
1  
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. –  David Speyer 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.

share|improve this answer

I found this:

...it's always possible to construct a linear recurring sequence of integers s[0], s1, s[2],... 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

for more information about this process.

share|improve this answer

If You are looking for pure arithmetical patterns in continued fractions there is many. For example here You may find some patterns for fractions in "canonical form": regular patterns in continued fractions. Here You may find interesting connections with hypergeometric function for generalized continued fractions: Gauss continued fractions.

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.

So there are possible and known other patterns than periodicity for classical continued fractions.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.