# Lavaurs Algorithm

Robert P. Munafo, 2023 Jun 15.

The Lavaurs algorithm is a method for finding the locations of all mu-atoms in relation to each other, ordered by increasing external argument (which increase as one goes counter-clockwise around the Mandelbrot set).

The algorithm is most often described in terms of fractions n/d
where the denominator d is a number of the form 2^{p}-1 for some
period p. As described in the external argument article these
fractions occur in pairs, with both fractions in a pair leading to the
cusp of a mu-atom of period p. The continent seed is special,
being the only mu-atom of period 1. Its denominator is 2^{1}-1 = 1,
and there are two fractions 0/1 and 1/1 that are treated as being
equivalent.

The Lavaurs algorithm was described in English for the first time by Prof. Bodil Branner in a talk to the AMS Chaos and Fractals conference in Providence, RI, USA in August 1988. That description is:

Lavaurs algorithm. We represent a t ∈ ]0,1[ as the point
e^{2πit} on the unit circle S^{1}. If two rationals with odd
denominator are equivalent, then we connect the two corresponding points
in S^{1} by an arc of a circle in D perpendicular to the boundary
S^{1}. Recursively, using the period k of the rationals, we can construct
the equivalence classes as follows:

1. Connect 1/3 and 2/3.

2. Suppose all points corresponding to rationals of period l
for 2 ≤ l < k have been connected. Then points
corresponding to rationals of period k are connected pairwise
following the two rules:

(i) all arcs are disjoint,

(ii) if t_{1} is the smallest rational in ]0,1[ of period k
which has not yet been connected, then connect t_{1} to the smallest
possible t_{2} > t_{1} observing rule (i).

The proof of the algorithm is a detailed analysis of the order
of periodic points in Julia sets and the order of hyperbolic components
in the Mandelbrot set.

I met with Prof. Branner later the same day and learned about the
algorithm. It is simplified by the (non-obvious) fact that any
"rational with odd denominator" can be expressed as a fraction with a
denominator 2^{p}-1 (using Euler's theorem). These are not the
"two rationals [that] are equivalent"; that phrase instead refers to
the two rationals whose external rays lead to the same cusp of a
mu-atom (see the "External Angles of Cusps" section in the
external argument article).

For a fraction with denominator 2^{p}-1 (provided that the fraction
does not reduce to something with a smaller denominator 2^{f}-1),
the number p is the period found by iterating the process of
doubling modulo 1, that is, starting with x equal to the fraction
and repeatedly transforming x to a new value x' by the
function:

x → 2x if x<1/2

2x-1 otherwise

until a cycle is found, with p being the number of steps in the
cycle^{1}.

Because all fractions with odd denominator are equivalent to fractions
with denominator 2^{p}-1, and because the algorithm as stated
instructs one to start with period 2 and proceed to period 3, then 4,
then 5 and so on, denominators other than 2^{p}-1 can be ignored. In
addition, the fractions 1/3 and 2/3 do not need to have their own step
in the instructions, as they fit into the general procedure (those
fractions have period 2 under the doubling function, and 3=2^{2}-1).
Lastly, there is no particular reason to place the fractions on "a
circle S^{1}"; a simple line stretching from 0 to 1 will do, and
makes it easier to work out on paper.

Here I translate Lavaurs into a more direct and obvious description:

- Start with the fractions 0/1 and 1/1. Mark these at endpoints of a line which can be interpreted as going from 0 to 1, or from 0.00000... to 0.11111.... if expressed as external argument binary expansions. All external arguments fall somewhere in between. This line represents the first "pair", the fractions 0/1 and 1/1.

- Follow the rest of the steps in order of increasing period p, starting with p=2, then p=3, then p=4, and so on.

- For each period p, add points on the line that correspond to
all fractions with denominator 2
^{p}-1, and numerators from 1 through 2^{p}-2; but do not add any fraxtions if they are equal to a fraction that was added previously (for example, 5/15 is the same as 1/3, so we'll add 1/3 when working on period 2, but we'll skip 5/15 when we get to period 4).

- Match up the new fractions by connecting them in pairs, with
each pair being joined by a curved line or "arc" that lies
entirely above the line segment between the two fractions being
joined.

- Do not connect to any fractions that already have arcs connecting them.

- Do this starting from the lowest of the new fractions and proceeding towards the highest. After forming each pair, continue with the lowest remaining unpaired fraction.

- Do not allow arcs to cross, but always choose the lowest available pair that can be reached without crossing. For example 6/15 cannot be connected to 7/15 because that would require crossing the existing arc from 3/7 to 4/7. Instead 6/15 must be paired with 9/15.

## Illustration

Here the "arcs" will be drawn in ASCII graphics.

We start with a line going from 0 to 1:

0.....................................................1 - - 0 1
Start with period 2. The denominator is 2^{2}-1=3. Add the fractions
1/3 and 2/3 to the line:

Pair up the two fractions by connecting them with an arc:

,-----------. / \ / \ / \ 0.................1.................2.................1 - - - - 0 3 3 1
Proceed to period 3, and denominator 2^{3}-1=7. Add the fractions with
denominator 7 to the line:

Pair up each of these fractions in the obvious way:

,-----------. / \ ,-----. / ,-----. \ .-----. / \ / / \ \ / \ 0.......1.......2.1....3.......4....2.5.......6.......1 - - - - - - - - - - 0 7 7 3 7 7 3 7 7 1
Proceed to period 4, and denominator 2^{4}-1=15. Add the fractions
with denominator 15 to the line, except for 5/15 which is the same as
1/3 and 10/15 which is the same as 2/3:

The first two pairs are easy:

,-----------. / \ ,-----. / ,-----. \ .-----. ,--. / ,--. \ / / \ \ / \ 0 .1..2.1..3..4.2.1..6.3..7..8.4..9.2.5.11.12.6.13.14.1 - - - - - - - - -- - -- -- - -- - - -- -- - -- -- - 0 15 15 7 15 15 7 3 15 7 15 15 7 15 3 7 15 15 7 15 15 1The next fraction 6/15 must be matched up with something. We can't draw an arc from it to 7/15 (or to 8/15) because the existing arc from 3/7 to 4/7 is in the way. So instead, we connect 6/15 with 9/15:

,-----------. / ,-------. \ ,-----. / / ,-----. \ \ .-----. ,--. / ,--. \ / / / \ \ \ / \ 0 .1..2.1..3..4.2.1..6.3..7..8.4..9.2.5.11.12.6.13.14.1 - - - - - - - - -- - -- -- - -- - - -- -- - -- -- - 0 15 15 7 15 15 7 3 15 7 15 15 7 15 3 7 15 15 7 15 15 1Match up the remaining fractions: 7/15 with 8/15, 11/15 with 12/15, and 13/15 with 14/15. The result is:

,-----------. / ,-------. \ ,-----. / / ,-----. \ \ .-----. ,--. / ,--. \ / / / ,--. \ \ \ / ,-. \ ,-. 0 .1..2.1..3..4.2.1..6.3..7..8.4..9.2.5.11.12.6.13.14.1 - - - - - - - - -- - -- -- - -- - - -- -- - -- -- - 0 15 15 7 15 15 7 3 15 7 15 15 7 15 3 7 15 15 7 15 15 1Here is the same information "sideways", with a 6-digit decimal expansion for each fraction.

0.000000 0/1 0.066667 1/15. 0.133333 2/15' 0.142857 1/7---. 0.200000 3/15. | 0.266667 4/15' | 0.285714 2/7---' 0.333333 1/3-------. 0.400000 6/15----. | 0.428571 3/7---. | | 0.466667 7/15. | | | 0.533333 8/15' | | | 0.571429 4/7---' | | 0.600000 9/15----' | 0.666667 2/3-------' 0.714286 5/7---. 0.733333 11/15. | 0.800000 12/15' | 0.857143 6/7---' 0.866667 13/15. 0.933333 14/15' 0.999999 1/1## Circle Representation

Although the line layouts illustrated above are simplest to draw, it is more common to see the fractions arranged around a circle with the arcs internal to it.

Starting with the horizontal line layout, this is done by bending the right end of the line up so that 1/1 is at the "3-o-clock" position on a circle, leaving 11/15 at the bottom "6-o-clock" position, and bringing the rest of the line around so that 7/15 and 8/15 are at the "9-o-clock" position, 4/15 is at the top, and 0/1 meets up with 1/1 to complete the circle. The result is the left figure here:

Lavaurs arcs for periods 2, 3, and 4 |
Lavaurs diagram with period-5 arcs in black |

The right figure shows the result after adding arcs for the fractions with 31 in the denominator.

## Topological Equivalence to the Mandelbrot Set

Notice that the circle has been divided into segments by the arcs. Two segments are "neighbors" if they share one of the arcs as a boundary.

Each arc corresponds to two external rays that meet at a cusp of a mu-atom. Because the rays meet each other, the two points they lead to are the same point.

This suggests that we could "shrink" all the arcs down to zero length, by bringing the endpoints of each arc together, and adjusting everything else as necessary so that neighboring segments still touch each other (but now touching at only one point). Branner states this as follows:

The Abstract Mandelbrot Set. From the equivalence relation
on rationals we can get a model of an abstract Mandelbrot set
on a pinched disc: each connecting arc is pinched to a point.
One can prove that the abstract Mandelbrot set is homeomorphic
to M if and only if M is locally connected.^{2}

The regions into which the circle has been divided correspond to mu-atoms. For example, the largest region that is bounded partly by one green 2 arc, two red 3 arcs and two blue 4 arcs is the continent seed, and the region that lies between a blue 4 arc and the green 2 arc is the period 2 mu-atom R2.1/2a.

If this is done with all of the arcs (an infinite number of arcs!)
and if the all-important MLC conjecture is true^{2}, the result would
be topologically equivalent to the Mandelbrot set in all of its
infinite detail. Points on the circle itself correspond to the
filament structure.

## Enumeration of Features

The Lavaurs algorithm gives a way to identify all of the mu-atoms, and a way to count how many there are of each period; furthermore it lets us locate them in relation to each other. This is similar to the results of the algorithms presented in the enumeration of features article; however those algorithms only give total statistics, such as the number of islands and non-island mu-atoms of period 5 (11 and 4 respectively).

See also the Farey addition article, which shows how to get the ordering of a set of child mu-atoms that share a parent.

footnotes

**1 :**
The doubling function is relevant because of the way that the
Julia set's squaring iteration z → z^{2}+c affects the two sets
of p external rays, corresponding to the iterated x values as
their angles. There are two sets, one for each of the external
arguments that meet each other at the cusp of a mu-atom. The rays with
these 2p different external angles can be traced in the plane of the
Julia set whose parameter c is the location of that mu-atom cusp. In
the Julia plane for parameter c, the 2p rays lead in pairs to p
different points. The pairs of rays form boundaries that partition the
complex plane into nonintersecting regions that each contain one of
the p points in the limit cycle for c.

**2 :**
The question of Mandelbrot set local connectivity is still an
open conjecture, called "MLC". Much work has been done over more
than 35 years, and pieces of the conjecture (e.g. at points that
satisfy certain restricted definitions) have been proven.

From the Mandelbrot Set Glossary and Encyclopedia, by Robert Munafo, (c) 1987-2024.

Mu-ency main page — index — recent changes — DEMZ

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2023 Jun 17. s.27