2120193174951

# Number of Orbits of Discrete Interval Exchanges

Mélodie Lapointe  LaCIM, Université du Québec à Montréal, Canada

(2018-11-1; 2019-4-29; 2019-5-13)

###### Abstract

A new recursive function on discrete interval exchange associated to a
composition of length $r$, and the permutation $\sigma(i)=r-i+1$ is defined.
Acting on a composition $c$, this recursive function counts the number of
orbits of the discrete interval exchange associated to the composition $c$.
Moreover, minimal discrete interval exchanges, i.e. the ones having only one
orbit, are reduced to the composition $(1,1)$ which label the root of the
Raney tree. Therefore, we describe a generalization of the Raney tree using
our recursive function.

###### keywords:

Interval exchanges, Rauzy induction, Raney tree, orbits

##  1 Introduction

An interval exchange is a map which cuts an interval into $r$ pieces and
reorders them. These maps were introduced by Oseledec in 1966 [11] to
generalize circle rotations following some ideas of Arnold [1, 2]. The
discrete analogue maps were introduced by Ferenczi and Zamboni in 2013 [7] by
replacing the interval by a discrete interval i.e. a set of integers between
$a$ and $b$. A discrete interval exchange is called minimal if it has only one
orbit. In the same paper, Ferenczi and Zamboni give a bijection between
minimal discrete interval exchange and a special subset of words called
$\pi$-clustering words (see [7] for more details on $\pi$-clustering words). A
natural question arises from that bijection: Can we identify compositions
associated with minimal discrete interval exchanges?

Some partial answers can be found in the literature when the pieces are
reordered in reverse order. It is well-known that a discrete interval exchange
with 2 pieces is minimal if and only if its composition has coprime parts.
Moreover, a discrete interval exchange with 3 pieces
$(\lambda_{1},\lambda_{2},\lambda_{3})$ is minimal if and only if
$\gcd(\lambda_{1}+\lambda_{2},\lambda_{2}+\lambda_{3})=1$ as shown by Pak and
Redlich [12]. We propose a new recursive function on compositions which counts
the number of orbits of a discrete interval exchange and agrees with the
greatest common divisor recursion when $r=2$. Other functions that coincide
with the greatest common divisor when $r=2$ are known. For example, Rauzy
induction is a generalization of Euclid’s algorithm which renormalized
intervals exchange and was introduced by Rauzy in 1979 [14]. Other examples
are given by the multidimensional continued fraction algorithms (see [9, 16]).

This paper is organized as follows. In Section 2, a formal definition of
symmetric discrete interval exchanges is presented. The presentation of the
recursive function counting the number of orbits is the main focus of the
Section 3. In Section 4, a generalization of the Raney tree where each
circular composition appears is shown. Finally, we describe the number of
orbits of any symmetric discrete interval exchange with 3 pieces extending the
result given by Pak and Redlich [12]. Moreover, we give the cyclic type of
these discrete interval exchanges.

Note that the recursive function counting the number of orbits presented in
Theorem 1, Corollary 3 giving the cyclic type of a discrete interval exchange
of length $3$ and a slightly modified version of the tree of circular
compositions were conjectured by Christophe Reutenauer [15].

After submission, we discovered that Karnauhova and Liebscher [8] (2017) have
given a similar algorithm as ours (Theorem 1). They work on a geometric
generalization of symmetric discrete interval exchanges, called bi-rainbow
meanders. Their main contribution is a formula which counts the number of
connected components of bi-rainbow meanders; this is the same as counting the
number of orbits of symmetric discrete interval exchanges. They do not study
the construction, nor the enumeration of connected bi-rainbow meanders, which
corresponds in our language to minimal symmetric discrete interval exchanges.

##  2 Discrete interval exchange

An _integer interval_ , denoted by $\llbracket a,b\rrbracket$, is the set
$[a,b]\cap\mathbb{Z}$ for some integers $a$ and $b$. A _composition_ of $n$ is
a finite sequence $(\lambda_{1},\dots,\lambda_{r})$ of positive integers whose
sum is $n$. A _permutation_ $\sigma$ of $\mathcal{S}_{r}$ can be written as
the _word_ $\sigma(1)\sigma(2)\dots\sigma(r).$ Recall that the _cycle
notation_ of a permutation $\sigma$ is written as the product of its orbits.
For example, the permutation written as the word $451326$, is written in cycle
notation as $(1,4,3)(2,5)(6)$. The number of orbits of $\sigma$ is denoted by
$\gamma(\sigma)$. A permutation is _circular_ if it has exactly one orbit.

We consider a particular case of _discrete interval exchanges_ , as they are
defined in [7] (as they are defined in [7]: for $\pi\in S_{r}$, let
$\pi(k)=r-k+1$ for all $k\in\llbracket 1,r\rrbracket$).

######  Definition 1.

Let $\lambda=(\lambda_{1},\dots,\lambda_{r})$ be a composition of $n$. The
associated _symmetric discrete interval exchange_ $T_{\lambda}$ is defined as
follows: let $B_{1},\dots,B_{r}$ be the subintervals of $\llbracket
1,n\rrbracket$ defined by $B_{i}=\llbracket
1+\sum_{j<i}\lambda_{j},\sum_{j\leq i}\lambda_{j}\rrbracket;$ let

$\displaystyle s_{i}=\sum_{j>i}\lambda_{j}-\sum_{j<i}\lambda_{j}.$

Then for all $x\in B_{i}$, $T_{\lambda}(x)=x+s_{i}$. We call $s_{i}$ the
$i$-th _translation parameter_ and $(s_{1},\dots,s_{r})$ the _translation
vector_.

The symmetric discrete interval exchange $T_{\lambda}$ is a permutation on the
set $\llbracket 1,n\rrbracket$. For example, the symmetric discrete interval
exchange $T_{(3,5,4,2)}$ is $(1,12,6,9,3,14,2,13)(4,7,10)(5,8,11)$ as shown in
Figure 1. The subintervals of $\llbracket 1,14\rrbracket$ are
$B_{1}=\\{1,2,3\\}$, $B_{2}=\\{4,5,6,7,8\\}$, $B_{3}=\\{9,10,11,12\\}$,
$B_{4}=\\{13,14\\}$ and the translation vector of $\llbracket 1,14\rrbracket$
is $s=(5+4+2,4+2-3,2-3-5,-3-5-4)=(11,3,-6,-12)$. A discrete interval exchange
is _minimal_ if it has only one orbit.

The translation vector of a symmetric discrete interval exchange is strictly
decreasing. Moreover, the inverse of a symmetric discrete interval exchange
$T_{(\lambda_{1},\dots,\lambda_{r})}$ is
$T_{(\lambda_{r},\dots,\lambda_{1})}$. Evidently, they both have the same
number of orbits.

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$B_{1}$$B_{2}$$B_{3}$$B_{4}$$B_{\sigma(1)}$$B_{\sigma(2)}$$B_{\sigma(3)}$$B_{\sigma(4)}$
Figure 1: The symmetric discrete interval exchange $T_{(3,5,4,2)}$

##  3 Counting Orbits

In this section, we define a recursive function on compositions that counts
the number of orbits of a symmetric discrete interval exchange. In fact, the
function subtracts the $i-$th translation parameter to $\lambda_{i}$. To
ensure that the result is positive, we first prove that each composition has a
part which is greater than its translation parameter.

######  Lemma 1.

Let $\lambda=(\lambda_{1},\dots,\lambda_{r})$ be a composition. There exists
an integer $t$ in the set $\llbracket 1,r\rrbracket$ such that
$\lambda_{t}\geq|s_{t}|$.

###### Proof.

There exists an integer $t$ such that

$\displaystyle\sum_{i<t}\lambda_{i}\leq\sum_{i\geq t}\lambda_{i}$
$\displaystyle\text{ and }\sum_{i\leq t}\lambda_{i}\geq\sum_{i>t}\lambda_{i},$

since all $\lambda_{i}$ are positive integers. By isolating $\lambda_{t}$ in
both inequalities, we obtain

$\displaystyle\sum_{i<t}\lambda_{i}-\sum_{i>t}\lambda_{i}\leq\lambda_{t}$
$\displaystyle\text{ and
}\lambda_{t}\geq\sum_{i>t}\lambda_{i}-\sum_{i<t}\lambda_{i},$

We combine both inequalities to obtain

$\displaystyle\lambda_{t}\geq\left|\sum_{i>t}\lambda_{i}-\sum_{i<t}\lambda_{i}\right|=|s_{t}|,$

by Definition 1.

∎

Remark: The value $t$ where $\lambda_{t}\geq|s_{t}|$ is not unique if
$\lambda_{t}=|s_{t}|$. For example, in the composition $(2,1,2,1)$ we have
that $\lambda_{2}\geq|s_{2}|$ and $\lambda_{3}\geq|s_{3}|$. However, one can
show that there are at most two possible values. These properties are proven
in Section 4.

Let $t$ be the smallest integer belonging to the set $\llbracket
1,r\rrbracket$ such that $\lambda_{t}\geq|s_{t}|$ where $(s_{1},\dots,s_{r})$
is the translation vector of $T_{\lambda}$. Define a function $f$ mapping from
the set of compositions to the natural numbers as

$f(\lambda_{1},\dots,\lambda_{r})=\begin{cases}\lambda_{1}&\text{if }r=1,\\\
\lambda_{t}+f(\lambda_{1},\dots,\lambda_{t-1},\lambda_{t+1},\dots,\lambda_{r})&\text{if
}|s_{t}|=0,\\\
f(\lambda_{1},\dots,\lambda_{t-1},\lambda_{t+1},\dots,\lambda_{r})&\text{if
}\lambda_{t}=|s_{t}|,\text{ and}\\\
f(\lambda_{1},\dots,\lambda_{t}-|s_{t}|,\dots,\lambda_{r})&\text{otherwise}.\\\
\end{cases}$ (1)

We show that $f$ counts the number of orbits of any symmetric discrete
interval exchange i.e. $f(\lambda)=\gamma(T_{\lambda})$.

######  Example 1.

The symmetric discrete interval exchange $T_{(3,5,4,2)}$ has $3$ cycles as
shown previously and

$\displaystyle f(3,5,4,2)$ $\displaystyle=f(3,2,4,3)=f(3,2,1,2)$
$\displaystyle=2+f(3,1,2)=2+f(1,2)=2+f(1,1)=2+f(1)$ $\displaystyle=3.$

The values of $t$ and the corresponding translation parameter at each step are
in Table 1.

$\lambda$ | $(3,5,4,2)$ | $(3,2,4,2)$ | $(3,2,1,2)$ | $(3,1,2)$ | $(1,2)$ | $(1,1)$ | $(1)$
---|---|---|---|---|---|---|---
$t$ | 2 | 3 | 2 | 1 | 2 | 1 |
$|s_{t}|$ | 3 | 3 | 0 | 3 | 1 | 1 |
Table 1: The first row gives the successive steps in the computation of
$f(3,5,4,2)$, the second row gives the indices where the recursion for $f$ is
applied on the composition and the third row gives the absolute value of the
$t$-th translation parameter.

We say that $(\lambda_{1},\dots,\lambda_{r})\leq(\beta_{1},\dots,\beta_{s})$
if $r<s$ or $r=s$ and
$(\lambda_{1},\dots,\lambda_{r})\leq_{lex}(\beta_{1},\dots,\beta_{s})$, where
$\leq_{lex}$ is the lexicographic order i.e. $\lambda_{1}<\beta_{1}$ or
$\lambda_{1}=\beta_{1}$ and
$(\lambda_{2},\dots,\lambda_{r})\leq_{lex}(\beta_{2},\dots,\beta_{s})$. One
can check that the composition in the recursive step of $f$ is smaller than
the composition.

The next few lemmas show that the operations used in the recursive step of the
function $f$ are valid.

######  Lemma 2.

If the value of $|s_{t}|$ is zero , then the symmetric discrete interval
exchange $T_{\lambda}$ has

$\lambda_{t}+\gamma(T_{(\lambda_{1},\dots,\lambda_{t-1},\lambda_{t+1},\dots,\lambda_{r})})$

orbits.

For example, $T_{(3,2,4,5)}$ has 5 orbits and its third translation parameter
is $0$. Moreover, one can check that $T_{(3,2,5)}$ has one orbit, hence
$\gamma(T_{(3,2,4,5)})=5=4+\gamma(T_{(3,2,5)})$ as predicted.

###### Proof.

Let $\lambda=(\lambda_{1},\dots,\lambda_{r})$ be a composition and $t$ an
integer in $\llbracket 1,r\rrbracket$ such that $s_{t}=0$. Let $x$ be an
integer in the set $\llbracket 1,n\rrbracket$. By definition, the symmetric
discrete interval exchange $T_{\lambda}$ is

$\displaystyle~{}T_{\lambda}(x)=x+s_{i}$ (2)

where $x$ belongs to $B_{i}$ with $B_{i}=\llbracket
1+\sum_{j<i}\lambda_{j},\sum_{j\leq i}\lambda_{j}\rrbracket$ and
$s_{i}=\sum_{j>i}\lambda_{j}-\sum_{j<i}\lambda_{j}$ as in Definition 1.

If $x\in B_{t}$, then Equation (2) becomes $T_{\lambda}(x)=x$. Thus, each
integer in $B_{t}$ is a fixed point of $T_{\lambda}$ and its orbit contains
only itself. Thus $T_{\lambda}|B_{t}$ is the identity and $T_{\lambda}$
stabilizes $H=\llbracket 1,n\rrbracket\backslash B_{t}$.

We show that $T_{\lambda}|H$ is conjugated to $T_{\lambda^{\prime}}$; that is
, $T_{\lambda}|H=\omega^{-1}\circ T_{\lambda^{\prime}}\circ\omega$, where
$\omega$ is the unique decreasing bijection $H\rightarrow\llbracket
1,n-\lambda_{t}\rrbracket$. This implies that the number of orbits of
$T_{\lambda}|H$ is equal to $\gamma(T_{\lambda^{\prime}})$.

Suppose that $x\notin B_{t}$. Let
$\lambda^{\prime}=(\lambda^{\prime}_{1},\dots,\lambda^{\prime}_{r-1})$ where
$\lambda^{\prime}_{i}=\lambda_{i}$ if $i<t$ and
$\lambda^{\prime}_{i}=\lambda_{i+1}$ otherwise. Note that
$T_{\lambda^{\prime}}$ is the symmetric discrete interval exchange where
$B^{\prime}_{1},\dots,B^{\prime}_{r-1}$ are subintervals of $\llbracket
1,n-\lambda_{t}\rrbracket$ defined by $B^{\prime}_{i}=\llbracket
1+\sum_{j<i}\lambda^{\prime}_{i},\sum_{j\leq
i}\lambda^{\prime}_{i}\rrbracket$. Its translation parameters are defined by
$s^{\prime}_{i}=\sum_{j>i}\lambda^{\prime}_{j}-\sum_{j<i}\lambda^{\prime}_{j}$.
Then for all $x\in B^{\prime}_{i}$,
$T_{\lambda^{\prime}}(x)=x+s^{\prime}_{i}$. Note that
$T_{\lambda^{\prime}}=T_{(\lambda_{1},\dots,\lambda_{t-1},\lambda_{t+1},\dots,\lambda_{r})}$.

First, we describe the sets $B_{i}$ using the sets $B^{\prime}_{i}$. We have
two cases to consider.

If $i<t$, then

$B_{i}=\left\llbracket 1+\sum_{j<i}\lambda_{j},\sum_{j\leq
i}\lambda_{j}\right\rrbracket=\left\llbracket
1+\sum_{j<i}\lambda^{\prime}_{j},\sum_{j\leq
i}\lambda^{\prime}_{j}\right\rrbracket=B^{\prime}_{i}$

since $j\leq i<t$, we know that $\lambda_{j}=\lambda^{\prime}_{j}$.

Otherwise, if $i>t$, then

$B_{i}=\left\llbracket 1+\sum_{j<i}\lambda_{j},\sum_{j\leq
i}\lambda_{j}\right\rrbracket=\left\llbracket
1+\lambda_{t}+\sum_{j<i}\lambda^{\prime}_{i},\lambda_{t}+\sum_{j\leq
i}\lambda^{\prime}_{i}\right\rrbracket=\\{x+\lambda_{t}\mid x\in
B^{\prime}_{i}\\},$

since $i>t$ and
$\sum_{j<i}\lambda_{j}=\sum_{j<t}\lambda_{j}+\sum_{t<j<i}\lambda_{j}+\lambda_{t}=\lambda_{t}+\sum_{i<j}\lambda^{\prime}_{i}$.

Secondly, we want to show that
$T_{\lambda}(x)=T_{\lambda^{\prime}}(x)\pm\lambda_{t}$. Recall that
$T_{\lambda}(x)=x+\sum_{j>i}\lambda_{j}-\sum_{j<i}\lambda_{j}$. We factorize
$\lambda_{t}$ to obtain

$T_{\lambda}(x)=\begin{cases}x+\sum_{j>t}\lambda_{j}+\sum_{t>j>i}\lambda_{j}-\sum_{j<i}\lambda_{j}+\lambda_{j}&\text{
if }i<t\\\
x+\sum_{j>i}\lambda_{j}-\sum_{j<t}\lambda_{j}-\sum_{t<j<i}\lambda_{j}-\lambda_{j}&\text{
if }i>t.\end{cases}$

Replacing $\lambda_{j}$ by $\lambda^{\prime}_{j}$ if $j<t$ and by
$\lambda^{\prime}_{j-1}$ otherwise gives

$\displaystyle T_{\lambda}(x)$
$\displaystyle=\begin{cases}x+\sum_{j>i}\lambda^{\prime}_{j}-\sum_{j<i}\lambda^{\prime}_{j}+\lambda_{t}&\text{
if }i<t\\\
x+\sum_{j>i}\lambda^{\prime}_{j}-\sum_{j<i}\lambda^{\prime}_{j}+\lambda_{t}&\text{
if }i>t,\end{cases}$ $\displaystyle=\begin{cases}x+s_{i}+\lambda_{t}&\text{ if
}i<t\\\ x+s_{i}-\lambda_{t}&\text{ if }i>t.\end{cases}$

Hence, $T_{\lambda}|H$ is conjugated to $T_{\lambda^{\prime}}$ and the number
of orbits of $T_{\lambda}$ is
$\lambda_{t}+\gamma(T_{(\lambda_{1},\dots,\lambda_{t-1},\lambda_{t+1},\dots,\lambda_{r})})$
as claimed. ∎

######  Lemma 3.

Let $(\lambda_{1},\dots,\lambda_{r})$ be a composition of $n$. The symmetric
discrete interval exchange $T_{(\lambda_{1},\dots,\lambda_{r})}$ and
$T_{(\lambda_{1},\dots,\lambda_{t}+|s_{t}|,\dots,\lambda_{r})}$ have the same
number of orbits.

We begin by understanding how the orbits of
$T_{(\lambda_{1},\dots,\lambda_{r})}$ can be transformed into the orbits of
$T_{(\lambda_{1},\dots,\lambda_{t}+|s_{t}|,\dots,\lambda_{r})}$. Through the
cycle notation, a symmetric discrete interval exchange can be viewed as a set
of circular words on the alphabet $\llbracket 1,n\rrbracket$. Therefore, a
substitution on $T_{(\lambda_{1},\dots,\lambda_{r})}$ describes this
operation:

$\displaystyle\psi_{t}(x)=\begin{cases}x&\mathrm{if}\ x\in\llbracket
1,k\rrbracket\\\ x\cdot(x+|s_{t}|)&\mathrm{if}\ x\in\llbracket
k+1,k+|s_{t}|\rrbracket\mathrm{\ and\ }s_{t}>0\\\ (x+|s_{t}|)\cdot
x&\mathrm{if}\ x\in\llbracket k+1,k+|s_{t}|\rrbracket\mathrm{\ and\
}s_{t}<0\\\ \ x+|s_{t}|&\mathrm{otherwise}\\\ \end{cases}$ (3)

where $x\in\llbracket 1,n\rrbracket$ is a letter, $\cdot$ denotes
concatenation and

$k=\begin{cases}\sum_{j\leq t}\lambda_{j}&\mathrm{if\ }s_{t}\geq 0\\\
\sum_{j<t}\lambda_{j}-|s_{t}|&\mathrm{if}s_{t}<0.\end{cases}$

For example, the symmetric discrete interval exchange of $T_{(5,1,2)}$ is
$(1,4,7)(2,5,8)(3,6)$ and the symmetric discrete interval exchange of
$T_{(5,4,2)}$ is $(1,7,4,10)(2,8,5,11)(3,9,6)$. Let us apply $\psi_{2}$ on
$T_{(5,1,2)}$. We have that $t=2$, $s_{t}=-3<0$ and $k=2$. For $T_{(5,1,2)}$,
the substitution is

$\displaystyle\psi_{2}(x)=\begin{cases}x&\mathrm{if}\ x\in\llbracket
1,2\rrbracket\\\ (x+3)\cdot x&\mathrm{if}\ x\in\llbracket 3,5\rrbracket\\\
x+3&\mathrm{otherwise.}\\\ \end{cases}$ (4)

Hence
$\psi_{2}(T_{(5,1,2)})=\psi_{2}((1,4,7)(2,5,8)(3,6))=(1,7,4,10)(2,8,5,11)(6,3,9)$
as predicted.

######  Lemma 4.

Let $t$ be an integer in $\llbracket 1,r\rrbracket$. The identity

$\psi_{t}(T_{(\lambda_{1},\dots,\lambda_{r})})=T_{(\lambda_{1},\dots,\lambda_{t}+|s_{t}|,\dots,\lambda_{r})}$

holds.

Here $\psi_{t}$ acts as a substitution on the orbits of
$T_{(\lambda_{1},\dots,\lambda_{r})}$. Recall that the circular factors of
length 2 of a circular word $(a_{1},\dots,a_{n})$ are the words
$a_{i}a_{(i+1)\bmod n}$, with $i\in\llbracket 1,n\rrbracket$. We use the
following obvious but useful result in the next proof: the orbits of $\sigma$
and $\alpha$ have the same circular factors of length 2.

###### Proof.

First, suppose that $s_{t}=0$. Thus,
$\psi_{t}(T_{\lambda})=T_{(\lambda_{1},\dots,\lambda_{t}+|s_{t}|,\dots,\lambda_{r})}$,
since $\psi_{t}$ is the identity morphism when $s_{t}=0$.

Let $t$ be an integer in the set $\llbracket 1,r\rrbracket$ and $T_{\lambda}$
a symmetric discrete interval exchange as in Definition 1. Let
$\lambda^{\prime}=(\lambda^{\prime}_{1},\dots,\lambda^{\prime}_{r})$ be a
composition where $\lambda^{\prime}_{t}=\lambda_{t}+|s_{t}|$ and
$\lambda^{\prime}_{i}=\lambda_{i}$ if $t\neq i$. Recall that
$T_{\lambda^{\prime}}$ is the symmetric discrete interval exchange where
$B^{\prime}_{1},\dots,B^{\prime}_{r}$ are subintervals of $\llbracket
1,n+|s_{t}|\rrbracket$ defined by $B^{\prime}_{i}=\llbracket
1+\sum_{j<i}\lambda^{\prime}_{i},\sum_{j\leq i}\lambda^{\prime}_{i}\rrbracket$
and its translation parameters are
$s^{\prime}_{i}=\sum_{j>i}\lambda^{\prime}_{j}-\sum_{j<i}\lambda^{\prime}_{j}$.
Then for all $x\in B^{\prime}_{i}$,
$T_{\lambda^{\prime}}(x)=x+s^{\prime}_{i}$. Note that the previous definition
implies
$T_{\lambda^{\prime}_{t}}=T_{(\lambda_{1},\dots,\lambda_{t}+|s_{t}|,\dots,\lambda_{r})}$.

We begin by describing the circular factors of length $2$ of
$T_{\lambda^{\prime}}$ using $\lambda$ and $B_{i}$ instead of
$\lambda^{\prime}$ and $B^{\prime}_{i}$.

To describe $B^{\prime}_{i}$ using the sets $B_{i}$, we have three cases to
consider. First, if $i<t$, then

$B^{\prime}_{i}=\left\llbracket 1+\sum_{j<i}\lambda^{\prime}_{i},\sum_{j\leq
i}\lambda^{\prime}_{i}\right\rrbracket=\left\llbracket
1+\sum_{j<i}\lambda_{i},\sum_{j\leq i}\lambda_{i}\right\rrbracket=B_{i}$

since $j\leq i<t$, we know that $\lambda^{\prime}_{j}=\lambda_{i}$. Secondly,
if $i=t$, then

$B^{\prime}_{t}=\left\llbracket 1+\sum_{j<i}\lambda^{\prime}_{i},\sum_{j\leq
i}\lambda^{\prime}_{i}\right\rrbracket=\left\llbracket
1+\sum_{j<i}\lambda_{i},|s_{t}|+\sum_{j\leq
i}\lambda_{i}\right\rrbracket=B_{t}\cup\left\llbracket 1+\sum_{j\leq
t}\lambda_{j},|s_{t}|+\sum_{j\leq t}\lambda_{j}\right\rrbracket$

as $\lambda^{\prime}_{t}=\lambda_{t}+|s_{t}|$ and
$\lambda^{\prime}_{i}=\lambda_{i}$. Finally, if $i>t$, then

$B^{\prime}_{t}=\left\llbracket 1+\sum_{j<i}\lambda^{\prime}_{i},\sum_{j\leq
i}\lambda^{\prime}_{i}\right\rrbracket=\left\llbracket
1+|s_{t}|+\sum_{j<i}\lambda_{i},|s_{t}|+\sum_{j\leq
i}\lambda_{i}\right\rrbracket=\\{x+|s_{t}|\mid x\in B_{i}\\}.$

We have that
$T_{\lambda^{\prime}}(x)=x+\sum_{j>i}\lambda^{\prime}_{j}-\sum_{j<i}\lambda^{\prime}_{j}$.
We factorize $\lambda^{\prime}_{t}$ to obtain

$T_{\lambda^{\prime}}(x)=\begin{cases}x+\sum_{t>j>i}\lambda^{\prime}_{j}+\sum_{j>t}\lambda^{\prime}_{j}-\sum_{j<i}\lambda^{\prime}_{j}+\lambda^{\prime}_{t}&\text{
if }i<t\\\
x+\sum_{j>i}\lambda^{\prime}_{j}-\sum_{j<i}\lambda^{\prime}_{j}&\text{ if
}i=t\\\
x+\sum_{j>i}\lambda^{\prime}_{j}-\sum_{j<t}\lambda^{\prime}_{j}-\sum_{t<j<i}\lambda^{\prime}_{j}-\lambda^{\prime}_{t}&\text{
if }i>t.\end{cases}$

Replacing $\lambda^{\prime}_{i}$ by $\lambda_{i}$ if $i\neq t$ and
$\lambda^{\prime}_{t}$ by $\lambda_{t}+|s_{t}|$ give that

$\displaystyle T_{\lambda^{\prime}}(x)$
$\displaystyle=\begin{cases}x+\sum_{t>j>i}\lambda_{j}+\sum_{j>t}\lambda_{j}-\sum_{j<i}\lambda_{j}+\lambda_{t}+|s_{t}|&\text{
if }i<t\\\ x+\sum_{j>i}\lambda_{j}-\sum_{j<i}\lambda_{j}&\text{ if }i=t\\\
x+\sum_{j>i}\lambda_{j}-\sum_{j<t}\lambda_{j}-\sum_{t<j<i}\lambda_{j}+\lambda_{t}-|s_{t}|&\text{
if }i>t,\end{cases}$ $\displaystyle=\begin{cases}x+s_{i}+|s_{t}|&\text{ if
}i<t\\\ x+s_{i}&\text{ if }i=t\\\ x+s_{i}-|s_{t}|&\text{ if }i>t.\end{cases}$

Therefore, the circular factors of length 2 of $T_{\lambda^{\prime}}$ are
$x\cdot(x+s_{i}+|s_{t}|)$ if $x\in B_{i}$ and $i<t$, $x\cdot(x+s_{i})$ if
$x\in B_{t}$ and $x\cdot(x+s_{i}-|s_{t}|)$, otherwise.

Now, it remains to find the circular factors of length 2 of
$\psi(T_{\lambda})$. There are two cases to analyze depending on the
translation parameter $s_{t}$.

Let $x$ be an integer in $\llbracket 1,n\rrbracket$. There exist an integer
$i$ such that $x\in B_{i}$.

Suppose that $s_{t}$ is positive. Thus, we have that $k=\sum_{j\leq
t}\lambda_{j}$.

If $i<t$, we have that $x\in\llbracket 1,\sum_{j<t}\lambda_{j}\rrbracket$,
then $x<k$. Also, we have that
$T_{(\lambda_{1},\dots,\lambda_{r})}(x)>k+|s_{t}|$, since
$\sum_{j>t}\lambda_{j}=s_{t}+\sum_{j<t}\lambda_{j}$. Therefore, we obtain that
$\psi_{t}(x\cdot
T_{\lambda}(x))=x\cdot(T_{\lambda}(x)+|s_{t}|)=x\cdot(x+s_{i}+|s_{t}|)$. Since
$i<t$, we know that $x\in B_{i}$ implies that $x\in B^{\prime}_{i}$ and
$T_{\lambda^{\prime}}(x)=x+s_{i}+|s_{t}|$ , the element $x$ is sent to the
same element in both symmetric discrete interval exchanges , as desired.

If $i=t$, we have that $x\in\llbracket 1+\sum_{j<t}\lambda_{j},\sum_{j\leq
t}\lambda_{j}\rrbracket$, then $x<k$. Moreover, we have
$T_{(\lambda_{1},\dots,\lambda_{r})}(x)\in\llbracket\sum_{j<t}\lambda_{j}+1,k+|s_{t}|\rrbracket$,
since $\sum_{j>t}\lambda_{j}=s_{t}+\sum_{j<t}\lambda_{j}$. Therefore, we
obtain that

$\psi_{t}(x\cdot T_{\lambda}(x))=\begin{cases}x\cdot(x+s_{i})&\text{ if
}x<k\\\ x\cdot(x+s_{i})\cdot(x+s_{i}+|s_{t}|)&\text{otherwise.}\end{cases}$

Which means that all elements of $B_{t}$ are sent to $(x+s_{i})$, as desired.

If $i>t$, we have that $x\in\llbracket 1+\sum_{j\leq
t}\lambda_{j},n\rrbracket$, then $x>k$. Moreover, we have that
$T_{\lambda}(x)<k+|s_{t}|$, since $\sum_{j\leq
t}\lambda_{j}>|s_{t}|+\sum_{j>t}\lambda_{j}$. Therefore, we obtain that

$\displaystyle~{}\psi_{t}(x\cdot
T_{\lambda}(x))=\begin{cases}x\cdot(x+|s_{t}|)&\text{ if }x\leq
k+|s_{t}|\text{ and }\sigma(x)\leq k,\\\ x\cdot(x+|s_{t}|)\cdot
T_{\lambda}(x)\cdot(T_{\lambda}(x)+|s_{t}|)&\text{ if }x\leq k+|s_{t}|\text{
and }\sigma(x)>k,\\\ (x+|s_{t}|)\cdot T_{\lambda}(x)&\text{ if
}x>k+|s_{t}|\text{ and }T_{\lambda}(x)\leq k,\\\ (x+|s_{t}|)\cdot
T_{\lambda}(x)\cdot(T_{\lambda}(x)+|s_{t}|)&\text{ if }x>k+|s_{t}|\text{ and
}T_{\lambda}(x)>k.\\\ \end{cases}$ (5)

Hence, we have that every element between $k+1$ and $k+|s_{t}|$ is sent to
$x+s_{i}$. Thus, all elements of $B^{\prime}_{t}$ are sent to the correct
value. Moreover, every element of $B^{\prime}_{i}$ with $i>t$ are of the form
$x+|s_{t}|$ corresponding to the last two cases in Equation (5). The circular
factors of length 2 are $(x+|s_{t}|)\cdot
T_{\lambda}(x)=(x+|s_{t}|)\cdot(x+s_{i})$, which can be rewritten to
$y\cdot(y+s_{i}-|s_{t}|)$ if we substitute $y$ to $x+|s_{t}|$, as desired.

If $s_{t}$ is negative, a similar case-by-case analysis shows the equality. ∎

Now, we are ready to prove Lemma 3.

###### of Lemma 3.

By Lemma 4, we have that

$\psi_{t}(T_{(\lambda_{1},\dots,\lambda_{r})})=T_{(\lambda_{1},\dots,\lambda_{t}+|s_{t}|,\dots,\lambda_{r})},$

for all $t\in\llbracket 1,r\rrbracket$. As a substitution on a set of circular
words preserves the number of circular words, we have that

$\gamma(T_{(\lambda_{1},\dots,\lambda_{r})})=\gamma(\psi_{t}(\lambda_{1},\dots,\lambda_{r}))=\gamma(T_{(\lambda_{1},\dots,\lambda_{t}+|s_{t}|,\dots,\lambda_{r})})$

as claimed. ∎

######  Theorem 1.

The function $f$ counts the orbits of the symmetric discrete interval exchange
$T_{\lambda}$.

###### Proof.

By Lemma 1, we know there exists an integer $t\in\llbracket 1,r\rrbracket$
such that $\lambda_{t}\geq|s_{t}|$ for any composition $\lambda$. Also,
$(\lambda_{1},\dots,\lambda_{t}-|s_{t}|,\dots,\lambda_{r})$ and
$(\lambda_{1},\dots,\lambda_{t-1},\lambda_{t+1},\dots,\lambda_{r})$ are both
compositions, since $\lambda_{t}-|s_{t}|\geq 0$. Hence, the function $f$ is
well-defined.

We show case by case that the recursive step of the function $f$ preserves the
number of orbits. First, $\gamma(\lambda_{1})=\lambda_{1}$, since
$T_{\lambda_{1}}(x)=x$ for all $x\in\llbracket 1,\lambda_{1}\rrbracket$.
Secondly, if $|s_{t}|=0$, we know that
$\gamma(\lambda_{1},\dots,\lambda_{r})=\lambda_{t}+\gamma(\lambda_{1},\dots,\lambda_{t-1},\lambda_{t+1},\dots,\lambda_{r})$
by Lemma 2. Thirdly, if $|s_{t}|=\lambda_{t}$, we know that
$\gamma(\lambda_{1},\dots,\lambda_{r})=\gamma(\lambda_{1},\dots,\lambda_{t}-|s_{t}|,\dots,\lambda_{r})$
by Lemma 3. However, $\lambda_{t}=|s_{t}|$ implies
$(\lambda_{1},\dots,\lambda_{t}-|s_{t}|,\dots,\lambda_{r})=(\lambda_{1},\dots,\lambda_{t-1},0,\lambda_{t+1},\dots,\lambda_{r})=\gamma(\lambda_{1},\dots,\lambda_{t-1},\lambda_{t+1},\dots,\lambda_{r})$
as desired. Finally, if $\lambda_{t}>|s_{t}|$, the equality
$\gamma(\lambda_{1},\dots,\lambda_{r})=\gamma(\lambda_{1},\dots,\lambda_{t}-|s_{t}|,\dots,\lambda_{r})$
follows directly from Lemma 3. Thus, the function $f$ counts the number of
orbits of $T_{\lambda}$. ∎

######  Corollary 1.

A symmetric discrete interval exchange is minimal if and only if
$f(\lambda_{1},\dots,\lambda_{r})=1$.

##  4 Tree of circular compositions

How can we use the function $f$ to enumerate the compositions defining minimal
symmetric discrete interval exchange? For minimal symmetric discrete
$2$-interval exchanges, solutions are given by the Raney tree [3, 13] (also
called Calkin-Wilf tree [5]) or the Stern-Brocot tree [4, 17]. A composition
$\lambda$ is called _circular_ if the symmetric discrete interval exchange
$T_{\lambda}$ is minimal. We propose a generalization of the Raney tree to
enumerate circular compositions of any lengths.

The _Raney tree_ is a complete infinite binary tree whose nodes are reduced
fractions, described recursively by the following rules :

  1. $\bullet$

the root of the tree is the fraction $\frac{1}{1}$;

  2. $\bullet$

each vertex $\frac{i}{j}$ has two children: the left child is the fraction
$\frac{i}{i+j}$ and the right child is the $\frac{i+j}{j}$.

Figure 2: Raney tree

Figure 2 shows the first few levels of the Raney tree. This tree contains each
reduced positive rational number exactly once as shown by Berstel and de Luca
[3], and by Calkin and Wilf [5]. Thus it contains all pairs of coprime natural
numbers. Therefore, the Raney tree contains every circular composition of
length 2 exactly once.

Observe that applying the function $f$ to any vertex in the Raney tree gives
the path from that vertex to the root $1/1$ in the Raney tree. Therefore, we
can use the function $f$ to generalize the Raney tree. The root of this
generalized tree is still $(1,1)$, since it is an extension of the Raney tree.
A circular composition $(\lambda_{1},\dots,\lambda_{r})$ has children of the
form $(\lambda_{1},\dots,\lambda_{t}+|s_{t}|,\dots,\lambda_{r})$ for all
$t\in\llbracket 1,r\rrbracket$ and
$(\lambda_{1},\dots,\lambda_{t},|\delta_{t}|,\lambda_{t+1},\dots,\lambda_{r})$
for all $t\in\llbracket 0,r\rrbracket$, where $\delta_{t}=n-2\sum_{j\leq
t}\lambda_{j}$. Figure 3 shows all the possible children of the composition
$(1,1,2,4)$. Note that $|s_{t}|$ cannot be zero, otherwise the composition is
not circular by Lemma 2. Moreover, the children of
$(\lambda_{1},\dots,\lambda_{r})$ of the form
$(\lambda_{1},\dots,\lambda_{t}+|s_{t}|,\dots,\lambda_{r})$ are circular by
Lemma 3. There are two problems with the children of
$(\lambda_{1},\dots,\lambda_{r})$ of the form
$(\lambda_{1},\dots,\lambda_{t},|\delta_{t}|,\lambda_{t+1},\dots,\lambda_{r})$.
First, if $\delta_{t}=0$ (e.g. $\delta_{3}$ in Figure 3), the result is the
same symmetric discrete interval exchange. We want to avoid this case as it
does not add any new information. Secondly, the resulting composition has two
parents. For example, the parents of the circular composition $(1,1,2,4)$ are
the compositions $(1,1,4)$ ($\delta=(6,4,\underline{2},-6)$) and $(1,1,2)$
($\delta=(4,2,0,\underline{-4})$) (as shown in Figure 4).

(a) Children of type 1

(b) Children of Type 2 (Note that $(1,1,2,0,4)$ is not a composition)

Figure 3: Children of Type 1 and 2 of the composition $(1,1,2,4)$ whose
translation vector is $(7,5,2,-4)$ and $\delta=(8,6,4,0,-8)$ Figure 4: The top
right discrete interval is $(1,1,4)$ and the top left one is $(1,1,2)$ both
can be the parent of $(1,1,2,4)$. The $\delta$ of $(1,1,4)$ is $(6,4,2,-6)$
and the $\delta$ of $(1,1,2)$ is $(4,2,0,-4)$. Hence,
$(1,1,|\delta_{2}|,2)=(1,1,2,4)=(1,1,2,|\delta_{4}|)$

Adding $\delta_{t}$ preserves the number of orbits of the symmetric discrete
interval exchange, since the $(t+1)$-th translation parameter of the
composition
$(\lambda_{1},\dots,\lambda_{t},|\delta_{t}|,\lambda_{t+1},\dots,\lambda_{r})$
is by definition $s_{t+1}=\sum_{j>t}\lambda_{t}-\sum_{j\leq
t}\lambda_{t}=n-2\sum_{j\leq t}=\delta_{t}$. By Lemma 3, these children of
$(\lambda_{1},\dots,\lambda_{r})$ are also circular. Compositions constructed
by the two rules have two parents, since adding $\delta_{t}$ or $\lambda_{t}$
if $\delta_{t}>0$ (resp. $\lambda_{t+1}$ if $\delta_{t}<0$) produces the same
composition (see Figure 4). To ensure that every child is a composition and
that each composition has a single parent, we add a condition on $\delta$.

The _tree of circular compositions_ is an infinite tree described by the
following recursive rules:

  1. $\bullet$

the root of the tree is the composition $(1,1)$;

  2. $\bullet$

each vertex $(\lambda_{1},\dots,\lambda_{r})$ has children of the form:

    1. Type 1:

$(\lambda_{1},\dots,\lambda_{t}+|s_{t}|,\dots,\lambda_{r})$ for all
$t\in\llbracket 1,r\rrbracket$;

    2. Type 2:

if $\delta_{t}>\lambda_{t+1}$ or $-\delta_{t}>\lambda_{t}$,
$(\lambda_{1},\dots,\lambda_{t},|\delta_{t}|,\lambda_{t+1},\dots,\lambda_{r})$
for all $t\in\llbracket 0,r\rrbracket$;

where $\delta_{t}=n-\sum_{j\leq t}\lambda_{j}$.

Figure 5: The tree of circular compositions

Figure 5 shows the first few levels of the tree of circular compositions. Note
that $\delta_{0}>\lambda_{1}$ and $-\delta_{r}>\lambda_{r}$, hence the
condition is always satisfied in those cases. Thus, the parent of $(1,1,2,4)$
is $(1,1,2)$, since $-\delta_{3}=4>\lambda_{3}$ and $(1,1,4)$ is not its
parent since $\delta_{3}=2<\lambda_{4}=4$ and $-\delta_{3}=-2<\lambda_{3}=2$.
Now we prove that each circular composition is a child of type $1$ or $2$ but
not both and has a unique parent.

######  Lemma 5.

Let $(\lambda_{1},\dots,\lambda_{r})$ be a circular composition and $t$ an
integer in $\llbracket 1,r\rrbracket$. If $\lambda_{t}>|s_{t}|$, then
$\lambda_{i}<|s_{i}|$ for all $i\in\llbracket 1,r\rrbracket$, $i\neq t$.

###### Proof.

Let $t$ be an integer in $\llbracket 1,r\rrbracket$ such that
$\lambda_{t}>|s_{t}|$. First, we show that $s_{i}>0$ if $i<t$ (resp. $s_{i}<0$
if $i>t$). Let $i$ be an integer in the set $\llbracket 1,t-1\rrbracket$.

If $s_{t}>0$, by the definition of $s_{t}$ the following inequality is
satisfied:

$\sum_{k>t}\lambda_{k}>\sum_{k<t}\lambda_{k}.$

Since $i<t$ and all $\lambda_{k}$’s are positive, we have that

$\sum_{k>i}\lambda_{k}>\sum_{k>t}\lambda_{k}>\sum_{k<t}\lambda_{k}>\sum_{k<i}\lambda_{k}.$

Hence $s_{i}=\sum_{k>i}\lambda_{k}-\sum_{k<i}\lambda_{k}>0$.

If $s_{t}<0$, by the definition of $s_{t}$, we know that

$\lambda_{t}>|s_{t}|=-s_{t}=\sum_{k<t}\lambda_{k}-\sum_{k>t}\lambda_{k}.$

Moreover, adding $\sum_{k>t}\lambda_{k}$ on both sides, we have that

$\lambda_{t}+\sum_{k>t}\lambda_{k}>\sum_{k<t}\lambda_{k}.$

Since $i<t$ and all $\lambda_{k}$’s are positive, the previous inequality
implies that

$\sum_{k>i}\lambda_{k}\geq\lambda_{t}+\sum_{k>t}\lambda_{k}>\sum_{k<t}\lambda_{k}>\sum_{k<i}\lambda_{k}.$

Hence, $s_{i}=\sum_{k>i}\lambda_{k}-\sum_{k<i}\lambda_{k}>0$ as claimed.

Similar arguments show that, if $i>t$, then $s_{i}<0$.

Now we can show that $\lambda_{i}<|s_{i}|$ if $i\neq t$. There are two cases
to consider.

Suppose that $s_{t}>0$. If $i<t$, the translation parameter $s_{i}$ can be
expressed as a sum of $s_{t}$ and some $\lambda_{k}^{\prime}s$ given below:

$\displaystyle s_{t}+\lambda_{t}+2\sum_{i<j<t}\lambda_{j}+\lambda_{i}=$
$\displaystyle\sum_{j>t}\lambda_{j}-\sum_{j<t}\lambda_{j}+\lambda_{t}+2\sum_{i<j<t}\lambda_{j}+\lambda_{i}$
$\displaystyle=$ $\displaystyle\sum_{j>i}\lambda_{j}-\sum_{j<i}\lambda_{j}$
$\displaystyle=$ $\displaystyle s_{i}.$

Moreover, we have that
$s_{i}=s_{t}+\lambda_{t}+2\sum_{i<j<t}\lambda_{j}+\lambda_{i}>\lambda_{i}$
since $s_{t}$ is positive. Thus, $|s_{i}|=s_{i}>\lambda_{i}$ since $i<t$.

If $i>t$, the translation parameter $s_{i}$ can be expressed by $s_{t}$ and
some $\lambda_{k}$ as below:

$\displaystyle s_{t}-\lambda_{t}-2\sum_{t<j<i}\lambda_{j}-\lambda_{i}=$
$\displaystyle\sum_{j>t}\lambda_{j}-\sum_{j<t}\lambda_{j}-\lambda_{t}-2\sum_{t<j<i}\lambda_{j}-\lambda_{i}$
$\displaystyle=$ $\displaystyle\sum_{j>i}\lambda_{j}-\sum_{j<i}\lambda_{j}$
$\displaystyle=$ $\displaystyle s_{i}.$

Since $i>t$, we have that $s_{i}<0$, hence
$|s_{i}|=-s_{t}+\lambda_{t}+2\sum_{t<j<i}\lambda_{j}+\lambda_{i}$ which is a
sum of positive integers since $\lambda_{t}-s_{t}>0$. Hence,
$|s_{i}|>\lambda_{i}$ as claimed.

Similar arguments show that the lemma also holds in the case where $s_{t}$ is
negative. ∎

######  Lemma 6.

Let $(\lambda_{1},\dots,\lambda_{r})$ be a circular composition and $t$ be an
integer in $\llbracket 1,r\rrbracket$. If $\lambda_{t}=|s_{t}|$, then there
exists an integer $d\in\\{t-1,t+1\\}$ such that $\lambda_{d}=|s_{d}|$ and
$\lambda_{i}<|s_{i}|$ for all $i\in\llbracket 1,r\rrbracket-\\{t,d\\}$.
Moreover $\lambda_{d}\neq\lambda_{t}$.

###### Proof.

Let $(\lambda_{1},\dots,\lambda_{r})$ be a circular composition such that
$\lambda_{t}=|s_{t}|$. First, we check that $\lambda_{d}$ exists.

If $s_{t}>0$, then

$\lambda_{t}=\sum_{k>t}\lambda_{k}-\sum_{k<t}\lambda_{k}\quad\Rightarrow\quad\lambda_{t+1}=\sum_{k<t+1}\lambda_{k}-\sum_{k>t+1}\lambda_{k}=|s_{t+1}|.$

Similarly, if $s_{t}<0$, we have that $\lambda_{t-1}=|s_{t-1}|$.

Secondly, we have to show that $\lambda_{t}\neq\lambda_{d}$. Suppose that we
are in the case $d=t+1$. Suppose further that $\lambda_{t}=\lambda_{d}$. Since
$\lambda_{t}=|s_{t}|$, we have that
$\gamma(\lambda_{1},\dots,\lambda_{r})=\gamma(\lambda_{1},\dots,\lambda_{t-1},\lambda_{t+1},\dots,\lambda_{r})$
by Theorem 1. Moreover,
$\lambda_{t}=\sum_{k>t}\lambda_{k}-\sum_{k<t}\lambda_{k}$ and
$\lambda_{t}=\lambda_{t+1}$ imply that
$0=\sum_{k>t+1}\lambda_{k}-\sum_{k<t}\lambda_{k}$. Hence,
$\gamma(\lambda_{1},\dots,\lambda_{t-1},\lambda_{t+1},\dots,\lambda_{r})=\lambda_{t+1}+\gamma(\lambda_{1},\dots,\lambda_{t-1},\lambda_{t+2},\dots,\lambda_{r})$
by Lemma 2. Thus $\gamma(\lambda_{1},\dots,\lambda_{r})$ is greater than 1
since $\lambda_{t+1}>0$, a contradiction. The case where $d=t-1$ is similar.

Finally, we have to check that $\lambda_{i}<|s_{i}|$ if $i\neq d$ and $i\neq
t$. Suppose that $s_{t}>0$, then $d=t+1$. If $i<t$, then we have that
$\lambda_{t}=s_{t}=\sum_{k>t}\lambda_{k}-\sum_{k<t}\lambda_{k}$. We isolate
$\lambda_{i}$ in this equation to obtain
$\lambda_{i}=-\sum_{j<i}\lambda_{j}-\sum_{i+1<j\leq
t}\lambda_{j}+\sum_{j>t}\lambda_{j}$. Moreover, we have that

$\displaystyle\lambda_{i}$
$\displaystyle=-\sum_{k<i}\lambda_{k}-\sum_{i+1<k\leq
t}\lambda_{k}+\sum_{k>t}\lambda_{k}+s_{i}-s_{i}$
$\displaystyle=s_{i}-2\sum_{i+1<k\leq t}\lambda_{k}$ $\displaystyle<s_{i}$

since all $\lambda_{k}$’s are positive.

Similar arguments show that if $i>t$, then $\lambda_{i}<|s_{i}|$. To complete
the proof, we use a similar argument to show that $\lambda_{i}<|s_{i}|$ if
$s_{t}<0$. ∎

######  Corollary 2.

Let $(\lambda_{1},\dots,\lambda_{r})$ be a circular composition. If the
composition is not $(1,1)$, then it has a unique parent in the tree of
circular composition.

###### Proof.

There exists a $t\in\llbracket 1,r\rrbracket$ such that
$\lambda_{t}\geq|s_{t}|$ by Lemma 1 and $s_{t}$ is positive, since the
composition is circular by Lemma 2. Therefore, the composition
$(\lambda_{1},\dots,\lambda_{r})$ is a child of type 1 or type 2 of the
composition $\lambda^{\prime}$.

Suppose that $(\lambda_{1},\dots,\lambda_{r})$ is a child of type 1. We know
that $\lambda_{i}<|s_{i}|$ for all $i\in\llbracket 1,r\rrbracket-\\{t\\}$ by
Lemma 5. Thus $(\lambda_{1},\dots,\lambda_{r})$ is not a child of type 2 and
the only valid position to reduce the composition is $t$. So the parent of
$(\lambda_{1},\dots,\lambda_{r})$ is
$\lambda^{\prime}=(\lambda_{1},\dots,\lambda_{t}-|s_{t}|,\dots,\lambda_{r})$.

Suppose that $(\lambda_{1},\dots,\lambda_{r})$ is a child of type 2. We know
that $\lambda_{i}<|s_{i}|$ for all $i\in\llbracket 1,r\rrbracket-\\{t,d\\}$.
Thus $(\lambda_{1},\dots,\lambda_{r})$ is not a child of type 1, since any
$\lambda_{i}\leq|s_{i}|$. If $\delta_{t}>\lambda_{t+1}$ or
$-\delta_{t}>\lambda_{t}$, then the parent of
$(\lambda_{1},\dots,\lambda_{r})$ is
$\lambda^{\prime}=(\lambda_{1},\dots,\lambda_{t-1},\lambda_{t+1},\dots,\lambda_{r})$,
otherwise it is
$\lambda^{\prime}=(\lambda_{1},\dots,\lambda_{t},\lambda_{t+2},\dots,\lambda_{r})$
if $\delta_{t}>0$, or
$\lambda^{\prime}=(\lambda_{1},\dots,\lambda_{t-2},\lambda_{t},\dots,\lambda_{r})$
if $\delta_{t}<0$.

∎

######  Theorem 2.

Every circular composition appears exactly once on the tree of circular
composition.

###### Proof.

First, we show that every composition in the tree is circular. The symmetric
discrete interval exchange $T_{(1,1)}$ is the permutation $(1,2)$ which is
obviously minimal. Let $(\lambda_{1},\dots,\lambda_{r})$ be a composition that
appears in the tree which is not associated with a circular permutation and
such that all compositions appearing in previous levels of the tree are
circular. There exists an integer $t\in\llbracket 1,r\rrbracket$ such that
$\lambda_{t}\geq|s_{t}|$ and

$\gamma(\lambda_{1},\dots,\lambda_{t}-|s_{t}|,\dots,\lambda_{r})=\gamma(\lambda_{1},\dots,\lambda_{r})>1,$

by Theorem 1. The composition
$(\lambda_{1},\dots,\lambda_{t}-|s_{t}|,\dots,\lambda_{r})$ appears in a
previous level of the tree, which is a contradiction. Thus, all the
compositions in the tree are circular.

Secondly, we prove that all circular compositions appear in the tree. The
composition $(1,1)$ is the root of the tree. Let $S$ be the set of all
circular compositions which are not in the tree and
$(\lambda_{1},\dots,\lambda_{r})$ the smallest composition in $S$ ordered them
as in Section 3. There exists a natural number $t\in\llbracket 1,r\rrbracket$
such that $\lambda_{t}\geq|s_{t}|$ and

$\gamma(\lambda_{1},\dots,\lambda_{t}-|s_{t}|,\dots,\lambda_{r})=\gamma(\lambda_{1},\dots,\lambda_{r})$

by Lemma 1. Therefore the composition
$(\lambda_{1},\dots,\lambda_{t}-|s_{t}|,\dots,\lambda_{r})$ cannot be an
element of the tree, otherwise $(\lambda_{1},\dots,\lambda_{r})$ is also an
element of the tree contradicting the minimality of
$(\lambda_{1},\dots,\lambda_{r})$.

Thirdly, we show that no circular composition occurs more than once in the
tree. Let $(\lambda_{1},\dots,\lambda_{r})$ be the smallest composition which
appears more than once in the tree. By Corollary 2, we know that
$(\lambda_{1},\dots,\lambda_{r})$ has a unique parent $\lambda^{\prime}$. Then
$(\lambda_{1},\dots,\lambda_{r})$ is the child of two distinct vertices both
labelled by $\lambda^{\prime}$, contradicting the minimality of
$(\lambda_{1},\dots,\lambda_{r})$. Therefore, each circular composition
appears only once in the tree. ∎

##  5 Cyclic type

The _cyclic type_ of a symmetric discrete interval exchange is a partition
$\ell_{1}^{\alpha_{1}}\dots\ell_{k}^{\alpha_{k}}$ where
$\ell_{1}>\ell_{2}>\dots>\ell_{k}$, $\ell_{i}$ is the length of an orbit of
$T_{\lambda}$ and $\alpha_{i}$ is the number of orbits of length $\ell_{i}$.
For example, the cyclic type of $T_{(3,5,4,2)}$ is the partition $8^{1}3^{2}$.
The cyclic type of symmetric discrete 2-interval exchanges is already known.

######  Lemma 7.

(folklore) Let $(\lambda_{1},\lambda_{2})$ be a composition. The cyclic type
of the symmetric discrete interval exchange
$T_{(\lambda_{1},\dots,\lambda_{r})}$ is the partition

$\left(\frac{\lambda_{1}+\lambda_{2}}{\gcd(\lambda_{1},\lambda_{2})}\right)^{\gcd(\lambda_{1},\lambda_{2})}.$

The cyclic type of symmetric discrete 3-interval exchange can also be
described by the $\gcd$ function.

######  Lemma 8.

Let $(\lambda_{1},\lambda_{2},\lambda_{3})$ be a composition. The integers
$s_{1},\ s_{2}$ and $s_{3}$ are multiples of
$\gcd(\lambda_{1}+\lambda_{2},\lambda_{2}+\lambda_{3})$.

###### Proof.

The result is straightforward for $s_{1}=\lambda_{2}+\lambda_{3}$ and
$s_{3}=-\lambda_{1}-\lambda_{2}$. Moreover, subtracting
$\lambda_{2}+\lambda_{3}$ from $\lambda_{1}+\lambda_{2}$, we obtain that
$\gcd(\lambda_{1}+\lambda_{2},\lambda_{2}+\lambda_{3})=\gcd(\lambda_{1}-\lambda_{3},\lambda_{2}+\lambda_{3})$.
Thus $s_{2}=|\lambda_{3}-\lambda_{1}|$ is a multiple of
$\gcd(\lambda_{1}+\lambda_{2},\lambda_{2}+\lambda_{3})$. ∎

Now, we can describe the number of orbits of a symmetric discrete 3-interval
exchange using the $\gcd(\lambda_{1}+\lambda_{2},\lambda_{2}+\lambda_{3})$.

######  Theorem 3.

The orbit of $x\in\llbracket 1,n\rrbracket$ in the symmetric discrete interval
exchange $T_{(\lambda_{1},\lambda_{2},\lambda_{3})}$ is the set

$\left\\{x+kd\,\middle|\,k\in\mathbb{N}\,\mathrm{and}\,\frac{1-x}{d}\leq
k\leq\frac{n-x}{d}\right\\},$

where $d=gcd(\lambda_{1}+\lambda_{2},\lambda_{2}+\lambda_{3})$.

For example, the cyclic decomposition of the symmetric discrete interval
exchangeof $T_{(9,1,4)}$ is $(1,6,11)(2,7,12)(3,8,14)(4,9,14)(5,10)$.
Therefore, the orbit of $9$ is $\\{9+5k|-8/5\leq k\leq 5/5\\}=\\{4,9,14\\}$ .

###### Proof.

Let $d$ be the $\gcd(\lambda_{1}+\lambda_{2},\lambda_{2}+\lambda_{3})$ and $x$
be an integer in $\llbracket 1,n\rrbracket$. First, we show by induction that
$T^{(k)}_{(\lambda_{1},\lambda_{2},\lambda_{3})}(x)=x+id$. We know that
$T^{0}_{(\lambda_{1},\lambda_{2},\lambda_{3})}(x)=x+0\cdot d$ and
$T^{1}_{(\lambda_{1},\lambda_{2},\lambda_{3})}(x)=x+s_{i}=x+id$ since $s_{i}$
is a multiple of $d$ as shown in Lemma 8. Let computes

$T^{(k+1)}_{(\lambda_{1},\lambda_{2},\lambda_{3})}(x)=T(T^{k}_{(\lambda_{1},\lambda_{2},\lambda_{3})}(x))=T(x+id)=x+id+s_{i}$

by induction. Moreover, $s_{i}$ is a multiple of $d$ by Lemma 8. Hence, we
have that $T^{(k+1)}_{(\lambda_{1},\lambda_{2},\lambda_{3})}(x)=x+jd$.

By the definition of $T_{(\lambda_{1},\lambda_{2},\lambda_{3})}$, we have that
$1\leq x+kd\leq n$ which gives that $(1-x)/d\leq k\leq(n-x)/d$. ∎

######  Corollary 3.

Let $(\lambda_{1},\lambda_{2},\lambda_{3})$ be a composition of
$n=\lambda_{1}+\lambda_{2}+\lambda_{3}$. Take
$d=\gcd(\lambda_{1}+\lambda_{2},\lambda_{2}+\lambda_{3})$. Let $q$ and $r$ be
integers with $0\leq r<d$ such that $n=qd+r$. The cyclic type of
$T_{(\lambda_{1},\lambda_{2},\lambda_{3})}$ is $q^{d}$ if $r=0$ and
$(q+1)^{r}q^{d-r}$ otherwise. Moreover
$d=\gamma(T_{(\lambda_{1},\lambda_{2},\lambda_{3})})$.

###### Proof.

By Theorem 3, we have that the orbit of $x$ is the set

$\left\\{x+kd\,\middle|\,k\in\mathbb{N}\,\mathrm{and}\,\frac{1-x}{d}\leq
k\leq\frac{n-x}{d}\right\\}.$

Therefore, every element in the orbit of $x$ is congruent to $x$ modulo $d$.
Hence, the number of orbit is the number of classes modulo $d$, which is
exactly $d$. The cardinality of $\gamma(x)$ is $[n/d]$ if $x\bmod d<r$ or
$[n/d]+1$ if $x\bmod d\geq r$. ∎

The symmetric discrete interval exchanges $T_{\lambda}$ where $\lambda$ is a
composition of length 2 or 3 has simple cyclic type. For symmetric discrete
interval exchanges of length 4 or more, no such description is known. As a
matter of fact, it does not seem to have any relation between the length of
the orbits in the cyclic type. However computer testing suggests that if
$\ell_{1}^{\alpha_{1}}\dots\ell_{k}^{\alpha^{k}}$ is the cyclic type of
$T_{(\lambda_{1},\dots,\lambda_{r})}$, then $k\leq\lceil\frac{r-1}{2}\rceil$.

Acknowledgement. I would like to thank Christophe Reutenauer, Alexandre
Blondin Massé, Vincent Delecroix and Michael Rao for their suggestions and
helpful comments. This work was supported by NSERC graduate scholarship.

## References

  * [1] V. I. Arnold.  Small denominators and problems of stability of motion in classical and celestial mechanics.  Uspehi Mat. Nauk, 18(6 (114)):91–192, 1963.  translated in Russian Math. Surveys 18:86–194, 1963.
  * [2] V. I. Arnold.  Arnold’s problems.  Springer-Verlag, Berlin; PHASIS, Moscow, 2004.  Translated and revised edition of the 2000 Russian original, With a preface by V. Philippov, A. Yakivchik and M. Peters.
  * [3] Jean Berstel and Aldo de Luca.  Sturmian words, Lyndon words and trees.  Theoret. Comput. Sci., 178(1-2):171–203, 1997.
  * [4] Achille Brocot.  Calcul des rouages par approximation, nouvelle méthode.  Revue Chonométrique, 3:186–194, 1861.
  * [5] Neil Calkin and Herbert S. Wilf.  Recounting the rationals.  Amer. Math. Monthly, 107(4):360–363, 2000.
  * [6] Sébastien Ferenczi and Luca Q. Zamboni.  Structure of $K$-interval exchange transformations: induction, trajectories, and distance theorems.  J. Anal. Math., 112:289–328, 2010.
  * [7] Sébastien Ferenczi and Luca Q. Zamboni.  Clustering words and interval exchanges.  J. Integer Seq., 16(2):Article 13.2.1, 9, 2013.
  * [8] Anna Karnauhova and Stefan Liebscher.  Connected components of meanders: I. Bi-rainbow meanders.  Discrete Contin. Dyn. Syst., 37(9):4835–4856, 2017.
  * [9] Sébastien Labbé.  $3$-dimensional Continued Fraction Algorithms Cheat Sheets.  ArXiv e-prints, November 2015.
  * [10] Artur O. Lopes and Luiz Fernando C. da Rocha.  Invariant measures for Gauss maps associated with interval exchange maps.  Indiana Univ. Math. J., 43(4):1399–1438, 1994.
  * [11] V. I. Oseledec.  The spectrum of ergodic automorphisms.  Dokl. Akad. Nauk SSSR, 168:1009–1011, 1966.
  * [12] Igor Pak and Amanda Redlich.  Long cycles in $abc$-permutations.  Funct. Anal. Other Math., 2(1):87–92, 2008.
  * [13] George N. Raney.  On continued fractions and finite automata.  Math. Ann., 206:265–283, 1973.
  * [14] Gérard Rauzy.  Échanges d’intervalles et transformations induites.  Acta Arith., 34(4):315–328, 1979.
  * [15] Christophe Reutenauer.  Personnal communication, November 2016.
  * [16] Fritz Schweiger.  Multidimensional Continued Fraction.  Oxford Univ. Press, New York, 2000.
  * [17] M. A. Stern.  Über eine zahlentheoretische funktion.  j. reine angew. Math., 55:193–220, 1858.