Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James
WorrellIoannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide
Sangiorgi 4 43rd International Colloquium on Automata, Languages, and
Programming (ICALP 2016) ICALP 2016 ICALP 2016 July 11–15, 2016 Rome, Italy 55
XXX

# Proving the Herman-Protocol Conjecture

Maria Bruna  Mathematical Institute, University of Oxford  Radu Grigore
School of Computing, University of Kent  Stefan Kiefer  Department of Computer
Science, University of Oxford  Joël Ouaknine  Department of Computer Science,
University of Oxford  James Worrell  Department of Computer Science,
University of Oxford

###### Abstract.

Herman’s self-stabilization algorithm, introduced 25 years ago, is a well-
studied synchronous randomized protocol for enabling a ring of $N$ processes
collectively holding any odd number of tokens to reach a stable state in which
a single token remains. Determining the worst-case expected time to
stabilization is the central outstanding open problem about this protocol. It
is known that there is a constant $h$ such that any initial configuration has
expected stabilization time at most $hN^{2}$. Ten years ago, McIver and Morgan
established a lower bound of $4/27\approx 0.148$ for $h$, achieved with three
equally-spaced tokens, and conjectured this to be the optimal value of $h$. A
series of papers over the last decade gradually reduced the upper bound on
$h$, with the present record (achieved in 2014) standing at approximately
$0.156$. In this paper, we prove McIver and Morgan’s conjecture and establish
that $h=4/27$ is indeed optimal.

###### Key words and phrases:

randomized protocols, self-stabilization, Lyapunov function, expected time

###### 1991 Mathematics Subject Classification:

F.1.2 Modes of Computation

##  1\. Introduction

The notion of _self-stabilization_ was introduced in a seminal paper of
Dijkstra [10], and rose to prominence a decade later, following (among others)
an invited talk of Lamport during which he pointed out that “self-
stabilization [is] a very important concept in fault tolerance” [21]. Both
self-stabilization and fault tolerance have since become central themes in
distributed computing (see, e.g., [11]), as recently witnessed by the award of
the 2015 Edsger W. Dijkstra Prize in Distributed Computing to Michael Ben-Or
and Michael Rabin for “starting the field of fault-tolerant randomized
distributed algorithms” in the early 1980s.

In this paper, we examine an early self-stabilization algorithm known as
Herman’s Protocol [18], whose exact mathematical analysis has proven
remarkably challenging over the two-and-a-half decades since its inception.
This algorithm considers a ring of $N$ processes (or nodes), where each
process either holds or doesn’t hold a token. Starting from any initial
configuration of $K$ tokens, where $K$ is required to be odd, Herman’s
algorithm proceeds as follows: at each time step, every process that holds a
token either keeps it or passes it to its clockwise neighbor with probability
$1/2$. All updates happen synchronously, and if a process finds itself with
two tokens (having simultaneously kept one and received one from its
counterclockwise neighbor) then both tokens are annihilated. It is
straightforward to see that, starting from an odd number of tokens and
following this procedure, almost surely only one token eventually remains, at
which point the ring is said to have _stabilized_.

Herman’s original paper [18] presents the algorithm in a form amenable to
implementation. Each process possesses a bit, which the process can read and
write. Each process can also read the bit of its counterclockwise neighbor. In
this representation, having the same bit as one’s counterclockwise neighbor is
interpreted as having a token. At each time step, each process compares its
bit with the bit of its counterclockwise neighbor; if the bits differ, the
process keeps its bit, whereas if the bits are the same, the process flips its
bit with probability $1/2$ and keeps it with probability $1/2$. It is
straightforward to verify that the bit-flipping version is an implementation
of the token-passing version: in particular, a process flipping its bit
corresponds to passing its token to its clockwise neighbor. If the number of
processes is odd, by construction this bit representation forces the number of
tokens to be odd as well, which justifies the assumption that $K$, the number
of tokens, is always odd. In this paper we make no assumption about the parity
of the number of _processes_ , as we abstract from the bit implementation, and
simply assume that the number of tokens is odd throughout.

Herman’s original paper [18] showed that the expected time (number of
synchronous steps) to stabilization is $O(N^{2}\log N)$. The same paper also
mentions an improved upper bound of $O(N^{2})$ due to Dolev, Israeli, and
Moran, without giving a proof or a further reference. In 2004, Fribourg et al.
[15] established an upper bound of $2N^{2}$, and the following year Nakata
[23] gave a tighter upper bound of $0.936N^{2}$ and exhibited an initial
configuration with expected stablization time $\Omega(N^{2})$. At the same
time and independently, McIver and Morgan showed in [22] that the initial
configuration consisting of three equally-spaced tokens has an expected
stabilization time of exactly $\frac{4}{27}N^{2}$, and conjectured that this
value is an upper bound on the expected time to stabilization starting from
_any_ initial configuration with _any_ (odd) number of tokens. The conjecture
is intriguing since increasing the initial number of tokens might be thought
to lengthen the expected time to stabilization, due to the larger number of
collisions required to achieve stabilization.

Nevertheless, McIver and Morgan’s Herman-Protocol Conjecture is supported by
considerable amount of experimental evidence [4], and in the intervening years
a series of papers have gradually reduced the upper bound on the constant $h$
such that stabilization from any initial configuration takes expected time at
most $hN^{2}$: upper bounds of approximately $0.64$, $0.521$, $0.167$, and
$0.156$ are given respectively in [20, 12, 13, 17], the last one provided last
year by Haslegrave, and coming relatively close to McIver and Morgan’s lower
bound of $4/27\approx 0.148$.

In this paper, we prove McIver and Morgan’s conjecture and establish that
$h=4/27$ is indeed optimal. Writing $T_{z}$ for the stabilization time
starting from an initial configuration $z$, we seek to prove that
$\mathbb{E}T_{z}\leq\frac{4}{27}N^{2}$. To this end, one of the key ideas is
to work with a Lyapunov function $V(z)$ in lieu of the (more complicated)
function $\mathbb{E}T_{z}$. The domain of the function $V$ is _continuous_ : a
domain element describes a configuration in terms of the distances between
adjacent tokens. Combinatorial arguments exploiting the highly symmetrical
structure of $V(z)$ enable us to establish that, for an arbitrary
configuration $z$, we have $\mathbb{E}T_{z}\leq V(z)$, with equality holding
for all three-token configurations. Finally, in what constitutes the most
technically challenging part of this paper, we combine induction on the number
of tokens with analytical techniques to show that $V$ is bounded by
$\frac{4}{27}N^{2}$. Taken together, we obtain
$\mathbb{E}T_{z}\leq\frac{4}{27}N^{2}$, entailing the Herman-Protocol
Conjecture.

The case of there being an _even_ number $K$ of tokens is equally natural from
a mathematical point of view, although it does not correspond to a concrete
bit-flipping protocol. It was established in [13] that the worst-case
configuration in this variant is the equidistant _two_ -token configuration,
with an expected stabilization time of $\frac{1}{2}N^{2}$; the analysis
underlying that result is considerably simpler than what is required in case
the number of tokens is odd, as in the present paper.

Herman’s protocol is also related to the notion of _coalescing random walks_
[2, 7, 1]. There, one considers multiple independent random walks on
$\mathbb{Z}^{d}$ (or on the vertices of a connected graph). When two walks
meet, they coalesce into a new random walk. A protocol for self-stabilizing
mutual exclusion based on such random walks was proposed in [19]. The expected
coalescence time was studied in [6, 24, 5].

It is interesting to note that Herman’s ring is closely related to widely-
studied models of random walks and Brownian motion in statistical physics.
Observe that by a simple modification of the formalism, one may equivalently
view Herman’s model as a ring in which tokens randomly move in discrete step
in _any_ direction, with pairwise collisions leading to annihilation; this
precisely corresponds to Fisher’s _vicious drunks_ model [14] (with periodic
boundary conditions). Similar models have been studied in chemical physics [9,
3, 27] and statistical mechanics [16, 25, 26], among others.

The rest of the paper is organized as follows. In Section 2 we review previous
results in the literature that are relevant to our proof. In Section 3 we
outline the structure of our proof, identifying two key lemmas, Lemma 3.5 and
Lemma 3.7. Those are proved in Appendix A and Section 4, respectively.

Another solution of the conjecture, using different techniques, is
independently shown in [8].

##  2\. Relevant Previous Results

For the rest of the paper we fix the number $N$ of processes. We assume that
the number $K$ of tokens is odd, and both $N$ and $K$ are at least $3$.

Processes are numbered from $1$ to $N$, clockwise, according to their position
in the ring. A configuration with $K$ tokens is formalized as a function
$z:\\{1,\ldots,K\\}\to\\{1,\ldots,N\\}$ with $z(1)<\cdots<z(K)$, where the
$i$th token ($i\in\\{1,\ldots,K\\}$) is held by the processor with the number
$z(i)$. We write $Z_{K}$ for the set of configurations with $K$ tokens, and
$Z$ for the set of all possible configurations, that is, $Z=Z_{1}\cup
Z_{3}\cup Z_{5}\cup\ldots$

For a fixed initial configuration $z=z_{0}$ we write $(z_{t})_{t\geq 0}$ for
the stochastic process of configurations emanating from $z$. The
_stabilization time_ $T_{z}$ is the smallest $t\geq 0$ such that $z_{t}\in
Z_{1}$, i.e., the time until only one token is left. In this paper we focus on
the expectation $\mathbb{E}T_{z}$. It is shown in [22] that if $N$ is odd and
a multiple of $3$, then there is a configuration $z\in Z_{3}$ (with the 3
tokens maximally separated in an equilateral triangle) such that
$\mathbb{E}T_{z}=\frac{4}{27}N^{2}$.

In this paper we show:

######  Theorem 2.1.

We have $\mathbb{E}T_{z}\leq\frac{4}{27}N^{2}$ for all $z\in Z$.

Equivalently, the Herman conjecture states that for all odd $K\geq 3$ and all
$z\in Z_{K}$ we have $\mathbb{E}T_{z}\leq\frac{4}{27}N^{2}$. Only the case
$K=3$ was previously known [22].

The following proposition has been used in a similar form in various papers on
Herman’s protocol, for instance in [22, Lemma 5]. It bounds the stabilization
time by a Lyapunov function $V$.

######  Proposition 2.2 (Bound by a Lyapunov function).

Given $z\in Z$, denote by $z^{\prime}\in Z$ the random successor configuration
of $z$. Let $V:Z\to\mathbb{R}$ be a function with

$\displaystyle\mathbb{E}(V(z^{\prime})\mid z)\;$ $\displaystyle\leq\;V(z)-1$
for all $z\in Z\setminus Z_{1}$, and (1) $\displaystyle 0\;$
$\displaystyle\leq\;V(z)$ for all $z\in Z_{1}$. (2)

Then $\mathbb{E}T_{z}\leq V(z)$ for all $z\in Z$. In particular, $V(z)\geq 0$
for all $z\in Z$.

Although this result is not new, we give a short proof based on a martingale
argument. The proof is inspired by [17], and may provide some intuition.

######  Proof 2.3.

Let $z\in Z$. Consider the stochastic process $(z_{t})_{t\geq 0}$ of
configurations emanating from $z=z_{0}$. Define $W_{t}:=V(z_{t})+t$. By (1)
the process $(W_{t})_{t\geq 0}$ is a supermartingale. The stabilization time
$T_{z}=T_{z_{0}}$ is a stopping time with finite expectation, and the
differences $|W_{t+1}-W_{t}|$ are bounded as the Markov chain reachable from
$z$ has finitely many states. Hence, the optional stopping theorem applies,
yielding $\mathbb{E}W_{T_{z}}\leq\mathbb{E}W_{0}=V(z)$. By definition of
$W_{t}$ we have $\mathbb{E}W_{T_{z}}=\mathbb{E}V(z_{T_{z}})+\mathbb{E}T_{z}$.
Since $z_{T_{z}}\in Z_{1}$, we have $\mathbb{E}T_{z}\leq\mathbb{E}W_{T_{z}}$
by (2). By combining the previous two inequalities, we obtain
$\mathbb{E}T_{z}\leq V(z)$.

Following [13, 17] we associate with a configuration $z\in Z_{K}$ the _gap
vector_ ${\bf g}(z)=(g_{0},\ldots,g_{K-1})\in\mathbb{N}^{K}$ by setting
$g_{0}:=N+z(1)-z(K)$, and $g_{i}:=z(i+1)-z(i)$ for $i\in\\{1,\ldots,K-1\\}$.
Then ${\bf g}(z)/N$ lives in the so-called standard $(K-1)$-simplex $D^{(K)}$,
defined by

$D^{(K)}:=\left\\{{\bf x}=(x_{0},\ldots,x_{K-1})\in[0,1]^{K}\ \mid\
x_{0}+\cdots+x_{K-1}=1\right\\}.$

Towards a suitable Lyapunov function $V$ we define the cubic polynomial
$f_{3}^{(K)}:D^{(K)}\to[0,\infty)$ by

$f_{3}^{(K)}({\bf x}):=\hskip-20.00003pt\sum_{\begin{subarray}{c}0\leq
i_{0}<i_{1}<i_{2}<K\\\ \text{$i_{2}-i_{1}$, $i_{1}-i_{0}$
odd}\end{subarray}}\hskip-20.00003ptx_{i_{0}}x_{i_{1}}x_{i_{2}}.$

For instance, we have $f_{3}^{(5)}({\bf
x})=x_{0}x_{1}x_{2}+x_{0}x_{1}x_{4}+x_{0}x_{3}x_{4}+x_{1}x_{2}x_{3}+x_{2}x_{3}x_{4}$.

The following lemma was implicitly proved in previous works:

######  Lemma 2.4 (Lyapunov function $V_{3}$ [13, Page 240, Proof of Theorem
1] and [17, Theorem 4]).

Let $V_{3}:Z\to[0,\infty)$ be defined by $V_{3}(z):=4N^{2}f_{3}^{(K)}({\bf
g}(z)/N)$ for $z\in Z_{K}$. Denote by $z^{\prime}\in Z_{1}\cup
Z_{3}\cup\ldots\cup Z_{K}$ the random successor configuration of $z\in Z_{K}$.
Then $\mathbb{E}(V_{3}(z^{\prime})\mid z)=V_{3}(z)-\frac{K-1}{2}$ for all
$z\in Z_{K}$. Hence, by Proposition 2.2, $\mathbb{E}T_{z}\leq
4N^{2}f_{3}^{(K)}({\bf g}(z)/N)$.

For $K=3$ Lemma 2.4 gives $\mathbb{E}T_{z}\leq 4N^{2}f_{3}^{(K)}({\bf
g}(z)/N)=\frac{4}{N}g_{0}g_{1}g_{2}$. In fact, for $K=3$ it was shown before
in [22] that $\mathbb{E}T_{z}$ is identically equal to
$\frac{4}{N}g_{0}g_{1}g_{2}$, providing an exact formula for the expected
stabilization time of configurations with three tokens. Lemma 2.4 suggests
analyzing $f_{3}$:

######  Lemma 2.5 (Maximum of $f_{3}$ [13, Proof of Theorem 2], [17, Theorem
3]).

For all $K\geq 3$ odd we have

$\max_{{\bf x}\in D}f_{3}^{(K)}({\bf x})\ =\
f_{3}^{(K)}\left(\frac{1}{K},\ldots,\frac{1}{K}\right)\ =\
\frac{1}{24}\left(1-\frac{1}{K^{2}}\right)\,.$

By combining Lemmas 2.4 and 2.5 one obtains
$\mathbb{E}T_{z}\leq\frac{N^{2}}{6}(1-\frac{1}{K^{2}})$, which is the bound
obtained in [13]. A slightly better bound is given in [17].

##  3\. Proof of the Herman Conjecture

The function $V_{3}$ from Lemma 2.4 leaves room for improvement since
$\mathbb{E}(V_{3}(z^{\prime})\mid z)=V_{3}(z)-\frac{K-1}{2}$, which is
strictly less than $V_{3}(z)-1$ for $K>3$. The idea for obtaining an optimal
bound is to decrease the gap between $\frac{K-1}{2}$ and $1$, by decreasing
the Lyapunov function $V$. One could think that the scaled function
$\frac{2}{K-1}V_{3}$ is also a Lyapunov function satisfying (1), but this is
not true; in particular, note that the number of tokens $K$ might be different
for a configuration $z$ and its successor $z^{\prime}$. Since scaling does not
work, we decrease the Lyapunov function by subtracting a quintic polynomial,
as follows. Define a quintic polynomial $f_{5}^{(K)}:D^{(K)}\to[0,\infty)$,
similar to $f_{3}^{(K)}$:

$\displaystyle f_{5}^{(K)}({\bf
x})=\hskip-20.00003pt\sum_{\begin{subarray}{c}0\leq
i_{0}<i_{1}<\cdots<i_{4}<K\\\ \text{$i_{4}-i_{3},\ldots,i_{1}-i_{0}$
odd}\end{subarray}}\hskip-20.00003ptx_{i_{0}}x_{i_{1}}x_{i_{2}}x_{i_{3}}x_{i_{4}}$

For instance, $f_{5}^{(3)}({\bf x})=0$, $f_{5}^{(5)}({\bf
x})=x_{0}x_{1}x_{2}x_{3}x_{4}$, and $f_{5}^{(7)}({\bf
x})=x_{0}x_{1}x_{2}x_{3}x_{4}+x_{0}x_{1}x_{2}x_{3}x_{6}+x_{0}x_{1}x_{2}x_{5}x_{6}+x_{0}x_{1}x_{4}x_{5}x_{6}+x_{0}x_{3}x_{4}x_{5}x_{6}+x_{1}x_{2}x_{3}x_{4}x_{5}+x_{2}x_{3}x_{4}x_{5}x_{6}$.
We also define a polynomial $f^{(K)}:D^{(K)}\to[0,\infty)$:

$f^{(K)}({\bf x}):=f_{3}^{(K)}({\bf x})-\alpha f_{5}^{(K)}({\bf
x})\qquad\text{with }\alpha:=24$ (3)

For example, $f^{(5)}({\bf
x})=x_{0}x_{1}x_{2}+x_{0}x_{1}x_{4}+x_{0}x_{3}x_{4}+x_{1}x_{2}x_{3}+x_{2}x_{3}x_{4}-\alpha
x_{0}x_{1}x_{2}x_{3}x_{4}$. Throughout the paper we use $\alpha$ in the
expression of $f^{(K)}$ for notational convenience. From now onwards we may
drop the superscript $K$ from the domain $D^{(K)}$ of the functions
$f_{3}^{(K)}$, $f_{5}^{(K)}$ and $f^{(K)}$ to avoid notational clutter when
$K$ is understood.

The following properties of $f$ are fundamental:

######  Lemma 3.1 (Symmetry and continuity properties).

The function $f$ has the following properties.

  * (a)

It is symmetric with respect to rotation:

$f(x_{0},\ldots,x_{K-1})=f(x_{1},\ldots,x_{K-1},x_{0})$

  * (b)

It is continuous: For $K\geq 5$ we have

$f^{(K)}(x_{0},0,x_{2},x_{3},\ldots,x_{K-1})=f^{(K-2)}(x_{0}+x_{2},x_{3},\ldots,x_{K-1}).$

Analogous properties were shown for $f_{3}$ in [13]. Their proof carries over
to $f_{5}$ and hence to $f$. The following lemma uses $f$ to define a tighter
Lyapunov function.

######  Lemma 3.2 (Lyapunov function $V$).

Define $V:Z\to[0,\infty)$ by $V(z):=4N^{2}f({\bf g}(z)/N)$. Let $z\in Z$ and
denote by $z^{\prime}$ the random successor configuration of $z$. Then
$\mathbb{E}(V(z^{\prime})\mid z)\leq V(z)-1$. Hence, by Proposition 2.2,
$\mathbb{E}T_{z}\leq 4N^{2}f({\bf g}(z)/N)$.

We remark that a similar Lyapunov function has been investigated in [13,
Equation (15)], but did not lead to a proof of the Herman conjecture. It seems
that $V(z)$ needs to be chosen with great care, since even slight variations
do not work.

Lemma 3.2 suggests analyzing $f$:

######  Lemma 3.3 (Maximum of $f$).

For all $K\geq 3$ odd we have

$\max_{{\bf x}\in D}f^{(K)}({\bf x})=\frac{1}{27}.$

With this in hand our main result follows:

######  Proof 3.4 (Proof of Theorem 2.1).

Immediate by combining Lemmas 3.2 and 3.3.

It remains to prove Lemmas 3.2 and 3.3.

###  3.1. Proof of Lemma 3.2

Towards Lemma 3.2 we show:

######  Lemma 3.5 (Lyapunov function $V_{5}$).

Define $V_{5}:Z\to[0,\infty)$ by $V_{5}(z):=4N^{2}f_{5}({\bf g}(z)/N)$. Let
$K\geq 5$ and $z\in Z$ and denote by $z^{\prime}$ the random successor
configuration of $z$. Then

$\mathbb{E}(V_{5}(z^{\prime})\mid
z)=V_{5}(z)+\frac{1}{32}\frac{(K-1)(K-3)}{N^{2}}-\frac{1}{2}(K-3)f_{3}\left(\frac{{\bf
g}(z)}{N}\right)\,.$

The proof in Appendix A requires an analysis of correlations among the changes
in gaps between tokens in each step of the protocol. Using Lemma 3.5 one can
readily prove Lemma 3.2:

######  Proof 3.6 (Proof of Lemma 3.2).

For $K=3$ the statement follows from Lemma 2.4. For $K\geq 5$ we have:

$\displaystyle\mathbb{E}(V(z^{\prime})\mid z)$
$\displaystyle=\mathbb{E}((V_{3}(z^{\prime})-24V_{5}(z^{\prime}))\mid z)$ by
the definitions $\displaystyle=\mathbb{E}(V_{3}(z^{\prime})\mid
z)-24\mathbb{E}(V_{5}(z^{\prime})\mid z)$ linearity of expectation
$\displaystyle=V_{3}(z)-\frac{K-1}{2}-24V_{5}(z)-\frac{3}{4}\frac{(K-1)(K-3)}{N^{2}}$
$\displaystyle\ \qquad+12(K-3)f_{3}\left(\frac{{\bf g}(z)}{N}\right)$ Lemmas
2.4 and 3.5 $\displaystyle\leq V(z)-\frac{K-1}{2}+12(K-3)f_{3}\left(\frac{{\bf
g}(z)}{N}\right)$ since $K\geq 3$ $\displaystyle\leq
V(z)-\frac{K-1}{2}+\frac{K-3}{2}$ Lemma 2.5 $\displaystyle=V(z)-1$

###  3.2. Proof of Lemma 3.3

Towards Lemma 3.3 we show:

######  Lemma 3.7 (Local maxima of $f$).

Let $K\geq 5$ and odd. There is no ${\bf v}\in D^{(K)}$ in the interior of
$D^{(K)}$ such that ${\bf v}$ is a local maximum and $f^{(K)}({\bf
v})>\frac{1}{27}$.

The proof in Section 4 involves a combinatorial analysis of inequalities
arising from conditions on the derivatives of $f^{(K)}$. Using Lemma 3.7 one
can readily prove Lemma 3.3:

######  Proof 3.8 (Proof of Lemma 3.3).

We proceed by induction on $K$. For the induction base we have $K=3$. It is
straightforward to check that the maximum of $f^{(3)}({\bf
x})=f_{3}^{(3)}({\bf x})=x_{0}x_{1}x_{2}$ is
$f^{(3)}(\frac{1}{3},\frac{1}{3},\frac{1}{3})=\frac{1}{27}$.

For the induction step we have $K\geq 5$. Let ${\bf v}\in D^{(K)}$ with
$f^{(K)}({\bf v})=\max_{{\bf x}\in D^{(K)}}f^{(K)}({\bf x})$. If ${\bf v}$ is
in the interior of $D^{(K)}$, then by Lemma 3.7 we have $f^{(K)}({\bf
v})\leq\frac{1}{27}$. If ${\bf v}$ is at the boundary of $D^{(K)}$, then
$v_{i}=0$ for some $i$. By Lemma 3.1(a) we can assume that $v_{1}=0$. Using
Lemma 3.1(b) the statement follows from the induction hypothesis.

##  4\. Proof of Lemma 3.7

In this section we prove Lemma 3.7. In Section 4.1 we state several properties
that an interior local maximum of $f^{(K)}$ would have to satisfy. In Section
4.2 we prove Lemma 3.7 for $K=5$ for a first taste of the general argument. In
Section 4.3 we prove Lemma 3.7 for $K=7$ to illustrate some fine points that
occur only for larger values of $K$. In Section 4.4 we state some
combinatorial facts needed for the general case. Finally, in Section 4.5 we
prove Lemma 3.7.

###  4.1. Properties of an Interior Local Maximum

The following lemma is obtained by considering first and second derivatives of
$f$ evaluated at an interior local maximum.

######  Lemma 4.1.

Let ${\bf v}$ be a local maximum of $f^{(K)}$ in the interior of $D^{(K)}$ and
define $c\in\mathbb{R}$ by

$\displaystyle c\ \ =\sum_{\begin{subarray}{c}1<i_{2}<K\\\ \text{$i_{2}$
even}\end{subarray}}v_{i_{2}}\
-\quad\alpha\hskip-15.00002pt\sum_{\begin{subarray}{c}1<i_{2}<i_{3}<i_{4}<K\\\
\text{$i_{2}$, $i_{4}$ even}\\\ \text{$i_{3}$
odd}\end{subarray}}\hskip-15.00002ptv_{i_{2}}v_{i_{3}}v_{i_{4}}\,.$ (4)

This expression holds for the same value of $c$ if the indices are rotated by
an arbitrary $k$: for all $j$ the index $i_{j}$ becomes $(i_{j}+k)\bmod K$.
Further, we have

$\displaystyle\sum_{\begin{subarray}{c}3\leq i_{3}<i_{4}<K\\\ \text{$i_{3}$
odd}\\\ \text{$i_{4}$
even}\end{subarray}}\\!\\!\\!\\!v_{i_{3}}v_{i_{4}}\leq\frac{1}{\alpha}\,.$ (5)

Again, this inequality also holds when indices are rotated.

For example, for $K=7$ we have
$c=v_{2}+v_{4}+v_{6}-\alpha(v_{2}v_{3}v_{4}+v_{2}v_{3}v_{6}+v_{2}v_{5}v_{6}+v_{4}v_{5}v_{6})=v_{1}+v_{3}+v_{5}-\alpha(v_{1}v_{2}v_{3}+v_{1}v_{2}v_{5}+v_{1}v_{4}v_{5}+v_{3}v_{4}v_{5})$.

######  Proof 4.2 (Proof of Lemma 4.1).

The idea of the proof is as follows. We pick a particular direction in
$D^{(K)}$, namely ${\bf d}=(-1,0,1,0,0,\ldots,0)$, and consider the function
$f({\bf v}+\epsilon{\bf d})$ as a univariate function of $\epsilon$. Since
${\bf v}$ is a local maximum, the first derivative must be zero and the second
derivative must be nonpositive. Exploiting the fact that $v_{i}>0$ for all $i$
holds in the interior, we obtain (4) and (5), respectively. See Appendix B for
the detailed proof.

Let $S_{j}^{(K)}({\bf x})$ denote the scalar product of ${\bf x}$ with a copy
of itself rotated $j$ times:

$S_{j}^{(K)}({\bf x}):=\sum_{i=0}^{K-1}x_{i}x_{i+j}$

In all formulas it will be the case that the subscript of $S$ is odd. Also,
the superscript will be omitted when unimportant or understood from context.

######  Corollary 4.3.

Let ${\bf v}$ be a local maximum of $f^{(K)}$ in the interior of $D^{(K)}$.
Then the following inequality holds:

$\sum_{\begin{subarray}{c}1\leq i<K-2\\\ \text{$i$
odd}\end{subarray}}\frac{K-i-2}{2}S_{i}({\bf
v})\quad\leq\quad\frac{K}{\alpha}$

For example, for $K=11$ we have $4S_{1}({\bf v})+3S_{3}({\bf v})+2S_{5}({\bf
v})+S_{7}({\bf v})\leq 11/\alpha$.

######  Lemma 4.4 (Bound for $f_{5}$).

Suppose that ${\bf v}\in D^{(K)}$ satisfies $f^{(K)}({\bf v})>\frac{1}{27}$.
Then $\alpha f_{5}({\bf v})<\frac{1}{216}$.

######  Proof 4.5.

By Lemma 2.5 we have $f_{3}({\bf v})\leq\frac{1}{24}$ and hence $\alpha
f_{5}({\bf v})=f_{3}({\bf v})-f({\bf
v})<\frac{1}{24}-\frac{1}{27}=\frac{1}{216}$.

###  4.2. Proof of Lemma 3.7 for $K=5$

Let $K=5$. Then

$\displaystyle f({\bf x})\ $ $\displaystyle=\ f_{3}({\bf x})-\alpha f_{5}({\bf
x})\ =\
x_{0}x_{1}x_{2}+x_{0}x_{1}x_{4}+x_{0}x_{3}x_{4}+x_{1}x_{2}x_{3}+x_{2}x_{3}x_{4}-\alpha
x_{0}x_{1}x_{2}x_{3}x_{4}$

Towards a contradiction, suppose that there is a local maximum ${\bf v}$ with
$f({\bf v})>\frac{1}{27}$ in the interior of $D$. By (4), the value

$c\ =\ v_{2}+v_{4}-\alpha v_{2}v_{3}v_{4}$ (6)

is invariant under rotations. Indeed, $v_{2+k}+v_{4+k}-\alpha
v_{2+k}v_{3+k}v_{4+k}\equiv c$ for all $k$, but we shall avoid explicitly
mentioning rotations, for notational simplicity. Summing (6) over all $K$
rotations we obtain:

$5c\ =\ 2-\alpha f_{3}({\bf v})$ (7)

By (6) we have $v_{0}v_{1}c=v_{0}v_{1}v_{2}+v_{0}v_{1}v_{4}-\alpha f_{5}({\bf
v})$ and, summing over all $K$ rotations,

$cS_{1}({\bf v})\ =\ 2f({\bf v})-3\alpha f_{5}({\bf v})$ (8)

Moreover,

$cS_{1}({\bf v})\ \mathop{\leq}^{\text{Cor.\leavevmode\nobreak\
\ref{cor-d2-nonpos-summed}}}\ \frac{5c}{\alpha}\ \mathop{=}^{\text{\eqref{eq-
proof5-five-c}}}\ \frac{2}{\alpha}-f_{3}({\bf v})\ =\ \frac{2}{\alpha}-f({\bf
v})-\alpha f_{5}({\bf v}).$

Combining this with (8) gives:

$\frac{2}{\alpha}\quad\geq\quad 3f({\bf v})-2\alpha f_{5}({\bf
v})\quad\mathop{\geq}^{\text{Lemma\leavevmode\nobreak\ \ref{lem-bound-
on-f5}}}\quad\frac{3}{27}-2\cdot\frac{1}{216}$

This implies $\alpha\leq 216/11\approx 19.6$, which is a contradiction as
required (since $\alpha=24$). ∎

###  4.3. Proof of Lemma 3.7 for $K=7$

Let $K=7$. Towards a contradiction, we suppose again that there is a local
maximum ${\bf v}$ with $f({\bf v})>\frac{1}{27}$ in the interior of $D$. By
(4), all $K$ rotations of the following hold with the same $c\in\mathbb{R}$:

$c\ =\
v_{2}+v_{4}+v_{6}-\alpha(v_{2}v_{3}v_{4}+v_{2}v_{3}v_{6}+v_{2}v_{5}v_{6}+v_{4}v_{5}v_{6})$
(9)

Summing (9) over $K$ rotations we obtain:

$7c\ =\ 3-2\alpha f_{3}({\bf v})$ (10)

By (9) we have

$v_{0}v_{1}c\;=\;v_{0}v_{1}v_{2}+v_{0}v_{1}v_{4}+v_{0}v_{1}v_{6}-\alpha(v_{0}v_{1}v_{2}v_{3}v_{4}+v_{0}v_{1}v_{2}v_{3}v_{6}+v_{0}v_{1}v_{2}v_{5}v_{6}+v_{0}v_{1}v_{4}v_{5}v_{6})$
(11)

and

$\displaystyle v_{0}v_{3}c$
$\displaystyle=\;v_{0}v_{3}v_{4}+v_{0}v_{3}v_{6}-\alpha
v_{0}v_{3}v_{4}v_{5}v_{6}+v_{0}v_{2}v_{3}(1-\alpha(v_{3}v_{4}+v_{3}v_{6}+v_{5}v_{6}))$
(12) $\displaystyle\geq\;v_{0}v_{3}v_{4}+v_{0}v_{3}v_{6}-\alpha
v_{0}v_{3}v_{4}v_{5}v_{6}$

where the last inequality is by (5). Summing (11) and (12) over $K$ rotations
we obtain:

$c\bigl{(}2S_{1}({\bf v})+S_{3}({\bf v})\bigr{)}\ \geq\ 4f_{3}({\bf
v})-9\alpha f_{5}({\bf v})=4f({\bf v})-5\alpha f_{5}({\bf v})$ (13)

Further we have:

$c\bigl{(}2S_{1}({\bf v})+S_{3}({\bf v})\bigr{)}\
\mathop{\leq}^{\text{Cor.\leavevmode\nobreak\ \ref{cor-d2-nonpos-summed}}}\
\frac{7c}{\alpha}\ \mathop{=}^{\text{\eqref{eq-proof7-five-c}}}\
\frac{3}{\alpha}-2f_{3}({\bf v})\ =\ \frac{3}{\alpha}-2f({\bf v})-2\alpha
f_{5}({\bf v})$

Combining this with (13) gives:

$\frac{3}{\alpha}\quad\geq\quad 6f({\bf v})-3\alpha f_{5}({\bf
v})\quad\mathop{\geq}^{\text{Lemma\leavevmode\nobreak\ \ref{lem-bound-
on-f5}}}\quad\frac{6}{27}-3\cdot\frac{1}{216}$

This leads to $\alpha\leq 14.4$, which is a contradiction as desired. ∎

###  4.4. Combinatorial Lemmas

In order to generalize the proofs from Sections 4.2 and 4.3 to any odd $K$, we
state some combinatorial lemmas in this subsection. They are proved in
Appendix C.

In order to generalize (7) and (10) we show the following lemma:

######  Lemma 4.6.

We have:

$\sum_{k=0}^{K-1}\sum_{\begin{subarray}{c}1<i^{\prime}_{0}<i^{\prime}_{1}<i^{\prime}_{2}<K\\\
\text{$i^{\prime}_{0}$, $i^{\prime}_{2}$ even}\\\ \text{$i^{\prime}_{1}$
odd}\end{subarray}}x_{i^{\prime}_{0}+k}x_{i^{\prime}_{1}+k}x_{i^{\prime}_{2}+k}=\frac{K-3}{2}\hskip-10.00002pt\sum_{\begin{subarray}{c}0\leq
i_{0}<i_{1}<i_{2}<K\\\ \text{$i_{2}-i_{1}$, $i_{1}-i_{0}$
odd}\end{subarray}}\hskip-20.00003ptx_{i_{0}}x_{i_{1}}x_{i_{2}}=\frac{K-3}{2}f_{3}^{(K)}({\bf
x})$

For example, if $K=5$, then we obtain that summing the $5$ rotations of
$x_{2}x_{3}x_{4}$ gives $f_{3}^{(5)}({\bf x})$. As another example, if $K=7$,
then we obtain that summing the $7$ rotations of
$x_{2}x_{3}x_{4}+x_{2}x_{3}x_{6}+x_{2}x_{5}x_{6}+x_{4}x_{5}x_{6}$ gives
$2f_{3}^{(7)}({\bf x})$. These two instances of Lemma 4.6 help establish (7)
and (10).

In order to generalize the inequality in (12) we need the following lemma:

######  Lemma 4.7.

Let ${\bf v}$ be a local maximum of $f^{(K)}$ in the interior of $D^{(K)}$. If
$i_{1}$ is odd and $0<i_{1}<K$, then the following inequality holds:

$v_{0}v_{i_{1}}\biggl{(}\sum_{\begin{subarray}{c}1<i_{2}<K\\\ \text{$i_{2}$
even}\end{subarray}}v_{i_{2}}-\hskip-10.00002pt\sum_{\begin{subarray}{c}1<i_{2}<i_{3}<i_{4}<K\\\
\text{$i_{2},i_{4}$ even}\\\ \text{$i_{3}$
odd}\end{subarray}}\hskip-20.00003pt\alpha
v_{i_{2}}v_{i_{3}}v_{i_{4}}\biggr{)}\geq
v_{0}v_{i_{1}}\biggl{(}\sum_{\begin{subarray}{c}i_{1}<i_{2}<K\\\ \text{$i_{2}$
even}\end{subarray}}v_{i_{2}}-\hskip-10.00002pt\sum_{\begin{subarray}{c}i_{1}<i_{2}<i_{3}<i_{4}<K\\\
\text{$i_{2},i_{4}$ even}\\\ \text{$i_{3}$
odd}\end{subarray}}\hskip-20.00003pt\alpha
v_{i_{2}}v_{i_{3}}v_{i_{4}}\biggr{)}$

The inequality says that if we drop those terms that do not occur in
$f_{3}^{(K)}$ or $f_{5}^{(K)}$, then we obtain a lower bound. The proof groups
those terms that are not in either of $f_{3}^{(K)}$ or $f_{5}^{(K)}$, and then
invokes (5) to show that their sum is nonnegative.

In order to generalize (8) and (13) we need Corollary 4.9 below, which is a
consequence of the following lemma:

######  Lemma 4.8.

Let $l$ be an odd, positive integer. Then:

$\sum_{k=0}^{K-1}\sum_{\begin{subarray}{c}1\leq i^{\prime}_{1}<K-2\\\
\text{$i^{\prime}_{1}$
odd}\end{subarray}}\frac{K-i^{\prime}_{1}-2}{2}\hskip-10.00002pt\sum_{\begin{subarray}{c}i^{\prime}_{1}<i^{\prime}_{2}<\cdots<i^{\prime}_{l-1}<K\\\
\forall j,\;i^{\prime}_{j}\equiv
j\pmod{2}\end{subarray}}x_{k}x_{i^{\prime}_{1}+k}\prod_{\begin{subarray}{c}1<j<l\end{subarray}}x_{i^{\prime}_{j}+k}=\\\
=\Bigl{(}\frac{l-1}{2}K-l\Bigr{)}\hskip-10.00002pt\sum_{\begin{subarray}{c}0\leq
i_{0}<\cdots<i_{l-1}<K\\\ \text{$i_{j}-i_{j-1}$ odd for
$0<j<l$}\end{subarray}}\prod_{j=0}^{l-1}x_{i_{j}}$

For example, if $K=5$ and $l=3$, then we have that summing $5$ rotations of
$x_{0}x_{1}x_{2}+x_{0}x_{1}x_{4}$ gives $2f_{3}^{(5)}({\bf x})$. As another
example, if $K=9$ and $l=3$, then summing $9$ rotations of
$3x_{0}x_{1}(x_{2}+x_{4}+x_{6}+x_{8})+2x_{0}x_{3}(x_{4}+x_{6}+x_{8})+x_{0}x_{5}(x_{6}+x_{8})$
gives $6f_{3}^{(9)}({\bf x})$.

######  Corollary 4.9.

We have:

$\sum_{k=0}^{K-1}\sum_{\begin{subarray}{c}1\leq i_{1}<K-2\\\ \text{$i_{1}$
odd}\end{subarray}}\frac{K-i_{1}-2}{2}\sum_{\begin{subarray}{c}i_{1}<i_{2}<K\\\
\text{$i_{2}$
even}\end{subarray}}x_{0+k}x_{i_{1}+k}x_{i_{2}+k}=(K-3)f_{3}^{(K)}({\bf x})$

and also

$\sum_{k=0}^{K-1}\sum_{\begin{subarray}{c}1\leq i_{1}<K-2\\\ \text{$i_{1}$
odd}\end{subarray}}\frac{K-i_{1}-2}{2}\sum_{\begin{subarray}{c}i_{1}<i_{2}<i_{3}<i_{4}<K\\\
\text{$i_{2},i_{4}$ even}\\\ \text{$i_{3}$
odd}\end{subarray}}x_{0+k}x_{i_{1}+k}x_{i_{2}+k}x_{i_{3}+k}x_{i_{4}+k}=(2K-5)f_{5}^{(K)}({\bf
x})$

######  Proof 4.10.

Instantiate Lemma 4.8 with $l=3$ and, respectively, $l=5$.

###  4.5. Proof of Lemma 3.7

Towards a contradiction, suppose that there is a local maximum ${\bf v}$ with
$f({\bf v})>\frac{1}{27}$ in the interior of $D$, i.e., $v_{i}>0$ for all
$i\in\\{0,\ldots,K-1\\}$. Summing up the $K$ rotations of (4) and using Lemma
4.6, we obtain:

$Kc\ =\ \frac{K-1}{2}-\frac{K-3}{2}\alpha f_{3}({\bf v})$ (14)

Multiplying (4) on both sides by $\sum_{\begin{subarray}{c}1\leq i_{1}<K-2\\\
\text{$i_{1}$ odd}\end{subarray}}\frac{K-i_{1}-2}{2}v_{0}v_{i_{1}}$ we obtain:

$\displaystyle c\sum_{\begin{subarray}{c}1\leq i_{1}<K-2\\\ \text{$i_{1}$
odd}\end{subarray}}\frac{K-i_{1}-2}{2}v_{0}v_{i_{1}}$
$\displaystyle=\sum_{\begin{subarray}{c}1\leq i_{1}<K-2\\\ \text{$i_{1}$
odd}\end{subarray}}\frac{K-i_{1}-2}{2}v_{0}v_{i_{1}}\Biggl{(}\sum_{\begin{subarray}{c}1<i_{2}<K\\\
\text{$i_{2}$
even}\end{subarray}}v_{i_{2}}-\hskip-10.00002pt\sum_{\begin{subarray}{c}1<i_{2}<i_{3}<i_{4}<K\\\
\text{$i_{2}$, $i_{4}$ even}\\\ \text{$i_{3}$
odd}\end{subarray}}\hskip-15.00002pt\alpha
v_{i_{2}}v_{i_{3}}v_{i_{4}}\Biggr{)}$
$\displaystyle\geq\sum_{\begin{subarray}{c}1\leq i_{1}<K-2\\\ \text{$i_{1}$
odd}\end{subarray}}\frac{K-i_{1}-2}{2}v_{0}v_{i_{1}}\Biggl{(}\sum_{\begin{subarray}{c}i_{1}<i_{2}<K\\\
\text{$i_{2}$
even}\end{subarray}}v_{i_{2}}-\hskip-10.00002pt\sum_{\begin{subarray}{c}i_{1}<i_{2}<i_{3}<i_{4}<K\\\
\text{$i_{2}$, $i_{4}$ even}\\\ \text{$i_{3}$
odd}\end{subarray}}\hskip-15.00002pt\alpha
v_{i_{2}}v_{i_{3}}v_{i_{4}}\Biggr{)}$

using Lemma 4.7. Summing $K$ rotations of this inequality yields:

$\displaystyle c\\!\\!\sum_{\begin{subarray}{c}1\leq i_{1}<K-2\\\
\text{$i_{1}$ odd}\end{subarray}}\frac{K-i_{1}-2}{2}S_{i_{1}}({\bf v})$
$\displaystyle\geq\ (K-3)f_{3}({\bf v})-(2K-5)\alpha f_{5}({\bf
v})=(K-3)f({\bf v})-(K-2)\alpha f_{5}({\bf v}).$ (15)

using Corollary 4.9. Further we have:

$c\sum_{\begin{subarray}{c}1\leq i_{1}<K-2\\\ \text{$i_{1}$
odd}\end{subarray}}\frac{K-i_{1}-2}{2}S_{i_{1}}({\bf v})\
\mathop{\leq}^{\text{Cor.\leavevmode\nobreak\ \ref{cor-d2-nonpos-summed}}}\
\frac{Kc}{\alpha}\ \mathop{=}^{\text{\eqref{eq-proof-Mc}}}\
\frac{K-1}{2\alpha}-\frac{K-3}{2}f_{3}({\bf v})$

Combining this with (15) gives:

$\frac{K-1}{2\alpha}\ \geq\ \frac{3K-9}{2}f({\bf v})-\frac{K-1}{2}\alpha
f_{5}({\bf v})\ \mathop{\geq}^{\text{Lemma\leavevmode\nobreak\ \ref{lem-bound-
on-f5}}}\ \frac{K-3}{2}\cdot\frac{1}{9}-\frac{K-1}{2}\cdot\frac{1}{216}$

This implies

$\alpha\leq\frac{216(K-1)}{23K-71}<19.7$

Since $\alpha=24$, this leads to a contradiction as desired. ∎

##  5\. Conclusions

In this paper we have proved the Herman-Protocol Conjecture formulated by
McIver and Morgan in [22] a decade ago, which says that the worst-case initial
configuration consists of three maximally-separated tokens, for $N$ multiple
of $3$. This follows from our result that the worst-case self-stabilization
time is at most $\frac{4}{27}N^{2}$, for any number of processes $N$ and any
odd number of tokens $K$.

The proof uses a Lyapunov function approach. To do so, we first find a
suitable Lyapunov function and then show that its maximum is
$\frac{4}{27}N^{2}$. Then we show that this function gives an upper bound for
the self-stabilization time for _each_ possible configuration in Herman’s
algorithm.

#### Acknowledgements

Stefan Kiefer is supported by a University Research Fellowship of the Royal
Society and by EPSRC grant EP/M003795/1. Joël Ouaknine is supported by ERC
grant AVS-ISS (648701).

## References

  * [1] D. Aldous and J. A. Fill.  Reversible Markov chains and random walks on graphs, 2002.  Unfinished monograph, recompiled 2014, available at http://www.stat.berkeley.edu/~aldous/RWG/book.html.
  * [2] R. Arratia.  Limiting point processes for rescalings of coalescing and annihilating random walks on ${Z}^{d}$.  The Annals of Probability, 9(6):909–936, 1981.
  * [3] D. Balding.  Diffusion-reaction in one dimension.  J. Appl. Prob., 25:733–743, 1988.
  * [4] PRISM case studies.  Randomised self-stabilising algorithms.
`http://www.prismmodelchecker.org/casestudies/self-stabilisation.php`.

  * [5] C. Cooper, R. Elsässer, H. Ono, and T. Radzik.  Coalescing random walks and voting on graphs.  In Proc. PODC, pages 47–56. ACM, 2012.
  * [6] D. Coppersmith, P. Tetali, and P. Winkler.  Collisions among random walks on a graph.  SIAM Journal on Discrete Mathematics, 6(3):363–374, 1993.
  * [7] J.T. Cox.  Coalescing random walks and voter model consensus times on the torus in ${Z}^{d}$.  The Annals of Probability, 17(4):1333–1366, 1989.
  * [8] E. Csóka and S. Mészáros.  Generalized solution for the Herman protocol conjecture.  Technical report, arxiv.org, 2015.  Available at `http://arxiv.org/abs/1504.06963`.
  * [9] P.-G. de Gennes.  Soluble model for fibrous structures with steric constraints.  J. Chem. Phys., 48(5):2257–2259, 1968.
  * [10] E. W. Dijkstra.  Self-stabilizing systems in spite of distributed control.  Comm. ACM, 17(11):643–644, 1974.
  * [11] S. Dolev.  Self-Stabilization.  MIT Press, 2000.
  * [12] Y. Feng and L. Zhang.  A Tighter Bound for the Self-Stabilization Time in Herman’s Algorithm.  Inf. Process. Lett., 113(13):486–488, 2013.
  * [13] Y. Feng and L. Zhang.  A nearly optimal upper bound for the self-stabilization time in Herman’s algorithm.  Dist. Comp., pages 1–12, 2015.
  * [14] M. E. Fisher.  Walks, walls, wetting, and melting.  J. Stat. Phys., 34(5-6):667–729, 1984.
  * [15] L. Fribourg, S. Messika, and C. Picaronny.  Coupling and self-stabilization.  Dist. Comp., 18:221–232, 2005.
  * [16] S. Y. Grigoriev and V. B. Priezzhev.  Random walk of annhilating particles on the ring.  Theor. Math. Phys., 146(3):411–420, 2006.
  * [17] J. Haslegrave.  Bounds on Herman’s algorithm.  Theoretical Computer Science, 550:100–06, 2014.
  * [18] T. Herman.  Probabilistic self-stabilization.  Inf. Process. Lett., 35(2):63–67, 1990.
  * [19] A. Israeli and M. Jalfon.  Token management schemes and random walks yield self-stabilizing mutual exclusion.  In Proc. PODC, pages 119–131. ACM, 1990.
  * [20] S. Kiefer, A. Murawski, J. Ouaknine, J. Worrell, and L. Zhang.  On stabilization in Herman’s algorithm.  In Proc. ICALP, volume 6756 of LNCS. Springer, 2011.
  * [21] L. Lamport.  Solved problems, unsolved problems and non-problems in concurrency.  In Proc. PODC, pages 1–11. ACM, 1984.
  * [22] A. McIver and C. Morgan.  An elementary proof that Herman’s ring is $\Theta(N^{2})$.  Inf. Process. Lett., 94(2):79–84, 2005.
  * [23] T. Nakata.  On the expected time for Herman’s probabilistic self-stabilizing algorithm.  Theor. Comput. Sci., 349(3):475–483, 2005.
  * [24] R.I. Oliveira.  On the coalescence time of reversible random walks.  Trans. Amer. Math. Soc., 364(4):2109–2128, 2012.
  * [25] J. Rambeau and G. Schehr.  Distribution of the time at which $N$ vicious walkers reach their maximal height.  Phys. Rev. E, 83, 2011.
  * [26] G. Schehr, S. N. Majumdar, A. Comtet, and P. J. Forrester.  Reunion probability of $N$ vicious walkers: Typical and large fluctuations for large $N$.  J. Stat. Phys., 150:491–530, 2013.
  * [27] M. Warner.  Aggregation in dense solutions of rods.  J. Chem. Soc. Faraday. Trans., 87(6):861–867, 1991.

##  Appendix A Proof of Lemma 3.5

Let $z:\\{1,\ldots,K\\}\rightarrow\\{1,\ldots,N\\}$ be a $K$-token
configuration on a ring with $N$ processes. Recall that the associated gap
vector ${\bf g}(z)=(g_{0},\ldots,g_{K-1})\in\mathbb{N}^{K}$ is defined by
$g_{0}:=N+z(1)-z(K)$ and $g_{i}:=z(i+1)-z(i)$ for $i=1,\ldots,K-1$.

Given $z$, consider the _gap-increment vector_ $\Delta:={\bf
g}(z^{\prime})-{\bf g}(z)$, where $z^{\prime}$ is the random successor
configuration of $z$. This is a random variable taking values in
$\\{-1,0,+1\\}^{K}$ where, for each $i\in\\{0,\ldots,K-1\\}$, $\Delta_{i}=0$
with probability $1/2$ (the two tokens adjacent to the $i$-th gap both stay or
both move clockwise), and $\Delta_{i}=\pm 1$ with probability $1/4$ (one token
stays and the other moves clockwise).

We will need the following two properties (18) and (19) concerning the
expectation of the random variable $\Delta$. First, it is straightforward to
verify by direct calculation that for $0\leq k<K$,

$\displaystyle\mathbb{E}(\Delta_{i}\Delta_{i+1}\ldots\Delta_{i+k})=\left\\{\begin{array}[]{ll}0&\mbox{if
$k$ is even}\\\ \left(-\frac{1}{4}\right)^{(k+1)/2}&\mbox{if $k$ is
odd}\end{array}\right.$ (18)

Secondly, suppose that $0\leq i_{1}\leq i_{2}<i_{3}\leq i_{4}<K$, with
$i_{3}\not\equiv i_{2}+1$ and $i_{1}\not\equiv i_{4}+1$ modulo $K$, that is,
$\\{i_{1},\ldots,i_{2}\\}$ and $\\{i_{3},\ldots,i_{4}\\}$ form two non-
adjacent intervals (treating $K-1$ and $0$ as adjacent). Then

$\displaystyle\mathbb{E}(\Delta_{i_{1}}\ldots\Delta_{i_{2}}\Delta_{i_{3}}\ldots\Delta_{i_{4}})=\mathbb{E}(\Delta_{i_{1}}\ldots\Delta_{i_{2}})\mathbb{E}(\Delta_{i_{3}}\ldots\Delta_{i_{4}})\,.$
(19)

because $\Delta_{i_{1}},\ldots,\Delta_{i_{2}}$ and
$\Delta_{i_{3}},\ldots,\Delta_{i_{4}}$ are determined by the movements of
disjoints sets of tokens, and hence are independent.

For a given configuration $z$ we want to compute $\mathbb{E}[f_{5}({\bf
g}(z)+\Delta)]$. From the definition of $f_{5}$ and the linearity of
expectation, this is a sum of expressions of the form

$\displaystyle\mathbb{E}(g_{i_{0}}+\Delta_{i_{0}})(g_{i_{1}}+\Delta_{i_{1}})(g_{i_{2}}+\Delta_{i_{2}})(g_{i_{3}}+\Delta_{i_{3}})(g_{i_{4}}+\Delta_{i_{4}})$
(20)

over the set of indices $0\leq i_{0}<i_{1}<i_{2}<i_{3}<i_{4}<K$ of alternating
parity.

Expression (20) evaluates to a degree-5 polynomial in the variables ${\bf g}$.
Observe that this polynomial has no monomials of even degree. For example, all
degree-2 monomials have coefficients of the form
$\mathbb{E}(\Delta_{i}\Delta_{j}\Delta_{k})$ with $i<j<k$. These coefficients
are zero by (18) and (19). Degrees 0 and 4 are proved similarly.

There is a single degree-5 monomial in (20)—namely $g_{i_{0}}\ldots
g_{i_{4}}$. Summing all such terms over indices $0\leq
i_{0}<i_{1}<i_{2}<i_{3}<i_{4}<K$ of alternating parity yields $f_{5}({\bf
g}(z))$.

Expanding the expression (20) yields degree-3 monomials of the form

$g_{j_{0}}g_{j_{1}}g_{j_{2}}\mathbb{E}(\Delta_{j_{3}}\Delta_{j_{4}})$

for distinct indices $j_{0}<j_{1}<j_{2}$. The coefficient of such a term is
$-1/4$ if $j_{4}\equiv j_{3}+1$ or $j_{3}\equiv j_{4}+1$ and $0$ otherwise.
Moreover, if $j_{0},j_{1},j_{2}$ have alternating parity there are $(K-3)/2$
choices of $j_{3}$ such that
$g_{j_{0}}g_{j_{1}}g_{j_{2}}\mathbb{E}(\Delta_{j_{3}}\Delta_{j_{3}+1})$
appears in (20). If $j_{0},j_{1},j_{2}$ do not have alternating parity then
there are no such terms in (20). We conclude that the sum of all degree-3
monomials in $\mathbb{E}(f_{5}({\bf g}(z)+\Delta)$ is

$-\frac{(K-3)}{8}f_{3}({\bf g}(z))\,.$

Finally, consider the degree-1 monomials. These have the form

$g_{j_{0}}\mathbb{E}(\Delta_{j_{1}}\Delta_{j_{2}}\Delta_{j_{3}}\Delta_{j_{4}})$

for distinct indices $j_{0}$ and $j_{1}<j_{2}<j_{3}<j_{4}$. By Property (19),
such terms are only non-zero if $\\{j_{1},j_{2},j_{3},j_{4}\\}$ comprises
either a single block of adjacent indices or two non-adjacent blocks of length
$2$ (considering $K-1$ and $0$ to be adjacent). In this case
$\mathbb{E}(\Delta_{j_{1}}\Delta_{j_{2}}\Delta_{j_{3}}\Delta_{j_{4}})=1/16$,
and there are $\binom{(K-1)/2}{2}=(K-1)(K-3)/8$ such choices of
$\\{j_{1},j_{2},j_{3},j_{4}\\}$ for each choice of $j_{0}$. Thus $g_{j_{0}}$
has total coefficient $(K-1)(K-3)/128$ in $\mathbb{E}(f_{5}({\bf
g}(z)+\Delta))$. Moreover, since $g_{0}+\ldots+g_{K-1}=N$, the degree-1 terms
in $\mathbb{E}(f_{5}({\bf g}(z)+\Delta))$ sum to $N(K-1)(K-3)/128$.

In summary, we have proved:

######  Proposition A.1.

For each $K$-token configuration $z$,

$\mathbb{E}(f_{5}({\bf g}(z)+\Delta))=f_{5}({\bf
g}(z))-\frac{K-3}{8}f_{3}({\bf g}(z))+\frac{(K-1)(K-3)N}{128}\,.$

Lemma 3.5 follows immediately from Proposition A.1 by scaling, since
$V_{5}(z)=4N^{2}f_{5}({\bf g}(z)/N)=\frac{4}{N^{3}}f_{5}({\bf g}(z))$ is a
linear multiple of $f_{5}({\bf g}(z))$.

##  Appendix B Proofs of Properties of an Interior Local Maximum

Lemma 4.1. Let ${\bf v}$ be a local maximum of $f^{(K)}$ in the interior of
$D^{(K)}$ and define $c\in\mathbb{R}$ by

$\displaystyle c\ \ =\sum_{\begin{subarray}{c}1<i_{2}<K\\\ \text{$i_{2}$
even}\end{subarray}}v_{i_{2}}\
-\quad\alpha\hskip-15.00002pt\sum_{\begin{subarray}{c}1<i_{2}<i_{3}<i_{4}<K\\\
\text{$i_{2}$, $i_{4}$ even}\\\ \text{$i_{3}$
odd}\end{subarray}}\hskip-15.00002ptv_{i_{2}}v_{i_{3}}v_{i_{4}}\,.$ (21)

This expression holds for the same value of $c$ if the indices are rotated by
an arbitrary $k$: for all $j$ the index $i_{j}$ becomes $(i_{j}+k)\bmod K$.
Further, we have

$\displaystyle\sum_{\begin{subarray}{c}3\leq i_{3}<i_{4}<K\\\ \text{$i_{3}$
odd}\\\ \text{$i_{4}$
even}\end{subarray}}\\!\\!\\!\\!v_{i_{3}}v_{i_{4}}\leq\frac{1}{\alpha}$ (22)

Again, this inequality also holds when indices are rotated.

######  Proof B.1.

We consider the second-order Taylor expansion of $f^{(K)}$ along the direction
${\bf d}=(-1,0,1,0,\ldots,0)$ (which is tangent to $D^{(K)}$):

$f^{(K)}({\bf x}+\epsilon{\bf d})=f^{(K)}({\bf x})+\epsilon Q({\bf
x})+\epsilon^{2}R({\bf x})+O(\epsilon^{3})\;.$

Since ${\bf v}$ is a local maximum, we have $Q({\bf v})=0$ and $R({\bf v})\leq
0$. Proving (21) boils down to calculating $Q({\bf x})$; proving (22) boils
down to calculating $R({\bf x})$.

First, we prove (21). Let

$f^{(K)}(x_{0}+\epsilon,x_{1},\ldots,x_{K-1})=f^{(K)}({\bf x})+\epsilon P({\bf
x})+O(\epsilon^{2}).$

By the chain rule and using the rotational symmetry of $f^{(K)}$ (Lemma
3.1(a)), we find that

$Q(x_{0},\ldots,x_{K-1})=P(x_{0+2},x_{1+2},\ldots,x_{K-1+2})-P(x_{0},x_{1},\ldots,x_{K-1}).$

Now recall the definition of $f^{(K)}$:

$f^{(K)}({\bf x}):=\hskip-10.00002pt\sum_{\begin{subarray}{c}0\leq
i_{0}<i_{1}<i_{2}<K\\\ \text{$i_{2}-i_{1}$ and $i_{1}-i_{0}$
odd}\end{subarray}}\hskip-20.00003ptx_{i_{0}}x_{i_{1}}x_{i_{2}}-\hskip-20.00003pt\sum_{\begin{subarray}{c}0\leq
i_{0}<\cdots<i_{4}<K\\\ \text{$i_{4}-i_{3},\ldots,i_{1}-i_{0}$ all
odd}\end{subarray}}\hskip-20.00003pt\alpha
x_{i_{0}}x_{i_{1}}x_{i_{2}}x_{i_{3}}x_{i_{4}}$ (23)

We differentiate $f^{(K)}$ with respect to $x_{0}$ to obtain

$\displaystyle P({\bf x})=\sum_{\begin{subarray}{c}0<i_{1}<i_{2}<K\\\
\text{$i_{1}$ odd}\\\ \text{$i_{2}$
even}\end{subarray}}\hskip-10.00002ptx_{i_{1}}x_{i_{2}}-\hskip-10.00002pt\sum_{\begin{subarray}{c}0<i_{1}<\cdots<i_{4}<K\\\
\text{$i_{1},i_{3}$ odd}\\\ \text{$i_{2},i_{4}$
even}\end{subarray}}\hskip-20.00003pt\alpha
x_{i_{1}}x_{i_{2}}x_{i_{3}}x_{i_{4}}.$ (24)

Since ${\bf v}$ is a local maximum, $Q({\bf v})=0$ and we have

$\sum_{\begin{subarray}{c}0<i_{1}<i_{2}<K\\\ \text{$i_{1}$ odd}\\\
\text{$i_{2}$
even}\end{subarray}}\hskip-10.00002ptv_{i_{1}}v_{i_{2}}-\hskip-10.00002pt\sum_{\begin{subarray}{c}0<i_{1}<\cdots<i_{4}<K\\\
\text{$i_{1},i_{3}$ odd}\\\ \text{$i_{2},i_{4}$
even}\end{subarray}}\hskip-20.00003pt\alpha
v_{i_{1}}v_{i_{2}}v_{i_{3}}v_{i_{4}}=\sum_{\begin{subarray}{c}0<i_{1}<i_{2}<K\\\
\text{$i_{1}$ odd}\\\ \text{$i_{2}$
even}\end{subarray}}\hskip-10.00002ptv_{i_{1}+2}v_{i_{2}+2}-\hskip-10.00002pt\sum_{\begin{subarray}{c}0<i_{1}<\cdots<i_{4}<K\\\
\text{$i_{1},i_{3}$ odd}\\\ \text{$i_{2},i_{4}$
even}\end{subarray}}\hskip-20.00003pt\alpha
v_{i_{1}+2}v_{i_{2}+2}v_{i_{3}+2}v_{i_{4}+2}$

Observe that the monomials not containing $v_{1}$ cancel each other out.
Dividing by $v_{1}=v_{1+K}$ (since $v_{1}>0$), we have

$\sum_{\begin{subarray}{c}1<i_{2}<K\\\ \text{$i_{2}$
even}\end{subarray}}\hskip-10.00002ptv_{i_{2}}-\hskip-10.00002pt\sum_{\begin{subarray}{c}1<i_{2}<i_{3}<i_{4}<K\\\
\text{$i_{3}$ odd}\\\ \text{$i_{2},i_{4}$
even}\end{subarray}}\hskip-20.00003pt\alpha
v_{i_{2}}v_{i_{3}}v_{i_{4}}=\sum_{\begin{subarray}{c}0<i_{1}<K-1\\\
\text{$i_{1}$
odd}\end{subarray}}\hskip-10.00002ptv_{i_{1}+2}-\hskip-10.00002pt\sum_{\begin{subarray}{c}0<i_{1}<i_{2}<i_{3}<K-1\\\
\text{$i_{1},i_{3}$ odd}\\\ \text{$i_{2}$
even}\end{subarray}}\hskip-20.00003pt\alpha v_{i_{1}+2}v_{i_{2}+2}v_{i_{3}+2}$

Now we observe that the right hand side can be obtained from the left hand
side by changing each index $i$ into $i+1$. Taking into account rotations of
the above equality, we conclude (21).

Next, we prove (22). To do so, we first calculate the terms of order
$\epsilon^{2}$ of $f^{(K)}({\bf x}+\epsilon{\bf d})$. Such terms occur only
when $i_{0}=0$, $i_{1}=1$, and $i_{2}=2$. In this case, the first sum reduces
to $(x_{0}-\epsilon)x_{1}(x_{2}+\epsilon)$, and the second sum reduces to

$\alpha(x_{0}-\epsilon)x_{1}(x_{2}+\epsilon)\hskip-10.00002pt\sum_{\begin{subarray}{c}2<i_{3}<i_{4}<K\\\
\text{$i_{3}$ odd, $i_{4}$
even}\end{subarray}}\hskip-10.00002ptx_{i_{3}}x_{i_{4}}.$

Thus,

$R({\bf x})=-x_{1}+\alpha
x_{1}\hskip-10.00002pt\sum_{\begin{subarray}{c}2<i_{3}<i_{4}<K\\\
\text{$i_{3}$ odd, $i_{4}$
even}\end{subarray}}\hskip-10.00002ptx_{i_{3}}x_{i_{4}}.$

Since the assumed interior local maximum ${\bf v}$ is in the interior of
$D^{(K)}$, we have that $v_{1}>0$, and so the condition $R({\bf v})\leq 0$ is
equivalent to $R({{\bf v}})/v_{1}\leq 0$:

$-1+\hskip-10.00002pt\sum_{\begin{subarray}{c}2<i_{3}<i_{4}<K\\\ \text{$i_{3}$
odd, $i_{4}$ even}\end{subarray}}\hskip-15.00002pt\alpha
v_{i_{3}}v_{i_{4}}\leq 0$

Up to trivial rearrangement, we obtained (22).

Corollary 4.3. Let ${\bf v}$ be a local maximum of $f^{(K)}$ in the interior
of $D^{(K)}$. Then the following inequality holds:

$\sum_{\begin{subarray}{c}1\leq i<K-2\\\ \text{$i$
odd}\end{subarray}}\frac{K-i-2}{2}S_{i}({\bf
v})\quad\leq\quad\frac{K}{\alpha}$

######  Proof B.2.

We sum (22) over all $K$ rotations:

$\displaystyle\frac{K}{\alpha}$
$\displaystyle\geq\sum_{i=0}^{K-1}\sum_{\begin{subarray}{c}3\leq
i_{3}<i_{4}<K\\\ \text{$i_{3}$ odd}\\\ \text{$i_{4}$
even}\end{subarray}}\\!\\!\\!v_{i_{3}+i}v_{i_{4}+i}=\sum_{\begin{subarray}{c}3\leq
i_{3}<i_{4}<K\\\ \text{$i_{3}$ odd}\\\ \text{$i_{4}$
even}\end{subarray}}\sum_{i=0}^{K-1}v_{i_{3}+i}v_{i_{4}+i}=\sum_{\begin{subarray}{c}3\leq
i_{3}<i_{4}<K\\\ \text{$i_{3}$ odd}\\\ \text{$i_{4}$
even}\end{subarray}}\\!\\!\\!S_{i_{4}-i_{3}}({\bf v})$
$\displaystyle=\sum_{\begin{subarray}{c}3\leq i_{3}<i_{3}+i<K\\\ \text{$i$
odd, $i_{3}$ odd}\end{subarray}}\\!\\!\\!\\!S_{i}({\bf
v})=\sum_{\begin{subarray}{c}1\leq i\\\ \text{$i$
odd}\end{subarray}}\sum_{\begin{subarray}{c}3\leq i_{3}<K-i\\\ \text{$i_{3}$
odd}\end{subarray}}\\!\\!\\!\\!S_{i}({\bf v})=\sum_{\begin{subarray}{c}1\leq
i<K-2\\\ \text{$i$ odd}\end{subarray}}\frac{K-i-2}{2}S_{i}({\bf v})$

##  Appendix C Proofs of Combinatorial Lemmas

We repeat the combinatorial facts of Section 4.4, this time with proofs.

Lemma 4.6. We have:

$\sum_{k=0}^{K-1}\sum_{\begin{subarray}{c}1<i^{\prime}_{0}<i^{\prime}_{1}<i^{\prime}_{2}<K\\\
\text{$i^{\prime}_{0}$, $i^{\prime}_{2}$ even}\\\ \text{$i^{\prime}_{1}$
odd}\end{subarray}}x_{i^{\prime}_{0}+k}x_{i^{\prime}_{1}+k}x_{i^{\prime}_{2}+k}=\frac{K-3}{2}\hskip-10.00002pt\sum_{\begin{subarray}{c}0\leq
i_{0}<i_{1}<i_{2}<K\\\ \text{$i_{2}-i_{1}$, $i_{1}-i_{0}$
odd}\end{subarray}}\hskip-20.00003ptx_{i_{0}}x_{i_{1}}x_{i_{2}}=\frac{K-3}{2}f_{3}^{(K)}({\bf
x})$

######  Proof C.1.

Let us fix $0\leq i_{0}<i_{1}<i_{2}<K$ such that both $i_{2}-i_{1}$ and
$i_{1}-i_{0}$ are odd. We want to show that the term
$x_{i_{0}}x_{i_{1}}x_{i_{2}}$ occurs $(K-3)/2$ times in each side of the
equality. The middle and right sides are trivial; it remains to check the left
side. Let us now fix an arbitrary $k$. For a term on the left hand side to
equal $x_{i_{0}}x_{i_{1}}x_{i_{2}}$, it must be that the sets
$\\{(i^{\prime}_{0}+k)\bmod K,(i^{\prime}_{1}+k)\bmod
K,(i^{\prime}_{2}+k)\bmod K\\}$ and $\\{i_{0},i_{1},i_{2}\\}$ are equal. In
other words, once $i_{0},i_{1},i_{2},k$ are fixed, the set
$\\{i^{\prime}_{0},i^{\prime}_{1},i^{\prime}_{2}\\}$ is uniquely determined.
Since, $i^{\prime}_{0}<i^{\prime}_{1}<i^{\prime}_{2}$, the potential values of
$i^{\prime}_{0},i^{\prime}_{1},i^{\prime}_{2}$ are also uniquely determined.
The remaining question is for how many $k\in\\{0,\ldots,K-1\\}$ it is the case
that the values $i^{\prime}_{0},i^{\prime}_{1},i^{\prime}_{2}$ so determined
obey the other constraints.

There are three disjoint cases: The smallest value in the set
$\\{i^{\prime}_{0},i^{\prime}_{1},i^{\prime}_{2}\\}$, namely $i^{\prime}_{0}$,
is $(i_{0}-k)\bmod K$ or $(i_{1}-k)\bmod K$ or $(i_{2}-k)\bmod K$. The case
$i^{\prime}_{0}=(i_{1}-k)\bmod K$ occurs exactly when (a) $i_{0}<k<i_{1}$, and
(b) $k$ has the same parity as $i_{1}$. Let $\delta_{0}$ denote the size of
the gap between $i_{0}$ and $i_{1}$. Then, there are $(\delta_{0}-1)/2$ values
of $k$ that obey both (a) and (b). The other two cases are similar, and so we
conclude that the term $x_{i_{0}}x_{i_{1}}x_{i_{2}}$ occurs on the left hand
side

$\frac{\delta_{0}-1}{2}+\frac{\delta_{1}-1}{2}+\frac{\delta_{2}-1}{2}=\frac{K-3}{2}$

times.

Lemma 4.7. Let ${\bf v}$ be a local maximum of $f^{(K)}$ in the interior of
$D^{(K)}$. If $i_{1}$ is odd and $0<i_{1}<K$, then the following inequality
holds:

$v_{0}v_{i_{1}}\biggl{(}\sum_{\begin{subarray}{c}1<i_{2}<K\\\ \text{$i_{2}$
even}\end{subarray}}v_{i_{2}}-\hskip-10.00002pt\sum_{\begin{subarray}{c}1<i_{2}<i_{3}<i_{4}<K\\\
\text{$i_{2},i_{4}$ even}\\\ \text{$i_{3}$
odd}\end{subarray}}\hskip-20.00003pt\alpha
v_{i_{2}}v_{i_{3}}v_{i_{4}}\biggr{)}\geq
v_{0}v_{i_{1}}\biggl{(}\sum_{\begin{subarray}{c}i_{1}<i_{2}<K\\\ \text{$i_{2}$
even}\end{subarray}}v_{i_{2}}-\hskip-10.00002pt\sum_{\begin{subarray}{c}i_{1}<i_{2}<i_{3}<i_{4}<K\\\
\text{$i_{2},i_{4}$ even}\\\ \text{$i_{3}$
odd}\end{subarray}}\hskip-20.00003pt\alpha
v_{i_{2}}v_{i_{3}}v_{i_{4}}\biggr{)}$

######  Proof C.2.

The proof below is a case analysis of where $i_{1}$ can be inserted in-between
$0<i_{2}<i_{3}<i_{4}<K$. As noted before, the task is to show that retaining
the terms that occur in $f_{5}$ gives a lower bound. In other words, we want
to show that those terms not occurring in $f_{5}$ have a positive sum. We
calculate this sum:

$\displaystyle\sum_{\begin{subarray}{c}1<i_{2}<i_{1}\\\ \text{$i_{2}$
even}\end{subarray}}v_{0}v_{i_{2}}v_{i_{1}}-\hskip-10.00002pt\sum_{\begin{subarray}{c}1<i_{2}<i_{3}<i_{4}<K\\\
i_{2}<i_{1}\end{subarray}}\hskip-20.00003pt\alpha
v_{0}v_{i_{2}}v_{i_{1}}v_{i_{3}}v_{i_{4}}$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}1<i_{2}<i_{1}\\\ \text{$i_{2}$
even}\end{subarray}}v_{0}v_{i_{2}}v_{i_{1}}\Bigl{(}1-\hskip-10.00002pt\sum_{\begin{subarray}{c}i_{2}<i_{3}<i_{4}<K\\\
\text{$i_{3}$ odd, $i_{4}$ even}\end{subarray}}\hskip-10.00002pt\alpha
v_{i_{3}}v_{i_{4}}\Bigr{)}$ $\displaystyle\geq$
$\displaystyle\sum_{\begin{subarray}{c}1<i_{2}<i_{1}\\\ \text{$i_{2}$
even}\end{subarray}}v_{0}v_{i_{2}}v_{i_{1}}\Bigl{(}1-\hskip-10.00002pt\sum_{\begin{subarray}{c}3\leq
i_{3}<i_{4}<K\\\ \text{$i_{3}$ odd, $i_{4}$
even}\end{subarray}}\hskip-10.00002pt\alpha
v_{i_{3}}v_{i_{4}}\Bigr{)}\quad\mathop{\geq}^{\text{by\leavevmode\nobreak\
\eqref{eq-d2-nonpos}}}\quad 0$

Lemma 4.8. Let $l$ be an odd, positive integer. Then:

$\sum_{k=0}^{K-1}\sum_{\begin{subarray}{c}1\leq i^{\prime}_{1}<K-2\\\
\text{$i^{\prime}_{1}$
odd}\end{subarray}}\frac{K-i^{\prime}_{1}-2}{2}\hskip-10.00002pt\sum_{\begin{subarray}{c}i^{\prime}_{1}<i^{\prime}_{2}<\cdots<i^{\prime}_{l-1}<K\\\
\forall j,\;i^{\prime}_{j}\equiv
j\pmod{2}\end{subarray}}x_{k}x_{i^{\prime}_{1}+k}\prod_{\begin{subarray}{c}1<j<l\end{subarray}}x_{i^{\prime}_{j}+k}=\\\
=\Bigl{(}\frac{l-1}{2}K-l\Bigr{)}\hskip-10.00002pt\sum_{\begin{subarray}{c}0\leq
i_{0}<\cdots<i_{l-1}<K\\\ \text{$i_{j}-i_{j-1}$ odd for
$0<j<l$}\end{subarray}}\prod_{j=0}^{l-1}x_{i_{j}}$

The proof is similar to that of Lemma 4.6.

######  Proof C.3.

Let us fix $0\leq i_{0}<\cdots<i_{l-1}<K$ with odd gaps in-between. We want to
show that the term $x_{i_{0}}\ldots x_{i_{l-1}}$ occurs $(l-1)K/2-l$ times on
each side of the equation. For the right side, it is trivial. The general form
of a term on the left side is
$x_{k}x_{i^{\prime}_{1}+k}x_{i^{\prime}_{2}+k}\ldots x_{i^{\prime}_{l-1}+k}$.
It must be that $k$ is one of $i_{0},\ldots,i_{l-1}$. Let us consider the case
$k=i_{0}$; the others are similar. If $k=i_{0}$, then, in fact,

$(k,i^{\prime}_{1}+k,i^{\prime}_{2}+k,\ldots,i^{\prime}_{l-1}+k)\bmod
K\quad=\quad(i_{0},i_{1},\ldots,i_{l-1}).$

In particular, $i^{\prime}_{1}$ equals the size of the gap between $i_{0}$ and
$i_{1}$. Let us denote this gap by $\delta_{0}$. On the left hand side, the
term is multiplied by $(K-i^{\prime}_{1}-2)/2$, which is $(K-\delta_{0}-2)/2$.
The cases $k=i_{1}$, $k=i_{2}$, …are similar. Because
$\delta_{0}+\cdots+\delta_{l-1}=K$, we conclude that the term $x_{i_{0}}\ldots
x_{i_{l-1}}$ occurs

$\frac{K-\delta_{0}-2}{2}+\cdots+\frac{K-\delta_{l-1}-2}{2}=\frac{l-1}{2}K-l$

times on the left side.