# Representations of Hecke algebras and Markov dualities for interacting
particle systems

Alexander Povolotsky  Bogoliubov Laboratory of Theoretical Physics, Joint
Institute for Nuclear Research, 141980 Dubna, Moscow region, Russia  National
Research University, Higher School of Economics, 20 Myasnitskaya street,
Moscow 101000, Russia  Pavel Pyatov  National Research University, Higher
School of Economics, 20 Myasnitskaya street, Moscow 101000, Russia  Bogoliubov
Laboratory of Theoretical Physics, Joint Institute for Nuclear Research,
141980 Dubna, Moscow region, Russia  Roger Tribe  Department of Mathematics,
University of Warwick, Coventry, CV4 7AL, UK  Bruce Westbury  Department of
Mathematics, University of Warwick, Coventry, CV4 7AL, UK  Oleg Zaboronski
Department of Mathematics, University of Warwick, Coventry, CV4 7AL, UK

###### Abstract

Many continuous reaction-diffusion models on ${\mathbb{Z}}$ (annihilating or
coalescing random walks, exclusion processes, voter models) admit a rich set
of Markov duality functions which determine the single time distribution. A
common feature of these models is that their generators are given by sums of
two-site idempotent operators. In this paper, we classify all continuous time
Markov processes on $\\{0,1\\}^{{\mathbb{Z}}}$ whose generators have this
property, although to simplify the calculations we only consider models with
equal left and right jumping rates. The classification leads to six familiar
models and three exceptional models. The generators of all but the exceptional
models turn out to belong to an infinite dimensional Hecke algebra, and the
duality functions appear as spanning vectors for small-dimensional irreducible
representations of this Hecke algebra. A second classification explores
generators built from two site operators satisfying the Hecke algebra
relations. The duality functions are intertwiners between configuration and
co-ordinate representations of Hecke algebras, which results in a novel co-
ordinate representations of the Hecke algebra. The standard Baxterisation
procedure leads to new solutions of the Young-Baxter equation corresponding to
particle systems which do not preserve the number of particles.

Keywords: Interacting particle system, Markov duality, Hecke Algebra, Yang-
Baxter equation

###### Contents

  1. 1 Introduction
    1. 1.1 Markov duality
    2. 1.2 Literature review
    3. 1.3 Aims of the present paper and its organisation
  2. 2 Two familiar models
    1. 2.1 Tensor notation
    2. 2.2 Annihilating simple random walks
    3. 2.3 Asymmetric simple exclusion process
    4. 2.4 The Hecke relations and duality
  3. 3 Classifications of generators
    1. 3.1 Generators built out of projectors
    2. 3.2 Generators built using the braid relation
  4. 4 The eleven models
    1. 4.1 Exclusion processes [SEP] and [ASEP]
    2. 4.2 Voter models [BVM], [AVM] and [AAVM]
    3. 4.3 Annihilating and coalescing systems [ACRW], [CSRWB], [ASRWPI]
    4. 4.4 Stationary coalescence-annihilation model [SCAM]
    5. 4.5 The dimer model [DM]
    6. 4.6 The reshuffle model [RM]
    7. 4.7 Erosion models: [EM1] and [EM2]
  5. 5 Algebra
    1. 5.1 Duality functions and representations of the generator algebra
    2. 5.2 On exact solvability and representation theory
    3. 5.3 Co-ordinate representation of a Hecke algebra
    4. 5.4 Baxterisation and R-matrices with non-conserved particle number
  6. 6 Linear Algebra Proofs
    1. 6.1 Proof of Lemma 4.
    2. 6.2 Proof of Lemma 5
    3. 6.3 Proof of Theorem 6
  7. 7 Acknowledgements.
  8. A Appendix

##  1 Introduction

###  1.1 Markov duality

Let $\\{X_{t}\\}_{t\in\mathbb{R}_{+}}$ and $\\{Y_{t}\\}_{t\in\mathbb{R}_{+}}$
be continuous time Markov processes with state spaces $\mathcal{X}$ and
$\mathcal{Y}$ and $H(\cdot,\cdot):\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$
be a measurable function. We say that $X_{t}$ and $Y_{t}$ are dual with
respect to $H(\cdot,\cdot)$ if for any $x\in\mathcal{X}$ and $y\in\mathcal{Y}$
the identity

$\mathbb{E}^{X}_{x}H(X_{t},y)=\mathbb{E}^{Y}_{y}H(x,Y_{t}),$ (1)

holds for any $t\in\mathbb{R}_{+}$, where the expectation $\mathbb{E}^{X}_{x}$
($\mathbb{E}^{Y}_{y}$) is with respect to the process $X_{t}$ ($Y_{t}$)
conditioned on the initial state $X_{0}=x$ ($Y_{0}=y$) respectively. Given the
generators of the processes $L_{X}$ and $L_{Y}$ that govern the evolution of
expectations of suitable test functions,

$\frac{d}{dt}\mathbb{E}^{X}_{x}F(X_{t})=L_{X}\mathbb{E}^{X}_{x}F(X_{t}),\quad\frac{d}{dt}\mathbb{E}^{Y}_{y}G(Y_{t})=L_{Y}\mathbb{E}^{Y}_{y}G(Y_{t}),$
(2)

where $F(\cdot):\mathcal{X}\to\mathbb{R}$ and
$G(\cdot):\mathcal{Y}\to\mathbb{R}$, eq. (1) implies

$L_{X}H(\cdot,y)(x)=L_{Y}H(x,\cdot)(y),$ (3)

where the operator $L_{X}$ ($L_{Y}$) in lhs (rhs) acts on $H(x,y)$ as a
function of the first (second) argument respectively with the other argument
fixed.

Formulas (1,3) allow one to rewrite the Kolmogorov equation for the
expectation of $H(x,y)$ considered as a function of the first argument as a
system of ordinary differential equations indexed by the values of the second
one.

$\frac{d}{dt}\mathbb{E}^{X}_{x}H(X_{t},y)=L_{Y}\mathbb{E}^{X}_{x}H(X_{t},\cdot)(y),\quad
y\in\mathcal{Y}.$ (4)

Markov duality is particularly useful in situations when the original process
$X$ is too complicated to analyse directly, whereas the operator $L_{Y}$ is
tractable (the equation (4) is useful even if a dual process $Y$ does not
exist). In other words, it is the exact solvability of (4) that we really care
about. Furthermore, in exceptional cases one can find sufficiently many
duality functions so that their expectations determine the whole law of the
original process or at least its fixed time distribution. In these cases we
say that the set of Markov dualities is complete.

In relation to the subject of this article, interacting particle systems, one
can draw a parallel between the existence of a complete set of Markov
dualities and the exact solvability of quantum particle models or quantum spin
chains coined in the term “quantum integrability” [15]. Loosely speaking, a
system is integrable if its evolution operator (the Hamiltonian for quantum
models or the generator for Markov processes) belongs to a sufficiently
‘large’ number of commuting operators called integrals of motion.
Algebraically, this corresponds to a large centre of a representation of some
operator algebra containing the evolution operator. Typically, such
representation possesses a high degree of symmetry. For example, in the
simplest case of a finite XXX Heisenberg spin-$1/2$ chain the Hamiltonian is
an element of the representation of the group algebra of the symmetric group
on the tensor product of two-dimensional spaces. The statement known as Schur-
Weyl duality implies that this representation commutes with the representation
of $SL(2)$ Lie group on the same space. This fact allows one to identify the
invariant subspaces used to construct the eigen-basis of the Hamiltonian.
However, there is a long way from the eigen-basis to physical observables,
which often makes the information about the correlation functions of interest
difficult to extract.

The Markov duality is often used as an alternative route which avoids the
diagonalization problem and goes directly to the observables instead. In
addition, it has a natural algebraic interpretation. Namely, interpreting the
generator $L_{X}$ as an element of the representation of some algebra, it is
natural to treat the dual operator $L_{Y}$ as another representation of the
same algebra with the duality function playing the role of the intertwiner
between the two, see e.g. [18]. The possibility to intertwine the
representations is crucial for the mentioned solvability of the problem. A
typical scenario realised for many models considered in this paper is as
follows: the original model has generator $L_{X}$ belonging to a
representation of some algebra $\mathbb{A}$ of dimension $O(2^{N})$, where
$N\rightarrow\infty$ is the system size. Yet, for each $n\in{\mathbb{N}}$
there is a duality function intertwining this ‘large’ representation to a
‘small’ representation of $\mathbb{A}$ of dimension $O(N^{n})$ containing the
dual generator $L_{Y}$. Then it follows from (4) that the expectation of the
corresponding duality function solves a closed system of $O(N^{n})$ ODE’s, a
small system in comparison with $2^{N}$ differential-difference equations
comprising the Kolmogorov equation for the original system. Probabilistically,
this scenario corresponds to a Markov duality between the original system with
$O(N)$ particles and the dual system with $n$ particles, for each
$n\in{\mathbb{N}}$. The crucial element of the described construction is the
existence of ‘small’ irreducible representations of the algebra $\mathbb{A}$
containing the generator. Therefore, the natural starting point for
constructing duality functions is the search for $\mathbb{A}$-invariants
subspaces within the original space of dimension $O(2^{N})$.

Of course, exact solvability is an exceptional phenomenon, implying that the
corresponding algebra $\mathbb{A}$ has a special structure. One of the aims of
the present paper is to understand the origins of the exact solvability for a
number of ‘integrable’ interacting particle systems including exclusion
processes as well as systems of interacting random walks with interactions
which do not preserve the particle number (coalescence and annihilation in the
presence of branching or immigration). For each of these cases we will observe
that the corresponding algebra $\mathbb{A}$ is a quotient of Hecke algebra. In
this instance the duality functions emerge as spanning vectors of ‘small’
representations of Hecke algebra.

###  1.2 Literature review

Let us briefly review the previous developments in this direction. Early
appearances of Markov duality in the literature go back to the middle of the
last century, when it was applied to studies of the Brownian motion [30],
queuing theory [34], birth and death processes [24], etc. Since then the
duality was shown to be useful in plenty applications and several efforts of
developing an approach to systematic search for Markov dualities were
undertaken (see [22] for review and references therein).

In the field of our interest, interacting particle systems, the first
application of duality was exploited by Spitzer to study the stationary
measures of the symmetric simple exclusion process ([SEP]) and independent
random walks [40]. Later the duality was applied to study ergodic properties
of several models like [SEP], voter model, contact process etc [31]. It is a
common scenario that the dualities, mainly constructed in ad hoc manner for
every particular case, allowed a reformulation of the problem of calculation
of $n-$point correlation functions in terms of $k$-particle problems in the
dual system with $k\leq n$. In particular, it was implemented in [38, 37, 39],
where the duality in partially symmetric and asymmetric simple exclusion
processes on the segment with reflecting ends followed from the invariance of
the Hamiltonians of the quantum chains associated with the generator of the
process with respect to the action of the representation of $SU(2)$ and
quantum group $U_{q}(gl_{2})$, respectively.

An attempt of a systematic search for dualities for the interacting particle
systems going beyond a case by case consideration was undertaken in [41, 35],
where the quantum mechanical algebraic language was shown efficient in
obtaining duality functions of product form for a large family of models.
However, the crucial step was the observation in [38, 37, 39] of the
connection between generator symmetries and dualities. It was used in [18] as
a starting point to propose a new systematic scheme for constructing the
duality functions in interacting particle systems within purely algebraic
framework. In a nutshell, starting from a trivial duality with the time
reversed process, new nontrivial dualities can be generated by the action of
the operators from the representation of a symmetry group of the generator.
This idea was then efficiently used to obtain new dualities in interacting
particle systems with one [11, 10, 9] as well as many species [4, 26, 3, 28,
27] of particles. The development [29] of this idea was based on the use of
the Schur-Weyl dauality to construct the Markov duality. The former connects
the representation of an algebra, to which a Markov generator belongs, with a
representation of its symmetry group.

Among numerous formulae for interacting particle systems based on dualities,
many of them can be expressed in terms of one-point or two-point correlation
functions. The reason, as was mentioned above, is that the duality often
allows one to recast the problem of calculating $n$-point correlation
functions in the infinite particle system in terms of a dual system with no
more than $n$ particles. Of course to go beyond $n\leq 2$ case, the many
particle problem in dual system should be solvable in some sense. If one wants
to describe exactly the finite time evolution, a kind of integrability should
stand behind the generator of the dual process, which potentially would make a
complete set of dualities analytically accessible. There are a few recent
advances in this direction. First we mention the results of [20, 7], where the
duality was used to obtain the integral formulas for the so-called $q$-moments
of distances traveled by tagged particles in the two models, ASEP and q-TASEP,
with specific initial conditions, using the self-duality of the former, found
first in [39], and the dulaity of the latter with q-Boson totally asymmetric
zero range process. These results were later extended to several other models,
like q-Hahn TASEP [13], q-Hahn ASEP [2], q-Hahn PushTASEP [14], dynamic ASEP
[6], and stochastic six vertex model [33]. In a parallel development, see
[16], [17], [43] for details, duality was used to obtain exact solutions for a
number of the so called reaction-diffusion particle systems including one-
dimensional annihilating-coalescing, coalescing-branching random walks, and
annihilating random walks with pair immigration. All of these models were
shown to have a dual process that can be taken to be a system of annihilating
random walks with $n<\infty$ initial particles. This dual process turns out to
have the structure reminiscent of free fermions, so that the $n$-particle
evolution problem is solved in terms of Pfaffians and the fixed time
distribution of particles for each of the model problems was shown to be
Pfaffian for all deterministic initial conditions (and a class of random
initial conditions). Interestingly, the Pfaffian structures survive the
continuous limit and describe the distribution of particles on the real line
for the corresponding interacting Brownian motions.

###  1.3 Aims of the present paper and its organisation

Our principal aim is to investigate the common structures responsible for
exact solvability of such apparently unrelated particle systems as exclusion
processes, annihilation random walks with pairwise immigration and coalescing-
branching random walks. Each of these models has a complete set of Markov
duality functions, which was discovered by independent analysis of each
particle system.

We notice that Markov generators for each of the interacting particle systems
listed above is defined on the space of test functions on the configuration
space $\\{0,1\\}^{\mathbb{Z}}$ and has the following form,

$\displaystyle L=\sum_{i\in{\mathbb{Z}}}(\sigma_{i}-I),$ (5)

where $I$ is the identity operator and $\sigma_{i}$ is the $2$-site operator
acting on functions of particle occupation numbers at sites $i$ and $i+1$.
Moreover, each of the two-site operators is idempotent, that is

$\displaystyle\sigma_{i}^{2}=\sigma_{i}\quad\mbox{for $i\in{\mathbb{Z}}$.}$
(6)

So in order to understand the commonality between the models of interest we
decided to classify $all$ continuous time Markov chains on the configuration
space $\\{0,1\\}^{\mathbb{Z}}$ with the generator satisfying (5, 6).

Keeping in mind the importance of duality for the models which motivated our
investigation, the first classification theorem is proved by attempting to
construct duality functions as basic vectors for ‘small’ representations of
the algebra $\mathbb{A}$ generated over $\mathbb{R}$ by the two-site
generators $\\{\sigma_{i}\\}_{i\in{\mathbb{Z}}}$, which we refer to as the
generator algebra. The result is a list of nine inequivalent interacting
particle systems, six familiar models either of exclusion or reaction-
diffusion type and three unfamiliar ’exceptional’ models. Also it turns out
that for all the six familiar models the generator algebras are certain
quotients of the infinite-dimensional Hecke algebra. For all the familiar
cases, the duality functions are built using a similar method which, as we
show separately, is a consequence of the braid relation satisfied by the
generators of a Hecke algebra. The method itself is one of the secondary
results of our investigation which can be described as a construction of
representations of Hecke algebras starting from the eigenvectors of the two-
site generators $\sigma_{i}$. Moreover, the generator algebras for many of the
reaction-diffusion systems on the list turn out to be isomorphic and the
corresponding duality functions have an identical structure, which we believe
should be responsible for the appearance of Pfaffians - a question which we
hope to investigate in the future.

The proof of the classification theorem consists of listing of all stochastic
idempotent $4\times 4$ matrices. Presently, we were only able to carry such a
search out under the assumption of reflection symmetry. In other words, we
only looked at particle systems with equal right and left hopping rates,
leaving a classification in the absence of such a symmetry for the future. In
the mean time, we notice that quotients of the Hecke algebra appear as the
generator algebras for most of our models, even for two of the three
exceptional models for special values of their parameters. Inspired by this
observation we attempt another classification theorem by listing all Markov
chains whose two-site generators obey the relations of Hecke algebra, but not
assuming the left-right symmetry. The classification is based on solving the
braid relation in terms of stochastic idempotent $4\times 4$ matrices.
Unfortunately, we were unable to solve the problem in full generality and were
forced to use a simplifying Ansatz by forbidding certain particle reactions.
Still, the resulting list contains eleven models all of which admit a full set
of duality functions supporting our suspicion about the link between exact
solvability and the representation theory of Hecke algebra.

At this point it is important to mention an alternative approach to
construction of Markov dualities for the one-component and two-component
asymmetric exclusion process, which also based on the Hecke structure of its
generator algebra [12]. The main idea is to use the so called q-Knizhnik-
Zamolodchikov equation to construct the intertwining relation between two
representations of the Hecke algebra, one in the tensor product of finite-
dimensional spaces and another in the space of symmetric polynomials. The
construction of polynomial representations and the extraction of Markov
duality functions from these representations turns out to be a highly non-
trivial problem which uses complicated tools of the theory of Macdonald
polynomials and quantum integrable systems. In contrast our construction is
completely explicit and requires only an elementary linear algebra toolbox.

Organisation of the paper. In Section 2 we motivate the algebraic approach to
the investigation of interacting particle systems by building duality
functions as bases of representations of the generator algebra for two
classical cases: annihilating random walks ([ARW]) and the asymmetric simple
exclusion process ([ASEP]) on ${\mathbb{Z}}$. We notice that for each model,
the two-site generators satisfy the relations of a Hecke algebra (reduced to
Temperley-Lieb relations in the case [ASEP]). Our approach consists of
building representations of the infinite-dimensional Hecke algebra by
extending the representation of the algebra generated by a single two-site
generator. In Subsection 2.4 we show that such an extension is always possible
due to the braid relation. In Section 3 we state our two main classification
theorems. In Section 4 we discuss the solvability of all the models appearing
in the classification theorems. Section 5 is dedicated to the discussion of
the algebraic structures appearing in the paper: in Subsection 5.1 we show how
to use duality functions to construct irreducible representations of the
quotient of a Hecke algebra corresponding to annihilating random walks on
${\mathbb{Z}}_{N}$; in Subsection 5.2 we discuss possible links between the
structure of irreducible representations of generator algebras and exact
solvability; in Subsection 5.3 we use the interpretation of duality functions
as intertwiners to construct co-ordinate representations of Hecke algebra in
the space of functions of several integer variables (the resulting Hecke
generators are expressed in terms of discrete Laplacians); in Subsection 5.4
we use the standard Baxterisation construction to find solutions of Yang-
Baxter equation which do not preserve the number of particles. The proof of
the main classification theorems can be found in Section 6.

##  2 Two familiar models

We start by re-examining two well understood particle systems, with well known
Markov dualities, using the algebraic approach adopted throughout this paper.
The models studied are continuous time Markov processes with state space
$\Omega=\\{0,1\\}^{\mathbb{Z}}$. Elements of $\Omega$ are denoted by
$\eta=(\eta(x))_{x\in{\mathbb{Z}}}$, where $\eta(x)=1$ or $\eta(x)=0$
indicates the presence of a particle or a hole at site $x\in{\mathbb{Z}}$. We
write $T(\Omega)$ for the linear space of cylinder functions
$f:\Omega\to\mathbb{R}$, that is functions that depend on only finitely many
co-ordinates.

The particle systems we study involve interactions only between nearest
neighbour sites. Their infinitesimal generators can be written as

$\mathcal{L}f(\eta)=\sum_{n\in{\mathbb{Z}}}\,\sum_{\xi,\xi^{\prime}\in\\{0,1\\}^{2}}R_{\xi,\xi^{\prime}}\left(f(\eta^{(n,n+1)}_{\xi^{\prime}})-f(\eta)\right)\mathbbm{1}_{\xi}(\eta(n),\eta(n+1))$
(7)

where $\eta^{(n,n+1)}_{\xi^{\prime}}$ is the configuration $\eta$ with the
pair $(\eta(n),\eta(n+1))$ replaced by $\xi^{\prime}$ and where
$R_{\xi,\xi^{\prime}}$ is the rate that a pair of sites with value $\xi$ jumps
to the value $\xi^{\prime}$. We wish to re-write the infinitesimal generators
of our Markov processes in a convenient form, and adopt some tensor notation
as explained in the next Section, familiar from the study of quantum spin
chains, see e.g. [25] for a review.

###  2.1 Tensor notation

Let $V$ denote a single copy of $\mathbb{R}^{2}$. Let
$(V_{n})_{n\in{\mathbb{Z}}}$ be a collection of copies
$V_{n}\simeq\mathbb{R}^{2}$. Define

$\displaystyle v=\left(\begin{array}[]{c}1\\\
1\end{array}\right)\in\mathbb{R}^{2}.$ (10)

The infinite tensor product $T=\bigotimes_{n\in{\mathbb{Z}}}V_{n}$ is the
linear space spanned by infinite strings $\otimes_{n\times{\mathbb{Z}}}v_{n}$
where $v_{n}\in V_{n}$ and $v_{n}=v$ for all but finitely many values of index
$n\in{\mathbb{Z}}$, modulo the usual equivalence relations:

$\displaystyle\ldots\otimes\alpha a_{m}\otimes\ldots\otimes
b_{n}\otimes\ldots$ $\displaystyle\sim$ $\displaystyle\ldots\otimes
a_{m}\otimes\ldots\otimes\alpha b_{n}\otimes\ldots,\qquad\forall
m,n\in{\mathbb{Z}},\;\alpha\in\mathbb{R},$
$\displaystyle\ldots\otimes(a_{n}+b_{n})\otimes\ldots$ $\displaystyle\sim$
$\displaystyle\ldots\otimes a_{n}\otimes\ldots+\ldots\otimes
b_{n}\otimes\ldots,\qquad\forall n\in{\mathbb{Z}}.$

The infinite-dimensional vector space $T$ is isomorphic to the cylinder
functions $T(\Omega)$. To construct such an isomorphism explicitly, notice
first that the space of functions on $\\{0,1\\}$ is isomorphic to $V$:

$\displaystyle
f=f(1)\,\mathbbm{1}_{1}+f(0)\,\mathbbm{1}_{0}\quad\leftrightarrow\quad\begin{pmatrix}f(1)\\\
f(0)\end{pmatrix}\in V.$

In particular $\mathbbm{1}_{1}\leftrightarrow e^{(1)}:=\begin{pmatrix}1\\\
0\end{pmatrix}$ and $\mathbbm{1}_{0}\leftrightarrow
e^{(0)}:=\begin{pmatrix}0\\\ 1\end{pmatrix}$. If $f\equiv 1$, its image under
the above isomorphism is the vector $v$ defined in (10), which we now call the
vacuum vector.

The space of test functions $T(\Omega)$ is spanned by products of indicator
functions $\prod_{x\in[n,m]}\mathbbm{1}_{\alpha_{x}}(\eta(x))$. The claimed
isomorphism between $T(\Omega)$ and $T$ is then defined via its action on
these spanning elements

$\displaystyle\prod_{x=n}^{m}\mathbbm{1}_{\alpha_{x}}(\eta(x))\quad\leftrightarrow\quad\ldots\otimes\left(\bigotimes_{x=n}^{m}e^{(\alpha_{x})}_{x}\right)\otimes\ldots\qquad\mbox{for
$n\leq m$ and $\alpha_{x}\in\\{0,1\\}$}$ (11)

where
$\ldots\otimes\left(\bigotimes_{x=n}^{m}e^{(\alpha_{x})}_{x}\right)\otimes\ldots$
denotes the vector with $e^{(\alpha_{x})}_{x}$ in position $x$, for all $n\leq
x\leq m$, and $v$ at all other positions. Such vectors span $T$. As an
illustrative example of the isomorphism, the vector $\ldots\otimes
e^{(1)}_{0}\otimes e^{(0)}_{1}\otimes e^{(1)}_{2}\otimes\ldots$ is mapped to
the cylinder function $f(\eta)=\mathbbm{1}(\eta(0)=1,\eta(1)=0,\eta(2)=1)$.

Using the isomorphism (11) we can rewrite the generator (7) as a linear
operator $L$ on the vector space $T$ in the form
$L=\sum_{n\in{\mathbb{Z}}}q_{n}$, where $q_{n}$ is the part of the generator
corresponding to jumps at sites $(n,n+1)$. Namely we write a $4\times 4$
Q-matrix

$q=\begin{pmatrix}\bullet&q_{(11),(10)}&q_{(11),(01)}&q_{(11),(00)}\\\
q_{(10),(11)}&\bullet&q_{(10),(01)}&q_{(10),(00)}\\\
q_{(01),(11)}&q_{(01),(10)}&\bullet&q_{(01),(00)}\\\
q_{(00),(11)}&q_{(00),(10)}&q_{(00),(01)}&\bullet\end{pmatrix}$

where we have written $q$ as the matrix of an operator on $V\otimes V$ in the
basis $(e^{(1)}\otimes e^{(1)},e^{(1)}\otimes e^{(0)},e^{(0)}\otimes
e^{(1)},e^{(0)}\otimes e^{(0)})$. The diagonal elements are chosen in such a
way that all row sums are equal to zero. Then

$L=\sum_{n\in{\mathbb{Z}}}q_{n}$ (12)

where $q_{n}$ is the operator on $T=\bigotimes_{n\in{\mathbb{Z}}}V_{n}$ which
leaves entries $(v_{k}:k<n)$ and $(v_{k}:k>n+1)$ unchanged and acts as $q$ on
the pair $V_{n}\otimes V_{n+1}$.

###  2.2 Annihilating simple random walks

Particles independently perform simple random walks on ${\mathbb{Z}}$, jumping
right with rate $r$ and left with rate $l$, and particles instantaneously
annihilate upon collision. We scale time so that $r+l=1$. The infinitesimal
generator $L$ acting on functions in $T$ can be written using the form (12)
above, with

$q=\begin{pmatrix}-1&0&0&1\\\ 0&-r&r&0\\\ 0&l&-l&0\\\ 0&0&0&0\end{pmatrix}$

For our results it is convenient to write

$\sigma=q+I=\begin{pmatrix}0&0&0&1\\\ 0&l&r&0\\\ 0&l&r&0\\\
0&0&0&1\end{pmatrix}$ (13)

where $I$ is the unit element of $\text{End}(V\otimes V)$. Then the generator
acting on $T$ becomes

$L=\sum_{n\in{\mathbb{Z}}}(\sigma_{n}-I).$ (14)

This trivial change is convenient because the relations satisfied by
$\\{\sigma_{n}\\}$ are in a familiar algebraic form. For example the matrix
$\sigma$ satisfies $\sigma^{2}=\sigma$, as is immediate from (13). A little
harder to check is

$\sigma_{n}\sigma_{n+1}\sigma_{n}-Q\sigma_{n}=\sigma_{n+1}\sigma_{n}\sigma_{n+1}-Q\,\sigma_{n+1},\quad\mbox{for
$n\in{\mathbb{Z}}$,}$ (15)

for the value $Q=rl$. This is an identity in $\mbox{End}(V\otimes V\otimes
V)$, and can be checked slowly by hand using $8\times 8$ matrices, or quickly
by Matlab. This relation is a deformation of the braid relation which,
together with the commutativity relation

$\sigma_{n}\sigma_{m}=\sigma_{m}\sigma_{n}\quad$ when $|n-m|>1$, (16)

and the quadratic relation

$\sigma_{n}^{2}=\sigma_{n},\quad\mbox{for $n\in{\mathbb{Z}}$,}$ (17)

are the defining relations for a Hecke algebra with parameter $Q$ (the
Appendix gives some details of Hecke algebras). Thus, for annihilating simple
random walks, the algebra $\mathbb{A}$ generated by
$\\{\sigma_{n}\\}_{n\in{\mathbb{Z}}}$ over $\mathbb{R}$ in
$\otimes_{i\in{\mathbb{Z}}}V_{i}$ is a quotient of a Hecke algebra with
parameter $Q=rl$. In Section 5.1 we conjecture the exact quotient for the
model on $N$ sites $\\{1,2,\ldots,N\\}$.

We now study some representations of the generator algebra $\mathbb{A}$, which
becomes a surprisingly straightforward task due to the structure of
eigenvectors of $\sigma$. Since $\sigma^{2}=\sigma$ the eigenvalues of
$\sigma$ are either zero or one. The row sums of $\sigma$ are all $1$, and the
therefore one of the eigenvectors with eigenvalue $1$ is

$\begin{pmatrix}1\\\ 1\\\ 1\\\ 1\end{pmatrix}=v\otimes v,$

recalling that $v=(1,1)^{T}$. As $\mbox{rank}(\sigma)=2$, we expect that there
might be a linearly independent eigenvector with eigenvalue $1$. It is
straightforward to check that such an eigenvector for $\sigma$ exists and can
be written in a factorised form $w\otimes w$, where

$w=\begin{pmatrix}-1\\\ 1\end{pmatrix}.$

Another computation shows that

$\sigma v\otimes w=lv\otimes v+rw\otimes w,\qquad\sigma w\otimes v=rv\otimes
v+lw\otimes w.$ (18)

This allows us to extend a representation of $\sigma_{n}$ on $V_{n}\otimes
V_{n+1}$ to a representation of $\mathbb{A}$ on
$\otimes_{n\in{\mathbb{Z}}}V_{n}$ as follows. Concretely, (18) implies that
$\mathbb{A}$ acts on certain subspaces of $\otimes_{n\in{\mathbb{Z}}}V_{n}$
spanned by the tensor product of runs of $w$’s and $v$’s. For example,
consider

$\displaystyle f_{x}=\left(\otimes_{i\leq
x}w_{i}\right)\otimes\left(\otimes_{j>x}v_{j}\right)\in\bigotimes_{n\in{\mathbb{Z}}}V_{n}.$
(19)

(We temporarily ignore that $f_{x}$ is not eventually constant and so not an
element of $T$.) Using (18), together with $\sigma v\otimes v=v\otimes v$ and
$\sigma w\otimes w=w\otimes w$, we see that

$\sigma_{x}f_{x}=rf_{x-1}+lf_{x+1}\quad\mbox{and}\quad\sigma_{y}f_{x}=f_{x}\quad\mbox{for
$y\neq x$.}$

Thus the algebra $\mathbb{A}$ is represented on the subspace
$\mbox{Span}_{\mathbb{R}}(f_{x},x\in{\mathbb{Z}})$. Moreover

$\displaystyle Lf_{x}=rf_{x-1}+lf_{x+1}-f_{x}:=\Delta^{r,l}f_{x},$ (20)

defining $\Delta^{r,l}$ a non-symmetric discrete Laplacian (we write $\Delta$
in the symmetric case $r=l=\frac{1}{2}$).

More generally, let $x_{1}\leq x_{2}\leq x_{3}\leq\ldots\leq x_{2n}$ for
$n\geq 1$ and

$f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}=\ldots\left(\otimes_{x_{1}+1\leq
j_{1}\leq x_{2}}w_{j_{1}}\right)\ldots\left(\otimes_{x_{3}+1\leq j_{2}\leq
x_{4}}w_{j_{2}}\right)\ldots\left(\otimes_{x_{2n-1}+1\leq j_{n}\leq
x_{2n}}w_{j_{n}}\right)\ldots$ (21)

where each $\ldots$ represent tensoring with the vacuum vector $v$ at all
other positions. We also let $f^{(0)}=\otimes_{i\in{\mathbb{Z}}}v_{i}$
(corresponding to the constant function with value $1$). These vectors do lie
in $T$. The action (18) again implies that
$\sigma_{x}f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}$ can be expressed either in
terms of the same type of function $f^{(2n)}$, or it may produce a term where
a run of $w$’s disappears or one where two runs of $w$’s merge, both of which
can be expressed as $f^{(2n-2)}$. For example

$\sigma_{3}f^{(4)}_{1346}=rf^{(4)}_{1246}+lf^{(4)}_{1446}=rf^{(4)}_{1246}+lf^{(2)}_{16}.$

Furthermore

$\displaystyle
Lf^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}=\sum_{k=1}^{2n}\Delta^{r,l}_{k}f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}},x_{1}<x_{2}<\ldots<x_{2n},$
(22) $\displaystyle
f^{(2n)}_{x_{1},\ldots,x_{i}=x_{i+1},\ldots,x_{2n}}=f^{(2n-2)}_{x_{1},\ldots,x_{i-1},x_{i+2},\ldots,x_{2n}},~{}i=1,\ldots,2n-1,$
(23)

where $\Delta^{r,l}_{k}$ is the discrete Laplacian applied to the $k$-th
argument.

From the algebraic point of view, we have constructed a lower triangular
representation of $\mathbb{A}$ in $\otimes_{i\in{\mathbb{Z}}}V_{i}$:

$T_{2n}:=\mbox{Span}_{\mathbb{R}}(f^{(2n)}_{x_{1},x_{2}\ldots
x_{2n}}:x_{1}<x_{2}<\ldots<x_{2n}),\qquad\mathbb{A}T_{2n}\subset T_{2n}\oplus
T_{2n-2}.$

From the probabilistic point of view, (22, 23) mean that $f^{(2n)}$, regarded
as a function on ${\mathbb{Z}}^{2n}\times\Omega$, is a Markov duality
function, and establishes a duality with annihilating random walks in reverse
time started with $2n$ particles. The duality function $f^{(2n)}$ is mapped
under the isomorphism (11) to the well known product spin function

$f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}\quad\leftrightarrow\quad\prod_{1\leq
i\leq
n}(-1)^{\eta(x_{2i-1},x_{2i}]}\quad\mbox{where}\quad\eta(a,b]=\sum_{x=a+1}^{b}\eta(x).$

See [16] for the use of these duality functions, where the lower-triangular
system of differential equations for
$\Phi^{(n)}(x_{1},\ldots,x_{2n}):={\mathbb{E}}[f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}(\eta_{t})]$
arising from the generator action in (22, 23) is solved, for deterministic
initial conditions, using Pfaffians, and the resulting formulae are shown to
characterise the distribution of $\eta_{t}$, for any fixed $t>0$, as a
Pfaffian point process on ${\mathbb{Z}}$.

We call a duality function in the form (21) an alternating interval duality
function. The key facts that allowed it to work were (i) the existence of a
second factorised eigenvector $w\otimes w$ and (ii) the fact that in the
action (18) of $\sigma$, the right hand side of $\sigma v\otimes w$
(respectively of $\sigma w\otimes v$) does not contain a term proportional to
$w\otimes v$ (respectively $v\otimes w$). We show in Section 2.4 below that
the second fact is sometimes a consequence of the braid relation in a Hecke
algebra.

###  2.3 Asymmetric simple exclusion process

In this process, particles jump to the right at rate $r$, or left at rate $l$,
but the jump is suppressed unless the jump is onto an unoccupied site. We
suppose $r+l=1$, and also that $r>l$. The generator $L$ on $T$ is still in the
form (14) with

$\displaystyle\sigma=\begin{pmatrix}1&0&0&0\\\ 0&l&r&0\\\ 0&l&r&0\\\
0&0&0&1\end{pmatrix}.$ (24)

Again it is possible to check that the operators $\\{\sigma_{n}\\}$ satisfy
the three relations (15), (16) and (17) of a Hecke algebra. Indeed the
relations of the Temperly-Lieb algebra are satisfied (which imply the Hecke
relations) namely

$\sigma_{n}\sigma_{n+1}\sigma_{n}-rl\,\sigma_{n}\;=0=\;\sigma_{n+1}\sigma_{n}\sigma_{n+1}-rl\,\sigma_{n+1},\quad\mbox{for
$n\in{\mathbb{Z}}$.}$ (25)

We can again use the eigenvalues of $\sigma$ to understand the known Markov
duality functions. It is easy to check that $\sigma w\otimes w=w\otimes w$ for
any $w\in V$. In other words, any tensor square of a non-zero two-dimensional
vector is an eigenvector of $\sigma$ with eigenvalue $1$. This is to be
contrasted with the case of annilating random walks, where the requirement
that $w\otimes w$ is an eigenvector with eigenvalue one essentially fixes a
single $w$ that is independent of $v$. However we aim to choose $w$ from the
requirement that $\sigma$ has a good action on $v\otimes w$ in the sense that

$\displaystyle\sigma v\otimes w=\alpha v\otimes v+\beta w\otimes w+\gamma
v\otimes w.$ (26)

There are no non-zero solutions with $w_{2}=0$. Therefore, we can search for
the answer in the form $w=(q,1)^{T}$, $q\neq 1$. The only solution to (26) for
such an Ansatz is

$\displaystyle q=\frac{l}{r},~{}\alpha=l,~{}\beta=r,\gamma=0.$ (27)

In contrast to the annihilating random walk example, $\sigma w\otimes v$
cannot then be expressed in terms of $v\otimes v$, $w\otimes w$ and $w\otimes
v$ only, so the representations of the algebra $\mathbb{A}$ generated by
$\\{\sigma_{n}\\}$ has to be constructed differently.

Fortunately, there is an additional algebraic structure, which comes to the
rescue. For any $a=(a_{1},a_{2})^{T},b=(b_{1},b_{2})^{T}\in V$, we use the
linear operation of pointwise multiplication (the Hadamard product), which
corresponds to the multiplication of functions on $\Omega$:

$\displaystyle a\cdot b:=\left(\begin{array}[]{c}a_{1}b_{1}\\\
a_{2}b_{2}\end{array}\right)\in V$ (30)

and where powers are defined by $a^{k}=a\cdot a\cdots a$. Similarly, for
$\otimes_{n\in{\mathbb{Z}}}a_{n},\otimes_{n\in{\mathbb{Z}}}b_{n}\in\otimes_{n\in
Z}V$, we define
$\otimes_{n\in{\mathbb{Z}}}a_{n}\cdot\otimes_{n\in{\mathbb{Z}}}b_{n}:=\otimes_{n\in{\mathbb{Z}}}(a_{n}\cdot
b_{n})$. The key facts we need concerning $\sigma$, $v$ and $w$, alongside
$\sigma v\otimes v=v\otimes v$ and $\sigma w\otimes w=w\otimes w$, are

$\displaystyle\sigma w^{n}\otimes w^{n+1}$ $\displaystyle=$ $\displaystyle
lw^{n}\otimes w^{n}+rw^{n+1}\otimes w^{n+1},\quad n\geq 0,$ (31)
$\displaystyle 0$ $\displaystyle=$ $\displaystyle
rw^{n+2}-w^{n+1}+lw^{n},\quad n\geq 0,$ (32)

the latter arising from the relation $rq^{2}-q+l=(rq-l)(q-1)=0$. Now we define

$\displaystyle h_{x}$ $\displaystyle=$ $\displaystyle\ldots\otimes
v_{x-2}\otimes v_{x-1}\otimes w_{x}\otimes w_{x+1}\otimes\ldots\quad\mbox{for
$x\in{\mathbb{Z}}$}$ (33) $\displaystyle h^{(n)}_{x_{1},\ldots,x_{n}}$
$\displaystyle=$ $\displaystyle h_{x_{1}}\cdot\ldots\cdot
h_{x_{n}}\quad\mbox{for $x_{1}\leq x_{2}\leq\ldots\leq x_{n}$.}$ (34)

We check below that the action in (31) implies that these are duality
functions, and we call $h^{(n)}_{x_{1},\ldots,x_{n}}$ a staircase duality
function. The corresponding functions on the configuration space are
$q^{\eta[x,\infty)}=q^{\sum_{y\geq x}\eta(y)}$ and products
$\prod_{i}q^{\eta[x_{i},\infty)}$, which are the duality functions developed
in Schutz [39]. Alas, these functions do not depend on finitely many co-
ordinates, and the vector $h_{x}$ does not lie in our tensor space
$T=\bigotimes_{n\in{\mathbb{Z}}}V_{n}$. To bypass this difficulty, we follow
[39] by restricting to configurations $\eta$ that have a rightmost particle.
Just for this Section we adopt a different definition of the infinite tensor
product. Let $\Omega^{\prime}$ be a reduced configuration space containing
only configurations with a rightmost particle: $\eta\in\Omega^{\prime}$ if
there is $j_{0}\in{\mathbb{Z}}:$ $\eta=((\eta_{j})_{j\leq j_{0}},0,0,\ldots)$.
Next, let $T(\Omega^{\prime})$ be the space of functions on $\Omega^{\prime}$
depending on semi-infinite strings of arguments, that is $f\in
T(\Omega^{\prime})$ if there is $i_{0}\in{\mathbb{Z}}$ such that $f$ depends
on $(\eta_{i})_{i\geq i_{0}}$ only. The action of the generator is well-
defined on $T(\Omega^{\prime})$: for any $\eta\in\Omega^{\prime}$ and $f\in
T(\Omega^{\prime})$

$Lf(\eta)=\sum_{k=i_{0}-1}^{j_{0}}(q_{k}f)(\eta).$

To model $T(\Omega^{\prime})$ using vector notation, we adapt the definition
of the infinite tensor product to let $T^{\prime}$ be the linear space spanned
by infinite strings $\otimes_{n\times{\mathbb{Z}}}\,v_{n}$, where $v_{n}\in
V_{n}$, for which there exists $i_{0}$ so that $v_{n}=v$ for all $n<i_{0}$
(modulo the usual equivalence relations). As before, the linear spaces
$T(\Omega^{\prime})$ and $T^{\prime}$ are isomorphic.

Using (31), we can check that the algebra $\mathbb{A}$ generated by
$\\{\sigma_{n}\\}$ is represented in each of the spaces

$\displaystyle
T_{n}^{\prime}=\text{Span}_{\mathbb{R}}\left(h^{(n)}_{x_{1},\ldots,x_{n}},\;x_{1}\leq
x_{2}\leq\ldots\leq x_{n}\right)\subset T^{\prime},\quad\mbox{for
$n=0,1,\ldots.$}$ (35)

Indeed it follows from (31) and $\sigma w^{n}\otimes w^{n}=w^{n}\otimes w^{n}$
that for $x_{1}<x_{2}<\ldots<x_{n}$,

$\displaystyle\sigma_{x_{i}}h^{(n)}_{x_{1},\ldots,x_{n}}$ $\displaystyle=$
$\displaystyle
h_{x_{1}}\cdot\ldots\left(lh_{x_{i}+1}+rh_{x_{i}-1}\right)\ldots\cdot
h_{x_{n}}\quad\mbox{for $1\leq i\leq n,$}$ (36)
$\displaystyle\sigma_{k}h^{(n)}_{x_{1},\ldots,x_{n}}$ $\displaystyle=$
$\displaystyle h^{(n)}_{x_{1},\ldots,x_{n}}\quad\mbox{for
$k\not\in\\{x_{1},x_{2},\ldots,x_{n}\\}.$}$ (37)

It remains to check that $\mathbb{A}$ maps $h_{x_{1},\ldots,x_{n}}$ to an
element of $T_{n}^{\prime}$ if $x_{i}$’s are allowed to coincide. Such a check
is elementary using the relation

$\displaystyle\sigma(w^{n}\otimes
w^{n+m})=\frac{q^{2}-q^{m}}{q^{2}-1}w^{n}\otimes
w^{n}+\frac{q^{m}-1}{q^{2}-1}w^{n+1}\otimes w^{n+1},~{}m,n\geq 0$ (38)

which is proved using (31) and the identity
$w^{m}=\frac{q-q^{m}}{q-1}v+\frac{q^{n}-1}{q-1}w$.

From the probabilistic point of view, we must examine the action of the entire
generator:

$\displaystyle
Lh^{(n)}_{x_{1},\ldots,x_{n}}=\sum_{k=1}^{n}\Delta^{r,l}_{k}h^{(n)}_{x_{1},\ldots,x_{n}},\quad
x_{1}<x_{2}<\ldots<x_{2n},$ (39) $\displaystyle
rh^{(n)}\mid_{x_{i}=x,x_{i+1}=x}+lh^{(n)}\mid_{x_{i}=x+1,x_{i+1}=x+1}-h^{(n)}_{x_{i}=x,x_{i+1}=x+1}=0,$
$\displaystyle 1\leq i<n.$ (40)

The operator on the right hand side of (39) is the generator of [ASEP] with
$n$ particles in the co-ordinate representation. Notice that the knowledge of
all
$\Phi^{(n)}_{t}(x_{1},\ldots,x_{n}):={\mathbb{E}}(h^{(n)}_{x_{1},\ldots,x_{n}})$
for $n\geq 0$ determines the law of [ASEP] at time $t$, showing the system of
duality functions constructed above is complete. The solution of the system
for $\Phi^{(n)}_{t}(x_{1},\ldots,x_{n})$ in Borodin, Corwin and Sasamoto [7]
leads eventually to Tracy-Widom distribution fluctuations for [ASEP].

###  2.4 The Hecke relations and duality

Another commonly arising type of duality function is of the form

$\ldots\otimes w_{x_{1}}\otimes\ldots\otimes w_{x_{n}}\otimes\ldots$ (41)

where the vector $w$ is in positions $x_{1},x_{2},\ldots,x_{n}$ and each
$\ldots$ represent tensoring with the vacuum vector $v$ at all other
positions. When $w=e^{(1)}$ this corresponds to the product moment duality
function:

$g^{(n)}_{x_{1},x_{2},\ldots,x_{n}}=\ldots\otimes
e^{(1)}_{x_{1}}\otimes\ldots\otimes
e^{(1)}_{x_{n}}\otimes\ldots\quad\leftrightarrow\quad\prod_{1\leq i\leq
n}\eta(x_{i}),$ (42)

and when $w=(\beta,1)^{T}$ for some $\beta\neq 1$ this corresponds to the
exponential product moment duality function:

$g^{(n)}_{\beta;x_{1},x_{2},\ldots,x_{n}}=\ldots\otimes
w_{x_{1}}\otimes\ldots\otimes
w_{x_{n}}\otimes\ldots\quad\leftrightarrow\quad\beta^{\sum_{i=1}^{n}\eta(x_{i})}.$
(43)

We call the number $n$ of non vacuum entries the order of the product moment.
These are well known duality functions for the symmetric exclusion process and
certain voter models (see Section 4). The key relation that needs to hold for
these to be duality functions is that $\sigma v\otimes w$ and $\sigma w\otimes
v$ can be expressed in terms of $v\otimes v,v\otimes w,w\otimes v$, that is
without using $w\otimes w$. This ensures that $\sigma_{y}$ can only reduce the
number of sites in a product moment. This leads, as in the two example above,
to invariant subspaces for the generator algebra, which here consist of
product moments of at most a given order.

Our aim in this paper is to examine whether there are underlying algebraic
facts that lead to the emergence of the duality functions we have seen above.
The braid relation (15) emerges as a surprise in the two models described
above. The following proposition shows that, when present together with two
factorised form eigenvectors, the Hecke relations imply that the generator
will act in a suitable way to construct duality functions.

######  Proposition 1.

Suppose that $\\{\sigma_{n}\\}_{n\in{\mathbb{Z}}}$, where $\sigma_{n}$ is a
linear operator $\sigma\in\text{End}(V\otimes V)$ acting on entries
$V_{n}\times V_{n+1}$ in the space $\otimes_{n\in Z}V$, satisfy the deformed
braid and quadratic Hecke relations (15) and (17). Suppose also that
$\dim\ker(\sigma-I)=2$ and that there are two independent factorised form
eigenvectors $\sigma v\otimes v=v\otimes v$ and $\sigma w\otimes w=w\otimes
w$.

Then the action of $\sigma$ on $v\otimes w$ and $w\otimes v$ must take one of
the following two forms:

$\displaystyle\left\\{\begin{array}[]{c}\sigma v\otimes w=\alpha v\otimes
v+\beta w\otimes w+\gamma v\otimes w,\\\ \sigma w\otimes
v=\tilde{\alpha}w\otimes w+\tilde{\beta}v\otimes v+\tilde{\gamma}w\otimes
v,\end{array}\right.$ (46)

or

$\displaystyle\left\\{\begin{array}[]{c}\sigma v\otimes w=\gamma v\otimes
w+\delta w\otimes v,\\\ \sigma w\otimes v=\tilde{\gamma}w\otimes
v+\tilde{\delta}v\otimes w,\end{array}\right.$ (49)

for some
$\alpha,\beta,\gamma,\delta,\tilde{\alpha},\tilde{\beta},\tilde{\gamma},\tilde{\delta}\in\mathbb{R}$.

The form (46) is consistent with alternating interval duality functions, and
the form (46) is consistent with product moment duality functions.

###### Proof.

For this proof, the argument is easier using the Q-matrix form, that is
$q=\sigma-I$. A short computation shows that the Hecke relations (15) and (17)
become

$\displaystyle q_{i}q_{i+1}q_{i}-(Q+1)q_{i}$ $\displaystyle=$ $\displaystyle
q_{i+1}q_{i}q_{i+1}-(Q+1)q_{i+1},$ $\displaystyle q_{i}^{2}$ $\displaystyle=$
$\displaystyle-q_{i},\quad i\in{\mathbb{Z}}.$

Expressed in terms of $\\{q_{i}\\}$ our assumptions mean that $qv\otimes
v=qw\otimes w=0$ and $\dim\ker(q)=2$.

The conclusion will follow after analysing the action of $L_{1}:=q\otimes Id$
and $L_{2}=Id\otimes q$ on the vectors $v\otimes w\otimes w,v\otimes v\otimes
w\in V_{1}\otimes V_{2}\otimes V_{3}$. By definition $L_{1}:=L\otimes Id$ and
$L_{2}=Id\otimes L$ act non-trivially on $V_{1}\otimes V_{2}$ and
$V_{2}\otimes V_{3}$ respectively. Applying the deformed braid relation one
finds

$\displaystyle\left\\{\begin{array}[]{ccc}L_{1}L_{2}L_{1}v\otimes w\otimes
w&=&(Q+1)\,L_{1}v\otimes w\otimes w\\\ L_{2}L_{1}L_{2}v\otimes v\otimes
w&=&(Q+1)\,L_{2}v\otimes v\otimes w\end{array}\right..$ (52)

As $\\{v\otimes v,w\otimes w,v\otimes w,w\otimes v\\}$ is a basis of $V\otimes
V$, there are $\alpha,\beta,\gamma,\delta$ such that

$\displaystyle Lv\otimes w=\alpha v\otimes v+\beta w\otimes w+\gamma v\otimes
w+\delta w\otimes v$ (53)

Substituting (53) into (52) and observing that $a\otimes v+b\otimes w=0$
implies $a=b=0$, one finds

$\displaystyle\left\\{\begin{array}[]{c}\alpha\delta q\left(v\otimes
w+w\otimes v\right)=0,\\\ \beta\delta q\left(v\otimes w+w\otimes
v\right)=0.\end{array}\right.$ (56)

Notice that the vectors $v\otimes v$, $w\otimes w$ and $v\otimes w+w\otimes v$
are linearly independent. As $qv\otimes v=qw\otimes w=0$ and
$\text{null}(q)=2$, we conclude that $\delta=0$ or $\alpha=\beta=0$. Repeating
the argument for $qw\otimes v$ we arrive at the following possibilities

$\displaystyle\left\\{\begin{array}[]{c}qv\otimes w=\alpha v\otimes v+\beta
w\otimes w+\gamma v\otimes w\\\ OR\\\ qv\otimes w=\gamma v\otimes w+\delta
w\otimes
v,\end{array}\right.\mbox{and}\quad\left\\{\begin{array}[]{c}qw\otimes
v=\tilde{\alpha}w\otimes w+\tilde{\beta}v\otimes v+\tilde{\gamma}w\otimes v\\\
OR\\\ qw\otimes v=\tilde{\gamma}w\otimes v+\tilde{\delta}v\otimes
w.\end{array}\right.$ (63)

The four possible actions described here can be reduced to just the two stated
in the proposition. Indeed, assume that

$\displaystyle qv\otimes w=\gamma v\otimes w+\delta w\otimes v,$ (64)

but

$\displaystyle qw\otimes v=\tilde{\alpha}w\otimes w+\tilde{\beta}v\otimes
v+\tilde{\gamma}w\otimes v.$ (65)

Applying $q$ to (64) and using the relation $q^{2}=-q$ and (65), one finds

$\displaystyle-\gamma v\otimes w-\delta w\otimes v=\gamma(\gamma v\otimes
w+\delta w\otimes v)+\delta(\tilde{\alpha}w\otimes w+\tilde{\beta}v\otimes
v+\tilde{\gamma}w\otimes v).$

It then follows from linear independence that either $\delta=0$ or
$\tilde{\alpha}=\tilde{\beta}=0$. In the former case (64), (65) become a
particular case of (46), in the latter of (49). ∎

Let us notice that the proposition is applicable to [ARW] as well as all other
reaction-diffusion systems considered below: for all these cases the non-
degeneracy condition $\dim\ker(\sigma-I)=2$ is satisfied and the corresponding
pair of factorised null vectors of $\sigma-I$ exists. For the reaction-
diffusion systems the alternative (46) is realised, which allows one to
construct a full system of the alternating interval duality functions, see
Section 2.2 for the example of annihilating random walks. The alternative (49)
corresponds to duality functions of the product moment type. It is well known
that products of particle indicators constitute a full system of duality
functions for the symmetric simple exclusion process ([SEP]). However notice
that the non-degeneracy condition is not satisfied for [SEP] as
$\dim\ker(\sigma-I)=1$.

The above proposition motivates a systematic search for operators $\sigma$ for
which the family $\\{\sigma_{n}\\}$ satisfy the Hecke algebra relations
(15),(17), and which have the constraints that allow $\sum_{n}(\sigma_{n}-I)$
to act as the generator of a particle system on ${\mathbb{Z}}$: that the off
diagonal entries of $\sigma$ are non-negative and that row sums equal $1$. As
an example, there is exactly one family of such operators which have rank $1$,
namely:

$\sigma=\begin{pmatrix}t^{2}&t(1-t)&t(1-t)&(1-t)^{2}\\\
t^{2}&t(1-t)&t(1-t)&(1-t)^{2}\\\ t^{2}&t(1-t)&t(1-t)&(1-t)^{2}\\\
t^{2}&t(1-t)&t(1-t)&(1-t)^{2}\\\ \end{pmatrix}\qquad\mbox{for $t\in[0,1]$}.$
(66)

which satisfies the braid relation (15) with $Q=0$. To prove this is the only
rank $1$ solution we may set $\sigma=(1,1,1,1)^{T}(a_{1},a_{2},a_{3},a_{4})$
since we know that its image must contain the eigenvector $(1,1,1,1)^{T}$. We
require $a_{1}+a_{2}+a_{3}+a_{4}=1$ and $a_{i}\geq 0$ for $i=1,..,4$. This
already ensures that $\sigma^{2}=\sigma$. Substituting this form into the
deformed braid relation (15) we find, using a symbolic algebra package, that
it can only hold for the family above. More details are given at the start of
Section 6.

A full search for all examples is still unfinished. The results in Section 3
give a partial classification, based on adding certain extra requirements, of
the set of rank $2$ and rank $3$ examples. We find exactly 11 families, among
them many familiar models and just a few new ones, such as (66). The particle
system corresponding to (66) we call a reshuffle model, as pairs of
neighbouring sites update their values at rate one, becoming $11$, $10$, $01$,
$00$ with fixed probabilities independent of their previous values. We study
this model in Section 4.6 where we show that its invariant measure is a
determinantal point process on ${\mathbb{Z}}$ related to the descent process
introduced by Borodin, Diaconis and Fulman in [8].

##  3 Classifications of generators

###  3.1 Generators built out of projectors

We will make two reductions in our first classification.

Reflective symmetry. Let $\rho\in\text{End}(V\otimes V)$ be defined by
$\rho(a\otimes b)=b\otimes a$, so that in the standard basis $\rho$ is given
by

$\displaystyle\rho=\begin{pmatrix}1&0&0&0\\\ 0&0&1&0\\\ 0&1&0&0\\\
0&0&0&1\end{pmatrix}.$ (67)

If a generator of a Markov process is of the form (14) and satisfies
$\rho\sigma=\sigma\rho$ then the reflected Markov chain $(\tilde{\eta}_{t})$,
defined by $\tilde{\eta}_{t}(x)=\eta_{t}(-x)$ for $x\in{\mathbb{Z}}$, has the
same law as $(\eta_{t})$.

Particle-hole interchange. The map $\eta_{x}\to 1-\eta_{x}$ for
$x\in{\mathbb{Z}}$ interchanges occupied and empty sites. For a Markov process
of the form (14) the induced Markov chain after this map is of the same form
but with $\sigma$ replaced by the conjugation $\tilde{\sigma}=\tau\sigma\tau$
where $\tau\in\text{End}(V\otimes V)$ is given in the standard basis by

$\displaystyle\tau=\begin{pmatrix}0&0&0&1\\\ 0&0&1&0\\\ 0&1&0&0\\\
1&0&0&0\end{pmatrix}.$ (68)

We note that $\rho^{2}=I$, $\tau^{2}=I$ and $\rho\tau=\tau\rho$.

######  Theorem 2.

Suppose $\sigma\in\text{End}(V\otimes V)$ is idempotent, that is
$\sigma^{2}=\sigma$, and satisfies the stochastic constraints, that is its
matrix in the standard basis satisfies

$\sigma_{ij}\geq 0$ for $1\leq i\neq j\leq 4$, and
$\sum_{j=1}^{4}\sigma_{ij}=1$ for $1\leq i\leq 4$. (69)

Assume also the reflective symmetry condition $\rho\sigma=\sigma\rho$. Then
any such non-trivial $\sigma\neq I$ must, after possibly a particle-hole
conjugation $\tau\sigma\tau$, lie in one of following nine families (written
in the standard basis)

$\displaystyle\begin{array}[]{c}\mbox{Symmetric exclusion process}\\\
\mbox{[SEP]}\end{array}\quad$ $\displaystyle\sigma=\begin{pmatrix}1&0&0&0\\\
0&\frac{1}{2}&\frac{1}{2}&0\\\ 0&\frac{1}{2}&\frac{1}{2}&0\\\
0&0&0&1\end{pmatrix}$ (72) $\displaystyle\begin{array}[]{c}\mbox{Biased voter
model}\\\ \mbox{[BVM]}\end{array}\quad$
$\displaystyle\sigma=\begin{pmatrix}1&0&0&0\\\ \theta&0&0&1-\theta\\\
\theta&0&0&1-\theta\\\ 0&0&0&1\end{pmatrix}$ for $\theta\in[0,1]$, (75)
$\displaystyle\begin{array}[]{c}\mbox{Symmetric anti-voter model}\\\
\mbox{[SAVM]}\end{array}\quad$
$\displaystyle\sigma=\begin{pmatrix}0&\frac{1}{2}&\frac{1}{2}&0\\\ 0&1&0&0\\\
0&0&1&0\\\ 0&\frac{1}{2}&\frac{1}{2}&0\end{pmatrix}$ (78)
$\displaystyle\begin{array}[]{c}\mbox{Annihilating-coalesing}\\\
\mbox{symmetric random walks}\\\ \mbox{[ACSRW]}\end{array}\quad$
$\displaystyle\sigma=\begin{pmatrix}0&\frac{1-\theta}{2}&\frac{1-\theta}{2}&\theta\\\
0&\frac{1}{2}&\frac{1}{2}&0\\\ 0&\frac{1}{2}&\frac{1}{2}&0\\\
0&0&0&1\end{pmatrix}$ for $\theta\in[0,1]$, (82)
$\displaystyle\begin{array}[]{c}\mbox{Coalesing symmetric random}\\\
\mbox{walks with branching}\\\ \mbox{[CSRWB]}\end{array}\quad$
$\displaystyle\sigma=\begin{pmatrix}1-2\theta&\theta&\theta&0\\\
1-2\theta&\theta&\theta&0\\\ 1-2\theta&\theta&\theta&0\\\
0&0&0&1\end{pmatrix}$ for $\theta\in[0,\frac{1}{2}]$, (86)
$\displaystyle\begin{array}[]{c}\mbox{Annihilating symmetric random}\\\
\mbox{walks with pair immigration}\\\ \mbox{[ASRWPI]}\end{array}\quad$
$\displaystyle\sigma=\begin{pmatrix}\frac{1}{2}-\theta&0&0&\frac{1}{2}+\theta\\\
0&\frac{1}{2}&\frac{1}{2}&0\\\ 0&\frac{1}{2}&\frac{1}{2}&0\\\
\frac{1}{2}-\theta&0&0&\frac{1}{2}+\theta\end{pmatrix}$ for
$\theta\in[0,\frac{1}{2}]$, (90)
$\displaystyle\begin{array}[]{c}\mbox{Stationary coalescence}\\\
\mbox{annihilation model}\\\ \mbox{[SCAM]}\end{array}\quad$
$\displaystyle\sigma=\begin{pmatrix}0&\theta&\theta&1-2\theta\\\ 0&1&0&0\\\
0&0&1&0\\\ 0&0&0&1\end{pmatrix}$ for $\theta\in[0,\frac{1}{2}]$, (94)
$\displaystyle\begin{array}[]{c}\mbox{Dimer model}\\\
\mbox{[DM]}\end{array}\quad$
$\displaystyle\sigma=\begin{pmatrix}1-\theta&0&0&\theta\\\ 0&1&0&0\\\
0&0&1&0\\\ 1-\theta&0&0&\theta\end{pmatrix}$ for $\theta\in[0,1]$, (97)
$\displaystyle\begin{array}[]{c}\mbox{Reshuffle model}\\\
\mbox{[RM]}\end{array}\quad$
$\displaystyle\sigma=\begin{pmatrix}\theta_{1}&\theta_{2}&\theta_{2}&\theta_{3}\\\
\theta_{1}&\theta_{2}&\theta_{2}&\theta_{3}\\\
\theta_{1}&\theta_{2}&\theta_{2}&\theta_{3}\\\
\theta_{1}&\theta_{2}&\theta_{2}&\theta_{3}\end{pmatrix}$
$\displaystyle\begin{array}[]{l}\mbox{for $\theta_{i}\geq 0$ and with }\\\
\mbox{$\theta_{1}+2\theta_{2}+\theta_{3}=1$.}\end{array}$ (102)

There are certain obvious redundancies in this listing: for example under
particle-hole conjugation the models [BVM], [DM] and [RM] change their
parameter values. There are certain less obvious overlaps in this listing: for
example the model [BVM] at $\theta=1$ equals [CSRWB] at $\theta=0$, and the
model [SCAM] at $\theta=0$ equals [DM] at $\theta=1$.

We use the above operators to form an algebra $\mathbb{A}$ generated by
$\\{\sigma_{n}\\}_{n\in{\mathbb{Z}}}$ over $\mathbb{R}$ in
$\otimes_{i\in{\mathbb{Z}}}V_{i}$ as in Section 2.2. We can now check for
which of the models in the classification the three conditions for a Hecke
algebra are satisfied, which here reduces to checking the deformed braid
relation (15).

######  Lemma 3.

The algebras corresponding to the models [SEP], [SAVM] and [ACSRW], defined in
(72), (78), and (82), satisfy the deformed braid relation (15) with parameter
$Q=1/4$.

The algebra corresponding to [BVM] (75) satisfies the deformed braid relation
with parameter $Q=\theta(1-\theta)$; that corresponding to [CSRWB] (86) with
parameter $Q=\theta(1-\theta)$; that corresponding to [ASRWPI] (90) with
parameter $Q=\theta^{2}$.

The remaining three models [SCAM], [DM], [RM] do not generically satisfy the
deformed braid relation, but at some exceptional values do so: namely [DM]
(97) at $\theta=1/2$ with parameter $Q=1/4$ and [RM] (102) when
$\theta_{1}=t^{2},\theta_{2}=t(1-t),\theta_{3}=(1-t)^{2}$ for $t\in[0,1]$ with
parameter $Q=0$.

The verification of Lemma 3 is a computation best carried out using a symbolic
linear algebra package.

The proof of the classification Theorem 2 is elementary linear algebra, meshed
with the stochasticity conditions, but is somewhat lengthy. The approach,
motivated by the treatment of annihilating random walks and the asymmetric
exclusion process in the introduction, is to look for eigenvectors of $\sigma$
that are in the factorised form $w\otimes w$ for some $w\in V$. The aim is to
find two such independent vectors, recalling that $v\otimes v=(1,1,1,1)^{T}$
is always one such vector. The first lemma below identifies exactly when this
is possible and the second lemma records an exact form for the second
factorised eigenvector, when it can be found, and the corresponding action of
$\sigma$ on $v\otimes w$ and $w\otimes v$ (which will be useful in describing
duality functions). Luckily, the search described in these two lemmas also
characterises all possibilities for $\sigma$, and Theorem 2 follows directly.
The lemmas are proved in Section 6.

######  Lemma 4.

Let $\sigma\in End(V\otimes V)$ be a stochastic matrix such that
$\sigma^{2}=\sigma$ and $\rho\sigma=\sigma\rho$. Then either

(i) there exists $w\in V$ such that $v=(1,1)^{T}$ and $w$ are linearly
independent and $\sigma w\otimes w=w\otimes w$, or

(ii) $\sigma$ is one of the following three models: the symmetric anti-voter
model [SAVM], the symmetric case $\theta=\frac{1}{2}$ of the biased voter
model [BVM], or the reshuffle model [RM] described in (78, 75, 102).

######  Lemma 5.

Let $\sigma\in End(V\otimes V)$ be a stochastic matrix such that
$\sigma^{2}=\sigma$ and $\rho\sigma=\sigma\rho$. Assume also that there is an
element $w\in V$, independent of $v=(1,1)^{T}$, such that $\sigma w\otimes
w=w\otimes w$. Then, after possibly a particle-hole conjugation, there are
exactly seven such non-trivial matrices $\sigma\neq I$ as listed below, where
we indicate one possible choice of the vector $w$, and the action of $\sigma$
on $v\otimes w$ and $w\otimes v$.

  1. [SEP] Symmetric exclusion process:

$\displaystyle w=\begin{pmatrix}1\\\
\omega\end{pmatrix}\;\mbox{with}\;\;\omega\neq 1,\mbox{ or
}w=\begin{pmatrix}0\\\ 1\end{pmatrix},\qquad\sigma v\otimes w=\sigma w\otimes
v=\frac{1}{2}(v\otimes w+w\otimes v).$

  2. [BVM] The non-symmetric case $\theta\neq\frac{1}{2}$ of the biased voter model:

$\displaystyle w=\begin{pmatrix}1-\theta\\\ \theta\end{pmatrix},\qquad\sigma
v\otimes w=\sigma w\otimes v=\theta(1-\theta)v\otimes v+w\otimes w.$

  3. [ACSRW] Symmetric annihilating-coalescing random walks:

$\displaystyle w=\begin{pmatrix}-\theta\\\ 1\end{pmatrix},\qquad\sigma
v\otimes w=\sigma w\otimes v=\frac{1}{2}v\otimes v+\frac{1}{2}w\otimes w.$

  4. [CSRWB] Symmetric coalescing random walks with branching:

$\displaystyle w=\begin{pmatrix}0\\\ 1\end{pmatrix},\qquad\sigma v\otimes
w=\sigma w\otimes v=\theta v\otimes v+(1-\theta)w\otimes w.$

  5. [ASRWPI] Symmetric annihilating random walks with pairwise immigration:

$\displaystyle w=\begin{pmatrix}-1\\\ 1\end{pmatrix},\qquad\sigma v\otimes
w=\sigma w\otimes v=\theta v\otimes v+\theta w\otimes w.$

  6. [SCAM] Stationary annihilation coalescence model:

$\displaystyle w=\begin{pmatrix}2\theta-1\\\ 1\end{pmatrix},\qquad\sigma
v\otimes w=\frac{1}{2}\left(v\otimes v+w\otimes w\right)+\frac{1}{2}(v\otimes
w-w\otimes v),$ $\displaystyle\sigma w\otimes v=\frac{1}{2}\left(v\otimes
v+w\otimes w\right)+\frac{1}{2}(w\otimes v-v\otimes w).$

  7. [DM] Dimer model::

$\displaystyle w=\begin{pmatrix}1\\\ -1\end{pmatrix},\qquad\sigma v\otimes
w=\frac{1-2\theta}{2}\left(v\otimes v+w\otimes w\right)+\frac{1}{2}(v\otimes
w-w\otimes v),$ $\displaystyle\sigma w\otimes
v=\frac{1-2\theta}{2}\left(v\otimes v+w\otimes w\right)+\frac{1}{2}(w\otimes
v-v\otimes w).$

###  3.2 Generators built using the braid relation

One drawback of Theorem 2 is that we imposed the symmetry condition
$\rho\sigma=\sigma\rho$. More work is needed to complete a classification
without this assumption, and we know we will find non-symmetric versions of
the models in Theorem 2 but do not know if other models will emerge. In this
Section we give a partial answer by establishing a second classification
without the symmetry assumption. instead we ask that the deformed braid
relation (15) holds (and also a further constraint detailed below that makes
the classification tractable). The outcome of the search is that we do indeed
get non-symmetric versions of all the models, and two further exceptional
models, which we call Erosion Models and are easy to analyse (see 4.7).

We were not able to classify all the examples of $\sigma$ satisfying the
deformed braid relation (15) and the quadratic relation (17). Instead we have
analyzed two Ansatzes for $\sigma$ which do give rise to physically
interesting solutions. We choose $\sigma$ in one of the following forms:

$\mbox{(a)}\quad\sigma=\begin{pmatrix}*&*&*&*\\\ *&*&*&*\\\ *&*&*&*\\\
*&0&0&*\end{pmatrix}\qquad\mbox{ (b)}\quad\sigma=\begin{pmatrix}*&*&*&*\\\
*&*&*&0\\\ *&*&*&0\\\ *&*&*&*\end{pmatrix}$ (103)

were symbol ”$*$” denotes components of $\sigma$ which are not restricted by
the Ansatz. Substituting the Ansatzes (103) into the Hecke relations we notice
that certain components of these matrix polynomial equations assume a
factorised form. The factorisation allows us to find more and more
constraints, and to eventually classify all models fitting the Ansatzes.

######  Theorem 6.

Suppose $\sigma\in\text{End}(V\otimes V)$ satisfies the stochastic constraints
(69) and also one of the two Anzatses (103). Suppose that the family
$\\{\sigma_{n}\\}$ satisfy the deformed braid relation (15) and the quadratic
relation (17). Then, after possibly a conjugation to $\rho\sigma\rho$ or
$\tau\sigma\tau$ or $\rho\tau\sigma\tau\rho$, any non-trivial $\sigma\neq I$
must lie in one of the following eleven families (written in the standard
basis):

$\displaystyle\begin{array}[]{c}\mbox{Asymmetric exclusion process}\\\
\mbox{[ASEP]}\end{array}\quad$ $\displaystyle\sigma=\begin{pmatrix}1&0&0&0\\\
0&l&r&0\\\ 0&l&r&0\\\ 0&0&0&1\end{pmatrix}$
$\displaystyle\quad\begin{array}[]{c}\mbox{for $r,l\in[0,1]$,}\\\
\mbox{$r+l=1$,}\end{array}$ (108) $\displaystyle\begin{array}[]{c}\mbox{Biased
voter model}\\\ \mbox{[BVM]}\end{array}\quad$
$\displaystyle\sigma=\begin{pmatrix}1&0&0&0\\\ \theta&0&0&1-\theta\\\
\theta&0&0&1-\theta\\\ 0&0&0&1\end{pmatrix}$ for $\theta\in[0,1]$, (111)
$\displaystyle\begin{array}[]{c}\mbox{Asymmetric voter model}\\\
\mbox{[AVM]}\end{array}\quad$ $\displaystyle\sigma=\begin{pmatrix}1&0&0&0\\\
r&0&0&l\\\ l&0&0&r\\\ 0&0&0&1\end{pmatrix}$
$\displaystyle\quad\begin{array}[]{c}\mbox{for $r,l\in[0,1]$,}\\\
\mbox{$r+l=1$,}\end{array}$ (116)
$\displaystyle\begin{array}[]{c}\mbox{Asymmetric anti-voter model}\\\
\mbox{[AAVM]}\end{array}\quad$ $\displaystyle\sigma=\begin{pmatrix}0&l&r&0\\\
0&1&0&0\\\ 0&0&1&0\\\ 0&r&l&0\end{pmatrix}$
$\displaystyle\quad\begin{array}[]{c}\mbox{for $r,l\in[0,1]$,}\\\
\mbox{$r+l=1$,}\end{array}$ (121)
$\displaystyle\begin{array}[]{c}\mbox{Annihilating-coalesing}\\\ \mbox{random
walks}\\\ \mbox{[ACRW]}\end{array}\quad$
$\displaystyle\sigma=\begin{pmatrix}0&l(1-\theta)&r(1-\theta)&\theta\\\
0&l&r&0\\\ 0&l&r&0\\\ 0&0&0&1\end{pmatrix}$
$\displaystyle\quad\begin{array}[]{c}\mbox{for $r,l,\theta\in[0,1]$,}\\\
\mbox{$r+l=1$,}\end{array}$ (127)
$\displaystyle\begin{array}[]{c}\mbox{Coalesing symmetric random}\\\
\mbox{walks with branching}\\\ \mbox{[CSRWB]}\end{array}\quad$
$\displaystyle\sigma=\begin{pmatrix}1-2\theta&\theta&\theta&0\\\
1-2\theta&\theta&\theta&0\\\ 1-2\theta&\theta&\theta&0\\\
0&0&0&1\end{pmatrix}$ for $\theta\in[0,\frac{1}{2}]$, (131)
$\displaystyle\begin{array}[]{c}\mbox{Annihilating symmetric random}\\\
\mbox{walks with pair immigration}\\\ \mbox{[ASRWPI]}\end{array}\quad$
$\displaystyle\sigma=\begin{pmatrix}\frac{1}{2}-\theta&0&0&\frac{1}{2}+\theta\\\
0&\frac{1}{2}&\frac{1}{2}&0\\\ 0&\frac{1}{2}&\frac{1}{2}&0\\\
\frac{1}{2}-\theta&0&0&\frac{1}{2}+\theta\end{pmatrix}$ for
$\theta\in[0,\frac{1}{2}]$, (135) $\displaystyle\begin{array}[]{c}\mbox{Dimer
model}\\\ \mbox{[DM]}\end{array}\quad$
$\displaystyle\sigma=\begin{pmatrix}\frac{1}{2}&0&0&\frac{1}{2}\\\ 0&1&0&0\\\
0&0&1&0\\\ \frac{1}{2}&0&0&\frac{1}{2}\end{pmatrix}$ (138)
$\displaystyle\begin{array}[]{c}\mbox{Reshuffle model}\\\
\mbox{[RM]}\end{array}\quad$ $\displaystyle\sigma=\begin{pmatrix}1&0&0&0\\\
1&0&0&0\\\ 1&0&0&0\\\ 1&0&0&0\end{pmatrix}$ (141)
$\displaystyle\begin{array}[]{c}\mbox{Erosion model 1}\\\
\mbox{[EM1]}\end{array}\quad$ $\displaystyle\sigma=\begin{pmatrix}1&0&0&0\\\
0&1&0&0\\\ 0&0&0&1\\\ 0&0&0&1\end{pmatrix}$ (144)
$\displaystyle\begin{array}[]{c}\mbox{Erosion model 2}\\\
\mbox{[EM2]}\end{array}\quad$ $\displaystyle\sigma=\begin{pmatrix}0&1&0&0\\\
0&1&0&0\\\ 0&0&0&1\\\ 0&0&0&1\end{pmatrix}$ (147)

##  4 The eleven models

We examine the models that arise in the classification theorems and, where
possible, link the algebraic information gained in the classification to
duality functions.

###  4.1 Exclusion processes [SEP] and [ASEP]

The asymmetric exclusion process [ASEP] is discussed in Section 2.3, where for
initial conditions with a rightmost particle the staircase duality functions
form a complete set.

For the symmetric exclusion process [SEP] the action of $\sigma$ on the basis
$(v\otimes v,w\otimes w,v\otimes w,w\otimes v)$ recorded in Lemma 5 shows that
duality functions of product moment type (41) exist. Indeed the choice
$w=(1,0)^{T}$ gives exactly the product moment $g^{(n)}_{x_{1},\ldots,x_{n}}$
which corresponds to the test function $\prod_{k=1}^{n}\eta(x_{k})$. These are
the standard dualities functions (see Liggett [32] Chapter VIII) where the
dual process can be taken to be a symmetric exclusion process with finitely
many particles.

Using the other vectors listed in Lemma 5, namely $w=(1,\omega)^{T}$ or
$w=(0,1)^{T}$, in the product moment duality function (41) corresponds to
certain special linear combinations of product moments, and the algebra just
shows that the generator leads to expressions that can be re-expressed in
terms of the same special linear combinations. For example when $w=(0,1)^{T}$
this shows that the probability of empty regions solves a closed set of
equations (for any fixed cardinality of region).

###  4.2 Voter models [BVM], [AVM] and [AAVM]

In the asymmetric voter model model [AVM], each site independently triggers a
disagreeing neighbouring site to the right to take its value at rate $r$, and
a disagreeing neighbouring site to the left to take its value at rate $l$.
This model has a generator of the form (14) with $\sigma$ given by (116). This
model is usually studied using the mapping to domain walls: the bijective
mapping that sends $\eta$ to the set markers in the dual lattice
$\frac{1}{2}+{\mathbb{Z}}$ that mark the boundaries between runs of $0$’s and
runs of $1$. The positions of these markers perform instantaneously
annihilating random walks on $\frac{1}{2}+{\mathbb{Z}}$, where the domain
walls jump left with rate $l$ and right with rate $r$, a model that is known
to lead to a Pfaffian point process at fixed times (see Section 5.3 below).

Analysing the generator of [AVM] in the framework we are using, we find there
are no second tensor form eigenvector $w\otimes w$ of $\sigma$. However there
are product moment type dualities functions. Indeed the product moments
$g^{(n)}_{x_{1},\ldots,x_{n}}$ as in (42) are duality functions, and the dual
action is that of instantaneously coalescing asymmetric random walks (left
jumps at rate $r$ and right jumps at rate $l$). Product exponential moments
$g^{(n)}_{\beta;x_{1},\ldots,x_{n}}$ as in (43) are also duality functions for
any $\beta$, in that $\sigma$ has a good action on $w\otimes w$, but the dual
action is more complicated.

In the biased voter model [BVM], each neighbouring pair of disagreeing sites,
that is with values $10$ or $01$, jump (independently) to $11$ at rate
$\theta$ or $00$ at rate $1-\theta$. This model has a generator of the form
(14) with $\sigma$ given by (75). The mapping to domain walls still yields a
Markov model, with a domain wall with $1$s to the left and $0$s to the right
jumps to the right at rate $\theta$ and to the left at rate $1-\theta$, while
a domain wall with $0$s to the left and $1$s to the right jumps to the right
at rate $1-\theta$ and to the left at rate $\theta$. In the non-symmetric case
$\theta\neq\frac{1}{2}$, there is a second eigenvector $w\otimes w$ as found
in Lemma 5. To simplify the dual action we scale this vector and take, when
$\theta\neq 1$, the vector $w=(1,\theta/(1-\theta))^{T}$, which leads to an
alternating interval duality function $f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}$
defined in (21). The dual action has annihilating particles with sites
$x_{2n}$ moving right at rate $\theta$ and left at rate $1-\theta$, while
sites $x_{2n+1}$ moving right at rate $1-\theta$ and left at rate $\theta$.
The case $\theta=1$ can be treated by particle-hole conjugation, which
interchanges $\theta$ and $1-\theta$.

The final voter model we met, the asymmetric anti-voter model [AAVM], is
mapped to the asymmetric model [AVM] by the bijection $\eta\to\tilde{\eta}$
where $\tilde{\eta}(x)=\eta(x)$ for $x\in 2{\mathbb{Z}}$ and
$\tilde{\eta}(x)=1-\eta(x)$ for $x\in 2{\mathbb{Z}}+1$, and the domain wall
map and the dualities functions still operate after this bijection.

###  4.3 Annihilating and coalescing systems [ACRW], [CSRWB], [ASRWPI]

Particles perform independent asymmetric simple random walks on
${\mathbb{Z}}$, jumping right with rate $r$ and left with rate $l$ (and
$r+l=1$), and upon any collision they instantaneously annihilate with
probability $\theta$ or instantaneously coalesce with probability $1-\theta$.
This produces the process [ACRW] with generator of the form (14) with $\sigma$
given by (127). Using the eigenvector $w=(-\theta,1)^{T}$, the alternating
interval vector $f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}$ defined in (21)
corresponds to

$f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}\quad\leftrightarrow\quad\prod_{1\leq
i\leq
n}(-\theta)^{\eta(x_{2i-1},x_{2i}]}\quad\mbox{where}\quad\eta(a,b]=\sum_{x=a+1}^{b}\eta(x).$

The action of $\sigma$ on the basis $(v\otimes v,w\otimes w,v\otimes
w,w\otimes v)$ recorded in Lemma 5 extends to the asymmetric case, with
$\sigma(w\otimes v)=rv\otimes v+lw\otimes w$ and $\sigma(v\otimes w)=lv\otimes
v+rw\otimes w$. This implies that

$Lf^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}=\sum_{k=1}^{2n}\Delta^{r,l}_{k}f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}},\quad\mbox{for
$x_{1}<x_{2}<\ldots<x_{2n}$,}$

where $\Delta^{r,l}_{k}$ is the non-symmetric discrete asymmetric Laplacian
acting on the variable $x_{k}$. Thus $f^{(2n)}$ is a duality function where
the dual is a system of $2n$ annihilating simple random walks. This duality
function was used in [16] to show the one-dimensional marginal $\eta_{t}$, for
any $t\geq 0$, is Pfaffian point processes on ${\mathbb{Z}}$ under any
deterministic initial condition. There are no product moment or exponential
product moment duality functions.

Next we examine coalescing symmetric random walks with branching [CSRWB].
Particles perform independent symmetric simple random walks on ${\mathbb{Z}}$,
with total jump rate $2\alpha$, they instantaneously coalesce upon collision,
and in addition each particle independently branches, producing a particle
onto each neighbouring empty site at rate $\beta$. Scaling time so that
$2\alpha+\beta=1$, then taking $\theta=\alpha=(1-\beta)/2$, we arrive at the
generator of the form (14) with $\sigma$ given by (86). The only other tensor
form eigenvector $w\otimes w$ with a good action is $w=(0,1)^{T}$, for which
the alternating interval vector $f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}$ defined
in (21) corresponds to

$f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}\quad\leftrightarrow\quad\prod_{1\leq
i\leq
n}\mathbbm{1}(\eta(x_{2i-1},x_{2i}]=0)\quad\mbox{where}\quad\eta(a,b]=\sum_{x=a+1}^{b}\eta(x),$

the well known empty interval duality function. The action of $\sigma$ on the
basis $(v\otimes v,w\otimes w,v\otimes w,w\otimes v)$ recorded in Lemma 5
shows that

$Lf^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}=\sum_{k=1}^{2n}\Delta^{1-\theta,\theta}_{2k-1}f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}+\sum_{k=1}^{2n}\Delta^{\theta,1-\theta}_{2k}f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}},\quad\quad
x_{1}<x_{2}<\ldots<x_{2n}$

The vector $f^{(2n)}$ is a duality function where the dual is a system of $2n$
annihilating random walks, where even and odd positioned particles have
different asymmetric rates. This duality function was used in [17] to show the
one-dimensional marginal $\eta_{t}$, for any $t\geq 0$, is Pfaffian point
processes on ${\mathbb{Z}}$ under any deterministic initial condition. Again
there are no product moment or exponential product moment duality functions.

Finally we examine annihilating symmetric random walks with pair immigration
[ASRWPI]. Particles perform independent symmetric simple random walks on
${\mathbb{Z}}$, with total jump rate $2\alpha$, they instantaneously
annihilate upon collision, and in addition there is immigration of pairs of
particles at each pair of sites $\\{x,x+1\\}$ at rate $\beta$ independently
for all $x\in{\mathbb{Z}}$. Scaling time so that $\alpha+\beta=\frac{1}{2}$,
then taking $\theta=\alpha=\frac{1}{2}-\beta$, we arrive at the generator of
the form (14) with $\sigma$ given by (90).

The only other tensor form eigenvector $w\otimes w$ with a good action using
$w=(-1,1)^{T}$, for which the alternating interval vector
$f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}$ defined in (21) corresponds to the
duality function

$f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}\quad\leftrightarrow\quad\prod_{1\leq
i\leq
n}(-1)^{\eta(x_{2i-1},x_{2i}]}\quad\mbox{where}\quad\eta(a,b]=\sum_{x=a+1}^{b}\eta(x).$

The action of $\sigma$ on the basis $(v\otimes v,w\otimes w,v\otimes
w,w\otimes v)$ recorded in Lemma 5 shows that

$Lf^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}=\theta\sum_{k=1}^{2n}\Delta_{k}f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}-(1-2\theta)\sum_{k=1}^{2n}f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}},\quad
x_{1}<x_{2}<\ldots<x_{2n}.$

This duality function was used in [17] to show the one-dimensional marginal
$\eta_{t}$, for any $t\geq 0$, is Pfaffian point processes on ${\mathbb{Z}}$
under any deterministic initial condition. Only the case $\theta=0$,
corresponding to immigration of pairs with no underlying motion, has product
moment dualities, where the product exponential moment function
$g^{(n)}_{\beta;x_{1},\ldots,x_{n}}$ as in (43) is a duality function for any
$\beta$.

###  4.4 Stationary coalescence-annihilation model [SCAM]

Every neighbouring pair of particles, at sites $\\{x,x+1\\}$ and independently
for all $x$, reacts at rate $1$; the reaction is either a coalescence,
producing $10$ or $01$ each with probability $\theta$, or an annihilation,
producing $00$ with probability $1-2\theta$. This process has generator of the
form (14) with $\sigma$ given by (94).

The rather simple dynamics produce decreasing sample paths. Configurations
without a pair of neighbouring occupied sites are the fixed point, which form
the extreme points for the set of invariant measures. No pair of distinct
initial conditions can be successfully coupled, and each solution converges to
a distinct (random) mixture of fixed points. Nevertheless, without a duality
function, exact calculations for the limiting distribution would be difficult.
We use the duality to analyse the limiting state for the process started from
its maximal initial condition where all sites are occupied, which turns out to
be a renewal process on ${\mathbb{Z}}$.

The action of $\sigma$ on the basis $(v\otimes v,w\otimes w,v\otimes
w,w\otimes v)$ recorded in Lemma 5 does not mesh with either an alternating
interval duality function, or a staircase duality function. Moreover there are
no product moment, or exponential product moment, dualities. However there are
other choices of $w$ that lead to a useful action, and we choose the
eigenvector $e^{(1)}\otimes e^{(1)}$, with eigenvalue $0$, on which the
generator acts nicely:

$\displaystyle\sigma v\otimes e^{(1)}=v\otimes
e^{(1)}-(1-\theta)e^{(1)}\otimes e^{(1)},\qquad\sigma e^{(1)}\otimes
v=e^{(1)}\otimes v-(1-\theta)e^{(1)}\otimes e^{(1)}.$ (148)

Therefore the action of the generator preserves the order of vectors $e^{(1)}$
and $v$ in the tensor product. We may take the alternating interval vector
defined in (21) with $w=e^{(1)}=(1,0)^{T}$, corresponding to

$f^{(2n)}_{x_{1},x_{2},\ldots,x_{2n}}\quad\leftrightarrow\quad\prod_{1\leq
i\leq n}\mathbbm{1}(\eta(y)=1\;\mbox{for $x_{2i-1}<y\leq x_{2i}$}),$

that is the indicator that the intervals $(x_{2i-1},x_{2i}]$ are fully
occupied. We take parameters $x_{1}<x_{2}<\ldots<x_{2n}$ and $n\geq 1$.

Using (148) it is straightforward to derive the following set of equations for
the expectations of the duality functions
$\Phi^{(2n)}_{t}(x_{1},\ldots,x_{2n}):={\mathbb{E}}[\prod_{1\leq i\leq
n}\mathbbm{1}(\eta(y)=1\;\mbox{for $x_{2i-1}<y\leq x_{2i}$})]$ under the
initial condition $\eta_{0}\equiv 1$: for every $n\in{\mathbb{N}}$,

$\partial_{t}\Phi^{(2n)}_{t}=-\sum_{k=1}^{n}D_{k}\Phi^{(2n)}_{t},\quad\mbox{for
$t\geq 0$, $x_{1}<\ldots<x_{2n}$},$ (149)

where

$\displaystyle D_{k}\Phi(\ldots,x_{2k-1},x_{2k},\ldots)$ $\displaystyle=$
$\displaystyle(1-\theta)\Phi(\ldots,x_{2k-1}-1,x_{2k},\ldots)+(1-\theta)\Phi(\ldots,x_{2k-1},x_{2k}+1,\ldots)$
$\displaystyle+(x_{2k}-x_{2k-1}-1)\Phi(\ldots,x_{2k-1},x_{2k},\ldots),$

and where we use the boundary conditions

$\Phi^{(2n)}_{t}(\ldots,x_{i-1},x_{i},x_{i+1},x_{i+2}\ldots)=\Phi^{(2n-2)}_{t}(\ldots,x_{i-1},x_{i+2}\ldots)\quad\mbox{when
$x_{i}=x_{i+1}$,}$ (150)

and the convention $\Phi^{(0)}_{t}\equiv 1$ to define the right hand side of
(149).

The system of equations (149), with the boundary conditions (150) and initial
condition $\Phi^{(2n)}_{0}\equiv 1$ corresponding to all sites occupied, can
be solved exactly. Uniqueness holds for bounded solutions, as can be shown
inductively in $n\in 2{\mathbb{N}}$, by an energy calculation: if
$\mathcal{E}_{t}:=\sum_{x\in
V_{2n}}(\Phi^{(2n)}_{t})^{2}(x)\exp(-\sum_{i}|x_{i}|)$, summing over the open
cell $V_{2n}=\\{x:x_{1}<\ldots<x_{2n}\\}$, then $(d/dt)\mathcal{E}_{t}\leq
C\mathcal{E}_{t}$. The main building block for the solution is
$\Phi^{(2)}_{t}(x,y)$, the probability that the interval $(x,y]$ is fully
occupied at time $t$. Exploiting the translation invariance we find that the
(unique bounded) solution is, setting $\gamma=2(1-\theta)$,

$\Phi^{(2)}_{t}(x,y)=e^{-(y-x-1)t}e^{-\gamma(1-e^{-t})},\quad x\leq y,\;t\geq
0.$ (151)

In particular, the one-particle density is

$\displaystyle\rho_{t}:=\Phi_{t}^{(2)}(x-1,x)=e^{-\gamma(1-e^{-t})}.$ (152)

We look for the solution to (149) in the form

$\displaystyle\Phi_{t}^{(2n)}(x_{1},y_{1},\ldots,x_{n},y_{n})=\prod_{k=1}^{n}\Phi_{t}^{(2)}(x_{k},y_{k})\prod_{k=1}^{n-1}F_{t}(x_{k+1}-y_{k}).$
(153)

The insertions of the function $F_{t}$ in (153) describe spatial correlations
between the runs of occupied sites. Substituting the Ansatz (153) into (149),
one finds that it can be satisfied provided the function $(F_{t}(x):t\geq
0,x\in{\mathbb{N}})$ solves the following problem

$\displaystyle\left\\{\begin{array}[]{ll}\partial_{t}F_{t}(x)=\gamma
e^{-t}\left(F_{t}(x)-F_{t}(x-1)\right),&t>0,\,x>0,\\\
F_{t}(0)=e^{-t}e^{\gamma\left(1-e^{-t}\right)},&t>0,\\\ F_{0}(x)=1,&x\geq
0.\end{array}\right.$ (157)

The solution is

$\displaystyle
F_{t}(x)=e^{\tau(t)}\left(E_{x}(-\tau(t))+\frac{1}{\gamma}\frac{(-\tau(t))^{x+1}}{(x+1)!}\right)\quad\mbox{for
$t\geq 0$ and $x\geq 0$,}$ (158)

where $\tau(t)=\gamma(1-e^{-t})$ for $t\geq 0$, and
$E_{n}(z)=\sum_{k=0}^{n}z^{k}/k!$ is the exponential polynomial of degree $n$.
Notice that, as $x\rightarrow\infty$, $F_{t}(x)$ approaches $1$ exponentially
fast, which describes the de-correlation of runs in the limit of large
separations.

By setting $x_{k}=y_{k}-1$ in (153) we get a complete description of the law
of SCAM at a fixed time $t>0$ in terms of the correlation functions: for
$t\geq 0,x_{1}<x_{2}<\ldots<x_{n}$ and $n\geq 1$

$\displaystyle\rho^{(n)}_{t}(x_{1},x_{2},\ldots,x_{n})$ $\displaystyle:=$
$\displaystyle\mathbb{P}\left[\eta_{t}(x_{k})=1,k=1,2,\ldots,n\right]$ (159)
$\displaystyle=$
$\displaystyle(\rho_{t})^{n}\prod_{k=2}^{n}F_{t}(x_{k}-x_{k-1}-1).$

Examining (159), we conclude that SCAM started from the fully occupied lattice
at $t=0$ is a stationary renewal process at any fixed $t>0$. One immediate
consequence of (159) and Bayes’ formula is that $\\{\eta_{t}(k)\\}_{k<x}$ and
$\\{\eta_{t}(k)\\}_{k>x}$ are independent conditionally on the event
$\\{\eta_{t}(x)=1\\}$. A stationary renewal processes are characterised by its
renewal measure (Janossi density in the terminology of point processes),

$J_{t}(n)=\mathbb{P}[\eta_{t}(k)=0,1\leq k\leq
n-1,\eta_{t}(n)=1|\eta_{t}(0)=1],\quad\mbox{for $n\geq 1$, $t>0$.}$ (160)

The above conditional independence property of a renewal processes allows one
to derive a linear (renewal) equation for the renewal measure

$\displaystyle\rho_{t}^{(2)}(0,n)$ $\displaystyle=$
$\displaystyle\mathbb{P}[\eta_{t}(1)=1,\eta_{t}(k)=0,1\leq k\leq
n-1,\eta_{t}(n)=1]$ (161) $\displaystyle\hskip
14.45377pt+\sum_{k=1}^{n-1}\mathbb{P}[\eta_{t}(0)=1,\eta_{t}(j)=0,1\leq j\leq
k,\eta_{t}(k+1)=1,\eta_{t}(n)=1]$ $\displaystyle=$
$\displaystyle\rho_{t}J_{t}(n)+\sum_{k=1}^{n-1}J_{t}(k)\;\rho_{t}^{(2)}(k+1,n)\quad\mbox{for
$n\geq 1$}.$

Translation invariance implies $\rho_{t}^{(2)}(k+1,n)=\rho_{t}^{(2)}(0,n-k)$.
Introducing the generating functions
$\hat{J}_{t}(z)=\sum_{n=1}^{\infty}J_{t}(n)z^{n}$ and
$\hat{\rho}^{(2)}_{t}(z)=\sum_{n=1}^{\infty}\rho^{(2)}_{t}(0,n)z^{n}$ it is
easy to solve the equation, namely

$\displaystyle\hat{J}_{t}(z)=\frac{\hat{\rho}^{(2)}_{t}(z)}{\rho_{t}+\hat{\rho}^{(2)}_{t}(z)}.$
(162)

Moreover, an explicit expression for the transform of the two-point density
can be found using (159)

$\displaystyle\hat{\rho}^{(2)}_{t}(z)=\frac{z\rho_{t}}{1-z}e^{-\tau(t)z}+\frac{\rho_{t}}{\gamma}(e^{-\tau(t)z}-1).$
(163)

The relations (162, 163) fully characterise the renewal measure.

As an application of the above exact formulae, we examine the large $n$
asymptotic of the renewal measure $J_{\infty}(n)$ in the stationary state,
that is sending $t\to\infty$. In this limit, $\tau(t)\rightarrow\gamma$ and
$\rho_{t}\to e^{-\gamma}$. We contrast the behaviour under pure coalescence
and under pure annihilation. When $\theta=\frac{1}{2}$ all reactions are
coalesences. In this case $\gamma=1$. From (162) one finds
$\hat{J}_{\infty}(z)=\left(1-(1-z)e^{z}\right)$ and hence

$\displaystyle J_{\infty}(n)=\frac{(n-1)}{n!},\quad\mbox{for $n\geq 1$.}$
(164)

Notice that $J_{\infty}(1)=0$, reflecting the fact that in the stationary
state the probability of a configuration with two ones in a row is zero.

When $\theta=0$ all reactions are annihilations. In this case $\gamma=2$ and
the formula for the generating function of Janossi densities takes the form

$\displaystyle\hat{J}_{\infty}(z)=\frac{z-\tanh(z)}{1-z\tanh(z)},~{}z\in\mathbb{C}.$
(165)

Notice that the function $\hat{J}_{\infty}$ is odd and so has zero Taylor
coefficients of even degree, reflecting the fact that the probability of runs
of zeros of odd length is zero as particles can only vanish in pairs. The
large $n$ asymptotics of $J_{\infty}(n)$ is determined by the singularities of
$\hat{J}_{\infty}$ nearest to zero. These are the smallest roots of the
equation $z\tanh(z)=1$ which are equal to $\pm r$, where $r\approx 1.19968$.
Applying Cauchy’s theorem one finds that

$\displaystyle
J_{\infty}(n)=(1-(-1)^{n})\,\frac{r-r^{-1}}{r^{2}}r^{-n}(1+O(\Delta^{-n})),$
(166)

where $\Delta>1$ is determined by the gap between $r$ and the set of absolute
values of complex roots. Notice also that the renewal measure decays
exponentially with $n$, whereas for pure coalescence the decay (164) is super-
exponential. The reason is that for pure coalesence particles disappear only
in singletons while reactions occur only when there is a neighbouring pair of
occupied sites; so to produce a long row of empty sites, the coalescences must
occur successively from left to right or successively from right to left, both
unlikely scenarios.

###  4.5 The dimer model [DM]

At neighbouring sites $\\{x,x+1\\}$, and independently for all $x$, an
occupied pair $11$ annihilates at rate $\theta$, and an unoccupied pair $00$
is replaced by an occupied pair at rate $1-\theta$. This process has generator
of the form (14) with $\sigma$ given by (97).

The action of $\sigma$ on the basis $(v\otimes v,w\otimes w,v\otimes
w,w\otimes v)$ recorded in Lemma 5 does not mesh with either an alternating
interval duality function, or a staircase duality function. When
$\theta\neq\frac{1}{2}$ there are no product moment or exponential product
moment dualities (we will see that the case $\theta=\frac{1}{2}$ is special
below).

This model, however, is equivalent to an inhomogeneous exclusion model, as
follows. The dimer model has the following two obvious trapped states, where
no jumps are possible,

$\eta_{a}(k):=\frac{\left(1-(-1)^{k}\right)}{2},~{}k\in{\mathbb{Z}},\quad\mbox{and}\quad\eta_{b}(k):=\frac{\left(1+(-1)^{k}\right)}{2},~{}k\in{\mathbb{Z}}.$

Let us define quasi-particles as deviations from one of the above states. We
fix $\eta_{a}$ as the reference state and then the configuration $\xi$ of
quasi-particles for a given configuration $\eta$ of particles is defined by

$\xi(k)=\left\\{\begin{array}[]{ll}\eta(k)&\text{when $k$ is even,}\\\
1-\eta(k)&\text{when $k$ is odd,}\end{array}\right.~{}~{}k\in{\mathbb{Z}}.$

The map $\eta\to\xi$ is a bijection on $\\{0,1\\}^{\mathbb{Z}}$, so that the
process of quasi-particles $(\xi_{t})$ remains Markov. Its generator is

$\displaystyle
L=\sum_{k\in{\mathbb{Z}}}\left(q^{(0)}_{2k}+q^{(1)}_{2k+1}\right),$ (167)

where

$\displaystyle q^{(0)}=\begin{pmatrix}0&0&0&0\\\ 0&-\theta&\theta&0\\\
0&1-\theta&-(1-\theta)&0\\\ 0&0&0&0\end{pmatrix},\qquad
q^{(1)}=\begin{pmatrix}0&0&0&0\\\ 0&-(1-\theta)&1-\theta&0\\\
0&\theta&-\theta&0\\\ 0&0&0&0\end{pmatrix}.$ (168)

We conclude that the image of the dimer model is equivalent to an exclusion
model. It coincides with standard SEP for $\theta=\frac{1}{2}$, but is a
spatially inhomogeneous, and non-symmetric in the notation from Liggett [32],
exclusion model otherwise. Therefore, when $\theta=\frac{1}{2}$ the model has
a spanning set of duality functions while for general asymmetric exclusion
processes dualities are not known.

We can, however, use the map to an exclusion model to find invariant measures.
Firstly, let us consider the degenerate case $\theta=0$. In this case the only
allowed transitions are $00\rightarrow 11$. The process has monotone
increasing paths and converges to a trap, that is any state without any pair
of successive zeroes. The particle-hole conjugation maps the dimer model
parameter $\theta$ to $1-\theta$, so we now consider the range of the
parameter $\theta$ to $(0,\frac{1}{2}]$. In [31], Chapter V111.2, Theorem 2.1,
Liggett gives a condition ensuring a family of product Bernouilli invariant
measures, which is satisfied for our quasi-particle process $(\xi_{t})$. In
our algebraic notation, such product Bernouilli measures can be found by
looking for a vector $\mu$ satisfying

$\left(\sum_{k\in{\mathbb{Z}}}q^{*}_{k}\right)\mu=0,\qquad\mbox{where}\quad
q^{*}=\begin{pmatrix}-\theta&0&0&1-\theta\\\ 0&0&0&0\\\ 0&0&0&0\\\
\theta&0&0&-(1-\theta)\end{pmatrix}$

and which is stochastic in each co-ordinate. Let $\mu_{0}=(p,1-p)$ for
$p\in[0,1]$. Solving for a stochastic vector $\mu_{1}=(\Phi(p),1-\Phi(p))$ so
that $q^{*}\mu_{0}\otimes\mu_{1}=0$, one finds

$\Phi(p)=\frac{(1-\theta)(1-p)}{\theta p+(1-\theta)(1-p)}.$

Notice that $\Phi\circ\Phi=I$, and this ensures that
$q^{*}\mu_{1}\otimes\mu_{0}=0$. Hence we may take
$\mu=\cdots\otimes\mu_{0}\otimes\mu_{1}\otimes\mu_{0}\otimes\cdots$ for any
$p$ as an invariant measure, corresponding to product Bernouilli with
parameters alternating between $p$ and $\Phi(p)$. The fixed point where
$\Phi(p)=p$ is solved by $p=\sqrt{1-\theta}/(\sqrt{\theta}+\sqrt{1-\theta})$
giving a translation invariant measure.

###  4.6 The reshuffle model [RM]

Each pair of neighbouring sites $\\{x,x+1\\}$, independently for all $x$,
reacts at rate $1$ to produce $00$ with probability $\alpha_{1}$, $10$ with
probability $\alpha_{2}$, $01$ with probability $\alpha_{3}$, and $11$ with
probability $\alpha_{4}$, leading to a process with generator of the form (14)
with the rank one matrix

$\sigma=\begin{pmatrix}\alpha_{1}&\alpha_{2}&\alpha_{3}&\alpha_{4}\\\
\alpha_{1}&\alpha_{2}&\alpha_{3}&\alpha_{4}\\\
\alpha_{1}&\alpha_{2}&\alpha_{3}&\alpha_{4}\\\
\alpha_{1}&\alpha_{2}&\alpha_{3}&\alpha_{4}\end{pmatrix},\quad\sum_{k=1}^{4}\alpha_{k}=1,\quad\alpha_{i}\geq
0,\;1\leq i\leq 4.$

The symmetric case (102) that emerged in the first classification theorem is a
special case.

The classification Theorem 2 did not reveal a second tensor form
eigenfunction. However the range of $\sigma$ is spanned by $v\otimes v$ and
this implies that product moments, or exponential product moments for any
$\beta$, are duality functions. We now make use of these to identify the
unique invariant measure, which can be described rather completely.

Figure 1: Graphical construction of RRM: times of horizontal bars connecting
vertical lines through $k$ and $k+1$ are a Poisson point process with unit
intensity. Poisson processes corresponding to different pairs of lines are
independent. Each horizontal bar is labelled with $(11),(10),(01),(00)$ with
probabilities $\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4}$ independently of
other lines. The current state at site $k$ at time $t$ is given by the label
at the last bar adjacent to $k$ dropped before time $t$, or the initial
condition if there is no such bar.

The evolution of the model can be visualised using the graphical construction
shown in Fig. 1. This construction gives a successful coupling of any two
initial conditions, which implies that all solutions are attracted to a single
invariant measure $(\xi_{\infty}(x):x\in{\mathbb{Z}})$. A further immediate
consequence of the construction is that for a fixed $t>0$ the random vectors
$(\eta_{t}(k))_{k<x}$ and $(\eta_{t}(k))_{k>x}$ are independent for any
$x\in{\mathbb{Z}}$ provided the initial random vectors $(\eta_{0}(k))_{k<x}$
and $(\eta_{0}(k))_{k>x}$ are independent. This property is known as one-
dependency. Starting with a deterministic initial condition we deduce that the
invariant measure is one dependent. Moroever, a one-dependent point process on
${\mathbb{Z}}$ is also a determinantal point process, which follows from a
general result proved in [8]. By the Theorem 7.1 of that paper, the
corresponding determinantal kernel is expressed in terms of the probability of
runs of occupied sites, which we now proceed to compute.

To use the product moment function $g^{(n)}_{x_{1},x_{2},\ldots,x_{n}}$ as in
(42) we need the action of $\sigma$ in the basis $e^{(1)}\otimes e^{(1)}$,
$e^{(1)}\otimes v$, $v\otimes e^{(1)}$, $v\otimes v$. The calculation is
simplified since $\text{Image}(\sigma)$ is spanned by $v\otimes v$. A direct
computation of the relevant constants gives:

$\displaystyle\sigma v\otimes v=v\otimes v,$ $\displaystyle\sigma
e^{(1)}\otimes e^{(1)}=\alpha_{1}v\otimes v,$ (169) $\displaystyle\sigma
v\otimes e^{(1)}=(\alpha_{1}+\alpha_{3})v\otimes v,$ $\displaystyle\sigma
e^{(1)}\otimes v=(\alpha_{1}+\alpha_{2})v\otimes v.$

Let

$P_{t}(n)={\mathbb{E}}\left[\prod_{k=1}^{n}\eta_{t}(k)\right]$

be the probability of finding $n\geq 1$ particles at sites $1,2,\ldots,n$ at
time $t$, and set $P_{t}(0)=1$ for all $t$. Using (169) one finds the
following evolution equation for $P_{t}$

$\displaystyle\frac{\partial P_{t}}{\partial t}(n)=2\rho
P_{t}(n-1)+\alpha_{1}\sum_{k=1}^{n-1}{\mathbb{E}}\left[\prod_{p=1}^{k-1}\eta_{t}(p)\prod_{q=k+2}^{n}\eta_{t}(q)\right]-(n+1)P_{t}(n),\quad
n\geq 1$

where an empty product is defined to be $1$, and where we introduce the
following parameter

$\displaystyle\rho:=\frac{2\alpha_{1}+\alpha_{2}+\alpha_{3}}{2}\in[0,1].$
(170)

Note that under particle-hole conjugation, $\rho\mapsto 1-\rho$. Therefore,
without loss, we now take $\rho\in[0,1/2]$.

Due to the one-dependence property established above, the random variables
$\prod_{p=1}^{k-1}\eta_{t}(p)$ and $\prod_{q=k+2}^{n}\eta_{t}(q)$ are
independent, which leads to the following non-linear equation for the
probabilities of runs

$\frac{\partial P_{t}}{\partial t}(n)=2\rho
P_{t}(n-1)\\!+\\!\alpha_{1}\sum_{k=1}^{n-1}P_{t}(k-1)P_{t}(n-k-1)-(n+1)P_{t}(n),\quad
n\geq 1,\;t>0.$ (171)

The differential-difference equation (171) can be converted to a partial
differential equation using the generating function for the run probabilities
defined as

$\displaystyle G_{t}(z)=\sum_{n=0}^{\infty}P_{t}(n)z^{n},\quad\mbox{for
$|z|<1$}.$ (172)

In the invariant measure $G_{t}(z)=G_{\infty}(z)$ and (171) becomes

$\displaystyle(zG_{\infty}(z))^{\prime}=1+2\rho
zG_{\infty}(z)+\alpha_{1}(zG_{\infty}(z))^{2},\quad|z|<1,\quad
G_{\infty}(0)=1.$ (173)

It is useful to consider the cases $\alpha_{1}=0$ and $\alpha_{1}>0$
separately. When $\alpha_{1}=0$ the equation (173) is linear and has solution

$\displaystyle G_{\infty}(z)=\frac{1}{2\rho z}\left(e^{2\rho
z}-1\right)=\sum_{n=0}^{\infty}\frac{(2\rho z)^{n}}{(n+1)!}.$ (174)

Therefore,

$\displaystyle P_{\infty}(n)=\frac{(2\rho)^{n}}{(n+1)!},\quad\mbox{for $n\geq
0$.}$ (175)

In particular, the particle density in the steady state is
$P_{\infty}(1)=\rho$. Together with the one dependence property, (175)
determines all the correlation functions of the invariant distribution
$(\eta_{\infty}(x):x\in{\mathbb{Z}})$. Indeed the determinantal structure
gives, for $x_{1}<x_{2}<\ldots<x_{m}$ and $m\geq 1$,

$\mathbb{P}\left[\eta_{\infty}(x_{k})=1,k=1,\ldots,m\right]=\det\left[K(x_{k}-x_{j}):j,k=1,\ldots,m\right],$
(176)

where the translation invariant kernel $K:{\mathbb{Z}}\rightarrow\mathbb{R}$
is determined by the following inversion formula (Corollary 4.3 of [8])

$\displaystyle\sum_{n\in{\mathbb{Z}}}K(n)z^{n}$ $\displaystyle=$
$\displaystyle-\frac{1}{zG_{\infty}(z)}$ $\displaystyle=$
$\displaystyle-\frac{2\rho}{e^{2\rho
z}-1}=-2\rho\sum_{n=-1}^{\infty}\frac{B_{n+1}}{(n+1)!}\left(2\rho
z\right)^{n},$

where $(B_{n})_{n\geq 0}$ is the set of Bernoulli numbers defined via the
generator function
$\frac{x}{e^{x}-1}=\sum_{n=0}^{\infty}\frac{B_{n}}{n!}x^{n}$. We conclude that
$K(n)=2\rho K_{2\rho}^{(BDF)}(n),n\in{\mathbb{Z}}$, where $K_{a}^{(BDF)}$ is
the translationally invariant kernel for the descent process introduced by
Borodin, Diaconis and Fulman in [8]:

$\displaystyle K_{a}^{(BDF)}(n)=\left\\{\begin{array}[]{cc}0,&n\leq-2,\\\
-\frac{B_{n+1}a^{n}}{(n+1)!}&n\geq-1.\end{array}\right.$ (180)

Note that the parameter $a$ does not affect the law of the descent process
since the determinants in (176) do not depend on $a\neq 0$ (there is a
similarity transformation by a diagonal matrix with diagonal entries $a^{k}$).
We conclude that, when $\alpha_{1}=0$, the kernel for the reshuffle model can
be taken to be the multiple, by $2\rho\in[0,1]$, of the kernel for the descent
process. The point process is therefore a thinning of the descent process. We
recall a direct construction of the descent process: let
$(U_{k})_{k\in{\mathbb{Z}}}$ be the sequence of i.i.d. uniform random
variables; the descent process can be defined by

$\displaystyle\eta^{(BDF)}_{k}=\mathbbm{1}\left(U_{k}>U_{k+1}\right),\quad
k\in{\mathbb{Z}}.$ (181)

Correspondingly, the stationary state of the random reshuffle model can be
generated using the usual thinning formula,

$\displaystyle\eta_{\infty}(k)=Z_{k}\mathbbm{1}\left(U_{k}>U_{k+1}\right),\quad
k\in{\mathbb{Z}},$ (182)

where $(Z_{k})_{k\in{\mathbb{Z}}}$ is the sequence of i.i.d.
Bernoulli($2\rho$) random variables independent of
$(U_{k})_{k\in{\mathbb{Z}}}$,

When $\alpha_{1}>0$ the equation (173) is non-linear, but it is still solvable
using elementary methods: let

$\displaystyle r_{\pm}=-\rho\pm\sqrt{\rho^{2}-\alpha_{1}}\in\mathbb{C},$ (183)

be the roots of the polynomial $h^{2}+2\rho h+\alpha_{1}$; the solution is,
for small $z$,

$\displaystyle
zG_{\infty}(z)=\frac{e^{r_{-}z}-e^{r_{+}z}}{r_{-}e^{r_{-}z}-r_{+}e^{r_{+}z}}\quad\mbox{when
$r_{-}\neq r_{+}$,}$ (184)

and $zG_{\infty}(z)=\frac{x}{1+rx}$ when $r_{-}=r_{+}=r$. As it is easy to
see, the generating function of run probabilities is real for real values of
the argument and $G(0)=1$. Notice also that for $\alpha_{1}>0$ the probability
of a run of $1$’s decays exponentially with run length, rather than as
$e^{-n\log n}$ in the $\alpha_{1}=0$ case, see (175).

An application of the inversion formula (4.6) yields the corresponding
determinantal kernel. For $\alpha_{1}\in[0,\rho^{2}]$ the explicit answer is

$\displaystyle
K(n)=(\rho-\sqrt{\rho^{2}-\alpha_{1}})\mathbbm{1}(n=0)+2\sqrt{\rho^{2}-\alpha_{1}}K^{(BDF)}_{2\rho}(n),~{}n\in{\mathbb{Z}}.$
(185)

To see how to construct the process (185) from the descent process define

$\displaystyle
p:=\rho-\sqrt{\rho^{2}-\alpha_{1}},\quad\gamma:=\frac{2\sqrt{\rho^{2}-\alpha_{1}}}{1-p}.$

As it is easy to check, $p\in[0,\frac{1}{2}]$, $\gamma\in[0,1]$. In terms of
these parameters,

$\displaystyle K(n)=p\mathbbm{1}(n=0)+(1-p)\gamma
K^{(BDF)}_{2\rho}(n),~{}n\in{\mathbb{Z}},$ (186)

which implies that the stationary state of the random reshuffle model for
$\alpha_{1}\in[0,\rho^{2}]$ is a determinantal point process built as the
union of a Bernoulli($p$) process on ${\mathbb{Z}}$ with an independent
$\gamma$-thinning of the descent process. More work is needed to characterise
the stationary state for $\alpha_{1}>\rho^{2}$ when the roots (183) become
complex.

###  4.7 Erosion models: [EM1] and [EM2]

In both models, the only changes that occur are flips $1\to 0$, so the models
are monotone decreasing.

The model [EM2] (147) is easiest to describe, as it is in fact a disguised
formulation of a non-interacting model. Indeed a comparison of the generators
shows that in this model each site $x\in{\mathbb{Z}}$ evolves independently,
flipping from $1\to 0$ at rate $1$. We say no more.

The other erosion model [EM1] (144) has no second factorized eigenvector.
Although there is a product exponential moment duality function (using
$w=(-1,1)^{T}$ yielding $\prod_{i\leq n}(-1)^{\eta(x_{i})}$), solving the
closed equations for ${\mathbb{E}}[\prod_{i\leq n}(-1)^{\eta_{t}(x_{i})}]$ is
not that useful since the system has a very simple probabilistic description.
We can break the initial condition into runs of successive $1$s, separated by
runs of successive $0$s. Zeroes never change and the process therefore
decouples into the independent evolution of the runs of $1$s. A finite run
$111\ldots 1$ erodes only from the left, that is only the left most $1$
changes to a $0$ at rate $1$, reducing the length. Finite runs therefore
eventually disappear, whilst a run that is semi-infinite on the right will
erode from the left forever, and a run that is semi-infinite on the left is a
fixed configuration. Thus the only possible limit points are the zero
configuration, and the traps $\eta(x)=\mathbbm{1}(x\leq k)$ for
$k\in{\mathbb{Z}}$.

##  5 Algebra

This Section contains a discussion of the algebraic structures appearing
naturally in the context of the Markov processes we have studied. One aim is
to examine in detail the models on a finite set of sites
${\mathbb{Z}}_{N}=\\{1,2,\ldots,N\\}$, with the corresponding generators
$\sum_{i=1}^{N-1}q_{i}$ and their corresponding finite dimensional generator
algebras $\mathbb{A}_{N}$. In particular the irreducible representations of
the finite dimensional generator algebras can sometimes be fully analysed.

In Section 5.1 we consider the generator algebra corresponding to annihilating
random walks on ${\mathbb{Z}}_{N}$. We compute exactly the dimensions of the
irreducible representations of this algebra. Originally, these dimensions were
calculated for small $N$ using the computational algebra package ‘Magma’ [42]
and turned out to be given by binomial coefficients. It was this fact that
motivated us to build these representations concretely as invariant subspaces
of $V^{\otimes N}$ spanned by eigenvectors.

In Section 5.2 we explore whether the size of irreducible representations can
provide information on the solvability of the model. The existence as in
Section 5.1 of ‘small’ (that is of polynomial size in $N$) irreducible
representations suggests there may be tractable duality functions.

In Section 5.3 we recall the well known fact that the duality functions can be
regarded as the intertwiners between two representations of the generator
algebra. We use this observation to construct a co-ordinate representation of
the infinite dimensional Hecke algebra in terms of the discrete Laplacians,
which we have not seen in the literature.

In Section 5.4 we recall the well known fact that a presentation of a Hecke
algebra can be used to construct a solution to the Young-Baxter equation
called an $R$-matrix. The R-matrix method is a cornerstone of another approach
to integrable probabilistic models based on the diagonalisation of the
transfer matrix. We give explicit examples of R-matrices for some of the
reaction-diffusion models on our classification list.

###  5.1 Duality functions and representations of the generator algebra

The considerations below apply to any of the reaction-diffusion models on our
list: [ACRW], [CSRWB], [ARWPI]. This is due to the fact that the two-site
generators for each model look identical if expressed in the corresponding
$(v,w)$ basis.

For concreteness we will work with annihilating random walks [ARW], perhaps
the most classical of the models and the one we considered in greatest detail
in Section 2.2 for the non-symmetric case $r\neq l$. To avoid dealing with
exceptional cases, we will not consider the totally asymmetric models and
assume that $r>0,l>0$.

The generator of [ARW] on ${\mathbb{Z}}_{N}$ with free boundary conditions is
mapped, as in Section 3.1, to an operator on $V^{\otimes N}=\otimes_{1\leq
k\leq N}V$ given by

$\displaystyle L_{N}=\sum_{k=1}^{N-1}(\sigma_{k}-I)$ (187)

as in (14) where $\sigma_{k}$ is the two site generator $\sigma$ from (13)
acting on $V_{k}\otimes V_{k+1}$. Let $\mathbb{A}_{N}$ be the generator
algebra of the model. By definition, $\mathbb{A}_{N}$ is the algebra over
$\mathbb{R}$ generated by $\\{\sigma_{k}\\}_{k=1}^{N-1}$.

Simulations using Magma for small values of $N$ suggest that the irreducible
representations of $L_{N}$ have the following dimensions

$\displaystyle
1^{(2)},(N-1)^{(2)},\frac{(N-1)(N-2)}{2}^{(2)},\ldots,{N-1\choose
k}^{(2)},\ldots,{N-1\choose N-1}^{(2)}.$ (188)

The superscript denotes the multiplicity of the corresponding representation.
As a consistency check, notice that

$2\sum_{k=0}^{N-1}{N-1\choose k}=2^{N}=\dim V^{\otimes N}.$

Our aim is to construct these representations explicitly using the duality
functions constructed in Section 3.1. Using $v=(1,1)^{T}$ and $w=(1,-1)^{T}$
we define the following elements of $T_{N}$:

$\displaystyle f_{x_{1},x_{2}}=v_{1}\otimes\ldots\otimes v_{x_{1}}\otimes
w_{x_{1}+1}\otimes\ldots\otimes w_{x_{2}}\otimes
v_{x_{2}+1}\otimes\ldots\otimes v_{N},\quad 1\leq x_{1}\leq x_{2}\leq N,$
(189) $\displaystyle g_{x_{1},x_{2}}=w_{1}\otimes\ldots\otimes
w_{x_{1}}\otimes v_{x_{1}+1}\otimes\ldots\otimes v_{x_{2}}\otimes
w_{x_{2}+1}\otimes\ldots\otimes w_{N},\quad 1\leq x_{1}\leq x_{2}\leq N.$
(190)

Next define $U^{(k)},W^{(k)}\subset V^{\otimes N}$ for $0\leq k\leq N-1$ as
follows:

$\displaystyle U^{(2n)}$ $\displaystyle=$
$\displaystyle\mbox{Span}_{\mathbb{R}}\left\\{\prod_{k=1}^{n}f_{x_{2k-1},x_{2k}},0\leq
x_{1}\leq x_{2}\leq\ldots\leq x_{2n}\leq N\\!\right\\},$ (191) $\displaystyle
U^{(2n-1)}\\!\\!\\!\\!\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\\!\\!\mbox{Span}_{\mathbb{R}}\\!\\!\left\\{\\!\prod_{k=1}^{n-1}\\!f_{x_{2k-1},x_{2k}}f_{x_{2n-1},N},0\leq
x_{1}\leq x_{2}\leq\ldots\leq x_{2n-1}\leq N\\!\right\\},$ (192)
$\displaystyle W^{(2n)}$ $\displaystyle=$
$\displaystyle\mbox{Span}_{\mathbb{R}}\left\\{\prod_{k=1}^{n}g_{x_{2k-1},x_{2k}},0\leq
x_{1}\leq x_{2}\leq\ldots\leq x_{2n}\leq N\\!\right\\},$ (193) $\displaystyle
W^{(2n-1)}\\!\\!\\!\\!\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\\!\\!\mbox{Span}_{\mathbb{R}}\\!\\!\left\\{\\!\prod_{k=1}^{n-1}\\!g_{x_{2k-1},x_{2k}}g_{x_{2n-1},N},0\leq
x_{1}\leq x_{2}\leq\ldots\leq x_{2n-1}\leq N\\!\right\\},$ (194)

where $0\leq 2n\leq N-1$ or $1\leq 2n-1\leq N-1$ and the Hadamard products are
used. Let us refer to the configurations of the form $v\otimes w$ and
$w\otimes v$ as jumps. For example, the vector $v\otimes v\otimes w\otimes
w\in V^{\otimes 4}$ has one jump, the vector $v\otimes w\otimes v\otimes w\in
V^{\otimes 4}$ has three jumps. Both $U^{(k)}$ and $W^{(k)}$ are spanned by
duality functions with at most $k$ jumps.

As a direct consequence of our definitions,

$W^{(k-1)},U^{(k-1)}\subset U^{(k)},\quad W^{(k-1)},U^{(k-1)}\subset
W^{(k)},\quad\mbox{for $1\leq k\leq N-1$.}$

Note that $U,W$ spaces are spanned by the duality functions. Therefore, it
follows from (22, 23) that these spaces are $\mathbb{A}_{N}$-invariant:

$\mathbb{A}_{N}W^{(k)}\subset W^{(k)},\quad\mathbb{A}_{N}U^{(k)}\subset
U^{(k)},\quad\mbox{for $1\leq k\leq N-1$.}$

So the action of $\mathbb{A}_{N}$ is well defined on the quotient spaces

$P^{(k)}=U^{(k)}/\left(U^{(k-1)}+W^{(k-1)}\right),~{}Q^{(k)}=Q^{(k)}/\left(U^{(k-1)}+W^{(k-1)}\right),$

namely if $a\in\mathbb{A}_{N}$, $u\in U^{(k)}$ and $[u]\in P^{(k)}$ then
$a[u]:=[au].$ Moreover, due to the invariance of the $U,W$ spaces, the
quotient spaces are also $\mathbb{A}_{N}$-invariant:

$\mathbb{A}_{N}P^{(k)}\subset P^{(k)},\quad\mathbb{A}_{N}Q^{(k)}\subset
Q^{(k)},\quad\mbox{for $1\leq k\leq N-1$.}$

The quotient spaces $P$ and $Q$ can be explicitly constructed as follows:

$\displaystyle P^{(2n)}$ $\displaystyle=$
$\displaystyle\mbox{Span}_{\mathbb{R}}\left\\{[\prod_{k=1}^{n}f_{x_{2k-1},x_{2k}}],1\leq
x_{1}<x_{2}<\ldots<x_{2n}<N\\!\right\\},$ (195) $\displaystyle
P^{(2n-1)}\\!\\!\\!\\!\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\\!\\!\mbox{Span}_{\mathbb{R}}\\!\\!\left\\{\\![\prod_{k=1}^{n-1}\\!f_{x_{2k-1},x_{2k}}f_{x_{2n-1},N}],1\leq
x_{1}\\!<\\!x_{2}\\!<\\!\ldots\\!<\\!x_{2n-1}\\!<\\!N\\!\right\\},$ (196)
$\displaystyle Q^{(2n)}$ $\displaystyle=$
$\displaystyle\mbox{Span}_{\mathbb{R}}\left\\{[\prod_{k=1}^{n}g_{x_{2k-1},x_{2k}}],1\leq
x_{1}<x_{2}<\ldots<x_{2n}<N\\!\right\\},$ (197) $\displaystyle
Q^{(2n-1)}\\!\\!\\!\\!\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\\!\\!\mbox{Span}_{\mathbb{R}}\\!\\!\left\\{\\![\prod_{k=1}^{n-1}\\!g_{x_{2k-1},x_{2k}}g_{x_{2n-1},N}],1\leq
x_{1}\\!<\\!x_{2}\\!<\\!\ldots\\!<\\!x_{2n-1}\\!<\\!N\\!\right\\},$ (198)

where $0\leq 2n\leq N-1$ or $1\leq 2n-1\leq N-1$. In words, the elements of
$P^{(k)}$ consist of equivalence classes of elements of $U^{(k)}$ of the form
$v\otimes\ldots$ with exactly $k$ jumps . The elements of $Q^{(k)}$ consist of
equivalence classes of elements of $V^{(k)}$ of the form $w\otimes\ldots$ with
exactly $k$ jumps.

Given such a characterisation, the dimensions of the $(P,Q)$-spaces are easy
to calculate:

$\dim P^{(k)}=\dim Q^{(k)}={N-1\choose k},\quad\mbox{for $0\leq k\leq N-1$.}$

which coincide with (187).

In fact, each of the invariant spaces $P^{(n)},Q^{(n)}$ for $0\leq n\leq N-1$
is irreducible. In particular, $V^{\otimes
N}=\oplus_{k=0}^{N-1}\left(P^{(k)}\oplus Q^{(k)}\right)$, which is a
representation of $V^{\otimes N}$ as the direct sum of irreducible
representations of $\mathbb{A}_{N}$. Namely, one has the following statement:

######  Proposition 7.

The generator algebra $\mathbb{A}_{N}$ is semi-simple. The representation of
$\mathbb{A}_{N}$ in $P^{(k)},Q^{(k)}$ is irreducible for $1\leq k\leq N-1$.

###### Proof.

It has been already established that the generators
$\\{\sigma_{k}\\}_{k=1}^{N-1}$ obey the relations (15,16,17) of (a
specialization of) type-A Hecke algebra with the parameter $Q=rl$. (Various
constants used to parameterise Hecke algebras are reviewed in the Appendix.)
Therefore, $\mathbb{A}_{N}$ is a quotient algebra of Hecke algebra. As
$r+l=1$, $Q$ takes values in $(0,\frac{1}{4}]$. This implies that the
parameter $q^{2}\in(0,1]$, where $q$ is related to $Q$ via (341). The Hecke
algebra over $\mathbb{R}$ generated by $\\{s_{i}\\}_{i=1}^{N-1}$ with
$q^{2}\in(0,1]$ (see (331) for the relations) is semi-simple, see [1], Theorem
$5.1$.111As far as Hecke algebras are concerned, the paper [1] generalises
classical results of [19] to arbitrary fields. Notice that there is a misprint
in the cited Theorem: the correct statement is obtained by the replacing $q$
with $q^{2}$.

Therefore, the generator algebra $\mathbb{A}_{N}$ is semi-simple as a quotient
of a semi-simple algebra.

Next, let us fix any $n:1\leq n\leq N-1$. It is sufficient to prove the
irreducibility of $P^{(n)}$, the result for $Q^{(n)}$ follows from the
symmetry $v\leftrightarrow w$, $l\leftrightarrow r$. The irreducibility will
be established by brute force by checking that any representation endomorphism
of $P^{(n)}$ is proportional to the identity operator. In this case, due to
the semi-simplicity of the algebra $\mathbb{A}_{N}$, the converse to Schur’s
lemma guarantees that $P^{(n)}$ is irreducible.

Let $U\in\mbox{End}(P^{(n)})$ be a representation isomorphism, a linear map
from $P^{(n)}$ to $P^{(n)}$ which commutes with the representation of
$\mathbb{A}_{N}$ in $P^{(n)}$. In other words,

$\displaystyle q_{x}U=Uq_{x},~{}1\leq x\leq N-1.$ (199)

It follows from (18), that the matrices of the generators of $\mathbb{A}_{N}$
in the basis (195) or (196) of $P^{(n)}$ have the following form:

$\displaystyle(q_{x})_{\mathbf{x},\mathbf{y}}=\sum_{k=1}^{n}\delta_{x,x_{k}}\prod_{p\neq
k}\delta_{y_{p},x_{p}}\left(\ell\delta_{y_{k},x+1}+r\delta_{y_{k},x-1}-\delta_{y_{k},x}\right),$
(200) $\displaystyle 1\leq x\leq N-1,\mathbf{x},\mathbf{y}\in W_{n}^{(N)}.$

Here $W_{n}^{(N)}=\\{1\leq x_{1}<x_{2}<\ldots x_{n}\leq N-1\\}$ and the
elements of $W_{n}^{(N)}$ are denoted by vectors, e.g.
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n})$. Let
$(U_{\mathbf{x},\mathbf{y}})_{\mathbf{x},\mathbf{y}\in W^{(N)}_{n}}$ be the
matrix of the linear operator $U$ in the basis (195) or (196). Using the fact
that $[g]=0$ for any $g\in U^{(n-1)}+W^{(n-1)}$, we can extend the definition
of $U$ by assuming that $U_{\mathbf{x},\mathbf{y}}=0$ if either $\mathbf{x}$
or $\mathbf{y}$ is not in $W^{(N)}_{n}$. The matrix form of (199) is

$\displaystyle\sum_{k=1}^{n}\delta_{x,x_{k}}\left(\ell
U_{\mathbf{x}+\bm{I}_{k},\mathbf{y}}+rU_{\mathbf{x}-\bm{I}_{k},\mathbf{y}}-U_{\mathbf{x},\mathbf{y}}\right)=\sum_{k=1}^{n}U_{\mathbf{x},\mathbf{y}}\mid_{y_{k}=x}\left(\ell\delta_{y_{k},x+1}+r\delta_{y_{k},x-1}-\delta_{y_{k},x}\right),$
(201)

where $\mathbf{x},\mathbf{y}\in W^{(N)}_{n}$ and $I_{k}$ is an $n$-dimensional
vector with the components $(\bm{I}_{k})_{\ell}=\delta_{k,\ell}$.

Let us pick any $x\neq x_{k}$. Then the left hand side of (201) vanishes and
one finds the following relation:

$\displaystyle\sum_{k=1}^{n}U_{\mathbf{x},\mathbf{y}}\mid_{y_{k}=x}\left(\ell\delta_{y_{k},x+1}+r\delta_{y_{k},x-1}-\delta_{y_{k},x}\right)=0.$

Next fix $m$ and set $y_{m}=x$. The only non-zero term in the above sum
corresponds to $k=m$ as for $k\neq m$,
$U_{\mathbf{x},\mathbf{y}}\mid_{y_{k}=x,y_{m}=x}=0$ due to
$\mathbf{y}\mid_{y_{k}=y_{m}=x}\notin W^{(N)}_{n}$. Therefore, the last
displayed equality reduces to $U_{\mathbf{x},\mathbf{y}}\mid_{y_{m}=x}=0$. We
proved that

$U_{\mathbf{x},\mathbf{y}}=0,$

provided that there is $m:~{}1\leq m\leq n$:
$y_{m}\notin\\{x_{1},x_{2},\ldots,x_{n}\\}$. If such $m$ does not exist, then
the components of $\mathbf{y}$ are a permutation of the components of
$\mathbf{x}$. But the components of $\mathbf{y}\in W^{(N)}_{n}$ are ordered,
therefore the only such permutation is the identity permutation and
$\mathbf{x}=\mathbf{y}$. We conclude that $U_{\mathbf{x},\mathbf{y}}=0$ for
any $\mathbf{x}\neq\mathbf{y}$, that is the matrix of $U$ is diagonal. Using
this diagonal Ansatz in (201), one finds:

$\displaystyle\sum_{k=1}^{n}\delta_{x,x_{k}}\prod_{p\neq
k}\delta_{y_{p},x_{p}}\left(\ell\delta_{y_{k},x_{k}+1}+r\delta_{y_{k},x_{k}-1}\right)U_{\mathbf{y},\mathbf{y}}$
$\displaystyle=$ $\displaystyle
U_{\mathbf{x},\mathbf{x}}\sum_{k=1}^{n}\delta_{x,x_{k}}\prod_{p\neq
k}\delta_{x_{p},y_{p}}\left(\ell\delta_{y_{k},x_{k}+1}+r\delta_{y_{k},x_{k}-1}\right).$

Equating the coefficients in front of similar products of $\delta$-functions
in the above identity shows that

$U_{\mathbf{x}+\bm{I}_{k},\mathbf{x}+\bm{I}_{k}}=U_{\mathbf{x},\mathbf{x}}=U_{\mathbf{x}-\bm{I}_{k},\mathbf{x}-\bm{I}_{k}}\quad\mbox{for
$1\leq k\leq n$.}$

Iterating the above identity we conclude that the diagonal matrix $U$ is
constant along the diagonal. Therefore, $U=cI$ for some constant $c$ and the
proposition is proved. ∎

Remark. At present we do not have a full set of relations obeyed the
generators $\\{q_{k}\\}_{k=1}^{N-1}$ characterising the generator algebra
$\mathbb{A}_{N}$. Basing on the dimensions of irreducible representations
calculated above we conjecture that $\mathbb{A}_{N}$ is isomorphic to the
centraliser algebra $\mbox{End}_{U_{q}(gl(1|1))}(V^{\otimes N})$ analyzed in
[5].

###  5.2 On exact solvability and representation theory

The model [ARW] on ${\mathbb{Z}}_{N}$ in the previous Section is an example of
interacting particle system where the generator algebra has ’small’
irreducible representations (”irreps”), growing polynomially with $N$, where
these irreps can be constructed using bases of duality functions, and where
these duality functions are sufficient to determine the fixed time law. It is
therefore natural to ask whether more generally the presence of ’small’ irreps
of the generator algebra signals the integrability of the model. We examine
three more models in this perspective, the final example indicating that the
presence of such small irreps does not seem to be sufficient for integrability
of the model on ${\mathbb{Z}}$. We used the symbolic algebra package Magma to
calculate the dimensions of the irreps for small $N$.

Consider the random reshuffle model [RM] from (102) on the finite lattice
${\mathbb{Z}}_{N}$. Magma experiments for small $N$ suggest that all irreps of
the corresponding generator algebra $\mathbb{A}$ are one-dimensional. This can
be easily confirmed using duality functions: the products of particle
indicators constitute a complete set of duality functions. Indeed for
$b\in\\{0,1\\}^{{\mathbb{Z}}_{N}}$ let $|b|_{1}:=\sum_{k=1}^{N}b_{k}$ be its
Hamming weight; let $m_{b}$ be the test function on $\eta\in{\mathbb{Z}}_{N}$
defined by $m_{b}(\eta)=\prod_{k:b_{k}=1}\eta_{k}$; and let
$M_{t}(b)={\mathbb{E}}[m_{b}(\eta_{t})]$ be the corresponding product moment.
A generator calculation shows that

$\partial_{t}M_{t}(b)=\lambda(b)M_{t}(b)+\sum_{c\in{\mathbb{Z}}_{N}:|c|_{1}<|b|_{1}}\mu(b,c)M_{t}(c),$
(202)

where $\lambda$ and $\mu$ are functions on ${\mathbb{Z}}_{N}$ and
${\mathbb{Z}}_{N}\times{\mathbb{Z}}_{N}$ whose explicit form we do not need.
In other words, the product moments satisfy closed linear inhomogeneous ODE’s
with the right hand side determined by product moments of lower weights. We
now check that this structure meshes with the irreps of the generator algebra.
For any $b\in{\mathbb{Z}}_{N}$ let

$g_{b}:=a_{1}\otimes a_{2}\otimes\ldots\otimes a_{N}\in V^{\otimes N},$

where $a_{i}=(1,1)^{T}$ if $b_{i}=0$ and $a_{i}=(1,0)^{T}$ if $b_{i}=1$. Then
$g_{b}$ is the image of the duality function $m_{b}$ under the isomorphism
between test functions and $V^{\otimes N}$ (as in Section 2.1 but restricted
to $N$ sites). Define $\overline{B}_{b}\subset{\mathbb{Z}}_{N}$ to be the set
of binary strings which contains contains $b$ as well as all the strings $c$
such that $c_{k}\leq b_{k}$ for $1\leq k\leq N$. Let
$B_{b}:=\overline{B}_{b}\setminus\\{b\\}$. Define

$\overline{W}_{b}:=\mbox{Span}_{\mathbb{R}}\\{m_{c}:c\in\overline{B}_{b}\\},\quad
W_{b}:=\mbox{Span}_{\mathbb{R}}\\{m_{c}:c\in B_{b}\\},\quad\mbox{for
$b\in{\mathbb{Z}}_{N}$.}$

It follows from (202) that the spaces $W_{b}$ and $\overline{W}_{b}$ are
invariant with respect to the action of the generator algebra. By
construction, $W_{b}\subset\overline{W}_{b}$. So the generator algebra acts on
the quotient space $P_{b}:=\overline{W}_{b}/W_{b}$ for $b\in{\mathbb{Z}}_{N}$
and $\dim P_{b}=1$. Thus we have constructed $2^{N}$ one-dimensional irreps of
the random reshuffle algebra using the duality functions.

An example coming from the opposite end of the spectrum is served by the
contact process defined by the two-site generator of the form

$\displaystyle q=\sigma-I=\left(\begin{array}[]{cccc}-2a&a&a&0\\\
b&-a-b&0&a\\\ b&0&-a-b&a\\\ 0&0&0&0\end{array}\right).$

Here $a$ is the recovery rate and $b$ is the infection rate. The contact
process is self dual, and the duality functions, indexed by subsets of
${\mathbb{Z}}$, have been used for studying various properties (such as
ergodic behaviour). However, the contact process is not expected to be
integrable and we are not aware of a system of duality functions leading to
explicit formulae. This lack of the integrability seems to mesh well with the
irreps of the contact process: Magma experiments for small $N$ suggest that
its generator algebra has just two irreps in $V^{\otimes N}$, the trivial one-
dimensional representation and a second representation of dimension $2^{N}-1$.
We expect a similar picture to be the generic situation for a typical
stochastic $\sigma$.

Our final example illustrates that the presence of small irreps does always
lead to useful duality functions. Note that the generator algebra of any
interacting particle system on ${\mathbb{Z}}_{N}$ such that the number of
particle is either conserved of decreases has irreps of dimensions growing
polynomially with system size, corresponding to the subspaces of any given
number of particles. However, we do not expect all such systems to be
integrable. For example the dimer model [DM] can be mapped to an inhomogeneous
symmetric exclusion model (see Section 4.5) where particle numbers are
conserved. It is not surprising then that MAGMA shows irreps of polynomial
size. However, the only duality functions we managed to find for this model
are given by the indicators $f_{b}(\eta)=\mathbbm{1}(\eta=b)$ for
$b\in\\{0,1\\}^{{\mathbb{Z}}_{N}}$. The expectations of $f_{b}(\eta_{t})$’s
are just the transition probabilities. These do obey closed dual equations
(the Kolmogorov equation), but become trivial in $N\rightarrow\infty$ limit
corresponding to the infinite model. Indeed, for a system with infinitely many
particles the transition density ${\mathbb{E}}[f_{b}(\eta_{t})]$ is
identically zero for any realisation $b$ with infinitely many particles. We do
not know how to characterise the distribution of the infinite dimer model. In
comparison, for [ASEP], where particle numbers are also preserved, there was
an alternative useful set of duality functions, the staircase functions, that
did extend usefully to (some) infinite systems.

###  5.3 Co-ordinate representation of a Hecke algebra

The duality functions studied above have two important properties: firstly,
they appear as a basis of $T(\Omega)$, for which the matrices of the two-site
generators $\sigma_{n}$, $n\in{\mathbb{Z}}$ are block lower-triangular.
Secondly, the action of the generator on these functions is modelled by
certain difference operators acting on the spatial arguments. This second
property is important from the point of view of Markov duality. More
pragmatically, as a consequence of the second property the expectations of
duality functions
${\mathbb{E}}_{\eta_{0}}[f_{x_{1},x_{2},\ldots,x_{n}}^{(n)}(\eta_{t}))]$
satisfy linear evolution equations with respect to independent variables
$t\in\mathbb{R}_{+},x_{1},\ldots x_{n}\in{\mathbb{Z}}$. For example, for the
reaction-diffusion models on ${\mathbb{Z}}$ it is easy to guess the solution
to these equations in terms of Pfaffians built out of
${\mathbb{E}}_{\eta_{0}}[f_{x,y}^{(2)}(\eta_{t})]$, $x,y\in{\mathbb{Z}}$. If
however we place our particle system on a circle ${\mathbb{Z}}_{N}$ for some
$N<\infty$ rather than the integer lattice, the naive Pfaffian ansatz fails.
It is still unknown what the law of our reaction-diffusion systems on a circle
is, so it is reasonable to hope that an algebraic structure of the evolution
operator will be useful for determining such a law. An algebraic
interpretation of the duality functions for models in Hecke class is that of
intertwiners between two representations of Hecke algebra: in the space
$T(\Omega)$ of test functions and the space of functions of several spatial
variables. This implies that the relevant evolution operators belong to (a
closure of) a representation of Hecke algebra, which in turn could enable a
systematic search for a basis diagonalizing the evolution operators using the
corresponding representation theory. Notice, that the role of Markov duality
functions as intertwiners has already been emphasized by many authors, see for
example [18].

Our aim here is modest: we will just build an explicit co-ordinate
representation of Hecke algebras intertwined with the representation in
$T(\Omega)$ we started with. This representation seems to be different from
other known representation of Hecke generators using difference operators, e.
g. the polynomial representation used to construct dualities for multi-species
asymmetric exclusion models in [12]. The study of its properties and
applications to interacting particle systems is a matter for future research.

Let us start with the most basic definition: let $\pi_{1},\pi_{2}$ be two
linear representations of an associative algebra $\mathbb{A}$ in linear spaces
$V_{1}$, $V_{2}$ correspondingly. A linear map $U:V_{1}\rightarrow V_{2}$ is
said to intertwine $\pi_{1}$ with $\pi_{2}$ if for any $a\in\mathbb{A}$,

$\displaystyle U\circ\pi_{1}(a)=\pi_{2}(a)\circ U.$ (204)

In other words, the diagram shown in Figure 2 is commutative.

Figure 2: If the diagram above is commutative, the map $U:V_{1}\rightarrow
V_{2}$ is called an intertwiner.

Assume that $V_{1},V_{2}$ are $L_{2}$ spaces of functions on some spaces
$\Omega_{1}$, $\Omega_{2}$ parametrised by co-ordinates $x$ and $\eta$
correspondingly. Then the relation (204) takes the form

$\displaystyle\pi_{2}(a)U(\eta,x)=(\pi_{1}(a))^{\dagger}U(\eta,x),~{}\forall
x\in\Omega_{1},\eta\in\Omega_{2}.$ (205)

where $U(\eta,x)$ is the kernel of the map $U:V_{1}\rightarrow V_{2}$ in the
chosen basis, the operator $\pi_{1}(a)$ acts on the $x$ co-ordinates of
$U(\eta,x)$, the operator $\pi_{2}(a)$ \- on the $\eta$ co-ordinates. The
adjoint operator $(\pi_{1}(a))^{\dagger}$ is defined with respect to the
$L_{2}$ inner product on $V_{1}$.

There is a useful application of (204) provided the intertwiner $U$ satisfies
some non-degeneracy conditions. Let
$\\{a_{1},a_{2},\ldots,a_{n}\\}\subset\text{End}(V_{2})$. Suppose that
operators $a$ satisfy a polynomial relation $R(a_{1},a_{2},\ldots,a_{n})=0$.
Assume that
$\\{\hat{a}_{1},\hat{a}_{2},\ldots,\hat{a}_{n}\\}\subset\text{End}(V_{1})$ are
such that

$\displaystyle
a_{k}U(\eta,x)=\hat{a}_{k}^{\dagger}U(\eta,x),~{}k=1,2,\ldots,n.$

Finally, suppose that the set $\\{U(\eta,\cdot)\\}_{\eta\in\Omega_{2}}$ spans
$V_{1}$. Then $R(\hat{a}_{1},\hat{a}_{2},\ldots,\hat{a}_{n})=0$. In other
words, the set of relations satisfied by operators $\\{a_{k}\\}_{k=1}^{n}$ is
a subset of relations satsfied by the operators $\\{\hat{a}_{k}\\}_{k=1}^{n}$.

Using the above elementary algebraic preliminaries it is easy to prove the
following statement:

######  Lemma 8.

Let $L_{2}({\mathbb{Z}})$ be the space of square summable functions on
${\mathbb{Z}}$. Define the following set of linear operators on
$L_{2}({\mathbb{Z}})$:

$\displaystyle\hat{q}_{x}=\mathbbm{1}_{x}\Delta,~{}x\in{\mathbb{Z}},$ (206)

where $\Delta=rD+lD^{-1}-1$ is the discrete Laplacian. Then
$\\{\hat{q}_{x}\\}_{x\in{\mathbb{Z}}}$ generate a representation of Temperley-
Lieb algebra,

$\displaystyle\left\\{\begin{array}[]{ll}\hat{q}_{i}\hat{q}_{j}=\hat{q}_{j}\hat{q}_{i},&|i-j|\geq
2,~{}i,j\in{\mathbb{Z}}\\\ \hat{q}_{i}\hat{q}_{i\pm
1}\hat{q}_{i}-Q\hat{q}_{i}=0,&i\in{\mathbb{Z}}\\\
\hat{q}_{i}^{2}=-\hat{q}_{i},&i\in{\mathbb{Z}}\end{array}\right.,$ (210)

where $Q=rl$.

A multi-dimensional generalisation is as follows. Let
$W^{n}=\\{z_{1}<z_{2}<\ldots<z_{n}:z_{k}\in{\mathbb{Z}},1\leq k\leq n\\}$. Let
$L_{2}(W^{n})$ be the space of square-summable functions on $W^{n}$ subject to
the following boundary conditions: if $f\in L_{2}(W^{n})$, then

$\displaystyle
D_{y}f(\cdot,\ldots,\cdot,y_{i}=y,y_{i+1}=y,\cdot,\ldots,\cdot)=0.$ (211)

In other words, the function $f\mid_{y_{i}=y_{i+1}=y}$ does not depend on $y$.
Then

######  Lemma 9.

The following operators acting on $L_{2}(W^{n})$, $n\geq 1$, generate a
representation of Hecke algebra $H_{\infty}$ defined in the Appendix:

$\displaystyle\hat{q}_{x}=\sum_{k=1}^{n}\mathbbm{1}_{x}^{(k)}\Delta_{k},~{}x\in{\mathbb{Z}},$
(212)

where $\Delta_{k}$ is the discrete Laplacian acting on the $k$-th co-ordinate
of a function on $L_{2}(W^{n})$; if $y=(y_{1},y_{2},\ldots,y_{n})\in W^{n}$,
then $\mathbbm{1}_{x}^{(k)}(y)=\mathbbm{1}_{x}(y_{k})$. Namely,

$\displaystyle\left\\{\begin{array}[]{ll}\hat{q}_{i}\hat{q}_{j}=\hat{q}_{j}\hat{q}_{i},&|i-j|\geq
2,~{}i,j\in{\mathbb{Z}}\\\
\hat{q}_{i}\hat{q}_{i+1}\hat{q}_{i}-Q\hat{q}_{i}=\hat{q}_{i+1}\hat{q}_{i}\hat{q}_{i+1}-Q\hat{q}_{i+1},&i\in{\mathbb{Z}}\\\
\hat{q}_{i}^{2}=-\hat{q}_{i},&i\in{\mathbb{Z}}\end{array}\right.,$ (216)

where $Q=rl$.

The proof of the above lemmas is a straightforward exercise given the
following remarks:

  1. 1.

Let $f:\Omega\times Z\rightarrow\mathbb{R}$: $(\eta,x)\mapsto
f_{x}(\eta)=(-1)^{\sum_{i\leq x}\eta_{i}}$. 222For simplicity we assume for
this Section that the elements of $\Omega$ have finite Hamming weight, which
makes $f$ well defined. Then it follows from (18), (20) that
$q_{y}f_{x}(\eta)=\hat{q}^{\dagger}_{y}f_{x}(\eta)$, for all
$y\in{\mathbb{Z}}$, $(\eta,x)\in\Omega\times{\mathbb{Z}}$ where
$\hat{q}_{x}^{\dagger}=\mathbbm{1}_{x}\Delta$.

  2. 2.

$L_{2}({\mathbb{Z}})$ is in the span of
$\\{f_{\cdot}(\eta)\\}_{\eta\in\Omega}$:

let $\eta_{y}=(\ldots,\eta_{y-3},\eta_{y-2},\eta_{y-1},\eta_{y},0,0\ldots)$
and
$\eta^{\prime}_{y}=(\ldots,\eta_{y-3},\eta_{y-2},1-\eta_{y-1},1-\eta_{y},0,0\ldots)$.
Then

$\displaystyle f_{x}(\eta_{y})-f_{x}(\eta^{\prime}_{y})=\pm
2\mathbbm{1}_{y-1}(x),\quad\mbox{for $x\in{\mathbb{Z}}$.}$

  3. 3.

So the algebraic argument given above implies that the operators
$\\{\hat{q}\\}_{x\in{\mathbb{Z}}}$ satisfy the relations of Hecke algebra. The
fact that each side of the ternary relation is zero can be confirmed using an
exact computation. Finally, the relations of both Hecke and Temperley-Lieb
algebras are invariant with respect to conjugation and the statement of Lemma
8 follows.

  4. 4.

The statement of Lemma 9 can be confirmed using a similar argument. The claim
can be verified also by a direct computation based on the fact that the
operators
$\hat{q}_{x}^{(k)}:=\mathbbm{1}_{x}^{(k)}\Delta_{k},x\in{\mathbb{Z}},1\leq
k\leq n$ satisfy Temperley-Lieb relations (210) for coinciding values of the
superscript. For different values of the superscript, the operators commute
and moreover $\hat{q}_{x_{1}}^{(k_{1})}\hat{q}_{x_{2}}^{(k_{2})}=0$ for