text:
\begin{document}

\title{Soliton decomposition of the Box-Ball System}

\author{Pablo A. Ferrari, Chi Nguyen, Leonardo T. Rolla, Minmin Wang}

\maketitle

\begin{abstract}
The Box-Ball System was introduced by Takahashi and Satsuma as a discrete counterpart of the KdV equation. Both systems exhibit solitons whose shape and speed are conserved after collision with other solitons. Conservation of solitons suggests that this dynamics has many spatially-ergodic invariant measures besides the i.i.d.\ distribution. Meanwhile, solitons of different sizes interact through a momentary change of speeds during collision, which cumulatively affects their asymptotic speeds, suggesting that the speeds are determined by such interaction. In order to understand general invariant measures and soliton interactions, we introduce a decomposition of configurations through slots, reducing the dynamics to a simple hierarchical translation of different components. Using this property we obtain an explicit recipe to construct a rich family of invariant measures. Finally, we obtain explicit equations for the soliton speeds in terms of spacial density of solitons.
\end{abstract}

\begin{figure*}[hb!]
\includegraphics[width=\textwidth]{figures/t2509}
\\
BBS dynamics for i.i.d.\ initial configuration with density 0.25. Straight red lines are deterministic and computed using Theorem~\ref{thm:speedsexplicit}.
{
\hfill
\small
(high resolution, color online)}
\end{figure*}

\section{Introduction}

Assume that there is a \emph{box} at each integer $x\in\Z$ and that each box may contain a \emph{ball} or be empty. Denote $\eta\in\{0,1\}^\Z$ a ball configuration, with the convention $\eta(x):= 1$ if there is a ball at $x$, else $\eta(x):= 0$. Consider first configurations with a finite number of balls and let an empty carrier start to the left of the leftmost ball and visit the boxes one after another. When visiting box $x$, the carrier picks a ball if there is any and if the $x$ is empty and the carrier has at least one ball, he deposits the ball in the box.
Let $T\eta$ be the configuration obtained after the carrier visited all boxes. An example of $\eta$, carrier load, and $T\eta$ is as follows. \\
\begin{align*}
\begin{array}{ll}
\hbox{\tt
0 0 1 0 1 1 0 0 0 0 1 1 0 1 0 0 0 0 0} &\eta\\
\hbox{\tt
\;\;0 0 1 0 1 2 1 0 0 0 1 2 1 2 1 0 0 0} &\hbox{carrier load}
\\
\hbox{\tt
0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 0 0 } &T\eta
\end{array}
\end{align*}

\medskip

This dynamics, called \emph{Box-Ball System} (BBS), was introduced in~\cite{TS} as a discrete system showing solitons, a phenomenon also present in the KdV equation.
For the relation between BBS and KdV see~\cite{TokihiroTakahashiMatsukidairaSatsuma96,TakahashiMatsukidaira97}.
For further physical motivation of the BBS model, see~\cite{kato2016spectral,levine-lyu-pike,TORII}.
See also~\cite{CroydonKatoSasadaTsujimoto17, InoueKunibaOkado04, InoueKunibaTakagi12, LPS, MadaIdzumiTokihiro06, Saka1, Saka2} for some other developments.

The transformation $T$ can be defined for configurations with infinitely many balls if the density of balls is well-defined and less than $\frac{1}{2}$.
The product measure with any such density is invariant under $T$.
But
the family of invariant probability measures is far richer than that,
since this transformation $T$ has many conservation properties.
In particular, a configuration can have \emph{solitons} of all sizes, these solitons are conserved by the dynamics and there is a distance measure between solitons of the same size which is also conserved.

Takahashi and Satsuma proposed an algorithm to identify solitons in a finite ball configuration and argued that the solitons identified at time 0 can be tracked at successive iterations of $T$.
An isolated \emph{$k$-soliton} $\gamma$ consists of $k$ successive occupied boxes followed by $k$ successive empty boxes. Evolving this configuration by $t$ iterations of $T$, the new configuration will have a $k$-soliton $\gamma^t$ which is a translation of $\gamma$ by $kt$.
The striking property of the BBS is that, although solitons can collide which momentarily changes their shapes and introduces shifts, such collisions neither create nor destroy solitons, see Proposition~\ref{prop:solitontrack}.

Given a soliton size $k\ge 1$ and a ball configuration $\eta$, we identify a subset of boxes called \emph{$k$-slots}.
To each $k$-slot, one can append any number of $k$-solitons.
For each ball configuration, we can describe the number of $k$-solitons appended to each $k$-slot and call \emph{$k$-component} the resulting vector.
The components are defined hierarchically starting from the bigger solitons, and ball configurations can be reconstructed from the components. We show that under the BBS evolution the $k$-component is rigid, conserving the number of $k$-slots between two successive $k$-solitons, for all $k$.
More precisely, the $k$-component is shifted by a quantity depending only on the $m$-soliton configuration for $m>k$, see Theorem~\ref{thm:hierarchy}.

Our main result about invariant measures is the following.
Given a family of shift-invariant probability measures on $\N^\Z_0$ indexed by $k$ and whose densities decay fast enough in $k$, we can construct a $T$-invariant probability measure $\mu$ whose components are independent and distributed according to such family, see Theorem~\ref{thm:invariant}.
We conjecture that this decomposition characterizes $T$-invariant probability measures in the sense that, if $\mu$ is shift-mixing and $T$-invariant then its components should be independent and shift-mixing.

We finally study the asymptotic speed of $k$-solitons.
The position of each $k$-soliton divided by time converges to a deterministic asymptotic speed $v_k$, and $(v_k)_{k\ge1}$ is the unique solution of an explicit system of linear equations, see Theorems~\ref{thm:hspeed} and~\ref{thm:speedsexplicit}.

In the sequel we give precise definitions and state some of the main results.

Our space will be the set of configurations defined by
\begin{align}
\cX_\lambda :=\Bigl\{\eta\in\{0,1\}^\Z: \lim_{y\to\infty}\,\frac1{y} \sum_{x=-y}^0\eta(x) =  \lim_{y\to\infty}\,\frac1{y} \sum_{x=0}^y\eta(x) =\lambda\Bigr\}
\ \
\text{ and }
\ \
\cX := \bigcup_{\mathclap{0 < \lambda < \frac12}} \cX_\lambda
.
\end{align}

For $\eta \in \cX$ we define the set of \emph{records} by
\begin{equation}
\label{eq:reta}
R\eta := \Big\{ x\in \Z : \sum_{y=z}^x \eta(y) < \sum_{y=z}^x [1-\eta(y)] \text{ for all } z\le x \Big\}.
\end{equation}
Sites in between records form finite \emph{excursions}.
The operator $T$ is defined by
\begin{align}
\label{t2}
T\eta(x) :=
\begin{cases}
0 ,& x \in R\eta, \\
1-\eta(x) ,& \text{otherwise}.
\end{cases}
\end{align}

\begin{lemma}
\label{lemma:densityconservation}
Let $0 \le \lambda< \frac12$ and $\eta\in\cX_\lambda$. Then $T\eta\in\cX_\lambda$.
\end{lemma}

The above lemma is a direct consequence of~\eqref{eq:Txi}, see \S\ref{sec:solitons}.

\subsection{Identifying solitons and computing speeds}

Define the \emph{runs} of $\eta$ as maximal blocks of successive sites where $\eta$ has a constant value, forming a partition of $\Z$.
Assume first $\eta$ has a finite number of balls, so it has a semi-infinite run of zeros to the left and one to the right.

The \emph{$k$-solitons} are identified in~\cite{TS} by the following algorithm.

\begin{algorithm}[H]
  Start with a doubly infinite \emph{word}, so that each letter in the word is $0$ or $1$ and remembers which box $x$ it corresponds to in the ball configuration $\eta$
  \\
  \While{\rm there are still ones in the \emph{word}}{
    Select the leftmost run in the \emph{word} whose length is at least as long as the length (denote it $k$) of the run preceding it
    \\
    Identify a soliton of size $k$, or simply $k$-soliton, consisting of the first $k$ letters of this run and the run preceding it
    \\
    Remove these $2k$ letters from the \emph{word}
  }
\end{algorithm}

\begin{figure}[b]
\centering
\includegraphics[width=.9\textwidth]{figures/algo-crop}
\caption{\small
Applying the algorithm to a sample configuration. Dots represent records. On the left we have the resulting word after successive iterations. Identified solitons are shown in bold once and then with a color corresponding to their size.
The algorithm is applied to each excursion separately, so it ignores the other $1$-soliton.
(color online)}
\label{fig:algo}
\end{figure}

Notice that a $k$-soliton consists of $k$ zeros followed by $k$ ones or vice-versa, and letters which do not belong to any soliton are all zero and correspond to the records of $\eta$, see Fig.~\ref{fig:algo}.
For general $\eta \in \cX$ we apply the above algorithm to each excursion.

Let $\gamma$ be a $k$-soliton. We define the \emph{head} and \emph{tail} of $\gamma$ as follows: the head $\H(\gamma)$ is the set of the positions of $k$ ones in $\gamma$ and the tail $\T(\gamma)$ is formed by the positions of the $k$ zeros.
Let $\Gamma_k\eta$ be the set of $k$-solitons of a ball configuration $\eta\in \cX$.
The following is proved in \S\ref{sec:postponed}.

\begin{proposition}
\label{prop:solitontrack}
For any $\eta\in\cX$ and $A \subseteq \Z$, there is a $k$-soliton $\gamma\in\Gamma_k\eta$ with tail $\T(\gamma)=A$ if and only if there is a $k$-soliton $\gamma^1 \in \Gamma_k(T\eta)$ with head $\H(\gamma^1) = A$.
\end{proposition}

By the above proposition, we can track each $k$-soliton $\gamma$ in the evolution of $\eta$. For each $k$-soliton $\gamma \in \Gamma_k \eta$, call $(\gamma^t)_{t\ge 0}$ the trajectory satisfying $\gamma^0 =\gamma$
and
\begin{equation}
\label{eq:trackgamma}
\H(\gamma^{t+1}) = \T(\gamma^t)
.
\end{equation}

Let $\mu$ be a shift-ergodic (when we say ergodic it also implies invariant) measure on $\cX$.
Denote by
$\rho_k$ the mean number of $k$-solitons per excursion,
by $w_0=1+\sum_k 2k\rho_k$ the mean size of excursions, and
by $\orho_k = \frac{\rho_k}{w_0}$ the mean number of $k$-solitons per site (precise definitions in \S\ref{sub:finitew}).
Denote by $x(\gamma)$ the leftmost site of $\gamma$.
We now state the main result concerning speeds.

\begin{theorem}
\label{thm:hspeed}
Let $\mu$ be a $T$-invariant and shift-ergodic measure on $\cX_\lambda$.
Then there exists deterministic $v=(v_k)_{k}$
such that, $\mu$-a.s., for all $\gamma \in \Gamma_k\eta$,
\begin{align}
\label{eq:speedexists}
\lim_{t\to\infty} \frac{x(\gamma^t)}{t} &= v_k.
\end{align}
The speeds $(v_k)_k$ are finite and satisfy the system
\begin{equation}
\label{eq:hspeedseq}
v_k = k + \sum_{m<k} 2m \orho_m (v_k-v_m) - \sum_{m>k} 2k \orho_m (v_m-v_k)
.
\end{equation}
\end{theorem}

For the next result we need a stronger assumption, described further below.

\begin{theorem}
\label{thm:speedsexplicit}
Let $\mu$ have independent i.i.d.\ soliton components. Then
the speeds $(v_k)_k$ in~\eqref{eq:speedexists} are also given by the unique solution to
\begin{equation}
\label{eq:hspeedexplicit}
w_k=1+\sum_{m>k} 2(m-k) \rho_m
, \
\
\rho_k = \alpha_k w_k
, \
\
s_k = k+\sum_{m<k}2(k-m) s_m \alpha_m
, \
\
v_k = \frac {s_k}{w_k}
,
\end{equation}
and in particular they are determined by $(\rho_k)_k$.
\end{theorem}

\begin{figure}[b]
\includegraphics[width=\textwidth]{figures/t1509}
\caption{\small
Simulation for an i.i.d.\ configuration with density $0.15$.
The transparent red lines have deterministic slopes computed by Theorem~\ref{thm:speedsexplicit}, which have been manually shifted so that they would overlay a soliton.
This window covers 2000 sites and 140 time steps going downwards, and has been stretched vertically by a factor of $5$.
The figure in the first page is the same except for the density.
(high resolution, color online)}
\label{fig:speeds1}
\end{figure}

\begin{figure}[b]
\includegraphics[width=\textwidth]{figures/trho}
\caption{\small
Simulation for $(\rho_k)_k=(.006,.005 ,.1,.003,0,0,0,\dots)$.
The initial configuration was obtained by first appending one $k$-soliton with probability $\rho_k$ after each record, and then applying $T$ a number of times in order to mix.
As in Fig.~\ref{fig:speeds1} it is a 2000x140 window stretched by 5, and red lines are deterministic.
(high resolution, color online)}
\label{fig:speeds2}
\end{figure}

So the above theorems describe the speeds explicitly.
In practice, the speeds $v_k$ can be computed by truncating $\rho$ (replace $\rho_k$ by $0$ for large $k$), and solving these finite recursions for $w$, $\alpha$, $s$ and finally $v$.
For i.i.d.\ initial conditions, one can find $\alpha_k$ explicitly in terms of the density $\lambda$ by computing partition functions~\cite{FG18}, substitute the equation for $\rho$ into that for $w$, then compute $s$ and $v$.
Using this and the above theorem, we have produced the simulations shown in Figs.~\ref{fig:speeds1} and~\ref{fig:speeds2} as well as that of the first page.

System~\eqref{eq:hspeedseq} comes from the following.
When a $k$-soliton is isolated, it advances by $k$ units, and when it encounters an $m$ soliton, the encounter causes it to advance $2m$ extra units if $m<k$ or be delayed by $2$ time steps if $m>k$.
The term $\orho_m |v_k-v_m|$ gives the frequency of such encounters as seen from a $k$-soliton.

In system~\eqref{eq:hspeedexplicit}, $w_k$ is the density of $k$-slots per excursion (see below), $\alpha_k$ is the density of $k$-solitons per $k$-slot, $s_k$ is the average size of the head of a $k$-soliton, $k-m$ is the number of $m$-slots in the head of a $k$-soliton, and the factor $\frac{1}{w_k}$ is the probability that a typical $k$-soliton is free to move (see \S\ref{sec:speeds} for details).

\subsection{Slots and invariant measures}

Recall that configurations $\eta\in\cX$ are decomposed into solitons and records, and that a $k$-soliton has a head and a tail, each one consisting of $k$ (possibly non-consecutive) sites.
We say that the $j$-th site of the head or tail of an $m$-soliton has a $k$-slot for all $k<j$.
Roughly speaking, $k$-slots are the places where $k$-solitons can be inserted without interfering with the rest of the configuration in terms of the Takahashi-Satsuma algorithm.
We also say that a record has $k$-slots for every $k$.
Indeed, a soliton of any given size can be inserted between two records.

Assume that $0 \in R\eta$.
Enumerate the $k$-slots in increasing order and so that the \emph{$0$-th $k$-slot} be at position $s_k(\eta,0)=0$, and let $s_k(\eta,i)$ denote the position of the $i$-th $k$-slot for $i\in\Z$.
We say that a $k$-soliton $\gamma$ is \emph{appended} to the $i$-th $k$-slot if it is contained
between $s_k(\eta,i)$ and $s_k(\eta,i+1)$.
Define the \emph{$k$-component} of $\eta$ as the configuration $M_k\eta$ of $k$-solitons appended to the $k$-slots, given by
\(
M_k\eta(i) := \text{number of the $k$-solitons appended to the $i$-th $k$-slot}.
\)
Let $\hmu=\mu(\, \cdot \,|\, 0\in R\eta)$.

\begin{theorem}
\label{thm:invariant}
Let $\zeta=(\zeta_k)_{k\ge 1}$ be independent random elements of $(\mathbb Z_{+})^{\mathbb Z}$ with shift-invariant distributions satisfying $\sum_k k E[\zeta_k(0)] <\infty$.
Then there exists a unique shift-invariant
probability $\mu$ on $\cX$ such that $M_k \eta \overset{d}{=}\zeta_k$ under $\hmu$, and this measure $\mu$ is $T$-invariant.
If moreover $(\zeta_k(i))_{i\in\Z}$ is i.i.d.\ for each $k$, then $\mu$ is also shift-ergodic.
\end{theorem}

The above theorem says that the family of invariant measures for this dynamics is at least as large as the family of sequences of states of $k$-soliton configurations.
This is in contrast with many stochastic systems, which have at most one invariant measure for each density $\lambda$.
Moreover, given a sequence $(\rho_k)_k$ specifying the density of $k$-solitons for each $k$, there is still a large family of mutually singular states, all having the same specified densities.

The extra assumption needed in Theorem~\ref{thm:speedsexplicit} is that $\mu$ be of the above form, i.e., under $\hmu$ each $k$-component is i.i.d.\ and they are independent over $k$.
In this case, we can also study the speed of tagged records and the speed of solitons measured in terms of tagged records, see \S\ref{sub:vertical}.

\subsection{Dynamics of components, main tools and paper outline}

The two previous results rely heavily on the analysis of how the $k$-components evolve under $T$.
Then main result in this analysis is Theorem~\ref{thm:hierarchy}, which says that $\zeta_k$ is translated by $k$ plus a correction caused by the relabeling of slots when larger solitons jump over the origin.
For brevity we defer a precise statement to \S\ref{sub:compevol} where the slot decomposition will have been described in more details.

Another tool that we use abundantly are Palm transformations, which allow us to go back and forth from a configuration seen from an external observer, a typical record or a typical $k$-soliton.
Combining Palm theory with the operator $T$ permits the analysis of the dynamics as seen from a tagged record or a tagged $k$-soliton. This framework is crucial in the explicit construction of invariant measures and in the analysis of asymptotic speeds.

The paper is organized as follows.
In \S\ref{sec:solitons} we describe the TS algorithm to identify solitons and show that solitons are conserved by the dynamics.
We then introduce the slot decomposition of ball configurations, describe how $k$-components are translated by the dynamics, and finally show that a configuration can be reconstructed from the $k$-components.
In \S\ref{sec:measures} we prove Theorem~\ref{thm:invariant} by giving an explicit construction of $T$-invariant measures which are shift-invariant.
In \S\ref{sec:speeds} we study the asymptotic speed of tagged solitons to prove Theorems~\ref{thm:hspeed} and~\ref{thm:speedsexplicit} and also study the speeds in terms of records.
In \S\ref{sec:postponed} we complete some proofs postponed in previous sections.

\section{Slot decomposition and reconstruction}
\label{sec:solitons}

\begin{figure}[b]
\centering
\includegraphics[width=.8\textwidth]{figures/6-4-3-junto}
\caption{\small
Time-evolution of a walk under seven iterations of $T$.
This example has four solitons,
of size 7, 5, 3 and 1.
Different colors are used to highlighting their conservation.
To facilitate view we have shifted the walk at time $t$ by $t$ units down. (color online)}
\label{fig:conservation}
\end{figure}

We define $\xi=\xi[\eta]$ as a walk on $\Z$ that jumps one unit up at $x$ when there is a ball at $x$ and jumps one unit down when box $x$ is empty.
That is,
\begin{align}
\xi(x)-\xi(x-1) = 2\eta(x)-1
.
\end{align}
We define records for a walk $\xi$ in the usual sense, that is,
we say that $x$ is a \emph{record} for $\xi$ if
$\xi(z)> \xi(x)$ for all $z<x$.
Let $\cW_\lambda = \{\xi[\eta]:\eta\in\cX_\lambda\}$ and $\cW = \{\xi[\eta]:\eta\in\cX\}$.
Then every $\xi \in \cW$ satisfies
$\min\limits_{y\le x}\xi(y) \in \Z$ for all $x \in \Z$, and we define
\begin{align}
\label{eq:Txi}
T\xi(x) := 2 \min_{y\le x} \xi(y) - \xi(x) = \big[\min_{y\le x}\xi(y)\big]-\Big[\xi(x)-\min_{y\le x}\xi(y)\Big].
\end{align}
This amounts to reflecting the walk $\xi$ with respect to its running minimum.
The operation $T$ on $\cW$ and conservation of solitons are illustrated in Fig.~\ref{fig:conservation}.

One can see $\xi$ as a \emph{lift} of $\eta$ which includes an arbitrary choice of vertical shift, or equivalently an arbitrary labeling of records in increasing order.
Conversely, $\eta[\xi]$ is unambiguously defined by $\eta(x)=\frac{1+\xi(x)-\xi(x-1)}{2}$.
Consider the following diagram:
\begin{displaymath}
\xymatrixcolsep{3pc}
\xymatrix{
  \xi
  \ar[r]^{T}
  \ar@/^.5pc/@{->}[d]^{\mathcal{P}}
                                                   & T\xi
                                                     \ar@/^.5pc/@{->}[d]^{\mathcal{P}}
\\
  \eta
  \ar[r]^{T}
  \ar@/^.5pc/@{->}[u]^{\mathcal{L}}
                                                   & T\eta
                                                     \ar@/^.5pc/@{->}[u]^{\mathcal{L}}
}
\end{displaymath}
In general this diagram commutes except that the lifting $\mathcal{L}$ misses uniqueness while the projection $\mathcal{P}$ cancels such non-uniqueness.
They are analogous to the derivative and indefinite integral where the latter comes with an indeterminate additive constant.
If a property is insensitive to the choice of the lift $\xi[\eta]$, then it is in fact a property of $\eta$, even if is described in terms of $\xi$.
For instance, the above definition of record coincides with the one given at the Introduction.
Likewise, \eqref{t2} is equivalent to~\eqref{eq:Txi}, and from the latter one immediately gets Lemma~\ref{lemma:densityconservation}.
Some of the objects considered in this section do however depend on the lift $\xi$.
Note that properties of $\eta$ always translate to $\xi$, for instance $\Gamma_m \xi$ means simply $\Gamma_m \eta[\xi]$, etc.

\subsection{Slots and components}

\begin{figure}[b]
\centering
\includegraphics[width=.9\textwidth]{figures/Seta65411-ball-only-slots}
\caption{\small
Slot configuration of a walk $\xi$.
Different colors correspond to different solitons; records are painted in black. For each site, the number of dots below it indicates its level in slots: there being $k$ dots means a $k$-slot. (color online)}
\label{fig:slots1}
\end{figure}

\begin{figure}[b]
\centering
\includegraphics[width=.8\textwidth]{figures/slots-tree-2}
\caption{\small
An illustration of how the solitons are nested inside bigger solitons via slots, in the same sample configuration as in Fig.~\ref{fig:slots1}.
Solitons are represented by squares and slots by circles. For each $k \ge 1$, each slot with index $m\ge k$ is a $k$-slot.
We say it is the $n$-th $k$-slot, where the ordinal $n$ is determined by counting how many $k$-slots appear before it in the depth-first order, and the counting starts from the 0-th $k$-slot present at Record~0.
}
\label{fig:slots-tree}
\end{figure}

We now describe how solitons can be nested inside each other via what we call \emph{slots}.
Let $\gamma$ be a $k$-soliton.
We label the sites in the head and tail of $\gamma$ in increasing oder by $\H(\gamma)=\{\H_1(\gamma), \dots, \H_k(\gamma)\}$ and by $\T(\gamma)= \{\T_1(\gamma),\dots,\T_k(\gamma)\}$.
Given a walk representation $\xi$,
the \emph{slot configuration} $S\xi:\Z\to \{0,1,2,\dots\}\cup\{\infty\}$ is defined by
\begin{align}
S\xi(x) :=
\begin{cases}
k-1,&\hbox{if } x = \T_k(\gamma) \text{ or } \H_k(\gamma), \hbox{ for }\gamma \in\Gamma_m\xi \hbox{ and } m \ge k,\\
\infty,&\hbox{if } x \hbox{ is a record for } \xi.
\end{cases}
\end{align}
For each $k\ge 1$ we say that $x$ is a \emph{$k$-slot} for $\xi$ if $S\xi(x)\ge k$.
Note that a record is a $k$-slot for all $k$, and an $m$-soliton contains a number $2m-2k$ of $k$-slots, see Fig.~\ref{fig:slots1}.
Since every $\xi\in \cW$ has infinitely many records, it also has infinitely many $k$-slots.

For $j\in \mathbb Z$, the position of the record at level $-j$ will be called \emph{Record}~$j$ and denoted
\begin{align}
\label{eq:r111}
r(\xi,j) := \min\{x\in\Z: \xi(x)=-j\}.
\end{align}
This is the leftmost site where the walk $\xi$ takes the value $-j$.
If $\xi\in\cW$, we have  $r(\xi,j) \in \Z$ is well-defined for all $j\in\Z$.

Denote the set of the $k$-slots of $\xi$ by $\{s_k(\xi,i)\}_{i\in\Z}$, so that the labeling is increasing in $i$ and the $0$-th $k$-slot is at Record~$0$, that is, $s_k(\xi,0)=r(\xi,0)$.
We say that a $k$-soliton $\gamma$ is \emph{appended} to the $i$-th $k$-slot if $\gamma$ is contained in the interval $[s_k(\xi,i)+1,s_k(\xi,i+1)-1]$. Each $k$-soliton in $\xi$ is appended to a unique $k$-slot, but any finite number of $k$-solitons can be appended to a single $k$-slot.
See Fig.~\ref{fig:slots-tree} for how the solitons are nested inside each other via slots.

For $\xi\in\cX$ we define the \emph{$k$-component} of $\xi$ as the configuration $M_k\xi$ of $k$-solitons appended to the $k$-slots, that is,
$M_k\xi(i)$ denotes the number of the $k$-solitons appended to the $i$-th $k$-slot.
In the example of Fig.~\ref{fig:slots1},
\(
M_6\xi(0) = 1,
\
M_5\xi(2) = 1,
\
M_4\xi(2) = 1,
\
M_1\xi(9) = 1,
\
M_1\xi(18) = 1,
\)
and $M_k\xi(i) = 0$ otherwise.

\subsection{Evolution of components}
\label{sub:compevol}

\begin{figure}[b]
\centering
\includegraphics[width=.8\textwidth]{figures/Evolution}
\caption{\small
Relabeling and tagging $k$-slots throughout the dynamics. In general the relabeled $k$-slot will not appear at the same position, and they are identified in $M_k$ by counting from Record~0. But some $m$-solitons with $m>k$ may cross Record~0, bringing a number $o_k^t(\xi)$ of slots with them, thus the need to relabel the $k$-slots. The dotted lines mark three relabeled slots and one tagged slot, which happens to contain a $k$-soliton.}
\label{fig:evolution}
\end{figure}

\begin{figure}[b]
\centering
\includegraphics[width=.98\textwidth]{figures/Seta-slots-2-t}
\caption{\small
We depict $T\xi$ below $\xi$. The support of excursion $\vep$ of $\xi$ is between the two vertical lines. Records 1 to 6 (numbered sites in the picture) are to the right of $\{\vep\}$ in $\xi$ and in positions $a_1(\vep)$ to $a_6(\vep)$ in $T\xi$. The blue $6$-soliton is $\tilde{\gamma}$, and $\T(\tilde{\gamma}^1)$, its tail in $T\xi$, is to the right of $\{\vep\}$. (color online)}
\label{fig:movingslots}
\end{figure}

Recall that we can track a tagged soliton $\gamma$ after $t$ iterations of $T$ by~\eqref{eq:trackgamma}.
Tagged records are also tracked by the formula~\eqref{eq:r111}.
In order to track slots we introduce the flows of solitons and slots, as follows.

Let $\xi\in\cW$ and define the \emph{flow of $m$-solitons through Record~$0$ by time $t$} as the number of $m$-solitons $\gamma$ to the left of Record~$0$ in $\xi$ and such that $\gamma^t$ is to the right of Record~0 in $T^t\xi$:
\begin{align}
\label{eq:solitonflow}
J^t_m \xi := \# \big\{ \gamma\in\Gamma_m\xi : \gamma\subset(-\infty,r(\xi,0))\hbox{ and } \gamma^t \subset[r(T^t\xi,0),\infty)\big\}
\end{align}
We now define an observable $o^t_k(\xi)$ which counts the flow of $k$-slots through Record~$0$
after $t$ iterations of $T$.
Because each $m$-soliton crossing Record~$0$ from left to right carries $2(m-k)$ $k$-slots, we define
\begin{align}
o^t_k(\xi) := \sum_{m>k} 2(m-k) J^t_m \xi. \label{itk}
\end{align}
Using this observable, we define the \emph{relabeled $0$-th $k$-slot at time $t$} by
\begin{align}
\label{eq:stk}
s^t_k(\xi,0) &:= s_k(T^t\xi,o^t_k(\xi)),
\end{align}
which is the position of the $o_k^t$-th $k$-slot counting from Record~$0$ of $T^t\xi$.
More generally, the \emph{relabeled $i$-th $k$-slot at time $t$} is defined as
\begin{align}
  s^t_k(\xi,i) &:= s_k(T^t\xi,o^t_k(\xi)+i).
\end{align}

\begin{theorem}
\label{thm:hierarchy}
Let $\xi\in\cW$ and $t\in\{1,2, 3, \dots\}$. Then, for any $k$-soliton $\gamma$ of $\xi$,
\begin{align}
  \# \Big\{ {i\in\Z} : \gamma \subset \big( -\infty,s_k(\xi,i) \big) \hbox{ and } \gamma^t \subset \big[s^t_k(\xi,i),\infty\big) \Big\} = kt,
\end{align}
that is, the right-to-left flow of relabeled $k$-slots through a tagged $k$-soliton between times $0$ and $t$ is exactly $kt$.
The $k$-soliton component of $T^t\xi$ is a shift of the $k$-soliton component of~$\xi$:
\begin{align}
\label{eq:M_kdynamic}
M_k T^t \xi(i) = M_k\xi\big(i - o^t_k(\xi)-kt\big)
,
\end{align}
where $o^t_k(\xi)$ is the label at time $t$ of the relabeled $k$-slot initially at Record~$0$.
Moreover, for each $k\in\N$, the offset $o_k^t(\xi)$ is determined by $(M_m \xi)_{m>k}$.
\end{theorem}

Let $\pi \in S_k\xi \subseteq \Z$.
Then $\pi = s_k(\xi,j)$ for some $j$ and we define
\begin{equation}
\label{eq:trackslot}
\pi^{k,t} := s_k \big( T^t\xi,o^t_k(\xi)+kt+j \big)
.
\end{equation}
If there is a $k$-soliton $\gamma$ appended to the $k$-slot $\pi$ of $\xi$, by Theorem~\ref{thm:hierarchy}
the $k$-soliton $\gamma^t$ will be appended to the $k$-slot $\pi^{k,t}$ of $T^t \xi$.
In particular, the definition of $\pi^{k,t}$ depends only on $\eta[\xi]$.
We note that the difference between the relabeled slots introduced before and tagged slots introduced just now is the factor of $kt$ related to the motion of $k$-solitons.
So a tagged $k$-soliton crosses $k$ relabeled $k$-slots per unit time whereas it does not cross tagged $k$-slots (in fact it just follows one of them), see Fig.~\ref{fig:evolution}.

In the remainder of this subsection we prove Theorem~\ref{thm:hierarchy}.

We start by showing how the second statement follows from the first one.
Since every $k$-soliton crosses exactly $k$ relabeled $k$-slots at each step,
the number of $k$-slots between any pair of tagged $k$-solitons is conserved by $T$.
Hence the $k$-soliton component as seen from the relabeled $0$-th $k$-slot just shifts $k$ $k$-slots per unit time, while the term $o^t_k(\xi)$ accounts for the relabeling of $k$-slots caused by bigger solitons crossing Record~0.

To show the first statement, it suffices to prove that the number of relabeled $k$-slots to the right of a $k$-soliton $\gamma$ in $\xi$ and to the left of $\gamma^1$ in $T\xi$ is exactly $k$. Consider an excursion $\vep$ of height $m\ge k$ and let $\tilde{\gamma}$ be the rightmost $m$-soliton in $\vep$.

Assume first that there are no solitons to the left of $\vep$.
Denote
\begin{align}
a_i(\vep):= \min \{\H_i(\gamma):\gamma \text{ is a soliton of size $\ge i$ and contained in }\vep\},\quad i=1,\dots,m
\end{align}
The slot configuration in the sites $\{\vep\}$ in $\xi$ is modified in $T\xi$ as follows.
\begin{align}
S\xi(a_i(\vep)) = i-1,\quad i=1,\dots,m\label{t116}\\
  ST\xi(a_i(\vep)) =\infty,\quad i=1,\dots,m.\label{t117}
\end{align}
Indeed, $m$ records that were to the right of $\{\vep\}$ in $\xi$ go respectively to $\{a_1(\vep),\dots,a_m(\vep)\}$ in $T\xi$, and the remaining sites of $\{\vep\}$ keep the same slot configuration:
\begin{align}
  S_kT\xi(x) = S_k\xi(x),\quad \hbox{for }x\in\{\vep\}\setminus\{a_1(\vep),\dots,a_m(\vep)\},
\end{align}
see Fig.~\ref{fig:movingslots}.
As a consequence,  we have that for each $i\in\{1,\dots, m\}$ and $j\ge i$, there is one $j$-slot ``jumping'' from the right of $\{\vep\}$ to $a_i(\vep)$.
More precisely, one 1-slot goes from the right of $\{\vep\}$ to $a_1(\vep)$, two 2-slots go to $a_1(\vep)$ and $a_2(\vep)$, and so on.
Since the $1$-solitons of $\vep$ are appended to 1-slots in $T\xi$ starting from $a_1(\vep)$, we have that exactly one 1-slot crossed from the right to the left of each 1-soliton in $\vep$.
In the same way, each $k$-soliton of $\vep$ is appended to a $k$-slot of $T\xi$ which is at some $x \ge a_k(\vep)$, so the flow of $k$-slots across any $k$-soliton in $\vep$ is exactly $k$, concluding the proof.

We now drop the assumption that there are no solitons to the left of $\vep$.
Suppose there is an excursion $\vep'$ of height $n \ge 2$ to the left of the excursion $\vep$ and there are $\ell<n$ records between $\vep'$ and $\vep$
(if there are more than $n$ records, then $\vep'$ will not interfere with $\vep$).
Then, the records that in the previous case were going to $a_i(\vep)$ are now going to $a_{n-\ell-i}(\vep')$
in $T\xi$ for $i \le n-\ell$, while the slot configuration of $\xi$ in $a_{n-\ell-i}(\vep')$ goes to $a_i(\vep)$ in $T\xi$.
Hence, as before the flow of relabeled $k$-slots across any $k$-soliton in $\vep$ equals $k$.
If there are more than two such excursions, the description gets more complicated but the principle remains the same.

For the third statement, we need to show that $o^t_k(\xi)= o^t_k(\xi')$ whenever $\xi,\xi'\in\hcW$ are such that $(M_m\xi :m>k)=(M_m\xi':m>k)$, that is, we need to show that for any $m>k$ the left-to-right flow of $m$-solitons through Record~0 for $\xi$ and $\xi'$ coincide, which means $J^1_m\xi=J^1_m\xi'$.
To prove that, we observe that $J^1_m \xi$ is given as follows.
Let $k_0=k_0(\xi)=\max\{k : M_k\xi (j) \ne 0 \text{ for some } j=-1,\dots,-k\}$.
Then $J^1_{k}(\xi)=0$ and thus $o^1_k(\xi)=0$ for all $k \ge k_0$.
For $k=k_0-1$, since $J_m(\xi)=0$ for all $m>k$, we have $o^1_k(\xi)=0$ and $J^1_k(\xi)$ is determined by $M_k\xi$ only.
For $k=k_0-2$, we have $o^1_k(\xi)$ determined by $J^1_m(\xi)$ for $m>k$, which in turn is determined by $(M_m(\xi):m>k)$ and hence $J^1_k(\xi)$ is determined by $(M_m\xi:m>k)$.
Proceeding by downward induction, the same will be true for $k=k_0-2,k_0-3,\dots,2,1$.
This concludes the proof of Theorem~\ref{thm:hierarchy}.

\subsection{Reconstructing the configuration from the components}
\label{sub:reconstruction}

\begin{figure}[b]
\centering
\includegraphics[clip,width=0.9\textwidth]{figures/reconstruction-3}
\caption{\small
Reconstruction algorithm for a single excursion. This example is obtained using the field $\zeta$ shown in Fig.~\ref{fig:zeta-2}.}
\label{fig:reconstruction-3}
\end{figure}

\begin{figure}[b]
\centering
\includegraphics[clip,width=0.9\textwidth]{figures/zeta-2}
\par
\includegraphics[clip,width=0.95\textwidth]{figures/eta-reconstructed-3}
\caption{\small
Reconstruction of $\xi$ from $\zeta$.
In the lower part we show Records~$-2$ to~$2$ in boldface and the excursions between them.
Above we show the parts of the field $\zeta$ that used in the reconstruction of $\vep^{-2},\vep^{-1},\vep^{0},\vep^{1}$.
Reconstruction of $\vep^0$ was shown in Fig.~\ref{fig:reconstruction-3} and $\vep^{1},\vep^{-1},\vep^{-2}$ is shown in Fig.~\ref{fig:reconstruction-4}.}
\label{fig:zeta-2}
\end{figure}

\begin{figure}[b]
\centering
\includegraphics[clip,width=0.9\textwidth]{figures/reconstruction-4}
\caption{\small
Reconstruction algorithm for other excursions. The procedure is the same as in Fig.~\ref{fig:reconstruction-3} but all the intermediate steps are omitted.}
\label{fig:reconstruction-4}
\end{figure}

Consider the map $\xi \mapsto M\xi := (M_k\xi)_{k\ge 1}$ and let
\begin{align}
 \mathcal M:=\big\{ M \xi : \xi\in \cW \big\}\subset \big((\N_{0})^{\mathbb Z}\big)^{\mathbb N}
\end{align}
denote the set of possible component sequences obtained from decomposing configurations in ${\cW}$.
Since the decomposition $\xi \mapsto M\xi$ is insensitive to horizontal shifts, it is not possible to determine $\xi$ knowing $(M_k\xi)_{k\ge 1}$.
So we define the space
\begin{align}
\hcW:= \{\xi\in\cW: r(\xi,0)=0\}.
\end{align}
We remark that, unlike the lift $\xi[\eta]$ from $\cX$ to $\cW$ which was not unique, for $\eta$ in
\[
\hcX := \left\{ \eta\in\cX : 0 \text{ is a record for } \eta \right\}
\]
there is a unique lift $\xi[\eta]$ which is in $\hcW$, we denote it $\bxi[\eta]$.
So the operator $M$ defined in the Introduction is given by $M_k\eta = M_k\bxi[\eta]$.
To remain consistent with the previous subsections, we continue working with $\xi$ instead of $\eta$.

In the sequel we show that the map $M$ restricted to $\hcW$ is invertible.

The \emph{height} of the excursion between Records~0 and~1 is defined as $0$ if the excursion is empty or as $\max \{k\ge 1: M_k\xi(0)>0\}$ otherwise.
In general, denoting $i_k(j)$ the label of the $k$-slot located at Record~$j$, we define the height of the excursion between Record~$j$ and Record~$j+1$ by
\begin{align}
\label{eq:height}
m(j) :&=
\min\{k\ge 0:  M_{k'}\xi(i_{k'}(j))=0 \hbox{ for all }k'>k\} \in \{0,1,2,\dots\},
\end{align}
which is well-defined for every $\xi\in\cW$. Both $m(j)$ and $i_k(j)$ depend on $\xi$ but we omit it in the notation.
Let
\[
\zeta = (\zeta_k)_k = M \xi
.
\]
Note that, for each $\xi \in \cW$ and $j\in\Z$, $i_k(j)=r(\xi,j)$ for all large $k$.
Since $m(j)$ is finite, we have that
\begin{equation}
\label{eq:finitezeta}
\text{ for each } i\in\Z,\
\zeta_k(i) = 0
\text{ for all large }
k.
\end{equation}
Finally, define the \emph{support} of an excursion $\vep$ between successive records $y_1<y_2$ by $\{\vep\}:=\{y_1+1,\dots, y_2-1\}$ and denote the number of $k$ slots in the excursion by
\begin{align}
  \label{sup-vep}
  n_k(\vep) := 1 + |S_k \xi \cap \{\vep\}|,
\end{align}
where the term $1$ refers to the record $y_1$ preceding $\{\vep\}$ and the second term counts the number of $k$-slots belonging to an $m$-soliton of $\vep$ for some $m>k$.

Let $\zeta = (\zeta_k)_{k\ge 1} \in \mathcal M$, so in particular $\zeta$ satisfies~\eqref{eq:finitezeta}.
We first give an algorithm which permits to reconstruct the excursion $\vep$ of $\xi$ between Records 0 and 1.
Here is the algorithm:

\begin{algorithm}[H]
\label{alg:reconstruct}
  Let $\vep \in \hcW$ denote the empty excursion \\
  Let $m:= \min\{k\ge0: \zeta_{k'}(0)=0 \hbox{ for all }k'>k\}$ \\
  \For{$k = m,m-1,\dots,2,1$}{
    Let $n_k  := n_k(\vep)= \#\{x \in S_k \vep : r(\vep,0)\le x<r(\vep,1) \}$, as in~\eqref{sup-vep} \\
    \For{$i=0,1,\dots,n_k-1$}{
      Insert a number $\zeta_{k}(i)$ of $k$-solitons in the $i$-th $k$-slot of $\vep$, that is, to the right of site $x=s_k(\vep,i)$; boxes to the right of $x$ are shifted further right in order to accommodate the insertion of these $k$-solitons \\
      This produces an updated configuration $\vep$ \\
    }
  }
\end{algorithm}

Note that $m$ is well-defined by~\eqref{eq:finitezeta}.
In case $m=0$, the algorithm produces an empty excursion.
The procedure is illustrated in Fig.~\ref{fig:reconstruction-3}.
Call $\vep^0$ the excursion just constructed. Construct $\vep^1$, the excursion between Records~1 and~2, using the same algorithm but with the data $\zeta^1 = (\zeta^1_k)_{k\ge 1}$, where each component is given by
\[
\zeta^1_k = \big( \zeta_k(n_k+i) \big)_{i \geq 0},
\]
which consists of the entries of $\zeta$ with non-negative indices $i$ not used in the reconstruction of $\vep^0$.
Note that $\zeta^1$ also satisfies~\eqref{eq:finitezeta}.
Iterate this procedure to construct an infinite sequence of excursions $(\vep^j)_{j=0,1,2,\dots}$.
See Fig.~\ref{fig:reconstruction-4}.

To reconstruct the configuration to the left of Record~$0$, that is, to obtain the excursions $\vep^j$ with negative $j$, we use an analogous algorithm that uses the entries of $\zeta$ with $i$-indices starting at $-1$ and moving left instead of starting at $0$ and moving right.
First take $\zeta^{-1} = (\zeta^{-1}_k)_{k \geq 1}$ where each component is given by $\zeta^{-1}_k = \big( \zeta_k(i) \big)_{i < 0}$ and use $\zeta^{-1}$ to construct $\vep^{-1}$.
Then define $\zeta^{-2} = (\zeta^{-2}_k)_{k \geq 1}$ where each component is given by $\zeta^{-2}_k = \big( \zeta_k(i-n_k) \big)_{i < 0}$ and use it to construct $\vep^{-2}$.
Iterate this procedure to construct an infinite sequence of excursions $(\vep^j)_{j=-1,-2,\dots}$.

Put Record~$0$ at the origin and concatenate the excursions with one record between each pair of consecutive excursions.
This yields a walk denoted $\xi^*$, shown in Fig.~\ref{fig:zeta-2}.

Call $M^{-1}:\zeta \mapsto \xi^*$ the resulting transformation.
We claim that $M^{-1}$ is the inverse map of $M$ restricted to $\hcW$, that is, $M^{-1} M\xi = \xi$ for $\xi\in\hcW$.
We will sketch the proof of a single excursion $\vep$ omitting tedious details.
For $k\ge 0$, denote by $\vep_{[k]}$ the ball configuration obtained by removing all the boxes belonging to an $\ell$-soliton with $\ell\le k$.
Then $\vep_{[0]}=\vep$ and $\vep_{[k]}$ is the empty excursion for $k$ sufficiently large. Now observe from the previous definitions that $M_m\vep_{[k]}=M_m \vep$ for all $m>k$, as the $m$-slots are only created by solitons of sizes larger than $m$.
So the reconstruction algorithm correctly finds $\vep_{[k]}$ from $M_{k}\vep$ and $\vep_{[k+1]}$, hence it correctly finds $\vep$, completing the proof.

\section{Invariant measures}
\label{sec:measures}

In this section we prove Theorem~\ref{thm:invariant}.
More precisely, we show explicitly how invariant measures can be constructed by specifying the distribution of each $k$-component $\zeta_k$.

We refer to probability measures as simply \emph{measures}.
We also refer to measurable functions as \emph{random elements}, and refer to the push-forward of a pre-specified measure
by such functions
as the \emph{law} of these random elements.
A measure $\mu$ on $\cX$ is \emph{$T$-invariant} if $\mu \circ T^{-1} = \mu$.
The following is proved in \S\ref{sec:postponed}.
\begin{proposition}
\label{prop:bernoulli}
For $\lambda<\frac{1}{2}$, the product measure $\mathrm{Bernoulli}(\lambda)^{\otimes\Z}$ is $T$-invariant.
\end{proposition}
Besides the i.i.d.\ states, there are many other invariant measures for the BBS.
This is due to the existence of many conservation laws intrinsic to this dynamics, in particular the conservation of solitons studied in the previous section.

\subsection{Construction of the measures}
\label{sub:muconstruct}

Our recipe to produce invariant measures uses the construction described in \S\ref{sub:reconstruction}, which gives a distribution $\hmu$ of configurations ``seen from a typical record.''
The proof of Theorem~\ref{thm:invariant} is based on properties of $\hmu$ and how they relate to the the dynamics.
This relationship is given by the Palm theory, which we briefly recall now.

Denote the shifts by
\[
\theta\eta(y):= \eta(y+1) \text{ for } \eta\in \{0,1\}^\Z
,
\quad
\theta A = A-1 \text{ for } A \subseteq \Z
.
\]
Let $\eta\in \{0,1\}^\Z$.
Recalling~\eqref{eq:reta}, note that $\theta R \eta = R \theta \eta$.
Suppose $\eta\in\hcX$, and denote
\[
\ww(\eta) := \inf\{x\ge 1: x \in R\eta\}
.
\]
If such $\eta$ is random with law $\hmu$ such that $\hmu(\ww):=\int \ww(\eta)\,\hmu(\dd\eta) < \infty$, its \emph{inverse-Palm measure} $\mu=\Palm_{R}^{\Z}(\hmu)$ is defined as follows.
For every test function $\varphi$,
\begin{align}
\label{eq:palm1}
\int \varphi(\eta) \,\mu(\dd\eta)
:=
\int
\frac
{\textstyle\sum_{i=1}^{\ww(\eta)} \varphi(\theta^i\eta)}
{\ww(\eta)}
\cdot
\frac{\ww(\eta)}{\hmu(\ww)}
\hmu(\dd\eta)
.
\end{align}
In words, to sample a configuration distributed as $\mu$ one can first sample a configuration using the distribution $\hmu$ biased by the length of the first excursion, and then choose a site uniformly from this excursion to place the origin.

We define a bijection between $R\eta$ and $RT\eta$ as follows.
For $x \in R\eta$, let $\psi_\eta(x) := r(T \xi,j)$, where $x=r(\xi,j)$.
Note that this definition does not depend on the lift $\xi[\eta]$.
We define the \emph{record-shift} $\htheta:\hcX\to\hcX$ and the \emph{dynamics seen from a record} $\hT:\hcX\to\hcX$ by
\begin{align*}
\htheta \eta := \theta^{\ww(\eta)}\eta
\quad
\text{ and }
\quad
\hT \eta := \theta^{\psi_\eta(0)}T\eta.
\end{align*}
The following are standard properties of Palm measures which we prove in \S\ref{sub:palm}.

\begin{lemma}
\label{lemma:harris}
If $\hmu$ is $\htheta$-invariant and $\hmu(\ww)<\infty$, then
$\Palm_{R}^{\Z}(\hmu)$ is $\theta$-invariant, supported on $\cX$ and satisfies
\(
\Palm_{R}^{\Z}(\hmu) \circ T^{-1} = \Palm_{R}^{\Z}(\hmu \circ \hT^{-1})
.
\)
\end{lemma}

\begin{lemma}
\label{lemma:palmergodic}
If moreover $\hmu$ is $\htheta$-ergodic, then
$\Palm_{R}^{\Z}(\hmu)$ is $\theta$-ergodic.
\end{lemma}

Let $\zeta=(\zeta_k)_{k\ge 1}$ be independent random elements of $(\mathbb Z_{+})^{\mathbb Z}$ with shift-invariant distribution whose expectations satisfy $\sum_k k E[\zeta_k(0)] <\infty$.
Take $\xi=M^{-1} \zeta$ as the configuration reconstructed from soliton components $\zeta$ according to the algorithm described in \S\ref{sub:reconstruction} and depicted in Fig.~\ref{fig:zeta-2}.
Let $\hmu$ denote the resulting law of $\eta=\eta[\xi]$.

\begin{proposition}
\label{prop:invariant}
The measure $\hmu$ defined above is $\hT$-invariant and $\htheta$-invariant, and it also satisfies $\hmu(\ww)<\infty$.
If moreover $(\zeta_k(i))_{i\in\Z}$ is i.i.d.\ for each $k$, then $\hmu$ is also $\htheta$-ergodic.
\end{proposition}
Before giving the proof, let us see how it implies Theorem~\ref{thm:invariant}.

Let $\hmu$ be the law of $\eta = M^{-1}\zeta \in \hcX$, and define
\[
\mu:=\Palm_{R}^{\Z}(\hmu)
.
\]
By Proposition~\ref{prop:invariant} and Lemma~\ref{lemma:harris}, $\mu$ is $\theta$-invariant and supported on $\cX$.
Also, $$\mu\circ T^{-1} = \Palm_{R}^{\Z}(\hmu\circ\hT^{-1})=\Palm_{R}^{\Z}(\hmu)=\mu,$$ so $\mu$ is also $T$-invariant.
Moreover, under the i.i.d.\ assumption, the second part of Proposition~\ref{prop:invariant} combined with Lemma~\ref{lemma:palmergodic} imply that $\mu$ is $\theta$-ergodic.

\begin{remark}
[i.i.d.\ measures]
A natural question is whether the product measures $\nu_\lambda$ can be constructed in this way.
This is indeed the case, as shown in~\cite{FG18}.
\end{remark}

\begin{remark}
[Counter-examples]
\label{rmk:counter-examples}
It is possible for law $\mu$ of $\eta$ to be $\theta$-ergodic and $T$-invariant while its components $M_k \eta$ not being independent under $\hmu$.
Let $\zeta'$ be the configuration $\zeta'(x) = \one\{x \ \mathrm{mod} \ 3 = 0\}$. Let $\zeta_1=\zeta_4$ be a configuration chosen uniformly at random in the set $\{\zeta', \theta\zeta', \theta^2\zeta'\}$; let $\zeta_k\equiv 0$ for all $k\notin\{1,4\}$ and $\zeta=(\zeta_k)_{k\ge 1}$.
The reader can check that this example satisfies the stated properties.
Likewise, it is also possible for $\zeta$ to be independent over $k$, $\theta$-ergodic for each $k$, but produce (by the above procedure) a configuration $\eta$ whose law is not $\theta$-ergodic.
To see that, take $\zeta_5(x)\equiv 1$, $\zeta_1$ as in the previous example, $\zeta_k\equiv 0$ for all $k\notin\{1,5\}$ and $\zeta=(\zeta_k)_{k\ge 1}$.
We conjecture that if $\mu$ is $T$-invariant and $\theta$-mixing then the $\zeta_k$ are independent over $k$ and each one is $\theta$-mixing.
\end{remark}

\subsection{Invariance of the reconstructed configuration}
\label{sub:invariance}

We now prove the main part of Proposition~\ref{prop:invariant}, namely $\htheta$-invariance and $\hT$-invariance of $\hmu$, as well as $\theta$-ergodicity in case of i.i.d.\ components.
The proof of $\hmu(\ww)<\infty$ is given in \S\ref{sub:finitew}.
Denote by $E$ the integral with respect to the law of $\zeta$, and by $\cF(\cdot)$ the sigma-field generated by the random elements~$(\cdot)$.
First note that $\xi:=M^{-1} \zeta$ is a.s.\ well-defined.
Indeed,
since $\sum_k E[\zeta_k(0)] < \infty$,
the random field $\zeta$ a.s.\ satisfies~\eqref{eq:finitezeta} by Borel-Cantelli.

To show that $\hmu$ is $\hT$-invariant it suffices to show that the slot decomposition of $\hT\eta$ has the same law as $\zeta$.
More precisely, it suffices to show
\begin{align}
E\Bigl(\prod_{k=1}^n \varphi_k(M_k\hT\eta)\Bigr) = \prod_{k=1}^n E \varphi_k(\zeta_k),\qquad \text{ for each }n\ge 1,\label{ttt}
\end{align}
for test functions $\varphi_1,\dots,\varphi_n$, $k\ge 1$.

Note that we can write
\begin{align*}
&E\big(\varphi_k(M_k\hT\eta)\,\big|\,\cF(\zeta_m:m>k)\big)
\\
&\qquad= E\big(\varphi_k(\theta^{-o^1_k(\bxi[\eta])-k}M_k\eta)\,\big|\, \cF(\zeta_m:m>k)\big) \qquad (\hbox{by Theorem~\ref{thm:hierarchy}})
\\
&\qquad= E\big(\varphi_k(\theta^{-o^1_k(\bxi[\eta])-k}\zeta_k)\,\big|\, \cF(\zeta_m:m>k)\big) \qquad (\hbox{because }M_k\eta=\zeta_k)
\\
&\qquad= E\varphi_k(\zeta_k)
,
\end{align*}
because $\zeta_k$ is shift-invariant and independent of $(\zeta_m)_{m>k}$ whereas $o^1_k(\bxi[\eta])$ is determined by these elements.
The inductive step to show~\eqref{ttt} is then
\begin{align}
E\Bigl(\prod_{i=k}^n \varphi_i(M_i\hT\eta)\Bigr)
&= E\Bigl(E\Bigl(\prod_{i=k}^n \varphi_i(M_i\hT\eta)\Big| \cF(\zeta_m:m> k)\Bigr)\Bigr),
\\
&= E\Bigl( \prod_{i=k+1}^n \varphi_i(M_i\hT\eta) E\Bigl(\varphi_k(M_k\hT\eta)\Big| \cF(\zeta_m:m> k)\Bigr)\Bigr),
\\
&= E \varphi_k(\zeta_k) \ E\Bigl(\prod_{i=k+1}^{n} \varphi_i(M_i\hT\eta)\Bigr);
\end{align}
in the second identity we have used that $M_i\hT\eta$ is determined by $(\zeta_m)_{m\ge i}$.
This shows that $\hmu$ is $\hT$-invariant.

Finally, consider the transformation $M^{-1} : \zeta \mapsto \eta^*$, defined in \S\ref{sub:reconstruction} and call
$\vep^0_*$ the excursion of $\eta^*$ between Records~0 and~1. The construction of \S\ref{sub:reconstruction} gives
\begin{align}
\htheta \eta^*
=
\theta^{r(\bxi[\eta^*],1)}\eta^*
=
M^{-1} \big(\theta^{n_k(\vep^0_*)}\zeta_k: k\ge 1\big)
\end{align}
So it suffices to show that $( \theta^{n_k(\vep^0_*)}\zeta_k )_{k\ge1}$ has the same law as $(\zeta_k)_{k \ge 1}$.
But $n_k(\vep^0_*)$ is determined by $(\zeta_m)_{m>k}$, thus independent of $\zeta_k$.
Hence the law of $\zeta_k$ is invariant by the random shift of $n_k(\vep^0_*)$ and it is independent of $(\zeta_m)_{m>k}$.
This shows that $\hmu$ is $\htheta$-invariant.

Finally, under the extra assumption that $(\zeta_k(i))_{i\in\Z}$ is i.i.d.\ for each $k$,
the reconstruction map mentioned above will produce an i.i.d.\ sequence of excursions separated by records.
This in turn implies that the resulting configuration $\eta$ is $\htheta$-ergodic.

\subsection{Expected excursion length}
\label{sub:finitew}

We continue the proof of Proposition~\ref{prop:invariant} proving that $\hmu(\ww)<\infty$.
The proof is probabilistic but it could be reformulated in terms of the spectrum of an infinite sub-Markovian matrix.
We start by showing that the system
\begin{align}
\label{eq:skk1}
w_k &= 1 + {\sum_{m>k}} 2(m-k) w_m\alpha_m,\qquad k=0,1,2,\dots
\end{align}
has a unique finite solution $w=(w_k)_{k\ge 0}$, where
\begin{equation}
\label{eq:alphak}
\alpha_k :=
E[\zeta_k(0)]
.
\end{equation}
Then we will show that the average number of $k$-slots per excursion in $M^{-1} \zeta$ is $w_k$, whence the average number of $k$-solitons per excursion satisfies
\begin{equation}
\label{eq:rhok}
\rho_k=\alpha_k w_k
.
\end{equation}
In particular, this will imply that the average size of the excursions (including the record preceding them) satisfies
\begin{align}
\label{eq:wfinite}
\hmu(\ww) = w_0 = 1 + \sum_{m\ge1} 2m\, \rho_m <\infty.
\end{align}

So we start by studying~\eqref{eq:skk1}.
Let
\(
c_k := 2 {\sum_{m>k}}(m-k) \alpha_m
\)
and take $\tilde{k}$ such that
\(
\sum_{m>\tilde{k}} 4 m \alpha_m < 1
,
\)
so
$c_k< \frac{1}{2}$ for $k\ge \tilde k$. Let $K:= \{k\in\N:k\ge \tilde k\}\cup \{\aleph\}$ and consider a Markov chain $(X_n)_{n\ge 0}$ on $K$ with absorbing state $\aleph$ and transition probabilities $q(k,m) := 2(m-k) \alpha_m \one\{m>k\}$; $q(k,\aleph) = 1-c_k$; $q(\aleph,\aleph)=1$ and $q(k,m)=0$ otherwise. Define the absorption time by
$\tau:= \inf\{n\ge 0: X_n=\aleph\}$.
Denote by $E_k$ the law of $(X_n)_n$ starting from $k$.
By conditioning on $X_1$, we see that the expectations $w_k = E_k\tau$ satisfy the system~\eqref{eq:skk1}.
Since $c_k\ge c_{k+1}$, we have $P_k(\tau>n) \le c_k^{n}$ and thus
\(
w_k=  E_k\tau \le \frac{1}{1-c_k} < 2 < \infty, \hbox{ for $k\ge \tilde k$}.
\)
Since $w_{\tilde{k}}<\infty$, using~\eqref{eq:skk1} with $k=\tilde{k}-1$ we get $w_{\tilde{k}-1}<\infty$, and iterating this argument we get $w_k < \infty$ for all $k$.

We now consider truncated approximations for the reconstruction algorithm of \S\ref{sub:reconstruction}.

Let
\begin{equation}
\label{eq:zetatrunc}
\zeta^{[n]}_k(i) :=
\begin{cases}
\zeta_k(i), & k \le n,
\\
0 , & k>n.
\end{cases}

\end{equation}
Let $\vep^{[n]}$ denote the first excursion (i.e.\ the one between Records~0 and~1) of $M^{-1} \zeta^{[n]}$.
Let $W^n_k\zeta = n_k(\vep^{[n]})$ be the number of $k$-slots in $\vep^{[n]}$; see \eqref{sup-vep}.
Then $W^n_k\zeta \nearrow W_k\zeta$ a.s., where $W_k \zeta := W_k^\infty \zeta$.
Letting $w_k^n:=E[W^n_k\zeta]$ and $w_k:=E[W_k\zeta]$, by monotone convergence we have $w^n_k\nearrow w_k$ as $n\to\infty$.
On the other hand,
since each $m$-soliton contains $2(m-k)$ $k$-slots,
\begin{align}
W_k^n \zeta = 1 + \sum_{m>k} 2(m-k) \times (\hbox{number of $m$-solitons in $\vep^{[n]})$}
\end{align}
and thus
\begin{align}
w_k^n=1+\sum_{m>k} 2(m-k) E(\hbox{number of $m$-solitons in $\vep^{[n]})$}.
\end{align}
Let $\alpha^n_m := \alpha_m \one_{m\le n}$ denote the expected number of $m$-solitons per $m$-slot in $\zeta^{[n]}$.
Since $W^n_k\zeta$ is a function of $(\zeta_m:m>k)$ which is independent of $\zeta_k$, the expected number of $m$-solitons in $\vep^{[n]}$ is $w_m^n \times \alpha_m^n$.
Therefore, $(w_k^n)_{k \ge 0}$ and $(\alpha_k^n)_{k \ge 1}$ satisfy the system~\eqref{eq:skk1}.
Finally, since $w^n_k < 2$ for all $k \ge \tilde{k}$ and $n\in\N$, $w_k$ is finite for every $k$ and therefore~\eqref{eq:wfinite} is satisfied, concluding the proof.

\subsection{Palm transformations}
\label{sub:palm}

There is a bijection between $\theta$-invariant measures $\mu$ on $\cX$ and $\htheta$-invariant measures $\hmu$ on $\hcX$ with $\hmu(\ww)<\infty$.
Given such a $\mu$, we define
$\hmu=\Palm_{\Z}^{R}(\mu)$
by
\begin{equation}
\label{palm2}
\hmu := \mu( \ \cdot\ |\, 0\in R\eta),
\end{equation}
that is, $\hmu$ equals $\mu$ conditioned on $\eta$ having a record at $x=0$.

The two maps $\Palm_{\Z}^{R}$ and $\Palm_{R}^{\Z}$ are the inverse of each other.
Although their descriptions~\eqref{eq:palm1} and~\eqref{palm2}
may look different, they are in fact very similar.
Indeed, one can think of the conditioning on $0\in R\eta$ as biasing by the number of records at the origin.
So rewriting the two definitions we get
\begin{align*}
\int \varphi(\eta) \,\hmu(\dd\eta)
=
\frac
{\int \one_{\hcX}(\eta) \, \varphi(\eta) \, \mu(\dd\eta)}
{\int \one_{\hcX}(\eta) \, \mu(\dd\eta)}
\text{ and }
\int \varphi(\eta) \, \mu(\dd\eta)
=
\frac
{\int\textstyle\sum_{i=1}^{\ww(\eta)} \varphi(\theta^i\eta) \, \hmu(\dd\eta)}
{\int\textstyle \ww(\eta) \, \hmu(\dd\eta)}
.
\end{align*}

These expressions are the discrete version of the \emph{inversion formula} (8.4.14$^\circ$) on p.264 of~\cite{Thorisson00}.
Theorem~8.4.1 on p.260 says that this is a bijection between $\theta$-invariant measures $\mu$ on $\cX$ and $\htheta$-invariant measures $\hmu$ on $\hcX$ with $\hmu(\ww)<\infty$.

For use in \S\ref{sec:speeds}, we note that one can conveniently pass from one random subset to another.
Let $Z\eta$ be a subset of $\Z$ which depends on $\eta$ in a translation-covariant way ($Z\theta\eta = \theta Z\eta$) and which has $\mu$-a.s.\ positive density.
Writing
$\tilde{\mu} := \mu(\, \cdot \,|\, 0 \in Z\eta)$,
we have
\[
\tilde{\mu} = \Palm_{\Z}^Z (\mu) = \Palm_{\Z}^Z (\Palm_R^{\Z} (\hmu)) = (\Palm_{\Z}^Z \circ \Palm_R^{\Z}) (\hmu) =: \Palm_R^Z (\hmu)
,
\]
where the operator $\Palm_R^Z:\hmu\mapsto \tilde{\mu}$ is given as follows.
Writing $\tilde{\cX} := \{\eta\in\cX:0\in Z\eta\}$, we have
\begin{align}
\label{eq:generalpalm}
\int \varphi(\eta) \, \tilde{\mu}(\dd \eta)
=
\frac
{
\int
\textstyle
\sum_{i=1}^{\ww(\eta)}
\one_{\tilde{\cX}}(\theta^i\eta)
\varphi(\theta^i\eta)
\,
\hmu(\dd\eta)
}
{
\int
\textstyle
\sum_{i=1}^{\ww(\eta)}
\one_{\tilde{\cX}}(\theta^i\eta)
\,
\hmu(\dd\eta)
}
,
\end{align}
which follows immediately by combining the two equations above, the first with $\tilde{\mu}$ instead of $\hmu$ and the second with $\varphi \cdot \one_{\tilde{\cX}}$ instead of $\varphi$.

\begin{proof}
[Proof of Lemma~\ref{lemma:harris}]
The property saying that $\mu$ is $\theta$-invariant and supported on $\cX$ has been quoted above, so it remains to show the identity.
We include a proof of this classical result~\cite{Harris71,PortStone73} in our context for convenience of the reader.
Denote $\mu= \Palm_R^\Z (\hmu)$.
Since $\mu\mapsto\Palm_{\Z}^{R}(\mu)$ is a bijection, the identity is equivalent to $\Palm_{\Z}^R (\mu\circ T^{-1})= \hmu \circ \hT^{-1}$, which we prove now.
For a test function $\varphi$,
\begin{align}
\Palm_{\Z}^{R}(\mu\circ T^{-1})\varphi
&=
\tfrac{1}{\mu(\hcX)}
\int \one_{\hcX}(T\eta) \varphi(T\eta) \, \mu(\dd \eta)
\\
&=
\tfrac{1}{\mu(\hcX)}
\int
\sum_x
\one_{[x \in R\eta,\psi_\eta(x)=0]} \, \varphi(T\eta) \, \mu(\dd \eta)
\\
&=
\tfrac{1}{\mu(\hcX)}
\sum_x
\int
\one_{[0 \in R \theta^x \eta,\psi_{\theta^x\eta}(0)=-x]} \, \varphi(T\eta) \, \mu(\dd \eta)
\\
&=
\tfrac{1}{\mu(\hcX)}
\sum_x
\int
\one_{[0 \in R \eta,\psi_{\eta}(0)=-x]} \, \varphi(T \theta^{-x} \eta) \, \mu(\dd \eta)
\\
&=
\tfrac{1}{\mu(\hcX)}
\int
\one_{[0 \in R \eta]}
\sum_x
\one_{[\psi_{\eta}(0)=x]} \, \varphi(T \theta^{x} \eta) \, \mu(\dd \eta)
\\
&=
\tfrac{1}{\mu(\hcX)}
\int
\one_{[0 \in R \eta]}
\varphi(\hT \eta) \, \mu(\dd \eta)
\\
&=
\int \varphi (\hT\eta) \,\hmu(\dd\eta) = \big( \hmu \circ \hT^{-1}\big)\varphi
.
\end{align}
The forth identity holds by translation invariance of $\mu$.
\end{proof}

\begin{proof}
[Proof of Lemma~\ref{lemma:palmergodic}]
It suffices to show that the Cesàro limits are $\mu$-a.s.\ constant. Let $k_n\in \mathbb Z$ be such that $r(\eta, k_n)\le n < r(\eta, k_n+1)$. Then,
\begin{align}
\lim_n \frac1n\sum_{x=1}^n \varphi (\theta^x \eta)
&=
\lim_n \frac{k_n}{n}\frac{1}{k_n} \sum_{i=0}^{k_n-1}\sum_{j=1}^{r(\htheta^i\eta, 1)} \varphi(\theta^j \htheta^i \eta)
+
\lim_n \frac1n \sum_{x=r(\eta, k_n)+1}^n \varphi(\theta^x \eta)
\\
&=
\lim_n\frac
{\frac{1}{k_n} \sum_{i=0}^{k_n-1}\sum_{j=1}^{r(\htheta^i\eta, 1)}\varphi(\theta^j \htheta^i \eta)}
{\frac{1}{k_n} \sum_{i=0}^{k_n-1} r(\htheta^i \eta, 1)}\
\\
&=
\frac{\int\textstyle\sum_{j=1}^{\ww(\eta)} \varphi(\theta^j\eta) \, \hmu(\dd\eta)}{\int\textstyle \ww(\eta) \, \hmu(\dd\eta) } = \mu \varphi.
\qedhere
  \end{align}
\end{proof}

\section{Asymptotic speed of solitons}
\label{sec:speeds}

In this section we prove Theorems~\ref{thm:hspeed} and~\ref{thm:speedsexplicit}
from a combination of simpler statements.
By looking at the dynamics as seen from a $k$-soliton, we show that
the speed $v_k$ exists and equals the expected length of the jump of a typical $k$-soliton in one step.

In \S\ref{sub:speedexists} we show that the speed $v_k$ that appears in~\eqref{eq:speedexists} is $\mu$-a.s.\ well-defined and is given by~\eqref{eq:vfrompalm}.
We also show that it is given by~\eqref{eq:anothervfrompalm}, and in particular it is finite.
Analyzing the interaction between solitons of different sizes, in \S\ref{sub:speedequation} we show that the speeds $(v_k)_k$ satisfy~\eqref{eq:hspeedseq}.
Finally, in \S\ref{sub:speedexplicit} analyze the formula~\eqref{eq:anothervfrompalm} using the description of $\mu$ from \S\ref{sub:muconstruct} to show that the speeds are given by~\eqref{eq:hspeedexplicit}.

\subsection{Existence of speeds via Palm measure and ergodicity}
\label{sub:speedexists}

Recall the definition of $x(\gamma)$ given before the statement of Theorem~\ref{thm:hspeed}.
Let $\Gamma_k^\circ\eta:=\{x(\gamma): \gamma\in\Gamma_k\eta\}$ denote the set of leftmost sites of $k$-solitons of $\eta$.

For $\gamma\in\Gamma_k\eta$ and $z=x(\gamma)$, we define $\Delta_\eta^k(z) := x(\gamma^1)-x(\gamma)$, the size of the jump of $k$-soliton $\gamma$ after one iteration of $T$.
For $z\not\in \Gamma_k^\circ\eta$ we set $\Delta_\eta^k(z)=0$.
With this notation, the displacement of a tagged $k$soliton after $t+1$ iterations of $T$ can decomposed as
\[
x(\gamma^{t+1})-x(\gamma) = \Delta^k_\eta(x(\gamma)) + \Delta^k_{T\eta}(x(\gamma^1)) + \cdots + \Delta^k_{T^t\eta}(x(\gamma^t))
.
\]
We want to divide both sides by $t$ and use the Ergodic Theorem.
This will require a couple of subtle observations.
The first step is to consider the system as seen from a typical $k$-soliton.

Let $\hcX^k$ be the set of configurations in $\cX$ such that $0 \in \Gamma_k^\circ\eta$.
Let $\hmu_k:=\Palm_{\Z}^{\Gamma_k^\circ}(\mu)$ be the Palm measure of $\mu$ with respect to $\Gamma_k^\circ\eta \subseteq \Z$, i.e., $\hmu_k=\mu(\,\cdot\,|\,0\in \Gamma_k^\circ\eta)$.
For $\eta\in\hcX^k$, let $\ww^k(\eta) := \inf\{x\ge 1: x\in \Gamma_k^\circ\eta \}$ and define $\htheta_k : \hcX^k \to \hcX^k$ as the ``shift to the next $k$-soliton'' given by $\htheta_k \eta := \theta^{\ww^k(\eta)}\eta$.
Also, for a $k$-soliton $\gamma$ such that $x(\gamma)=0$, let $\hT_k\eta := \theta^{x(\gamma^1)} T\eta$ denote the dynamics as seen from a tagged $k$-soliton.

As in Lemma~\ref{lemma:harris}, $T$-invariance of $\mu$ implies $\hT_k$-invariance of $\hmu_k$.
On the other hand, for $\eta \in \hcX^k$, and $\gamma$ containing $x=0$ the above decomposition becomes
\[
x(\gamma^{t+1}) = \Delta^k_{\eta}(0) + \Delta^k_{\hT_k\eta}(0) + \Delta^k_{\hT_k^2\eta}(0) + \cdots + \Delta^k_{\hT_k^t\eta}(0).
\]
By the Ergodic Theorem for $(\hT_k^t\eta)_{t \in \Z}$, $\lim\limits_{t\to\infty} \frac{1}{t}x(\gamma^t)$ exists $\hmu_k$-a.s., and on average it equals
\begin{equation}
\label{eq:vfrompalm}
v_k
:=
\int \Delta_\eta^k(0) \, \hmu_k(\dd\eta)
.
\end{equation}
It remains to show that it is in fact non-random.
Consider the field
\[
\tv_k(\eta,z) :=
\begin{cases}
\lim\limits_{t\to\infty}
\dfrac{x(\gamma^t)}{t}, &\hbox{if } z = x(\gamma) \text{ for } \gamma\in\Gamma_k(\eta), \\
0,&\hbox{otherwise.}
\end{cases}
\]
Since
\(
( \tv_k(\eta,x) )_{x\in\Z}
\)
is a $\htheta_k$-covariant function of $\eta$, its distribution is $\htheta_k$-ergodic.
On the other hand, since different tagged $k$-solitons never overtake each other, we have
\[
\tv_k(\eta,x) \le \tv_k(\eta,y) \text{ for all } x\le y \text{ in } \Gamma_k^\circ\eta
.
\]
By $\htheta_k$-ergodicity, this implies that the non-zero entries of this field are a.s.\ constant.

Finally, applying~\eqref{eq:generalpalm} to~\eqref{eq:vfrompalm} we get
\begin{equation}
\label{eq:anothervfrompalm}
v_k
=
\frac
{
\int
\textstyle
\sum_{i=1}^{\ww(\eta)}
\one_{\hcX^k}(\theta^i\eta)
\Delta_{\theta^i\eta}^k(0)
\,
\hmu(\dd\eta)
}
{
\int
\textstyle
\sum_{i=1}^{\ww(\eta)}
\one_{\hcX^k}(\theta^i\eta)
\,
\hmu(\dd\eta)
}
=
\frac{1}{\rho_k}
\int
\sum_{y=1}^{\ww(\eta)}
\Delta_{\eta}^k(y)
\,
\hmu(\dd\eta)
.
\end{equation}
Since $\sum_{y=1}^{\ww(\eta)} \Delta_{\eta}^k(y) \le \ww(\eta)$,
we get $v_k \le \frac{w_0}{\rho_k} < \infty$.

\subsection{Equation for speeds from soliton interactions}
\label{sub:speedequation}

We now prove that the speeds satisfy~\eqref{eq:hspeedseq}.
We start by analyzing how collision affects the displacement of solitons.
Let $m>k$, $\tilde{\gamma}\in \Gamma^m\eta$ and $\gamma\in \Gamma^k\eta$.
We observe that $\tilde{\gamma}$ takes over ${\gamma}$ in two time steps, both when $\tilde{\gamma}$ is free to move forward, i.e., when it is not nested inside a bigger soliton.
The first step occurs when $\gamma$ is nested in the right half of $\tilde{\gamma}$, after which it will be nested in the left half of $\tilde{\gamma}$.
The second step occurs when $\gamma$ is nested in the left half of $\tilde{\gamma}$ after which it will no longer be nested inside $\tilde{\gamma}$.
During these two steps, $\gamma$ is prevented from moving due to the collision with $\tilde{\gamma}$.
For each step in between, $\gamma$ is also prevented from moving, but this is due to collision between $\gamma$ and the largest soliton in the nesting chain (the only which is free to move), not with $\tilde{\gamma}$ which is also prevented from moving.
So collision with $\tilde{\gamma}$ causes $\gamma$ to stay put at two time steps.
Conversely, collision with $\gamma$ causes $\tilde{\gamma}$ to move $2k$ units more than it normally would have.

Let $\gamma \in \Gamma_k \eta$ be such that
$0 = x(\gamma)$.
After $t$ steps we have
\begin{equation}
\label{eq:displacement}
x(\gamma^{t}) = k\, t - 2k \sum_{m>k} N_t^m + \sum_{m<k} 2m \, N_t^m
.
\end{equation}
Here $N_t^m$ counts the number of $m$-solitons which collide with the tagged soliton $\gamma$ during steps $1,\dots,t$.
The first and last of such collisions is counted as a half in case only one of the two steps described above occurs in this lapse, so $N_t^m$ may be a half integer.

Assume $\orho_m=0$ for all large $m$.
By~\eqref{eq:speedexists} and~\eqref{eq:displacement}, to get~\eqref{eq:hspeedseq} it suffices to show that
\begin{equation}
\label{eq:collisions}
\displaystyle \tfrac{1}{t} N_t^m \to \orho_m |v_k-v_m| \quad\text{ in probability under }\hmu_k.
\end{equation}
Let $m>k$.
Consider the rightmost $m$-soliton of $\eta$ contained in $(-\infty,-1]$ and let $X^-_t$ be its position at time $t$.
Likewise, consider the leftmost $m$-soliton of $\eta$ contained in $[1,+\infty)$ and let $X^+_t$ be its position at time $t$.
Now $N_t^m$ is bounded from above by the number of $m$-solitons in $T^t \eta$ which intersect $[x(\gamma^t),X_t^+]$ and bounded from below by the number of $m$-solitons which are contained in $[x(\gamma^t),X_t^-]$.
By~\eqref{eq:speedexists}, $\frac{1}{t}x(\gamma^t) \to v_k$ and $\frac{1}{t} X_t^\pm \to v_m$, $\hmu_k$-a.s.
Hence, by definition of $\orho$ and the Ergodic Theorem, the upper and lower bounds are both close to $\orho_m(v_m-v_k)$, with high probability as $t$ increases.
This proves~\eqref{eq:collisions} for $m>k$.
The case $m<k$ is analogous.

To complete the proof of~\eqref{eq:hspeedseq}, it remains to drop the assumption that $\orho_m=0$ for all large $m$.

The above proof contains all the argument, except that combining~\eqref{eq:displacement} and~\eqref{eq:collisions} requires a limit and an infinite sum to commute. To prove the general case, we take expectation in~\eqref{eq:displacement} with $t=1$ and combine it with~\eqref{eq:vfrompalm}:
\begin{align}
v_k &= \int x(\gamma^1) \hmu_k (\dd \eta) =
\int \Big[ k - \sum_{m>k} 2k\,N_1^m + \sum_{m<k} 2m\, N_1^m \Big] \, \hmu_k(\dd \eta)
\\
& =
k + \sum_{m \ne k} c_{k,m} \int N_1^m(\eta) \, \hmu_k(\dd \eta),
\end{align}
where $c_{k,m} = -2k$ for $m>k$ and $2m$ for $m<k$.
So it remains to show that $\int N_1^m(\eta) \, \hmu_k(\dd \eta) = \orho_m|v_k-v_m|$.
Similar to the argument in \S\ref{sub:speedexists}, we decompose
\[
N_{t+1}^m(\eta) = N_1^m(\eta) + N_1^m(\hT_k \eta) + N_1^m(\hT_k^2 \eta) + \dots + N_1^m(\hT_k^t \eta)
.
\]
By $\hT_k$-invariance, $\frac{1}{t}N_t^m(\eta)$ converges $\hmu_k$-a.s.\ to a random variable (i.e.\ a measurable function of $\eta$) whose average is $\int N_1^m(\eta) \, \hmu_k(\dd \eta)$.
Now this variable is in fact constant and equal to $\orho_m|v_k-v_m|$ by~\eqref{eq:collisions}, concluding the proof.

\subsection{Recursion formulas for independent components}
\label{sub:speedexplicit}

We finally prove~\eqref{eq:hspeedexplicit}.
Let $\zeta = M \eta$.
We are assuming that the field $\left\{ \zeta_k(i) \right\}_{i\in\Z}$ is i.i.d.\ over $i$ for each $k$, and independent over $k$.
So let us proceed the other way around.
We let $P$ denote the law of $\zeta$ and $E$ the corresponding expectation.
In this notation, $\hmu$ is the law of $\eta=M^{-1} \zeta$.

Note that~\eqref{eq:skk1} and~\eqref{eq:rhok} give the first two equations in~\eqref{eq:hspeedexplicit}.
The third equation can be taken as the definition of $s_k$, it is a simple recursive definition once one has $\rho$, $w$ and $\alpha$.
Combining these with~\eqref{eq:anothervfrompalm}, to get the last equation in~\eqref{eq:hspeedexplicit} we need to show that
\begin{equation}
\label{eq:totaldisplacement}
E \sum_{y=1}^{\ww(\eta)} \Delta^k_\eta(y)
=
\alpha_k \cdot s_k
.
\end{equation}
We now use the assumption that $\eta=M^{-1} \zeta$, where $M^{-1}$ denotes de reconstruction map of \S\ref{sub:reconstruction}.
First note that $\sum_{y=1}^{\ww(\eta)} \Delta^k_\eta(y)$ equals the sum over all $k$-solitons $\gamma$ in the first excursion of $\eta$ of the size of the jump of $\gamma$ in one time step, that is $x(\gamma^1)-x(\gamma)$.
Moreover, $k$-solitons appended to $k$-slots belonging to bigger solitons will stay frozen, just switching zeros for ones, and only the $k$-solitons which are appended directly to the $0$-th $k$-slot at $x=0$ will actually jump.
Furthermore, the size of their jump equals the distance between their leftmost one and their leftmost zero, that is, the distance between the tip of their head and the tip of their tail.

Now the number of $k$-solitons appended to the $0$-th $k$-slot is exactly $\zeta_k(0)$, which on average equals $\alpha_k$ by~\eqref{eq:alphak}.
So to conclude the proof of~\eqref{eq:totaldisplacement}, it is enough to observe that $s_k$ given by the recursion relation in~\eqref{eq:hspeedexplicit} in fact gives the average distance between the tips of the head and tail of a typical $k$-soliton.

We show a stronger statement: that $s_k$ equals both the average distance between the tip of the head and the tip of the tail as well as the average distance between the tip of the tail and the next $k$-slot.
We made the statement stronger so we can prove it by induction.
For $k=1$ we have $s_1=1$, consistent with the fact that a $1$-soliton is always given by the strings $a=10$ or $\tilde{a}=01$ with nothing appended inside.
For $k=2$, note that each $2$-soliton (including smaller solitons appended to its slots) is of the form $b=11\tilde{a}^*00{a}^*$ or $\tilde{b}=00{a}^*11\tilde{a}^*$ where $a^*$ stands for $\zeta_1(i)$ copies of $a$ and $\tilde{a}^*$ stands for $\zeta_1(j)$ copies of $\tilde{a}$ for some $i,j$ which are determined by $\{\zeta_m\}_{m>1}$.
So the average size of $11\tilde{a}^*$ and that of $00a^*$ both equal $2+2\alpha_1$.
For $k=3$, note that each $3$-soliton is of the form
${c}=11\tilde{a}^*1\tilde{a}^*\tilde{b}^*00{a}^*0{a}^*{b}^*$
or
$\tilde{c}=00{a}^*0{a}^*{b}^*11\tilde{a}^*1\tilde{a}^*\tilde{b}^*$
where $b^*$ stands for $\zeta_2(i)$ independent copies of $b$, etc.
So the average size of each half of a $3$-soliton equals $s_3=3 + 2s_2 \alpha_2 + 4 s_1 \alpha_1$.
The induction step is clear, which concludes the proof of~\eqref{eq:hspeedexplicit}.

\subsection{Vertical speed}
\label{sub:vertical}

For $\beta \in R\eta$, we define
\(
\beta^{t}:=r(T^t \xi,j),

\text{ where }
\beta=r(\xi,j)
.
\)
Note that this definition does not depend on the lift $\xi[\eta]$.
Recalling~\eqref{eq:trackslot},
we define displacement of a tagged $k$-slot $\pi\in S_k\eta$ measured in terms of records by
\[
y_k^t(\eta,\pi) = \# \left\{ \beta\in R\eta: \pi < \beta \text{ and } \pi^{k,t} \ge \beta^t  \right\}
,
\quad
\pi \in S_k \eta
.
\]
In case there is a $k$-soliton $\gamma\in\Gamma_k\eta$ appended to the $k$-slot $\pi$ in $\eta$, the tagged $k$-soliton $\gamma^t$ will appear appended to the $k$-slot $\pi^t$ in $T^t\eta$, so $y_k^t$ also measures the displacement of tagged $k$-solitons.

\begin{theorem}
\label{thm:speeds}
Let $\mu$ be a measure on $\cX$ such that under $\hmu$ each $k$-component $M_k \eta$ is i.i.d.\ and they are independent over $k$.
There exists a non-decreasing deterministic sequence $h=(h_k)_{k\ge 1}$ such that, $\mu$-a.s.\ on $\eta$, for all $k\in\N$ and $\pi\in S_k\eta$,
\begin{align}
\label{eq:vk0}
\lim_{t\to\infty} \frac{y_k^t(\eta,\pi)}{t} &= h_k
\in [k,\infty].
\end{align}
Assuming
\(
\sum_{k} k^2 \rho_k < \infty,
\)
the vector $(h_k)_{k\ge 1}$ is the unique finite solution of the linear system
\begin{align}
\label{eq:veleq}
h_k &= k + \sum_{m>k} 2(m-k)(h_m-h_k)\rho_m ,\quad k\ge 1
.
\end{align}
The asymptotic speed of tagged records is given by
\begin{align}
\label{eq:6.1}
\lim_{t\to\infty} - \frac{\beta^t}{t}
=
v_0
:=
\sum_{m\ge 1}  2m \rho_m h_m,
\quad
\text{for all } \beta\in R\eta,\
\mu\text{-a.s.}
\end{align}
The asymptotic speed $v_k$ of tagged $k$-slots is also given by
\begin{align}
\label{eq:6.2}
\lim_{t\to\infty} \frac{\pi^{k,t}}{t} =
v_k =
h_k w_0 - v_0
,\quad
\text{ for all } \pi\in S_k\eta,\
\mu\text{-a.s.}
,
\end{align}
From the two last equations, the speed of tagged records is also given by
\begin{align}
\label{eq:anothervzero}
v_0=\sum_{m\ge 1}  2m \rho_m v_m.
\end{align}
Furthermore, the vertical speed of the walk representation $\xi=\bxi[\eta]$ is given by
\begin{equation}
\label{eq:h0}
\lim_{t\to\infty} -\frac{T^t\xi(0)}{t} = h_0 := \frac{v_0}{w_0}.
\end{equation}
\end{theorem}

We outline the proof of the first four equations, referring to \href{https://arxiv.org/abs/1806.02798v3}{arXiv:1806.02798v3} for the details.

The proof of~\eqref{eq:vk0} is similar to that of~\eqref{eq:speedexists}.
Each time an $m$-soliton overtakes a $k$-soliton, this causes the position of the $k$-soliton measured in records to be incremented by an extra factor of $2(m-k)$. On the other hand, the position of a soliton measured in records is not affected by overtaking smaller solitons.
These two facts explain the origin of~\eqref{eq:veleq}.

Each time a tagged $m$-soliton crosses a tagged record from left to right, it causes the record to move $2m$ boxes left.
On the other hand, by mass conservation the number of such crossings by time $t$ equals $\rho_m y_m^t$ which is about $\rho_m h_m t$ by~\eqref{eq:vk0}.
Summing over $m$ we get~\eqref{eq:6.1}.

Finally, by~\eqref{eq:vk0}, the tagged $k$-slot $\pi = 0 \in S_k \xi$ will typically have crossed about $h_k t$ records by time $t$, so it will be between two tagged records with initial index about $h_k t$.
By ergodicity, the initial position of these records is about $w_0 h_k t$, so by~\eqref{eq:6.1} their position at time $t$ will be about
$w_0 h_k t - v_0 t$.
Dividing by $t$ and taking a limit one gets~\eqref{eq:6.2}.

From~\eqref{eq:6.2} we have $h_m = \frac{v_0+v_m}{w_0}$, substituting into~\eqref{eq:6.1} and using~\eqref{eq:wfinite} we get~\eqref{eq:anothervzero}.
To prove~\eqref{eq:h0} we note that after $t$ iterations of $T$, Record~$i$ will be at $x=o(t)$ if $r(\xi,i) = v_0 t + o(t)$, which implies that $T^t \xi(0) = i + o(t)$.
On the other hand, $r(\xi,i) = w_0 i + o(i)$, whence $T^t \xi(0) = h_0 t + o(t)$, concluding the proof.

\section{Postponed proofs}
\label{sec:postponed}

\begin{proof}
[Proof of Proposition~\ref{prop:bernoulli}]
By~\eqref{eq:Txi}, this statement corresponds to the discrete version of Pitman's $2M-X$ theorem, see~\cite{HamblyMartinOConnell01,Pitman1975}.
We will prove it here following the proof of Burke's Theorem given in~\cite{Reich}.
Recall the nearest-neighbor walk $\xi=\xi[\eta]$, which is in this case distributed as a simple random walk with i.i.d.~increments distributed as Bernoulli$(\lambda)$. We introduce the reflected process: $W(x)=\xi(x)-\min\limits_{y\le x}\xi(y)$, $x\in \mathbb Z$.
Then for all $x$, $W(x)$ has distribution $\mathrm{Geom}(\frac{\lambda}{1-\lambda})$, that is, $\mathbb P(W(x) \ge k)=(\frac{\lambda}{1-\lambda})^k$. Moreover, $W$ is \emph{reversible}. Observe that we can recover $\eta$ from $W$: $A:=\{x\in \mathbb Z: \eta(x)=1\}=\{x\in \mathbb Z: W(x)-W(x-1)=1\}$. We also write $A^c:=\{x\in \mathbb Z: \eta(x)=0\}:=D\cup R$, where $D:=\{x\in \mathbb Z: W(x)-W(x-1)=-1\}$ and $R:=\{x\in \mathbb Z: x \text{ is a record}\}=\{x\in \mathbb Z: W(x)=0\}$. Notice that $T\eta$ consists in reversing the increments of the boxes in $A$ and $D$; in other words, exchange the roles of $A$ and $D$. But the reversibility of $W$ implies that $A$ has the same distribution as $D$.
The conclusion then follows.
\end{proof}

\begin{proof}
[Proof of Proposition~\ref{prop:solitontrack}]
Let us prove for finite $\eta$ first.
The proof is by induction on number of balls contained in $\eta$.
Identifying $0$ with ``$\ominus$'' and $1$ with ``$\oplus$'', consider the following data stream version of the TS-Algorithm.

\begin{algorithm}[H]
  Start with the word $\ominus^\infty$ which is semi-infinite to the left  \\
  \For{\rm each symbol in the finite configuration $\eta$}{
    Append the symbol to the word
    \\
    Perform annihilation if the two last runs have the same length
    \\
    Symbols that annihilate correspond to a soliton
  }
\end{algorithm}

For example, for the finite sequence $\eta=\oplus\oplus\ominus\oplus\oplus\ominus\ominus\oplus\oplus\oplus\ominus\ominus\ominus\ominus\ominus$ the algorithm would produce the words
$\ominus^\infty\oplus$,
$\ominus^\infty\oplus^2$,
$\ominus^\infty\oplus^2\ominus$,
$\ominus^\infty\oplus^2\underline{\ominus\oplus}$,
$\ominus^\infty\oplus^3$,
$\ominus^\infty\oplus^3\ominus$,
$\ominus^\infty\oplus^3\ominus^2$,
$\ominus^\infty\oplus^3\ominus^2\oplus$,
$\ominus^\infty\oplus^3\underline{\ominus^2\oplus^2}$,
$\ominus^\infty\oplus^4$,
$\ominus^\infty\oplus^4\ominus$,
$\ominus^\infty\oplus^4\ominus^2$,
$\ominus^\infty\oplus^4\ominus^3$,
$\ominus^\infty\underline{\oplus^4\ominus^4}$,
and
$\ominus^\infty\ominus=\ominus^\infty$,
identifying a $1$-soliton, a $2$-soliton and a $4$-soliton.
For the example in Fig.~\ref{fig:algo}, it produces
$\ominus^\infty\oplus$,
$\ominus^\infty\oplus^2$,
$\ominus^\infty\oplus^3$,
$\ominus^\infty\oplus^4$,
$\ominus^\infty\oplus^4\ominus$,
$\ominus^\infty\oplus^4\ominus^2$,
$\ominus^\infty\oplus^4\ominus^2\oplus$,
$\ominus^\infty\oplus^4\ominus^2\underline{\oplus\ominus}$,
$\ominus^\infty\oplus^4\ominus^2\oplus$,
$\ominus^\infty\oplus^4\underline{\ominus^2\oplus^2}$,
$\ominus^\infty\oplus^5$,
$\ominus^\infty\oplus^5\ominus$,
$\ominus^\infty\oplus^5\underline{\ominus\oplus}$,
$\ominus^\infty\oplus^5\ominus$,
$\ominus^\infty\oplus^5\ominus^2$,
$\ominus^\infty\oplus^5\ominus^3$,
$\ominus^\infty\oplus^5\ominus^4$,
$\ominus^\infty\oplus^5\ominus^4\oplus$,
$\ominus^\infty\oplus^5\ominus^4\oplus^2$,
$\ominus^\infty\oplus^5\ominus^4\oplus^2\ominus$,
$\ominus^\infty\oplus^5\ominus^4\oplus^2\underline{\ominus\oplus}$,
$\ominus^\infty\oplus^5\ominus^4\oplus^3$,
$\ominus^\infty\oplus^5\ominus^4\oplus^3\ominus$,
$\ominus^\infty\oplus^5\ominus^4\oplus^3\ominus^2$,
$\ominus^\infty\oplus^5\ominus^4\underline{\oplus^3\ominus^3}$,
$\ominus^\infty\underline{\oplus^5\ominus^5}$,
identifying three $1$-solitons, a $2$-soliton, a $3$-soliton, and a $5$-soliton.

Let us call \emph{$\oplus$-alternating suffix} (or simply \emph{$\oplus$-suffix}) a finite word $\omega$ which is either empty or starts with $\oplus$ and such that each run in the word is strictly longer than the next one.
So the above algorithm always produces words given by $\ominus^\infty$ followed by a $\oplus$-suffix.
We define \emph{$\ominus$-suffix} in the obvious way.
The \emph{net value} $v(\omega)$ of a finite suffix $\omega$ is the number of $\oplus$'s minus the number of $\ominus$'s.

Remark~1. The net value of a non-empty $\oplus$-suffix $\omega$ is positive and it is at most equal to the length $\ell_1(\omega)$ of its first run (e.g.\ for $\cdots\oplus^4\ominus^3\oplus$ we have $0 < 2 \le 4$).
In particular, $v(\omega)=\ell_1(\omega)$ only if it consists of a single run.

Remark~2. The net value of a finite suffix $\omega$ equals the net value of the portion of $\eta$ that generated it, which in turn is given by the net increase in $\xi[\eta]$.

Remark~3. If the suffixes $\omega_1,\dots,\omega_n$ produced while processing a certain piece of $\eta$ are all $\oplus$-suffixes, then $\ell_1(\omega_n)$ equals the maximal net value of $\omega_i$ for $i=1,\dots,n$.
In particular, if $v(\omega_n)=\max_{i} v(\omega_i)$, then $\ell_1(\omega_n)=v(\omega_n)$ and, by Remark~1, $\omega_n$ consists of a single run.

To prove the proposition we will split a finite $\eta$ into three blocks and analyze how they interact under the data stream algorithm, both before and after the application of $T$, as shown in Fig.~\ref{fig:proof-prop-conserv}.

\begin{figure}[b]
\centering
\includegraphics[width=.8\textwidth]{figures/proof-prop-conserv-2}
\caption{\small
Example showing conservation of solitons by splitting space in three parts: rising, falling and remainder. After applying $T$, the configuration on the rising and falling parts are flipped, the smaller solitons are conserved and flipped, the biggest soliton moves forward, and will have its tail in the remainder part. Applying $T$ to the remainder part conserves solitons by induction.}
\label{fig:proof-prop-conserv}
\end{figure}

Define the first non-empty soft excursion as the piece of $\eta$ going from the first $\oplus$ until the first point that makes the net value equal zero.
Split this excursion into \emph{rising} and \emph{falling} parts as follows.
The rising part goes until the point where the net value $k$ is maximal (in case the maximum is attained more than once, take the rightmost one), and the falling part consist of the remaining boxes, until the end of the first soft excursion.
The \emph{remainder} consists of all the sites to the right of the falling block.
Let $I_1,I_2,I_3 \subseteq \Z$ denote these sets of sites.

By definition of $I_1$ and by Remark~2, the streaming algorithm applied to $\eta$ on $I_1$ always produces a non-empty $\oplus$-suffix, its net value is always at most $k$ and ends being equal to $k$.

By Remarks~1 and~3, the word produced by the algorithm after processing this first block is $\oplus^k$.
By similar considerations, the algorithm applied to $\eta$ on $I_2$ always produces non-empty $\ominus$-suffixes whose net values are strictly between $-k$ and $0$, except for the final step when it produces $\ominus^k$.

Hence, when processing $\eta$ on $I_1 \cup I_2$, the $\oplus^k$ obtained after processing the rising part is kept untouched until the very end, when it is annihilated by the $\ominus^k$ obtained after processing the falling part.
So when the algorithm starts processing $\eta$ on $I_3$ there is no suffix left by the previous steps and this part of $\eta$ is decomposed into solitons just as it would if it was processing $\eta_{|_{I_3}}$ instead.

Now notice that, by the definition of $T$ on $\xi[\eta]$, the net value of $T \eta$ on any prefix of $I_3$ is non-positive.
Indeed, at the rightmost site $y$ of $I_2$, the walk $\xi$ coincides with its running minimum, so $T\xi(y)=\xi(y)$ and $T\xi(x) \le T\xi(y)$ for all $x>y$.
Hence, applying the streaming algorithm to this portion of $T\eta$ produces a $\ominus$-suffix at all steps.

Also, since $\xi(x) \ge \xi(y)$ for all $x\in I_1 \cup I_2$, by definition of $T$ we have that $\eta$ and $T \eta$ are the complementary of each other on these two blocks.
So by the previous observations, the streaming algorithm applied to $\eta$ and to $T \eta$ on $I_1$ will produce exactly the opposite suffixes at every step.
The same is true for $I_2$.
The only difference is that now the $\ominus^k$ produced after processing $T\eta$ on $I_1$ is incorporated into the infinite prefix $\ominus^\infty$, and it will not annihilate with the $\oplus^k$ obtained after processing $T\eta$ on $I_2$.
Hence, while processing $T\eta$ on $I_1 \cup I_2$, the same solitons will be generated, with $\oplus$ replaced by $\ominus$, that is, with the head occupying the former position of the tail, except for this last $k$-soliton.

Finally, the $\oplus^k$ obtained after processing $T\eta$ on $I_1 \cup I_2$ will not increase its length while processing $T\eta$ on $I_3$, because processing $T\eta$ on $I_3$ always produces $\ominus$-suffixes.
So this run $\oplus^k$ is preserved until the first time when the processing of $T\eta$ on $I_3$ produces a $\ominus^k$, and they both annihilate.
This eventually occurs because $T \eta$ has infinitely many records to the right.
So again the head of the corresponding $k$-soliton will take the position previously occupied by the tail of a $k$-soliton.
Moreover, when it occurs, it annihilates $\ominus$'s that were not going to be annihilated while processing $(T\eta)_{|_{I_3}}$
because they would have been simply absorbed by the prefix $\ominus^\infty$.
Hence, the presence of this $\oplus^k$ does not change how the algorithm processes $T\eta$ on $I_3$, neither before nor after such annihilation occurs.
To conclude, note that $\eta_{|_{I_3}}$ contains fewer balls than $\eta$ so we can assume by induction that the tails of all the solitons of $\eta_{|_{I_3}}$ will become the heads of the solitons of $T\eta_{|_{I_3}}$, proving the proposition for the case of a finite configuration $\eta$.

We finally consider general $\eta\in\cX$.
Let $A$ be a set of $k$ sites.
Let $y_2,y_3$ be records for $T\eta$ to the left and right of $A$, respectively.
Let $y_1<y_2$ and $y_4>y_3$ be records for $\eta$.
Let $\eta'$ denote the restricted configuration, given by $\eta'(x):=\eta(x)\one_{[y_1, y_4]}(x)$
Since solitons are always contained in the interval between two consecutive records, if some $\gamma\in\Gamma_k\eta$ intersects $A$ then it is contained in $[y_1,y_4]$. Since $\eta'\le\eta$, and $x$ being a record for $\eta$ is a non-decreasing property in $\eta$, $y_1$ and $y_4$ are also records for $\eta'$.
Hence, the soliton configuration $\Gamma_k\eta$ restricted to $[y_1,y_4]$ coincides with $\Gamma_k\eta'$.
Now notice that $T\eta'=T\eta$ on $[y_1,y_4]$ and $T\eta'=0$ on $(-\infty,y_1]$.
In particular, $T\eta'=T\eta$ on $[y_2,y_3]$, $T\eta' \le T\eta$ on $(-\infty,y_2]$,
and thus $y_2,y_3$ are also records for $T\eta'$.
Hence, by the same argument as above, if some $\gamma\in\Gamma_k\eta'$ intersects $A$ then it is contained in $[y_2,y_3]$, moreover $\Gamma_k T \eta$ restricted to $[y_2,y_3]$ coincides with $\Gamma_k T \eta'$ restricted to $[y_2,y_3]$.
Since $\eta'$ is a finite configuration, by the previous case this concludes the proof.
\end{proof}

\section*{Acknowledgments}

We thank Roberto Fernández for very helpful discussions.

{
\small
\setstretch{1}
\bibliographystyle{bib/leo}
\bibliography{bib/refs}
}

\end{document}

config: arxiv