15

18

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

flag
3 
 Community wiki? – Andrey Rekalo Dec 19 2010 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},\ldots,a_1,a_0)=\\=a^2+b^2, \end{gather*} where $K$ are continuants. – Alexey Ustinov Jan 4 2011 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 2011 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 2011 at 11:49
1 
 Thank you, Gerry. There is one more sourse: bearspace.baylor.edu/Lance_Littlejohn/www/… – Alexey Ustinov Feb 22 2011 at 6:08
show 4 more comments

12 Answers

8

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.

link|flag
Thank you, Paolo, very interesting application. – Alexey Ustinov Dec 19 2010 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 2011 at 17:21
7

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

link|flag
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 2010 at 10:41
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.

link|flag
The quantum algorithm relies on continued fractions as well. – Steve Huntsman Dec 20 2010 at 1:17
Steve, can you give a reference? – Alexey Ustinov Dec 20 2010 at 3:47
2 
 See step 5 under en.wikipedia.org/wiki/… – Steve Huntsman Dec 20 2010 at 5:01
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.

link|flag
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 2011 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 2011 at 7:16
3

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.

link|flag
Let me add this application to the trivial list. – Alexey Ustinov Feb 20 2011 at 6:53
3

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

link|flag
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 2011 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 2011 at 15:19
3

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

link|flag
Kelly, do you know more available (downloadable) reference? – Alexey Ustinov Feb 20 2011 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 2011 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 2011 at 20:08
Thank you. This book also available at avaxhome.ws – Alexey Ustinov Feb 21 2011 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 2011 at 7:27
1

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 .

link|flag
1

When resolving singularities in toric surfaces, one looks for some subdivision $\Delta'$ of the defining fan $\Delta \subset \mathbb{R}^2$ of the surface. Such a subdivision corresponds to a proper birational map $X(\Delta')\to X(\Delta)$, giving the resolution of singularities. The 1-dimensional rays of this subdivision is found using the Hirzebruch-Jung continued fractions.

As Alexey remarks, the convergents of this continued fraction gives the vertices of the convex hull of $(\Delta\cap \mathbb{Z}^2)\setminus {(0,0)}$. The above image is taken from Jon Voigt's paper

link|flag
Rodseth used the same (reduced regular) continued fractions. They describe the convex hull of non-zero lattice points from first quadrant. Probably this problem should be added to the list of application as well. – Alexey Ustinov Dec 19 2010 at 12:15
More generally, the same continued fraction shows up in the resolution of cyclic quotient singularities of surfaces, i.e. singularities analytically isomorphic to $C^2/G$, with $G$ cyclic. – rita Dec 20 2010 at 7:36
@rita: Yes you are right, and as you probably know, all toric surface singularities are cyclic. – J.C. Ottem Dec 20 2010 at 9:56
1

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.

link|flag
Yes, it is relates to 5) and 8) but I agree that this application should be mentioned separately. – Alexey Ustinov Feb 20 2011 at 6:51
1

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

link|flag
1

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.

link|flag

Your Answer

Get an OpenID
or

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