Motivation for Hirzebruch-Jung Modified Euclidean Algorithm

Question

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.

Answer 1

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"

Answer 2

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.

Another application is Conway tangles. The shortest way to generate a tangle $T$ with given invariant $i(T)$ is to expand $i(T)$ into a "negative-regular" continued fraction.