# Length of Hirzebruch continued fractions

Suppose $a,b$ are two natural numbers relatively prime to $n$ and to each other. Assume $n\geq ab+1$. Suppose further that $\frac{a}{b}\equiv k \pmod{n}$ for some $k\in \lbrace 1,2,\dots, n-1\rbrace$ and $\frac{a}{b}\equiv k'\pmod{n+ab}$ for some $k'\in \lbrace 1,2,\dots, n+ab-1\rbrace$.

Question: Is there an elementary proof that the length of the continued fraction of $\frac{n}{k}$ is equal to the length of the continued fraction of $\frac{n+ab}{k'}$?

This came out of a broader result, and for this particular case I can prove it using routine toric geometry, however I would like to know of some elementary tricks to deal with continued fractions.

Here by continued fraction I mean the Hirzebruch continued fraction $$\frac{n}{k}=a_0-\frac{1}{a_1-\frac{1}{a_2-\cdots}}.$$ For example, when $a=2, b=3$ and $n=17$, we get $k=12$ and $k'=16$, so the fractions are $$\frac{17}{12}=2-\frac{1}{2-\frac{1}{4-\frac{1}{2}}}\qquad and \qquad\frac{23}{16}=2-\frac{1}{2-\frac{1}{5-\frac{1}{2}}}.$$

-
Sometimes known as the "negative-regular continued fraction". –  Gerry Myerson Nov 3 '12 at 4:28
Is there, by any chance, a pun on Kettenbruch? –  Alain Valette Nov 3 '12 at 7:16
@Alain Valette: I am not sure if you mean something more specific, but the Hirzebruch is the mathematician, as he conisdererd them somewhere, sometimes also the name Jung is mentioned in addition. So one finds say Hirzebruch-Jung-Kettenbruch in German texts. I could envision somebody coming along and calling it (or rather the plural) Hirzebrüche as a pun; I found nothing googling for this. But, the next person doing so might ;) –  quid Nov 3 '12 at 11:09
@Gjergji: Your "routine toric geometry" line brought a smile to my face. I suppose you could try to convert the routine geometry facts into statements on the geometry of numbers. As far as I can remember the length of the Hirzebruch-Jung continued fraction is related to the number of edges in a Newton polygon, the convex hall of the nonzero lattice points in side the angle determined by the positive horizontal semi-axis and the ray of slope $a/b$. –  Liviu Nicolaescu Nov 5 '12 at 10:18
According to Perron (Vol. 1, $\S$ 43) this fraction as known as reduced regular continued fraction'' (reduziert-regelmaessige Kettenbrueche). –  Alexey Ustinov Nov 6 '12 at 1:35

Lets call expansions $$\langle x_1,\ldots,x_m\rangle:=\cfrac{1}{x_1-{\atop\ddots\,\displaystyle{-\cfrac{1}{x_m}}}}$$ (as in Perron's book) reduced regular continued fractions (RRCF). Probably they are older then Hirzebruch.

We'll prove more precise statement.

Theorem. If $(n,ab)=1$ and $n>ab$ then RRCF for all numbers $$\left\{\frac{ab^{-1}\pmod{(n+kab)}}{n+kab}\right\}\qquad(k\ge 0)$$ are almost equal: they have equal length and differ only in one partial quotient.

Remark 1. Common factors of $a$ and $b$ can be moved into $k$. If $d=(a,b)$, $a=da_1$, $b=db_1$, then \begin{gather*} \left\{ \frac{ab^{-1}\pmod{(n+kab)}}{n+kab}\right\} =\left\{ \frac{a_1b_1^{-1}\pmod{(n+kab)}}{n+kab}\right\} \\=\left\{ \frac{a_1b_1^{-1}\pmod{(n+(kd^2)a_1b_1)}}{n+(kd^2)a_1b_1}\right\}. \end{gather*} So we can assume that $(a,b)=1$.

Remark 2. The proof will be given in terms of modified continuants $K(x_1,\ldots, x_n)$ (see Concrete Mathematics'' for more explanations). These polynomials are defined by initial conditions $$K()=1,\quad K(x_1)=x_1$$ and the following recurrence: $$K(x_1,\ldots, x_n)=x_nK(x_1,\ldots, x_{n-1})-K(x_1,\ldots, x_{n-2})\qquad(n\ge2).$$ (In the usual definition minus must be replaced by plus.) For convenience $K_{-1}:=0$ (empty RRCF is $0$).

In terms of continuants RRCF can be written as $$\langle x_1,\ldots,x_n\rangle=\frac{K(x_2,\ldots, x_n)}{K(x_1,\ldots, x_n)}.$$

Continuant's properties. All these properties can be proved by induction (or from Euler’s rule'').

1$^{\circ}.$ $K(x_1,\ldots, x_n)=K(x_n,\ldots, x_{1})$.

2$^{\circ}.$ \begin{gather*} K(x_1,\ldots, x_n,x_{n+1}, \ldots, x_{m+n})\\=K(x_1,\ldots, x_n)K(x_{n+1}, \ldots, x_{m+n})-K(x_1,\ldots, x_{n-1})K(x_{n+2}, \ldots, x_{m+n}) \end{gather*}

3$^{\circ}.$ $\begin{vmatrix} K(x_2,\ldots, x_{n-1})&K(x_2,\ldots, x_n) \\ K(x_1,\ldots, x_{n-1})&K(x_1,\ldots, x_n) \end{vmatrix}=-1$. In particular if $$\frac{A}{a}=\left<r_1, \ldots, r_v\right>=\frac{K(r_2, \ldots, r_v)}{K(r_1, \ldots, r_v)}$$ then $$K(r_1, \ldots, r_{v-1})=A^{-1}\pmod{a},\qquad K(r_2, \ldots, r_{v-1})=\frac{AA^{-1}\pmod{a}-1}{a}.$$

4$^{\circ}.$ Euler's identity (see A Short Proof of Euler's Identity for Continuants for additional arguments). (2$^{\circ}$ and 3$^{\circ}$ are special cases of this identity) $$K(x_1, \ldots, x_{m+n})K(x_{m+1}, \ldots, x_{m+l})-K(x_1, \ldots, x_{m+l})K(x_{m+1}, \ldots, x_{m+n})$$ $$+K(x_1, \ldots, x_{m-1})K(x_{m+l+2}, \ldots, x_{m+n})=0.$$

Proof of the Theorem. For a given $n$ define $a^{-1}:=a^{-1}\pmod{n}$, $b^{-1}:=b^{-1}\pmod{n}$, $0\le a,b\le n-1$ (inverse number is always least possible nonnegative) and $t_a$, $t_b$ such that $aa^{-1}=1+t_an$, $bb^{-1}=1+t_bn$. Let $$\frac{A}{a}=\left\{\frac{bt_a}{a}\right\}=\left<r_1, \ldots, r_v\right>,\qquad A^{-1}:=A^{-1}\pmod{a};$$ $$\frac{B}{b}=\left\{\frac{at_b}{b}\right\}=\left<q_1, \ldots, q_u\right>,\qquad B^{-1}:=B^{-1}\pmod{b};$$ $$\frac{P(x)}{Q(x)}=\left<q_1, \ldots, q_u,x,r_v, \ldots, r_1\right>.$$ By 2$^{\circ}$, 3$^{\circ}$ and main recurrence $$Q(x)=K(q_1, \ldots, q_u,x,r_v, \ldots, r_1)=$$ $$xK(q_1, \ldots, q_u)K(r_v, \ldots, r_1)-K(q_1, \ldots, q_{u-1})K(r_v, \ldots, r_1)-K(q_1, \ldots, q_u)K(r_{v-1}, \ldots, r_1)$$ $$=xab-aB^{-1}-bA^{-1}.$$ Hence $$Q(x)\equiv -bA^{-1}\equiv -b((bt_a)^{-1}\pmod{a})\equiv -t_a^{-1}\equiv n\pmod{a},$$ $$Q(x)\equiv -aB^{-1}\equiv -a((at_b)^{-1}\pmod{b})\equiv -t_b^{-1}\equiv n\pmod{b}.$$ Therefore $$Q(x)\equiv n\pmod{ab},$$ and for some integer $x_0$ we have $Q(x_0)=n$. We know that $n>ab$. It means that $$x_0ab-aB^{-1}-bA^{-1}>ab,$$ so $x_0\ge 2$ and $\left<q_1, \ldots, q_u,x_0,r_v, \ldots, r_1\right>$ is really RRCF. Choosing arbitrary $x=x_0+k$ we'll get progression $n+kab$ as in the statement of the theorem.

Let's check the numerator $P(x)$. Final step $P(x)\equiv ab^{-1}\pmod{Q(x)}$ follows from identity $$bP(x)-BQ(x)=a,$$ which is a special case of Euler's identity. Nevertheless this identity can be verified directly with help of 1$^{\circ}$--3$^{\circ}$: $$P(x)=K(q_2, \ldots, q_u,x,r_v, \ldots, r_1)=$$ $$xK(q_2, \ldots, q_u)K(r_v, \ldots, r_1)-K(q_2, \ldots, q_{u-1})K(r_v, \ldots, r_1)-K(q_2, \ldots, q_u)K(r_{v-1}, \ldots, r_1)$$ $$=xaB-a\frac{BB^{-1}-1}{b}-BA^{-1},$$ $$bP(x)-a=B(xab-aB^{-1}-bA^{-1})=BQ(x).$$

-
Thanks, this is very useful, and definitely the kind of argument I was looking for. –  Gjergji Zaimi Nov 7 '12 at 8:33
Will it give anything useful for toric geometry? –  Alexey Ustinov Nov 7 '12 at 9:33
This answer was published as a short note "On continued fractions of equal length" at mathnet.ru/php/… –  Alexey Ustinov Mar 18 at 2:43

Forgive me, this should be in the comments, but I am still building my reputation up to comment. If a=5, b=4, n=7, then k=3, k'=8, and n+ab=27.

Here, $\frac{n}{k}=\frac{7}{3}=3-\frac{1}{2-\frac{1}{2}}$ but $\frac{n+ab}{k'}=\frac{27}{8}=4-\frac{1}{2-\frac{1}{3-\frac{1}{2}}}$. Am I missing something or is there a further assumption on these numbers?

-
Yes, there was a crucial missing assumption, that $n > ab$. Thank you for pointing this out. –  Gjergji Zaimi Nov 5 '12 at 19:19