% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P1.31}{23(1)}{2016}


% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsmath,amsthm,amssymb}
%\usepackage[utf8x]{inputenc}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}



% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% YLB additions
% \usepackage{xcolor}

\usepackage{tikz}
 \usetikzlibrary{arrows,snakes,backgrounds}



% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf On computation of Baker and Norine's rank on complete graphs}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Robert Cori \thanks{The first author acknowledges the support of ERC under the agreement ``ERC StG 208471 - ExploreMap''}\\
\small LaBRI \\[-0.8ex]
\small Universit\'e de Bordeaux\\[-0.8ex] 
\small Talence, France\\
\small\tt cori@labri.fr\\
\and
Yvan Le Borgne \thanks{Part of this work was done in PIMS, Simon Fraser University, Burnaby, Canada}\\
\small CNRS, LaBRI\\[-0.8ex]
\small Universit\'e  de Bordeaux\\[-0.8ex]
\small Talence, France\\
\small\tt borgne@labri.fr
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{May 5, 2014}{Feb 3, 2016}{Feb 19, 2016}\\
\small Mathematics Subject Classifications: 05C88, 05C89}


\newcommand{\rank}{\mathrm{rank}}
\newcommand{\degree}{\mathrm{degree}}
\newcommand{\test}[1]{\chi(#1)}
\newcommand{\area}{\mathrm{area}}
\newcommand{\bounce}{\mathrm{bounce}}
\newcommand{\dinv}{\mathrm{dinv}}
\newcommand{\cdinv}{\mathrm{cdinv}}
\newcommand{\prerankmap}{\theta}
\newcommand{\prerank}{\mathrm{prerank}}
\newcommand{\laplacianconf}[1]{\Delta^{(#1)}}
\newcommand{\topplingequiv}{\equiv_{\Delta}}
\newcommand{\proofs}[1]{\mathrm{Proofs}(#1)}
\newcommand{\park}{\mathrm{park}}
\newcommand{\stabilize}{\mathrm{stabilize}}
\newcommand{\distancedegreedistribution}{\mathrm{ddd}}
\newcommand{\lexorder}{<_{lex}}
\newcommand{\positivedegree}{\degree_{+}}
\newcommand{\diameter}[1]{\delta_{#1}}
\newcommand{\onechipconf}[1]{\epsilon^{(#1)}}
\newcommand{\permutations}[1]{S_{#1}}
\newcommand{\conf}[2]{(#1;#2)}
\newcommand{\compact}{\mathrm{compact}}
\newcommand{\sort}{\mathrm{sort}}
\newcommand{\topplingpermutingequivalent}{\equiv_{\Delta,S_{n-1}}}
\newcommand{\T}{T}
\newcommand{\compactsortedclass}[1]{CS(#1)}
\newcommand{\Titerate}[2]{{#1}^{[{#2}]}}
\newcommand{\shiftmod}{\ \mathrm{mad}\ }
\newcommand{\TK}{K_\T}
\newcommand{\prefixai}[3]{{#1}_{]{#2}_{#3}}}
\newcommand{\dyckToparking}{\mathrm{dyck2parking}}
\newcommand{\YLBnext}{\mathrm{next}}
\newcommand{\cutstrip}[1]{B[#1]}
\newcommand{\leftcutstrip}[1]{L[#1]}
\newcommand{\rightcutstrip}[1]{R[#1]}
\newcommand{\leftcutstriprow}[2]{L_{#1}[#2]}
\newcommand{\E}{E}
\newcommand{\traceuupdate}[1]{\mathrm{traceu}(#1)}
\newcommand{\extralength}{\mathrm{extralength}}
\newcommand{\lrtrace}{\mathrm{lrtrace}}
\newcommand{\substitutionLRToTE}{\pi_{L\rightarrow \E\T^{-1};R\rightarrow \T^{-1}}}
\newcommand{\almostbalancedword}{D}
\newcommand{\cutskewcylinder}[2]{\mathrm{cylinder}[{#1}\circlearrowleft {#2}]}
\newcommand{\leftcutskewcylinder}[2]{L[{#1} \circlearrowleft {#2}]}
\newcommand{\rightcutskewcylinder}[2]{R[{#1} \circlearrowleft {#2}]}
\newcommand{\oriented}[1]{{#1}\uparrow}
\newcommand{\scompact}[4]{\mathrm{scompact}[{#1}\Rightarrow {#2} \circlearrowleft {#3}; {#4}]}
\newcommand{\prefixtoconjugate}[2]{{#1}_{[{#2}}}
\newcommand{\rrinvolutionconf}{\xi}
\newcommand{\reverse}[1]{\tilde{#1}}
\newcommand{\sgrankdegree}{K}
\newcommand{\leftset}[1]{\mathrm{left}[#1]}
\newcommand{\rightset}[1]{\mathrm{right}[#1]}
\newcommand{\sgleftright}{M}
\newcommand{\lefttorightcell}[2]{LR[#1 \circlearrowleft #2]}
\newcommand{\righttoleftcell}[2]{RL[#1 \circlearrowleft #2]}
\newcommand{\nextleftcell}[3]{S_{[#1 \circlearrowleft #2]}(#3)}
\newcommand{\leftcellonrowi}[4]{L_{#3}[#1 \circlearrowleft #2;#4]}
\newcommand{\xpara}{\mathrm{xpara}}
\newcommand{\ypara}{\mathrm{ypara}}
\newcommand{\crossedleftcells}[3]{\mathrm{CL}[#1 \circlearrowleft #2;#3]}
\newcommand{\uncrossedrightcells}[3]{\mathrm{UR}[#1 \circlearrowleft #2;#3]}
\newcommand{\leftpara}[3]{\mathrm{left}[#1\circlearrowleft #2;#3]}
\newcommand{\rightpara}[3]{\mathrm{right}[#1\circlearrowleft #2;#3]}
\newcommand{\monomleftright}[3]{M_{[#1\circlearrowleft #2;#3]}}
\newcommand{\size}{\mathrm{size}}
\newcommand{\X}{\mathbb{X}}
\newcommand{\Y}{\mathbb{Y}}
\newcommand{\height}{h}
\newcommand{\R}{\mathrm{R}}

\begin{document}

\maketitle



\begin{abstract}
 The paper by M. Baker and S. Norine in 2007 introduced a new parameter on configurations of graphs and gave a new result in the theory of graphs which has an algebraic geometry flavor. 
 This result was called Riemann-Roch formula for graphs since it defines a combinatorial version of divisors and their ranks in terms of configurations on graphs.
 The so called chip firing game on graphs and the sandpile model in physics play a central role in this theory.

 In this paper we present an algorithm for the determination of the rank of configurations for the complete graph $K_n$.
 This algorithm has linear arithmetic complexity.
 The analysis of number of iterations in a less optimized version of this algorithm leads to an apparently new parameter which we call the prerank.
 This parameter and the parameter dinv provide an alternative description to some well known $q,t$-Catalan numbers.
 Restricted to a natural subset of configurations, the two natural statistics degree and rank lead to a distribution which is described by a generating function which, up to a change of variables and a rescaling, is a symmetric fraction involving two copies of Carlitz $q$-analogue of the Catalan numbers.

 In annex, we give an alternative presentation of the theorem of Baker and Norine in purely combinatorial terms.%, which is more accessible and shorter than the original one.
 
  % keywords are optional
  %% \bigskip\noindent \textbf{Keywords:} graph reconstruction
  %% conjecture; Broglington manifold; Pipletti's classification
\end{abstract}

\section{Introduction}

On a graph, a configuration is a map from its vertices to the integers of $\mathbb{Z}$.
Motivated by the generalization for graphs of a Riemann-Roch theorem, Baker and Norine~\cite{bakerNorine} defined for any configuration a parameter they called rank.
This parameter is an integer greater or equal to $-1$.
The abelian sandpile model~\cite{bakTang1,dhar1,dharIntro} provides a framework for the original definition of the rank which seems to involve non-trivial computations. 
At submission date of this work, the complexity of the computation of the rank for general graphs was unknown.
Just after, Kiss and T\'othm\'er\'esz announced on arXiv~\cite{kisstothmeresz} their proof for general graphs that computation is NP-hard.
  

The complete graph $K_n$ is the non-oriented graph with $n$ vertices and exactly one edge between any pair of distinct vertices.
We present here an algorithm which computes the rank of a configuration in the particular case of complete graphs.
We prove that our most efficient version has a linear arithmetic complexity where the size of the problem is the number of vertices of the graph.
The design of this algorithm has enumerative byproducts in the context of the rank parameter and also some intensively studied $q,t$-Catalan numbers~\cite{haglund}.
The results in this second context strengthen the connection with the abelian sandpile model as in recent work involving one of the authors~\cite{DukesLeBorgne,ADDHL}.

Let $G=(V_G,E_G)$ be an non-oriented connected simple graph without loops and with vertex set $V_G$ and edge set $E_G$.
Baker's and, Norine's theorem~\cite{bakerNorine} states that for any configuration $u=(u_i)_{i\in V_G}\in \mathbb{Z}^{|V_G|}$ of $G$,  
$$ \rank(u) - \rank(K_G-u) = \degree(u) + |E_G| - |V_G| $$
where the cardinality of a set $E$ is denoted by $|E|$; the definition of the parameter $\rank$ is still postponed to the preliminaries in Section~\ref{sec:naive-algo}; the configurations are seen as vectors allowing additions and subtractions; the degree of the configuration $u$ is $\degree(u):=\sum_{i\in V_G} u_i$; the configuration $K_G:=(k_i)_{i\in V_G}$ is defined by $k_i := d_i-2$ where $d_i$ is the degree of the vertex $i$ which is its number of incident edges. In this context, a configuration is called a divisor but we prefered to use the abelian sandpile model terminology.
This paper focus on the particular case where $G$ is a complete graph $K_n$: we use the integers $1,2,\ldots n$ to label the vertices $V_{K_n}$ of the complete graph $K_n$; the configuration $K_{K_n} = (k_i)_{i=1\ldots n}$ satisfies $k_i=n-3$ for all $i$.

The two next sections are dedicated to the design of our main algorithm which computes the rank of a configuration on $K_n$.
Section~\ref{sec:naive-algo} focus on correctness of a first version of the algorithm.
We use the numerous symmetries of the complete graphs to obtain a greedy algorithm computing the rank.
The complexity of this version is not clear but the aim of Section~\ref{sec:optimised-algo} is to optimize this algorithm.
We select a particular run of this non-deterministic first algorithm to reach the announced complexity while preserving the correctness.
The optimization requires to work at the level of orbits of a subgroup of symmetries.
The toppling equivalence, an additional equivalent relation on configurations based on the sandpile model framework, shows that one can efficiently reduce the computation to the case of a sorted parking configuration.
The configuration $u$ is a sorted parking configuration if $0 \leq u_i < i$ for $i < n$ and $u_1\leq u_2 \leq \ldots \leq u_{n-1}$.
Notice that there is no constrain on the value of $u_n$.
If we had used the divisor terminology, we may called this configuration a sorted $n$-reduced divisor.
The optimized algorithm computes the rank via the following rather explicit expression for the rank of a sorted parking configuration $u$ in $K_n$:
$$ \rank(u) = \left(\sum_{i=1}^{n-1}\max(0,q-i+u_i+\test{i\leq r}) \right)-1.$$
where $u_n+1 = q(n-1)+r$ is the euclidean division defining the quotient $q$ and the non-negative remainder $r$, and $\test{P}$ is $1$ if the proposition $P$ is true and $0$ otherwise. 


The second optimized algorithm still manipulates the configurations as vectors.
Yet the proof that it corresponds to a run of the first algorithm deeply relies on another coding of some configurations.
These configurations on $K_n$ may be encoded by a Dyck word of size $n-1$ and one or two integers depending on its additional properties. 
A word $v$ on the two-letter alphabet $\{a,b\}$ is a Dyck word of size $n$ if $|v|_a=|v|_b=n$ and for any prefix $p$ of $v$, $|p|_a \geq |p|_b$ where $|v|_c$ denotes the number of occurrences of letter $c$ in the word $v$.   
This data is embedded in a cut skew cylinder to make use of a cyclic symmetry.
The skew cylinder of circumference $n$ is an already known slight variation of the usual $\mathbb{Z}\times \mathbb{Z}/(n-1)\mathbb{Z}$ cylinder, for example already presented by Kramers and Wannier~\cite{kramersWannier} in 1941. 
The main interest of this skew is that it merges the usually ``parallel'' finite cycles interpreting $\mathbb{Z}/(n-1)\mathbb{Z}$ into a single infinite spiral traversal isomorphic to $\mathbb{Z}$.
A cut of this skew cylinder is a self-avoiding directed cycle made up of north and east steps disconnecting the cylinder into two components.
A classical cyclic lemma due to Dvoretsky and Motzkin~\cite{dvoMotzk} implies that any cut may be defined by the choice of a Dyck word of size $n-1$ and a starting vertex.
One interest of this change of encoding is that computation on configurations becomes simpler updates of the Dyck word or the integers.
After all, our optimized algorithm on the configuration $u=(u_i)_i$ may be interpreted as a spiral traversal of $u_n+1$ cells on a related cut skew cylinder counting the occurrences of cells in one of the two components defined by the cut.


In Section~\ref{sec:rank-byproducts}, we describe as follows the generating function 
$$ K_n(r,d) := \sum_{u} r^{\rank(u)}d^{\degree(u)} = \frac{d^{{n-1 \choose 2}}}{rd}M_n(\frac{1}{d},rd)$$
where $u$ runs over \emph{sorted} parking configurations on $K_n$ and $M_n(x,y)$ is the coefficient of $z^{n-1}$ in
$$ \mathbb{M}(x,y;z) := \frac{1-xy}{(1-x)(1-y)}\frac{C(x;xz)+C(y;yz)-C(x;xz)C(y;yz)}{1-C(x;xz)zC(y;yz)}$$
where $C(q;z)$ is a classical Carlitz $q$-analogue of Catalan numbers counting the Dyck words according to size via the variable $z$ and the later defined area via the variable $q$.
The formula for $\mathbb{M}(x,y;z)$ comes from the decomposition, on each cut skew cylinder, of the spiral traversal at crossings of the cut,  leading to geometric sums of reasons $x$ or $y$. 
If the sum in $K_n(r,d)$ were not restricted to sorted parking configurations, we would have reached a two-variable zeta function for graphs introduced recently by Lorenzini~\cite{lorenzini}.
We provide a combinatorial interpretation of the generating function $M_n(x,y)$ in terms of cut skew cylinders.
Those cut skew cylinders admits an natural involution $\rrinvolutionconf$ which roughly speaking consists in reversing the spiral traversal.
This involution also explains via a superimposition principle why $M_n(x,y) = M_n(y,x)$.
In addition, this involution is related to the involution on configurations $u\rightarrow K_{K_n}-u$ appearing in Riemann-Roch theorem for graphs. 

In Section~\ref{sec:qt-byproducts}, we study connections of this work with $q,t$-Catalan numbers presented for example by Haglund in~\cite{haglund}. 
These $q,t$-Catalan numbers $(C_n(q,t))_{n\in\mathbb{N}}$ may be combinatorialy described by some pairs of statistics on a generic Dyck word $w$ chosen among the later defined $\area(w)$, $\bounce(w)$ and $\dinv(w)$:
$$C_n(q,t) := \sum_{w} q^{\area(w)}t^{\dinv(w)} = \sum_{w} q^{\area(w)}t^{\bounce(w)}$$
where $w$ runs over Dyck words of size $n$.
The symmetry $C_n(q,t)=C_n(t,q)$ is obvious once non-trivially proven equivalent to some alternative definitions. 
There is still no combinatorial explanation of this symmetry \cite{Haglund2}. 
In this context,Haglund designed an involution $\zeta$ on Dyck words which satisfies for any Dyck word $w$:
$$ (\dinv(w),\area(w)) = (\area(\zeta(w)),\bounce(\zeta(w)))$$
establishing combinatorially the equivalence of the two presented definitions of $C_n(q,t)$.
Our involution $\rrinvolutionconf$ on cut skew cylinders may be canonically restricted to Dyck words and this restriction also called $\rrinvolutionconf$. 
It appears that $\dinv(\rrinvolutionconf(w))=\dinv(w)$.
An early optimization of our algorithm computing the rank leads us to the apparently new parameter $\prerank(w)=\area(\rrinvolutionconf(w))$.
Hence we have 
$$ C_n(q,t) = \sum_w q^{\dinv(w)}t^{\prerank(w)} $$
where $w$ runs of Dyck words of size $n$.
There is also a relation between the maps $\zeta$ and $\rrinvolutionconf$:
$$ \zeta \circ \rrinvolutionconf = \R \circ \zeta $$
where $\R(w)$ classically maps the Dyck word $w$ to its reverse word where each occurrence of $a$ is replaced by $b$ and conversely.
  
  
\section{A first greedy algorithm \label{sec:naive-algo}}

In our preliminaries, we recall classical properties of the abelian sandpile model and
 Baker's and, Norine's definition of the rank parameter.
We then prove the correctness of our first version of a greedy algorithm computing the rank for a configuration in a complete graph.
 
\subsection{Preliminaries}

%\subsubsection{Notations for the abelian sandpile model} 
Let $G$ be a non-oriented connected graph without loops and where multiple edges are allowed.
We denote by $V=\{1,2,\ldots n\}$ where $n=|V|$ the vertex set of $G$ and $E$ its edge set.
The number of edges of $E$ between the vertices $i$ and $j$ is denoted by $e_{i,j}$.
Hence the \emph{degree $d_i$ of the vertex} $i\in V$ is $\sum_{j\in V} e_{i,j}.$
A \emph{configuration} $u=(u_i)_{i\in V}$ is a vector of $\mathbb{Z}^n$: the possibly negative number of grains $u_i$ is placed on vertex $i$ in configuration $u$.
Since a configuration $u$ is a vector we can add or subtract configurations: the configuration $w=u-v$ is defined by $w_i=u_i-v_i$ for any vertex $i$.
The \emph{degree of the configuration} $u$ is $\degree(u) := \sum_{i\in V} u_i$.
In the abelian sandpile model, the \emph{toppling of the vertex $i$} in configuration $u$ consists in sending from the vertex $i$ one unit along each incident edge to the opposite endpoint of the edge. 
These amounts of one unit are also called \emph{grains}. 
This leads to the configuration $u'=u-\laplacianconf{i}$ where $\laplacianconf{i}_i := d_i$ and $\laplacianconf{i}_j := -e_{i,j}$ otherwise.
This toppling is $\emph{legal}$ if $u_i \geq d_i$ ensuring that $u'_i\geq 0$ and $u'_j \geq u_j$ for any $j\neq i$.
In this paper non legal topplings are sometimes allowed. 
The toppling of vertex $i$ preserves the degree of any configuration since $\degree(\laplacianconf{i})= 0$.
Two configurations $u$ and $v$ are \emph{toppling equivalent} if they differ by a finite combination of topplings:
$$ u \topplingequiv v :=  \exists (a_i)_{i\in V}\in \mathbb{N}^n,\  u = v-\sum_{i\in V} a_i\laplacianconf{i}$$  
The symmetry of this equivalence relation comes from the relation $\sum_{i\in V}\laplacianconf{i} = 0$ which allows to use $-\laplacianconf{i} = \sum_{j\neq i} \laplacianconf{i}$ to change signs in the combination. 

%\subsubsection{Definition of the rank}

We mainly summarize with our notation the definition of the rank presented by Baker and Norine in \cite{bakerNorine}.
A configuration $u$ is \emph{positive}, also denoted $u\geq 0$, if $u_i\geq 0$ for any vertex $i$. 
A configuration $v$ is \emph{effective} if $v$ is toppling equivalent to a positive configuration: $\exists u, v\topplingequiv u,\mbox{ and } u\geq 0$.
The \emph{rank} of the configuration $u$ is defined by the following optimization:
$$ \rank(u) := -1 + \min_f \degree(f) $$
where $f$ runs over all positive configurations such that $u-f$ is non-effective. 
An optimal choice $f$ for the computation of $\rank(u)$ is called a \emph{proof} for the rank of $u$.
The set of such proofs is denoted by  $\proofs{u}$.

The test that a configuration $u$ is effective is a first difficulty in this description of the rank since naively it may require to run over the infinite set of all configurations toppling equivalent to $u$.
Hopefully, one can limit the test to a canonical configuration in the class of toppling equivalence: the $n$-parking configuration of $u$ denoted $\park(u)$ which will be defined below.\footnote{It corresponds to the notion of $n$-reduced divisor.}

\begin{lemma}[\cite{bakerNorine},see also Proposition~\ref{prop:eff_on_park} in annex]\label{lem:eff_on_park}
We have $u$ effective if and only if $\park(u)$ is positive.
\end{lemma}

The definition of these $n$-parking configurations requires additional notions.
By convention the vertex $n$ is distinguished and called the \emph{sink}.
A vertex $i$ in configuration $u$ is \emph{unstable} if $u_i \geq d_i$ where $d_i$ is the degree of the vertex $i$ in $G$. 
A configuration $u$ is \emph{stable outside the sink} if any vertex $i\neq n$ is stable.
A configuration $u$ is \emph{positive outside the sink} if for any vertex $i\neq n$, $u_i\geq 0$.
This is also denoted by $u\geq_{\neq n} 0$.
A subset of vertices $A$ is \emph{set-unstable} in a configuration $u$ if $A$ is non-empty, $n\notin A$ and, in the configuration $u'=u-\sum_{a\in A} \laplacianconf{a}$, we have $u'_a \geq 0$ for any $a\in A$.   
In other words, $A$ is set-unstable if the toppling of all the vertices of $A$ leads to a configuration whose restriction to $A$ is positive.
If $A$ is a singleton $\{ i \}$, $A$ is set-unstable if and only if $i$ is unstable and hence the toppling of $i$ is legal.
A configuration $u$ is \emph{set-stable} if there is no subset of vertices set-unstable in $u$.  
A configuration $u$ is \emph{$n$-parking}, also shorten in \emph{parking}, if $u$ is stable and positive outside the sink and set-stable.
We refer to the literature \cite{dharIntro} for a proof that any configuration $u$ is toppling equivalent to exactly one $n$-parking configuration.  
This property implies that the parking configuration $\park(u)$ toppling equivalent to the configuration $u$ is well-defined.
There exists many algorithms to compute the map $u\rightarrow \park(u)$ on any graph.
A recent one is due to Baker and Shokrieh~\cite{bakerShokrieh}.
We will use the existence of such an algorithm in this section but in Section~\ref{sec:optimised-algo} we will design a most efficient one in the case of the complete graphs.

The \emph{stabilization process} of the configuration $u$ consists in toppling one unstable vertex distinct from the sink $n$ while there exists at least one.  
A key classical property of the abelian sandpile model~\cite{dharIntro} is that this stabilization process terminates on a configuration denoted  $\stabilize(u)$ which is stable outside the sink and do not depend on the hence unspecified order in which the unstable vertices are toppled.




\subsection{A first greedy algorithm computing the rank on complete graphs}

From now on we assume that $G$ is a complete graph $K_n$ with $n\geq 2$.
Let $\onechipconf{i}$ be the configuration with $\onechipconf{i}_i=1$ and for $j\neq i$, $\onechipconf{i}_j=0$.
We consider the following greedy algorithm where the variable $g$ is a configuration on $K_n$:

\begin{center}
\begin{minipage}{15cm}
\framebox{\bf First greedy algorithm for the rank}:\newline
{\bf Input:} A configuration $u$ on $K_n$\newline
 $u \leftarrow \park(u)$; $rank \leftarrow -1$; $g\leftarrow 0$;\newline
While $u_n\geq 0$ do let $i\neq n$ such that $u_i=0$ in $u\leftarrow \park(u-\onechipconf{i})$; $g\leftarrow g+\onechipconf{i}$;od;
{\bf Output:} rank ($=\rank(u)$) and $g$ ($\in \proofs{u}$).
\end{minipage}
\end{center}

\begin{proposition}[Correctness of the rank algorithm]\label{prop:correctness-rank} Given any configuration $u$ on $K_n$, the greedy naive algorithm for the rank terminates and returns $\rank(u)$ in the variable $rank$ and the configuration variable $g\in \proofs{u}$ is a proof of this rank.
\end{proposition}

The postponed proof of this proposition requires two main proofs: one for the existence of some vertex $i\neq n$ such that $u_i=0$ in any parking configuration and another one that $g$ is a proof for $\rank(u)$.
The second proof relies on the combination of the two following lemmas: the first is related on symmetries of the complete graph $K_n$ while the other, more general, is probably folklore.

\begin{lemma}[Greedy choice for rank's proof on $K_n$]\label{lem:greedy-choice} Let $u$ be a positive configuration on the complete graph $K_n$ such that there exists a vertex $i$ for which $u_i=0$.
Then there exists a proof $g\in\proofs{u}$ for the rank of $u$ such that $g_i>0$. 
\end{lemma} 

\begin{lemma}[Subproof for the rank]\label{lem:subproof-rank}
Let $u$ be a configuration on any graph $G$ and $i$ a vertex of $G$.
Assume there is a proof $g$ for the rank of $u$ such that $g_i >0$. 
Then any proof $f'$ for the rank of $u'=u-\onechipconf{i}$ leads to a proof $f=f'+\onechipconf{i}$ of the rank of $u$. 

\end{lemma}

The possibility in our algorithm of a greedy choice for finding a proof for the rank comes from the numerous symmetries of the complete graph.
Let $\sigma$ be a generic permutation of the set $\permutations{n}$ of permutations on elements of $\{1,2,\ldots n\}$.
The action of $\sigma$ on a configuration $u=(u_i)_{i=1\ldots n}$ is defined by $\sigma.u := (u_{\sigma(i)})_{i=1\ldots n}$.
We gather in the following lemma properties related to symmetries used in this section but also later:


\begin{lemma}[Symetries on $K_n$ and the rank]\label{lem:symetries}
Let $u$ and $v$ be any configuration on $K_n$ and $\sigma$ any permutation of $\permutations{n}$.
We have :
\begin{enumerate}
\item $u$ positive $\iff$ $\sigma.u$ positive,
\item $u\topplingequiv v$ $\iff$ $\sigma.u \topplingequiv \sigma.v$,
\item $u$ effective $\iff$ $\sigma.u$ effective,
\item $g \in \proofs{u}$ $\iff$ $\sigma.g \in \proofs{\sigma.u}$,
\item $\rank(\sigma.u) = \rank(u)$,
\item If $\sigma(n)=n$ (or with a slight abuse of notation $\sigma \in \permutations{n-1}\subset \permutations{n}$) then:
\begin{enumerate} 
\item $u$ positive outside the sink $\iff$ $\sigma.u$ positive outside the sink, 
\item $u$ set-stable $\iff$ $\sigma.u$ set-stable, 
\item $u$ parking $\iff$ $\sigma.u$ parking.
\item $\park(\sigma.u) = \sigma.\park(u)$
\end{enumerate}
\end{enumerate} 
\end{lemma}

Now we listed the required lemmas to prove the correctness of the algorithm, we use another schedule to prove them. 


\begin{proof}(of Lemma~\ref{lem:symetries}: Symmetries on $K_n$ and the rank)

$(1)$ is straightforward. 
We remark that $\sigma$ acts also nicely on the configurations $\laplacianconf{i}$, hence $u= v-\sum_{i} a_i \laplacianconf{i} \iff \sigma.u=\sigma.v-\sum_{i} a_i\laplacianconf{\sigma(i)}$.
This remark leads to $(2)$; 
$(1)$ and $(2)$ imply $(3)$.


The following paragraph proves $(4)$.
If $g\in \proofs{u}$ then $u-g$ is non-effective and for any positive configuration $f$ such that $\degree(f) < \degree(g)$, $u-f$ is effective. 
From $(3)$ we deduce that $\sigma.u-\sigma.g$ is non-effective and for any positive configuration $f$ such that $\degree(f) < \degree(g)$, $\sigma.u-\sigma.f$ is effective.
Since $\{f|f\geq 0,\degree(f) < \degree(g)\} = \{\sigma.f|\sigma.f\geq 0, \degree(\sigma.f)<\degree(\sigma.g)\}$ we deduce that $\sigma.g\in \proofs{\sigma.u}$. Conversely, for the opposite implication of $(4)$ we use similarly $\sigma^{-1}$, the inverse permutation of $\sigma$.

$(4)$ implies $(5)$.
The proof of $(6.(a))$ is similar to the proof $(1)$ and the proof of $(6.(b))$ to the proof of $(2)$: the single additional remark is that the sink vertex $n$ is simultaneously excluded from the set-unstable set of vertices and a fix-point of $\sigma\in \permutations{n-1} \subset \permutations{n}$. 
$(6.(a))$ and $(6.(b))$ imply $(6.(c))$.
We have $\park(u)=u-\sum_{i} a_i\laplacianconf{i}$ hence like in the proof of $(2)$, $\sigma.\park(u) = \sigma.u - \sum_{i} a_i\laplacianconf{\sigma(i)}$ where $\sigma.\park(u)$ is parking according to $(6.(c))$ and toppling equivalent to $\sigma.u$ hence $\park(\sigma.u)=\sigma.\park(u)$.  
\end{proof}


\begin{proof}(of Lemma~\ref{lem:greedy-choice} Greedy choice for rank's proof on $K_n$)

Let $f\in \proofs{u}$. 
If $f_i > 0$ then $g=f$ concludes the proof.
In the remaining case, we have $f_i=0$. 
Since $f$ is a proof, $u-f$ is non-effective hence there exists a vertex $j$ such that $u_j-f_j <0$.
We have $j\neq i$ since $u_i-f_i=0-0$.
We will show that $g=f+(f_j-u_j)(\onechipconf{i}-\onechipconf{j})$ is the expected proof for the rank of $u$.
By definition,  $g_i=f_j-u_j > 0$ and more generally $g$ is positive and $\degree(g)=\degree(f)$.
Hence it simply remains to show that $u-g$ is non-effective.
We consider $u'=u-f+(f_j-u_j)\onechipconf{j}.$
Let $\sigma=(ij)$ the transposition of $\permutations{n}$ which exchanges $i$ and $j$: $\sigma(i)=j$, $\sigma(j)=i$ and otherwise $\sigma(k)=k$.
By definition  $u'_j=u_j-f_j+(f_j-u_j)=0$ and $u'_i=0-0=0$, so $\sigma.u' = u'$.
Hence:
$$ \sigma.(u-g) = \sigma.(u-f-(f_j-u_j)(\onechipconf{i}-\onechipconf{j}))=\sigma.(u'-(f_j-u_j)\onechipconf{i}) = u'-(f_j-u_j)\onechipconf{j} = u-f.$$
Using $ \sigma.(u-g) = u-f$ and  $(3)$ in lemma~\ref{lem:symetries} we deduce as expected that like $u-f$, $u-g$ is non-effective. 
\end{proof}




\begin{proof}(of Lemma~\ref{lem:subproof-rank} Subproof for the rank)
Let $g$ a proof of $u$ such that $g_i >0$ and $f'$ a proof of $u'=u-\onechipconf{i}$.
On one hand,  $u'-f'=u-(f'+\onechipconf{i})$ is non-effective so by definition of $g$, $\degree(f')+1 \geq \degree(g)$.
On the other hand,  $u'-\onechipconf{i})=u-g$ is non-effective and $g-\epsilon^{(i)}$ is positive so by definition of $f'$ $\deg(g)-1 \geq \deg(f')$.
Joining these hands, $\degree(f')=\degree(g)-1$.
Since $f=f'+\onechipconf{i}$ is of degree $\degree(g)$ and  $u-f=u'-f'$ is non effective, $f$ is a proof for the rank of $u$. 
\end{proof}

\begin{proof}(of Proposition~\ref{prop:correctness-rank} Correctness of the rank algorithm)

First, if $u$ is a parking configuration on $K_n$ there exists a vertex $i$ distinct from the sink such that $u_i=0$.
Indeed we obtain a contradiction if for any $i\neq n$, $u_i \neq 0$. 
Since $u$ is positive outside of the sink, it means that $u_i\geq 1$.
Hence $A=\{1,2,\ldots n-1\} = V-\{n\}$ is a set-unstable set.
This is in contradiction with the assumption that $u$ is parking.


We conclude the proof of correctness by an induction on the rank of the given configuration $u$.
If $\rank(u) = -1$, the configuration $u$ is non-effective so, according to Lemma~\ref{lem:eff_on_park}, $\park(u)$ has a negative value on the sink then the algorithm skips the while-loop and returns $rank=-1$ and $g=0$ as expected.
Let $m\geq 0$.
We assume that the algorithm is correct on any given configuration of rank at most $m-1$.
Let $u$ be a configuration of rank $m$, $v=\park(u)$ and $i$ the first chosen vertex by the algorithm such that $v_i=0$.
Lemma~\ref{lem:greedy-choice} on the greedy choice for the rank implies the existence of a proof $g$ for the rank of $u$ such that $g_i>0$ and so $g-\onechipconf{i}$ is positive.
Since $v-g = (v-\onechipconf{i}) - (g-\onechipconf{i})$ is non-effective, the rank of $v-\onechipconf{i}$ is at most $m-1$.
Our inductive assumption implies that the algorithm applied to $v-\onechipconf{i}$ leads to a proof $f$ of its rank.
Applying Lemma~\ref{lem:subproof-rank} about subproofs for the rank, the configuration $f+\onechipconf{i}$ is a proof for the rank of the given $u$.
This is also the value in the variable $g$ at the end of the run given the configuration $u$. 
\end{proof}

% SKIPPED Discussion on complexities

\section{An algorithm of linear arithmetic complexity\label{sec:optimised-algo}}

In this section we optimize the correct greedy naive algorithm.
Subsection~\ref{subsec:compact-sorted} explains how to restrict quickly the algorithms to the manipulation of configurations soon defined and called compact and sorted.
Subsection~\ref{subsec:conf2skcyl} motivates this restriction by a bijection between these compact and sorted configurations and pointed cut skew cylinders.
This second class of combinatorial objects may be encoded by a Dyck word and one up to three integers.
In the algorithms computing the rank or the parking configurations, atomic updates or tests on configurations admits more regular interpretations in terms of pointed cut skew cylinders.
Subsection~\ref{subsec:formula-rank} translates a possible run of the algorithm for the rank into a simple partial spiral traversal in the cut skew cylinder.
The analysis of this traversal leads to an explicit formula for the rank of a sorted and parking configuration based on a single euclidean division.
Subsection~\ref{subsec:searchparking} describes an algorithm adapted to the complete graph to find the parking configuration toppling equivalent to any given configuration.
We conclude this section by discussing the details of a possible implementation in linear arithmetic complexity of an algorithm computing the rank of any configuration on $K_n$.

\subsection{Restriction to compact and sorted configurations} \label{subsec:compact-sorted}

The distinguished sink $n$ on $K_n$ implies that we frequently manipulate configurations where the sink is the only particular case.
We often abbreviate a configuration $u=(u_1,\ldots u_n)$ into $(u_i;u_n)$ which means implicitly that the variable $i$, part of the notation, runs from $1$ to $n-1$. 
Our next definition illustrates this notation.

The \emph{compacted} configuration $u^c$ of $u$ is the configuration 
$$\compact(u) := u^c :=  ( (u_i-u_n)\mod n;\degree(u)-\sum_{i=1}^{n-1} u^c_i).$$ 
In other words, for $i=1\ldots n-1$, $u^c_i := (u_i-u_n)\mod n$ and for $i=n$, $u^c_n:=\degree(u)-\sum_{i=1}^{n-1} u^c_i$. 

\begin{lemma}\label{lem:compact}(Compact configuration on $K_n$)
For any configuration $u$ on $K_n$, we have $\compact(u) \topplingequiv u$.
\end{lemma}

\begin{proof}
On one hand, we topple $u_n$ times each vertex different from the sink in the configuration $u$ to obtain
$$ u \topplingequiv (u_i;u_n)-\sum_{j=1}^{n-1}u_n\laplacianconf{j} = (u_i-u_n;nu_n).$$
On the other hand, by definition of $u^c:=\compact(u)$ there exists $(k_1,\ldots,k_{n-1})\in \mathbb{Z}^n$ such that for $i\neq n$, $u_i-u_n=u^c_i+k_in$.
Joining the hands, $u\topplingequiv (u^c_i+k_in;nu_n)$.
Then we consider
$$ (u^c_i+k_in;nu_n)-\sum_{j\neq n} k_j(\laplacianconf{j}-\laplacianconf{n}) = (u_i^c;nu_n-n\sum_{j\neq n}k_j) = (u^c_i;\degree(u)-\sum_{j\neq n} u^c_j)$$
where $k_i(\laplacianconf{i}-\laplacianconf{n})$ cancels $k_in$ in $u_i^c+k_in$ and $\degree(u)$ is introduced using that topplings preserve the degree of configurations. 
The rightmost term is the preceding sequence of equalities is $\compact(u)$ which is hence proved to be toppling equivalent to $u$.  
\end{proof}

This definition of $\compact(u)$ particular to the complete graphs is inspired by a work on general graphs of Dhar, Ruelle and, Verma~\cite{dharRuelleVerma}.
One find similar ideas also in~\cite{bakerShokrieh}.
We observe that $\compact(u)$ can be quickly computed, it is positive and stable outside of the sink but not necessarily equal to  $\stabilize(u)$.

A configuration $u$ on $K_n$ is \emph{compact} if $$\max_{i\neq n,j\neq n}|u_i-u_j|\leq n.$$

It is straightforward that the configuration $\compact(u)$ is compact.
Moreover, most of the configurations appearing in the optimized algorithms are compacts.

Another aspect of the optimization consists in working at the level of orbits under the action of $\permutations{n-1}\subset \permutations{n}$ permuting the vertices $1,2,\ldots n-1$ distinct from the sink.
The representative of the orbit of $u$ will be the defined below $\sort(u)$ sorted configuration.
A configuration $u$ is \emph{sorted} if $u_1,\ldots u_{n-1}$ is weakly increasing: for $i=2\ldots n-1$, $u_{i-1}\leq u_i$.
Notice that there is no constraint on $u_n$.
The configuration $\sort(u)$ is obtained by sorting in weakly increasing order of the first $n-1$ entries of the configuration $u$.

We also combine the action of $S_{n-1}$ and the toppling equivalence.
Two configurations $u$ and $v$ on $K_n$ are \emph{toppling and permuting equivalent}, denoted $u\topplingpermutingequivalent v$ if there exists a permutation $\sigma\in \permutations{n-1}\subset\permutations{n}$ such that $u$ and $\sigma.v$ are toppling equivalent.

\begin{lemma}(compatibilities for toppling and permuting equivalence)\newline\label{lem:sortedparking}$(1).$ The relation $\topplingpermutingequivalent$ is an equivalence relation.\newline
$(2).$ Moreover, for any configuration $u$, there exists a unique sorted and parking configuration $v := \sort(\park(u))$ toppling and permuting equivalent to $u$.
\end{lemma}

\begin{proof}
$(1).$ The relation is symmetric mainly according to the second of the following equivalences:
\begin{align}
    u \topplingpermutingequivalent v & \iff \exists \sigma\in \permutations{n-1},\exists(a_i)_i\in \mathbb{Z}, \sigma.u = v-\sum_{i=1}^n a_i\laplacianconf{i} \nonumber\\
    &\iff \exists \sigma\in \permutations{n-1},\exists(a_i)_i\in \mathbb{Z}, \sigma^{-1}.v = u-\sum_{i=1}^n (-a_{\sigma^{-1}(i)})\laplacianconf{\sigma^{-1}(i)} \nonumber\\
    &\iff v \topplingpermutingequivalent u \nonumber
  \end{align}
The transitivity of the relation comes from the composition of permutations. Let $\sigma.u=v-\sum_{i=1}^n a_i\laplacianconf{i}$ and $\tau.v = w - \sum_{i=1}^n b_i\laplacianconf{i}$ then
$$ (\tau \circ \sigma).u = w - \sum_{i=1}^n (b_i-a_{\tau^{-1}(i)})\laplacianconf{i}.$$


$(2).$ The existence of a sorted parking configuration toppling and permuting equivalent to $u$ is straightforward since by definition $\sort(\park(u))$ is such a configuration. 

Our proof of the uniqueness considers two configurations $u$ and $v$ toppling and permuting equivalent.
By assumption, there is a permutation $\sigma\in \permutations{n-1}$ such that $\sigma.u$ is toppling equivalent to $v$.
The uniqueness of the parking configuration in a toppling equivalent class implies that $\park(\sigma.u)=\park(v)$.
Using the identity $6.(d)$ of Lemma~\ref{lem:symetries} on symmetries of $K_n$, we deduce that $\sigma.\park(u)=\park(v)$ hence $\sort(\park(u))=\sort(\park(v))$ as expected.
\end{proof}


\subsection{From sorted and compact configurations to pointed cut skew cylinders \label{subsec:conf2skcyl}}

The parking configurations on the complete graph $K_n$ admits a more explicit description which explains the adjective parking.
A \emph{parking function} of size $n$ is a map $f$ from $\{1,2,\ldots n\}$ to $\mathbb{Z}$ such that  for $i=1\ldots n-1$, $f(i)\geq 0$ and for $j=1\ldots n$, $|\{i|f(i) \geq  j\}| \leq n-j$. 
%The existence of a superunstable set in a configuration positive outside of the sink on $K_n$ admits the following translation\cite{}.
It was already noticed in~\cite{coriRossin} that a configuration $u$ on $K_n$ is parking if and only if $f$ defined by $(f(i))_{i=1\ldots n-1} := (u_i)_{i=1\ldots n-1}$ is a parking function of size $n-1$.
We already observed that $u$ is parking if and only if $\sigma.u$ where $\sigma\in S_{n-1}\subset S_n$, in particular $\sort(u)$, is parking.
Sorting simplifies the checking: a sorted configuration $u$ is parking if and only if for $i=1\ldots n-1$, $0\leq u_i < i$.


Until now, we manipulated the configurations as vectors in $\mathbb{Z}^n$.
We introduce an alternative description of sorted and compact configurations on $K_n$ which will simplify our analysis.
This description requires some (painful but then rewarding) preliminaries.


\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.9]
\draw (-8, 0) grid (9, 5.2);
\foreach \s/\x/\y/\color in {40/-7/0/black,46/-7/1/black,52/-7/2/black,58/-7/3/black,64/-7/4/black,70/-7/5/blue,35/-6/0/black,41/-6/1/black,47/-6/2/black,53/-6/3/black,59/-6/4/black,65/-6/5/blue,30/-5/0/black,36/-5/1/black,42/-5/2/black,48/-5/3/black,54/-5/4/black,60/-5/5/blue,25/-4/0/black,31/-4/1/black,37/-4/2/black,43/-4/3/black,49/-4/4/black,55/-4/5/blue,20/-3/0/black,26/-3/1/black,32/-3/2/black,38/-3/3/black,44/-3/4/black,50/-3/5/blue,15/-2/0/black,21/-2/1/black,27/-2/2/black,33/-2/3/black,39/-2/4/black,45/-2/5/blue,10/-1/0/black,16/-1/1/black,22/-1/2/black,28/-1/3/black,34/-1/4/black,40/-1/5/blue,5/0/0/black,11/0/1/black,17/0/2/black,23/0/3/black,29/0/4/black,35/0/5/blue,0/1/0/black,6/1/1/black,12/1/2/black,18/1/3/black,24/1/4/black,30/1/5/blue,1/2/1/black,7/2/2/black,13/2/3/black,19/2/4/black,25/2/5/blue,2/3/2/black,8/3/3/black,14/3/4/black,20/3/5/blue,3/4/3/black,9/4/4/black,15/4/5/blue,4/5/4/black,10/5/5/blue,5/6/5/blue,0/7/5/blue}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\s$}};
}
\foreach \s/\x/\y/\color in {5/2/0/black,10/3/0/black,4/3/1/black,15/4/0/black,9/4/1/black,3/4/2/black,20/5/0/black,14/5/1/black,8/5/2/black,2/5/3/black,25/6/0/black,19/6/1/black,13/6/2/black,7/6/3/black,1/6/4/black,30/7/0/black,24/7/1/black,18/7/2/black,12/7/3/black,6/7/4/black,35/8/0/black,29/8/1/black,23/8/2/black,17/8/3/black,11/8/4/black,5/8/5/blue,40/9/0/black,34/9/1/black,28/9/2/black,22/9/3/black,16/9/4/black,10/9/5/blue}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\overline{\s}$}};
}
% blue cut
\draw[line width=2,draw=blue] (-1,0) -- (-1,1) -- (0,1) -- (0,3) -- (1,3) -- (1,4) -- (3,4) -- (3,5) -- (5,5);
\draw[line width=1,draw=blue,dashed] (-1,0) -- (4,5);
% magenta cut: TODO
\draw[line width=2,draw=magenta] (1,0) -- (1,1) -- (2,1) -- (2,2) -- (5,2) -- (5,4) -- (7,4) -- (7,5);
\draw[line width=1,draw=magenta,dashed] (5,2) -- (8,5);
\draw[line width=1,draw=magenta,dashed] (2,0) -- (4,2);
% green segment
\foreach \y/\i in {3/1,4/2} {
\draw[line width=2,draw=green,->] (-1,\y) -- (-1,\y+1);
\draw node[green] at (-1.5,\y+.5) {\small{$a_{\oriented{28}\i}$}};
}
\foreach \y/\i in {0/3,1/4,2/5} {
\draw[line width=2,draw=green,->] (-7,\y) -- (-7,\y+1);
\draw node[green] at (-7.5,\y+.5) {\small{$a_{\oriented{28}\i}$}};
}
% red segment
\foreach \y/\i in {0/1,1/2,2/3,3/4,4/5} {
\draw[line width=2,draw=red,->] (-3,\y) -- (-3,\y+1);
\draw node[red] at (-3.5,\y+.5) {\small{$a_{\oriented{20}\i}$}};
}
% orange segment
\foreach \y/\i in {0/1,1/2,2/3,3/4,4/5} {
\draw[line width=2,draw=orange,->] (9,\y) -- (9,\y+1);
\draw node[orange] at (8.5,\y+.5) {\small{$a_{\oriented{\overline{40}}\i}$}};
}
\end{tikzpicture}
\caption{Skew cylinder of circumference $6$, two of its cuts and three oriented segments.\label{fig:defscompact}} 
\end{center}
\end{figure}

The \emph{skew cylinder} of circumference $n$ is a kind of skewed two dimensional grid embedded in a cylinder.
A first precise definition considers the quotient of the usual grid of $\mathbb{Z}^2$ where each vertex of integer coordinates $(x,y)$ admits the four neighbours $\{(x+1,y),(x-1,y),(x,y+1),(x,y-1)\}$ by the equivalent relation $(x,y) \equiv (x',y')$ if there exists $k\in\mathbb{Z}$ such that $(x',y')=(x+kn,y+k(n-1))$.
A possible notation for this is $\mathbb{Z}^2/(n,n-1)\mathbb{Z}$.   
We fix our notation on a second precise and more explicit definition of skew cylinder which has the drawback to partially hide the invariance by translation. 
This definition is illustrated by the example in Figure~\ref{fig:defscompact}.
The \emph{strip} of $n-1$ rows is the subgraph of the usual two dimensional grid $\mathbb{Z}^2$ induced by the vertices $\{(x,y)| x\in \mathbb{Z}, 0 \leq y \leq n-1\}$.
The  two-dimensional of \emph{cell} coordinates $(x,y)\in\mathbb{Z}^2$ is the unit square which corners are $\{(x,y),(x-1,y),(x-1,y+1),(x,y+1)\}$.
In other words the two-dimensional coordinates of a cell are the coordinates of its south-east corner.
For a cell $c$ we denote by $(x(c),y(c))$ its two-dimensional coordinates. 
We will use the \emph{spiral coordinate} as an alternative coordinate for the cells of the strip.
The cell of two dimensional coordinate $(0,0)$ is labeled by the spiral coordinate $0\in\mathbb{Z}$, then we label the cells, incrementing the spiral coordinate, from south-west to north-east in the cells along the diagonal in north-east direction, then the next diagonal is the next on the west.
This \emph{spiral traversal} labels all the cells of spiral coordinate $k\in \mathbb{N}$.
In Figure~\ref{fig:defscompact}, the spiral coordinate of each cell is indicated by the small number written in the south-west corner.
Negative coordinate $-x$ is written $\overline{x}$ for graphical purpose. 
This number is blue for partial cells in the top row and means that these are repetitions of the cells on the bottom row.
In the opposite direction and starting from the cell $(0,0)$, the reversed spiral traversal labels all the cells with a non-positive spiral coordinate.     
Hence, this spiral traversal defines a bijection between the cells of the strip of $n-1$ rows and $\mathbb{Z}$.
We frequently use the cell (of spiral coordinate) $k\in \mathbb{Z}$ and the vertex (of spiral coordinate) $k$ which is the south-east corner of this cell $k$.
A more operational description is that the cell of two dimensional coordinates $(x,y)$ in the strip has spiral coordinate $ny-(n-1)x$ and the cell of spiral coordinate $k\in\mathbb{Z}$ has two dimensional coordinates $(r-q,r)$ where $k=q(n-1)+r$ is the euclidean division of $k$ by $n-1$. 
We turn this strip into the skew cylinder of circumference $n$ by an identification of the vertices of coordinates $(x,0)$ and $(x+n,n-1)$ which implies that the south side of the cell $(x,0)$ is also the north side of the cell $(x+n-1,n-2)$.  


In a word $w$, we denote by $|w|_x$ the number of occurrences of the letter $x$.
An \emph{almost balanced word} of size $n$ is a word on the alphabet $\{a,b\}$ such that $|w|_a=n-1$ and $|w|_b=n$.
Let $\almostbalancedword_n$ denotes the set of almost balanced words of size $n$.


Given a vertex $k\in \mathbb{Z}$ in the skew cylinder of circumference $n$ and a word $w$ on the two-letter alphabet $\{a,b\}$, the \emph{embedding of the word $w$ at vertex $k$} is the \emph{path} starting from vertex $k$ and such that an occurrence of letter $a$ in $w$ corresponds to a unit north step and an occurrence of letter $b$ to a unit east step. 
The \emph{cell of a north step} in such a path is the cell whose east side is the north step.   


We first observe that the embedding at vertex $m\in\mathbb{Z}$ of an almost balanced word $w\in\almostbalancedword_n$ in the skew cylinder of circumference $n$ also ends at vertex $m$.
This defines a (self-avoiding) loop that we call a \emph{cut}.
The resulting \emph{cut skew cylinder} is denoted by $\cutskewcylinder{m}{w}$.
In Figure~\ref{fig:defscompact}, the blue path is a cut defining $\cutskewcylinder{10}{abaababbabb}$ and the magenta path is a cut defining $\cutskewcylinder{2}{bbaabbaabab}=\cutskewcylinder{-3}{baabbaababb}$.



\begin{definition}
A cut skew cylinder $\cutskewcylinder{m}{w}$ and two additional integers $k\in\mathbb{Z}$ and $s\in\mathbb{Z}$ allow the definition of a configuration on $K_n$
$$ \scompact{k}{m}{w}{s} := (u_i;u_n) = (x(a_i)-x(a_{\oriented{k}i});s)$$
where the $a_{\oriented{k}i}$ for $i=1\ldots n-1$ are the $n-1$ north steps of the \emph{oriented segment} which is the embedding of the word $a^{n-1}$ at vertex $k$, and $a_i$ is the north step of the cut on $\cutskewcylinder{m}{w}$ which crosses the same row as the north step $a_{\oriented{k}i}$ and $x(.)$ is the first coordinate of the two-dimensional coordinates of the starting vertex of a step.
\end{definition}

In Figure~\ref{fig:defscompact}, there are three oriented segments: the red one starts from $20$, the orange one from $-40$ and the green one from $28$.
The last one is drawn into two green lines since it visits the two copies of the vertex $40$.
The red oriented segment, the blue cut and the integer $39$ define the configuration 
$$ \scompact{20}{10}{abaababbabb}{39} = (2,3,3,4,6;39)$$ 
$$= (x(10)-x(20),x(11)-x(26),x(17)-x(32),x(18)-x(38),x(14)-x(44);39).$$

The properties of the description $\scompact{k}{m}{w}{s}$ require additional preliminary definitions.

Two cells are connected in a cut skew cylinder if they share a common side which is  not  a step of the cut.
In the cut skew cylinder $\cutskewcylinder{m}{w}$ there are two connected components of cells: the \emph{left component} $\leftcutskewcylinder{m}{w}$, which contains the cell $m$, and the other called the \emph{right component} $\rightcutskewcylinder{m}{w}$.
A cell is \emph{left} if it belongs to $\leftcutskewcylinder{m}{w}$ and \emph{right} otherwise.

A \emph{Dyck word} of size $n$ is a word $w$ on the two-letters alphabet $A=\{a,b\}$ where for any prefix $p$ of $w$, $|p|_a\geq |p|_b$ and in addition $|w|_a=|w|_b=n$.
Any factorization $w=w'w''$ defines a cyclic conjugate $v=w''w'$ of the word $w$.
The classical cyclic lemma due to Dvoreztky and Motzkin~\cite{dvoMotzk} states that among the $2n-1$ distinct cyclic conjugates of an almost balanced word $w\in \almostbalancedword_n$ exactly one may be written $vb$ where $v$ is a Dyck word of size $n-1$. 
We recover this lemma in our setting.
In Figure~\ref{fig:defscompact}, a dashed line indicates the Dyck factor $abaababbab$ respectively $aabbaababb$ in the cyclic conjugate for the blue, respectively magenta, cut.
A first indication is that pairs $(w,s)$ where $w$ is a Dyck word of size $n-1$ and $s\in\mathbb{Z}$ are in classical bijection with sorted parking configurations on $K_n$ as follows.
$$ (u_i;u_n) = (\sum_{j=1}^i k_j;s) \leftrightarrow (w,s) = (ab^{u_2-u_1}ab^{u_3-u_2}\ldots ab^{u_{n-1}-u_{n-2}}ab^{n-1-u_{n-1}},u_n)$$
where\footnote{Remark that $k_1=0$ and $u_1=0$} $w=b^{k_1}ab^{k_2}ab^{k_3}\ldots ab^{k_n}$.
This bijection translates the fact that in a sorted parking configuration $u$ we have $0\leq u_i <i$ for $i=1\ldots n-1$ into the fact that $w$ is a Dyck word. 
Another classical notion for an non-empty Dyck word $w$ is its non-ambiguous \emph{decomposition at first return} $w=afbg$ where $f$ and $g$ are both possibly empty Dyck words. 

We define the map $\T$ on sorted configurations on $K_n$:
$$ \T.u :=\sort(u-\laplacianconf{n-1})$$
and the map $\E$ on sorted \emph{parking} configurations on $K_n$ which corresponds to the subtraction of one unit on a vertex with value $0$ in the configuration:
$$ \E.u := u-\onechipconf{1}.$$

\begin{proposition}(From sorted compact configurations to pointed cut skew cylinders)\label{prop:convert}\ 
\begin{enumerate}
\item A configuration $u$ on $K_n$ is sorted and compact if and only if there exists a word $w\in \almostbalancedword_n$ and three integers $(k,m,s)\in\mathbb{Z}^3$ such that $u=\scompact{k}{m}{w}{s}$.
\item For any factorization $w=w'w''$ of $w\in \almostbalancedword_n$ we have $$\cutskewcylinder{m}{w'w''} = \cutskewcylinder{m+n|w'|_a-(n-1)|w'|_b}{w''w'}.$$
\item For any $p\in\mathbb{Z}$, we have 
$$ \scompact{k}{m}{w}{s} = \scompact{k+p}{m+p}{w}{s}.$$
\item The map $(v,k,s)\rightarrow \scompact{k}{0}{vb}{s}$ defines a bijection between  the triplets made up of a  Dyck word $v$ of size $n-1$ and two integers $(k,s)\in\mathbb{Z}^2$ and the sorted and compact configurations on $K_n$.

Moreover, the sorted and compact configurations toppling and permuting equivalent to $\scompact{k}{0}{vb}{s}$ are exactly the configurations $(\scompact{k+r}{0}{vb}{s-r})_{r\in\mathbb{Z}}$.

\item The restriction of $\T$ to sorted and compact configurations is well-defined and reversible. 
Moreover we have 
$$ \T.\scompact{k}{m}{w}{s} = \scompact{k-1}{m}{w}{s+1}$$
and for any sorted and compact configuration $u$ on $K_n$ we have 
$$ \T^{1-n}.u = u - \laplacianconf{n}.$$
\item The configuration $\scompact{k}{m}{w}{s}$ is parking if and only if $k=\min \leftcutskewcylinder{m}{w}$ where we use the spiral coordinate for cells of $\leftcutskewcylinder{m}{w}$.
Moreover
$$ \park(\scompact{k}{m}{w}{s}) = \T^{k-\min \leftcutskewcylinder{m}{w}}.\scompact{k}{m}{w}{s}$$
$$=\scompact{\min\leftcutskewcylinder{m}{w}}{m}{w}{s+k-\min \leftcutskewcylinder{m}{w}}.$$
\item The map $(v,s)\rightarrow \scompact{0}{0}{vb}{s}$ defines a bijection between the pairs made up of a Dyck word $v$ of size $n-1$ and one integer $s\in \mathbb{Z}$ and the sorted and parking configurations on $K_n$.
%% \item Let $v=av'$ be a Dyck word of size $n-1$ and $(m,s)\in \mathbb{Z}^2$. 
%% For the parking configuration $u=\scompact{m}{m}{av'b}{s}$ we have 
%% $$ \E.u = \scompact{m}{m+n-1}{bv'a}{s}$$
%% and moreover
%% $$ \leftcutskewcylinder{m+n-1}{bv'a} = \leftcutskewcylinder{m}{av'b}-\{m\}.$$ 
\item Let $u=\scompact{m}{m}{vb}{s}$ and $v=afbg$ be the factorization at first return of the Dyck word $v$ and $j=\min (\leftcutskewcylinder{m}{vb}-\{m\})$ the second smallest spiral coordinate of a left cell, we have 

$$ \sort(\park(\E.u)) = \scompact{j}{j}{gabfb}{s-(j-m)}$$

where $gabf$ is a Dyck word and moreover
$$ \leftcutskewcylinder{j}{gabfb} = \leftcutskewcylinder{m}{vb}-\{m\}.$$
\end{enumerate}
\end{proposition}


\begin{proof}
$1.$  If $u=(u_i;u_n)$ is a sorted and compact configuration, let $m=0$, $k=(n-1)u_1$, $s=u_n$ and 
$w=ab^{u_2-u_1}ab^{u_3-u_2}ab^{u_4-u_3}\ldots ab^{u_{n-1}-u_{n-2}}ab^{n-(u_{n-1}-u_1)}\in D_n.$
By definition, we have $u=\scompact{k}{m}{w}{s}$.
Conversely, given $w\in D_n$ and $(m,k,s)\in\mathbb{Z}^3$. 
Let $k=q(n-1)+r$ be the euclidean division of $k$ by $n-1$ and factorize $w$ as $w=b^{k_1}ab^{k_2}ab^{k_3}\ldots ab^{k_{n}}$. 
By definition we have $u=\scompact{k}{m}{w}{s}$ which is also defined by $u_n=s$ and $u_i=q+\sum_{j=1}^{i}k_j$.
Hence $u$ is sorted and $u_{n-1}-u_1=\sum_{j=2}^{n-1} k_j \leq n$ so $u$ is also compact.

$2.$ Moving the start of the cut along the first step does not modify the cut skew cylinder. 
This remark leads to either $\cutskewcylinder{m}{aw'} = \cutskewcylinder{m+n}{w'a}$ or $\cutskewcylinder{m}{bw'} = \cutskewcylinder{m-(n-1)}{w'b}$. 
Iterations of these two rules leads to the expected claim.

$3.$ Two equal translations of the cut and the oriented segment preserve the pairs $(a_i,a_{\oriented{k}i})$ and their differences $x(a_i)-x(a_{\oriented{k}i})$ hence proves the claim.

$5.$ (see $4.$ below) Let $u$ be a sorted and compact configuration. 
First we compute explicitly 
$$\begin{array}{ll}
v := \T.u & = \sort((u_1+1,u_2+1,\ldots u_{n-2}+1,u_{n-1}-(n-1);u_n+1)) \\
\ & = (u_{n-1}-(n-1),u_1+1,u_2+1,\ldots u_{n-2}+1;u_n+1)\\
\end{array}$$ 
where $\sort$ induces the cyclic permutation $\tau$ of the $n-1$ first entry sending $n-1$ to $1$, since $u_{n-1}-(n-1)\leq u_1+1$ because $u$ is compact.
Moreover $v_{n-1}-v_1=u_{n-2}+1-u_{n-1}+(n-1) \leq n$ so $v$ is also compact.
The inverse of the cyclic permutation $\tau$ is well defined and also the inverse of the toppling of $n-1$ which corresponds to the toppling of all vertices distinct from $n-1$.
The reader may then check that the inverse $\T^{-1}$ of $\T$ is the expected composition of these two inverses, {\it ie} $\T^{-1}.v=u$.

According to $1.$, let $(k,m,w,s)$ such that $u=\scompact{k}{m}{w}{s}$.
Inspection shows that $\scompact{k-1}{m}{w}{s+1}=v=\T.u$.

During the computation of $\T^{1-n}=(\T^{-1})^{n-1}$, the fact that $\tau^{-1}$ is cyclic implies that each vertex distinct from the sink $n$ is toppled $n-2$ times and the sink $n$ is toppled $n-1$ times.
Since toppling $n-2$ times each vertex does not change the configuration and $\tau^{1-n}$ is the identity we deduce that $\T^{1-n}$ is equivalent to one toppling of the sink $n$ as claimed.

$6.$ First we suppose that $u$ is parking.
The cells at west of the oriented segment $(a_{\oriented{k}i})_{i=1\ldots n-1}$ are $(k+n(i-1))_{i=1\ldots n-1}$.
We consider the vector $(l_i)_{i=1\ldots n-1}$ where $l_i$ is the minimal spiral coordinate of a cell in the left component of $\leftcutskewcylinder{m}{w}$ on the same row as $a_{\oriented{k}i}$.
Hence by definition of $\scompact{k}{m}{w}{s}$, we have for $i\neq n$,  $u_i=\frac{k+n(i-1)-l_i}{n-1}$.
The configuration $u$ is sorted and parking so we have $u_i<i$.
This is equivalent to $\frac{k+n(i-1)-l_i}{n-1} <i \iff l_i > k-1 \iff l_i \geq k$.
Moreover, $u_1=0$ so $k=l_1\in \leftcutskewcylinder{m}{w}$ and $k=\min \leftcutskewcylinder{m}{w}$.

Conversely, we suppose that $k=\min \leftcutskewcylinder{m}{w}$.
The cut is made of east or south steps so $k\in \leftcutskewcylinder{m}{w}$ implies recursively via the north sides of cells that $k+n(i-1) \in \leftcutskewcylinder{m}{w}$ for $i=1,\ldots, n-1$.
Combined with the backward equivalences of the previous argument we have $k \leq l_i \leq k+n(i-1)$ and so $0\leq u_i <i$.
So $u$ is a sorted parking configuration.

The power of $\T$ in the description of $\park(\scompact{k}{m}{w}{s})$ is chosen so that, in the resulting configuration, the oriented segment starts at the vertex in the south-east corner of the cell $\min \leftcutskewcylinder{m}{w}$. 
This choice is correct by uniqueness of the toppling and permuting equivalent sorted and parking configuration. 


$7.$ Let $u=\scompact{k}{m}{w}{s}$ be a parking configuration. 
According to $6.$, $k=\min \leftcutskewcylinder{m}{w} \in \leftcutskewcylinder{m}{w}$.
Hence the cell $k-(n-1)$ sharing the vertical east side of the cell $k$ belongs to $\rightcutskewcylinder{m}{w}$.
So this vertical side is a step of the cut of $\cutskewcylinder{m}{w}$ and according to $2.$ there exists a cyclic conjugate $w'$ of $w$ and $k'\in \mathbb{Z}$  such that  $u =\scompact{k'}{k'}{w'}{s}$.
According to $3.$, we have $u=\scompact{0}{0}{w'}{s}$.
We have $\min \leftcutskewcylinder{0}{w'}=0$ so the cells $(-i)_{i=1\ldots n-1}$ belong to $\rightcutskewcylinder{0}{w'}$.
This implies that $w'=vb$ where $v$ is a Dyck word of size $n-1$.

Conversely, if $u=\scompact{0}{0}{vb}{s}$ where $v$ is a Dyck word of size $n-1$, then $\min \leftcutskewcylinder{0}{vb} = 0$ so $u$ is sorted and parking.   
    
The map $(v,s)\rightarrow \scompact{0}{0}{vb}{s}$ is obviously injective. 
Hence this map is the expected bijection. 

$4.$ Let $u$ be a sorted and compact configuration and $u'=\sort \circ \park(u)$.
According to $6.$, there exists $m\in \mathbb{Z}$ such that $u=\T^m.u'$.
According to $8.$, $u'=\scompact{0}{0}{vb}{s}$ where $v$ is a Dyck word of size $n-1$ and $s\in\mathbb{Z}$ and the pair $(v,s)$ is unique.
Hence, according to $5.$, $u=\T^m.\scompact{0}{0}{vb}{s}=\scompact{m}{0}{vb}{s-m}$.
The observation of the value on the sink $n$ shows that all sorted and compact configurations $(\scompact{m}{0}{vb}{s-m})_{m\in \mathbb{Z}}$ are distinct and toppling and permuting equivalent to $u'$ and also $u$.
 
$8.$ 
By definition, $m=\min \leftcutskewcylinder{m}{afbgb}$.
Inspection shows that the explicit occurrence of the letter $b$ in the factor $afb$ corresponds to the south side of the cell $j$. 
Hence $j=m+|afb|_a$ and the vertex $j$ belongs to the cut.
Changing the start of the cut from $m$ to $j$, we also have $u=\scompact{m}{j}{gbafb}{s}$.
By definition the occurrence of the letter $a$ in $gbabfb$, appears in the definition of $u_1$.
Hence the commutation of this occurrence of $a$ with the preceding occurrence, which is necessarily a letter $b$, has two consequences.
First, exactly $u_1$ is decremented by one, leading to the sorted and compact configuration $\E.u = \scompact{m}{j}{gabfb}{s}$. 
Second, the left cell $m$ in $\scompact{m}{j}{gbafb}{s}$ becomes a right cell in $\scompact{m}{j}{gabfb}{s}$ since the cut visiting the south and east side of cell $m$ in the first case, visits the west and north side of this cell after the commutation.
As expected, we have $\leftcutskewcylinder{j}{gabfb}=\leftcutskewcylinder{m}{afbgb}-\{m\}$.    
Moreover, after the deletion of the smallest value $m$, the second smallest value $j$ becomes minimal: $\min \leftcutskewcylinder{j}{gabfb}=j$.
By application of $6.$, we deduce that $\sort(\park(\E.u))=\T^{m-j}.\E.u= \scompact{j}{j}{gabfb}{s-(j-m)}$.
\end{proof}

\subsection{An explicit formula for the rank of sorted parking configurations on $K_n$\label{subsec:formula-rank}}


We describe a possible run of our correct first greedy algorithm for the rank presented in Section~\ref{sec:naive-algo} combined with the action of the symmetric group $S_{n-1}\subset S_n$.
In a sorted parking configuration $u$, we necessarily have $u_1=0$ which will be our systematic choice of $i\neq n$ such that $u_i=0$.
Hence a possible run of the correct algorithm on parking configurations in terms of the sorted configurations is 
\begin{center}
\begin{minipage}{15cm}
\framebox{\bf Algorithm selecting a run for the rank on sorted configurations:}\newline
{\bf Input:} A sorted parking configuration $u$ on $K_n$\newline
$rank \leftarrow -1$; \newline
While $u_n\geq 0$ do $u\leftarrow \sort(\park(\E.u))$; $rank\leftarrow rank+1$; od; \newline 
{\bf Output:} $rank (=\rank(u))$
\end{minipage}
\end{center}

This run is tightly related to the following spiral traversal of some cells of the cut skew cylinder such that $u=\scompact{m}{m}{vb}{s}$. 
We define $\nextleftcell{m}{vb}{s}=\min\{ s'| s'> s\mbox{ and } s'\in \leftcutskewcylinder{vb}{s}\}$ which is the minimal spiral coordinate strictly greater than $s$ of a left cell in $\cutskewcylinder{m}{vb}$. 




\begin{center}
\begin{minipage}{15cm}
\framebox{\bf Algorithms for the rank via a spiral traversal on a cut skew cylinder:}\newline 
{\bf Input:} A sorted parking configuration $u=\scompact{m}{m}{vb}{s}$ on $K_n$.\newline
$rank = \leftarrow -1$;\newline
For $k$ from $m$ to $F(u)$  do\newline
\_\_\_\_ if $k$ is a left cell $(k\in \leftcutskewcylinder{m}{vb})$ then $rank\leftarrow rank+1$; od;\newline
{\bf Output:} $rank (=\rank(u))$.
\end{minipage}
\end{center}

\begin{center}
\begin{figure}[ht!]
 \begin{tikzpicture}[scale=0.55]
 \draw[black!30!white] (0,0) grid (10, 10);
\draw[->,line width = 1,dashed] (0,0) -> (10, 10);
\draw[->, line width = 1,dashed,blue] (0, -1) -> (0,12);

\draw[->,line width = 1,dashed,blue] (-4, 0)--(11, 0);
\foreach \x/\fx in {0/0,1/0,2/0,3/1,4/1,5/1,6/4,7/7,8/7,9/9}{
\draw node at (\x+0.5,12+1) {$\fx$};}
\draw node at (11, 13){\tikz{\draw[line width = 2] (0,0) circle (0.3);\draw node at (0,0) {$26$};}};

\foreach \x/\fx/\fnx in {0/0/0,0/1/0,0/2/1,1/3/1,1/4/1,1/5/4,4/6/7,7/7/7,7/8/9,9/9/10}{
\draw[blue,line width=2] (\x,\fx) -- (\x,\fx+1);
\draw[blue,line width=2] (\x,\fx+1) -- (\fnx,\fx+1);
}
%\draw[blue,line width=0,opacity=0.15,fill=blue] (\x,0) rectangle (\fx+1, \x);
\draw[black!30!white](-4,0) grid (0, 10);
\foreach \x/\y/\color/\currentsink in {0/0/green/0,1/1/white/1,2/2/white/2,3/3/white/3,4/4/white/4,5/5/white/5,6/6/white/6,7/7/green/7,8/8/white/8,9/9/green/9,0/-1/green/10,1/0/green/11,2/1/white/12,3/2/white/13,4/3/white/14,5/4/white/15,6/5/white/16,7/6/green/17,8/7/green/18,9/8/green/19,0/-2/green/20,1/-1/green/21,2/0/green/22,3/1/green/23,4/2/white/24,5/3/white/25,6/4/green/26}{
\draw node[black] at (\y-0.5,\x+0.5) {\small $\currentsink$};
}
 \foreach \x/\y in {0/0,7/7,9/9,0/-1,1/0,7/6,8/7,9/8,0/-2,1/-1,2/0,3/1,6/4}{
\draw[opacity=0.6,fill=green,draw=green] (\y-0.5,\x+0.5) circle (0.4);
}

\foreach \x/\rx in {1/3,2/2,3/1,4/1,5/0,6/0,7/1,8/2,9/1,10/2}{
\draw[green!50!brown] node at (12,\x-0.1,) {$\rx$}; 
}
\draw[green!50!brown] node at (12,-0.5) {$=13$};

\draw[line width=0.7] (10,7) -- ( -4.8,7);
\draw[->,line width=2] (-5,0) -> (-5,7);
\draw node at (-6.2,3.5) {$R=7$};
\draw[->,line width=2] (10,10.6) -> (7,10.6);
\draw node at (8.5,11.5) {$Q=2$};
\end{tikzpicture}
\caption{Calculation of the rank on a Dyck path}
 \label{fig:calcRank}
 
 \end{figure}
\end{center}



We use two versions of this algorithm corresponding to the two distinct definitions of $F(u)$.
If $F(u):=\nextleftcell{m}{vb}{m+s}-1$, it defines the \emph{extended spiral traversal for the rank}.
If $F(u):=m+s$, it defines the \emph{shortest spiral traversal for the rank}.
In Figure~\ref{fig:calcRank}, we labeled the cells visited by the shortest spiral traversal for the rank of 
$$u=(0,0,0,1,1,1,4,7,7,9;26)=\scompact{0}{0}{aaabaaabbbabbbaabbabb}{26}.$$
The $14$ visited cells in the left component contains a green disk so the returned value for the rank is $13$. 
These two versions of the spiral traversal produce exactly the same values since all the additional cell visited in the extended version belongs to the right component by definition of $\nextleftcell{m}{vb}{m+s}$.  
The extended spiral is closer to the algorithm selecting a run for the rank while the shortest spiral induces more symmetries in the forthcoming the enumerative studies.




This paragraph consider the connection between the extended spiral traversal for the rank and the selected run on sorted configurations for the rank.
We discuss the beginning of this spiral traversal, if any.
If $s<0$, then $\nextleftcell{m}{vb}{m+s} \leq m$ so there is no loop iteration and the output $rank=-1$ as expected.
Otherwise, let $j=\nextleftcell{m}{vb}{m}$.
We consider the iterations for $k$ from $m$ to $j-1$.
It visits $j-m$ cells $m$,$m+1$,\ldots $j-1$ where $m$ is a left cell and all other cells are right while $j$ is the next left cell.
This part may be interpreted as the computation of $\sort(\park(\E.u))=\scompact{j}{j}{gabfb}{s-(j-m)}$ as described by $8.$ in Proposition~\ref{prop:convert}: move via operator $\E$ the left cell $m=\min \leftcutskewcylinder{m}{vb}$ to the right component, increment the rank, then visit via operator $\T^{-1}$ all the $j-m$ cells starting at $m$ in spiral order until you find the next left cell $j=\min \leftcutskewcylinder{j}{gabfb}$.
In addition, the value of $s$ is decremented at each visit of a cell so we have $\nextleftcell{m}{vb}{m+s}=\nextleftcell{j}{gabfb}{j+s}$.
Hence, by induction, we observe that this traversal simulates the run of the sorted version of the correct algorithm.

\begin{proposition}(Reading a proof for the rank using spiral traversals)\\
Let $u=\scompact{m}{m}{vb}{s}$ be a sorted parking configuration.
The extended spiral traversal for the rank on $\cutskewcylinder{m}{vb}$ returns $\rank(u)$.
\end{proposition}

\begin{proof}
The discussion preceding this proposition shows that the correct algorithm on sorted configurations with input $u$ is simulated by the traversal algorithm  on $\cutskewcylinder{m}{vb}$ so that both return $\rank(u)$.  
\end{proof}

We recall that by definition all the cells of spiral indices from $m+s+1$ to $\nextleftcell{m}{vb}{s}-1$, if any, are right cells so the extended and shortest spiral traversals, which differs only by these cells, returns the same value.   
We can also recover from the shortest traversal a proof $g$ for the rank of the sorted parking configuration $u=\scompact{m}{m}{vb}{s}$.
For a cut skew cylinder and $i=1\ldots n-1$ we define the set  $\leftcellonrowi{m}{vb}{i}{s}$  of left cells of spiral coordinate at most $m+s$ and on the same row as the step related to $a_{\oriented{m}i}$ the $i$-th step of the oriented segment $a^{n-1}$ starting at $m$.

\begin{proposition}(Reading a proof for rank in spiral traversals) \label{prop:read-proof}
Let $u=\scompact{m}{m}{vb}{s}$ be a sorted parking configuration on $K_n$.
The configuration $g=(g_i;g_n) := (|\leftcellonrowi{m}{vb}{i}{s}|;0)$ is a proof for $\rank(u)$.
\end{proposition}

\begin{proof}
In the correspondence between the selected run on sorted configurations and the extended traversal, a grain $\epsilon^{(i)}$ is removed on the vertex $i$ each time a cell of the row related to $u_i$ is moved from the left to the right component.
All such left cells are the left cells in $\leftcutskewcylinder{m}{vb}$ of spiral coordinate between $m$ and $m+s$ since between $m+s+1$ and $m+\nextleftcell{m}{vb}{m+s}-1$ there are only right cells, if any.
When those cells are partitioned into rows, it corresponds exactly to the definition of $\leftcellonrowi{m}{vb}{i}{s}$.
Hence $g_i$ count the number of removed grains on vertex $i$ during the algorithm so $g$ is a proof for the rank of $u$ according to the sorted version of the correct greedy naive algorithm.
\end{proof}

It appears that the  $(|\leftcellonrowi{m}{vb}{i}{s}|)_{i=1\ldots n-1}$ may be efficiently computed via a single euclidean division.

\begin{theorem}\label{theo:rank-formula}(Formula for the rank of a sorted parking configuration)
Let $u$ be a sorted parking configuration on $K_n$ and $u_n+1 = q(n-1)+r$ the euclidean division of $u_n+1$ by $n-1$.
$$ \rank(u) = \left(\sum_{i=1}^{n-1} \max(0,q-i+1+u_i+\test{i\leq r} \right)-1 $$
and the proof for the rank found from the algorithm selecting a run for the rank by collecting removed grains is   
$$ g = (\max(0,q-i+1+u_i+\test{i\leq r};0).$$
\end{theorem}

\begin{proof}
Let $u=\scompact{m}{m}{vb}{s}$ with $s=u_{n}$.
In this proof, we consider that the visited cells during the traversal algorithm are exactly the cells with spiral coordinate from $m$ to $m+s$, if any.
It means that we deliberately ignore the cells of spiral coordinates from $m+s+1$ to $m+\nextleftcell{m}{vb}{m+s}-1$.
These cells are necessarily right cells by definition of $\nextleftcell{m}{vb}{m+s}$.
With this convention, the number of visited cells on the row crossed by $a_{\oriented{m}i}$ is $q+\test{i\leq r}$.
Moreover, on this row the traversal begins by visiting all the right cells of spiral coordinate at least $m$.
These cells are counted by $i-1-u_i\geq 0$ by definition of $\scompact{m}{m}{vb}{s}$.  
We conclude that $$|\leftcellonrowi{m}{vb}{i}{s}| = \max(0,(q+\test{i\leq r})-(i-1-u_i))$$ since the visited left cell on the row crossed by  $a_{\oriented{m}i}$ are the visited cells minus the possibly first visited right cells.
This shows that $g$ is the proof computed by the traversal algorithm and a summation leads to the formula for the rank.
\end{proof}



\subsection{Optimizing the search of the equivalent sorted parking configuration\label{subsec:searchparking}}

We describe here an efficient algorithm to compute for any configuration $u$ on $K_n$ the toppling and permuting equivalent configuration $ \sort(\park(u))$.
%Then we will apply to its result the efficient formula of the preceeding subsection to compute with a linear arithmetic complexity the rank of any configuration on $K_n$.

\begin{center}
\begin{minipage}{15cm}
\framebox{\bf Search toppling and permuting equivalent sorted parking configuration}\newline
{\bf Input:} A configuration $u$ on $K_n$.\newline
$u'\leftarrow \compact(u)$;\newline
$u'\leftarrow \sort(u')$;\newline
For $i$ from $1$ to $n-1$ do $k_i \leftarrow (n-1)u'_i-n(i-1)$;od;\newline
$i_{\max }\leftarrow i$ such that $k_i = \max_{j=1\ldots n-1}(k_j)$;\newline
Let $k_{i_{\max}}=q(n-1)+r$ be the euclidean division  by $n-1$ defining $q$ and $r$;\newline
For $i$ from $1$ to $n-1$ do $u''_{i} \leftarrow u'_{((i-1-r)\mod (n-1))+ 1}-q+r+\test{i\leq r} $;od;\newline
$u''_n \leftarrow u'_n+k_{i_{\max}}$;\newline
{\bf Output:} The configuration $u''$ ($=\sort(\park(u))$).
\end{minipage}
\end{center}


\begin{proposition}
The preceding algorithm correctly returns $u''=\sort(\park(u))$ and may be implemented with a linear arithmetic complexity.
\end{proposition}

\begin{proof}

First we show that this algorithm is correct.

We implicitly use a formula for $\T^j.u$ where $j\in\mathbb{Z}$ and $u$ is a sorted compact configuration:
$$ \T^j.u = (\T^{(1-n)})^{-q}\T^r.u = \T^r.u+q\laplacianconf{n} = (u_{(i-1-r\mod n-1)+1}-q+r-n\test{i\leq r};u_n+j)$$
where $j=q(n-1)+r$ is the euclidean division of $j$ by $n-1$.
This formula is obtain by iteration of the formula in the proof of $5.$ in Proposition~\ref{prop:convert}.
Roughly speaking, $u_{(i-1-r\mod n-1)+1}$ takes into account the cyclic permutations induced by $\T^r$, $-q$ corresponds to the $-q$ topplings of the sink, $+r$ to the $r$ topplings of vertices in $\T^r$ and $-n\test{i\leq r}$ compensate in the case where the vertex is toppled once during the computation of $\T^r$. 

The configuration $u'=\sort(\compact(u))$ is a sorted and compact configuration.
We search the power $j\in \mathbb{Z}$ such that $\T^j.u'=u''=\sort(\park(u'))$. 
If $u''=\T^j.u'$ is sorted and parking then in particular $u''_1=0$. 
We use this equality as a criterion to filter the possible values of $j$.
We discuss the $n-1$ possible values of $r$ and indeed the two values of $\test{1\leq r}$.
It will appear that for each value there exists a single value $j_r$ such that $u^{(r)} := \T^{j_r}.u'$ satisfies $u^{(r)}_1=0$.
For any choice of $r$, let $j_r=q_r(n-1)+r$ the euclidean division  by $n-1$ of this hypothetical $j_r$ and $i = (1-r) \mod (n-1) +1$.
We then use the preceding formula for $\T^{j_r}.u'$.
If $r=0$ then $i=r+1$ and $u^{(r)}_1 = 0  \iff  u'_i-q_r+r = 0 \iff j_r = (n-1)u'_i+nr = (n-1)u'_i+n(i-1)$.
If $r > 0$ then $i=n-r$ and $u^{(r)}_1=0 \iff u'_i-q_r+r-n = 0 \iff j_r = (n-1)u'_i+nr-n(n-1)=(n-1)u'_i+n(i-1)$.
Hence, the expected value of $j$ appears in $\{(n-1)u'_i+n(i-1)\}_{i=1\ldots n-1}$ also called the $\{k_i\}_{i=1\ldots n-1}$ in the algorithm. 

We may write $u'=\scompact{k}{0}{w}{s}$ for $k=(n-1)u'_1$, $s=u'_n$ and some almost balanced word $w$.
Since by definition $\T^{j_r}.u'=u^{(r)}=\scompact{k-j_r}{0}{w}{s+j_r}$ satisfies $u^{(r)}_1 = 0$, the cell of spiral coordinate $k-j_r$ is a left cell of $\cutskewcylinder{0}{w}$.
In the cut skew cylinder related to the sorted and parking $u''=\T^{j}.u'$ the cell $k-j$ should also be $\min \leftcutskewcylinder{0}{w}$ according to $6.$ in Proposition~\ref{prop:convert}.
This means that $j$ is the maximal value among the $\{j_r\}_{r=1\ldots n-1}=\{k_i\}_{i=1\ldots n-1}$.
This value is called $k_{i_{\max}}$ in the algorithm.
This algorithm is correct since it returns $u''=\T^{k_{i_{\max}}}.u'$ computed via the first formula of this proof.

Then we discuss how this algorithm may be implemented within a linear arithmetic complexity also called $O(n)$.

The explicit definition of $\compact(u)$ may be evaluated in $O(n)$.
The sort of the compact configuration $u'=\compact(u)$ may be performed in $O(n)$ using a classical sort by \emph{values} since those values are between $0$ and $n-1$.
More precisely we use a vector $v=(v_i)_{i=0\ldots n-1}$ initialized to $v=0\in \mathbb{Z}^{n-1}$, then we increment $v[u'_i]$ for $i=1\ldots n-1$ and finally we compute $\sort(u')$ has the concatenation of blocks of $v_i$ values $i$ for $i$ from $0$ to $n-1$.
Our model of complexity is called arithmetic since we assume that an euclidean division or a comparison may be performed in constant time, no matter of the size of the involved integers.  
Within this framework, the evaluation of the $k_i$, the search of the maximal element $\max\{ k_i\}_{i=1\ldots n-1}$ by a classical loop and the evaluation of $\T^{k_{i_{\max}}}.u'$ are explicitly in $O(n)$.
\end{proof}


\begin{theorem}
There exists an explicit algorithm of linear arithmetic complexity computing the rank of any configuration on the complete graph $K_n$.
\end{theorem}

\begin{proof}
Let $u$ be a configuration on $K_n$.
We compute $u'=\sort(\park(\sort(\compact(u))))$ in $O(n)$ via the preceding algorithm.
Then we return $\rank(u')(=\rank(u))$ computed via an evaluation in $O(n)$ of the formula in Theorem~\ref{theo:rank-formula}.
\end{proof}

\section{Enumerative byproducts related to the context}
\label{sec:rank-byproducts}
%\subsection{On Laurent series for $(\degree,\rank)$ bistatistic on configurations}

The degree and rank parameters are the two parameters on configurations involved in the Riemann-Roch theorem for graphs.
These two parameters are invariant by toppling and permuting vertices.
We use as canonical element the unique sorted and parking configuration in each equivalence class by toppling and permuting.
Hence, a natural generating function in this context is  
$$ \sgrankdegree_n(r,d) := \sum_{u} r^{\rank(u)}d^{\degree(u)} $$
where $u$ runs on sorted parking configurations on $K_n$.
This series is not a usual power series since $\degree(u)$ may be as small as wished however if is a formal Laurent series.

\begin{figure}[ht!]
\begin{center}
\begin{minipage}{9.5cm}
\begin{tikzpicture}[scale=0.52]
  \draw (-1,0) grid (14,8);
\foreach \area/\level/\multiplicity in {-1/0/14,0/0/14,1/0/13,1/1/1,2/0/12,2/1/2,3/0/10,3/1/4,4/0/7,4/1/7,5/0/4,5/1/8,5/2/2,6/0/1,6/1/9,6/2/3,6/3/1,7/1/4,7/2/8,7/3/2,8/2/7,8/3/7,9/3/10,9/4/4,10/4/12,10/5/2,11/5/13,11/6/1,12/6/14,13/7/14} {
\draw node at (\area+0.5,\level+0.5) {\small $\multiplicity$};
}
\foreach \i in {-2,-1,...,12}{
\draw node at (\i+1.5,-0.5) {\small $d^{\i}$};
}
\foreach \i in {-1,0,...,6}{
\draw node at (-1.7,\i+1.5) {\small $r^{\i}$};
}
\end{tikzpicture}
\end{minipage}
\begin{minipage}{5.5cm}
\begin{tikzpicture}[scale=0.52]
\draw (0,0) grid (8,8);
\foreach \area/\level/\multiplicity in {0/0/1,0/1/4,0/2/7,0/3/10,0/4/12,0/5/13,0/6/14,1/0/4,1/1/9,1/2/8,1/3/7,1/4/4,1/5/2,1/6/1,2/0/7,2/1/8,2/2/3,2/3/2,3/0/10,3/1/7,3/2/2,3/3/1,4/0/12,4/1/4,5/0/13,5/1/2,6/0/14,6/1/1,7/0/14,0/7/14} {
\draw node at (\area+0.5,\level+0.5) {\small $\multiplicity$};
}
\foreach \i in {0,1,...,7}{
\draw node at (\i+0.5,-0.5) {\small$x^\i$};
\draw node at (-0.5,\i+0.5) {\small$y^\i$};
}
\draw[red,opacity=0.3,line width=2] (0,0) -- (8,8);
\end{tikzpicture}
\end{minipage}
\caption{Part of the support of $K_5(r,d)$ and the related support of $M_5(x,y)$\label{fig:support-K5}}
\end{center}
\end{figure}



Inspection of the data for the small values of $n$ leads to conjecture a symmetry.
In the left part of Figure~\ref{fig:support-K5} we present the values in a two dimensional array where the cell $(i,j)$ contains the coefficient $[d^ir^j]\sgrankdegree_5(r,d)$ for configurations on the complete graph $K_5$ of degree between $-2$ and $12$. 
The complete support of $K_5(d,r)$ would require to add an half-infinite diagonal and an half-infinite horizontal line filled with the value $14$. 
The coefficients $1,4,7,10,13,14,14,\ldots$ along the diagonal starting at $r^{-1}d^5$ also appears along the bottom horizontal row starting at the same $r^{-1}d^5$.
This property also appears for the next pairs of diagonals and horizontal rows.
In the right part of the same Figure~\ref{fig:support-K5}, the change of variable $(\degree,\rank)\rightarrow (\rank+1,{n-1\choose 2}-\degree + \rank)$ lay the values out so that the symmetry is the more explicit symmetry along the main diagonal.
This motivates the definition of the two parameters $\xpara(u):=\rank(u)+1$ and $\ypara(u) := {n-1\choose 2} - \degree(u)+\rank(u)$ on a configuration $u$ and the definition of the generating function
$$ \sgleftright_n(x,y) := \sum_{u} x^{\xpara(u)}y^{\ypara(u)}$$
where $u$ runs overs sorted parking configurations on $K_n$.


This generating function is a power series in $x$ and $y$ since by definition $\rank(u)\geq -1$ so $\xpara(u)\geq 0$ and $\ypara(u)\geq 0$ will be deduced from the proof of the conjectural symmetry $\sgleftright_n(x,y)=\sgleftright_n(x,y)$.
This symmetry will be proven by the involution of Riemann-Roch theorem detailed in Subsection~\ref{subsec:riemann-roch-symmetry}. 
We will interpret this involution in terms of cut skew cylinders.
This interpretation will provide in Subsection~\ref{subsec:xypara-inter} an alternative definition of the parameters $\xpara$ and $\ypara$ in terms of the traversal computing the rank.
Moreover,in Subsection~\ref{subsec:degree-rank-enumeration} geometric sums will appear along these computations and their summations will lead to an expression for 

$$ \mathbb{M}(x,y;z) = \sum_{n\geq 1} \sgleftright_n(x,y)z^n$$

as a rather simple rational function involving two copies of a classical generating function on Dyck words. 

\subsection{On the involution in Riemann-Roch theorem}
 \label{subsec:riemann-roch-symmetry}

For the graph $G$, the Riemann-Roch theorem relates the ranks of configurations $u$ and $K_G-u$ on $G$.
The map $u\rightarrow K_G-u$ is an involution.
For the complete graph $G=K_n$, we have $K_G = (n-3;n-3)$.
In this case, this involution combines nicely with the equivalence by toppling and permutation: if $u$ and $v$ are toppling and permuting equivalent then also are $K_G-u$ and $K_G-v$.
This leads to the involution on sorted parking configurations on $K_n$,
$$ \rrinvolutionconf.u := \sort\circ \park (K_G-u).$$

\begin{proposition}
Let $u$ be a sorted parking configuration  on $K_n$, we have $$(\xpara(\rrinvolutionconf.u),\ypara(\rrinvolutionconf.u)) = (\ypara(u),\xpara(u)).$$
\end{proposition}

\begin{proof}
The proof is similar for any configuration $u$ on $K_n$.
The Riemann-Roch theorem applied to $u$ implies that 
$$ \xpara(K_G-u) = \rank(K_G-u) + 1 = \rank(u) - \degree(u) + {n \choose 2} - n +1 = \ypara(u).$$
Applying the same proof to $K_G-u$, we obtain $\ypara(K_G-u) = \xpara(u)$.
\end{proof}

\begin{corollary}
For any $n\geq 1$, we have $\sgleftright_n(x,y)=\sgleftright_n(y,x)$.
\end{corollary}



This involution $\rrinvolutionconf$ corresponds to an natural involution on cut skew cylinders.
Roughly speaking, the involution on cut skew cylinders consists in reversing the order in which the cells are visited along the spiral traversal.

For a word $w=w_1w_2\dots w_k$ the \emph{reverse word} is $\reverse{w}=w_kw_{k-1}\ldots w_1$.
For any Dyck word $w$, let $w=fabg$ be the \emph{last maximum factorization} where $|fa|_a-|fa|_b$ is the longest prefix $p$ of $w$ where the maximal value $|p|_a-|p|_b$ is reached.
%In other words, the occurence of letter $a$ in the factorization leads to the last vertex of maximal (vertical height) of the Dyck path.
We define the  map $$\rrinvolutionconf(w):=a\reverse{f}b\reverse{g}.$$
This map is an involution since in the last maximum factorization $f'abg'$ of $\rrinvolutionconf(w)$ we have $f'a=a\reverse{f}$ and $bg'= \reverse{g}b$. 
A restriction of this involution $\rrinvolutionconf$ appears in previous work of one of the authors~\cite{leborgne}. % YLB upper interactions

In terms of cut skew cylinder, the involution $\rrinvolutionconf$ on sorted parking configurations will map the cell of spiral coordinate to a cell of spiral coordinate $C(w)-s$ where by definition
$$ C(w) := \max \rightcutskewcylinder{0}{w} - \min \leftcutskewcylinder{0}{w}.$$ 

\begin{proposition}\label{prop:xiinvol}
Let $u=\scompact{0}{0}{wb}{s}$ be a sorted parking configuration on $K_n$ and $w=fabg$ the last maximum factorization of $w$. We have 

$$ \rrinvolutionconf.u  = \scompact{0}{0}{\rrinvolutionconf(w)b}{C(w)-s-1}.$$

\end{proposition}

\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=1]
\draw (-4, 0) grid (10, 7.2);
\foreach \s/\x/\y in {28/-3/0,36/-3/1,44/-3/2,52/-3/3,60/-3/4,68/-3/5,76/-3/6,21/-2/0,29/-2/1,37/-2/2,45/-2/3,53/-2/4,61/-2/5,69/-2/6,14/-1/0,22/-1/1,30/-1/2,38/-1/3,46/-1/4,54/-1/5,62/-1/6,7/0/0,15/0/1,23/0/2,31/0/3,39/0/4,47/0/5,55/0/6,0/1/0,8/1/1,16/1/2,24/1/3,32/1/4,40/1/5,48/1/6,1/2/1,9/2/2,17/2/3,25/2/4,33/2/5,41/2/6,2/3/2,10/3/3,18/3/4,26/3/5,34/3/6,3/4/3,11/4/4,19/4/5,27/4/6,4/5/4,12/5/5,20/5/6,5/6/5,13/6/6,6/7/6}{
\draw node[green] at (\x-0.2,\y+0.2) {\tiny{$\s$}};
\draw node[red] at (\x-0.8,\y+0.8) {\tiny{$\overline{\s}$}};
}
\foreach \s/\x/\y in {7/2/0,14/3/0,6/3/1,21/4/0,13/4/1,5/4/2,28/5/0,20/5/1,12/5/2,4/5/3,35/6/0,27/6/1,19/6/2,11/6/3,3/6/4,42/7/0,34/7/1,26/7/2,18/7/3,10/7/4,2/7/5,49/8/0,41/8/1,33/8/2,25/8/3,17/8/4,9/8/5,1/8/6,56/9/0,48/9/1,40/9/2,32/9/3,24/9/4,16/9/5,8/9/6,63/10/0,55/10/1,47/10/2,39/10/3,31/10/4,23/10/5,15/10/6}{
\draw node[green] at (\x-0.2,\y+0.2) {\tiny{$\overline{\s}$}};
\draw node[red] at (\x-0.8,\y+0.8) {\tiny{$\s$}};
}
\draw[line width=2,draw=blue] (1,0) -- (1,3) -- (2,3) -- (2,5) -- (4,5) -- (4,6) -- (6,6) -- (6,7) -- (9,7);
\foreach \y in {1,...,7}{
\draw[line width=2,draw=green,->] (-2.05,\y-1) -- (-2.05,\y);
\draw[line width=2,draw=red,<-] (-1.95,\y-1) -- (-1.95,\y);
\draw[line width=2,draw=green,->] (-2.05,\y-0.5) -- (-2.05,\y);
\draw node[green] at (-2.5,\y-0.5) {$a_{\oriented{21}\y}$};
\draw node[red] at (-1.5,8-\y-0.5) {$a_{\oriented{\overline{62}}\y}$};
}
\end{tikzpicture}
\caption{Example of the superimposition principle\label{fig:superimposition}}
\end{center}
\end{figure}


From the briefly postponed proof of this proposition, we extract in a lemma the following \emph{superimposition principle} for $u=\scompact{k}{m}{w}{s}$ based on the involution which maps the cell $k\in \mathbb{Z}$ to the cell $-k\in \mathbb{Z}$ reversing the spiral ordering of cells.


\begin{lemma}(Superimposition principle)\label{lem:superimposition}
Let $u=\scompact{k}{m}{w}{s}$ be a sorted and compact configuration on $K_n$.
$$ u':=(-u_{n-i};u_n) = \scompact{k'}{m'}{w'}{s'} $$
where $k'= n(1-n)+(2n-1)-k$, $m'=(2n-1)-m$, $w'=\reverse{w}$ and $s=s'$. 
\end{lemma}

\begin{proof}
The configuration $\scompact{k}{m}{w}{s}$ is defined by a cut skew cylinder $\cutskewcylinder{m}{w}$ and an oriented segment $\oriented{k}$. 
The claim is the consequence of the following symmetries: reverse the orientation of the segment $\oriented{k}$, reverse the order in which the cells are visited, the cell $k$ becoming the cell $-k$, and change the corner related to a cell from south-east to north-west.
This leads to a new cut skew cylinder $\cutskewcylinder{m'}{w'}$ and a new oriented segment $\oriented{k'}$ (toward south).
This data defines the new configuration $u'=\scompact{k'}{m'}{w'}{s}$ as the image via the central symmetry with respect to the origin exchanging left and right and also top and bottom.
An example is provided in Figure~\ref{fig:superimposition} where in red are the initial data and in green the new data.
In this case, the green oriented segment $\oriented{21}$ is reversed to become the red oriented segment $\oriented{\overline{62}}$.
Inspection shows that $k'=-n^2+3n-1-k$, $m'=2n-1-m$, and $w'=\reverse{w}$.
We also have  
$$ u' := (u'_i;u'_n) = (-u_{n-i};u_n)$$ 
since the differences of abscissa are opposite and the order of steps in the oriented segment $\oriented{k'}$ reversed compared to $\oriented{k}$. 
\end{proof}

\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.8]
%grid
\draw (-5,0) grid (9,7);
% w and \Phi(w) cut
\draw[line width=2,draw=blue] (0,0) -- (0,2) -- (1,2) -- (1,5) -- (3,5) -- (3,6) -- (5,6) -- (5,7) -- (8,7);
% w Dyck path proof
\draw[line width=1,dashed,draw=green] (0,0) -- (7,7);
% w cut start
\draw[line width=0,fill=green] (0,0) circle (0.1);
% \Phi(w) Dyck path proof
\draw[line width=1,dashed,draw=red] (1,5) -- (-4,0);
\draw[line width=1,dashed,draw=red] (4,7) -- (2,5);
% \Phi(w) cut start
\draw[line width=0,fill=red] (1,5) circle (0.1);
% Label in w
\foreach \i/\j/\wlabel in {0/0/0,1/1/1,2/2/2,3/3/3,4/4/4,5/5/5,6/6/6,-1/0/7,0/1/8,1/2/9,2/3/10,3/4/11,4/5/12,5/6/13,-2/0/14,-1/1/15,0/2/16,1/3/17,2/4/18,3/5/19,4/6/20,-3/0/21,-2/1/22,-1/2/23,0/3/24,1/4/25,2/5/26,3/6/27,-4/0/28,-3/1/29,-2/2/30,-1/3/31,0/4/32,1/5/33,1/6/41}{
\draw node[green] at (\i-0.25,\j+0.25) {\tiny{$\wlabel$}};
}
% Label in Phi(w)
\foreach \i/\j/\phiwlabel in {1/5/0,0/4/1,-1/3/2,-2/2/3,-3/1/4,4/7/5,3/6/6,2/5/7,1/4/8,0/3/9,-1/2/10,-2/1/11,5/7/12,4/6/13,3/5/14,2/4/15,1/3/16,0/2/17,-1/1/18,6/7/19,5/6/20,4/5/21,3/4/22,2/3/23,1/2/24,0/1/25,7/7/26,6/6/27,5/5/28,4/4/29,3/3/30,2/2/31,1/1/32,8/7/33}{
\draw node[red] at (\i+0.25,\j-0.25) {\tiny{$\phiwlabel$}};
}
% % Cells of left/right component
% \foreach \j/\wj in {1/0,2/0,3/1,4/1,5/1,6/3,7/5}{
%   \foreach \i in {-4,-3,...,\wj}{
%     \draw[fill=red,opacity=0.3] (\i-1,\j-1) rectangle (\i,\j);
%   }
%   \foreach \i in {\wj+1,\wj+2,...,8}{
%     \draw[fill=green,opacity=0.3] (\i-1,\j-1) rectangle (\i,\j);
%   } 
% }
% w spiral traversal
\foreach \diag/\length in {-2/3,-1/6}{
  \foreach \j in {0,...,\length}{
   \draw[green,line width=2,->,opacity=0.4] (\diag+\j+0.1,\j+0.1) -- (\diag+\j+1-0.1,\j+1-0.1);
 }
}
% pointed vertex
\draw[fill=black,line width=0] (2,4) circle (0.12); 
% \Phi(w) spiral traversal
\foreach \diag/\colength/\y in {-2/4/6,-3/0/4}{
  \foreach \j in {\colength,...,\y}{
   \draw[red,line width=2,->,opacity=0.4] (\diag+\j+0.9,\j+0.9) -- (\diag+\j+0.1,\j+0.1);
 }
}
% rank w 
\foreach \i/\j in {-1/0,-2/0,-1/1,0/2}{
\draw[line width=0,fill=green,opacity=0.4] (\i+0.5,\j+0.5) circle (0.15); 
}
% rank Phi(w)
\foreach \i/\j in {1/4,2/4,3/5}{
\draw[line width=0,fill=red,opacity=0.4] (\i+0.5,\j+0.5) circle (0.15); 
}
% w oriented segment
\draw[line width=4,opacity=0.6,draw=green,->] (0,0) -- (0,7);
% Phi(w) oriented segment
\draw[line width=4,opacity=0.6,draw=red] (1,5) -- (1,0);
\draw[line width=4,opacity=0.6,draw=red,->] (9,7) -- (9,5);
\draw node[red] at (0+0.25,7-0.25) {\tiny{$\overline{23}$}};
\end{tikzpicture}
\caption{Superimposition principle for the traversals related to the computation of the rank of $\scompact{0}{0}{aabaaabbabbabbb}{10}$ and $\scompact{0}{0}{aaabaabbbabbabb}{7}$.\label{fig:xypara-superimposition}}
\end{center}
\end{figure}

We then use this superimposition principle in the proof of Proposition~\ref{prop:xiinvol}. 

\begin{proof} 

By definition, we have $$ \sort(K_G - u) = (n-3-u_{n-i};n-3-u_n)= (-u_{n-i};-u_n)-(n-3)\laplacianconf{n}+n(n-3)\onechipconf{n}.$$


We factorize $w$ in $w=fabgb$ where $v=fabg$ is the factorization at last maximal height of the Dyck word $v$ defined by $w=vb$. 
Using the superimposition principle of Lemma~\ref{lem:superimposition} and changing the value of $u_n$ to its opposite, we have 
$$(-u_{n-i};-u_n)=\scompact{-n^2+3n-1}{2n-1}{b\reverse{g}ba\reverse{f}}{-s}.$$
It appears that $a\reverse{f}b\reverse{g}b=\rrinvolutionconf(v)b$ is a cyclic conjugate of $b\reverse{g}ba\reverse{f}$.
According to $2.$ in Proposition~\ref{prop:convert}, we change the start of the cut to make appear this cyclic conjugate:
$$(-u_{n-i};-u_n)=\scompact{-n^2+3n-1}{2n-1+n|b\reverse{g}b|_a-(n-1)|b\reverse{g}b|_b}{\rrinvolutionconf(v)b}{-s}.$$
On one hand $w$ is a cut, so we have $n|w|_a+(n-1)|w|_b = 0$, hence $n|b\reverse{g}b|_a-(n-1)|b\reverse{g}b|_b = -n|fa|_a+(n-1)|fa|_b$.
On another hand, since $m=0=\min \leftcutskewcylinder{0}{w}$, $C(w)=\max \rightcutskewcylinder{0}{fabg}$ is also the spiral label of the cell whose west vertical side is related to the explicit occurence of $a$ in $w=fabgb$, hence $C(w)=n|fa|_a-(n-1)|fa|_b-(2n-1).$
These two observations leads to  
$$(-u_{n-i};-u_n)=\scompact{-n^2+3n-1}{-C(w)}{\rrinvolutionconf(v)b}{-s}.$$
Using $3.$ of Proposition~\ref{prop:convert}, we increment the labeling of cells by $C(w)$ so that the cut starts in cell $0$: 
$$(-u_{n-i};-u_n)=\scompact{-n^2+3n-1+C(w)}{0}{\rrinvolutionconf(v)b}{-s}.$$
Adding $n(n-3)\onechipconf{n}$ modifies only the value on the sink $n$ and the $n-3$ topplings of this sink $n$ are equivalent to $\T^{(1-n)(n-3)}$ hence using $5.$ of Proposition~\ref{prop:convert} we obtain 
$$\sort(K_{K_n}+(-u_{n-i};-u_n))=\scompact{3(1-n)+C(w)}{0}{\rrinvolutionconf(v)b}{-s+(n-3)}.$$
According to $6.$ (and then $5.$) in Proposition~\ref{prop:convert}, we apply $\T^{3(1-n)+C(w)}$ to obtain the toppling and permuting equivalent parking configuration $\sort(\park(K_{K_n}-u))=\rrinvolutionconf.u$ with the claimed expression in the proposition.
%% Inspection shows that $\rrinvolutionconf(w)b$ is the cyclic conjugate of $b\reverse{w}$ which may be written $vb$ where $v$ is a Dyck word. 
%% We use $2.$ of Proposition~\ref{prop:convert} to move the start of the cut along the factor $b\reverse{g}b$ to replace the cut $b\reverse{w}=b\reverse{g}ba\reverse{f}$ by the cyclically equivalent cut $\rrinvolutionconf(w)b$:  $$(-u_{n-i};-u_n)=\scompact{-n^2+3n-1}{2n-1+C(w)}{\rrinvolutionconf(w)b}{-s}.$$ 
%% Using $3.$ of Proposition~\ref{prop:convert}, we decrement the labeling of cells by $2n-1+C(w)$ so that the cut starts in cell $0$: $$(-u_{n-i};-u_n)=\scompact{-n^2+n-C(w)}{0}{\rrinvolutionconf(w)b}{-s}.$$
%% Adding $n(n-3)\onechipconf{n}$ modifies only the value on the sink $n$ and the $n-3$ topplings of this sink $n$ are equivalent to $\T^{(1-n)(n-3)}$ hence using $5.$ of Proposition~\ref{prop:convert} we obtain 
%% $$ \sort(K_G - u) = \scompact{3(n-1)-C(w)}{0}{\rrinvolutionconf(w)b}{-s+n-3}.$$
%% The word $\rrinvolutionconf(w)$ is a Dyck word so $\min \leftcutskewcylinder{0}{\rrinvolutionconf(w)b} = 0$ and using $6.$ of Proposition~\ref{prop:convert} we have the expected expression for $ \sort(\park(\sort(K_G - u))) =: \rrinvolutionconf.u.$
\end{proof}


\subsection{Interpretation of $(\xpara,\ypara)$ on cut skew cylinders \label{subsec:xypara-inter}}

Let $u=\scompact{0}{0}{vb}{s}$ be a sorted parking configuration on $K_n$.
Let $w$ a cyclic conjugate of $vb$ and $m\in \mathbb{Z}$ be such that $\cutskewcylinder{m}{w} = \cutskewcylinder{0}{vb}$ proven by a change of the start for the cut.
The parameters $\xpara(u)$ and $\ypara(u)$ admits a description in terms of $\cutskewcylinder{m}{w}$ and $s$.
The \emph{crossed left cells} of $u=\scompact{k}{m}{w}{s}$ are 
$$ \crossedleftcells{m}{w}{s} := \{k | k \leq s \mbox{ and } k\in \leftcutskewcylinder{m}{w} \}.$$
We also consider the \emph{uncrossed right cells} defined by 
$$ \uncrossedrightcells{m}{w}{s} := \{k | k > s \mbox{ and } k\in \rightcutskewcylinder{m}{w}\}.$$
We denote the cardinalities of these sets by $$\leftpara{m}{w}{s} := |\crossedleftcells{m}{w}{s}|\mbox{ and }\rightpara{m}{w}{s} := |\uncrossedrightcells{m}{w}{s}|$$



We illustrate these definitions in Figure~\ref{fig:xypara-superimposition} in the particular case $w=vb$ where $v=aabaaabbabbabb$ is a Dyck word and so $m=0$, and $s=10$.
This factorization $w=vb$ is also proven by the dashed green diagonal.
The traversal of cells computing $\rank(\scompact{0}{0}{vb}{s})$ visits the cells of spiral coordinate from $0$ to $s$ and those cells are crossed by a green diagonal arrow in north-west direction. 
%The origin of the name of these sets appears in this particular case. 
There the cells of $\crossedleftcells{0}{vb}{s}=\{0,7,8,9\}$ are marked by a green disk and the cells of $\uncrossedrightcells{0}{vb}{s}=\{11,12,18\}$ by a red disk.






%% Let $u=\scompact{m}{m}{w}{s}$ be a sorted parking configuration on $K_n$.
%% The parameters $\xpara(u)$ and $\ypara(u)$ admits a description embedded in the related cut skew cylinder.
%% In the spirit of the definition of $(\leftcellonrowi{m}{w}{i}{s})_i$ is Subsection~\ref{}, we define the \emph{crossed left cells} of $\scompact{m}{m}{w}{s}$ by 
%% $$ \crossedleftcells{m}{w}{s} := \{k | m \leq k \leq m+s \mbox{ and } k\in \leftcutskewcylinder{m}{w} \} (= \cup_{i=1}^{n-1}\leftcellonrowi{m}{w}{i}{s}).$$
%% We also consider the \emph{uncrossed right cells} defined by 
%% $$ \uncrossedrightcells{m}{w}{s} := \{k | k > m+s \mbox{ and } k\in \rightcutskewcylinder{m}{w}\}.$$
%% We illustrate these definitions in Figure~\ref{fig:xypara-superimposition}.
%% The cells ``visited'' by the traversal for the computation of the rank of $\scompact{0}{0}{aabaaabbabbabbb}{10}$ are crossed by a green arrow. 
%% The left cells crossed by this traversal are marked by a green circle: $\crossedleftcells{0}{aabaaabbabbabbb}{10} = \{0,7,8,9\}$.
%% The right cells not crossed by this traversal are marked by a red circle: $\uncrossedrightcells{0}{aabaaabbabbabbb}{10} = \{11,12,18\}$.


\begin{proposition}
Let $u=\scompact{0}{0}{vb}{s}$ be a sorted parking configuration on $K_n$, we have 
$$ \xpara(u) = \leftpara{0}{vb}{s} \mbox{ and } \ypara(u) = \rightpara{0}{vb}{s}.$$
\end{proposition}

\begin{proof}
In this case $\min \leftcutskewcylinder{0}{vb}=0$, so $\crossedleftcells{0}{vb}{s}=\{k| 0 \leq k \leq s \mbox{ and } k \in \leftcutskewcylinder{0}{vb}\} = \cup_{i=1}^{n-1}\leftcellonrowi{0}{vb}{i}{s}.$ 
Hence the identity $$|\crossedleftcells{m}{vb}{s}| = \sum_{i=1}^{n-1}|\leftcellonrowi{m}{vb}{i}{s}| = \rank(u)+1 = \xpara(u)$$ directly follows from the Proposition~\ref{prop:read-proof} describing a proof for the rank of $u$ via the traversal.

The other identity is deduced from this first identity via an extension of the superimposition principle to the traversals computing the rank of $u$ and $\rrinvolutionconf.u$. 
An example of this superimposition with traversals is given in Figure~\ref{fig:xypara-superimposition}.
%% In green, the dotted diagonal segment matches the cannoncial Dyck word $w=aabaaabbabbabb$ for $u=\scompact{0}{0}{wb}{s}$ where $s=10$.
The green oriented vertical segment toward north, which defines $u$, starts from the south-east corner of spiral green coordinate $0$.
%% The cells from green spiral coordinate $0$ to $s=10$ are the cells visited by the optimiszed algorithm computing the rank and crossed by green diagonal arrow toward north-east.
In red, we describe the same notions as in green but on $\rrinvolutionconf.u=\scompact{0}{0}{\rrinvolutionconf(w)b}{C(w)-s-1}$ where $C(w)=18$ so that $C(w)-s-1=7$. 
The dashed red diagonal (drawn in two parts) matches $\rrinvolutionconf(w)$, the red oriented vertical segment toward south, which defines $\rrinvolutionconf.u$, starts from the north-west corner of red spiral coordinate $0$ and the visited cells during the computation of the rank of $\rrinvolutionconf.u$ are crossed by red diagonal arrows toward the south-west.  

First we assume that $s\geq 0$ and $C(w)-s-1\geq 0$ as in Figure~\ref{fig:xypara-superimposition}.
It means that $(s+1)+(C(w)-s-1+1) = C(w)+1$ cells are crossed.
This number corresponds exactly to the number of cells of spiral between the cell of spiral green coordinate $0$ and the cell of spiral red coordinate $0$.
Hence the green and red sequences of diagonals both ends in the black disk which is the south-east corner of the cell of green spiral coordinate $s+n(=18$ on example).
Since the involution $\rrinvolutionconf$ on skew cylinders exchange left and right components, we deduce that the cells of spiral green coordinate $\uncrossedrightcells{0}{wb}{s}$ are also the cells of spiral red coordinate $\crossedleftcells{0}{\rrinvolutionconf(w)b}{C(w)-s-1}$.
Hence $|\uncrossedrightcells{0}{wb}{s}| = \xpara(\rrinvolutionconf.u) = \ypara(u)$.

If $s< 0$, then only red diagonal arrows may exist.
Inspection shows that $\uncrossedrightcells{0}{wb}{s} = \rightcutskewcylinder{0}{wb} \cap \{ s,\ldots \max \rightcutskewcylinder{0}{wb}\} = \crossedleftcells{0}{\rrinvolutionconf(w)b}{C(w)-s-1}$ hence $|\uncrossedrightcells{0}{wb}{s}|=\xpara(\rrinvolutionconf.u)=\rank(\rrinvolutionconf.u)+1=\ypara(u)$.

If $C(w)-s-1 < 0$, then only green diagonal arrows may exist. 
We have $s\geq C(w)=\max(\rightcutskewcylinder{0}{wb}{s})$ so $\uncrossedrightcells{0}{wb}{s}$ is empty.
In addition, the value $C(w)-s$ on the sink of  $\rrinvolutionconf.u$ implies that this configuration is non-effective so $\rank(\rrinvolutionconf.u)=-1$.
Hence, it this case one also has $|\uncrossedrightcells{0}{wb}{s}|=0=\xpara(\rrinvolutionconf.u) = \ypara(u)$.
\end{proof}


\subsection{Enumeration of sorted parking configurations according to $(\degree,\rank)$}
\label{subsec:degree-rank-enumeration}

According $7.$ in Proposition~\ref{prop:convert}, the bijective decomposition $u=\scompact{0}{0}{vb}{s}$ of sorted parking configuration on $K_n$ where $v$ is a Dyck word of size $n-1$ implies that  
$$ \sgleftright_n(x,y) = \sum_{v}\sum_{s\in\mathbb{Z}} x^{\leftpara{0}{vb}{s}}y^{\rightpara{0}{vb}{s}}$$
where $v$ runs over Dyck words of size $n-1$. 
We introduce a partial sum of $\sgleftright_n(x,y)$ indexed by a Dyck word $v$: 
$$ \sgleftright_v(x,y) = \sum_{s\in\mathbb{Z}} x^{\leftpara{0}{vb}{s}}y^{\rightpara{0}{vb}{s}}.$$
We also introduce a slightly more general and redundant notation for monomials in these sums 
$$ \monomleftright{m}{w}{s} = x^{\leftpara{m}{w}{s}}y^{\rightpara{m}{w}{s}}.$$

First, we study independently each $\sgleftright_v(x,y)$ for each Dyck word $v$ defining the sorted and parking configurations $(\scompact{0}{0}{vb}{s})_{s\in \mathbb{Z}}$.
The partition $(\leftcutskewcylinder{0}{vb},\rightcutskewcylinder{0}{vb})$ of cells indexed by their spiral coordinate induces a partition of $\mathbb{Z}$ into maximal intervals totally contained either in $\leftcutskewcylinder{0}{vb}$ or $\rightcutskewcylinder{0}{vb}$.
We describe this partition in intervals with the maximal elements of each interval, if any.
This leads to the sets 
$$\lefttorightcell{0}{vb} := \{ s| s \in \leftcutskewcylinder{0}{vb}, s+1\in \rightcutskewcylinder{0}{vb}\}$$ 
and 
$$\righttoleftcell{0}{vb} :=  \{ s| s\in \rightcutskewcylinder{0}{vb}, s+1\in \leftcutskewcylinder{0}{vb}\}.$$ 

\begin{lemma}\label{lem:geometric-sums}
Let $v$ be a Dyck word and $H(x,y) := \frac{1-xy}{(1-x)(1-y)}$. We have 
$$ \sgleftright_v(x,y) = H(x,y)\left(\sum_{s\in \righttoleftcell{0}{vb}} \monomleftright{0}{vb}{s} - \sum_{s \in \lefttorightcell{0}{vb}} \monomleftright{0}{vb}{s} \right).$$
\end{lemma}

The notation of the proof are illustrated in Figure~\ref{fig:alternationofgeometrics}.

  
\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.8]
\draw (-4, 0) grid (9, 6.2);
\foreach \s/\x/\y/\color in {24/-3/0/black,31/-3/1/black,38/-3/2/black,45/-3/3/black,52/-3/4/black,59/-3/5/black,66/-3/6/blue,18/-2/0/black,25/-2/1/black,32/-2/2/black,39/-2/3/black,46/-2/4/black,53/-2/5/black,60/-2/6/blue,12/-1/0/black,19/-1/1/black,26/-1/2/black,33/-1/3/black,40/-1/4/black,47/-1/5/black,54/-1/6/blue,6/0/0/black,13/0/1/black,20/0/2/black,27/0/3/black,34/0/4/black,41/0/5/black,48/0/6/blue,0/1/0/black,7/1/1/black,14/1/2/black,21/1/3/black,28/1/4/black,35/1/5/black,42/1/6/blue,1/2/1/black,8/2/2/black,15/2/3/black,22/2/4/black,29/2/5/black,36/2/6/blue,2/3/2/black,9/3/3/black,16/3/4/black,23/3/5/black,30/3/6/blue,3/4/3/black,10/4/4/black,17/4/5/black,24/4/6/blue,4/5/4/black,11/5/5/black,18/5/6/blue,5/6/5/black,12/6/6/blue,6/7/6/blue,0/8/6/blue}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\s$}};
}
\foreach \s/\x/\y/\color in {6/2/0/black,12/3/0/black,5/3/1/black,18/4/0/black,11/4/1/black,4/4/2/black,24/5/0/black,17/5/1/black,10/5/2/black,3/5/3/black,30/6/0/black,23/6/1/black,16/6/2/black,9/6/3/black,2/6/4/black,36/7/0/black,29/7/1/black,22/7/2/black,15/7/3/black,8/7/4/black,1/7/5/black,42/8/0/black,35/8/1/black,28/8/2/black,21/8/3/black,14/8/4/black,7/8/5/black,48/9/0/black,41/9/1/black,34/9/2/black,27/9/3/black,20/9/4/black,13/9/5/black,6/9/6/blue}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\overline{\s}$}};
}
\draw[line width=2,draw=blue] (1,0) -- (1,1) -- (2,1) -- (2,4) -- (5,4) -- (5,6) -- (8,6);
% oplus
\foreach \x/\y in {7/6,6/6,4/4,3/4}{
\fill[white!60!red] (\x,\y) circle (0.2);
\draw node at (\x,\y) {$\oplus$};
}
% ominus
\foreach \x/\y in {5/5,2/3,2/2}{
\fill[white!60!green] (\x,\y) circle (0.2);
\draw node at (\x,\y) {$\ominus$};
}
% ri
\foreach \x/\y/\i in {6/5/1,3/3/2,5/5/3,2/3/4}{
\draw[red] node at (\x+0.5,\y+0.5) {$r_\i$};
}
% li
\foreach \x/\y/\i in {1/1/1,4/4/2,1/2/3}{
\draw[green] node at (\x+0.5,\y+0.5) {$l_\i$};
}
\end{tikzpicture}
\vspace{0.5cm}
\begin{tikzpicture}[scale=0.8]
\foreach \x in {1,...,4}{
\draw node[rotate=45] at (-\x,0) {\tikz[scale=0.57]{\draw (0,0) grid (1,1);}}; 
\draw node at (-\x,-0.25) {\tiny{$\overline{\x}$}};
}
\foreach \x in {0,...,12}{
\draw node[rotate=45] at (\x,0) {\tikz[scale=0.57]{\draw (0,0) grid (1,1);}}; 
\draw node at (\x,-0.25) {\tiny{$\x$}};
}
% ri
\foreach \x/\i in {-1/1,3/2,5/3,9/4}{
\draw node[red] at (\x,0.05) {$r_\i$};
\draw[line width=2,draw=blue] (\x+0.5-0.5,0+0.5) -- (\x+0.5+0.5,0-0.5);
\fill[white!80!red] (\x+0.5,0) circle (0.2);
\draw node at (\x+0.5,0) {$\oplus$};
} 
% li
\foreach \x/\i in {1/1,4/2,8/3}{
\draw node[green] at (\x,0.05) {$l_\i$};
\draw[line width=2,draw=blue] (\x+0.5-0.5,0-0.5) -- (\x+0.5+0.5,0+0.5);
\fill[white!80!green] (\x+0.5,0) circle (0.2);
\draw node at (\x+0.5,0) {$\ominus$};
} 
\draw node at (-5,0) {$\ldots$};
\draw node at (13,0) {$\ldots$};
\foreach \x in {-4,-3,-2,2,}{
}
\end{tikzpicture}
\caption{Example of decomposition of $\sgleftright_v(x,y)$ into an alternation of geometric sums.\label{fig:alternationofgeometrics}}
\end{center}
\end{figure}


\begin{proof}
If $s<0$, then by convention $s\in \rightcutskewcylinder{0}{vb}$.
If $s\geq (n+1)(n-1)$, then $s\in \leftcutskewcylinder{0}{vb}$ since the greatest possible integer in the right cut appears only in the case $\cutskewcylinder{0}{a^{n-1}b^n}$ and is $ n^2-3n+1$.
Hence $|\righttoleftcell{0}{vb}|=|\lefttorightcell{0}{vb}|+1$ and let $k := |\lefttorightcell{0}{vb}|$.
We sort in increasing order the elements of $\righttoleftcell{0}{vb} = \{r_1,\ldots,r_{k+1}\}$ and $\lefttorightcell{0}{vb} = \{l_1,\ldots,l_k\}$.
So the partition of $\mathbb{Z}$ in maximal intervals induced by $(\leftcutskewcylinder{0}{vb},\rightcutskewcylinder{0}{vb})$ is
$$ ]-\infty,r_1],[r_1+1,l_1],[l_1+1,r_2],\ldots [r_k+1,l_k],[l_k+1,r_{k+1}],[r_k+1,+\infty[.$$
To observe that on a given interval $I$ of this partition, the sum $\sum_{s\in I} \monomleftright{0}{vb}{s}$ is a geometric sum of reason $x$ or $1/y$, the following key discussion comes directly from the definition of $\crossedleftcells{0}{vb}{s}$ and $\uncrossedrightcells{0}{vb}{s}$:
\begin{itemize}
\item either $s+1\in \leftcutskewcylinder{0}{vb}$, then $\crossedleftcells{0}{vb}{s+1} = \crossedleftcells{0}{vb}{s} \cup \{s+1\}$ and $\uncrossedrightcells{0}{vb}{s+1} = \uncrossedrightcells{0}{vb}{s}$.% leading to the reason $x$ for the sum on $I$.  
\item or $s+1\in \rightcutskewcylinder{0}{vb}$, then $\crossedleftcells{0}{vb}{s+1} = \crossedleftcells{0}{vb}{s}$ and $\uncrossedrightcells{0}{vb}{s+1} = \uncrossedrightcells{0}{vb}{s}- \{s+1\}$. %leading to the reason $1/y$ for the sum on $I$.
\end{itemize}
Hence for $i=1,\ldots k$, for any $j$ in the interval $[r_i+1,l_i]$ we have $\monomleftright{0}{vb}{j}=x\monomleftright{0}{vb}{j-1}$ using previous discussion for $s=j-1$. 
This leads to the geometric sum of reason $x$
$$ \sum_{j=r_i+1}^{l_i}\monomleftright{0}{vb}{j} = \frac{x\monomleftright{0}{vb}{r_i}-x\monomleftright{0}{vb}{l_i}}{1-x}.$$  
Similarly, for $i=1,\ldots k$ and the intervals $[l_i+1,r_{i+1}]$, we obtain geometric sums of reason $1/y$ leading to
$$ \sum_{j=l_i+1}^{r_{i+1}} \monomleftright{0}{vb}{j} = \frac{(1/y)\monomleftright{0}{vb}{l_i}-(1/y)\monomleftright{0}{vb}{r_{i+1}}}{1-1/y} = \frac{-\monomleftright{0}{vb}{l_i}+\monomleftright{0}{vb}{r_{i+1}}}{1-y}.$$  
For the two remaining infinite intervals $]-\infty,r_1]$ and $[r_{k+1}+1,+\infty[$ we obtain respectively, after an inversion of summation order over first interval, 
$$ \sum_{j=-\infty}^{r_1} \monomleftright{0}{vb}{j} = \frac{\monomleftright{0}{vb}{r_1}}{1-y} \mbox{ and } \sum_{j=r_{k+1}+1}^{+\infty} \monomleftright{0}{vb}{j} = \frac{x\monomleftright{0}{vb}{r_{k+1}}}{1-x}.$$

In the sum $\sgleftright_v(x,y)=\sum_{j=-\infty}^{+\infty}\monomleftright{0}{vb}{j}$ decomposed into geometric sum on these intervals, each term $\monomleftright{0}{vb}{r_i}$ appears twice for a total factor of $H(x,y)=\frac{x}{1-x}+\frac{1}{1-y}$ and each term $\monomleftright{0}{vb}{l_i}$ also twice for a total factor $-H(x,y)$ as expected.  
\end{proof}

\begin{figure}[ht!]
\begin{center}
% q-Carlitz
\begin{tikzpicture}[scale=0.8]
\draw (1, 0) grid (7, 6.2);
\foreach \s/\x/\y/\color in {1/2/1/black,8/2/2/black,15/2/3/black,22/2/4/black,29/2/5/black,36/2/6/blue,2/3/2/black,9/3/3/black,16/3/4/black,23/3/5/black,30/3/6/blue,3/4/3/black,10/4/4/black,17/4/5/black,24/4/6/blue,4/5/4/black,11/5/5/black,18/5/6/blue,5/6/5/black,12/6/6/blue,6/7/6/blue}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\s$}};
}
\foreach \s/\x/\y/\color in {6/2/0/black,12/3/0/black,5/3/1/black,18/4/0/black,11/4/1/black,4/4/2/black,24/5/0/black,17/5/1/black,10/5/2/black,3/5/3/black,30/6/0/black,23/6/1/black,16/6/2/black,9/6/3/black,2/6/4/black,36/7/0/black,29/7/1/black,22/7/2/black,15/7/3/black,8/7/4/black,1/7/5/black}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\overline{\s}$}};
}
\draw[line width=1,draw=blue,dashed] (1,0) -- (7,6);
\draw[line width=2,draw=blue] (1,0) -- (1,2) -- (2,2) -- (2,3) -- (4,3) -- (4,6) -- (7,6);
\fill[fill=blue,opacity=0.3] (1,0) -- (1,2) -- (2,2) -- (2,3) -- (4,3) -- (4,6) -- (7,6) -- cycle;
\foreach \x in {2,...,6}{
 \foreach \y in {\x,...,6}{
  \draw node at (\x-0.5,\y-0.5) {$q$};
 }
}
\foreach \x in {0,...,5}{
 \draw node at (\x+1.3,\x+0.7) {$z$};
}
\draw[line width=3,draw=orange] (1,0) -- (2,0) -- (2,1) -- (3,1) -- (3,2) -- (4,2) -- (4,3) -- (5,3) -- (5,4) -- (6,4) -- (6,5) -- (7,5) -- (7,6);
\end{tikzpicture}
\caption{A Dyck path of size $6$, area $5$ and augmented area $11$\label{fig:area}} 
\end{center}
\end{figure}


Our final expression for $\mathbb{M}(x,y;z)=\sum_{n\geq 1} \sgleftright_n(x,y)z^n$ uses the generating function of Dyck words/path according to the size and the area.
Figure~\ref{fig:area} contains in blue an embedding of the Dyck word $aababbaaabbb$ as a Dyck path.
Graphically, the area of the blue Dyck path is the number of cells completely included between the Dyck path and the dashed diagonal.
We use the equivalent following definition in terms of words.
The \emph{area} of a Dyck word $v$ is  
$$\area(v) := \sum_{fa} (|f|_a-|f|_b)$$
where $fa$ runs over all prefixes of $v$ ending by an occurrence of letter $a$.  
The \emph{size} of the Dyck word $v$ is denoted by $\size(v) := |v|_a$.
The \emph{Carlitz $q$-analogue} of Catalan numbers is 
$$ C(q;z) := \sum_{v} q^{\area(v)}z^{\size(v)}$$
where $v$ runs over all possibly empty Dyck words. 
The \emph{augmented area} of a Dyck path consists in adding to the area the cells crossed by the dashed diagonal in Figure~\ref{fig:area}.
These cells also contain the variable $z$ to suggest that its are counted by the size of the path.
Hence the augmented area of $v$ is $\area(v)+\size(v)$ and the generating function of Dyck words according to augmented area and size is $C(q;qz)$.
This generating function will appear in our proof via its interpretation as the cells between the blue and orange paths in Figure~\ref{fig:area} or the symmetric picture according to the main dashed diagonal.


Let $\Y$ be the language/set of possibly empty Dyck words and $\epsilon$ the empty word.
So $\Y-\epsilon$ denotes the language of non-empty Dyck words.
Let $\kappa$ the morphism on words defined on letters by $\kappa(a):=b$ and $\kappa(b):=a$.
Let $\X:=\kappa(\Y)$.
For example, $v=aababb\in \Y$ and $\kappa(v)=\kappa(a)\kappa(a)\kappa(b)\kappa(a)\kappa(b)\kappa(b)=bbabaa=\reverse{aababb}$.
An alternative definition of $\X$ is the set of reverses of Dyck words in $\Y$.
For a language $\mathbb{L}$, we recall a classical notion of formal languages:  $\mathbb{L}^*:=\cup_{n\geq 0} \mathbb{L}^n$ where $\mathbb{L}^n$ is formed by the concatenations of $n$ words in $\mathbb{L}$.  

\begin{theorem}
$$\mathbb{M}(x,y;z) = \frac{1-xy}{(1-x)(1-y)}\frac{C(x;xz)+C(y;yz)-C(x;xz)C(y;yz)}{1-C(x;xz)zC(y;yz)}.$$
\end{theorem}

\begin{proof}

The assumption $n\geq 3$ is comfortable in our generic proof that may degenerate for $n=1$ or $n=2$. 

Hence, we first consider that $n=1$ and then $n=2$.
If $n=1$, the sorted parking configurations are the $((;s))_{s\in\mathbb{Z}}$ and $\degree((;s))=s$ and $\rank((;s))=\max(-1,s)$.
So $K_1(r,d) = \sum_{s\in \mathbb{Z}} d^sr^{\max(-1,s)}$ and after the change of variable, we have $L_1(x,y)=\frac{1-xy}{(1-x)(1-y)}=H(x,y)$.
If $n=2$, the sorted parking configurations are the $((0;s))_{s \in \mathbb{Z}}$ and $\degree((0;s))=s$ and $\rank((0;s))=\max(-1,s)$.
So $K_2(r,d) = K_1(r,d)$ and after the change of variable one obtain $L_2(x,y) = L_1(x,y)$.


\begin{figure}[ht!]
\begin{center}
% at ri
\begin{tikzpicture}[scale=0.8]
\draw (1, 0) grid (7, 6.2);
\foreach \s/\x/\y/\color in {1/2/1/black,8/2/2/black,15/2/3/black,22/2/4/black,29/2/5/black,36/2/6/blue,2/3/2/black,9/3/3/black,16/3/4/black,23/3/5/black,30/3/6/blue,3/4/3/black,10/4/4/black,17/4/5/black,24/4/6/blue,4/5/4/black,11/5/5/black,18/5/6/blue,5/6/5/black,12/6/6/blue,6/7/6/blue}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\s$}};
}
\foreach \s/\x/\y/\color in {6/2/0/black,12/3/0/black,5/3/1/black,18/4/0/black,11/4/1/black,4/4/2/black,24/5/0/black,17/5/1/black,10/5/2/black,3/5/3/black,30/6/0/black,23/6/1/black,16/6/2/black,9/6/3/black,2/6/4/black,36/7/0/black,29/7/1/black,22/7/2/black,15/7/3/black,8/7/4/black,1/7/5/black}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\overline{\s}$}};
}
\draw (0,-1) grid (1,0);
\draw node[black] at (1-0.25,-1+0.25) {\tiny{$\overline{7}$}};
\draw node[red] at (1-0.5,-1+0.5) {$r_i$};
\fill[fill=blue,opacity=0.3] (1,0) -- (7,6) -- (8,6) -- (2,0) -- cycle;
\draw (7,5) grid (8,6);
\draw node[black] at (8-0.25,5+0.25) {\tiny{$\overline{7}$}};
\draw node[red] at (8-0.5,5+0.5) {$r_i$};
\foreach \x/\y in {3/3,4/3,3/2}{
\draw[line width=0,fill=white] (\x+0.5,\y+0.5) circle (0.25);
\draw[line width=0,fill=red,opacity=0.4] (\x+0.5,\y+0.5) circle (0.25);
}
\foreach \x/\y in {2/0,6/4}{
\draw[line width=0,fill=white] (\x+0.5,\y+0.5) circle (0.25);
\draw[line width=0,fill=green,opacity=0.4] (\x+0.5,\y+0.5) circle (0.25);
}
\foreach \x in {1,...,6}{
 \foreach \y in {\x,...,6}{
  \draw node at (\x+0.5,\y-0.5) {$y$};
 }
}
\foreach \x in {2,...,6}{
 \foreach \y in {2,...,\x}{
  \draw node at (\x+0.5,\y-1.5) {$x$};
 }
}
\draw[line width=5,draw=orange,opacity=0.8] (1,0) -- (2,0) -- (2,1) -- (3,1) -- (3,2) -- (4,2) -- (4,3) -- (5,3) -- (5,4) -- (6,4) -- (6,5) -- (7,5) -- (7,6) -- (8,6);
\draw[line width=2,draw=magenta] (0,0) -- (2,0);  
\draw[line width=1,draw=blue,dashed,opacity=0.5] (1,0) -- (7,6);
\draw[line width=2,draw=magenta] (7,6) -- (8,6);
\draw[line width=2,draw=blue] (2,0) -- (3,0) -- (3,4) -- (7,4) -- (7,6);
\end{tikzpicture}
% at li
\begin{tikzpicture}[scale=0.8]
\draw (1, 0) grid (8, 6.2);
\foreach \s/\x/\y/\color in {1/2/1/black,8/2/2/black,15/2/3/black,22/2/4/black,29/2/5/black,36/2/6/blue,2/3/2/black,9/3/3/black,16/3/4/black,23/3/5/black,30/3/6/blue,3/4/3/black,10/4/4/black,17/4/5/black,24/4/6/blue,4/5/4/black,11/5/5/black,18/5/6/blue,5/6/5/black,12/6/6/blue,6/7/6/blue,0/8/6/blue}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\s$}};
}
\foreach \s/\x/\y/\color in {6/2/0/black,12/3/0/black,5/3/1/black,18/4/0/black,11/4/1/black,4/4/2/black,24/5/0/black,17/5/1/black,10/5/2/black,3/5/3/black,30/6/0/black,23/6/1/black,16/6/2/black,9/6/3/black,2/6/4/black,36/7/0/black,29/7/1/black,22/7/2/black,15/7/3/black,8/7/4/black,1/7/5/black,42/8/0/black,35/8/1/black,28/8/2/black,21/8/3/black,14/8/4/black,7/8/5/black}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\overline{\s}$}};
}
\draw (0,-1) grid (1,0);
\draw node[black] at (1-0.25,-1+0.25) {\tiny{$\overline{7}$}};
\draw node[green] at (1-0.5,-1+0.5) {$l_i$};
\fill[fill=blue,opacity=0.3] (1,0) -- (7,6) -- (8,6) -- (2,0) -- cycle;
\draw (7,5) grid (8,6);
\draw node[black] at (8-0.25,5+0.25) {\tiny{$\overline{7}$}};
\foreach \x/\y in {1/0,1/1,2/1,5/4}{
\draw[line width=0,fill=white] (\x+0.5,\y+0.5) circle (0.25);
\draw[line width=0,fill=red,opacity=0.4] (\x+0.5,\y+0.5) circle (0.25);
}
\foreach \x/\y in {4/2}{
\draw[line width=0,fill=white] (\x+0.5,\y+0.5) circle (0.25);
\draw[line width=0,fill=green,opacity=0.4] (\x+0.5,\y+0.5) circle (0.25);
}
\draw[line width=0,fill=white] (7.25,5.6) circle (0.25);
\draw[line width=0,fill=green,opacity=0.4] (7.25,5.6) circle (0.25);
\draw node at (7.25,5.6) {$x$};
\draw node[green] at (7.75,5.6) {$l_i$};
\foreach \x in {1,...,6}{
 \foreach \y in {\x,...,6}{
  \draw node at (\x+0.5,\y-0.5) {$y$};
 }
}
\foreach \x in {2,...,6}{
 \foreach \y in {2,...,\x}{
  \draw node at (\x+0.5,\y-1.5) {$x$};
 }
}
\foreach \y in {0,...,4}[{
 \draw node at (7.5,\y+0.5) {$x$};
}
\draw[line width=5,draw=orange,opacity=0.8] (1,0) -- (2,0) -- (2,1) -- (3,1) -- (3,2) -- (4,2) -- (4,3) -- (5,3) -- (5,4) -- (6,4) -- (6,5) -- (7,5) -- (7,6) -- (8,6);
\draw[line width=2,draw=magenta] (1,-1) -- (1,1);  
\draw[line width=1,draw=blue,dashed,opacity=0.5] (1,0) -- (7,6);
\draw[line width=2,draw=magenta] (8,5) -- (8,6);
\draw[line width=2,draw=blue] (1,1) -- (1,2) -- (5,2) -- (5,5) -- (8,5);
\end{tikzpicture}
\caption{$r_i$ leads to $bfb \in b\X a\Y (b\X a\Y)^* b$ and $l_i$ leads to $afa \in (\Y-\epsilon)b(\X a \Y b)^*(\X-\epsilon)$\label{fig:factors}}
\end{center}
\end{figure}



We assume that $n\geq 3$.
Starting from the expression of $\sgleftright_v(x,y)$ in Lemma~\ref{lem:geometric-sums}, we provide alternative descriptions of $\monomleftright{0}{vb}{r_i}$ where $r_i\in \righttoleftcell{0}{vb}$ and of $\monomleftright{0}{vb}{l_i}$ where $l_i\in \lefttorightcell{0}{vb}$.

The sequence of cells $(r_i+k)_{k=1\ldots n-1}$ contains the minimal cell in each row of spiral coordinate strictly greater than $r_i$.
In Figure~\ref{fig:factors} at left, it corresponds to the cells crossed by the dashed blue diagonal.
This observation proves that $\leftcutskewcylinder{r_i+n}{(ba)^{n-1}b} = \{ k| k > r_i\}$ and $\rightcutskewcylinder{r_i+n}{(ba)^{n-1}b} = \{k | k \leq r_i\}$.
In Figure~\ref{fig:factors}, the cut skew cylinder $\cutskewcylinder{r_i+n}{(ba)^{n-1}b}$ corresponds to the orange path.


By choice, $r_i \in \rightcutskewcylinder{0}{vb}$ and $r_i+1\in \leftcutskewcylinder{0}{vb}$ so the vertex in south-east corner of cell $r_i+n$ belongs to the cut of $\cutskewcylinder{0}{vb}$ and is preceded and followed by east steps.
Changing the start of the cut to $r_i+n$, we obtain a cyclic conjugate $bfb$ of $vb$ such that $\cutskewcylinder{0}{vb}=\cutskewcylinder{r_i+n}{bfb}$. 

Intersecting the two preceding observations, we have 
$$ \crossedleftcells{0}{vb}{r_i} = \rightcutskewcylinder{r_i+n}{(ba)^{n-1}b} \cap \leftcutskewcylinder{r_i+n}{bfb} $$
and
$$ \uncrossedrightcells{0}{vb}{r_i} = \leftcutskewcylinder{r_i+n}{(ba)^{n-1}b} \cap \rightcutskewcylinder{r_i+n}{bfb}.$$

The embedding of $(ba)^{n-1}b$ and $bfb$ both starts at the same vertex $r_i+n$.
We factorize $bfb$ at its steps which are common with those of $(ba)^{n-1}b$.
In Figure~\ref{fig:factors} at left, the steps of $bfb$ are magenta if forced and otherwise blue while the steps of $(ba)^{n-1}b$ are orange.
Hence we factorize $bfb$ at the blue (or magenta) and orange steps.
This example should help to convince the reader that $bfb=b(ba)a(aabb)b(ba)a()b$ is in general factorized as a word of $b\X a\Y(b\X a\Y)^*b$.
This factorization in non-ambiguous since the word $(ba)^{n-1}b$ is constant and the factors in $\X$ and $\Y$ are well defined. 
Conversely, any word  $w\in b\X a\Y(b\X a\Y)^*b$ such that $|w|_a\geq 2$ is almost balanced and may be written $bfb$ and is a cyclic conjugate of some word $vb$ where $v$ is a Dyck word.

Moreover, in the decomposition showing $bfb\in b\X a\Y(b\X a\Y)^*b$, the augmented area of factors in $\X$ counts the cells of $ \crossedleftcells{0}{vb}{r_i}$ and the augmented area of factors in $\Y$ counts the cells of $\uncrossedrightcells{0}{vb}{r_i}$.
On the example of $bfb=b(ba)a(aabb)b(ba)a()b$, the first factor $(ba)$ corresponds to $\{\overline{12}\} \subset \crossedleftcells{0}{vb}{r_i}$, the factor $(aabb)$ corresponds to $\{\overline{4},\overline{3},3\}=\crossedleftcells{0}{vb}{r_i}$ and the second factor $(ba)$ corresponds to $\{\overline{8}\}\subset \crossedleftcells{0}{vb}{r_i}$ and the empty factor $()$ in $\Y$ adds no cell to $\uncrossedrightcells{0}{vb}{r_i}$. 
In terms of generating function, it leads to 
$$ \sum_{v} \sum_{r_i \in \righttoleftcell{0}{vb}} \monomleftright{0}{vb}{r_i} = \frac{C(x;xz)zC(y;yz)}{1-C(x;xz)zC(y;yz)}-z $$
where $v$ runs over Dyck words of size at least $2$.
More precisely, $\frac{C(x;xz)zC(y;yz)}{1-C(x;xz)zC(y;yz)}$ is the generating function of all the almost balanced words written $bfb$ according to the augmented area of factors $\X$, counted by the variable $x$, and the augmented area of factors $\Y$, counted by the variable $y$, and the size $|bfb|_a\geq 1$ counted by $z$.
The subtracted term $z$ corresponds to the excluded almost balanced word of size $1$, $bab$.  


The proof for a cell $l_i$ is very similar and illustrated by the right example in Figure~\ref{fig:factors}.
The choice  $l_i\in \leftcutskewcylinder{0}{vb}$ and $l_i+1\in \rightcutskewcylinder{0}{vb}$  implies that the vertex $l_i+n$ belongs to the cut of $\cutskewcylinder{0}{vb}$ and is preceded and followed by north steps.
Hence when the vertex $l_i+n$ is chosen as the start of the cut, it makes appear a cyclic conjugate $afa$ of $vb$ such that $\cutskewcylinder{0}{vb} = \cutskewcylinder{l_i+n}{afa}$. 
We have 
$$ \crossedleftcells{0}{vb}{l_i} = \rightcutskewcylinder{l_i+n}{(ba)^{n-1}b} \cap \leftcutskewcylinder{l_i+n}{afa} $$
and
$$ \uncrossedrightcells{0}{vb}{l_i} = \leftcutskewcylinder{l_i+n}{(ba)^{n-1}b} \cap \rightcutskewcylinder{l_i+n}{afa}.$$
The factorization of $afa$ at the common steps of the embedding of $afa$ and $(ba)^{n-1}b$ leads to words in $(\Y-\epsilon)b(\X a\Y b)^*(\X -\epsilon)$ where the first $\Y$ factor and the last $\X$ factor are non empty due to the distinct extreme steps of these two embeded words.
Hence we have,
$$ \sum_{v} \sum_{l_i \in \lefttorightcell{0}{vb}} \monomleftright{0}{vb}{l_i} = \frac{(C(x;xz)-1)(C(y;yz)-1)}{1-C(x;xz)zC(y;yz)}$$
where $v$ runs over Dyck words of size at least $2$.

We conclude the proof by a summation following Lemma~\ref{lem:geometric-sums} to get the expected expression.
\end{proof}

\section{Enumerative byproducts related to $q,t$-Catalan numbers}
\label{sec:qt-byproducts}

In a Dyck word $v$ we denote by $a_i$ the $i$-th of the occurence of the letter $a$ in the word $v$.
The \emph{height} $\height(a_i)$ of $a_i$ is defined by $|p|_a-|p|_b$ where $v=pa_iq$ is a decomposition defining the prefix $p$. 
The letter $a_i$ and $a_j$ in the Dyck word $v$ are in \emph{$\dinv$-interaction} if either $i<j$ and $\height(a_i)=\height(a_j)$ or 
$j < i$ and $\height(a_j) = \height(a_i)+1$.
The \emph{parameter} $\dinv(v)$ of the Dyck word $v$ is the number of $\dinv$-interactions in $v$. 
Haiman, quoted by Haglund \cite{haglund}, devised this statistic to provide a combinatorial interpretation of 
$$ C_n(q,t) := \sum_{v} q^{\area(v)}t^{\dinv(v)} $$
where $v$ runs over Dyck words of size $n$.
These polynomials initially appears as Hilbert series of some space of multivariate polynomials, see again \cite{haglund} for the context.
The algebraic definition of these Hilbert series has an obvious symmetry implying that $C_n(q,t)=C_n(t,q)$.
This symmetry has still no elementary explanation in terms of the combinatorial interpretation, see \cite{Haglund2} a recent chapter due to Haglund.   

This work is not the first connection between the sandpile model and these $q,t$-Catalan numbers.
For example, in \cite{DukesLeBorgne}, one of the author with his co-author interprets on sorted recurrent configurations the pair of statistics $(\area,\bounce)$ also defining the same $q,t$-Catalan numbers.
Classicaly  the $\area$ parameter corresponds to the number of grains outside the sink.
The $\bounce$ parameter, not defined in this paper, corresponds to the cumuled elapsed time on vertices before toppling in the maximally parallel execution of the Dhar criterion which topples the sink and then once all other vertices.


Hence, the additional results of this section are strengthening the connection between the sandpile model on $K_n$ and these $q,t$-Catalan numbers. 
Subsection~\ref{subsec:dinv} shows that the parameter $\dinv$ is preserved by the map $\rrinvolutionconf$.
Subsection~\ref{subsec:zeta} details a relation between $\rrinvolutionconf$ and a map $\zeta$ due to Haglund which maps the bistatistic $(\dinv,\area)$ to the bistatistic $(\area,\bounce)$. 
Subsection~\ref{subsec:prerank} introduces the parameter $\prerank(w) := \area(\rrinvolutionconf(w))$ which appear in one of our ealy optimisation of the algorithm for the rank. 
The bistatistic $(\prerank,\dinv)$ is another possible definition of $C_n(q,t)$.


\subsection{A $\dinv$ statistic on cut skew cylinders.\label{subsec:dinv}}

The involution $\rrinvolutionconf$ on Dyck words related to the Riemann-Roch theorem for graphs preserves the $\dinv$ parameter.

\begin{proposition}\label{prop:dinvpreserved}
For any Dyck word $v$, we have $\dinv(\rrinvolutionconf(v)) = \dinv(v)$.
\end{proposition}

The postponed proof of this proposition is based on a definition of a parameter $\cdinv$ on the cylinder $\cutskewcylinder{m}{w}$ such that 
$\dinv(v)=\cdinv(\cutskewcylinder{0}{vb})$.
Then the superimposition principle will imply the proposition.

The \emph{(left-)contacts} $(c_i)_{i=1\ldots n-1}$ in the cut skew cylinder $\cutskewcylinder{m}{w}$ are the cells where $c_i$ is the smallest spiral coordinate for a left cell in the row crossed by $a_{\oriented{m}i}$.
Two distinct contacts $c_i$ and $c_j$ in $\cutskewcylinder{m}{w}$ are in \emph{$\cdinv$-interaction} if $|c_i-c_j| < n-1$.
The \emph{cyclic}-$\dinv$ parameter $\cdinv(\cutskewcylinder{m}{w})$ is the number of pairs of contacts in $\cdinv$-interaction. 

In Figure~\ref{fig:xypara-superimposition} the green spiral coordinates of contacts for $\cutskewcylinder{0}{aabaaabbabbabbb}$ are $(c_i)_{i=1\ldots n-1}=(0,8,9,17,25,19,13)$ so
$$\begin{array}{lcl}
\cdinv(v) & = & |\{\{8,9\},\{8,13\},\{9,13\},\{13,17\},\{13,19\},\{17,19\},\{19,25\} \}| = 7\\
=\dinv(v) & =& |\{\{a_{2},a_{3}\},\{a_{2},a_{7}\},\{a_{3},a_{7}\},\{a_{7},a_{4}\},\{a_{7},a_{6}\},\{a_{4},a_{6}\},\{a_{6},a_{5}\}\}|\\
\end{array}$$

\begin{proof}
The contacts $c_i$ and $c_j$ where $i<j$ are in $\cdinv$-interaction in $\cutskewcylinder{0}{vb}$ if and only if either $c_i < c_j$ and then $\height(a_i)=\height(a_j)$ so $a_i$ and $a_j$ are in the first kind of $\dinv$-interaction or $c_j < c_i$ and then $\height(a_i)=\height(a_j)+1$ so $a_j$ and $a_i$ are in the second kind of $\dinv$-interaction.
Hence $\cdinv(\cutskewcylinder{0}{vb}) = \dinv(v)$.

Then we consider the superimposition of $u=\scompact{0}{0}{vb}{s}$ and $\rrinvolutionconf.u=\scompact{0}{0}{\rrinvolutionconf(v)b}{C(vb)-s}$ like in Figure~\ref{fig:xypara-superimposition}.
We remind that the spiral green coordinate $k\in\mathbb{Z}$ of a cell corresponds to the usual spiral coordinate in $\cutskewcylinder{0}{vb}$ while the red spiral coordinate $C(w)-k$ corresponds to the coordinate in the superimposed $\cutskewcylinder{0}{\rrinvolutionconf(v).b}$. 
We consider the contact of green spiral coordinate $c_i$ in $\cutskewcylinder{0}{vb}$.
By definition, the east side of $c_i$ belongs to the cut.
The other cell at east sharing this side has green coordinate $c_i-(n-1)$ and red coordinate $d_{i'}=C(w)-c_i+(n-1)$ and is one of the contacts $(d_{i'})_{i'=1\ldots n}$ in $\cutskewcylinder{0}{\rrinvolutionconf(v)b}$.
For any other contact $c_j$, a similar proof leads to the contact $d_{j'}=C(w)-c_j+(n-1)$ in $\cutskewcylinder{0}{\rrinvolutionconf(v)b}$.
Since $d_{i'}-d_{j'} = c_j-c_i$ we deduce that $c_i$ and $c_j$ are in $\cdinv$-interaction if and only if $d_{i'}$ and $d_{j'}$ are in $\cdinv$-interaction.
Hence $\cdinv(\cutskewcylinder{0}{vb}) = \cdinv(\cutskewcylinder{0}{\rrinvolutionconf(v)b}).$

For example, in Figure~\ref{fig:xypara-superimposition} the red spiral coordinates of contacts for $\cutskewcylinder{0}{aaabaabbbabbabb}$ are $(d_j)_{j=1\ldots n-1} = (0,8,16,17,25,12,6)$ and 
\begin{align*}\{C(w)-d_j+(n-1)\}_{j=1\ldots n-1} &= \{18-d_j+7\}_{j=1\ldots n-1}\\
                          & = \{25,17,9,8,0,13,19\}\\
                       &=\{c_i\}_{i=1\ldots n-1}.\qedhere\end{align*}
\end{proof}


\subsection{A comparison of the involution $\rrinvolutionconf$ in Riemann-Roch and $\zeta$ map of Haglund\label{subsec:zeta}}

The involution $\rrinvolutionconf$ on Dyck words preserves the $\dinv$ statistic.
Haglund defined a bijective map $\zeta$ such that for any Dyck word $v$, $\dinv(v)=\area(\zeta(v))$ and $\area(v)=\bounce(\zeta(v))$ where $\bounce$ is a statistic still undefined in this paper, see \cite{haglund}.  
An anonymous referee for a conference where this work was presented \cite{coriLeBorgne2} suggested to study possible relations between the maps $\zeta$ and $\rrinvolutionconf$.
We use the notation $\R(w) := \kappa(\reverse{w})$ for a word $w$ to describe the relation we found between $\rrinvolutionconf$ and $\zeta$.
In other words, the operator $\R$ reverses the letters of $v$ and then replace each letter $a$ by a letter $b$ and each letter $b$ by a letter $a$.
\begin{proposition}
For any Dyck word $v$, we have $\zeta(\rrinvolutionconf(v)) = \R(\zeta(v))$.
\end{proposition}

The proof of this proposition is based on reformulations of the $\zeta$ map in our framework and leads to another application of the  superimposition principle.
The \emph{height vector} of a Dyck word $v$ of size $n$ is $(\height(a_i))_{i=1\ldots n}$ where we recall that $a_i$ is the $i$-th occurrence of a letter $a$ in $v$.

\begin{proof} 

We reformulate Haglund's definition of $\zeta(v)$ by the following equivalent algorithm on the height vector:

\begin{center}
\begin{minipage}{7.5cm}
\framebox{\bf Haglund's $\zeta$ map via height vector}\newline
{\bf Input:} $v$ of size $n-1$\newline
$w\leftarrow \epsilon$;\newline
For $h$ from 0 to $n$ do\newline
\_\_$\eta^{h} \leftarrow \epsilon$;\newline
\_\_For $i$ from $1$ to $n-1$ do\newline 
\_\_\_\_if $\height(a_i)=h$ then $\eta^{h}\leftarrow \eta^{h}a$ fi;\newline
\_\_\_\_if $\height(a_i)=h-1$ then $\eta^{h}\leftarrow \eta^{h}b$ fi;od;\newline 
\_\_ $w\leftarrow w\eta^{h}$;od;\newline 
{\bf Output:} $w$ ($=:\zeta(v)$);
\end{minipage}
\begin{minipage}{8cm}
\framebox{\bf Haglund's $\zeta$ map via traversal}\newline
{\bf Input:} A cut skew cylinder $\cutskewcylinder{0}{vb}$.\newline
Compute the contacts $(c_i)_i$ in each row.\newline
For $i$ from $1$ to $n-1$ do\newline
\_\_add a letter $a$ in cell $c_i$\newline
\_\_add a letter $b$ in cell $c_i+n-1$; od;\newline
$w\leftarrow \epsilon$\newline
For $k$ from $0$ to $\max_i(c_i+n-1)$ do\newline
\_\_append letter in cell $k$ to $w$, if any;od;\newline 
{\bf Output:} $w$ ($=\zeta(v)$);
\end{minipage}
\end{center} 


Haglund's definition is slightly different and a bit more trickier.
It distinguishes as particular the two degenerated loop iterations for $h=0$, where no letter $b$ can be read and for $h=1+\max_i \height(a_i)$ where no letter $a$ can be read.
Moreover it reads the height vector and the factors $\eta^{h}$ from right to left.
It is left to the reader to figure out that our definition is equivalent.


\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.8]
\draw (-6, 0) grid (11, 8.2);
\foreach \s/\x/\y/\color in {48/-5/0/black,57/-5/1/black,66/-5/2/black,75/-5/3/black,84/-5/4/black,93/-5/5/black,102/-5/6/black,111/-5/7/black,120/-5/8/blue,40/-4/0/black,49/-4/1/black,58/-4/2/black,67/-4/3/black,76/-4/4/black,85/-4/5/black,94/-4/6/black,103/-4/7/black,112/-4/8/blue,32/-3/0/black,41/-3/1/black,50/-3/2/black,59/-3/3/black,68/-3/4/black,77/-3/5/black,86/-3/6/black,95/-3/7/black,104/-3/8/blue,24/-2/0/black,33/-2/1/black,42/-2/2/black,51/-2/3/black,60/-2/4/black,69/-2/5/black,78/-2/6/black,87/-2/7/black,96/-2/8/blue,16/-1/0/black,25/-1/1/black,34/-1/2/black,43/-1/3/black,52/-1/4/black,61/-1/5/black,70/-1/6/black,79/-1/7/black,88/-1/8/blue,8/0/0/black,17/0/1/black,26/0/2/black,35/0/3/black,44/0/4/black,53/0/5/black,62/0/6/black,71/0/7/black,80/0/8/blue,0/1/0/black,9/1/1/black,18/1/2/black,27/1/3/black,36/1/4/black,45/1/5/black,54/1/6/black,63/1/7/black,72/1/8/blue,1/2/1/black,10/2/2/black,19/2/3/black,28/2/4/black,37/2/5/black,46/2/6/black,55/2/7/black,64/2/8/blue,2/3/2/black,11/3/3/black,20/3/4/black,29/3/5/black,38/3/6/black,47/3/7/black,56/3/8/blue,3/4/3/black,12/4/4/black,21/4/5/black,30/4/6/black,39/4/7/black,48/4/8/blue,4/5/4/black,13/5/5/black,22/5/6/black,31/5/7/black,40/5/8/blue,5/6/5/black,14/6/6/black,23/6/7/black,32/6/8/blue,6/7/6/black,15/7/7/black,24/7/8/blue,7/8/7/black,16/8/8/blue,8/9/8/blue,0/10/8/blue}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\s$}};}
\foreach \s/\x/\y/\color in {8/2/0/black,16/3/0/black,7/3/1/black,24/4/0/black,15/4/1/black,6/4/2/black,32/5/0/black,23/5/1/black,14/5/2/black,5/5/3/black,40/6/0/black,31/6/1/black,22/6/2/black,13/6/3/black,4/6/4/black,48/7/0/black,39/7/1/black,30/7/2/black,21/7/3/black,12/7/4/black,3/7/5/black,56/8/0/black,47/8/1/black,38/8/2/black,29/8/3/black,20/8/4/black,11/8/5/black,2/8/6/black,64/9/0/black,55/9/1/black,46/9/2/black,37/9/3/black,28/9/4/black,19/9/5/black,10/9/6/black,1/9/7/black,72/10/0/black,63/10/1/black,54/10/2/black,45/10/3/black,36/10/4/black,27/10/5/black,18/10/6/black,9/10/7/black,80/11/0/black,71/11/1/black,62/11/2/black,53/11/3/black,44/11/4/black,35/11/5/black,26/11/6/black,17/11/7/black,8/11/8/blue}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\overline{\s}$}};
}
\foreach \x in {0,1,2,3,4}{
\draw[line width=8,draw=orange,opacity=0.4,->] (-\x-0.5,-0.5) -- (-\x+9,9);
\draw[line width=2,draw=orange,opacity=1,fill=white] (-\x-0.5,-0.5) circle (0.35);
\draw node at (-\x+-0.5,-0.5) {\small{$\eta^{\x}$}};
}
\draw[line width=2,draw=blue] (1,0) -- (1,3) -- (2,3) -- (2,4) -- (3,4) -- (3,6) -- (6,6) -- (6,8) -- (9,8);
\draw[line width=2,draw=magenta] (9,8) -- (10,8);
\draw[line width=1,draw=blue,dashed] (1,0) -- (9,8);
\foreach \i/\j in {0/0,0/1,0/2,1/3,2/4,2/5,5/6,5/7}{
\draw[line width=2,draw=green] (\i+0.4,\j+0.45) -- (\i+1,\j+0.45);
\fill[line width=1,fill=white,draw=green] (\i+0.4,\j+0.45) circle (0.23);
\draw node[green] at (\i+0.4,\j+0.45) {\small{$a$}};
\draw[line width=2,draw=green,rounded corners] (\i-0.3,\j+0.8) -- (\i+0.7,\j+0.8) -- (\i+0.85,\j+0.5) -- (\i+1,\j+0.45);
\fill[line width=1,fill=white,draw=green] (\i-0.3,\j+0.7) circle (0.23);
\draw node[green] at (\i-0.3,\j+0.7) {\small{$b$}};
\draw[line width=2,draw=red] (\i+1.7,\j+0.7) -- (\i+1,\j+0.7);
\fill[line width=1,fill=white,draw=red] (\i+1.7,\j+0.7) circle (0.23);
\draw node[red] at (\i+1.7,\j+0.7) {\small{$a$}};
\draw[line width=2,draw=red,rounded corners] (\i+1,\j+0.7) -- (\i+1.2,\j+0.7) -- (\i+1.2,\j+0.45) -- (\i+2.45,\j+0.45);
\fill[line width=1,fill=white,draw=red] (\i+2.45,\j+0.45) circle (0.23);
\draw node[red] at (\i+2.45,\j+0.45) {\small{$b$}};
}
\end{tikzpicture}
\caption{Description of Haglund's $\zeta$ map via traversal of a cut skew cylinder\label{fig:zetamap}}
\end{center}
\end{figure}


In Figure~\ref{fig:zetamap}, we use the same example as Haglund (see page 50 in \cite{haglund}).
We embed our first algorithm describing the $\zeta$ map in a cut skew cylinder.
The spiral traversal visit the cells diagonals by diagonals drawn in orange.
Split diagonal by diagonal, this traversal corresponds to the nested loops on $h$ and $i$ in the algorithm defining $\zeta$ via the height vector.
We consider the cells visited during the traversal of the $h$-th diagonal supposed to define $\eta^{(h)}$.
If a cell is a contact $c_i$ in this diagonal, it means that the $a$ step in $vb$ in the same row is at height $h$ in $v$.
So it exactly corresponds to adding a letter $a$ to $\eta^{(h)}$.
We mark such a cell by a \emph{green} letter $a$ in the cell $c_i$.
If a cell is $c_j+(n-1)$ where $c_j$ is a contact, it  means that the $a$ step in $vb$ in the same row is at height $h-1$ in $v$.
So it exactly corresponds to adding a letter $b$ in $\eta^{(h)}$.
We mark such a cell by a \emph{green} letter $b$ in the cell $c_j+(n-1)$.
Since the traversal of the diagonal respect the order of the inner loop on $i$ in the algorithm, we deduce that $\eta^{(h)}$ is also define by the order in which the preceding cells $c_i$ or $c_j+(n-1)$ are visited.
These observation should convince the reader that the second algorithm entitled ``Haglund's $\zeta$ map via traversal'' also defines the $\zeta$ map.
On the example, collecting the \emph{green} letters on each orange diagonal leads to $\eta^{(0)} = a$,$\eta^{(1)}=baa$, $\eta^{(2)}=baaaba$,$\eta^{(3)}=bbbab$ and $\eta^{(4)}=b$. 

\medskip

We reformulated the definition of $\zeta$ into a spiral traversal since it is well suited for the superimposition principle.
The proof is similar to the proof of Proposition~\ref{prop:dinvpreserved} that $\rrinvolutionconf$ preserves the $\dinv$ parameter.
We keep only the (green) spiral coordinates here.
The vertical step defining the contact $c_i$ in $vb$ shows that $\zeta(v)$ add a letter $a$ in cell $c_i$ and a letter $b$ in cell $c_i+(n-1)$.
But this vertical step also appears in $\rrinvolutionconf(v)b$ and in the computation of $\zeta(\rrinvolutionconf(v))$, we add a (red) letter $a$ in cell $c_i-(n-1)$ and a letter (red) $b$ in cell $c_i-2(n-1)$.  
Moving the red letters two west steps and exchanging the red letters $a$ and $b$ on each row leads exactly to the position of the green letters.
Then inspection shows that the reversed traversal in the computation of $\zeta(\rrinvolutionconf(v))$ leads also to $\R(\zeta(v))$.
\end{proof}

\subsection{A $\prerank$ statistic so that $(\prerank,\dinv)$ defines expected $q,t$-Catalan\label{subsec:prerank}}


The \emph{prerank} of a Dyck word $v$ is $$\prerank(v) := \area(\rrinvolutionconf(v)).$$

\begin{proposition}
For any $n\geq 0$, we have 
$$ C_n(q,t) := \sum_{v} q^{\dinv(v)}t^{\area(v)} = \sum_{v} q^{\dinv(v)}t^{\prerank(v)}$$
where $v$ runs over Dyck words of size $n$.
\end{proposition}

\begin{proof}
The involution $\rrinvolutionconf$ satisfies $\prerank(v)=\area(\xi(v))$ and $\dinv(v)=\dinv(\rrinvolutionconf(v))$.
\end{proof}

We call this parameter prerank because of an early partial optimization of our algorithms computing the rank.
A \emph{staircase} (sorted parking) configuration $u$ on $K_n$ is such that for $i\neq n$, $u_i=i-1$ and there are no restriction on $u_n$.
Any staircase configuration may be written $u=\scompact{m}{m}{(ab)^{n-1}b}{s}$.
Applying $8.$ in Proposition~\ref{prop:convert}, we have $\sort(\park(u-\onechipconf{1}))=\scompact{m+1}{m+1}{(ab)^{n-1}b}{s-1}$ which is also a staircase configuration. 
By induction, we have $$\rank(\scompact{m}{m}{(ab)^{n-1}b}{s}=\max(-1,s).$$
Hence one may accelerate the algorithm computing the rank as soon as we reach a staircase configuration.
It appears that, if $s$ is big enough, the number of loops before we reach such a staircase configuration is finite and is exactly the prerank of the initial Dyck word in the cut $vb$.

%\bibliography{references.bib}
%\bibliographystyle{plain}

\begin{thebibliography}{99}

\bibitem{aminiManjunath}
O.~Amini and M.~Manjunath.
\newblock Riemann-{R}och for sub-lattices of the root lattice $a_n$.
\newblock {\em Electron. J.  Combin.}, 17:R124, 2010.

\bibitem{ADDHL}
Jean-Christophe Aval, Michele D'Adderio, Mark Dukes, Angela Hicks, and Yvan
  Le~Borgne.
\newblock Statistics on parallelogram polyominoes and a {$q,t$}-analogue of the
  {N}arayana numbers.
\newblock {\em J. Combin. Theory Ser. A}, 123:271--286, 2014.

\bibitem{backman}
S.~Backman.
\newblock Riemann-{R}och theory for graph orientations.
\newblock \arxiv{1401.3309}, 2014.

\bibitem{bakTang1}
P.~Bak, C.~Tang, and K.~Wiesenfeld.
\newblock Self-organized criticality: An explanation of 1/f noise.
\newblock {\em Phys. Rev Letters}, 59:381--384, 1987.

\bibitem{bakTang2}
P.~Bak, C.~Tang, and K.~Wiesenfeld.
\newblock Self-organised criticality.
\newblock {\em Physical Review A.}, 38:364--374, 1988.

\bibitem{bakerNorine}
M.~Baker and S.~Norine.
\newblock Riemann-{R}och and {A}bel-{J}acobi theory on a finite graph.
\newblock {\em Advances in Mathematics}, 215:766--788, 2007.

\bibitem{bakerShokrieh}
M.~Baker and F.~Shokrieh.
\newblock Chip-firing games, potential theory on graphs, and spanning trees.
\newblock {\em J. Combin. Theory Ser. A}, 120:164--182, 2013.

\bibitem{bensonChakTetali}
B.~Benson, D.~Chakrabarty, and P.~Tetali.
\newblock G-parking functions, acyclic orientations and spanning trees.
\newblock {\em Discrete Mathematics}, 310:1340--1353, 2010.

\bibitem{biggs1}
N.~Biggs.
\newblock Chip-firing and the critical group of a graph.
\newblock {\em J. Algebraic Combin.}, 9:25--45, 1999.

\bibitem{BjoLovShor}
A.~Bj{\"o}rner, L.~Lov\'asz, and P.Shor.
\newblock Chip-firing game on graphs.
\newblock {\em European J. Combin.}, 12:283--291, 1991.

\bibitem{coriLeBorgne1}
R.~Cori and Y.~Le {B}orgne.
\newblock The sand-pile model and {T}utte polynomials.
\newblock {\em Advances in App. Math.}, 30:44--52, 2003.

\bibitem{coriLeBorgne2}
R.~Cori and Y.~Le {B}orgne.
\newblock On ranks of configurations on the complete graph.
\newblock {\em DMTCS Proceedings, 25th International Conference on Formal Power
  Series and Algebraic Combinatorics (FPSAC 2013)}, 2013.

\bibitem{coriRossin}
R.~Cori and D.~Rossin.
\newblock On the sandpile group of dual graphs.
\newblock {\em European J. Combin.}, 21:447--459, 2000.

\bibitem{dhar2}
D.~Dhar.
\newblock Self-organized critical state of the sandpile automaton models.
\newblock {\em Phys. Rev. Lett.}, 64:1613--1616, 1990.

\bibitem{dharIntro}
D.~Dhar.
\newblock Theoretical studies of self-organized criticality.
\newblock {\em Physica A}, 369 (1), 2006.

\bibitem{dharMajumdar}
D.~Dhar and S.~Majumdar.
\newblock Equivalence between the {A}belian sandpile model and the $q
  \rightarrow 0$ limit of the {P}otts model.
\newblock {\em Physica A}, 185:129--135, 1992.

\bibitem{dhar1}
D.~Dhar and R.~Ramaswamy.
\newblock Exactly solved model of self-organized critical phenomena.
\newblock {\em Phys. Rev. Lett.}, 63:1659--1662, 1989.

\bibitem{dharRuelleVerma}
D.~Dhar, P.~Ruelle, S.~Sen, and D.~Verma.
\newblock Algebraic aspects of abelian sandpile model.
\newblock {\em J. Phys. A}, A28:805--831, 1995.

\bibitem{DukesLeBorgne}
Mark Dukes and Yvan Le~Borgne.
\newblock Parallelogram polyominoes, the sandpile model on a complete bipartite
  graph, and a {$q,t$}-{N}arayana polynomial.
\newblock {\em J. Combin. Theory Ser. A}, 120(4):816--842, 2013.

\bibitem{dvoMotzk}
A.~Dvoretsky and T.~Motzkin.
\newblock A problem of arrangements.
\newblock {\em Duke Math. J.}, 14:305--313, 1947.

\bibitem{farkasKra}
H.~M. Farkas and I.~Kra.
\newblock {\em Riemann Surfaces}.
\newblock Graduate {T}exts in {M}athematics, {Springer}, 1992.

\bibitem{kramersWannier}
Kramers H. and Wannier C.
\newblock Statistics of the two-dimensional ferromagnet. part {I}.
\newblock {\em Physical Review}, 60:252--262, 1941.

\bibitem{haglund}
J.~Haglund.
\newblock {\em The $q,t$-Catalan numbers and the space of diagonal harmonics}.
\newblock AMS University Lectures Series, 2008.

\bibitem{Haglund2}
Jim Haglund.
\newblock {\em Handbook of Enumerative Combinatorics}, chapter Catalan Paths
  and $q,t$-Enumeration.
\newblock 2015.

\bibitem{kisstothmeresz}
V.~Kiss and L.~Th\'othm\'er\'esz.
\newblock Chip-firing games on eulerian digraphs and np-hardness of computing
  the rank of a divisor on a graph.
\newblock \arxiv{1407.6958}, 2014.

\bibitem{knuthVol4}
D.~E. Knuth.
\newblock {\em The art of Computer Programming, Volume 4 Combinatorial
  Algorithms, Fasc 4A}.
\newblock Addison Wesley, 2004.

\bibitem{leborgne}
Yvan Le~Borgne.
\newblock Counting upper interactions in {D}yck paths.
\newblock {\em S\'em. Lothar. Combin.}, 54:Art. B54f, 16 pp. (electronic),
  2005/07.

\bibitem{lorenzini}
D.~Lorenzini.
\newblock Two-variable zeta-functions on graphs and riemann-roch theorems.
\newblock {\em Int. Math. Res. Notices.}, 2012,22:5100--5131, 2012.

\bibitem{merinoLopez}
C.~Merino-{L}opez.
\newblock Chip firing and {T}utte polynomials.
\newblock {\em Ann. Combin.}, 3:253--259, 1997.

\bibitem{mikhalkinZharkov}
Grigory Mikhalkin and Ilia Zharkov.
\newblock Tropical curves, their {J}acobians and theta functions.
\newblock In {\em Curves and abelian varieties}, volume 465 of {\em Contemp.
  Math.}, pages 203--230. Amer. Math. Soc., Providence, RI, 2008.

\bibitem{perkPerlWilm}
D.~Perkinson, J.~Perlman, and J.~Wilmes.
\newblock Primer for the algebraic geometry of sandpiles.
\newblock  \arxiv{1112.6163}, 2011.

\end{thebibliography}


\section{Annex: A proof of the Riemann Roch Theorem  for graphs}

\newcommand{\fort}{\ \longrightarrow \ }
\newcommand{\faible}{\parbox[c]{28pt}{\begin{picture}(28,0)(0,0) 
\multiput(4,0)(5,0){3}{\line(1,0){3}}
\put(19,0){\vector(1,0){4}}
\end{picture}}}

\newcommand{\rc}[3]{\textcolor{blue}{[#1]}\textcolor{red}{[#2]}\textcolor{green}{[#3]}}
\newcommand{\fortht}[1]{{\stackrel{#1}{\makebox[3pt]{} 
\longrightarrow \makebox[1pt]{} }}}

\newcommand{\faibleht}[1]{{\stackrel{#1}{\makebox[3pt]{} 
\faible \makebox[1pt]{} }}}

\newcommand{\vufaible}{{\stackrel{*}{\faible}}}
\newcommand{\vufort}{{\stackrel{*}{\ \longrightarrow \ }}}
\newcommand{\simil}{\sim_{L_G}}

\newcommand{\eps}{\varepsilon}
\newcommand{\deltaB}{\overline{\delta}}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Del}[1]{\Delta^{(#1)}}
%\newcommand{\f}{f(z,u,v)}
\newcommand{\Sn}[1] {{\mathcal S}_{#1}}

\newcommand{\Snp}[1]{{\mathbb S}_{#1}}
\newcommand{\etoile}{\stackrel{*}{\rightarrow}}
\newcommand{\mult}[1]{\left(
\begin{array}{c}
#1 \\
d_1 \ldots d_k
\end{array}
\right)
}





We consider the following solitary  game on an undirected (non oriented) connected graph $G=(X,E)$ without loops:
at the beginning  integer  values $f_i$ are attributed to the $n$ vertices 
$x_1, x_2, \ldots x_n$ of the graph, these  values can be positive
or negative and define a configuration $f$. At each step a toppling can be performed by the player on a vertex $x_i$, it consists
in subtracting $d_i$ (the number of edges incident to $x_i$) to the amount $f_i$ and for each neighbor  $x_j$ of $x_i$  increase $f_j$  by the number of edges between these two vertices.
In this operation the amount of vertex $x_i$ may become, or stay negative. The aim of the 
player is to find  a sequence of toppling operations  which will 
end with a configuration where all the $f_i$ are non negative.   Since the sum  of the $f_i$ is invariant by  toppling, a necessary
condition to succeed is that in the initial configuration this sum should be non negative. We will see that 
this condition is not sufficient.


This game has much to do with the chip firing game (see \cite{BjoLovShor}, \cite{biggs1})
and the sandpile model  (see \cite{bakTang2},  \cite{dharIntro},  \cite{dharMajumdar}), for which  recurrent configurations 
where  defined and proved to be canonical representatives of the classes 
of configurations equivalent by a sequence of  topplings (for a more algebraic treatment see also \cite{perkPerlWilm}).


The game  was introduced and studied in detail by Baker and Norine in \cite{bakerNorine}
who also introduced a new parameter on graph configurations: the rank.  One characteristic of the 
rank $\rho(f)$ of a configuration  $f$
is that it is non negative if and only if one can get from $f$ a configuration non-negative on every vertices by performing
a sequence of topplings.
For this parameter they obtain a simple formula expressing a symmetry
similar to  the Riemann-Roch formula for surfaces and curves (a classical reference to this formula is
the book by H. Farkas and I. Kra \cite{farkasKra}).

Our aim here is to give a simple  presentation of this Riemann-Roch like theorem for graphs.
It's wortwhile in this context to mention the independant work of Backman~\cite{backman} and the precedings works~\cite{mikhalkinZharkov,aminiManjunath}. 


\subsection{Configurations on a graph}





Let $G= (X, E)$ be a multi-graph with $n$ vertices, where $X =\{x_1,x_2, \ldots, x_n\}$
is the vertex set and $E$ is a symmetric matrix such that $e_{i,j}$
is the number of edges with endpoints $x_i, x_j$, hence
$e_{i,j} = e_{j,i}$. In all this paper  $n$ denotes
the number of vertices of the graph $G$ and $m$ the number of its edges.
We  assume that $G$ is connected and 
has no loops, so that $e_{i,i}=0$ for all $i$.




We will consider {\em configurations} on a graph,  these  are  elements of 
the discrete lattice $\Z^n$.  Each configuration $f$ may be considered as 
assigning (positive or negative) tokens to the vertices.
The symbol $\eps^{(i)}$ 
will   denote the configuration in which the value 1
is assigned to vertex $x_i$ and the value 0 is assigned to all other vertices.

The  {\em degree} of the configuration $f$ is the sum
of the $f_i$'s it  is denoted by  $deg(f)$. 

\subsubsection{The Laplacian configurations}
These configurations correspond to the  rows of the Laplacian 
matrix of a graph, a classical tool in Algebraic Graph Theory.

The  {\em Laplacian configuration} $\Del{i}$ is given by:
$ \Del{i} = d_i \eps^{(i)}- \sum_{i=1}^n e_{i,j}\eps^{(j)}$, 
where   $d_i = \sum_{i=1}^n e_{i,j}$ is the degree of the vertex $x_i$.
These  configurations which degrees are equal to 0  play a central role.




We denote by  
 $L_G$ the subgroup of  $\Z^n$
 generated by the $\Del{i}$, and two configurations $f$ and $g$ will be said 
{\em toppling equivalent} if $f -g\in L_G$, which will also be written as
$ f \simil g$.


In the sandpile model, the transition from 
configuration $f$  to  the configuration $f- \Del{i}$ is allowed only if $f_i \geq d_i$ and is called a toppling. The
same condition is assumed  in the theory of chip firing games, and toppling is called firing; here we omit this condition and perform topplings even
if $f_i < d_i$.


Notice that $\sum_{i=1}^n \Del{i} = 0$ and that for a connected graph 
this is the unique relation (up to multiplication by a constant) satisfied by the $\Del{i}$, moreover 
the principal minors of the Laplacian matrix are all equal to the number of spanning trees
of the graph.

\subsubsection{Recurrent configurations}
We use in this section  the notation usually considered in the sandpile model, so that we will call
{\em sandpile configuration} a configuration $f$ such that $f_i \geq 0$ for all
$i < n$. This corresponds to the fact that in the sandpile model the vertex $x_n$ is 
considered as a sink collecting tokens, so that  the number of tokens of the sink  has not taken into account
in this context. 

\begin{definition}
\label{def:toppling}
In the sandpile model, a toppling on vertex $x_i$, where $i \neq n$, may occur in 
a sandpile configuration only  if $f_i \geq d_i$. A sandpile configuration $f$ is stable if no toppling can occur, that is
$f_i < d_i$ for all $i <n$.
\end{definition}
Notice that when a toppling occurs in the sandpile model, the configuration 
 $f - \Del{i}$ is  also a sandpile configuration.

The toppling  operation for a sandpile configuration will be denoted
by $ f \rightarrow g$.
We also write:
$$ f \etoile g$$ if $f$ and $g$ are sandpile configurations 
and if $g$ is obtained from $f$ by a sequence 
of  toppling operations meeting only sandpile configurations.  Notice that $ f \etoile g$ implies $ f \simil g$.

%\medskip


Sequences of topplings may be performed in any order
until a stable configuration is attained as the following proposition 
states, the proof of which may be found in \cite{dhar1} or in \cite{knuthVol4} pages 42, and 70.

\begin{proposition}
\label{prop:uniqueStable}
For any sandpile configuration $f$ there exists a unique
stable configuration  $f'$  such that $f \etoile f'$.
\end{proposition}





%\medskip
A configuration is {\em recurrent} in an evolving system if it could be
observed after a long period of the evolution of the system. In the
case of the  sandpile model, the system is considered to evolve
by adding a token in any cell at random and then applying 
topplings  until a stable configuration is reached. This
translates into the  following notion which is  central~:

\begin{definition}
\label{def:recurrent}
A configuration $f$ is recurrent if it is stable and
 there exists a sandpile  configuration $g \neq 0$ such that $f +g \vufort
f$.
\end{definition}

%\medskip

\noindent
The following  important result, giving canonical representatives in the classes of the 
relation  $\simil$  is obtained in \cite{dhar2, biggs1, coriRossin} by different ways.


\begin{theorem}
For any configuration $f$ there exists a unique recurrent configuration $g$ such that
$ f \simil g$.
\end{theorem}






%\medskip

In order to characterize the recurrent configurations D. Dhar
used  the configuration $\Del{n}$ and proposed the following algorithm.




\begin{theorem}{\rm Burning Algorithm.}
\label{cor:burning}
A stable  configuration $u$ is recurrent if and only if
$$f - \Del{n} \vufort f$$
Moreover in this sequence of topplings each vertex different from  $x_n$ topples exactly
once.
\end{theorem}

\noindent
This algorithm can be translated into  another characterization, giving:


\begin{corollary}
\label{cor:caracRecur}
A stable configuration $f$ is recurrent if and only if for any non-empty subset
$Y$ of $X \setminus \{x_n\}$ there is at least  an $x_k$ in $Y$ such that
its  degree in the subgraph spanned by $Y$ is not greater
than $f_k$, more precisely if the following condition is satisfied:
\begin{equation}
\label{eq:antiParking}
f_k \geq  \sum_{x_i\in Y} e_{i,k} 
\end{equation}
\end{corollary}

\begin{proof}Let $f$ be a recurrent configuration, and $Y$ be a subset of $X$,  then by Dhar's Burning Algorithm,
starting from the configuration $f- \Del{n}$ 
there is a sequence of topplings 
 of the vertices  in which any vertex topples. We may 
suppose that the vertices are numbered 
in the order in which they topple, $x_1$ just after $x_n$,
then $x_2$ and so on until
$x_{n-1}$ then for allowing a toppling at
 vertex $x_i$ each $f_i$ has to satisfies the condition:
$$ d_i \leq f_i + \sum_{j=1}^{i-1}  e_{i,j}$$ 
Now for any subset   $Y$ of $X$,
let $k$ be the smallest integer such that $x_k \in Y$, then since there
is no $x_i\in Y$ with $i$  less than $k$ we have:
$$ d_k \geq  \sum_{j=1}^{k-1}  e_{j,k} +   \sum_{x_i\in Y} e_{i,k}$$
Putting  $i=k$ in the first inequality and the two inequalities together gives the result.


%\medskip
Conversely if $f$ is a stable configuration satisfying 
condition \ref{eq:antiParking}  we build a toppling sequence 
starting with vertex $x_n$, then taking as $x_1$ the vertex in $Y=\{x_1, x_2, \ldots, x_{n-1}\}$ satisfying $f_1 \geq \sum_{i=2}^{n-1} e_{1,i}$, this vertex can 
topple after $x_n$ 
 since in that case $f_1 + e_{1,n} \geq \sum_{i=2}^{n} e_{1,i}= d_1$.
Then at each step, a  vertex $x_j$ such that
  $f_j \geq \sum_{i=j+1}^{n-1} e_{i,j}$ exists taking $Y = X \setminus
\{x_n, x_1, x_2, \ldots x_{j-1}\}$, this vertex can topple at this stage.
We have thus built a sequence of toplings proving that $f$ is recurrent.
\end{proof}






\subsubsection{Parking configurations}
\label{sec:ParkingConf}
We consider a kind of dual notion to that of  recurrent configuration,
  such configurations are often called
 {\em parking configurations} since in the case of complete
graphs, these are exactly the parking functions, a  central object in combinatorics.

\begin{definition}
\label{def:parking}
A sandpile configuration $f$ on a graph $G$ is a  parking configuration if
for any subset $Y$ of
$X\setminus \{x_n\}$ there is a vertex $x_k$ in $Y$ such that 
$f_k$ is less than the number of edges which are incident to $x_k$ and a vertex out of $Y$.
 More precisely if the exists  $x_k \in Y$  such that 
$ f_k<  \sum_{x_i \notin Y} e_{i,k}$.
\end{definition}

In other words  a sandpile configuration $f$ 
is a  parking configuration if and only if 
 there is no 
toppling of all the vertices in a subset $Y$ of $\{x_1, x_2, \ldots x_{n-1}\}$ leaving all the  $f_i \geq 0$.
For this reason these configurations are also called {\em superstable} (as for instance in \cite{perkPerlWilm}).

\begin{proposition}
\label{prop:recToParking}
Let $f$ be a stable configuration and let $\delta $ be the configuration such 
that $\delta_i = d_i - 1$. Define $\beta(f) =  \delta- f$. Then $f$ is recurrent if and only if $\beta(f)$
is a parking configuration.
\end{proposition}
\begin{proof}
It suffices to compare Corollary \ref{cor:caracRecur} and Definition  \ref{def:parking}
and to notice that:
\[ d_k = \sum_{x_j\notin Y} e_{k,j} + \sum_{x_j\in Y} e_{k,j} \qedhere\]
\end{proof}
\begin{corollary}
\label{prop:caracParking}
For any configuration $f$ there exists a unique parking configuration
$g$  such that $f \simil g$.
\end{corollary}

\begin{proof}
For any  configuration $f$  let $g$ be the recurrent configuration such that 
$g \simil \delta - f $ then $ \beta(g)$ is a parking configuration such that $ f \simil  \beta(g)$.
\end{proof}

In this paper we will often consider the parking configuration  in a class as a representative of this class.
A parking configuration $f$  in a graph with $n$ vertices will be represented by the subsequence  consisting of this first $n-1$ terms
and an integer $s$  such that:

\begin{equation}
\label{eq:defParking}
(f_1, f_2, \ldots, f_{n-1}) {\hskip 1cm}   s = f_n
\end{equation}

\noindent 
hence $s$ represents the number of tokens on the distinguished often called  " sink " vertex $x_n$. 


{\bf Parking configurations and acyclic orientations}

An orientation of $G$ is a directed graph obtained from $G$ by
orienting each edge, so that one end vertex becomes  the head and the
other one  the tail.  A directed path in such a graph
consists of a sequence of edges such that the head of an edge is
equal to the tail of the subsequent one.

The orientation is acyclic if
there is no directed circuit, i.e. a directed 
path starting and ending at the same
vertex. We associate to any parking configuration $f$
an acyclic orientation by :

\begin{proposition}
\label{prop:parkingToAcyclic}
For any parking configuration $f$ on $G=(X,E)$ there exists
at least one  acyclic orientation $\overrightarrow{G}$ such that for any vertex $x_i$,
 $i\neq n$, $f_i$  is strictly less  than its 
indegree $d^{-}_i$ (i.e. the number of edges with head $x_i$).
\end{proposition}

\begin{proof}
We orient the edges using an algorithm that terminates after $n$ steps.
Consider $Y = \{x_1,x_2, \ldots, x_{n-1}\}$. From the definition of 
 parking configurations, 
there is at least one vertex $x_i$ such that 
$f_i < e_{i,n}$ then orient all  these $e_{i,n}$
 edges from $x_n$ (the tail) to $x_i$ (the head), and remove $x_i$ from $Y$.
Repeat the following operation until $Y$ is empty:
   \begin{itemize}
\item Find $x_k$ in $Y$ such that $f_k < \sum_{x_j \notin Y} e_{k,j}$; orient all the edges joining any vertex $j$ 
outside $Y$ to $x_k$  from $x_j$ to $x_k$ and remove $x_k$ from $Y$.\qedhere
\end{itemize}
\end{proof}
In the preceding proof one may recognize a scheduling of topplings related to the Dhar criterion applied to the recurrent configuration $\beta(f)$.
Notice that more precise results involving maximal parking configurations are given in \cite{bensonChakTetali}.
  
  
  
 
   
\subsection{Effective configurations}
In this section we define the 
notion of $L_G$-effective configuration and recall the main results of \cite{bakerNorine},  the proofs we give in this section are more 
or less a reformulation in our terms  of the proofs of them given in \cite{bakerNorine}.
The game described in the introduction can be translated 
in determining if a configuration is $L_G$-effective with the following definition of effectiveness:
\begin{definition}
\label{def:effective}
A configuration $f$ is effective if 
$f_i \geq 0 $ for all $i$.
A configuration $f$  is $L_G$-effective if there exists an effective 
configuration $g$ toppling equivalent to $f$ (recall that this means $f -g \in L_G$). 
\end{definition}

Since two   equivalent configurations by $\simil$  have the same degree,
it is clear that a configuration with negative degree
is not $L_G$-effective. However we will prove that  configurations
with positive degree are not necessarily $L_G$-effective as these two 
examples show:

\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale =0.8]

\tikzstyle{sommet}=[circle,draw=blue!50,thick,
                   inner sep=0pt,minimum size=6mm]
\foreach \x/\y/\name/\value in {0/0/q0/1,2/2/q1/1,4/0/q2/2,2/4/q3/0,0/6/q4/{\footnotesize -1},4/6/q5/0}{
\node[sommet] (\name) at (\x,\y) {\small $\value$};
}
\foreach \source/\dest in {q0/q1,q2/q0,q2/q1,q3/q1,q4/q0,q4/q3,q4/q5,q5/q3,q5/q2}{
\draw[draw=red,line width=2] (\source) to (\dest);
}

\foreach \x/\y/\name/\value in {0/0/q0/1,2/2/q1/0,4/0/q2/2,2/4/q3/1,0/6/q4/-1,4/6/q5/0}{
\node[sommet] (\name) at (8 +\x,\y) {\small $\value$};
}
\foreach \source/\dest in {q0/q1,q2/q0,q2/q1,q3/q1,q4/q0,q4/q3,q4/q5,q5/q3,q5/q2}{
\draw[draw=red,line width=2] (\source) to (\dest);
}
\end{tikzpicture}

\caption{An $L_G$-effective configuration and a non $L_G$-effective one}
\label{fig:effectConfig}

\end{center}
\end{figure} 

\subsubsection{Configuration associated to an acyclic orientation of $G$}

As already seen in Section \ref{sec:ParkingConf} an orientation of $G$ is a directed graph obtained from $G$ by orienting
each edge, that is distinguishing for each edge with end points $x_i$ and
 $x_j$ which one is the head and the other being the tail.
 The orientation is acyclic if
there is no directed circuit.  Let $\overrightarrow{G}$ be an acyclic orientation of $G$, we define
the configuration $C(\overrightarrow{G})$ by: 
$$ (C(\overrightarrow{G}))_i = d_i^{-} -1$$
Where $ d_i^{-}$ is the number of edges  which have  head  $x_i$.

Notice that for any acyclic orientation $\overrightarrow{G}$ we have:
$$deg( C(\overrightarrow{G})) = \sum_{i=1}^n (d_i{^-} -1) = m -n$$
 The configuration represented in the right of 
  Figure \ref{fig:effectConfig} is equal to $C(\overrightarrow{G})$ for the orientation 
of $G$ represented  in  Figure \ref{fig:acycOrient}.


\begin{figure}[ht!]




\begin{center}
\begin{tikzpicture}[scale =0.8]

\tikzstyle{sommet}=[circle,draw=blue!50,thick,
                   inner sep=0pt,minimum size=6mm]
\foreach \x/\y/\name/\value in {0/0/q0/1,
2/2/q1/0,
4/0/q2/2,
2/4/q3/1,
0/6/q4/-1,
4/6/q5/0}{
\node[sommet] (\name) at (\x,\y) {\small $\value$};
}
\foreach \source/\dest in {q0/q2,q1/q0,q1/q2,q3/q1,q4/q0,q4/q3,q4/q5,q5/q3,q5/q2}{
\draw[draw=red,->,line width=2] (\source) to (\dest);
}
\end{tikzpicture}


\caption{An orientation of $G$ and the corresponding  configuration}
\label{fig:acycOrient}
\end{center}
\end{figure}



\begin{proposition}
\label{propo:acyclicNonEffective}
The configuration associated to an acyclic orientation of $G$ is 
not $L_G$-effective.
\end{proposition}

\begin{proof}
Let $ \overrightarrow{G}$ be an acyclic orientation of $G$ and $f= C(\overrightarrow{G})$.
We will show that for any linear combination $g = \sum_{i=1}^n a_i \Del{i}$
the sum $h$ of $g$ and $f$  is not an effective   configuration.
Let $\varepsilon_{i,j}$ denote the number of edges with head $x_j$ and tail
$x_i$ in $ \overrightarrow{G}$. Then $e_{i,j} = \varepsilon_{i,j} + \varepsilon_{j,i}$ (but notice
that since the orientation is acyclic, at least one of the two values in the sum above is 
equal to 0).

For any vertex $x_i$ of $G$ we have $d_i^{-} = \sum_{j=1}^n \varepsilon_{j,i}$
so  that: 
$$ h_i = -1 + \sum_{j=1}^n \varepsilon_{j,i} + a_id_i - \sum_{j=1}^na_je_{i,j}$$
Using $d_i = \sum_{j=1}^n e_{j,i}$ and decomposing each $e_{i,j}$ into
$\varepsilon_{i,j} + \varepsilon_{j,i}$ gives for any $i$:

\begin{equation}
h_i = -1 + \sum_{j=1}^n \varepsilon_{j,i} + a_i\sum_{j=1}^n (\varepsilon_{i,j} + \varepsilon_{j,i})  - \sum_{j=1}^na_j(\varepsilon_{i,j} + \varepsilon_{j,i})
\end{equation}

 
Separating the edges for which $x_i$ is a head in $ \overrightarrow{G}$ form those for which it is a tail, we get:

\begin{equation}
h_i = -1 + \sum_{j=1}^n (1+a_i-a_j)\varepsilon_{j,i} 
+ \sum_{j=1}^n (a_i-a_j) \varepsilon_{i,j} 
\end{equation}
Now take $i$ be such that $a_i \leq j$ for all $j \neq i$, we have $a_i - a_j\leq 0$ and  $1+ a_i- a_j\leq 1$.
If there is a unique minimal value in the sequence  $a_j$ we have $1 + a_j - a_i \leq 0$, hence $h_i <0$.

 
If there are many $a_i$'s attaining the minimal value take $k$ among them 
such that  $\varepsilon_{j,k} = 0$ for all the  $j$ such that $ a_j = a_k$.
The existence of such a $k$ follows from the acyclicity of
$\overrightarrow{G}$. Then for this $k$ we have $h_k < 0$.
\end{proof}








\subsubsection{Characterization of $L_G$-effective configurations}

We can see that computing the  parking configuration toppling equivalent 
to a given configuration allows to determine if it is effective since we have

\begin{proposition}\label{prop:eff_on_park}
A configuration $f$ is $L_G$-effective if and only if the parking 
configuration $g$ equivalent to $f$ is such that $g_n \geq 0$.
\end{proposition}
\begin{proof}
If $g_n \geq0$ $g$ is effective so that $f$ is $L_G$-effective.
If $f$ is $L_G$-effective then there exists an effective configuration $h$ 
such that $f \simil h$. Then $g$ is the unique parking configuration such that $h \simil g$,
it may be obtained form $h$ performing subset topplings. These do not decrease the value of
$h_n$, hence $g_n \geq h_n \geq 0$. 
\end{proof}


The following Theorem is the central result in \cite{bakerNorine}.

\begin{theorem}
\label{th:caracEffective}
For any configuration $f$ one and only one of the following 
assertions is satisfied:

(1) $f$ is $L_G$-effective

(2) There exists an acyclic orientation $\overrightarrow{G}$ such that
$C(\overrightarrow{G}) - f$ is $L_G$-effective.

\end{theorem}

\begin{proof}
 Let $f$ be non $L_G$-effective,  consider the parking configuration $g$ equivalent to $f$
 and let $\overrightarrow{G}$ be the acyclic orientation given by Proposition  \ref{prop:parkingToAcyclic}, let
$h= C(\overrightarrow{G}) -g$. Then for $i \neq n$ we have
$$ h_i =  d_i^- - 1 - f_i \geq 0$$
and since $g_n <0$:
$$ h_n = -1 + g_n \geq 0.$$

Hence $h$ is effective, moreover  since $f$ and $g$ are  in the same class, so are 
$C(\overrightarrow{G}) - f$ and $C(\overrightarrow{G})- g=h$ showing that
$C(\overrightarrow{G}) - f$ is $L_G$-effective.

%\medskip
Notice that 
$f$ and $C(\overrightarrow{G}) - f$ cannot be both $L_G$-effective since
their sum $C(\overrightarrow{G})$ would be too, contradicting 
Proposition \ref{propo:acyclicNonEffective}.
\end{proof}

\begin{corollary}
\label{cor:effectiveIfLargeDegree}
Any configuration $f$ with degree greater than $m-n$ is $L_G$-effective.
\end{corollary}

\begin{proof}
If $f$ such that $deg(f) > m-n $ is not $L_G$-effective, by the above 
theorem there exists an acyclic orientation $\overrightarrow{G}$ of $G$ 
such that $C(\overrightarrow{G})- f$ is.
But the degree of this configuration is negative, giving a contradiction.
\end{proof}



\subsection{The rank of configurations}


From now on it will be convenient to denote effective configurations 
using greek letters  $\lambda, \mu$ and configurations with no particular
assumptions on them by letters $f, g, h$.


\subsubsection{Definition of the rank}

\begin{definition}
\label{def:rank}
The rank $\rho(f)$ of a configuration $f$ is the integer equal to:
\begin{itemize}
\item  $-1$, if $f$ is non $L_G$-effective,

\item  or, if $f$ is  $L_G$-effective, the largest integer $r$
such that for any effective 
configuration $\lambda$ of degree $r$ the configuration $f-\lambda$ is $L_G$-effective.
\end{itemize}
\end{definition}

Denoting   {$  \mathbb{P}$} the set of effective  configurations  and 
  {$ \mathbb{E}$} the set of $L_G$-effective  configurations this definition
 can be given by the following compact formula which is valid in both 
cases:
$$ \rho(f) +1 = \min_{\displaystyle \lambda \in \mathbb{P},  f- \lambda\notin \mathbb{E} }\ \ \  deg(\lambda)$$


In other words let $f$ be a configuration of rank $\rho(f)$ and 
 {$\lambda $} be  an effective  configuration such that 
 $deg(\lambda) \leq \rho(f)$ then  {$f-\lambda$} is  $L_G$-effective; moreover    there exists
an effective configuration $\mu$ of degree $\rho(f) + 1$ such that $f-\mu$ is 
not $L_G$-effective.

\bigskip



An immediate consequence of this definition is that if 
$deg(f) < 0 $  or if $f =C(\overrightarrow{G})$
 for an acyclic orientation $\overrightarrow{G}$ then the rank of $f$ is $-1$.
 Moreover if  two configurations $f$ and $g$ are such that
$f_i \leq g_i$ for all $i$ then $\rho(f) \leq \rho(g)$.

 
The following notion will be useful do prove properties of the rank:

\begin{definition}
\label{def:proofRank}
An  effective configuration $\mu$ is a proof for the rank $\rho(f) $ of an $L_G$-effective 
configuration $f$ if $f-\mu$ is not $L_G$-effective and $f-\lambda$ is $L_G$-effective for any
effective configuration $\lambda$ such that $deg(\lambda) < deg(\mu)$.
\end{definition}

Notice that if $\lambda$ is a proof for $\rho(f)$ then $\rho(f) =deg(\lambda) - 1$.






\begin{proposition}
\label{propo:largeDegreeRank}
A configuration  $f$ of degree greater than $2m-2n$ has rank
$$ r= deg(f) - m +n -1$$
\end{proposition}

\begin{proof}
We first show that for any effective configuration $\lambda$ such that $deg(\lambda) =r$, the configuration 
$f-\lambda$ is $L_G$-effective. This follows from $deg(f - \lambda) = deg(f) - r = m-n+1$
by Corollary \ref{cor:effectiveIfLargeDegree}.


%\medskip
We now build a effective configuration $\lambda$ of degree $r+1$ such 
that $f-\lambda$ is not $L_G$-effective. Consider any acyclic orientation 
$\overrightarrow{G}$ of $G$ and let $g = f- C(\overrightarrow{G})$
then $g$ is $L_G$-effective since its degree is equal to  $deg(f) - m +n$ 
hence greater than $m-n$. Let $\lambda$ be the effective configuration
such that $ g \simil \lambda$, then $f-\lambda$ is such that 
$$C(\overrightarrow{G})  \simil f-g \simil f - \lambda$$ 
so that $f-\lambda$ is not $L_G$-effective by Proposition \ref{propo:acyclicNonEffective}.
And the Proposition results from:
 \[deg(\lambda) = deg(g) = deg(f) - deg(C(\overrightarrow{G})) = deg(f) -m +n = r+1\qedhere\]
\end{proof}


\subsubsection{Riemann-Roch like  theorem for graphs}
We give here a proof of the following theorem first proved in \cite{bakerNorine} which we estimate shorter and simpler
than the original  one.

\begin{theorem}
\label{th:RR}
 Let   {$\kappa$} be the configuration such that  {$\kappa_i = d_i -2$} for all $1 \leq i \leq n$,
 so that   {$deg(\kappa)  = 2(m-n)$}.  Any configuration   {$f$} satisfies:

     $$ \rho(f) - \rho(\kappa-f) \ \  = \ \ deg(f) + n - m$$

\end{theorem}

\begin{proof}
The main ingredient for the proof is to use Theorem \ref{th:caracEffective} and 
remark that for any acyclic orientation $\overrightarrow{G}$  the orientation $\overleftarrow{G} $ of $G$ obtained from $\overrightarrow{G}$
by reversing the orientations  of all the edges  is such that: $C(\overrightarrow{G} )+ C(\overleftarrow{G})
=\kappa$.

%\medskip

Let $f$ be any configuration we first give an upper bound for $ \rho(\kappa-f)$, we define  $\lambda$ to 
be a proof for the rank of $f$ if $f$ is $L_G$-effective,
and to be equal to $0$  if $f$ is not $L_G$-effective. So that $\rho(f) = deg(\lambda) -1$ in both cases.

Since  $f-\lambda$  is not $L_G$-effective, we have  by Theorem \ref{th:caracEffective} that there exists 
an acyclic orientation  $\overrightarrow{G}$ of $G$ such that 
$C(\overrightarrow{G}) - (f-\lambda)$ is $L_G$-effective, hence  equivalent to an  effective configuration
$\mu$. This may be written as:

\begin{equation}
\label{eq:proofRR1}
C(\overrightarrow{G}) - (f-\lambda)  \simil \mu
\end{equation}

Now consider the orientation $\overleftarrow{G} $ of $G$ obtained from $\overrightarrow{G}$ 
by reversing the orientations  of all the arrows, clearly $C(\overrightarrow{G}) + C(\overleftarrow{G})
=\kappa$. Hence adding $C(\overleftarrow{G})$ to both sides of (\ref{eq:proofRR1}) we have:
\begin{equation}
\label{eq:proofRR2}
\kappa- (f - \lambda)  \simil \mu + C(\overleftarrow{G})
\end{equation}
which may be written as:

$$ (\kappa - f) - \mu \simil C(\overleftarrow{G}) -\lambda$$
Giving that $\kappa-f - \mu$ is not $L_G$-effective since the reverse of an acyclic orientation is also acyclic.
Hence by the definition of the rank we have
\begin{equation}
\label{eq:proofRR3}
\rho(\kappa-f) < deg(\mu)
\end{equation}
The degree of $\mu$ is obtained from (\ref{eq:proofRR1}) giving:
$$ deg(\mu) = deg(C(\overrightarrow{G})) - deg(f) + deg(\lambda) = m-n -deg(f) + \rho(f) +1$$
and:
\begin{equation}
\label{eq:proofRR4}
\rho(\kappa-f) <  m-n -deg(f) + \rho(f) +1
\end{equation}

%\medskip

Now to obtain a lower bound for $\rho(\kappa-f)$ we exchange the roles of $f$ and $\kappa-f$ giving:

\begin{equation}
\label{eq:proofRR5}
\rho(f) <  m-n -deg(\kappa-u) + \rho(\kappa-u) +1
\end{equation}
Since $deg(\kappa-u) = 2(m-n) - deg(f)$, inequality (\ref{eq:proofRR5}) may be written as:

\begin{equation}
\label{eq:proofRR6}
\rho(f) + m-n -deg(f)  -1  <  \rho(\kappa-f) 
\end{equation}
Comparing inequalities (\ref{eq:proofRR4}) and (\ref{eq:proofRR6}), and noticing that the
rank is an integer gives
$$\rho(f) + m-n -deg(f)  =  \rho(\kappa-f) $$
hence proving the Theorem.
\end{proof}
\subsection{Enumerating the effective configurations}


\begin{proposition}
\label{polTutteNbEffective}
Let $T_G(x,y)$ be the Tutte polynomial of the graph $G$, 
and let $t_i$ be the integer coefficients given by:  $$T_G(1,y) = 
\sum_{i=0}^{m-n+1}  t_iy^i$$ 
Then the number of non equivalent $L_G$-effective configurations of degree $d$
is given by:
$$ \sum_{k = m-n+1-d}^{m-n+1} t_k$$
\end{proposition}

\begin{proof}

In \cite{merinoLopez} the level of a recurrent configuration $f$ 
was defined as
$$ level(f) \  \   = \   \  \sum_{i=0}^{n-1} f_i - m +d_n$$

where $d_n$ is the degree of the vertex $x_n$.

It was proved that this level varies from $0$ to $m-n+1$ and
that the number of recurrent 
configurations of level $p$  and such that $x_n = q$ 
does not depend on $q$ and is equal to the coefficent  $t_p$
of $y^p$ in the evaluation of the Tutte polynomial $T_G(x,y)$  of $G$ for $x=1$.
A bijective proof of this result was given in \cite{coriLeBorgne1}.

Using the bijection $\beta$ defined in Proposition \ref{prop:recToParking}
we have that the number of parking configurations $g$ such that
$\sum_{i=1}^{n-1} g_i = j$ and a given value for $g_n$
 is equal to the number of recurrent
configurations $f$ such that:

$$\sum_{i=1}^{n-1} f_i = \sum_{i=1}^{n-1} (d_i - 1 - g_i)  =  \   \  2m - d_n - (n-1) -j$$
and $f_n = d_n-1 - g_n$, which 
is the number of recurrent configurations of level $k=m-n+1-j$ and a given value of $f_n$.
This number is equal to $t_k$.

In order that the configuration  $g$ of degree $d$ to be $L_G$-effective we must have $g_n \geq 0$
so that $k$ must be greater or equal to 0 and not greater than $m-n+1$,
thus ending the proof.
\end{proof}

The generating function for non-equivalent $L_G$-effective configurations according to the degree counted by the variable $y$ is $\frac{y^{m-n+1}}{1-y}T_G(1,y^{-1})$.





\end{document}
