Applications of finite continued fractions

Question

I know some applications of finite continued fractions. Probably you know more. Can you add anything? (For Applications of periodic continued fractions I have made a special topic.)

1) (Trivial) Analysis of Euclidean algorithm (and its variants). This item includes extended Euclidean algorithm, calculation of $a^{-1}\pmod n$, lattice reduction, number recognition (Andreas Blass), parametrization of solution of the equation $ad-bc=N$, calculation of convex hull of non-zero lattice points from first quadrant etc.

2) Decomposition of prime $p=4n+1$ to the sum of two squares.

3) Rodseth's formula for Frobenius numbers with three arguments.

4) Analysis of Frieze Patterns from The Book of Numbers (Conway, J. H. and Guy, R. K.)

5) Calculation of goodness (dicrepancy or something similar) of 2-dimesional lattice rules for numerical integration.

6) Singularitie resolution in toric surfaces (added by J.C. Ottem).

7) Classification of rational tangles (added by Paolo Aceto).

8) Calculation of Dedekind sums.

9) Calculation of the number of A-graded algebras (V.I. Arnold A-graded algebras and continued fractions)

10) Asymptotic behavior of a curve in $\mathbb{R}^n$ with constant curvature $k_1$, constant second curvature $k_2$, ... (till constant curvature $k_{n-1}$). (V.I. Arnold)

11) The way to attack (discovered by Michael J. Wiener) RSA public key crypto system with small private exponents (added by jp).

12) DDA-algorithm for converting a segment into a nice-looking sequence of pixels. Another algorithms of integer linear programming: finding a “closest points” in a given halfplane (added by Wilberd van der Kallen).

13) Analysis of Lehmer pseudo-random number generator (added by Gerry Myerson). See U. Dieter. Pseudo-random numbers. The exact distribution of pairs and Knuth D. E. The art of computer programming. Volume 2 (Theorem D, section 3.3.3).

14) Bach and Shallit show how to compute the Jacobi symbol in terms of the simple continued fraction (Bach, E. and Shallit, J. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. Cambridge, MA: MIT Press, pp. 343-344, 1996.)

15) A criterion for a rectangle to be tilable by rectangles of a similar shape. Construction of alternating-current circuits with given properties (added by M. Skopenkov).

16) Slam dunking of rational surgery diagrams for a three-manifolds (added by Kelly Davis).

17) CF allows to predict digets in $1/M$ random number generator, see Blum, L.; Blum, M. & Shub, M. A simple unpredictable pseudo-random number generator. SIAM J. Comput., 1986, 15, 364-383.

18) Asymptotic analysis of incomplete Gauss sums (theta sums) (Fiedler, H.; Jurkat, W. & Koerner, O. Asymptotic expansions of finite theta series. Acta Arith. , 1977, 32, 129-146; J. Marklof, Theta sums, Eisenstein series, and the semiclassical dynamics of a precessing spin, in: D. Hejhal, J. Friedman, M. Gutzwiller and A. Odlyzko (eds.), Emerging Applications of Number Theory, IMA Volumes in Mathematics and its Applications, Volume 109 (Springer, New York, 1999) pp. 405-450)

19) The statistics of the trajectory of Sinai billiard in a flat two-torus, see Boca, Gologan, Zaharescu and Bykovskii, Ustinov.

20) Analysis of "linear" permutations (from Zolotarev's proof of quadratic reciprocity law).

21) Calculation of quadratic character sums with polynomial arguments.

22) The signature of a generic symmetric integral matrix can be expressed as a finite continued fraction (added by Andrew Ranicki).

23) Lehman's algorithm for factoring large integers.

Answer 1

In knot theory continued fractions are used to classify rational tangles. Conway proved that two rational tangles are isotopic if and only if they have the same fraction. This is proved by Kauffman in http://arxiv.org/pdf/math/0311499.pdf. The paper also contains all the basic definitions and I think it can be read by any mathematician.

Answer 2

You did not limit the context of continued fractions to numbers. Did you ? Then continued fractions can be used whenever you have a Euclidian division, preferably when there is a natural choice of quotient / remainder, so that it is done in a unique way. An important example is that of polynomials. Then continued fractions can be used to find accurate approximations of smooth functions by rational fractions about a given point, say $x=0$. This is related to Padé approximants.

This is described in the French wikipedia page (sorry, not in the English one) link text

Answer 3

One of the first factorization algorithms beyond trial division and Fermat's method was CFRAC: from the continued fraction expansion of $\sqrt{n}$ one computed solutions $x^2 - ny^2 = d^2$ and then had the (possibly trivial) factor $\gcd(n,x-d)$ of $n$. It is the father of the quadratic seive method.

Answer 4

Here's a lower-level but still useful application. A student came to me with some computer-produced 10-digit (maybe more than 10, I don't remember exactly) floating-point numbers, which I suspected were actually (approximations to) some fairly reasonable rational numbers (with denominators in the 3- or 4-digit range). A way to get those rational numbers, if they exist, is to start computing the continued fraction expansion of the floating-point numbers, until you get an exceptionally large denominator. Then pretend that denominator is $\infty$, i.e., truncate the continued fraction at that point.

Answer 5

The first attacks (discovered by Michael J. Wiener) against using small private exponents in the RSA public key crypto system were based on continued fractions. Better attacks are now obtained with the help of the LLL-algorithm.

Answer 6

Reverse slam dunk http://lakers.topbuzz.com/gallery/d/272643-1/Kobe+Bryant+reverse+slam+dunk+in+the+2009+preseason.JPG

Reverse slam dunking any rational surgery diagram for a three-manifold into an integral surgery diagram for the same three manifold. (See for example the end of Exercise 5.3.9(b) in 4-Manifolds and Kirby Calculus by Stipsicz and Gompf.)

Answer 7

in 2008, an interesting applications of continued fraction to the theory of (generalized) root systems was found by Cuntz and Heckenberger. This result is obtained as a consequence of a deep connection between continued fractions and finite Weyl groupoids of rank two.

As you may expect, the notions of generalized root system and Weyl groupoids are related. Weyl groupoids are the right choice for studying certain aspects of Lie superalgebras (see this MO question). Weyl groupoids are also very important for the structure and the classification of an interesting family of braided Hopf algebras known as Nichols algebras.

Here you have the reference:

Cuntz, Michael; Heckenberger, István. Weyl groupoids of rank two and continued fractions. Algebra Number Theory 3 (2009), no. 3, 317--340. MR2525553 (2010h:20082), link, arXiv

Answer 8

Wim Hesselink posed a problem motivated by image processing of a discretized picture. I found that it was helpful to consider the convergents in a continued fraction approximation of rational numbers. See link text

Answer 9

Along the lines of the relationship between continued fractions and Padé approximants, there is the acceleration of convergence of slowly converging series and the summation of divergent series. These generally run along the idea of computing continued fractions from formal power series. Among the various algorithms developed from this approach are the epsilon algorithm and the Lanzcos algorithm .

Answer 10

In 3-dimensional contact geometry, every contact rational surgery is equivalent to a sequence of $\pm 1$-surgeries on a link, determined by the continued fraction expansion of a function of the slope.

I think the result is originally due to Ding and Geiges, and is explained here (section 5). A similar scheme appears in the classification of tight contact structures on lens spaces, due to Honda (see here). Ozbagci and Stipsicz give a pleasant exposition of both (and many other) results in their book "Surgery on contact 3-manifolds and Stein surfaces".

Answer 11

I like the application to the study of equal tempered musical scales, which, for example, leads to an the explanation of why (and in what sense) the standard scale of 12 semitones is optimal. A web search for "music, continued fractions" reveals lots of references. This one has some ideas that were new to me: http://doctroid.wordpress.com/2009/04/13/generalized-continued-fractions-and-equal-temperament

Answer 12

Jürgen Moser used finite contined fractions (functional Stieltjes contined fractions) in his solution of the open Toda lattice

Answer 13

Related to 5) and 8), measurements of how random a Lehmer pseudo-random number generator $x_{n+1}\equiv ax_n+b\pmod m$ might be. Work of Dieter in the 1970s, I think it's also in Knuth's Art of Computer Programming in the section on random numbers.

Answer 14

M. Skopenkov gave a reference to criterion for a rectangle to be tilable by rectangles of a similar shape: C. Freiling, D. Rinne, Tiling a square with similar rectangles, Math. Res. Lett. 1 (1994) 547–558; M. Laczkovich, G. Szekeres, Tiling of the square with similar rectangles, Discrete Comput. Geom. 13 (1995) 569–572. This results related to construction of alternating-current circuits with given properties M. Prasolov, M. Skopenkov, Tiling by rectangles and alternating current, Journal of Combinatorial Theory, Series A 118 (2011) 920–937.

Answer 15

Let $(a,b)=1$, $\pi(x)=ax\pmod b$ and $I(a,b)$ denote the number of inversions of permutation $$(0,1,\ldots, b-1)\to(\pi(0),\pi(1),\ldots,\pi (b-1)).$$ Zolotarev proved quadratic reciprocity law using formula $$\left(\frac ab\right)=(-1)^{I(a,b)}.$$ Meyer (see Über einige Anwendungen Dedekindscher Summen, 1957) proved that $$I(a,b)=-3s(a,b)+\frac{(b-1)(b-2)}2,$$ where $$s(a,b)=\sum_{k=1}^b\left\|\frac{ak}b\right\|\cdot\left\|\frac{k}b\right\|$$ is a Dedekind sum. If $a/b=[0;a_1,\ldots,a_n]$ is a regular continued fraction expansion, then (Barkan-Hickerson-Knuth formula) $$12s(a,b)=\sum_{j=1}^n(-1)^{j-1}a_j+\frac{a+a^*}b-3,$$ where $aa^*=1\pmod b$ and $0<a^*<b$. This links continued fractions with properties of permutations.

Answer 16

The signature of a generic symmetric integral matrix can be expressed as a finite continued fraction. Indeed, Sylvester introduced the notion of signature (or rather the inertia) of a symmetric integral matrix by considering this expression. See the paper "Signatures in algebra, topology and dynamics" by Etienne Ghys and myself in Volume 30 of Ensaios Matematicos http://ensaios.sbm.org.br/contents for the expression, and the history.

Answer 17

Nearest integer continued fractions (NICF) can be applied to analysis of number's spectra and "eta-sequences". The spectrum of a real number is defined to be an infinite multiset of integers (see "Concrete mathematics") $$\rm{Spec}(\alpha) = \{\lfloor \alpha\rfloor,\lfloor 2\alpha\rfloor,\lfloor 2\alpha\rfloor,\ldots\},$$ and "eta-sequences" (see Some unpublished notes of Hofstadter) is defined by $$\eta_k(\alpha)=\lfloor (k+1)\alpha\rfloor-\lfloor k \alpha\rfloor.$$ This sequence has nice quasi-periodic structure and consists of segments of 2 types. Replacing these two segments by "1" and "2" we get new eta-sequence corresponding to $\alpha'=\min\{\{\frac1{\alpha}\},1-\{\frac1{\alpha}\}\}$. Such transformation is equivalent to one step in NICF expansion of $\alpha$. For example $$\eta(\sqrt2)=\{(1,2),(1,2),(1,1,2),(1,2),(1,1,2),(1,2),(1,2),(1,1,2),\ldots\}\to\\\to\{1,1,2,1,2,1,1,2,...\}.$$

This example is not purely finite but somehow interesting.

Answer 18

Sturm's theorem which counts real roots of given polinomial in arbitrary interval. A similar application by A. G. Khovanskii: calculation of topological degree of some univariate rational function. Original publication A. Khovanskii and Y. Burda. Degree of rational mapping, and the theorems of Sturm and Tarski. Journal of Fixed Point Theory and Applications. V.3, No.1, 2008, 79–93.

Answer 19

[Lidl, R. & Niederreiter, H. Finite fields, pp. 237-239.]

For $q$ odd, put $G(x) = x^q - x$, let $f\in\mathbb{F}_q[x]$ be a polynomial of positive degree with no roots in $\mathbb{F}_q$, and set $F(x) = f(x)^{(q-1)/2}.$ Consider the continued fraction expansions $$\frac{F ( x ) - 1}{G(x)} = [ A_0,A_1,\ldots,A_s]$$ and $$\frac{F ( x ) + 1}{G(x)} = [ a_0,a_1,\ldots,a_t].$$ It is clear that $A_0 = a_0$. Define $n_f$ to be the largest integer $m$ such that $A_i = a_i$ for $i = 0,1,\ldots,m$.

5.59. Lemma. Either $n_f= s = t-1$ or $n_f = t = s - 1$.

5.60. Theorem. Let $\eta$ be the quadratic character of $\mathbb{F}_q$, $q$ odd, and let $f\in\mathbb{F}_q[x]$ be apolynomial of positive degree with no roots in $\mathbb{F}_q$. Then $$\sum_{c\in\mathbb{F}_q}\eta(f(c))=\begin{cases}\mathrm{deg}(a_t),&\text{if }n_f=s,\\-\mathrm{deg}(A_s),&\text{if }n_f=t. \end{cases}$$

Answer 20

In the article Factoring large integers Lehman proposed a modification of Fermat's difference of squares method for factoring large integers. This modification permits factoring $n$ in $ O({n^{1/3}})$ elementary operations. Justification of this algorithm is based on finite continued fractions.

Answer 21

Cornacchia's algorithm for solving the Diophantine equation $x^{2}+dy^{2}=m$. See for details On Cornacchia’s algorithm for solving the diophantine equation $x^{2}+dy^{2}=m$ by F. Morain and J.-L. Nicolas, and On Cornacchia’s Algorithm by Y. Motohashi.