---
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.' 
author:
- Mélodie Lapointe
bibliography:
- 'bibliographie.bib'
nocite: '[@*]'
title: Number of Orbits of Discrete Interval Exchanges
---

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 [@O1966] to generalize circle rotations following some ideas of Arnold [@A1963; @A2004].  The discrete analogue maps were introduced by Ferenczi and Zamboni in 2013 [@FZ2013] 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 [@FZ2013] 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 [@PR2008].  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 [@R1979].  Other examples are given by the multidimensional continued fraction algorithms (see [@L2015; @S2000]). 

This paper is organized as follows.  In Section \[sec:def\], 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 \[sec:counting\].  In Section \[sec:tree\], 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 [@PR2008].  Moreover, we give the cyclic type of these discrete interval exchanges. 

Note that the recursive function counting the number of orbits presented in Theorem \[thm:algo\], Corollary \[cor:cycle\_type\_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 [@R2016]. 

After submission, we discovered that Karnauhova and Liebscher [@KL2017] (2017) have given a similar algorithm as ours (Theorem \[thm:algo\]).  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. 

Discrete interval exchange
==========================

 \[sec:def\]

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 [@FZ2013] (as they are defined in [@FZ2013]: for $\pi \in S_r$, let $\pi(k) = r-k+1$ for all $k \in {\llbracket 1, r \rrbracket}$). 

 \[D:DIET\] 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 $$\begin{aligned}
        s_i = \sum_{j > i} \lambda_j - \sum_{j < i} \lambda_j. 
    \end{aligned}$$ 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 \[fig:DIET\].  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. 

in [1,2,...,14]{} [ node () at (,0) [$\x$]{}; ]{} in [1,2,...,14]{} [ node () at (,-2) [$\x$]{}; ]{} (0.6,-0.4) rectangle (3.4,0.4); (3.6,-0.4) rectangle (8.4,0.4); (8.6,-0.4) rectangle (12.4,0.4); (12.6,-0.4) rectangle (14.4,0.4); (11.6,-1.6) rectangle (14.4,-2.4); (6.6,-1.6) rectangle (11.4,-2.4); (2.6,-1.6) rectangle (6.4,-2.4); (0.6,-1.6) rectangle (2.4,-2.4); (2,-0.4) – (13,-1.6); (6,-0.4) – (9,-1.6); (10.5,-0.4) – (4.5,-1.6); (13.5,-0.4) – (1.5,-1.6); node at (2,0.7) [$B_1$]{}; node at (6,0.7) [$B_2$]{}; node at (10.5,0.7) [$B_3$]{}; node at (13.5,0.7) [$B_4$]{}; node at (13,-2.7) [$B_{\sigma(1)}$]{}; node at (9,-2.7) [$B_{\sigma(2)}$]{}; node at (4.5,-2.7) [$B_{\sigma(3)}$]{}; node at (1.5,-2.7) [$B_{\sigma(4)}$]{};

Counting Orbits
===============

 \[sec:counting\]

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. 

 \[l:existence\] 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|$.

There exists an integer $t$ such that $$\begin{aligned}
        \sum_{i < t} \lambda_i \leq \sum_{i \geq t } \lambda_i & \text{ and } 
        \sum_{i \leq t} \lambda_i \geq \sum_{i > t} \lambda_i,
    \end{aligned}$$ since all $\lambda_i$ are positive integers.  By isolating $\lambda_{t}$ in both inequalities, we obtain $$\begin{aligned}
        \sum_{i < t} \lambda_i - \sum_{i > t } \lambda_i \leq \lambda_t& \text{ and } 
        \lambda_t \geq  \sum_{i > t} \lambda_i - \sum_{i < t} \lambda_i ,
    \end{aligned}$$

We combine both inequalities to obtain $$\begin{aligned}
        \lambda_t \geq  \left| \sum_{i > t} \lambda_i - \sum_{i < t} \lambda_i \right|  = |s_t|,
    \end{aligned}$$ by Definition \[D:DIET\]. 

**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 \[sec:tree\]. 

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}
    \label{eqn:formule}$$ We show that $f$ counts the number of orbits of any [symmetric discrete interval exchange]{} i.e. $f(\lambda) = \gamma(T_{\lambda})$.

The [symmetric discrete interval exchange]{} $T_{(3,5,4,2)}$ has $3$ cycles as shown previously and $$\begin{aligned}
        f(3,5,4,2) & = f(3,2,4,3) = f(3,2,1,2) \\
                   & = 2 + f(3,1,2) = 2 + f(1,2) = 2 + f(1,1) = 2 + f(1)\\ 
                   & = 3. 
    \end{aligned}$$ The values of $t$ and the corresponding translation parameter at each step are in Table \[t:calcul\_f\]. 

   $\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     

  : 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.[]{data-label="t:calcul_f"}

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. 

 \[l:addcycles\] 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. 

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 $$\begin{aligned}
~\label{eq:proof}
        T_{\lambda}(x) = x + s_i
    \end{aligned}$$ 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 \[D:DIET\]. 

If $x \in B_t$, then Equation  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'}$; that is , $T_{\lambda} | H = \omega^{-1}\circ T_{\lambda'} \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'})$.

Suppose that $x \notin B_t$. Let $\lambda' = (\lambda'_1,\dots,\lambda'_{r-1})$ where $\lambda'_i = \lambda_i $ if $i < t$ and $\lambda'_i = \lambda_{i+1}$ otherwise.  Note that $T_{\lambda'}$ is the [symmetric discrete interval exchange]{} where $B'_1,\dots, B'_{r-1}$ are subintervals of ${\llbracket 1, n - \lambda_t \rrbracket}$ defined by $B'_i = \llbracket 1 + \sum_{j < i} \lambda'_i, \sum_{j \leq i} \lambda'_i \rrbracket$. Its translation parameters are defined by $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$. Note that $T_{\lambda'} = T_{{(\lambda_1,\dots, \lambda_{t-1},\lambda_{t+1},\dots,\lambda_r)}}$.

First, we describe the sets $B_i$ using the sets $B'_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'_j, \sum_{j \leq i} \lambda'_j \right\rrbracket = B'_i$$ since $j \leq i < t$, we know that $\lambda_j = \lambda'_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'_i, \lambda_t + \sum_{j \leq i} \lambda'_i \right\rrbracket = \{x + \lambda_t \mid x \in B'_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'_i$.

Secondly, we want to show that $T_{\lambda}(x)  = T_{\lambda'}(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'_j$ if $j < t$ and by $\lambda'_{j-1}$ otherwise gives $$\begin{aligned}
        T_{\lambda}(x) & = \begin{cases}
        x + \sum_{j > i }  \lambda'_j- \sum_{j < i }  \lambda'_j + \lambda_t  & \text{ if } i < t \\
        x + \sum_{j > i } \lambda'_j - \sum_{j < i }  \lambda'_j + \lambda_t  & \text{ if } i > t,
        \end{cases} \\
        & = \begin{cases}
        x + s_i + \lambda_t & \text{ if } i < t \\
        x + s_i  - \lambda_t & \text{ if } i > t.
        \end{cases}
    \end{aligned}$$

Hence, $T_{\lambda}|H$ is conjugated to $T_{\lambda'}$ 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. 

 \[l:diffcycles\] 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: $$\begin{aligned}
    \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}
    \label{def:morphism}\end{aligned}$$ 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 $$\begin{aligned}
    \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}\end{aligned}$$

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. 

 \[l:morphism\] 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_ia_{(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. 

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 \[D:DIET\].  Let $\lambda' = (\lambda'_1,\dots,\lambda'_r)$ be a composition where $\lambda'_t = \lambda_t + |s_t|$ and $\lambda'_i = \lambda_i$ if $t \neq i$. Recall that $T_{\lambda'}$ is the [symmetric discrete interval exchange]{} where $B'_1,\dots, B'_r$ are subintervals of ${\llbracket 1, n + |s_t| \rrbracket}$ defined by $B'_i = \llbracket 1 + \sum_{j < i} \lambda'_i, \sum_{j \leq i} \lambda'_i \rrbracket$ and its translation parameters are $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$. Note that the previous definition implies $T_{\lambda'_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'}$ using $\lambda$ and $B_i$ instead of $\lambda'$ and $B'_i$.

To describe $B'_i$ using the sets $B_i$, we have three cases to consider.  First, if $i < t$, then $$B'_i = \left\llbracket 1 + \sum_{j < i} \lambda'_i, \sum_{j \leq i} \lambda'_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'_j = \lambda_i$. Secondly, if $i = t$, then $$B'_t = \left\llbracket 1 + \sum_{j < i} \lambda'_i, \sum_{j \leq i} \lambda'_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'_t = \lambda_t + |s_t|$ and $\lambda'_i = \lambda_i$. Finally, if $i > t$, then $$B'_t = \left\llbracket 1 + \sum_{j < i} \lambda'_i, \sum_{j \leq i} \lambda'_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'}(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_{t > j > i }  \lambda'_j + \sum_{j > t } \lambda'_j - \sum_{j < i }  \lambda'_j + \lambda'_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 & \text{ if } i > t.
        \end{cases}$$ Replacing $\lambda'_i$ by $\lambda_i$ if $i \neq t$ and $\lambda'_t$ by $\lambda_t + |s_t|$ give that $$\begin{aligned}
        T_{\lambda'}(x) & = \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} \\
        & = \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}
    \end{aligned}$$ Therefore, the circular factors of length 2 of $T_{\lambda'}$ 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'_i$ and $T_{\lambda'}(x) = x +s_i + |s_t|$ , the element $x$ is sent to the same element in both [symmetric discrete interval exchange]{}s , 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 $$\begin{aligned}
~\label{eq:cases}
        \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}
    \end{aligned}$$ Hence, we have that every element between $k+1$ and $k+|s_t|$ is sent to $x + s_i$. Thus, all elements of $B'_t$ are sent to the correct value.  Moreover, every element of $B'_i$ with $i > t$ are of the form $x + |s_t|$ corresponding to the last two cases in Equation .  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 \[l:diffcycles\]. 

By Lemma \[l:morphism\], 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. 

 \[thm:algo\] The function ${f}$ counts the orbits of the [symmetric discrete interval exchange]{} $T_{\lambda}$.

By Lemma \[l:existence\], 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 \[l:addcycles\].  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 \[l:diffcycles\].  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 \[l:diffcycles\].  Thus, the function ${f}$ counts the number of orbits of $T_{\lambda}$.

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

Tree of circular compositions
=============================

 \[sec:tree\]

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 [@BdL1997; @R1973] (also called Calkin-Wilf tree [@CW2000]) or the Stern-Brocot tree [@B1861; @S1858].  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.   the root of the tree is the fraction $\frac{1}{1}$;

2.   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}$.

![ Raney tree[]{data-label="fig:arbre_fractions"}](arbre_fractions)

Figure \[fig:arbre\_fractions\] 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 [@BdL1997], and by Calkin and Wilf [@CW2000].  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 \[fig:exempletype\] 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 \[l:addcycles\].  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 \[l:diffcycles\].  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 \[fig:exempletype\]), 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 \[fig:coincide\]). 

![ 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)$[]{data-label="fig:exempletype"}](arbre_1124_1)

![ 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)$[]{data-label="fig:exempletype"}](arbre_1124)

![ 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|)$[]{data-label="fig:coincide"}](type2)

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 \[l:diffcycles\], 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 \[fig:coincide\]).  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.   the root of the tree is the composition $(1,1)$;

2.   each vertex ${(\lambda_1,\dots,\lambda_r)}$ has children of the form:

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

    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$.

![ The tree of circular compositions[]{data-label="fig:gen_tree"}](arbre_3)

Figure \[fig:gen\_tree\] 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. 

 \[l:unicite1\] 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$.

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's$ given below: $$\begin{aligned}
        s_t + \lambda_t + 2\sum_{i < j < t} \lambda_j + \lambda_i =&  \sum_{j > t} \lambda_j - \sum_{j<t} \lambda_j + \lambda_t + 2\sum_{i < j < t} \lambda_j + \lambda_i   \\
        =& \sum_{j > i} \lambda_j - \sum_{j < i } \lambda_j \\
        =& s_i. 
    \end{aligned}$$ 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: $$\begin{aligned}
        s_t - \lambda_t - 2\sum_{t < j < i} \lambda_j - \lambda_i =& \sum_{j > t} \lambda_j - \sum_{j < t} \lambda_j - \lambda_t - 2\sum_{t < j < i} \lambda_j - \lambda_i \\ 
        =& \sum_{j > i} \lambda_j - \sum_{j < i } \lambda_j \\
        =& s_i. 
    \end{aligned}$$ 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. 

 \[l:unicite2\] 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$.

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 \[thm:algo\].  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 \[l:addcycles\].  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 $$\begin{aligned}
        \lambda_i & = -\sum_{k<i} \lambda_k - \sum_{i+1 < k \leq t} \lambda_k + \sum_{k > t} \lambda_k + s_i - s_i\\
        & = s_i - 2 \sum_{i+1 < k \leq t} \lambda_k \\
        & < s_i
    \end{aligned}$$ 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$.

 \[cor:uni\] 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. 

There exists a $t \in {\llbracket 1, r \rrbracket}$ such that $\lambda_t \geq |s_t|$ by Lemma \[l:existence\] and $s_t$ is positive, since the composition is circular by Lemma \[l:addcycles\].  Therefore, the composition ${(\lambda_1,\dots,\lambda_r)}$ is a child of type 1 or type 2 of the composition $\lambda'$.

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 \[l:unicite1\].  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' = {(\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' = {(\lambda_1,\dots, \lambda_{t-1},\lambda_{t+1},\dots,\lambda_r)}$, otherwise it is $\lambda' = (\lambda_1,\dots,\lambda_t,\lambda_{t+2},\dots, \lambda_r)$ if $\delta_{t} > 0$, or $ \lambda' = (\lambda_1,\dots,\lambda_{t-2},\lambda_{t},\dots, \lambda_r)$ if $\delta_t < 0$.

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

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 \[thm:algo\].  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 \[sec:counting\].  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 \[l:existence\].  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 \[cor:uni\], we know that ${(\lambda_1,\dots,\lambda_r)}$ has a unique parent $\lambda'$. Then ${(\lambda_1,\dots,\lambda_r)}$ is the child of two distinct vertices both labelled by $\lambda'$, contradicting the minimality of ${(\lambda_1,\dots,\lambda_r)}$. Therefore, each circular composition appears only once in the tree. 

Cyclic type
===========

 \[sec: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^13^2$. The cyclic type of symmetric discrete 2-interval exchanges is already known. 

(folklore) \[l:folk\] 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. 

 \[l:s\_gcd\] 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)$.

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)$.

 \[thm:orbit\] 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\vert \, 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 exchange]{}of $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\}$ . 

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 \[l:s\_gcd\].  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 \[l:s\_gcd\].  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$.

 \[cor:cycle\_type\_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)}})$.

By Theorem \[thm:orbit\], we have that the orbit of $x$ is the set $$\left\{x + kd \, \middle\vert \, 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 exchange]{}s $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. 

\[sec:biblio\]
