---
abstract: 'The Three Gaps Theorem states that for any $\alpha \in (0,1)$ and any integer $N \geq 1$, the fractional parts of the sequence $0, \alpha, 2\alpha, \cdots, (N-1)\alpha$ partition the unit interval into $N$ subintervals having at most three distincts lengths. We here provide a new proof of this theorem using zippered rectangles, and present a new gaps theorem (along with two proofs) for general interval exchange transformations. We also touch on the statistics of the Three Gaps Theorem.'
address: Department of Mathematics University of Washington
author:
- 'Diaaeldin (Dia) Taha'
title: 'The Three Gaps Theorem, Interval Exchange Transformations, and Zippered Rectangles'
---

Introduction
============

Orbits, gaps, and randomness
----------------------------

A key theme in dynamical systems is understanding the extent to which orbits of a dynamical system resemble sequences of independent, identically distributed (i.i.d.) random variables. In this paper we consider sequences $s = (s_n)_{n=1}^\infty \subset [0,1)$ arising as orbits of rotations and interval exchange transformations $T:[0,1) \rightarrow [0, 1)$. That is, we consider sequences $s$ defined by $$s_n = T^{n-1}(0),$$ with $T$ being an interval exchange transformation. In what follows, we use the interval $[0, 1)$ and the circle $\mathbb{S}^1$ interchangeably.

Following [@Athreya2012-kd], the equidistribution of a sequence $s = (s_n)_{n=1}^\infty \subset [0,1)$ can be considered as a first order statistical measure of randomness. Specifically, a sequence $s = (s_n)_{n=1}^\infty \subset [0,1)$ is said to *equidistribute* if the measures $\Delta_N = \frac{1}{N}\sum_{n=1}^N \delta_{s_n}$ weak-$\ast$ converge to the Lebesgue measure $\operatorname{Leb}_{[0,1)}$ on the unit interval as $N \to \infty$. For the orbit sequences $s = (T^n x)_{n=1}^\infty$, ergodicity of the map $T$ implies this convergence for almost every starting point $x$, and unique ergodicity strengthens this to every point. This covers the first order statistics of the sequences.

A finer measure of randomness is whether the *gap distribution* for the sequence $(s_n)_{n=1}^\infty$ resembles that of an i.i.d sequence of uniformly distributed random variables $(X_n)_{n=1}^\infty \subset [0,1)$. More precisely, given a finite segment $(s_n)_{n=1}^N$, the points arrange themselves on the unit interval $$0 \leq s_{\sigma_{s, N}(1)} \leq s_{\sigma_{s, N}(2)} \leq \cdots \leq s_{\sigma_{s, N}(N)} < 1,$$ with $\sigma_{s, N} : \{1, 2, \cdots, N\} \to \{1, 2, \cdots, N\}$ denoting a permutation of $\{1, 2, \cdots, N\}$ induced by the order of the points. The gaps $$s_{\sigma_{s,N}(1)} - 0,\ s_{\sigma_{s,N}(2)} - s_{\sigma_{s,N}(1)},\ \cdots,\ s_{\sigma_{s,N}(N)} - s_{\sigma_{s,N}(N-1)}, 1 - s_{\sigma_{s,N}(N)}$$ form a multiset $\widetilde{\operatorname{Gaps}}_{s, N}$. The limiting behavior of the normalized gap distribution $$\lim_{N \to \infty} \frac{\#\left((N \cdot \widetilde{\operatorname{Gaps}}_{s, N}) \cap (a, b)\right)}{N}$$ for $0 \leq a  < b \leq \infty$ gives us the second order statistics of the sequence. For an iid sequence of uniformly distributed variables $(X_n)_{n=1}^\infty$, the limiting behavior is Poiassonian: for any $t>0$, $$\lim_{N \to \infty} \frac{\#\left((N \cdot \widetilde{Gaps}_{(X_n)_{n=1}^\infty, N} \cap (t, \infty))\right)}{N} = e^{-t}.$$ Sequences $s$ whose gaps stray from that Poissonian limiting behavior are called *exotic* in [@Athreya2012-kd]. The interested reader should refer to [@Athreya2012-kd] for examples of exotic sequences, and to get an understanding of the dynamical approach to gap distributions in general.

Rotations, IETS, and gaps
-------------------------

Circle rotations and interval exchange transformations (IETs for short) are low complexity maps (zero topological entropy) essential to the study of polygonal billiards and linear flows on translation surfaces. In this paper, we study gaps for sequences $s$ that arise as orbits of circle rotations $s = (R_\alpha^n0)_{n=0}^\infty$, and interval exchange transformations $s = (T^n0)_{n=0}^\infty$. Our main results are \[theorem: d + 2 gap theorem\], \[theorem: gap distribution for circle rotation\], and \[theorem: gap distribution for iets\], along with a new proof for the Three Gap Theorem (\[theorem: three gap theorem\]).

We start by presenting the definition of interval exchange transformations, and follow it with a short exposition of the Three Gap Theorem to provide historical context.

Interval Exchange Transformations {#subsection: interval exchange transformations}
---------------------------------

Given $\lambda = (\lambda_1, \lambda_2, \cdots, \lambda_d) \in \mathbb{R}^n$ with $\lambda_i \geq 0$ and $|\lambda| = \sum_{i=1}^d \lambda_i = 1$, and a permutation $\pi \in S_d$ on the $d$ letters $\{1, 2, \cdots, d\}$, we get a map $T = T_{(\lambda, \pi)} : [0, 1) \to [0, 1)$ exchanging the intervals $I_i = [\sum_{k=1}^{i-1}\lambda_k,\sum_{k=1}^i \lambda_k)$ ($i=1, 2, \cdots, d$) according to the permuation $\pi$. That is, if $x \in I_i$, then $$T_{(\lambda, \pi)}(x) = x - \sum_{k < i}\lambda_k + \sum_{\pi(k) < \pi(i)}\lambda_k.$$ We say that $T_{(\lambda, \pi)}$ is a *$d$-interval exchange transformation*, or *$d$-IET* for short, with *length data* $\lambda$ and *combinatorial data* $\pi$.

A permutation $\pi \in S_d$ is said to be *irreducible*, and denote that by $\pi \in S_d^o$, if $\pi(\{1, 2, \cdots, k\}) \neq \{1, 2, \cdots, k\}$ for every $k < d$.

The length data $\lambda$ can be parametrized by the unit simplex $\Delta_d =  \{(t_1, t_2, \cdots, t_d) \in \mathbb{R}^d \mid t_i \geq 0, \text{ and } \sum_{i=1}^d t_i = 1\}$. The unit simplex comes with the Lebesgue measure $\operatorname{Leb}_{\Delta_d}$, which makes it possible to talk about “almost all $d$-IETs”.

Denote the discontinuities of $T^{-1}$ by $\alpha_0 = 0, \alpha_1, \cdots, \alpha_d = 1$, and those of $T$ by $\beta_0 = 0, \beta_1, \cdots, \beta_d = 1$. Note that the subintervals $(\alpha_{i-1}, \alpha_i)$ are permuted by $T^{-1}$, and get sent to the subintervals $(\beta_{\pi^{-1}(i) - 1}, \beta_{\pi^{-1}(i)})$ for $i = 1, 2, \cdots, d$.

For more on IETs, the interested reader should check the excellent survery [@Yoccoz2007-zz].

### Gaps of IETs

Let $T = T_{(\pi, \lambda)} : [0, 1) \to [0, 1)$ be a $d$-interval exchange map with irreducible combinatorial data $\pi \in S_d^o$. For an integer $N \geq 1$, consider the orbit segment $\{T^k0 \mid 0 \leq n < N\}$, ordered on $[0, 1)$ as $$0 = T^{\sigma_{T, N}(0)}0 < T^{\sigma_{T, N}(1)}0 < \cdots < T^{\sigma_{T, N}(N-1)}0 < 1$$ with $\sigma_{T, N} : \{0, 1, \cdots, N-1\} \to \{0, 1, \cdots, N-1\}$ the permutation induced by the order the points arrange themselves on the interval. We denote for $i = 0, 1, \cdots, N-1$ the $i$th gap by $$\operatorname{gap}_{T, N}(i) =
\begin{cases}
T^{\sigma_{T, N}(i+1)}0 - T^{\sigma_{T, N}(i)}0, & i \neq N - 1 \\
1 - T^{\sigma_{T, N}(N-1)}0, & i = N - 1
\end{cases}.$$ We also denote the set of gap lengths by $$\operatorname{Gaps}_{T, N} := \{\operatorname{gap}_{T, N}(i) \mid 0 \leq i < N\},$$ and the multiset of gaps by $$\widetilde{\operatorname{Gaps}}_{\alpha, N} := \{\!\{\operatorname{gap}_{\alpha, N}(i) \mid 0 \leq i < N\}\!\}.$$ We interpret the elements of the multiset $\widetilde{\operatorname{Gaps}}_{T, N}$ as the actual gaps (i.e. the set of open intervals $\{(T^{\sigma_{T, N}(1)}, T^{\sigma_{T, N}(0)}), (T^{\sigma_{T, N}(2)}, T^{\sigma_{T, N}(1)}), \cdots, (T^{\sigma_{T, N}(N-1)}, 1)\}$ bounded by the orbit points $\{T^n0 \mid 0 \leq n < N-1\}$).

### Gap Theorems For IETs {#subsubsection: gap theorem for iets}

The first main result of this paper is the following.

\[theorem: d + 2 gap theorem\] Let $T$ be a minimal $d$-IET with combinatorial data $\pi$. For any integer $N\geq 1$,

-   if $\pi^{-1}(\pi(1) - 1) = d$, then $\# \operatorname{Gaps}_{T, N} \leq d+1$, and

-   if $\pi^{-1}(\pi(1) - 1) \neq d$, then $\# \operatorname{Gaps}_{T, N} \leq d+2$.

In [@Boshernitzan1985-fb], Boshernitzan proved a $3(d-1)$ Gap Theorem for IETS using graph theoretic methods which we present in \[subsection: Boshernitzan’s proof\] with a slight modification.

\[theorem: 3(d-1) gap theorem\] Let $T$ be a minimal $d$-IET. Then $\# \operatorname{Gaps}_{T, N} \leq 3(d-1)$.

When $d=2$, the $3(d-1)$ bound agrees with that of \[theorem: three gap theorem\]; namely, the Three Gap Theorem. (Refer to \[subsubsection: combinatorial structure\].)

Circle Rotation
---------------

For $\theta \in \mathbb{R}$, denote the circle rotation map $t \mapsto t + \theta \mod 1$ by $R_\theta$. The circle rotation is a $2$-IET with length data $\lambda = (1 - \theta, \theta)$ and combinatorial data $\pi = (1\ 2)$. Also, for $t \in \mathbb{R}$, let $\{t\} = t - \lfloor t \rfloor$ denote the fractional part of $t$. The orbit sequence $(R_\alpha^n 0)_{n=0}^\infty$ and the fractional parts sequence $(\{n\alpha\})_{n=0}^\infty$ agree.

For $T = R_\alpha$, the permutation $\sigma_{R_\alpha, N}$, the set of gaps $\operatorname{Gaps}_{R_\alpha, N}$, and the multiset $\widetilde{\operatorname{Gaps}}_{R_\alpha, N}$ are pretty much understood as can be seen in the next few sections.

### The Combinatorial Structure of the $\widetilde{\operatorname{Gaps}}_{R_\alpha, N}$ {#subsubsection: combinatorial structure}

It was observed by H. Steinhaus (1957) that there are at most three gap lengths in the above sequence. That is, $$\#\operatorname{Gaps}_{R_\alpha, N} \leq 3.$$

(0,0) circle (3);

node\[fill=blue\] at (0,3) node at (0, 3.5) [$\scriptscriptstyle R_\alpha^0(0)$]{}

node\[fill=blue\] at (-2.89171, -0.798766) node at (-3.37366, -0.931894) [$\scriptscriptstyle R_\alpha^1(0)$]{}

node\[fill=blue\] at (1.53987, -2.57465) node at (1.79651, -3.00376) [$\scriptscriptstyle R_\alpha^2(0)$]{}

node\[fill=blue\] at (2.07171, 2.16979) node at (2.417, 2.53143) [$\scriptscriptstyle R_\alpha^3(0)$]{}

node\[fill=blue\] at (-2.64307, 1.41921) node at (-3.08359, 1.65575) [$\scriptscriptstyle R_\alpha^4(0)$]{}

node\[fill=blue\] at (-0.664248, -2.92554) node at (-0.774955, -3.41313) [$\scriptscriptstyle R_\alpha^5(0)$]{}

node\[fill=blue\] at (2.99679, 0.13867) node at (3.49626, 0.161782) [$\scriptscriptstyle R_\alpha^6(0)$]{}

node\[fill=blue\] at (-0.931577, 2.8517) node at (-1.08684, 3.32698) [$\scriptscriptstyle R_\alpha^7(0)$]{}

node\[fill=blue\] at (-2.50072, -1.65723) node at (-2.91751, -1.93343) [$\scriptscriptstyle R_\alpha^8(0)$]{}

node at (0.393103, -2.4689) [A]{} node at (2.27511, 1.03627) [A]{} node at (-1.60463, 1.91708) [A]{} node at (-1.42063, -2.05713) [A]{} node at (-2.48445, 0.278445) [A]{} node at (0.929891, 2.32063) [A]{}

node at (-0.393045, 2.46891) [C]{} node at (-2.27514, -1.03622) [C]{}

node at (2.20253, -1.18274) [B]{};

The first proof of this observation, which is now known as the Three Gap Theorem, was given by V. Sós [@Sos1957-nu; @Sos1958-em]. The list of mathematicians who subsequently proved it includes S. Swierczkowski [@Swierczkowski1958-ji], Szüz, Erdös, Turan, Chung & Graham [@Chung1976-tu], among others. Recent work on the Three Gap Theorem and how it relates to the spaces of lattices has been done by Marklof & Strömbergsson in [@Marklof2016-tx], and by Haynes & Marklof in [@Haynes2017-xs]. A formal proof using the Coq proof assistant system has been published by Mayero [@Mayero2006-dy].

The different proofs usually come with a description of the gap (combinatorial) structure, giving the following theorem. (Check [@Polanco_undated-ts] for a proof.)

\[theorem: three gap theorem\] Consider $\alpha \in (0, 1)$, and $N \geq 1$ an integer. Let $\mathcal{F}(N) = \{0 \leq \frac{a}{q} \leq 1 \mid \gcd(a, q) = 1,\, q \leq N\}$ be the Farey fractions of order $N$.

-   If $\alpha = \frac{a}{q} \in \mathcal{F}(N)$, then there are $q$ gaps of equal length $\frac{1}{q}$.

-   Otherwise, there exists consecutive fractions $\frac{a_1}{q_1}$ and $\frac{a_2}{q_2}$ in $\mathcal{F}(N)$ such that $\frac{a_1}{q_1} < \alpha < \frac{a_2}{q_2}$. In that case, we get[^1]

      ---------------------- ----------- ----------------------------------------------
          $N - q_1$ gaps                    $A = q_1 \alpha - a_1 = \{q_1 \alpha\}$
       $q_1 + q_2 - N$ gaps   of length                   $B = A + C$
          $N - q_2$ gaps                  $C = a_2 - q_2 \alpha  = 1 - \{q_2 \alpha\}$
      ---------------------- ----------- ----------------------------------------------

In the second case, the permutation $\sigma = \sigma_{R_\alpha, N} : \{0, 1, \cdots, N-1\} \to \{0, 1, \cdots, N-1\}$ giving the ordering $$0 = \{\sigma_{R_\alpha, N}(0) \alpha\} < \{\sigma_{R_\alpha, N}(1) \alpha\} < \cdots < \{\sigma_{R_\alpha, N}(N-1)\alpha\} < 1$$ is recursively defined by $$\sigma(0) = 0,$$ and $$\sigma(i+1) - \sigma(i) =
\begin{cases}
q_1, & \text{if } \sigma(i) \in [0, N-q_1) \text{ ($A$ gap)}\\
q_1 - q_2, & \text{if } \sigma(i) \in [N-q_1, q_2) \text{ ($B$ gap)} \\
-q_2, & \text{if } \sigma(i) \in [q_2, N) \text{ ($C$ gap)}
\end{cases}
.$$

Note that in the second case, when $\alpha \not\in \mathcal{F}(N)$, the elements belonging to the same Farey arc $\left(\frac{a_i}{q_i}, \frac{a_{i+1}}{q_{i+1}}\right)$ in $\mathcal{F}(N)$ have the same gap structure. The gap lengths vary linearly between the two end points of the arc. Finally, the elements of $\mathcal{F}(N)$ give the *non-generic* gap structure, and are pretty much handled by modular arithmetic.

### Example: $\alpha = 1/\sqrt{2}$, $N = 9$

(0, 0) – (1, 0) – (1, [(1 + sqrt(5))/2]{}) – (0, [(1 + sqrt(5))/2]{}) – (0, 0); (0, [0 \* (1 + sqrt(5))/(2 \* 3)]{}) – (1, [0 \* (1 + sqrt(5))/(2 \* 7)]{}) – (1, [2 \* (1 + sqrt(5))/(2 \* 7)]{}) – (0, 0); (0, [0 \* (1 + sqrt(5))/(2 \* 3)]{}) – (1, [2 \* (1 + sqrt(5))/(2 \* 7)]{}) – (1, [3 \* (1 + sqrt(5))/(2 \* 7)]{}) – (0, [1 \* (1 + sqrt(5))/(2 \* 3)]{}) – (0, 0); (0, [1 \* (1 + sqrt(5))/(2 \* 3)]{}) – (1, [3 \* (1 + sqrt(5))/(2 \* 7)]{}) – (1, [5 \* (1 + sqrt(5))/(2 \* 7)]{}) – (0, [1 \* (1 + sqrt(5))/(2 \* 3)]{}); (0, [1 \* (1 + sqrt(5))/(2 \* 3)]{}) – (1, [5 \* (1 + sqrt(5))/(2 \* 7)]{}) – (0, [2 \* (1 + sqrt(5))/(2 \* 3)]{}) – (0, [1 \* (1 + sqrt(5))/(2 \* 3)]{}); (0, [2 \* (1 + sqrt(5))/(2 \* 3)]{}) – (1, [5 \* (1 + sqrt(5))/(2 \* 7)]{}) – (1, [7 \* (1 + sqrt(5))/(2 \* 7)]{}) – (0, [2 \* (1 + sqrt(5))/(2 \* 3)]{}); (0, [2 \* (1 + sqrt(5))/(2 \* 3)]{}) – (1, [7 \* (1 + sqrt(5))/(2 \* 7)]{}) – (0, [3 \* (1 + sqrt(5))/(2 \* 3)]{}) – (0, [2 \* (1 + sqrt(5))/(2 \* 3)]{}); (0, 0) – (1, [(1 + sqrt(5))/(2 \* 7)]{}); (0, 0) – (1, [2 \* (1 + sqrt(5))/(2 \* 7)]{}); (0, [1 \* (1 + sqrt(5))/(2 \* 3)]{}) – (1, [3 \* (1 + sqrt(5))/(2 \* 7)]{}); (0, [1 \* (1 + sqrt(5))/(2 \* 3)]{}) – (1, [4 \* (1 + sqrt(5))/(2 \* 7)]{}); (0, [1 \* (1 + sqrt(5))/(2 \* 3)]{}) – (1, [5 \* (1 + sqrt(5))/(2 \* 7)]{}); (0, [2 \* (1 + sqrt(5))/(2 \* 3)]{}) – (1, [5 \* (1 + sqrt(5))/(2 \* 7)]{}); (0, [2 \* (1 + sqrt(5))/(2 \* 3)]{}) – (1, [6 \* (1 + sqrt(5))/(2 \* 7)]{}); (0, [2 \* (1 + sqrt(5))/(2 \* 3)]{}) – (1, [7 \* (1 + sqrt(5))/(2 \* 7)]{}); ([21 \* (1/sqrt(2) - 2/3)]{}, 0) – ([21 \* (1/sqrt(2) - 2/3)]{}, [(1+sqrt(5))/2]{}); node at (0, -0.15) [$\scriptstyle \frac{2}{3}$]{} node at ([21 \* (1/sqrt(2) - 2/3)]{}, -0.15) [$\scriptstyle \frac{1}{\sqrt{2}}$]{} node at (1, -0.15) [$\scriptstyle \frac{5}{7}$]{};

The two fractions bounding $\alpha$ in $\mathcal{F}(9)$ are $\frac{a_1}{q_1} = \frac{2}{3}$, and $\frac{a_2}{q_2} = \frac{5}{7}$, and we have

         \# gaps         type                     length
  --------------------- ------ ---------------------------------------------
      $N - q_1 = 6$      $A$    $q_1 \alpha - a_1 = \frac{3}{\sqrt{2}} - 2$
   $q_1 + q_2 - N = 1$   $B$          $A+C = 3 - \frac{4}{\sqrt{2}}$
      $N - q_2 = 2$      $C$    $a_2 - q_2 \alpha = 5 - \frac{7}{\sqrt{2}}$

### The Statistics of the $\widetilde{\operatorname{Gaps}}_{R_\alpha, N}$

Fix $\alpha \in (0,1)$, and $N \geq 1$ an integer. The expected value of the gap lengths is $$\frac{1}{N} \sum_{i=0}^{N-1} \operatorname{gap}_{R_\alpha, N}(i) = \frac{1}{N}.$$ Let $$\begin{aligned}
\mathcal{G}_{R_\alpha, N}(z) &:=& \# \{\ell \in \widetilde{\operatorname{Gaps}}_{R_\alpha, N} \mid \ell \geq \frac{z}{N}\} \\
&=& \#\{L \in N \cdot \widetilde{\operatorname{Gaps}}_{R_\alpha, N} \mid L \geq z\}\end{aligned}$$ denote the number of *normalized gap lengths* greater than or equal to $z$.

Now, for $0 < a < b < 1$, consider the *average gap distribution* $$g_{R_\cdot}^{[a, b]}(z; N) ;= \frac{1}{b-a} \int_a^b \frac{\mathcal{G}_{R_\alpha, N}(z)}{N}\, d\alpha.$$ It was proved in [@Polanco_undated-ts] that $g_{R_\cdot}^{[a, b]}(z; N)$ has a limit.

As $N \to \infty$, the limit $\lim_{N \to \infty} g_{R_\cdot}^{[a, b]}(z; N)$ exists, is independent of $[a, b]$, and is equal to $g(z)=$ $$= \frac{6}{\pi^2} \scriptsize
        \begin{cases}
        \frac{\pi^2}{6} - z & 0 < z < 1 \\
        \begin{aligned}
        \log^2(2) - \frac{2\pi^2}{3} - 1 + \left(\frac{z}{2} - \frac{2}{z}\right)\log\left(\frac{2-z}{z - 1}\right) + \frac{3z}{2}\log\left(\frac{z}{z - 1}\right) \\
        -\log\left(\frac{4}{z}\right)\log(z) + 4{\operatorname{Li}}_2(\frac{1}{z}) + 2{\operatorname{Li}}_2(\frac{z}{2})
        \end{aligned} & 1 < z < 2 \\
        -1 + \left(\frac{z}{2} - \frac{2}{z}\right) \log \left(\frac{z - 2}{z - 1}\right) + \frac{3}{2} z \log \left(\frac{z}{z - 1}\right) + 4 {\operatorname{Li}}_2\left(\frac{1}{z}\right) - 2 {\operatorname{Li}}_2\left(\frac{2}{z}\right) & 2 < z
        \end{cases}$$ where the Dilogarithm is defined for $|z| \leq 1$ by $${\operatorname{Li}}_2(z) := \sum_{n=1}^\infty \frac{z^n}{n^2}.$$

In \[subsection: gap dist. for three gap theorem\], we interpret the average gap distribution $g_{R_\cdot}^{[a, b]}(z; N)$ in terms of zippered rectangle decompositions, and prove the existence of the limit as $N \to \infty$ using the equidistribution of large horocycles. This proves the following theorem. (Refer to \[subsection: notation\], and \[subsection: gap dist. for three gap theorem\] for the definitions of $f_z$ and $\mathfrak{Z}$.)

\[theorem: gap distribution for circle rotation\] The average gap distribution $g_{R_\cdot}^{[a, b]}(z; N)$ has a limiting distribution $$\lim_{N \to \infty} g^{[a, b]}(z; N) = \int_{X_2} f_z(\mathfrak{Z}(\Lambda))\, d\mu_2(\Lambda).$$ That is, in the limit, $g^{[a, b]}(z; N)$ is equal to the distribution of heights of the zippered rectangle decomposition of unimodular tori.

In fact, the same approach provides \[subsection: gap distribution for iets\], we prove the following axiomatic theorem generalizing \[theorem: gap distribution for circle rotation\] to compositions of IETs and circle rotations. (Refer to \[subsection: the surface $S_T$\] for the definition of $S_T$, and to \[subsection: notation\], \[subsection: gap dist. for three gap theorem\], and \[subsection: gap distribution for iets\] for the definitions of $f_z$ and $\mathfrak{Z}_\text{canon}$.)

\[theorem: gap distribution for iets\] Let $T$ be an IET, with $S_T \in \mathcal{H}$. If an equidistribution of large horocycles result implying $(g_t)_\ast (\pi_{S_T})_\ast (h_\cdot)_\ast \operatorname{Leb}_{[a, b]} \rightharpoonup \mu$, with $\mu$ a measure on $\mathcal{H}$, holds true, then the average gap distribution $g_{T \circ R_\cdot}^{[a, b]}(z; N)$ has a limiting distribution $$\lim_{N \to \infty} g_{T \circ R_\cdot}^{[a, b]}(z; N) = \int_\mathcal{H} f_z\left(\mathfrak{Z}_\text{canon}(S)\right)\, d\mu(S).$$

Organization
------------

In \[section:background\] we present the background needed to understand the rest of the paper. In \[section: circle rotation\] we relate gaps for circle rotations to zippered rectangle decompositions of tori, providing a proof for the Three Gap Theorem. In \[section: iets\] we show that the same procedure used in \[section: circle rotation\] to prove the Three Gap Theorem can be used to prove a $d+2$ Gap Theorem for general IETS. In \[appendix: kloosterman sums\] we mention a proof for the equidistribution of large horocycles using Kloosterman sums. In \[appendix: combinatorial proof of the gap theorem\], we present a second proof for the $d+2$ Gap Theorem using a purely combinatorial argument.

Background {#section:background}
==========

Linear Flow on Translation Surfaces {#subsection: linear flow on translation surfaces}
-----------------------------------

The relationship between the linear flow on the torus (and translation surfaces in general) and interval exchange transformations is widely known. The folklore result here is the following.

Let $S$ be an open bounded geodesic segment in a translation surface. The first return map of a linear flow on the translation surface to $S$ is an interval exchange map.

In particular, the following proposition is true. (The author has not been able to find an appearance of this in the literature preceeding [@Arnold2007-kz]).

The first return map defined by a minimal linear flow on a torus to a transversal to the flow gives an interval exchange map with $2$ or $3$ intervals.

As we will see in a bit, the above proposition is equivalent to the Three Gap Theorem, and thus provides a geometric proof of the aforementioned result.

The same phenomenon is true for general translation surfaces. (Check [@Yoccoz2007-zz] or [@Zorich2006-of].)

\[proposition: d interval theorem\] Let $S$ be a translation surface, and denote its genus and number of singularities by $g$ and $s$ respectively. Write $d_S = 2g + s - 1$. Then the first return map of a minimal linear flow on $S$ to a transversal $X$ is an interval exchange interval $T$ on

-   $d_T = d_S$ intervals if the forward or backward trajectories of both end points of $X$ under the flow hit singularities,

-   $d_T = d_S + 1$ intervals if the forward or backward trajectories of exactly one of the end points of $X$ under the flow hit a singularity

-   $d_T = d_S + 2$ intervals if the forward or backward trajectories of neither end point of $X$ under the flow hits a singularity

This proposition will similarly be used to prove a gaps theorem for general IETs.

Zippered Rectangles Decomposition {#subsection: zippered rectangles decomposition}
---------------------------------

Consider a translation surface $S$, a minimal linear flow $\phi$ on that surface, and a transversal $X$ to that flow. The first return map of the flow to the transveral is an interval exchange map $T$ on $d_T$ subintervals of $X$. It can be shown that the return time of $\phi$ is constant on each of the $d_T$ subintervals of $X$. (Check [@Yoccoz2007-zz].) This decomposes the surface $S$ into $d_T$ rectangles, whose widths are the lengths $\lambda = (\lambda_1, \lambda_2, \cdots, \lambda_{d_T})$ associated with $T$, and whose heights $h = (h_1, h_2, \cdots, h_{d_T})$ are the return times of $\phi$ to $X$ on each of the $d_T$ subintervals of $X$. The vector $(h, \lambda)$ is the *height-width parameters* of the *zippered rectangle decomposition* of $S$ with respect to the suspension of $\phi$ over $X$.

The Space of Unimodular Lattices
--------------------------------

Let $X_2 = \operatorname{SL}_2 \mathbb{R} / \operatorname{SL}_2 \mathbb{Z}$ be the modular surface. The points of $X_2$, which are cosets of $\operatorname{SL}_2 \mathbb{Z}$, can be identified with unimodular lattices and unit area tori $$A \cdot \operatorname{SL}_2 \mathbb{Z} \leftrightarrow A \cdot \mathbb{Z}^2 \leftrightarrow \mathbb{R}^2 / A \cdot \mathbb{Z}^2$$ for every $A \in \operatorname{SL}_2 \mathbb{R}$.

The space $X_2$ inherits an $\operatorname{SL}_2 \mathbb{R}$ action given by left translation: for any $B \in \operatorname{SL}_2 \mathbb{R}$ we have $$B(A \cdot \operatorname{SL}_2\mathbb{Z}) = (BA) \cdot \operatorname{SL}_2\mathbb{Z} \leftrightarrow B(A \cdot \mathbb{Z}^2) = (BA)\cdot \mathbb{Z}^2 \leftrightarrow B(\mathbb{R}^2 / A \cdot \mathbb{Z}^2) = \mathbb{R}^2 / (BA)\cdot \mathbb{Z}^2.$$ This gives rise to two important flows on $X_2$:

-   the *horocycle flow* given by the matrices $h_s = \begin{pmatrix} 1 & 0 \\ -s & 1\end{pmatrix}$, for $s \in \mathbb{R}$

-   the *geodesic flow* given by the matrices $g_t := \begin{pmatrix} e^{-t} & 0 \\ 0 & e^t \end{pmatrix}$, for $t \in \mathbb{R}$

The space $X_2$ also comes with an $\operatorname{SL}_2 \mathbb{R}$-invariant Haar probability measure which is usually denoted by $\mu_2$.

The following is true about the convergence of measures on horocycles under translation by the geoedisic flow.

Let $\nu$ be a Borel measure on $\mathbb{R}$, absolutely continuous with respect to to the Lebesgue measure. Then for any bounded continuous function $f : X_2 \to \mathbb{R}$, then we have for any $\Lambda_0 \in X_2$ that $$\lim_{t \to \infty} \int_{\mathbb{R}} f(g_t h_{s} \cdot \Lambda_0)\, d\nu(s) = \int_{X_2} f(\Lambda)\, d\mu_2(\Lambda).$$

To see how this is a statement about measures, consider the projection $\pi_{\Lambda_0} : \operatorname{SL}_2\mathbb{R} \to X_2$ defined by $A \mapsto A \cdot \Lambda_0$. Then the conclusion of the above theorem is literally $$\lim_{t \to \infty} (g_t)_\ast (\pi_{\Lambda_0})_\ast (h_\cdot)_\ast\nu(f) = \mu_2(f).$$ That is, $(g_t)_\ast(\pi_{\Lambda_0})_\ast(h_\cdot)_\ast \nu \rightharpoonup \mu_2$ in the weak-$\ast$ topology of measures on $X_2$.

The Three Gap Theorem and Zippered Rectangles {#section: circle rotation}
=============================================

The circle rotation $R_\alpha$ can be identified with the return map of the linear flow $\phi_\alpha^t(x, y) = (x+t, y+\alpha t) \mod 1$ on the torus $\mathbb{T}^2 = \mathbb{R}^2 / \mathbb{Z}^2$ to the vertical segment $V_{\mathbb{T}^2} = \{0\} \times [0, 1] \subset \mathbb{T}^2$. The shear matrix $h_\alpha = \begin{pmatrix}1 & 0 \\ -\alpha & 1\end{pmatrix}$ “fixes” the vertical $V_{\mathbb{T}^2}$ pointwise ($h_\alpha \cdot V_{\mathbb{T}^2} \leftrightarrow V_{h_\alpha \cdot \mathbb{T}^2}$), maps the linear flow $\phi_\alpha^t \curvearrowright \mathbb{T}^2$ to the horizontal flow $\phi_0^t \curvearrowright h_\alpha \cdot \mathbb{T}^2$ ($h_\alpha \circ \phi_\alpha^t = \phi_0^t \circ h_\alpha$). As such, the circle rotation is also the return map of the horizontal flow on $h_\alpha \cdot \mathbb{T}^2$ to the vertical $V_{h_\alpha \cdot}$. Moreover, $\phi_\alpha^{[0, N]} \cap V_{\mathbb{T}^2} = \{(0, R_\alpha(0)^k)\}_{k=0}^{N} \subset \mathbb{T}^2$ and $\phi_0^{[0,N]} \cap V_{h_\alpha \cdot \mathbb{T}^2} = \{(0, R_\alpha^k(0))\}_{k=0}^N \subset h_\alpha \cdot \mathbb{T}^2$. The points $\{(0, R_\alpha^k(0))\}_{k=0}^N$ order themselves around the closed vertical segment $V_{\mathbb{T}^2}$ the same way the points $\{R_\alpha^k(0)\}_{k=0}^N$ order themselves on the interval $[0, 1) \leftrightarrow \mathbb{S}^2$. This gives the following result.

\[theorem: three height theorem\] For a fixed $\alpha$ and $N$, the pairs $$(\text{gap length}, \text{number of gaps of that length})$$ describing the multiset $\widetilde{\operatorname{Gaps}}_{\alpha, N}$ correspond to the height-width parameters $(h, \lambda)$ of the zippered rectangle decomposition of the torus $h_\alpha \cdot \mathbb{T}^2$ over any horizontal segment of length $N$.

In light of the above theorem, we get the following equivalence.

The Three Gap Theorem and the Three Intervals Theorems are equivalent.

This proves \[theorem: three gap theorem\].

(0, 0) – (1.3, 0); (1.3, 0) – (2.5, 0); (2.5, 0) – (3.5, 0); (3.5, 0) – (3.5, 2); (3.5, 2) – (2.2, 2); (2.2, 0) – (2.2, 2); (2.2, 3) – (1, 3); (1, 3) – (1, 1); (1, 1) – (0, 1); (1, 0) – (1, 1); (0, 0) – (0, 1); (2.2, 2) – (2.2, 3);

node\[fill, circle, scale=0.35\] at (0,0) ;

node at (0.5, 0.5) [$R_1$]{} node at (1.6, 0.5) [$R_2$]{} node at (2.85, 0.5) [$R_3$]{}; node at (1.9, 2.5) node at (3.2, 1.5) ;

The Three Gap Theorem as a Theorem on Zippered Rectangles
---------------------------------------------------------

The Three Gap Theorem (\[theorem: three gap theorem\]) gives the zippered rectangle decomposition of tori corresponding to the lattices $\Lambda_{\alpha, N} = g_{\log N} h_\alpha \cdot \mathbb{Z}^2$ with basis $$[B_{\alpha, N}] = \begin{pmatrix} 1/N & 0 \\ 0 & N\end{pmatrix}
\begin{pmatrix} 1 & 0 \\ -\alpha & 1 \end{pmatrix} = \begin{pmatrix} 1/N & 0 \\ -\alpha N & N \end{pmatrix}$$ over horizontal marked segments of unit length.

If $\mathcal{F}(N)$ are the Farey sequence at level $N$, we get one of two cases:

-   That $\alpha = \frac{a}{q} \in \mathcal{F}(N)$, with $\gcd(1, q) = 1$ and $q \leq N$: The horizontal segment of length $1$ closes at stage $N = q$, and starts wrapping around itself for $N > q$. In both cases, we get a zippered rectangle with combinatorial data $\pi = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}$, length data $$\begin{aligned}
    \lambda_1 &=& \frac{q - n_1}{N}, \\
    \lambda_2 &=& \frac{n_1}{N},\end{aligned}$$ where $n_1$ is the unique $n \in \{1, 2, \cdots, q-1\}$ such that $n a = 1 \mod q$, and height data $$h_1 = h_2 = \frac{N}{q}.$$

-   That there exists two successive elements $\frac{a_1}{q_1}, \frac{a_2}{q_2}$ of $\mathcal{F}(N)$ such that $\alpha \in \left(\frac{a_1}{q_1}, \frac{a_2}{q_2}\right)$: In that case, we get a zippered rectangle with combinatorial data $\pi = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1\end{pmatrix}$, length data $$\begin{aligned}
    \lambda_1 &=& 1 -\frac{q_1}{N}, \\
    \lambda_2 &=& \frac{q_1 + q_2}{N} - 1, \\
    \lambda_3 &=& 1 - \frac{q_2}{N},\end{aligned}$$ and height data $$\begin{aligned}
    h_1 &=& N \{q_1 \alpha\} = N(q_1 \alpha - a_1), \\
    h_2 &=& h_1 + h_2, \\
    h_3 &=& N(1 - \{q_2 \alpha\}) = N(a_2 - q_2 \alpha)\end{aligned}$$ Note that they satisfy the following two relationships: $|\lambda| = \lambda_1 + \lambda_2 + \lambda_3 = 1$, and $\lambda \cdot h = \lambda_1 h_1 + \lambda_2 h_2 + \lambda_3 h_3 = 1$. The values $(\lambda_1, \lambda_2, \lambda_3, h_1, h_2, h_3)$ are linear on each interval $\left(\frac{a_1}{q_1}, \frac{a_2}{q_2}\right)$.

Notation {#subsection: notation}
--------

To wrap everything up, we define the operator $\mathfrak{Z}$ that takes a unimodular torus $T \in X_2$, and returns the length-height vector $(\lambda, h) \in \mathbb{R}^4 \sqcup \mathbb{R}^6$ of its zippered rectangle decomposition over a horizontal line segment of unit length. For a fixed $N > 0$ we have $$\frak{Z}(\mathbb{R}^2 / g_{\log N} h_{\alpha} \mathbb{Z}^2) =
\begin{cases}
(\frac{q-n_1}{N}, \frac{n_1}{N}, \frac{N}{q}, \frac{N}{q}), & \alpha = \frac{a}{q} \in \mathcal{F}(N) \\
(1 - \frac{q_1}{N}, \frac{q_1}{N} + \frac{q_2}{N} - 1, 1 - \frac{q_1}{N}, N(q_1 \alpha - a_1), N((q_1 - q_2)\alpha - (a_1 - a_2)), N(a_2 - q_2 \alpha)), & \alpha \in \left(\frac{a_1}{q_1}, \frac{a_2}{q_2}\right)
\end{cases}
.$$

It will be convenient in the second case to write $\alpha = \frac{a_1}{q_1} + \frac{t}{q_1 q_2}$, with $t \in (0,1)$. In that case, $\frak{Z}(\mathbb{R}^2/g_{\log N} h_\alpha \cdot\mathbb{Z}^2)$ is equal to $$(1 - \frac{q_1}{N}, \frac{q_1}{N} + \frac{q_2}{N} - 1, 1 - \frac{q_1}{N}, \frac{N}{q_2} t, (\frac{N}{q_2} - \frac{N}{q_1})t + \frac{N}{q_1}, \frac{N}{q_1}(1 - t)).$$

Gap Distribution {#subsection: gap dist. for three gap theorem}
----------------

At this stage, we have everything we need to present our second main result: \[gap distribution for circle rotation\]. Namely, relating the average gap distribution $$g^{[a, b]}(z; N) := \frac{1}{b-a} \int_a^b \frac{\mathcal{G}_{\alpha, N}(z)}{N}\, d\alpha$$ to the zippered rectangles decomposition of tori. We achieve this through expressing the integrand in terms of a cut-off function on the vector $(\lambda, h)$.

Recall the definition of the *Iverson bracket*: for a predicate $P$, the iversion bracket $[P]$ is given by $$[P] :=
\begin{cases}
1, & \text{ if $P$ is true} \\
0, & \text{ if $P$ is false}
\end{cases}.$$ For $z \geq 0$, we define the cut-off function $d_z : \mathbb{R}^2 \to \mathbb{R}$ by $$d_z(x, y) = x [y \geq z],$$ and define the aggregate cut-off function $f_z : \mathbb{R}^6 \to \mathbb{R}$ with $$f_z(\lambda_1, \lambda_2, \lambda_3, h_1, h_2, h_3) = d_z(\lambda_1, h_1) + d_z(\lambda_2, h_2) + d_z(\lambda_3, h_3).$$

By \[theorem: three height theorem\], the integrand in question evaluates to $$\frac{\mathcal{G}_{\alpha, N}(z)}{N} =
\begin{cases}
\frac{q[1/q \geq z]}{N}, & \alpha = \frac{a}{q} \in \mathcal{F}(N) \\
f_z(\frak{Z}(g_{\log N} h_\alpha \cdot \mathbb{Z}^2))\, d\alpha, & \text{ otherwise}
\end{cases}.$$

Integrating we get $$g^{[a, b]}(z; N) = \frac{1}{b-a} \int_a^b \frac{\mathcal{G}_{\alpha, N}(z)}{N}\, d\alpha = \frac{1}{b-a} \int_a^b f_z(\frak{Z}(g_{\log N} h_\alpha \cdot \mathbb{Z}^2))\, d\alpha.$$

The uniform probability measure $\nu(\cdot) = \frac{1}{b-a} \int_a^b \cdot\, d\alpha$ is obviously absolutely continuous with respect to the Lebesgue measure on $\mathbb{R}$. A compactness argument, and the equidistribution of large horocycles theorem proves \[theorem: gap distribution for circle rotation\]

Gap Theorem for $d$-IETS {#section: iets}
========================

In this section, we demonstrate that the technique we used in \[section: circle rotation\] to prove \[theorem: three gap theorem\] can be used to prove a generalization of the theorem for general intervals exchange maps. We introduce an elegant construction from [@Athreya2012-yw] and then proceed to our proof.

The surfaces $S_T$ defined by IET $T$ {#subsection: the surface $S_T$}
-------------------------------------

Construct the surface $S_T$ as follows: Take the square $[0, 1] \times [0, 1]$, identify the horizontal sides by translation, and the vertical sides by $T$. Concretely, for each $i$, mark the points $(0, \alpha_i)$ on the left vertical, the points $(1, \beta_i)$ on the right vertical, and glue the vertical segments $[(0, \alpha_{i-1}), (0, \alpha_i)]$ and $[(1, \beta_{\pi(i)-1}), (1, \beta_{\pi(i)})]$ together.

(0, 0) – (5, 0) – (5, 5) – (0, 5) – (0, 0); node at (0, 0) [$\circ$]{} node at (0, 1) [$\star$]{} node at (0, 2) [$\circ$]{} node at (0, 3) [$\times$]{} node at (0, 4) [$\circ$]{} node at (0, 5) [$\circ$]{}

node at (5, 0) [$\circ$]{} node at (5, 1) [$\circ$]{} node at (5, 2) [$\times$]{} node at (5, 3) [$\circ$]{} node at (5, 4) [$\star$]{} node at (5, 5) [$\circ$]{};

node at (-1, 0.5) [$\scriptstyle I_4 = I_{\pi^{-1}(1)} $]{} node at (-1, 1.5) [$\scriptstyle I_5 = I_{\pi^{-1}(2)}$]{} node at (-1, 2.5) [$\scriptstyle I_2 = I_{\pi^{-1}(3)}$]{} node at (-1, 3.5) [$\scriptstyle I_3 = I_{\pi^{-1}(4)}$]{} node at (-1, 4.5) [$\scriptstyle I_1 = I_{\pi^{-1}(5)}$]{} node at (5.5, 0.5) [$\scriptstyle I_1$]{} node at (5.5, 1.5) [$\scriptstyle I_2$]{} node at (5.5, 2.5) [$\scriptstyle I_3$]{} node at (5.5, 3.5) [$\scriptstyle I_4$]{} node at (5.5, 4.5) [$\scriptstyle I_5$]{}; node at (2.5, -0.5) [$J_0$]{}; node at (2.5, 5.5) [$J_0$]{};

After gluing, we mark the point on $S_T$ corresponding to $(0, 0)$ and call it a *marked origin*. As such, $S_T$ is a Riemann surface with a marked point. We intend to follow the same strategy used to prove the Three Gap Theorem: We start at the vertex $(0, 0)$, and flow horizontally along the for time $t = N$. A small subtlety arises here: For a general IET $T$, the horizontal trajectory in question can hit singularities in its path, and there will be a finite choice to make when it comes to flowing *out* of each singularity. We choose the trajectory that gives the “correct” returns to the vertical through $(0, 0)$ (i.e. that intersects the vertical at the points corresponding to the orbit $\{T^n0\}_{n=0}^\infty$). We call this the *canonical horizontal trajectory of length $N$ coming out of the origin*.

The following lemma characterizes the property of marked origins being singularities.

Let $T$ and $S_T$ be as above. The marked origin is a singularity if and only if $\pi^{-1}(1) - \pi^{-1}(d) \neq 1$.

Since the permutation $\pi$ is irreducible, it is easy to see that $(0,0)$ is not a singularity if and only if the first and last segment $I_{\pi^{-1}(1)}$ and $I_{\pi^{-1}(d)}$ on the left side correspond to segments on the right side that are *back to back*, that is, $\pi^{-1}(1) = \pi^{-1}(d) + 1$.

We call IETs with $\pi^{-1}(1) - \pi^{-1}(d) = 1$ *arc exchange maps*.

The IET $T$ is said to satisfy the *infinite distinct orbit condition* (i.d.o.c for short) or *Keane’s condition* if the orbits $\{(T^{-1})^n\alpha_1\}_{n=1}, \{(T^{-1})^n\alpha_2\}_{n=1}, \cdots, \{(T^{-1})^n\alpha_{d-1}\}_{n=1}$ of the discontinuities $\alpha_1, \alpha_2, \cdots, \alpha_{d-1}$ of $T^{-1}$ are both infinite and pairwise distinct.

Let $T$ and $S_T$ be as above.

1.  The first return map of the horizontal flow to any closed vertical segment is given by the map $T$.

2.  The IET $T$ fails to satisfy the i.d.o.c condition if and only if there are a horizontal saddle connection that is not the horizontal unit length closed line segment $[(0, \alpha_0), (1, \beta_0)] \sim [(0, \alpha_d), (1, \beta_d)]$.

Let $T$ and $S_T$ be as above. For any $\alpha \in \mathbb{R}$:

1.  The construction $S_\cdot$ is compatible with shearing by $h_\alpha$. That is, $h_\alpha \cdot S_T = S_{T \circ R_\alpha}$.

2.  Shearing by $h_\alpha$ takes any line segment $X \subset S_T$ of slope $\alpha$ to a horizontal line segment $h_\alpha \cdot X \subset S_{T \circ R_\alpha}$. Moreover, the return time of any $x \in X$ to $X$ by the vertical flow on $S_T$ is the same as that of $h_\alpha \cdot x \in h_\alpha \cdot X$ to $h_\alpha \cdot X$ by the vertical flow on $S_{T \circ R_\alpha}$.

This proves the following property of the compositions of IETs and circle rotations.

For any IET $T$, there are at most countably many $\alpha \in \mathbb{R}$ for which $T \circ R_\alpha$ does not satisfy the i.d.o.c condition.

The failure of $T \circ R_\alpha$ to satisfy the i.d.o.c is equivalent to the existence of non-horizontal saddle connections in $S_{T \circ R_\alpha}$ that are not $[(0, \alpha_0), (1, \beta_0)] \sim [(0, \alpha_d), (1, \beta_d)]$. Any horizontal saddle connection in $S_{T \circ R_\alpha} = h_\alpha \cdot S_T$ corresponds to a saddle connection in $S_T$ with slope $\alpha$. The result follows from the fact that there are countably many saddle connections on any translation surface.

Gap Theorem for Interval Exchange Transformations
-------------------------------------------------

The argument used in \[section: circle rotation\] can be adapted to prove the following.

For a fixed minimal IET $T$ and integer $N \geq 1$, the pairs $$(\text{gap length}, \text{number of gaps of that length})$$ describing the multiset $\widetilde{\operatorname{Gaps}}_{T, N}$ correspond to the height-width parameters $(h, \lambda)$ of the zippered rectangle decomposition of the surface $S_T$ over the canonical horizontal trajectory of length $N$ coming out of the marked origin.

The above theorem, along with \[proposition: d interval theorem\] and the characterization of the marked origin being a singularity, proves \[theorem: d + 2 gap theorem\].

Gap Distribution {#subsection: gap distribution for iets}
----------------

For a general IET $T$, we denote the number of *normalized gap lengths* greater than or equal to $z$ by $$\begin{aligned}
\mathcal{G}_{T, N}(z) &:=& \# \{\ell \in \widetilde{\operatorname{Gaps}}_{T, N} \mid \ell \geq \frac{z}{N}\} \\
&=& \#\{L \in N \cdot \widetilde{\operatorname{Gaps}}_{T, N} \mid L \geq z\}\end{aligned}$$

For compositions of $T$ and circle rotations, we can consider the *average gap distribution* $$g_{T \circ R_\cdot}^{[a, b]}(z; N) ;= \frac{1}{b-a} \int_a^b \frac{\mathcal{G}_{T \circ R_\alpha, N}(z)}{N}\, d\alpha.$$

Copying \[subsection: notation\], we define an operator $\mathfrak{Z}_\text{canon}$ as follows: for any translation surface $S$ with a marked point and a canonical choice of horizontal unit length trajectory coming out of the marked point, $\mathfrak{Z}_\text{canon}(S)$ is the vector of length-height data of the zippered rectangle decomposition of $S$ over the aforementioned horizontal.

Also, an aggregate cut-off function $f_z$ can appropriately be defined as was done in \[subsection: gap dist. for three gap theorem\]. Moreover, the idea of the argument used to prove \[theorem: gap distribution for circle rotation\] can be used here to relate the average gap distribution for compositions of a fixed IET $T$ and circle rotations to the distribution of zippered rectangle decomposition heights $$g_{T \circ R_\cdot}^{[a, b]}(z; N) = \frac{1}{b-a} \int_a^b \frac{\mathcal{G}_{T \circ R_\alpha, N}(z)}{N}\, d\alpha = \frac{1}{b-a} \int_a^b f_z(\frak{Z}_\text{canon}(g_{\log N} h_\alpha \cdot S_T))\, d\alpha.$$ This proves the axiomatic \[theorem: gap distribution for iets\].

Acknowledgement
===============

I would like to show my gratitude to my adviser Jayadev S. Athreya for introducing me to this problem, and offering me his time, advice, guidance, and assistance during the writing of this paper. I would also like to acknowledge all the excellent mathematicians I had the privilege to talk to during the Thematic Month on Dynamical Systems in CIRM (Marseille, Luminy), where my understanding of this problem crystallized. I especially would like to thank Jayadev Athreya and Pascal Hubert for facilitating my visit to CIRM, and sharing their insights with me.

Equidistribution of Large Horocycle via Kloosterman Sums {#appendix: kloosterman sums}
========================================================

We would like to point out a very interesting, and curious observation concerning the derivation of the gap distribution in [@Polanco_undated-ts]. The derivation takes places by applying the lemma (lemma 8, [@Boca2001-he])below to the three gap thereom. It should be noticed that this is, in essence, an equidistribution of large horocycles theorem using zippered rectangles. We cite the lemma used in the original proof, and distill the equidistribution result as a theorem.

**Notation:** Denote $$\sum_\Omega f := \sum_{\substack{(\frac{q_1}{N}, \frac{q_2}{N}) \in \Omega \\ a \leq \frac{q_1}{N} < \frac{q_2}{N} \leq b}}f\left(\frac{q_1}{N}, \frac{q_2}{N}\right).$$

If $\Omega \subseteq [0, 1] \times [0, 1]$ is a convex subregion with rectifiable boundary, and $f$ is a $C^1$ functino on $\Omega$, then $$\left|\frac{1}{b-a} \sum_\Omega f\left(\frac{q_1}{N}, \frac{q_2}{N}\right) - \frac{6}{\pi^2} \iint_\Omega f(x, y)\, dxdy\right|$$ $$\ll_\epsilon \frac{1}{b-a} \left(\left(\left\|\frac{\partial f}{\partial x}\right\|_\infty +\left\|\frac{\partial f}{\partial y}\right\|_\infty\right) \frac{\operatorname{area}(\Omega)\log N}{N} + \|f\|_\infty \frac{(1 + \operatorname{length}(\partial\Omega))\log N}{N} + \frac{m_f \|f\|_\infty}{N^{1/2 - \epsilon}}\right),$$ where $m_f$ is an upper bound for the number of intervals on monotonicity of each of the maps $y \mapsto f(x, y)$.

Let $f : \mathbb{R}^6 \to \mathbb{R}$ be a function such that $$F(x, y) = \frac{1}{xy} \int_0^1 f_z(1-x, x + y - 1, 1 - y, \frac{t}{y}, (\frac{1}{y} - \frac{1}{x})t + \frac{1}{x}, \frac{1-t}{x})dt$$ is defined and $C^1$ on a convex subregion $\Omega \subseteq [0, 1] \times [0, 1]$, and $0$ elsewhere. Then for any subinterval $[a, b] \subseteq [0, 1]$ we have $$\lim_{t \to \infty} \frac{1}{b-a}\int_a^b f(\frak{Z}(\mathbb{R}^2 / g_t h_\alpha \cdot \mathbb{Z}^2))\, d\alpha = \frac{6}{\pi^2} \iint_\Omega F(x, y)\, dxdy.$$

The proof is very simple. It is a direct computation where we use the change of variables $\alpha = \frac{a_i}{q_i} + \frac{t}{q_iq_{i+1}}$ on each Farey arc, and apply the above lemma on the convergence of Kloosterman sums. In particular, we have

$\frac{1}{b-a} \int_a^b f(\frak{Z}(\mathbb{R}^2 / g_{-\log N} h_{-\alpha} \mathbb{Z}^2))\, d\alpha$ $$\begin{aligned}
&=& \frac{1}{b - a}\sum_{a \leq \frac{a_i}{q_i} < \frac{a_{i+1}}{q_{i+1}} \leq b} \int_{a_i / q_i}^{a_{i+1}/q_{i+1}} f(\frak{Z}(\mathbb{R}^2 / g_{-\log N} h_{-\alpha} \mathbb{Z}^2))\, d\alpha + o(N)\\
&=& \frac{1}{b-a} \sum_{a \leq \frac{a_i}{q_i} < \frac{a_{i+1}}{q_{i+1}} \leq b} \int_{a_i/q_i}^{a_{i+1}/q_{i+1}} f(\text{expression for $\frak{Z}$})\, d\alpha + o(N)\\
&=& \frac{1}{b-a} \sum_{a \leq \frac{a_i}{q_i} < \frac{a_{i+1}}{q_{i+1}} \leq b} \int_0^1 f(1 - \frac{q_i}{N}, \frac{q_i}{N} + \frac{q_{i+1}}{N} - 1, 1 - \frac{q_i}{N}, \frac{N}{q_{i+1}} t, (\frac{N}{q_{i+1}} - \frac{N}{q_i})t + \frac{N}{q_i}, \frac{N}{q_i}(1 - t)) \frac{dt}{q_i q_{i+1}} + o(N)\\
&=& \frac{1}{b-a} \sum_{a \leq \frac{a_i}{q_i} < \frac{a_{i+1}}{q_{i+1}} \leq b} F(\frac{q_i}{N}, \frac{q_{i+1}}{N}) \frac{1}{N^2} +o(N) \\
&\to& \frac{6}{\pi^2} \int_\Omega F(x, y)\, dxdy\end{aligned}$$

Combinatorial Proof of the Gap Theorem {#appendix: combinatorial proof of the gap theorem}
======================================

In this appendix, we present Boshernitzan’s proof for \[theorem: 3(d-1) gap theorem\], and give another proof \[theorem: d + 2 gap theorem\] inspired by it. We use the same notation for IETs, discontinuities, gap sets and multisets, ... from before.

Boshernitzan’s Proof {#subsection: Boshernitzan's proof}
--------------------

Following [@Boshernitzan1985-fb], define the directed graph $\operatorname{GGaps}_{T, N} = (V_{T, N}, E_{T,N})$. The vertices agree with the gaps $V_{T,N} = \widetilde{\operatorname{Gaps}}_{T, N}$. There exists an edge $e_{i,j} : \operatorname{gap}_{T, N}(i) \to \operatorname{gap}_{T, N}(j)$ if and only if $(T^{-1}\operatorname{gap}_{T,N}(i)) \cap \operatorname{gap}_{T,N}(j) \neq \varnothing$. It should be noted that $\operatorname{GGaps}_{T,N}$ is the *Rauzy graph* describing the coding generated by $T^{-1}$ and the partioning of $[0,1)$ defined by $\{T^i0\}_{i=0}^{N-1}$.

For a general directed graph $G = (V, E)$, a function $w : V \sqcup E \to \mathbb{R}^+$ is said to be a *weight function* if

1.  $\sum_{v \in V} w(v) = 1$, and

2.  for any $v \in V$, $$w(v) = \sum_{e \in \operatorname{in}(v)}w(e) = \sum_{e \in \operatorname{out}(v)}w(e),$$ where $\operatorname{in}(v)$ and $\operatorname{out}(v)$ are the edges of $G$ going in and coming out of $v$.

The *support* $\operatorname{supp}(w)$ of is the subgraph $G_w = (V_w, E_w) \subseteq G$ defined by $V_w = \{v \in V \mid w(v) > 0\}$ and $E_w = \{e \in E \mid w(e) > 0\}$.

A cycle $v_1, v_2, \cdots, v_k$ is said to be a *distinct cycle* if $\operatorname{indeg}(v_i) = \operatorname{outdeg}(v_i)$ for every $i = 1, 2, \cdots, k$.

Let $G$ be a directed graph without distinct cycles, and $w$ a weight function of $G$ supported on the whole graph. The cardinality of the set of possible vertex weight has the upper bound $$\#\{w(v) \mid v \in V\} \leq 3 (\#E - \#V).$$

The Lebesgue measure induces a weight function $w$ on the graph $\operatorname{GGaps}_{T, N}$: for every $v_i \in V_{T, N}$, take $w(v_i) = \operatorname{Leb}(\operatorname{gap}_{T,N}(i))$, and for every $e_{i, j} \in E_{T,N}$, take $w(e_{i, j}) = \operatorname{Leb}((T^{-1}\operatorname{gap}_{T,N}(i)) \cap \operatorname{gap}_{T,N}(j))$.

The outdegree of a vertex $v_i \in \operatorname{GGaps}_{T, N}$ can be expressed as $$\operatorname{outdeg}(v_i) = 1 + 1_{\operatorname{gap}_{T,N}(i)}(T^N0) + \sum_{i=1}^{d-1}1_{\operatorname{gap}_{T,N}(i)}(\alpha_i).$$ From this it follows that $$\begin{aligned}
\#E_{T,N} - \#V_{T,N} &=& \sum_{v \in V} (\operatorname{outdeg}(v) - 1) \\
&=& \sum_{i=0}^{d-1} \left(1_{\operatorname{gap}_{T,N}(i)}(T^N0) + \sum_{k=1}^{d-1}1_{\operatorname{gap}_{T,N}(i)}(\alpha_k)\right) \\
&\leq& d - 1.\end{aligned}$$ The reason this is $d-1$ and not $d$ is that $T^{1}0 = \alpha_{i_0}$, with $i_0 = \pi(1) - 1$. That is, the discontinuity $\alpha_{i_0}$ is an end point of one of the gaps, and hence necessarily does not contribute to the sum.

A minimal IET $T$ will not have distinct cycles in $\operatorname{GGaps}_{T, N}$. This proves Boshernitzan’s $3(d-1)$ Gap Theorem (\[theorem: 3(d-1) gap theorem\]).

Improvement
-----------

In this section, we present a modification of the Rauzy graphs $\operatorname{GGaps}_{T, N}$ used by Boshernitzan to prove \[theorem: 3(d-1) gap theorem\], and provide a proof for \[theorem: d + 2 gap theorem\].

For $i=0, 1, \cdots, d-1$, we denote the closest orbit point in the segment $\{T^n0\}_{n=0}^{N-1}$ to a discontinuity $\beta_i$ of $T$ by $$r(i) = r_{T, N}(i) := \min \{T^n0 \mid 1 \leq n < N, T^n0 > \beta_i\},$$ and for $i = 1, 2, \cdots, d$, we denote the closest orbit point to a discontinuity $\beta_i$ by $$l(i) = l_{T, N}(i) := \max \{T^n0 \mid 1 \leq n < N, T^n0 < \beta_i\}.$$ We also denote the collection of “slots” on the right and left of the discontinuitities of by $$\mathfrak{R} = \mathfrak{R}_{T,N} := \{(\beta_i, r(i)) \mid i = 0, 1, \cdots, d-1\},$$ and $$\mathfrak{L} = \mathfrak{L}_{T,N} := \{(l(i), \beta_i) \mid i = 1, 2, \cdots, d\}.$$ Finally, we write $$R_i = R_{T, N, i} := r(i) - \beta_i,\ i = 0, 1, \cdots, d-1$$ and $$L_i = L_{T, N, i} := \beta_i - l(i),\ i = 1, 2, \cdots, d.$$ for the respective lengths of the right and left slots. As was done with the circle rotation, we *notationally* identify $R_i$ and $(\beta_i, r(i))$, and $L_i$ and $(l(i), \beta_i)$.

We define the graph $\operatorname{FGaps}_{T, N}$ as follows:

-   The vertices $FV_{T, N} = \widetilde{Gaps}_{T, N} \sqcup \mathfrak{R}_{T,N} \sqcup \mathfrak{L}_{T,N}$.

-   The edges: When $T^{-1}$ acts on a gap in $\widetilde{\operatorname{Gaps}}_{T, N}$, it maps it to a disjoint union–modulo the endpoints–of elements of $\widetilde{Gaps}_{T, N} \sqcup \mathfrak{R}_{T,N} \sqcup \mathfrak{L}_{T,N}$. A directed edge goes out of each gap and into the elements of $\widetilde{Gaps}_{T, N} \sqcup \mathfrak{R}_{T,N} \sqcup \mathfrak{L}_{T,N}$ it gets pulled back to by $T^{-1}$. The collection of all edges is denoted by $FE_{T,N}$.

It can be easily seen that $\operatorname{FGaps}_{T, N}$ is a forest. It should also be noted that if we glue each pair $L_i$ and $R_i$, $i = 1, 2, \cdots, d-1$, together and identify them with the gap $L_i \cup \{\beta_i\} \cup R_i$ surrounding the discontinuity $\beta_i$, we get Boshernitzan’s Rauzy graph $\operatorname{GGaps}_{T, N}$.

We first present an example to make both the definition of the forest and the idea of the proof that will follow clearer.

Example
-------

Consider the IET with length data $\mathbf{\lambda} = (1/\sqrt{3}, 1/\sqrt{2} - 1/\sqrt{3}, 1 - 1/\sqrt{2})$ (i.e. $T$ has discontinuities at $\beta_1 = 1/\sqrt{3}$ and $\beta_2 = 1/\sqrt{2}$) and combinatorial data $\pi = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1\end{pmatrix}$. The inverse map $T^{-1}$ is an IET, with length data $\mathbf{\lambda}^{-1} = (1 - 1/\sqrt{2}, 1/\sqrt{2} - 1/\sqrt{3}, 1/\sqrt{3})$ (i.e. discontinuities at $\alpha_1 = 1 - 1/\sqrt{2}$ and $\alpha_2 = 1 - 1/\sqrt{3}$), and combinatorial data $\pi^{-1} = \pi$.

Below we show two copies of the interval $[0,1)$, along with the orbit points $\{T^k 0\}_{k=1}^8$, the points $\alpha_i$ bounding the subintervals being permuted by $T^{-1}$, and the points $\beta_i$ bounding the subintervals being permuted by $T$.

(0,0) – (1,0) node\[fill=red, scale = 0.25\] at (0.42265,0) node at (0.42265,0.05) [$T^{1}0$]{}

node\[fill=red, scale = 0.25\] at (0.845299,0) node at (0.845299,0.05) [$T^{2}0$]{}

node\[fill=red, scale = 0.25\] at (0.138193,0) node at (0.138193,0.05) [$T^{3}0$]{}

node\[fill=red, scale = 0.25\] at (0.560842,0) node at (0.560842,0.05) [$T^{4}0$]{}

node\[fill=red, scale = 0.25\] at (0.983492,0) node at (0.983492,0.05) [$T^{5}0$]{}

node\[fill=red, scale = 0.25\] at (0.276385,0) node at (0.276385,0.05) [$T^{6}0$]{}

node\[fill=red, scale = 0.25\] at (0.699035,0) node at (0.699035,0.05) [$T^{7}0$]{}

node\[fill=cyan, scale = 0.25\] at (0.414578,0) node at (0.414578,0.08) [$\textcolor{cyan}{T^{8}0}$]{};

(0,-0.015) – (0,0.015) (0.292893, -0.015) – (0.292893, 0.015) (0.42265, -0.015) – (0.42265, 0.015) (1,-0.015) – (1, 0.015); node at (0,-0.05) [$\alpha_0$]{} node at (0.292893,-0.05) [$\alpha_1$]{} node at (0.42265,-0.05) [$\alpha_2$]{} node at (1,-0.05) [$\alpha_3$]{};

(0,0) – (1,0) node\[fill=red, scale = 0.25\] at (0.42265,0) node at (0.42265,0.05) [$T^{1}0$]{}

node\[fill=red, scale = 0.25\] at (0.845299,0) node at (0.845299,0.05) [$T^{2}0$]{}

node\[fill=red, scale = 0.25\] at (0.138193,0) node at (0.138193,0.05) [$T^{3}0$]{}

node\[fill=red, scale = 0.25\] at (0.560842,0) node at (0.560842,0.05) [$T^{4}0$]{}

node\[fill=red, scale = 0.25\] at (0.983492,0) node at (0.983492,0.05) [$T^{5}0$]{}

node\[fill=red, scale = 0.25\] at (0.276385,0) node at (0.276385,0.05) [$T^{6}0$]{}

node\[fill=red, scale = 0.25\] at (0.699035,0) node at (0.699035,0.05) [$T^{7}0$]{};

(0,-0.015) – (0,0.015) (0.57735, -0.015) – (0.57735, 0.015) (0.707107, -0.015) – (0.707107, 0.015) (1,-0.015) – (1, 0.015); node at (0,-0.05) [$\beta_0$]{} node at (0.57735,-0.05) [$\beta_1$]{} node at (0.707107,-0.05) [$\beta_2$]{} node at (1,-0.05) [$\beta_3$]{};

Now, considering the action of $T^{-1}$ on $\widetilde{\operatorname{Gaps}}_{T, 8}$, we get the following diagram for the forest $\operatorname{FGaps}_{T, 8}$. $$\xymatrix@C-1pc{
(T^4 0, T^7 0) \ar[r] & (T^3 0, T^6 0) \ar[r] & (T^2 0, T^5 0) \ar[r] & (T^1 0, T^4 0) \ar[r] & \underline{(\beta_0, T^3 0)} \\
 & & \underline{(T^5 0, \beta_3)} & & \\
(T^7 0, T^2 0) \ar[r] & \underline{(T^6 0, T^1 0)} \ar[ur] \ar[r] \ar[dr] & (\beta_1, T^7 0) & & \\
 & & (T^7 0, \beta_2) & &
}$$ When we get a gap pointing to another gap like $$\xymatrix{
(T^3 0, T^6 0) \ar[r] & (T^2 0, T^5 0)
}$$ the two gaps have the same length. If a gap splits (i.e. its preimage under $T^{-1}$ is a disjoint union of more than one interval), its length is the sum of the intervals it splits into. As such, the gaps that contribute to the set of gap lengths $G(8)$ are

1.  the gaps that show on the extreme right, namely $(\beta_0, T^3 0)$ and $(T^5 0, \beta_3)$, and

2.  the gaps that split, namely $(T^6 0, T^1 0)$.

Note how the intervals showing on the extreme right in the above diagram are all slots surrounding the discontinuitites $\beta_i$ of $T$.

We thus get that $$\operatorname{Gaps}_{T, 8} := \{R_0, L_3, L_3 + R_1 + L_2\}.$$

Proof
-----

We consider any orbit $\{T^k0\}_{k=0}^{N-1}$, with $N$ an integer large enough so that the orbit points separate the discontinuities $\alpha_i$ of $T^{-1}$. For counting purposes, we have to consider:

1.  The gaps that will split due to intersecting with the discontinuities of $T^{-1}$, or the point $T^N 0$.

2.  The gaps that get pulled back to gaps.

3.  The first and last gaps.

We choose to call the point $T^N0$ a “ghost” orbit point, since it is not in the orbit $\{T^k0\}_{k=0}^{N-1}$, but introduces the orbit point $T^{N-1}0$ when it gets pulled back by $T^{-1}$.

We enumerate the different cases pictorially, with red representing orbit points, and cyan representing the point $T^N 0$. The index $i_0 = \pi(1) - 1$ specifies the discontinuity $\alpha_{i_0}$ where $T^1 0$ occurs.

(0,0) – (12,0) node at (0.5, 0.5) [Case V]{} node\[fill=red\] at (1, 0) node\[fill=red\] at (2, 0) node at (2.5, 0.5) [Case IV]{} node at (3.5, 0.5) [Case IV]{} node\[fill=red\] at (4, 0) node at (4.5, 0.5) [Case I]{} node\[fill=red\] at (5, 0) node\[fill=red\] at (7, 0) node\[fill=red\] at (8, 0) node at (8.5, 0.5) [Case II]{} node\[fill=red\] at (9,0) node at (9.5, 0.5) [Case III]{} node at (11.5, 0.5) [Case VI]{} node\[fill=red\] at (10, 0) node\[fill=red\] at (11, 0) ; (3,-0.25) – (3, 0.25); (6,-0.25) – (6, 0.25); (9,-0.25) – (9, 0.25);

Based on the location where the ghost orbit point $T^N0$ situates itself, there are six distinct cases that should be accounted for.

-   Case I: The point $T^N0$ belongs to a gap $(T^{n_1}0, T^{n_2}0)$ with $n_1, n_2 \neq 1$.

-   Case II: Same as case I with $n_2 = 1$.

-   Case III: Same as case I with $n_1 = 1$.

-   Case IV: The point $T^N0$ belongs to $(T^{n_1}0, T^{n_2}0)$ that includes a $\alpha_i$.

-   Case V: The point $T^n 0$ belongs to the first gap $(0, T^{\sigma(1)}0)$.

-   Case VI: The point $T^N0$ belongs to the last gap $(T^{\sigma(N-1)}0, 1)$.

We now proceed to count the possible gap lengths.

Gaps that split
---------------

### Case I

-   One instance of

    (-0.5,0) – (4.5,0) node\[fill=red\] at (0,0) node at (0, 0.5) [$T^{n_1}0$]{} node\[fill=red\] at (2,0) node at (2,0.5) [$T^1 0$]{} node at (2,-0.5) [$\alpha_{i_0}$]{} node\[fill=red\] at (4,0) node at (4,0.5) [$T^{n_2}0$]{}; (2,-0.25) – (2, 0.25);

    $$\label{eq:I1}
    \tag{I.1}
    \xymatrix{
    (T^{n_1}0, T^10) \ar[d]    & (T^1 0, T^{n_2}0) \ar[d] \\
    (T^{n_1 - 1}0, \beta_{\pi^{-1}(i_0)})    & (\beta_0, T^{n_2 - 1} 0)
    }$$

    This contributes the two lengths $L_{\pi^{-1}(i_0)}$ and $R_0$ to the set of gap lengths.

-   $d-2$ instances of

    (-0.5,0) – (4.5,0) node\[fill=red\] at (0,0) node at (0, 0.5) [$T^{n_1}0$]{} node at (2,-0.5) [$\alpha_i$]{} node\[fill=red\] at (4,0) node at (4,0.5) [$T^{n_2}0$]{}; (2,-0.25) – (2, 0.25);

    $$\label{eq:I2}
    \tag{I.2}
    \xymatrix{
        &  (T^{n_1}0, T^{n_2}0) \ar[dl] \ar[dr]  &   \\
    (T^{n_1 - 1}0, \beta_{\pi^{-1}(i)}) & & (\beta_{\pi^{-1}(i+1) - 1}, T^{n_2 - 1}0)
    }$$

    Each of those instances contributes $L_{\pi^{-1}(i)} + R_{\pi^{-1}(i+1) - 1}$ to the set of gap lengths, for a total of $d-2$ elements.

-   One instance of

    (-0.5,0) – (4.5,0) node\[fill=red\] at (0,0) node at (0, 0.5) [$T^{n_1}0$]{} node\[fill=cyan\] at (2,0) node at (2, 0.5) [$T^N0$]{} node at (2,0.5) [$T^N 0$]{} node\[fill=red\] at (4,0) node at (4,0.5) [$T^{n_2}0$]{};

    $$\label{eq:I3}
    \tag{I.3}
    \xymatrix{
     & (T^{n_1}0, T^{n_2}0) \ar[dl] \ar[dr] & \\
    (T^{n_1 - 1}0, T^{N-1}0) & & (T^{N-1}0, T^{n_2 - 1}0)
    }$$

    This contributes the sum of the lengths of the two consecutive gaps $(T^{n_1 - 1}0, T^{N-1}0)$ and $(T^{N-1}0, T^{n_2 - 1}0)$ to the set of gap lengths.

### Case II

-   One instance of

    (-0.5,0) – (4.5,0) node\[fill=red\] at (0,0) node at (0, 0.5) [$T^{n_1}0$]{} node\[fill=cyan\] at (1,0) node at (1, 0.5) [$T^N0$]{} node\[fill=red\] at (2,0) node at (2,0.5) [$T^1 0$]{} node at (2,-0.5) [$\alpha_{i_0}$]{} node\[fill=red\] at (4,0) node at (4,0.5) [$T^{n_2}0$]{}; (2,-0.25) – (2, 0.25);

    $$\label{eq:II1}
    \tag{II.1}
    \xymatrix@C-2pc{
        & (T^{n_1}0, T^10) \ar[dl] \ar[dr] & & (T^1 0, T^{n_2}0) \ar[d] \\
    (T^{n_1 - 1}0, T^{N-1}0) &    & (T^{N-1}0, \beta_{\pi^{-1}(i_0)}) & (\beta_0, T^{n_2 - 1} 0)
    }$$

    This instance contributes the two lengths $|(T^{n_1 - 1}0, T^{N-1}0)| + L_{\pi^{-1}(i_0)}$ and $R_0$ to the set of gap lengths.

-   $d-2$ instances of

    (-0.5,0) – (4.5,0) node\[fill=red\] at (0,0) node at (0, 0.5) [$T^{n_1}0$]{} node at (2,-0.5) [$\alpha_i$]{} node\[fill=red\] at (4,0) node at (4,0.5) [$T^{n_2}0$]{}; (2,-0.25) – (2, 0.25);

    $$\label{eq:II2}
    \tag{II.2}
    \xymatrix{
        & (T^{n_1}0, T^{n_2}0) \ar[dr] \ar[dl] & \\
    (T^{n_1 - 1}0, \beta_{\pi^{-1}(i)}) &   & (\beta_{\pi^{-1}(i+1) - 1}, T^{n_2 - 1}0)
    }$$

    Each of these instance contribute $L_{\pi^{-1}(i)} + R_{\pi^{-1}(i+1) - 1}$ to the set of gap lengths, for a total of $d-2$ lengths.

### Case III

-   One instance of

    (-0.5,0) – (4.5,0) node\[fill=red\] at (0,0) node at (0, 0.5) [$T^{n_1}0$]{} node\[fill=red\] at (2,0) node at (2,-0.5) [$\alpha_{i_0}$]{} node at (2,0.5) [$T^1 0$]{} node\[fill=cyan\] at (3,0) node at (3, 0.5) [$T^N0$]{} node\[fill=red\] at (4,0) node at (4,0.5) [$T^{n_2}0$]{}; (2,-0.25) – (2, 0.25);

    $$\label{eq:III1}
    \tag{III.1}
    \xymatrix@C-2pc{
    (T^{n_1}0, T^1 0) \ar[d] & & (T^1 0, T^{n_2}0) \ar[dl] \ar[dr] \\
    (T^{n_1 - 1}0, \beta_{\pi^{-1}(i_0)}) & (\beta_0, T^{N-1} 0) & & (T^{N-1} 0, T^{n_2 - 1}0)
    }$$

-   $d-2$ instances of

    (-0.5,0) – (4.5,0) node\[fill=red\] at (0,0) node at (0, 0.5) [$T^{n_1}0$]{} node at (2,-0.5) [$\alpha_i$]{} node\[fill=red\] at (4,0) node at (4,0.5) [$T^{n_2}0$]{}; (2,-0.25) – (2, 0.25);

    $$\label{eq:III2}
    \tag{III.2}
    \xymatrix@C-2pc{
        & (T^{n_1}0, T^{n_2}0) \ar[dr] \ar[dl] & \\
    (T^{n_1 - 1}0, \beta_{\pi^{-1}(i)}) &   & (\beta_{\pi^{-1}(i+1) - 1}, T^{n_2 - 1}0)
    }$$

    Each of those instances contribute $L_{\pi^{-1}(i)} + R_{\pi^{-1}(i+1) - 1}$ to the set of gap lengths, for a total of $d-2$ lengths.

### Case IV

-   One instance of

    (-0.5,0) – (4.5,0) node\[fill=red\] at (0,0) node at (0, 0.5) [$T^{n_1}0$]{} node\[fill=red\] at (2,0) node at (2,0.5) [$T^1 0$]{} node at (2,-0.5) [$\alpha_{i_0}$]{} node\[fill=red\] at (4,0) node at (4,0.5) [$T^{n_2}0$]{}; (2,-0.25) – (2, 0.25);

    $$\label{eq:IV1}
    \tag{IV.1}
    \xymatrix@C-2pc{
    (T^{n_1}0,\ T^10) \ar[d] & (T^1 0,\ T^{n_2}0) \ar[d] \\
    (T^{n_1 - 1}0,\ \beta_{\pi^{-1}(i_0)}) & (\beta_0,\ T^{n_2 - 1} 0)
    }$$

    This contributes two lengths $L_{\pi^{-1}(i_0)}$ and $R_0$ to the set of gap lengths.

-   One instance of

    (-0.5,0) – (4.5,0) node\[fill=red\] at (0,0) node at (0, 0.5) [$T^{n_1}0$]{} node at (2,-0.5) [$\alpha_i$]{} node\[fill=cyan\] at (1,0) node at (1, 0.5) [$T^N0$]{} node\[fill=red\] at (4,0) node at (4,0.5) [$T^{n_2}0$]{}; (2,-0.25) – (2, 0.25);

    $$\label{eq:IV2}
    \tag{IV.2}
    \xymatrix@C-2pc{
        & (T^{n_1}0, T^{n_2}0) \ar[dl] \ar[d] \ar[dr] & \\
    (T^{n_1-1}0, T^{N-1}0) & (T^{N-1}0, \beta_{\pi^{-1}(i)}) & (\beta_{\pi^{-1}(i+1)-1}, T^{n_2-1}0)
    }$$

    This instance contributes $|(T^{n_1 - 1}0, T^{N-1}0)| + L_{\pi^{-1}(i)} + R_{\pi^{-1}(i+1) - 1}$ to the set of gap lengths.

-   $d-3$ instances of

    (-0.5,0) – (4.5,0) node\[fill=red\] at (0,0) node at (0, 0.5) [$T^{n_1}0$]{} node at (2,-0.5) [$\alpha_i$]{} node\[fill=red\] at (4,0) node at (4,0.5) [$T^{n_2}0$]{}; (2,-0.25) – (2, 0.25);

    $$\label{eq:IV3}
    \tag{IV.3}
    \xymatrix@C-2pc{
        & (T^{n_1}0, T^{n_2}0) \ar[dr] \ar[dl] & \\
    (T^{n_1 - 1}0, \beta_{\pi^{-1}(i)}) &   & (\beta_{\pi^{-1}(i+1) - 1}, T^{n_2 - 1}0)
    }$$

    Each of these instances contribute $L_{\pi^{-1}(i)} + R_{\pi^{-1}(i+1)-1}$ to the set of gap lengths, for a total of $d-3$ lengths.

### Case V

-   One instance of

    (-0.5,0) – (4.5,0) node\[fill=red\] at (0,0) node at (0, 0.5) [$T^{n_1}0$]{} node\[fill=red\] at (2,0) node at (2,0.5) [$T^1 0$]{} node at (2,-0.5) [$\alpha_{i_0}$]{} node\[fill=red\] at (4,0) node at (4,0.5) [$T^{n_2}0$]{}; (2,-0.25) – (2, 0.25);

    $$\label{eq:V1}
    \tag{V.1}
    \xymatrix{
    (T^{n_1}0, T^10) \ar[d]    & (T^1 0, T^{n_2}0) \ar[d] \\
    (T^{n_1 - 1}0, \beta_{\pi^{-1}(i_0)})    & (\beta_0, T^{n_2 - 1} 0)
    }$$

    This contributes the two lengths $L_{\pi^{-1}(i_0)}$ and $R_0$ to the set of gap lengths.

-   $d-2$ instances of

    (-0.5,0) – (4.5,0) node\[fill=red\] at (0,0) node at (0, 0.5) [$T^{n_1}0$]{} node at (2,-0.5) [$\alpha_i$]{} node\[fill=red\] at (4,0) node at (4,0.5) [$T^{n_2}0$]{}; (2,-0.25) – (2, 0.25);

    $$\label{eq:V2}
    \tag{V.2}
    \xymatrix{
        &  (T^{n_1}0, T^{n_2}0) \ar[dl] \ar[dr]  &   \\
    (T^{n_1 - 1}0, \beta_{\pi^{-1}(i)}) & & (\beta_{\pi^{-1}(i+1) - 1}, T^{n_2 - 1}0)
    }$$

    Each of those instances contributes $L_{\pi^{-1}(i)} + R_{\pi^{-1}(i+1) - 1}$ to the set of gap lengths, for a total of $d-2$ elements.

-   One instance of

    (-0.5,0) – (4.5,0) node at (-0.5, 0.5) [$\alpha_0 = 0$]{} node\[fill=cyan\] at (2,0) node at (2, 0.5) [$T^N0$]{} node at (2,0.5) [$T^N 0$]{} node\[fill=red\] at (4,0) node at (4,0.5) [$T^{\sigma(1)}0$]{};

    This has the first gap length $R_0$.

### Case VI

-   One instance of

    (-0.5,0) – (4.5,0) node\[fill=red\] at (0,0) node at (0, 0.5) [$T^{n_1}0$]{} node\[fill=red\] at (2,0) node at (2,0.5) [$T^1 0$]{} node at (2,-0.5) [$\alpha_{i_0}$]{} node\[fill=red\] at (4,0) node at (4,0.5) [$T^{n_2}0$]{}; (2,-0.25) – (2, 0.25);

    $$\label{eq:VI1}
    \tag{VI.1}
    \xymatrix{
    (T^{n_1}0, T^10) \ar[d]    & (T^1 0, T^{n_2}0) \ar[d] \\
    (T^{n_1 - 1}0, \beta_{\pi^{-1}(i_0)})    & (\beta_0, T^{n_2 - 1} 0)
    }$$

    This contributes the two lengths $L_{\pi^{-1}(i_0)}$ and $R_0$ to the set of gap lengths.

-   $d-2$ instances of

    (-0.5,0) – (4.5,0) node\[fill=red\] at (0,0) node at (0, 0.5) [$T^{n_1}0$]{} node at (2,-0.5) [$\alpha_i$]{} node\[fill=red\] at (4,0) node at (4,0.5) [$T^{n_2}0$]{}; (2,-0.25) – (2, 0.25);

    $$\label{eq:VI2}
    \tag{VI.2}
    \xymatrix{
        &  (T^{n_1}0, T^{n_2}0) \ar[dl] \ar[dr]  &   \\
    (T^{n_1 - 1}0, \beta_{\pi^{-1}(i)}) & & (\beta_{\pi^{-1}(i+1) - 1}, T^{n_2 - 1}0)
    }$$

    Each of those instances contributes $L_{\pi^{-1}(i)} + R_{\pi^{-1}(i+1) - 1}$ to the set of gap lengths, for a total of $d-2$ elements.

-   One instance of

    (-0.5,0) – (4.5,0) node\[fill=red\] at (0,0) node at (0, 0.5) [$T^{\sigma(N-1)}0$]{} node\[fill=cyan\] at (2,0) node at (2, 0.5) [$T^N0$]{} node at (2,0.5) [$T^N 0$]{} node at (4.5,0.5) [$\alpha_d = 1$]{};

    This has the last gap length $L_d$.

Gaps that get pulled to other gaps
----------------------------------

If a gap $(T^{n_1}0, T^{n_2}0)$ with $n_1, n_2 \neq 1$ does not include $T^N 0$ or a discontinuity $\alpha_i$ of $T^{-1}$, it will be pulled back by $T^{-1}$ to the gap $(T^{n_1 - 1}0, T^{n_2 - 1}0)$.

(-0.5,0) – (4.5,0) node\[fill=red\] at (0,0) node at (0,0.5) [$T^{n_1}0$]{} node\[fill=red\] at (4,0) node at (4,0.5) [$T^{n_2}0$]{};

The two gaps have the same lengths, so no instance of $$\xymatrix{
(T^{n_1}0, T^{n_2}0) \ar[d] \\ (T^{n_1 - 1}0, T^{n_2 - 1}0)
}$$ contributes new elements to the set of gap lengths.

The first and last gaps: $(0, T^{\sigma(1)}0)$ and $(T^{\sigma(N-1)}0, 1)$
--------------------------------------------------------------------------

The first gap $(0, T^{\sigma(1)}0)$ shows up as a gap length in \[eq:I1\], \[eq:II1\], \[eq:IV1\], \[eq:V1\], and \[eq:VI1\]; and so its length $R_0$ is accounted for in those cases. However, the length of the first gap $R_0$ shows up as a summand in \[eq:III1\]. In that case, the first gap contributes $R_0$ to the set of gap lengths on its own.

The situation is similar with the last gap $(T^{\sigma(N-1)}0, 1)$ and its length $L_d$. We get one of two cases:

1.  If $\pi^{-1}(i_0) = d$ (i.e. if $\pi(1) - \pi(d) = 1$) in cases I, III, IV, V, and VI above: the length of the last gap $L_d$ shows up as a gap length in equations \[eq:I1\], \[eq:III1\], \[eq:IV1\], \[eq:V1\], \[eq:VI1\] and is accounted for. (Note that in case VI the last gap length shows as a gap length.)

2.  Otherwise, the length of the last gap contribute as a summand in \[eq:I2\], \[eq:II1\] or \[eq:II2\], \[eq:III2\], \[eq:IV2\] or \[eq:IV3\] and is not accounted for. In that case, the last gap contributes $L_d$ to the set of gap lengths on its own.

Adding up all the contributions, we get the following table with upper bounds on the number of possible gap lengths:

              $\pi^{-1}(i_0) = d$   $\pi^{-1}(i_0) \neq d$
  ---------- --------------------- ------------------------
    Case I           $d+1$                  $d+2$
   Case II           $d+1$                  $d+1$
   Case III          $d+1$                  $d+2$
   Case IV            $d$                   $d+1$
    Case V            $d$                   $d+1$
   Case VI            $d$                   $d+1$

This proves \[theorem: d + 2 gap theorem\].

[9]{} Alessandri, P., & Berthé, V. (1998). Three distance theorems and combinatorics on words. Enseignement des Mathematiques, 44, 103–132.

Arnol’d, V. I. (2007). Small Denominators and Problems of Stability of Motion in Classical and Celestial Mechanics. Russian Mathematical Surveys, 18(6), 85. Accessed 19 October 2016

Athreya, J. S. (2012). Gap distributions and homogeneous dynamics. Geometry, Topology, and Dynamics in Negative Curvature 425, 1.

Athreya, J. S., & Boshernitzan, M. (2012). Ergodic Properties of Compositions of Interval Exchange Maps and Rotations. Nonlinearity 26 (2013), 417-421.

Athreya, J. S., & Cheung, Y. (2013). A Poincaré Section for the Horocycle Flow on the Space of Lattices. International Mathematics Research Notices. doi:10.1093/imrn/rnt003

Boca, F. P., Cobeli, C., & Zaharescu, A. (2001). A conjecture of R. R. Hall on Farey points. Journal fur die Reine und Angewandte Mathematik. \[Crelle’s Journal\], 2001(535). doi:10.1515/crll.2001.049

Boshernitzan, M. (1985). A Condition for Minimal Interval Exchange Maps to be Uniquely Ergodic. Duke Mathematical Journal, 52(3), 723–752. Accessed 28 September 2016

Chung, F., & Graham, R. L. (1976). On the set of distances determined by the union of arithmetic progressions. Ars Combinatoria, 1, 57–76.

Forni, G. (1997). Solutions of the Cohomological Equation for Area-Preserving Flows on Compact Surfaces of Higher Genus. Annals of mathematics, 146(2), 295–344.

Haynes, A., & Marklof, J. (2017). Higher dimensional Steinhaus and Slater problems via homogeneous dynamics. arXiv \[math.NT\]. http://arxiv.org/abs/1707.04094

Keane, M. (1975). Interval Exchange Transformations. Mathematische Zeitschrift, 141, 25–32. Accessed 24 October 2016

Keane, M. (1977). Non-ergodic interval exchange transformations. Israel Journal of Mathematics, 26(2), 188–196.

Keynes, H. B., & Newton, D. (1976). A “minimal”, non-uniquely ergodic interval exchange transformation. Mathematische Zeitschrift, 148(2), 101–105.

Liang, F. M. (1979). A short proof of the $3d$ distance theorem. Discrete mathematics, 28(3), 325–326.

Marklof, J., & Strömbergsson, A. (2016). The three gap theorem and the space of lattices. arXiv \[math.NT\]. http://arxiv.org/abs/1612.04906

Masur, H. (1982). Interval Exchange Transformations and Measured Foliations. Annals of mathematics, 115(1), 169–200.

Mayero, M. (2006, September 22). The Three Gap Theorem (Steinhauss Conjecture). arXiv \[cs.LO\]. http://arxiv.org/abs/cs/0609124

Meyers, R. A. (2011). Mathematics of Complexity and Dynamical Systems. Springer Science & Business Media.

Nogueira, A. (1989). Almost all interval exchange transformations with flips are nonergodic. Ergodic Theory and Dynamical Systems, 9(3), 515–525.

Polanco, G., Schultz, D., & Zaharescu, A. (n.d.). Continuous distributions arising from the Three Gap Theorem. International Journal of Number Theory, 0(0), 1650107.

Rauzy, G. (1979). Échanges d’intervalles et transformations induites. Acta Arithmetica, 34(4), 315–328.

Sós, V. T. (1957). On the theory of diophantine approximations. I1 (on a problem of A. Ostrowski). Acta Mathematica Academiae Scientiarum Hungaricae, 8(3-4), 461–472.

Sós, V. T. (1958). On the distribution mod 1 of the sequence n$\alpha$. Annales Universitatis Scientiarum Budapestinensis de Rolando Eotvos Nominatae. Sectio Mathematica, 1, 127–134.

Świerczkowski, S. (1958). On successive settings of an arc on the circumference of a circle. Fundamenta Mathematicae, 46(2), 187–189.

Veech, W. A. (1982). Gauss Measures for Transformations on the Space of Interval Exchange Maps. Annals of mathematics, 115(2), 201–242.

Veech, W. A. (1978). Interval exchange transformations. Journal d’Analyse Mathematique, 33(1), 222–272.

Yoccoz, J. C. (2007). Interval exchange maps and translation surfaces. Homogeneous flows, moduli spaces and arithmetic, 2007.

Zorich, A. (1996). Finite Gauss measure on the space of interval exchange transformations. Lyapunov exponents. In Annales de l’institut Fourier (Vol. 46, pp. 325–370).

Zorich, A. (1997). Deviation for interval exchange transformations. Ergodic Theory and Dynamical Systems, 17(06), 1477–1499.

Zorich, A. (2006). Flat Surfaces. Frontiers in number theory, physics, and geometry I, 2006 - Springer.

[^1]: The number of one of the gaps might be $0$. For instance, the number of $C$ gaps is zero on the Farey arc $\left(\frac{0}{1}, \frac{1}{N}\right)$.
