33
$\begingroup$

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.

$\endgroup$
10
  • 4
    $\begingroup$ 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. $\endgroup$ Jan 4, 2011 at 7:09
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 20, 2011 at 11:30
  • 1
    $\begingroup$ @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. $\endgroup$ Feb 20, 2011 at 11:49
  • 1
    $\begingroup$ Thank you, Gerry. There is one more source: bearspace.baylor.edu/Lance_Littlejohn/www/smithfv.pdf $\endgroup$ Feb 22, 2011 at 6:08
  • 1
    $\begingroup$ @GerryMyerson "There are two hard things in Computer Science, cache invalidation, naming things, and off by one errors.". $\endgroup$ May 14, 2023 at 13:20

21 Answers 21

22
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ (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)$. $\endgroup$ Apr 6, 2011 at 17:21
14
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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''. $\endgroup$ Dec 19, 2010 at 10:41
12
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$ Feb 20, 2011 at 4:35
  • $\begingroup$ 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. $\endgroup$ Feb 20, 2011 at 7:16
11
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Let me add this application to the trivial list. $\endgroup$ Feb 20, 2011 at 6:53
  • 4
    $\begingroup$ 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$.) $\endgroup$ Jan 18, 2014 at 9:14
  • 1
    $\begingroup$ I wonder whether there is an analogue of this for rational functions - say given a series expansion with algorithmically given coefficients, whether one may detect a linear recurrence if one of the convergents is suddenly divisible by a very high power of the variable or something like that... $\endgroup$ Jan 14, 2018 at 4:03
8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The quantum algorithm relies on continued fractions as well. $\endgroup$ Dec 20, 2010 at 1:17
  • $\begingroup$ Steve, can you give a reference? $\endgroup$ Dec 20, 2010 at 3:47
  • 2
    $\begingroup$ See step 5 under en.wikipedia.org/wiki/… $\endgroup$ Dec 20, 2010 at 5:01
6
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Kelly, do you know more available (downloadable) reference? $\endgroup$ Feb 20, 2011 at 16:09
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 20, 2011 at 16:44
  • $\begingroup$ 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. $\endgroup$ Feb 20, 2011 at 20:08
  • $\begingroup$ Thank you. This book also available at avaxhome.ws $\endgroup$ Feb 21, 2011 at 3:28
  • $\begingroup$ Just found a typo in the above. It's Example 5.3.9(b) not Example 5.3.9(c). $\endgroup$ Feb 21, 2011 at 7:27
6
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Feb 21, 2011 at 3:13
  • $\begingroup$ 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. $\endgroup$ Feb 22, 2011 at 15:19
4
$\begingroup$

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 .

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, it is relates to 5) and 8) but I agree that this application should be mentioned separately. $\endgroup$ Feb 20, 2011 at 6:51
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

[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}$$

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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