Let $a,b \in \mathbb{N} \ \ s.t. \ \ a > b$ have $\gcd(a,b) =1$. We can define the Hirzebruch-Jung modified euclidean algorithm as follows:

Let $e_i \in \mathbb{N} >2$, and $ r_k \in \mathbb{N}$ where $0\le r_k<r_{k-1}$. Then we can do the following procedure (analogous to the standard Euclidean algorithm): $$ \begin{array}{rcl} a &= & e_1b -r_1\\ b &= & e_2r_1 - r_2\\ r_1 &= &e_3r_2 -r_3\\ &...\\ r_{k-2} &= &e_ir_{k-1} = e_i \end{array}$$ That last line is true because the $\gcd(a,b) =1$, by hypothesis.

Considering that the greatest common divisor is known by hypothesis, what is the utility of this modified Euclidean algorithm, and what was the motivation for its development? I have heard that it has applications to toric geometry, but I am not familiar with those.

  • 2
    $\begingroup$ Presumably, the procedure includes the specification, $0\le r_i<r_{i-1}$. The procedure bears the same relation to what might be called "negative-regular" continued fractions, as the usual Euclidean procedure bears to the usual continued fractions. $\endgroup$ – Gerry Myerson Oct 16 '15 at 4:56
  • $\begingroup$ @GerryMyerson Yes, I forgot to add that specification, but it is indeed required. I have edited the question accordingly. I presume by the "usual fractions" and such you mean what is described here ? $\endgroup$ – Juan Sebastian Lozano Oct 16 '15 at 5:06
  • $\begingroup$ Yes, though in this context only the finite continued fractions will arise. $\endgroup$ – Gerry Myerson Oct 16 '15 at 6:01
  • $\begingroup$ In Perron's book these fractions called "reduced regular continued fractions. Probably they are older then Hirzebruch. $\endgroup$ – Alexey Ustinov Oct 16 '15 at 6:23

I think the motivation for the Hirzebruch-Jung algorithm is not the algorithm itself, but the fact the it yields directly a very interesting continued fraction expansion. It is those, now called Hirzebruch-Jung continued fractions, that have a wide number of applications. A bit more on that later.

Using your notation (but changing $b$ with $r_o$ for clarity).

$$ \begin{array}{rcl} a &= & e_1r_0 -r_1\\ r_0 &= & e_2r_1 - r_2\\ r_1 &= &e_3r_2 -r_3\\ &...\\ r_{k-2} &= &e_ir_{k-1} = e_i \end{array}$$

By simple division you get:

$$ \begin{array}{rcl} a/r_0 &= & e_1 -r_1/r_0\\ r_0/r_1 &= & e_2 - r_2/r_1\\ r_1/r_2 &= &e_3 -r_3/r_2\\ &...\\ r_{k-2}/r_{k-2} &= &e_i \end{array}$$

And from that you can simply read off:

$$a/r_0 = e_1 -\frac{1}{e_1-\frac{1}{...-\frac{1}{e_i}}}$$

It is those finite continued fractions $a/r_0$ that have, among many others, applications to toric varieties. To quote from D. I. Dais' "Geometric Combinatorics in the Study of Compact Toric Surfaces" (2000):

"Examining two-dimensional toric singularities "under the microscope" one discovers a peculiar algebro-geometric world endowed with a rich combinatorial structure. Viewed historically, everything begins with Hirzebruch-Jung continued fractions."

For some more motivation and applications, I quote form a very recent (2015) paper:

"Hirzebruch-Jung (H-J) continued fractions are widely used in various branches of mathematics as well as in theoretical physics. First of all, HJ-continued fractions arise naturally in the minimal resolution of cyclic quotient (that is, Hirzebruch-Jung) surface singularities of the type $\mathbb{C}/\mathbb{Z}_p$, which is also known as HJ-resolution" [...]

HJ-continued fractions are used also to describe the plumbing decomposition of the other type of link of surface singularities, namely, Seifert fibered homology spheres (Sfh-spheres), particularly Brieskorn homology spheres (Bh-spheres) [...]

In condensed matter theory, the HJ-continued fractions are used to describe fractional quantum Hall (FQH) systems with k levels of hierarchy [...]

Also, in topological string theory, the structure of internal space (Calabi-Yau threefold) can be encoded in terms of HJ-continued fraction expansion of positive integers, which are the topological invariants of the internal space and define the mode of interactions between D-branes"


This algorithm gives best possible left (or right, it depends on the first step) convergents to a given number, while usual continued fractions give left and right convergents.

From gemetrical point of view convergents to ususal continued fractions for $a/N$ correspond to the verteces of two sails (in 1st and 2nd quarter) for the lattice generated by vectors $(a,1)$ and $(N,0)$ while "negative-regular" continued fractions (aka reduced regular continued fractions) give the verteces of only one sail (in 1st or 2nd quarter), see Geometric proof of Rödseth's formula for Frobenius numbers for the picture.


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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