# Brun's algorithm

Does anyone have an exact reference for the weak convergence (convergence in angle) of Brun's subtractive multi-dimensional continued fractions algorithm (in all dimensions)? I have been given Schweiger's book on multi-dimensional continued fractions as a reference. However, perhaps the area is a bit foreign to me so that I could not exactly find it in there.

Thank you very much!

-
possibly, stuff by Valerie Berthé (pdf)? –  john mangual Jul 24 '14 at 19:55
I tried looking through a number of her papers for it & couldn't find it (that doesn't mean that it's not somewhere in one of them, it's just that I couldn't find it). –  Catherine Pfaff Jul 24 '14 at 20:04
I can not read French, but is it not possible that a proof appear's in Brun's original paper? V. Brun, Algorithmes euclidiens pour trois et quatre nombres, 13th Congr. Math. Scand. Helsinki (1957), 45-64. –  Daniel Rust Jul 25 '14 at 16:06

In section 5 of Brun Expansions, Substitutions and Discrete Geometry a $d$-dimensional" Brun map is introduced:

$$T: (a_1, \dots, a_n) \mapsto (\tfrac{a_1}{a_k}, \dots, \{\tfrac{1}{a_j} \},\dots,\tfrac{a_n}{a_k})$$

where $\{ x\} \equiv x \mod 1$. Maps of this kind usually arise as an accelerated version of the Euclidean algorithm.

We could imagine a map $R: x \mapsto x + a$ with initial value $0$.

Consider the first-return map on the interval $[0,R(0)=a]$. We need to find a number such that

$$ma < a \mod 1$$

In fact, $m = \lfloor \tfrac{1}{a} \rfloor+1$. If we rescale the interval so that $[0,a]$ is now $[0,1]$. In that case

$$0 \mapsto \lfloor \tfrac{1}{a} \rfloor \mod \tfrac{1}{a} \equiv \{ \tfrac{1}{a}\}$$

So our rotation got rescaled to $R_1: x \mapsto x + \{ \tfrac{1}{a}\}$. This renormalization is acting on the set of rotations.

It's likely the Brun expansion arises from a "Euclidean algorithm" on vectors.

Here is another interesting question: Do simple, multi-dimensional generalizations of this continued fraction formula exist?

Google searching has found many interesting variants on the continued fraction algorithm:

The more I read the more ambiguous the term "multidimensional continued fraction" gets.

-
Unfortunately, this is not exactly the algorithm I'm using (or want to use). I'm using the one where at each stage you subtract the second largest coordinate from the largest coordinate & leave all others the same. There are a number of multi-dimensional continued fraction algorithms. For example, there is one by Arnoux-Rauzy. I believe that, if one looks through the work of Valerie Berthé (possibly in particular with Sebastian Labbe), one can find several different algorithms (also in the book of Schweiger). –  Catherine Pfaff Jul 25 '14 at 12:28
@CatherinePfaff do any of these examples on these slides by Shweiger match your definition? –  john mangual Jul 25 '14 at 12:38