---
author:
- 'Quentin De Mourgues\'
title: |
    \
    \
    of the KZB Classification Theorem
---

Rauzy-type dynamics are group actions on a collection of combinatorial objects. The first and best known example (the Rauzy dynamics) concerns an action on permutations, associated to interval exchange transformations (IET) for the Poincaré map on compact orientable translation surfaces. The equivalence classes on the objects induced by the group action have been classified by Kontsevich and Zorich, and by Boissy through methods involving both combinatorics algebraic geometry, topology and dynamical systems. Our precedent paper [@DS17] as well as the one of Fickenscher [@Fic16] proposed an ad hoc combinatorial proof of this classification.

However, unlike those two previous combinatorial proofs, we develop in this paper a general method, called the labelling method, which allows one to classify Rauzy-type dynamics in a much more systematic way. We apply the method to the Rauzy dynamics and obtain a third combinatorial proof of the classification. The method is versatile and will be used to classify three other Rauzy-type dynamics in follow-up articles.

Another feature of this paper is to introduce an algorithmic method to work with the sign invariant of the Rauzy dynamics. With this method we can prove most of the identities appearing in the literature so far ([@KZ03],[@Del13] [@Boi13] [@DS17]...) in an automatic way.

The sign invariant {#sec.signinv}
==================

Arf functions for permutations {#ssec.arf_inv}
------------------------------

For $\s$ a permutation in $\kS_n$, let () = \# { 1i&lt;j n | (i)&lt;(j) } i.e. $\chi(\s)$ is the number of pairs of non-crossing edges in the diagram representation of $\s$.

Let $E=E(\s)$ be the subset of $n$ edges in $\cK_{n,n}$ described by $\s$. For any $I \subseteq E$ of cardinality $k$, the permutation $\s|_{I} \in \kS_k$ is defined in the obvious way, as the one associated to the subgraph of $\cK_{n,n}$ with edge-set $I$, with singletons dropped out, and the inherited total ordering of the two vertex-sets.

Define the two functions $$\begin{aligned}
A(\s)
&:=
\sum_{I \subseteq E(\s)} (-1)^{\chi(\s|_I)}
\ef;
&
\Abar(\s)
&:=
\sum_{I \subseteq E(\s)} (-1)^{|I|+\chi(\s|_I)}
\ef.\end{aligned}$$ When $\s$ is understood, we will just write $\chi_I$ for $\chi(\s|_I)$. The quantity $A$ is accessory in the forthcoming analysis, while the crucial fact for our purpose is that the quantity $\Abar$ is invariant in the $\perms_n$ dynamics.

In the following section, we define a technique to demonstrate identities of the arf invariant involving differents configurations.

Automatic proofs of Arf identitites {#ssec.arfcalcseasy}
-----------------------------------

We will *not* try to evaluate Arf functions of large configurations starting from scratch. We will rather compare the Arf functions of two (or more) configurations, which differ by a finite number of edges, and establish linear relations among their Arf functions. The method we develop here, gives an algorithm to find and check Arf identities.

In order to have the appropriate terminology for expressing this strategy, let us define the following: Given a permutation $\s$ define $\s_{k,\ell}$ to be a permutation with $k$ marks on its bottom line and $\ell$ marks on its top line. The marks are all at distinct positions and do not touch the corners of the permutation. These marks break the bottom (respectively top) line into $k+1$ open interval $P_{-,1},\ldots,P_{-,k+1}$ (respectively $\ell+1$ open interval $P_{+,1},\ldots,P_{+,\ell+1}$).

For example if $k=1,\ell=3$: $$\put(50,-30){$P_{-,1}$}\put(100,-30){$P_{-,2}$}\put(26,25){$P_{+,1}$}\put(60,25){$P_{+,2}$}\put(90,25){$P_{+,3}$}\put(125,25){$P_{+,4}$}
\s_{k,\ell}=\raisebox{-20pt}{\includegraphics[scale=2.5]{P05_Arf/figure/fig_arf_ex1.pdf}}$$

Let $\s_{k,\ell,E'}$ be the permutation obtained by adding a set of edges $E'$ on the marks of permutation $\s_{k,\ell}$ with the following convention: an edge $e\in E'$ is a pair $(i.x,j.y)$. The edge connects the $i$th bottom mark and the $j$th top mark, and it is ordered as the $x$th edge within the bottom mark and the $y$th edge within the top mark. Note that if $i=0$ of $i=k+1$ (likewise of $j$) this implies that the edge is connected to a corner of the permutation.

For example if $k=1,\ell=3$ and $E'=\{(0.1,2.2),(1.1,3.1),(1.2,1.1),(1.3,2.1),(2,1.2)\}$: $$\put(60,-30){$P_{-,1}$}\put(110,-30){$P_{-,2}$}\put(36,25){$P_{+,1}$}\put(70,25){$P_{+,2}$}\put(105,25){$P_{+,3}$}\put(135,25){$P_{+,4}$}
\s_{k,\ell,E'}=\raisebox{-20pt}{\includegraphics[scale=2.5]{P05_Arf/figure/fig_arf_ex2.pdf}}$$ We will define an algorithm that allows one to check if, for all $\s$, we have $\sum^n_{i=1} K_i\Abar(\s_{k,\ell,E^i})=0$ or $\sum^n_{i=1} K_iA(\s_{k,\ell,E^i})=0$ for some $k,\ell,(E^i)_i,(K_i)_i,n.$

\[def.637647\] Let $\s_{k,\ell,E'}$, $P_{-,1},\ldots,P_{-,k+1}$ and $P_{+,1},\ldots,P_{+,\ell+1}$ be as defined above. Then define the $m \times (k+1)(\ell+1)$ matrix valued in $\gf_2$ Q\_[e,ij]{} := {

[ll]{} 1 &\
0 &

. For $v \in \gf_2^{(k+1)(\ell+1)}$, let $|v|$ be the number of entries equal to $1$. Similarly, identify $v$ with the corresponding subset of $[(k+1)(\ell+1)]$. Given such a construction, introduce the following functions on $(\gf_2)^{(k+1)(\ell+1)}$ $$\begin{aligned}
A_{k,\ell,E'}(v)
&:=
\sum_{u \in (\gf_2)^{E'}}
(-1)^{\chi_u + (u,Qv)}
\ef;
&
\Abar_{k,\ell,E'}(v)
&:=
\sum_{u \in (\gf_2)^{E'}}
(-1)^{|u|+\chi_u + (u,Qv)}
\ef.\end{aligned}$$

The construction is illustrated in Figure \[fig.arf\_ex\_def\].

![\[fig.arf\_ex\_def\]The permutation $\s_{1,4,\{(0.1,0.1),(0.2,3.1),(0.3,1.1),(1.1,4.1),(1.2,2.1)\}}$. We cannot show the full matrix $Q$ for such a big example, but we can give one row, for the edge which has the label $e$ in the drawing. The row $Q_e$ reads $(Q_e)_{11, 12, \ldots, 15, 21, \ldots, 25}=(1,1,0,0,0,\,0,0,1,1,1)$.](FigFol/Figure4_fig_arf_ex_def.pdf)

Let us comment on the reasons for introducing such a definition. The quantities $A_{k,\ell,E'}(v)$ (respectively $\Abar_{k,\ell,E'}(v)$) do not depend on $\s$ and allows to sum together many contributions to the function $A(\s_{k,\ell,E'})$. Our goal is to have $E'$ of fixed size, while $E$ (the edge set of $\s$) is arbitrary and of unbounded size, so that the verification of our properties, as it is confined to the matrix $Q$, involves a finite data structure. Thus the algorithm will be exponential in $|E'|$ which will not be a problem for small sizes.

Indeed, let us split in the natural way the sum over subsets $I$ of $E\bigcup E'$ the edge set of $\s_{k,\ell,E'}$ namely $$\sum_{I_0 \subseteq E\bigcup E'} f(I_0)
=
\sum_{I \subseteq E}
\sum_{I' \subseteq E'} 
 f(I \cup I')$$ For $I$ and $J$ two disjoint sets of edges, call $\chi_{I,J}$ the number of pairs $(i,j) \in I \times J$ which do not cross. Then clearly $$\chi_{I \cup J} = \chi_{I} + \chi_{J} + \chi_{I,J}$$ Now let $u(I') \in \{0,1\}^{E'}$ be the vector with entries $u_e=1$ if $e \in I'$ and $0$ otherwise. Let $m(I)=\{m_{ij}(I)\}$ be the $(k+1) \times (\ell+1)$ matrix describing the number of edges connecting the intervals $P_{-,i}$ to $P_{+,j}$ in $\s$, and let $v(I)=\{v_{ij}(I)\}$, $v_{ij} \in \{0,1\}$ be the parities of the $m_{ij}$’s. Call $I_{ij}$ the restriction of $I$ to edges connecting $P_{-,i}$ and $P_{+,j}$. Clearly, $$\chi_{I',I}=\sum_{ij} \chi_{I',I_{ij}} 
= \sum_{e,ij} u_e Q_{e,ij} m_{ij}=(u(I'),Qm(I)),$$ which has the same parity as the analogous expression with $v$’s instead of $m$’s. I.e. we have $$(-1)^{\chi_{I',I}}=(-1)^{(u(I'),Qv(I))}.$$ Now, while the $m$’s are in $\bN$, the vector $v$ is in a linear space of finite cardinality, which is crucial for allowing a finite analysis of our expressions.

As a consequence, $$\begin{aligned}
\label{eq.arf_explain_def}
A(\s_{k,\ell,E^i})
&=
\sum_{I \subseteq E}(-1)^{\chi_I}A_{k,\ell,E'}(v(I))
\ef;
\\\label{eq.arf_explain_def_1}
\Abar(\s_{k,\ell,E^i})
&=\sum_{I \subseteq E}(-1)^{|I|+\chi_I}\Abar_{k,\ell,E'}(v(I))
\ef.\end{aligned}$$

Thus we have the following proposition:

\[prop.ArfProp\]\[prop.Arf0\] Let $k,\ell \in \N$ and let $(E^i)_{1\leq i\leq n}$ be a family of edge set. Then the two following statements are equivalent:

1.  For all $v \in GF_2^{(k+1)(\ell+1)},$ we have $\sum_{i=1}^n K_i A_{k,\ell,E^i}(v)=0$.

2.  for all $\s,$ we have $\sum_{i=1}^n K_i A(\s_{k,\ell,E^i})=0.$

The same statement holds for $\Abar$.

Statement 1 implies 2 due to equation (\[eq.arf\_explain\_def\]).\
Let us show the converse: If $\s$ has no edge then $\sum_{i=1}^n K_i A(\s_{k,\ell,E^i})=0$ is equivalent to $\sum_{i=1}^n K_i A_{k,\ell,E^i}(v)=0$ with $v$ being the zero vector of $(GF_2)^{(k+1)(\ell+1)}$.

Then we choose the family of permutations $(\s^{a,b})_{a,b}$ with exactly one edge connecting $P_{-,a}$ to $P_{+,b}$. Then if we define $v_{a,b}$ to be the vector $(GF_2)^{(k+1)(\ell+1)}$ with exactly one 1 at position $ab$ we have

&\_[i=1]{}\^n K\_i A(\^[a,b]{}\_[k,,E\^i]{})=0\
& \_[i=1]{}\^n K\_i ( A\_[k,,E\^i]{}(0) + A\_[k,,E\^i]{}(v\_[a,b]{})) =0\
& \_[i=1]{}\^n K\_i A\_[k,,E\^i]{}(v\_[a,b]{}) =0\

in the last line we have used that $\sum_{i=1}^n K_i A_{k,\ell,E^i}(0)=0$.

Thus inductively we show that $\sum_{i=1}^n K_i A_{k,\ell,E^i}(v)=0$ for any $v\in (GF_2)^{(k+1)(\ell+1)}$ with at most $p\leq n$ ones.

This theorem is very important since it reduces the problem of calculating Arf identities for permutations of any size to a check of an Arf identity for $2^{(k+1)(\ell+1)}$ values. Thus in exponential time in $k\ell$ we can calculate $A_{k,\ell,E'}(v)$ for every $v \in GF_2^{(k+1)(\ell+1)}$ and decide if a given Arf identity is correct.

We can even do better:

Let $k,\ell \in \N$ and let $(E^i)_{1\leq i\leq n}$ be a family of edge set. We can decide (in exponential time in $k\ell$) if there exists $x_1,\ldots,x_n$ such that $\sum_{i=1}^n x_i A(\s_{k,\ell,E'})=0$.

For every $v$ we have an equation $\sum_{i=1}^n x_i A_{k,\ell,E^i}(v) =0$ with the $n$ unknown variables. So there are $2^{(k+1)(\ell+1)}$ equations. We can find the subspace of solution in time exponential in $k\ell$.

The previous proposition can be used when we suspect a relation between a few configurations without knowing the coefficients. The algorithm demands little more than the previous one for the verification so it remains usable for small $|E'|$.

Finally we can actually enumerate all the possible Arf identities:

There is an algorithm that enumerate all the arf identities with at most $n$ terms and on an edge set $E'$ of size at most $h$.

This algorithm is really not praticable. However it can be used in the following case: we have two terms and we want to find an arf identity relating them to one another but the previous algorithm failed (i.e there are no identity containing only those two terms). Then we use this algorithm to find a third term (or a fourth etc...) for which an identity exists.

We can even propose a generalisation of this framework: let us choose two permutations $\pi_{-}$ and $\pi_{+}$ of size $k+1$ and $\ell+1$ respectively then $\s_{k,\ell,E',\pi_{-},\pi_{+}}$ is obtained from $\s_{k,\ell,E'}$ by permuting the $P_{-,i}$ with $\pi_{-}$ and $P_{+,i}$ with $\pi_{+}$.

For example if $k=1,\ell=3$ and $E'=\{(0.1,2.2),(1.1,3.1),(1.2,1.1),(1.3,2.1),(2,1.2)\}$: $$\put(60,-30){$P_{-,1}$}\put(110,-30){$P_{-,2}$}\put(36,25){$P_{+,1}$}\put(70,25){$P_{+,2}$}\put(105,25){$P_{+,3}$}\put(135,25){$P_{+,4}$}
\s_{k,\ell,E'}=\raisebox{-20pt}{\includegraphics[scale=2.5]{P05_Arf/figure/fig_arf_ex2.pdf}}
\put(130,-30){$P_{-,\pi_{-}1}$}\put(180,-30){$P_{-,\pi_{-}2}$}\put(100,25){$P_{+,\pi_{+}1}$}\put(140,25){$P_{+,\pi_{+}2}$}\put(175,25){$P_{+,\pi_{+}3}$}\put(210,25){$P_{+,\pi_{+}4}$}
\qquad \qquad\s_{k,\ell,E',\pi_{-},\pi_{+}}=\raisebox{-20pt}{\includegraphics[scale=2.5]{P05_Arf/figure/fig_arf_ex2.pdf}}.$$ For an example with $\pi_{-}=id_2$ and $\pi_{+}=(2,1)$ (the reversing permutation $\omega$ at size 2) we have: $$\put(55,-30){$P_{-,1}$}\put(95,-30){$P_{-,2}$}\put(55,25){$P_{+,1}$}\put(85,25){$P_{+,2}$}
\s_{1,1,E'}=\raisebox{-20pt}{\includegraphics[scale=2.5]{P05_Arf/figure/fig_arfproof_s11-eps-converted-to.pdf}}
\put(125,-30){$P_{-,1}$}\put(165,-30){$P_{-,2}$}\put(120,50){$P_{+,2}$}\put(160,50){$P_{+,1}$}
\qquad \qquad\s_{1,1,E',\pi_{-},\pi_{+}}=\raisebox{-20pt}{\includegraphics[scale=2.5]{FigFol/fig_arfproof_general_model_ex.pdf}}$$ It is easily checked that the previous theorems continue to hold for this generalisation once we introduce for $v \in \gf_2^{(k+1)(\ell+1)}$ the following function on $(\gf_2)^{(k+1)(\ell+1)}$ (similar definition for $\Abar_{k,\ell,E',\pi_{-},\pi_{+}}$) $$\begin{aligned}
A_{k,\ell,E',\pi_{-},\pi_{+}}(v)
&:=
\sum_{u \in (\gf_2)^{E'}}
(-1)^{\chi_u + (u,Q(P^{-1}_{\pi_{-}}vP_{\pi_{+}}))}
\ef;\end{aligned}$$ Where in the expression $(P^{-1}_{\pi_{-}}vP_{\pi_{+}})$, $v$ is identified to the matrix of size $(k+1)\times (\ell+1)$ and $P_{\pi_{-}}$ and $P_{\pi_{+}}$ are the permutation matrices associated to $\pi_{-}$ and $\pi_{+}$.

The framework of automatic proofs of Arf identities we have developped is rather general. Most of the identities found in the litterature (see [@KZ03], [@Boi13], [@DS17], [@Del13], [@Gut17]) can be obtained in this setting.

Let us now apply the algorithm to find Arf identities.

It is convenient to introduce the notation $\vec{A}(\s)=\begin{pmatrixsm} \Abar(\s) \\ A(\s) \end{pmatrixsm}$. We have

\[prop.fingerred\] $$\begin{aligned}
\label{prop.signinvdyn}
\Abar\bigg(\,\tau=\raisebox{-12pt}{\includegraphics[scale=1.8]{FigFol/Figure4_fig_arfproof_t1.pdf}}\,\bigg)
&=
\Abar\bigg(\,\s=\raisebox{-12pt}{\includegraphics[scale=1.8]{FigFol/Figure4_fig_arfproof_s1.pdf}}\,\bigg)
\\
\label{eq.546455a}
\vec{A}\bigg(\,
%\tau=
\raisebox{-12pt}{\includegraphics[scale=1.8]{FigFol/Figure4_fig_arfproof_t3.pdf}}\,\bigg)
&=
\begin{pmatrix}
1 & -1 \\ 1 & 1
\end{pmatrix}
\vec{A}\bigg(\,
%\s=
\raisebox{-12pt}{\includegraphics[scale=1.8]{FigFol/Figure4_fig_arfproof_s3.pdf}}\,\bigg)
\ef;
\\
\label{eq.546455b}
\vec{A}\bigg(\,
%\tau=
\raisebox{-12pt}{\includegraphics[scale=1.8]{FigFol/Figure4_fig_arfproof_t4.pdf}}\,\bigg)
&=
\begin{pmatrix}
0 & 0 \\ 0 & 2
\end{pmatrix}
\vec{A}\bigg(\,
%\s=
\raisebox{-12pt}{\includegraphics[scale=1.8]{FigFol/Figure4_fig_arfproof_s3.pdf}}\,\bigg)
\ef;\end{aligned}$$

Clearly equation (\[prop.signinvdyn\]) prove the invariance of the arf invariant for the dynamics since $\s=L(\tau)$ and the case $R$ is deduced by symmetry.

Exceptional classes
===================

In this appendix, when using a matrix representation of configurations, it is useful to adopt the following notation: The symbol $\epsilon$ denotes the $0 \times 0$ empty matrix. The symbol denotes a square block in a matrix (of any size $\geq 0$), filled with an identity matrix. A diagram, containing these special symbols and the ordinary bullets used through the rest of the appendix, describes the set of all configurations that could be obtained by specifying the sizes of the identity blocks. In such a syntax, we can write equations of the like $$\begin{aligned}
\id 
&:=
\raisebox{-1mm}{\includegraphics[width=4.8mm]{FigFol/FigureA2_fig_matr_id.pdf}}
=
\epsilon \cup
\raisebox{-3mm}{\includegraphics[width=8.8mm]{FigFol/FigureA2_fig_matr_Bid.pdf}}
=
\epsilon \cup
\raisebox{5.8mm}{\includegraphics[width=8.8mm,
    angle=180]{FigFol/FigureA2_fig_matr_Bid.pdf}}
\ef;
% \\
% \intertext{and}
&
\id'
&:=
\raisebox{-7mm}{\includegraphics[width=16.8mm]{FigFol/fig_matr_idp.pdf}}
\ef.\end{aligned}$$ The sets $\id$ and $\id'$ contain one element per size, $\id_n$ and $\id'_n$, for $n \geq 0$ and $n \geq 3$ respectively.

The two exceptional classes $\Id_n$ and $\tree_n$ contain the configurations $\id_n$ and $\id'_n$, respectively.

We have the following proposition:

\[pro\_excep\_std\] The permutation $\s=\id_n$ (respectively $\s=\id'_n)$ is the only permutation of $\Id_n$ (respectively $\Id'_n$) with $\s(1)=1$ and $\s(2)=2$.

The structure of the classes $\Id_n$ is summarised by the following relation: := \_n \_n = ( \_[k 1]{} (X\_[RL]{}\^[k]{} X\_[LR]{}\^[k]{} X\_[LL]{}\^[k]{} X\_[RR]{}\^[k]{}) ) where the configurations $X_{\cdot \cdot}^{k}$ are defined as in figure \[fig.struct\_id\] (discard colours for the moment).\

$$\begin{aligned}
X_{LL}^{(k)}
&=
\quad
\makebox[0pt][l]{\raisebox{-16mm}{\includegraphics[width=33mm]{FigFol/FigureA2_fig_matr_CidGen1.pdf}}}
\hspace{-16pt}
\raisebox{-30pt}{$\rotatebox{45}{$k \left\{\rule{0pt}{50pt}\right. $}$}
&
X_{RR}^{(k)}
&=
\makebox[0pt][l]{\raisebox{-16mm}{\includegraphics[width=33mm]{FigFol/FigureA2_fig_matr_CidGen2.pdf}}}
\hspace{28pt}\raisebox{14pt}{$\rotatebox{45}{$\left. \rule{0pt}{50pt}\right\} k $}$}
\\
X_{RL}^{(k)}
&=
\makebox[0pt][l]{\raisebox{-16mm}{\includegraphics[width=38mm]{FigFol/FigureA2_fig_matr_CidGen3.pdf}}}
\hspace{-2pt}
\raisebox{-30pt}{$\rotatebox{45}{$k \left\{\rule{0pt}{50pt}\right. $}$}
&
X_{LR}^{(k)}
&=
\makebox[0pt][l]{\raisebox{-16mm}{\includegraphics[width=38mm]{FigFol/FigureA2_fig_matr_CidGen4.pdf}}}
\hspace{42pt}\raisebox{14pt}{$\rotatebox{45}{$\left. \rule{0pt}{50pt}\right\} k $}$}\end{aligned}$$

We can now prove the lemma \[lem.StFamNotmanyId\_tobeproveninAppC\] that we introduced in section 10.4 !!!!!!!!!.\
This is equivalent to say that there are no pairs of permutations $\s_1, \s_2 \in \Id_n$ which allow for a block decomposition $$\begin{aligned}
\s_1 &= \begin{array}{|c|}
\hline
\rule{5pt}{0pt} 
A 
\rule{5pt}{0pt} 
\\ 
\hline
B \\
\hline
\end{array}
&
\s_2 &= \begin{array}{|c|}
\hline
\rule{5pt}{0pt} 
B
\rule{5pt}{0pt} 
\\ 
\hline
A \\
\hline
\end{array}\end{aligned}$$ If the block $A$ has $\ell$ rows, we say that $\s_2$ is the result of shifting $\s_1$ by $\ell$.

Clearly, at the light of the structure of configurations that we have presented (refer in particular to Figure \[fig.struct\_id\]), this pattern is incompatible with $\s_1$ or $\s_2$ being $\id_n$ (as a non-trivial shift produces a configuration which is not even irreducible), so we have excluded the cases in which, still with reference to the figure, we have only one violet block, and the number of black points is at least 3, for $X^{(k)}_{LL}$ and $X^{(k)}_{RR}$, and at least 4, for $X^{(k)}_{LR}$ and $X^{(k)}_{RL}$. Note that the black points are the positions in the grid which are south-west or north-east extremal (i.e., positions $(i,j) \in \s$ such that there is no $(i',j') \in \s$ with $i'<i$ and $j'<j$, or the analogous statement with $i'>i$ and $j'>j$). Let us call *number of records*, $\rho(\s)$, this parameter. Thus we have that configurations in $X^{(k)}_{LL}$ and $X^{(k)}_{RR}$ have $\rho=2k+1$, and configurations in $X^{(k)}_{LR}$ and $X^{(k)}_{RL}$ have $\rho=2k+2$.

Now, if we perform a shift within one block of consecutive ascents, it is easily seen, by investigation of the sub-configuration at the right of the entry of the new configuration in the bottom-most row, or the one at the left of the entry of the new configuration in the top-most row, that the resulting structure is incompatible with the structure of $\Id$. The same reasoning apply if we perform the shift at the beginning/end of a non-empty diagonal block, which is not the one at the bottom-right/top-left. On the other side, if we perform a shift in any other configuration, we have a new configuration in which $\rho$ has strictly decreased. As $\s_2$ is a non-trivial shift of $\s_1$, and $\s_1$ is a non-trivial shift of $\s_2$, we can thus conclude.
