# 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. – Dan 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

The original 1957 article by Brun himself article is clearly written. It contains full, clean proofs of weak convergence and of some linear independence results (at least for dimension 2).

But the article is only available in French, in the proceedings of the XIIIth Congress of Scandinavian Mathematicians (1957). Fortunately, there is a copy of these proceedings in IHP (Paris). Here is a scanned copy: http://jolivet.org/timo/docs/Brun_algo.pdf