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

I know some applications of finite continued fractions. Probably you know more. Can you add anything? (For 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).

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.

share|improve this question
3  
Community wiki? –  Andrey Rekalo Dec 19 '10 at 10:08
3  
We can define an involution from the set $\{\frac p2,\frac p3,\ldots,\frac p{2n}\}$ by following formula $$\frac pk=[a_0;a_1,\ldots,a_s]\to \frac pl=[a_s;a_{s-1},\ldots,a_0].$$ Cardinality of this set is odd. It means that involution has a fixed point $\frac pk=[a_0;a_1,\ldots,a_1,a_0]$. Number of partial quotients is even (else we have contradiction with primality of p). Hence \begin{gather*} p=K(a_0,a_1,…,a_m,a_m,\ldots,a_1,a_0)=\\= K(a_0;a_1,\ldots,a_m)K(a_m,\ldots,a_1,a_0)+K(a_0;a_1,\ldots,a_{m-1})K(a_{m-1},\l‌​dots,a_1,a_0)=\\=a^2+b^2, \end{gather*} where $K$ are continuants. –  Alexey Ustinov Jan 4 '11 at 7:09
1  
Using continued fractions to express $p\equiv-1\pmod4$ as sum of 2 squares goes back to Hermite - see John Brillhart, Note on representing a prime as a sum of two squares, Math Comp 26 (1972) 1011-1013. But what you have is different, an existence proof rather than an algorithm, and I don't know the history. –  Gerry Myerson Feb 20 '11 at 11:30
1  
@Alexey, it may go all the way back to H J S Smith, De compositione numerorum primorum formae $4\lambda+1$ ex duobus quadratis, Crelle 50 (1855) 91-92. See Dekking, Mendes France, and van der Poorten, FOLDS! II, Math Intel 4 (1982) 173-181. –  Gerry Myerson Feb 20 '11 at 11:49
1  
Thank you, Gerry. There is one more sourse: bearspace.baylor.edu/Lance_Littlejohn/www/smithfv.pdf –  Alexey Ustinov Feb 22 '11 at 6:08
show 4 more comments

14 Answers 14

up vote 12 down vote accepted

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.

share|improve this answer
    
Thank you, Paolo, very interesting application. –  Alexey Ustinov Dec 19 '10 at 14:04
1  
(Note: everything that I'm going to say has to be taken up to switching $p$ and $q$ and up to signs) It's probably worth pointing out the following fact. To each rational tangle one can associate a closed 2-bridge knot/link: this is obtained by connecting the two bottom (respectively top) endpoints of the tangle by unknotted arcs in the bottom (resp. top) part of the picture. This gives an association $p/q\leadsto T(p/q)\stackrel{\rm def}{\leadsto}K(p/q)$. The double cover of $S^3$ branched over $K(p/q)$ is the lens space $L(p,q)$. –  Marco Golla Apr 6 '11 at 17:21
add comment

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

share|improve this answer
    
Yes, I asked about continued fractions for numbers. Nevetheless Padé approximants are good example because you can replace your variable by $p$ and you will get best $p$-adic approximation for a given number. But this example is not exactly ``finite''. –  Alexey Ustinov Dec 19 '10 at 10:41
add comment

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.

share|improve this answer
    
Mention might also be made of Shanks' SQUFOF (SQUare FOrm Factoring) algorithm, not as powerful as the others but factored $n$ doing arithmetic on numbers the size of $\sqrt n$, so you could factor 20-digit numbers on a 10-digit calculator without writing double-precision routines. It, too, was based on the expansion of $\sqrt n$ (and not on the periodicity thereof). –  Gerry Myerson Feb 20 '11 at 4:35
    
The idea of finding a solution to $x^2-ny^2=d^2$ is actually a variant of SQUFOF. CFRAC does better by combining many $x^2-ny^2=d$ to get $x^2\cong z^2$. See Cohen. –  Dror Speiser Feb 20 '11 at 7:16
add comment

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.

share|improve this answer
    
The quantum algorithm relies on continued fractions as well. –  Steve Huntsman Dec 20 '10 at 1:17
    
Steve, can you give a reference? –  Alexey Ustinov Dec 20 '10 at 3:47
2  
See step 5 under en.wikipedia.org/wiki/… –  Steve Huntsman Dec 20 '10 at 5:01
add comment

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.

share|improve this answer
    
Let me add this application to the trivial list. –  Alexey Ustinov Feb 20 '11 at 6:53
2  
Another version of this is the 'batting average' problem, as it appears in Knuth's The Art of Computer Programming (vol. 2): what's the fewest number of at bats a baseball player can have if their average (rounded to 3 decimals) is .334? (The solution proceeds by computing the CFs for $.3335 = 667/2000 = [0; 2, 1, 666]$ and $.3345 = 669/2000 = [0; 2, 1, 94, 1, 1, 3]$ - the correct answer is then found by finding the fraction for the 'simplest' number in that range, $[0; 2, 1, 95]$ - namely, $\frac{96}{287}\approx 0.334495$.) –  Steven Stadnicki Jan 18 at 9:14
add comment

Reverse slam dunk

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.)

share|improve this answer
    
Kelly, do you know more available (downloadable) reference? –  Alexey Ustinov Feb 20 '11 at 16:09
1  
I've not read math/0311380 in its entirety, only the bit dealing with slam dunking, but Proposition 3 of the above paper defines the term slam-dunk. In addition Figure 8 of the same paper shows the effect of a slam-dunk on the surgery diagram of a three-manifold. A reverse slam-dunk is simply reading Figure 8 from right-to-left instead of left-to-right. –  Kelly Davis Feb 20 '11 at 16:44
    
Note, if you follow the link to "4-Manifolds and Kirby Calculus", click on "search inside this book", search on "slam", click on the result for page 163, then you'll see the same diagram as Figure 8 from above. Also, the next page, 164, which contains Example 5.3.9(c), is also in the preview. –  Kelly Davis Feb 20 '11 at 20:08
    
Thank you. This book also available at avaxhome.ws –  Alexey Ustinov Feb 21 '11 at 3:28
    
Just found a typo in the above. It's Example 5.3.9(b) not Example 5.3.9(c). –  Kelly Davis Feb 21 '11 at 7:27
add comment

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

share|improve this answer
    
As I understand you algorithm is not really finite. You can solve Hesselink's problem for any real points. You use geometrical inerpretation of continued fractions. And this approach is more general (see discussion on How to find a closest integer point to intersection of two lines? here mathoverflow.net/questions/22777/… Generalisation of continued fraction algorithm on inhomogeneous case also known as Delone's “divided cells” algorithm, but details are not cleare for me. –  Alexey Ustinov Feb 21 '11 at 3:13
    
For me the continued fraction algorithm for approximating a rational number is really finite. It stops. My contribution is the proof of a theorem. It is not about how to construct something. The theorem is about lattice points. It would be wrong for real points. The proof exploits well known geometric properties of the continued fraction algorithm. –  Wilberd van der Kallen Feb 22 '11 at 15:19
add comment

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

share|improve this answer
add comment

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".

share|improve this answer
add comment

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

share|improve this answer
add comment

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 .

share|improve this answer
add comment

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.

share|improve this answer
    
Yes, it is relates to 5) and 8) but I agree that this application should be mentioned separately. –  Alexey Ustinov Feb 20 '11 at 6:51
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.