# Perturbative Symmetry Approach for Differential-Difference Equations.

Alexander V. Mikhailov+∗, Vladimir S. Novikov† and Jing Ping Wang&
$+$School of Mathematics, University of Leeds, UK
$*$P. G. Demidov Yaroslavl State University, RF
$\dagger$ School of Mathematics, Loughborough University, UK
$\&$ School of Mathematics, Statistics and Actuarial Science, University of
Kent, UK

###### Abstract

We propose a new method for solution of the integrability problem for
evolutionary differential-difference equations of arbitrary order. It enables
us to produce necessary integrability conditions, to determine whether a given
equation is integrable or not, and to advance in classification of integrable
equations. In this paper we define and develop symbolic representation for the
difference polynomial ring, difference operators and formal series. In order
to formulate necessary integrability conditions, we introduce a novel quasi-
local extension of the difference ring. It enables us to progress in
classification of integrable differential-difference evolutionary equations of
arbitrary order. In particular, we solve the problem of classification of
integrable equations of order $(-3,3)$ for the important subclass of quasi-
linear equations and produce a list of 17 equations satisfying the necessary
integrability conditions. For every equation from the list we present an
infinite family of integrable higher order relatives. Some of the equations
obtained are new.

##  1 Introduction

The problem to determine whether a given equation is integrable (testing for
integrability) and much more difficult problem to give an exhaustive
description of all integrable cases for a certain type of equations up to
invertible transformations (the classification problem) are central in the
theory of integrable systems. In this paper we study evolutionary
differential-difference equations

$u_{t}=F(u_{p},\ldots,u_{q})$ (1)

for a function $u=u(n,t)$ of one discrete variable $n\in\mathbb{Z}$ and a
continuous independent variable $t\in\mathbb{C}$. Here we use the standard
notations

$\displaystyle u_{t}=\partial_{t}(u),\quad
u_{k}={\mathcal{S}}^{k}u(n,t)=u(n+k,t)$

and ${\mathcal{S}}$ is the shift operator. Existence of an infinite algebra of
(infinitesimal) symmetries of equation (1) we take as the definition of its
integrability. There are many alternative views on integrability, including
existence of multi-soliton solutions, “regular dynamics”, Painlevé property of
finite dimensional reductions, integrable continuous limits, etc., which are
useful but difficult to formalise or inconclusive. The symmetry approach
provides us with a rigorous framework enabling to formulate necessary
integrability conditions which are suitable for solution of the classification
problem for equations of arbitrary order.

In the case of partial differential equations (PDEs) the symmetry approach
proved to be successful for classification of evolutionary equations and
system of equations [1]-[3]. Its further development, the perturbative
symmetry approach for PDEs, based on the natural degree grading structure and
symbolic representation of the differential ring [4]-[7] enabled us to extend
the method to nonlocal and/or non-evolutionary equations such as the Benjamin-
Ono equation and the Camassa-Holm equation [8, 9, 10]. Symbolic representation
was successfully used for global classification of integrable scalar
homogeneous evolutionary equations [6]. We refer to, for example, the review
paper [11] and the recent book [12] for detail discussion of classification
problems for integrable PDEs and related publications.

The classification of integrable differential-difference equations has not
enjoyed the same success as for partial differential equations so far. The
first classification result was obtained by Yamilov in 1983 [13] for general
differential-difference equations of order $(-1,1)$:

$u_{t}=f(u_{-1},u,u_{1}),\qquad\frac{\partial f}{\partial u_{1}}\neq
0,\qquad\frac{\partial f}{\partial u_{-1}}\neq 0.$

Yamilov derived and used for classification necessary conditions for existence
of higher order generalised symmetries and conservation laws. Since then this
method has been developed further and used for the classification of other
important types of differential-difference equations, including Toda and
relativistic Toda-type equations [14].

Recently, Garifullin, Yamilov and Levi gave a partial classification result
for the five-point differential-difference equations [15]. They produced a
complete list of quasi-linear equations of order $(-2,2)$, i.e. equations of
the form

$u_{t}=A(u_{-1},u,u_{1})u_{2}+B(u_{-1},u,u_{1})u_{-2}+C(u_{-1},u,u_{1}),$ (2)

which admit a symmetry of order $(-4,4)$. Their impressive classification list
contains 31 equations up to autonomous point transformations, including some
new equations, which are all proved to be integrable by the following-up
study. Their list contains equations of two types, namely equations which
admit symmetries of orders $(-n,n)$ for all $n\in\mathbb{N}$, and equations
which admit only even order of symmetries $(-2n,2n),n\in\mathbb{N}$. Thus the
resulting list depends on the assumption on the order of a symmetry that
equation (2) admits. This, list would represent a complete classification of
integrable equations, if it is shown that any integrable equation (2)
necessarily admits a symmetry of order $(-4,4)$. The latter is a challenging
problem which cannot be tackled by the methods used in [15].

To formulate integrability conditions which are suitable for any lacunae in
the sequence of symmetries, we develop here a perturbative symmetry approach
for differential-difference equations. The adaptation of methods previously
used for PDEs is far not straightforward. It requires building a symbolic
representation of difference rings and rings of difference operators, quasi-
local extensions of rings and formal pseudo-difference series with quasi-local
coefficients. For a differential-difference equation admitting an infinite
algebra of symmetries Adler proved existence of a formal recursion operator
[16]. We define a canonical formal recursion operator and for an integrable
equation prove its existence and uniqueness. In symbolic representation its
coefficients can be found explicitly for any equation, but if the equation
admits an infinite algebra of symmetries then the coefficients must be quasi-
local. Quasi-locality of the coefficients of the canonical formal recursion
operator are universal integrability conditions for differential-difference
equations of arbitrary orders. We demonstrate the power of our method by
solving the classification problem for an important family of quasi-linear
differential-difference equations of order $(-3,3)$.

The paper starts with basic algebraic setting for the study of evolutionary
differential-difference equations and algebras of their symmetries. In Section
2 we discuss different grading for the difference polynomial ring and its
evolutionary derivations, difference operators, and formal pseudo-difference
series. An introduction to the symmetry approach is given in Section 3.
Approximate symmetries and approximate integrability are defined in Section
3.2. In Section 4, we define symbolic representation of a difference
polynomial ring, difference operators and formal series and formulate criteria
of approximate integrability using symbolic representation. For a given
evolutionary differential-difference equation, either polynomial or
represented by a formal series, we give a recursive formula for the
coefficients of its symmetries (Theorem 2). The coefficients are uniquely
determined by the linear part of the symmetry. This result can be used to test
the existence of fixed order symmetries and to derive the necessary
integrability conditions if the linear part of a symmetry is known.

For integrable PDEs the coefficients of a formal recursion operator must
belong to differential field. These necessary integrability conditions are
independent of possible lacunae in the hierarchy of symmetries. The proof is
based on the existence of fractional powers of formal pseudo-differential
series with coefficients in the differential field [1]-[3]. In the case for
difference operators or difference formal series, fractional powers with
coefficients in the difference ring (or field) may not exist [17]. It
motivates us to introduce a quasi-local extension of the difference ring
(Section 5.1). Then the universal integrability conditions can be formulated
as the conditions on the coefficients of the canonical formal recursion
operator: the coefficients must be quasi-local (Section 5.2).

In Section 6 we give a complete classification integrable differential-
difference equations of the form

$u_{t}=u_{3}f(u_{2},u_{1},u)-u_{-3}f(u_{-2},u_{-1},u)+g(u_{2},u_{1},u)-g(u_{-2},u_{-1},u),\qquad
f(0,0,0)\neq 0,$ (3)

where $f,g$ are polynomial functions or formal series. We list only equations
(3) which do not admit symmetries of order $(-1,1)$ and $(-2,2)$. The latter
are known equations, since they are members of well known integrable
hierarchies studied in [14, 15]. Our list consists on 17 equations satisfying
necessary integrability conditions (Theorem 5). We claim that the list is
complete and have shown that all equations from the list are integrable. They
either can be reduced to known integrable equations by difference
substitutions (not invertible), or admit Lax representations. To the best of
our knowledge, the list contains two genuinely new equations:

$\displaystyle u_{t}$ $\displaystyle=$
$\displaystyle(u^{2}+1)(u_{3}\sqrt{u_{1}^{2}+1}\sqrt{u_{2}^{2}+1}-u_{-3}\sqrt{u_{-1}^{2}+1}\sqrt{u_{-2}^{2}+1}).$
(4) $\displaystyle u_{t}$ $\displaystyle=$ $\displaystyle
u(u_{2}u_{3}+uu_{1}-uu_{-1}-u_{-2}u_{-3})-u(u_{2}+u_{1}-u_{-1}-u_{-2}),$ (5)

For each of these $17$ equations, we found an infinite family of integrable
equations of arbitrary high order. For instance, equation (4) is a member of
the family of integrable equations

$\displaystyle
u_{t}=(1+u^{2})(u_{n}\prod_{k=1}^{n-1}\sqrt{1+u_{k}^{2}}-u_{-n}\prod_{k=1}^{n-1}\sqrt{1+u_{-k}^{2}}),\quad
n\in\mathbb{N}.$ (6)

Equation (4) is the $3$–relative (i.e. $n=3$) of this family. The $2$–relative
($n=2$) was discovered in classification of $(-2,2)$ order integrable
equations [15] and $1$–relative is the well known modified Volterra equation.
For any two distinct values of $k$ the corresponding $k$–relative non-linear
equations from the same family are not compatible. In Section 6.3 we have
shown that equation (6) has a Lax representation $L_{t}=[A,L]$ with

$\displaystyle L=Q^{-1}P,\quad A=L_{+}-L_{+}^{\dagger},\quad
Q=u-u_{1}\sqrt{1+u^{2}}\ {\mathcal{S}}^{-1},\quad P=\left(u\sqrt{1+u_{1}^{2}}\
{\mathcal{S}}-u_{1}\right){\mathcal{S}}^{n-1},$

where $L_{+}$ is the part with non-negative powers of ${\mathcal{S}}$ in the
Laurent formal difference series $L$ and $\dagger$ denotes the formal adjoint
operator.

We conclude the paper with a short summary and discussion. In particular, we
include Adler’s Lax representation (with his kind permission [18]) for the
integrable family of equations which includes equation (5).

##  2 Derivations, difference operators and formal series

The main objects of our study are evolutionary differential-difference
equations and algebras of their symmetries. Although the phase space of such
systems is infinite dimensional, each equation of the system relates a finite
number of dynamical variables which we will treat as independent. In order to
develop a rigorous theory we will use elements of the theory of difference
rings, difference operators and formal series, including their symbolic
representation. It will also enable us to introduce quasi-local extensions of
the difference rings and formulate verifiable integrability conditions for
differential-difference equations.

###  2.1 Difference ring and its evolutionary derivations

We define the polynomial ring ${\mathcal{R}}=\mathbb{C}[{\bf u}]$ and the
corresponding field of fractions ${\mathcal{F}}=\mathbb{C}({\bf u})$ of the
infinite set of (commutative) variables ${\bf
u}=\\{u_{n}\,|\,n\in\mathbb{Z}\\}$. We will often omit index zero at $u_{0}$.
The set of all monomials
${\mathcal{M}on({\mathcal{R}})}=\\{u_{n_{1}}^{m_{1}}u_{n_{2}}^{m_{2}}\cdots
u_{n_{k}}^{m_{k}}\,|\,n_{i}\in\mathbb{Z},\ m_{i}\in\mathbb{Z}_{\geqslant
0}\\}$ is the additive basis in ${\mathcal{R}}$.

There is a natural automorphism ${\mathcal{S}}$ of the field ${\mathcal{F}}$,
which we call the shift operator, defined as

${\mathcal{S}}:a(u_{k},\ldots,u_{r})\mapsto
a(u_{k+1},\ldots,u_{r+1}),\quad{\mathcal{S}}:\alpha\mapsto\alpha,\qquad
a(u_{k},\ldots,u_{r})\in{\mathcal{F}},\ \ \alpha\in\mathbb{C}.$

The field ${\mathcal{F}}$ equipped with the automorphism ${\mathcal{S}}$ is a
difference field.

The reflection ${\mathcal{T}}$ of the lattice $\mathbb{Z}$ defined by

${\mathcal{T}}:a(u_{k},\ldots,u_{r})\mapsto
a(u_{-k},\ldots,u_{-r}),\quad{\mathcal{T}}:\alpha\mapsto\alpha,\qquad
a(u_{k},\ldots,u_{r})\in{\mathcal{F}},\ \ \alpha\in\mathbb{C},$

is another automorphism of ${\mathcal{F}}$. The composition
${\mathcal{S}}{\mathcal{T}}{\mathcal{S}}{\mathcal{T}}=\mbox{Id}$ is the
identity map. Thus the automorphisms ${\mathcal{S}},{\mathcal{T}}$ generate
the infinite dihedral group $\mathbb{D}_{\infty}$ and the infinite cyclic
subgroup generated by ${\mathcal{S}}$ is normal in $\mathbb{D}_{\infty}$. The
automorphism ${\mathcal{T}}$ defines a $\mathbb{Z}_{2}$ grading of the
difference field ${\mathcal{F}}$:

${\mathcal{F}}={\mathcal{F}}_{0}\oplus{\mathcal{F}}_{1},\qquad{\mathcal{F}}_{0}\cdot{\mathcal{F}}_{0}={\mathcal{F}}_{0},\
\ {\mathcal{F}}_{0}\cdot{\mathcal{F}}_{1}={\mathcal{F}}_{1},\ \
{\mathcal{F}}_{1}\cdot{\mathcal{F}}_{1}={\mathcal{F}}_{0},$ (7)

where
${\mathcal{F}}_{k}=\\{a\in{\mathcal{F}}\,|\,{\mathcal{T}}(a)=(-1)^{k}a\\}$.
The ring ${\mathcal{R}}\subset{\mathcal{F}}$ inherits the same grading
${\mathcal{R}}={\mathcal{R}}_{0}\oplus{\mathcal{R}}_{1}$.

A derivation $\partial$ in the field ${\mathcal{F}}$ is a $\mathbb{C}$–linear
map $\partial\,:\,{\mathcal{F}}\mapsto{\mathcal{F}}$ satisfying Leibniz’s law

$\partial(a\cdot b)=\partial(a)\cdot b+a\cdot\partial(b),\qquad
a,b\in{\mathcal{F}}.$

A set of all derivations in ${\mathcal{F}}$ is denoted
${\mathcal{D}er({\mathcal{F}})}$. Let
$\partial,\partial^{\prime}\in{\mathcal{D}er({\mathcal{F}})}$ be two
derivations in ${\mathcal{F}}$ then their commutator
$[\partial,\partial^{\prime}]\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\partial\circ\partial^{\prime}-\partial^{\prime}\circ\partial\in{\mathcal{D}er({\mathcal{F}})}$
is also a derivation. Any three derivations
$\partial,\partial^{\prime},\partial^{\prime\prime}\in{\mathcal{D}er({\mathcal{F}})}$
satisfy the Jacobi identity

$[\partial,[\partial^{\prime},\partial^{\prime\prime}]]+[\partial^{\prime},[\partial^{\prime\prime},\partial]]+[\partial^{\prime\prime},[\partial,\partial^{\prime}]]=0,$

and therefore ${\mathcal{D}er({\mathcal{F}})}$ is a Lie algebra over
$\mathbb{C}$. A formal sum

$X=\sum_{n\in\mathbb{Z}}f^{(n)}\frac{\partial}{\partial u_{n}},\qquad
f^{(n)}\in{\mathcal{F}}$ (8)

is a derivation in ${\mathcal{F}}$. Its action on
$X:{\mathcal{F}}\mapsto{\mathcal{F}}$ is well defined, since any element
$a\in{\mathcal{F}}$ depends on a finite subset of variables, and thus the sum
$X(a)$ contains only a finite number of non-vanishing terms.

Partial derivatives $\frac{\partial}{\partial
u_{i}}\in{\mathcal{D}er({\mathcal{F}})}$ are commuting derivations satisfying
the conditions

${\mathcal{S}}\frac{\partial}{\partial u_{i}}=\frac{\partial}{\partial
u_{i+1}}{\mathcal{S}},\qquad{\mathcal{T}}\frac{\partial}{\partial
u_{i}}=\frac{\partial}{\partial u_{-i}}{\mathcal{T}}.$ (9)

A derivation $X\in{\mathcal{D}er({\mathcal{F}})}$ is said to be evolutionary
if it commutes with the shift operator ${\mathcal{S}}$. For an evolutionary
derivation it follows from the condition
$X\circ{\mathcal{S}}={\mathcal{S}}\circ X$ and (9) that all coefficients
$f^{(n)}$ in (8) can be expressed $f^{(n)}={\mathcal{S}}^{n}(f)$ in terms of
one element $f\in{\mathcal{F}}$, which is called the characteristic of the
evolutionary derivation. We will use notation

$X_{f}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\sum_{i\in\mathbb{Z}}{\mathcal{S}}^{i}(f)\frac{\partial}{\partial
u_{i}}.$ (10)

for the evolutionary derivation corresponding to the characteristic $f$.

Evolutionary derivations form a Lie subalgebra of
${\mathcal{D}er({\mathcal{F}})}$. Indeed,

$\begin{array}[]{l}\alpha X_{f}+\beta X_{g}=X_{\alpha f+\beta
g},\qquad\alpha,\beta\in\mathbb{C},\\\
\phantom{}[X_{f},X_{g}]=X_{[f,g]},\end{array}$

where $[f,g]\in{\mathcal{F}}$ denotes the Lie bracket

$[f,g]=X_{f}(g)-X_{g}(f),$ (11)

which is bi-linear, skew-symmetric and satisfying the Jacobi identity. Thus
${\mathcal{F}}$ is a Lie algebra with Lie bracket defined by (11).
Evolutionary derivations with characteristics belonging to the ring
${\mathcal{R}}$ form a subalgebra of ${\mathcal{D}er({\mathcal{R}})}$.

The reflection ${\mathcal{T}}$ acts naturally on evolutionary derivations

${\mathcal{T}}:\,X_{f}\mapsto X_{{\mathcal{T}}(f)}={\mathcal{T}}\cdot
X_{f}\cdot{\mathcal{T}}\,$

The polynomial ring ${\mathcal{R}}$ is degree graded

${\mathcal{R}}=\bigoplus\limits_{n=0}^{\infty}{\mathcal{R}}^{n},$ (12)

where ${\mathcal{R}}^{n}$ is the set of all homogeneous polynomials of degree
$n$. The degree grading (12) and ${\mathcal{T}}$–grading (7) are compatible
and thus ${\mathcal{R}}$ is a bi-graded ring

${\mathcal{R}}=\bigoplus\limits_{n=0}^{\infty}{\mathcal{R}}^{n}_{0}\oplus{\mathcal{R}}^{n}_{1},\quad{\mathcal{R}}^{n}_{k}={\mathcal{R}}^{n}\cap{\mathcal{R}}_{k}\,.$
(13)

The homogeneous parts ${\mathcal{R}}^{n}_{k}$ are additive groups and
${\mathcal{R}}^{n}_{k}{\mathcal{R}}^{m}_{\ell}={\mathcal{R}}^{n+m}_{(k+\ell)\mod
2}$. It follows from the definition of the Lie bracket (11) that the Lie
algebra ${\mathcal{R}}$ is also degree graded and bi-graded

$[{\mathcal{R}}^{n},{\mathcal{R}}^{m}]\subset{\mathcal{R}}^{n+m-1}\,,\quad[{\mathcal{R}}^{n}_{p},{\mathcal{R}}^{m}_{q}]\subset{\mathcal{R}}^{n+m-1}_{(p+q)\mod
2}.$ (14)

Every element $f$ of the polynomial ring ${\mathcal{R}}$ can be uniquely
represented as a sum of homogeneous components $f=\sum_{k\geqslant 0}f^{(k)},\
f^{(k)}\in{\mathcal{R}}^{k}$ (some of the components may be equal to zero).
The selection of the $k$–th homogeneous component $f^{(k)}$ is a projection
$\pi_{k}\,:\,{\mathcal{R}}\mapsto{\mathcal{R}}^{k}$ defined by

$\pi_{k}(f)=\pi_{k}\left(\sum_{i\geqslant 0}f^{(i)}\right)=f^{(k)}.$ (15)

Obviously $\pi_{k}\pi_{s}=\delta_{s,k}\pi_{k}$. Similarly one can define
projectors to bi-graded homogeneous components.

###  2.2 Difference, pseudo-difference operators and formal series

Let $a(u_{n},\ldots,u_{m})$ be a non-constant element of ${\mathcal{F}}$, and
we assume that $n\leqslant m$ are the minimal and the maximal index
respectively in the sequence of its arguments. Then $X_{f}(a)$ can be
represented by a finite sum

$X_{f}(a)=\sum_{i=n}^{m}\frac{\partial a}{\partial
u_{i}}{\mathcal{S}}^{i}(f)=a_{*}[f],$

where

$a_{*}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\sum_{i=n}^{m}\frac{\partial
a}{\partial u_{i}}{\mathcal{S}}^{i}$ (16)

is the Fréchet derivative of $a(u_{n},\ldots,u_{m})$ and $a_{*}[f]$ is the
Fréchet derivative of $a$ in the direction $f$. Using the Fréchet derivative
we can represent the Lie bracket (11) in the form:

$[f\,,\,g]=g_{*}[f]-f_{*}[g].$ (17)

It is obvious that

$({\mathcal{S}}a)_{*}={\mathcal{S}}\cdot
a_{*}=\sum_{i=n}^{m}{\mathcal{S}}\left(\frac{\partial a}{\partial
u_{i}}\right){\mathcal{S}}^{i+1}\quad\mbox{and}\quad({\mathcal{T}}a)_{*}={\mathcal{T}}\cdot
a_{*}=\sum_{i=n}^{m}{\mathcal{T}}\left(\frac{\partial a}{\partial
u_{i}}\right){\mathcal{S}}^{-i}.$

######  Definition 1.

A difference operator $B$ of order ${\rm ord}\,B:=(n,m)$ with coefficients in
${\mathcal{F}}$ is a finite sum of the form

$B=b^{(m)}{\mathcal{S}}^{m}+b^{(m-1)}{\mathcal{S}}^{m-1}+\cdots+b^{(n)}{\mathcal{S}}^{n},\quad
b^{(m)}b^{(n)}\neq 0,\ b^{(k)}\in{\mathcal{F}},\ \ n\leq m,\
n,m\in\mathbb{Z}.$ (18)

The total order of $B$ is defined as ${\rm Ord}B=m-n$. The total order of the
zero operator is minus infinity ${\rm Ord}\,\,0:=-\infty$ by definition.

The Fréchet derivative (16) is an example of a difference operator of order
$(n,m)$ and total order ${\rm Ord}\,a_{*}=m-n$. For a non-constant element
$f\in{\mathcal{F}}$ the order and total order are defined as ${\rm
ord}\,f_{*}$ and ${\rm Ord}\,f_{*}$ respectively.

Difference operators form a unital ring
${{\mathcal{F}}[{\mathcal{S}},{\mathcal{S}}^{-1}]}$ of Laurent polynomials in
${\mathcal{S}}$ with coefficients in ${\mathcal{F}}$, where multiplication is
defined by

$a{\mathcal{S}}^{n}\cdot
b{\mathcal{S}}^{m}=a{\mathcal{S}}^{n}(b){\mathcal{S}}^{n+m}=ab_{n}{\mathcal{S}}^{n+m}.$
(19)

This multiplication is associative, but non-commutative.

From the above definition it follows that if $A$ is a difference operator of
order ${\rm ord}\,A=(p,q)$, then ${\rm ord}\,({\mathcal{S}}^{n}\cdot
A\cdot{\mathcal{S}}^{m})=(p+n+m,q+n+m)$ and the total order ${\rm
Ord}\,({\mathcal{S}}^{n}\cdot A\cdot{\mathcal{S}}^{m})={\rm Ord}\,A=q-p$. For
any $A,B\in{{\mathcal{F}}[{\mathcal{S}},{\mathcal{S}}^{-1}]}$ we have ${\rm
Ord}\,(AB)={\rm Ord}\,A+{\rm Ord}\,B$.

For a difference operator $B$ given by (18), we define its adjoint operator
$B^{\dagger}$ as

$B^{\dagger}={\mathcal{S}}^{-m}\cdot b^{(m)}+{\mathcal{S}}^{-m+1}\cdot
b^{(m-1)}+\cdots+{\mathcal{S}}^{-n}\cdot b^{(n)}.$

Note that ${\rm ord}\ B^{\dagger}=(-m,-n)$ and ${\rm Ord}\ B^{\dagger}={\rm
Ord}\ B$.

Below we define pseudo-difference (or rational) operators and skew-fields of
formal series.

######  Definition 2.

A rational (pseudo–difference) operator $M$ is defined as $M=AB^{-1}$ for some
$A,B\in{{\mathcal{F}}[{\mathcal{S}},{\mathcal{S}}^{-1}]}$ and $B\neq 0$. The
set of all rational operators is

${\mathfrak{F}}=\\{AB^{-1}\,|\,A,B\in{{\mathcal{F}}[{\mathcal{S}},{\mathcal{S}}^{-1}]},\
B\neq 0\\}.$

######  Definition 3.

The sets ${\mathfrak{F}}_{L}$ of Laurent and ${\mathfrak{F}}_{M}$ of Maclaurin
formal difference series with coefficients in ${\mathcal{F}}$ are

${\mathfrak{F}}_{L}=\left\\{\sum_{n=k}^{\infty}a^{(-n)}{\mathcal{S}}^{-n}\ |\
a^{(m)}\in{\mathcal{F}},\
k\in\mathbb{Z}\right\\},\quad{\mathfrak{F}}_{M}=\left\\{\sum_{n=k}^{\infty}a^{(n)}{\mathcal{S}}^{n}\
|\ a^{(m)}\in{\mathcal{F}},\ k\in\mathbb{Z}\right\\}.$

These sets equipped with addition and composition rules for difference
operators have structure of skew fields [20]. The skew field ${\mathfrak{F}}$
is a minimal subfield of the skew fields ${\mathfrak{F}}_{L}$ and
${\mathfrak{F}}_{M}$, containing
${{\mathcal{F}}[{\mathcal{S}},{\mathcal{S}}^{-1}]}$. A rational operator can
be expanded in the Maclaurin or Laurent series and thus represented by an
element of ${\mathfrak{F}}_{M}$ or ${\mathfrak{F}}_{L}$ respectively. The skew
fields ${\mathfrak{F}}_{L}$ and ${\mathfrak{F}}_{M}$ are isomorphic. The
isomorphism is given by the reflection map ${\mathcal{T}}$.

For $L\in{\mathfrak{F}}_{L}$, we denote its part with non-negative powers of
${\mathcal{S}}$ by $L_{+}$, which is a difference operator.

A rigorous theory pseudo-difference operators with detail proofs and
applications to integrable differential-difference equations can be found in
[20].

##  3 Perturbative symmetry approach

With an evolutionary differential-difference equation

$u_{t}=F(u_{n},\ldots,u_{m}),\qquad F(u_{n},\ldots,u_{m})\in{\mathcal{F}}$
(20)

we associate the evolutionary derivation
$X_{F}\in{\mathcal{D}er({\mathcal{F}})}$ (the vector field corresponding to
the dynamical system (20)). Thus, there is a bijection between evolutionary
derivations of ${\mathcal{F}}$ and differential-difference equations.

Derivation $X_{F}$ enables us to differentiate any element $a\in{\mathcal{F}}$
in the direction of $F$. It follows from the chain rule that (20)

$a_{t}=a_{*}[F]=X_{F}(a).$ (21)

In what follow we will study generators of infinitesimal symmetries of
evolutionary equations and for brevity will call them symmetries.

######  Definition 4.

We say that $G(u_{p},\ldots,u_{q})\in{\mathcal{F}}$ is a symmetry of (20) if
$[G,F]=0.$

If $G$ is a symmetry of (20), equation (20) is invariant ${\rm
mod}\,\epsilon^{2}$ under the near identity transformation $\hat{u}=u+\epsilon
G$. The evolution equation associated to this symmetry is

$u_{\tau}=G(u_{p},\ldots,u_{q}),$ (22)

which is compatible with (20). These can be used as equivalent definitions for
symmetry.

Let $G_{1}$ and $G_{2}$ be any two symmetries of equation (20). It follows
immediately from the Definition 4 and the Jacobi identity that the Lie bracket
$G_{3}=[G_{1},G_{2}]$ is also a symmetry of (20). Thus, symmetries of equation
(20) form a subalgebra of the Lie algebra ${\mathcal{D}er({\mathcal{F}})}$
which will be denoted ${\mathfrak{A}}_{F}$

${\mathfrak{A}}_{F}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{G\in{\mathcal{F}}\;|\;[F,G]=0\\}.$

The existence of an infinite dimensional commutative Lie algebra of symmetries
is a characteristic property of integrable systems.

######  Definition 5.

A differential-difference equation $u_{t}=F$ (20) is called integrable if its
Lie algebra of symmetries ${\mathfrak{A}}_{F}$ is infinite dimensional and
contains symmetries of arbitrary high total order.

An infinite hierarchy of commuting symmetries of an integrable differential-
difference equation (20) can be constructed using a recursion operator
$\Lambda$ (if $\Lambda$ is known), namely, $G_{k}=\Lambda(G_{k-1})$, where
$\Lambda\in{\mathfrak{F}}$ is a rational pseudo-difference operator with
coefficients in ${\mathcal{F}}$ satisfying the equation

$X_{F}(\Lambda)-[F_{*},\Lambda]=0.$ (23)

######  Example 1.

The Volterra equation

$u_{t}=F,\ \ F=u_{1}u-uu_{-1},\ \
F_{*}=u{\mathcal{S}}+u_{1}-u_{-1}-u{\mathcal{S}}^{-1}$

has order ${\rm ord}(F)=(-1,1)$ and total order ${\rm Ord}(F)=2$. Its
recursion operator

$\Lambda=AB^{-1},\qquad
A=u({\mathcal{S}}+1)(u{\mathcal{S}}-{\mathcal{S}}^{-1}u),\
B=u({\mathcal{S}}-1)$

generates the infinite hierarchy of symmetries $G_{k}=\Lambda^{k}(F)$

$\displaystyle G_{1}$ $\displaystyle=$
$\displaystyle\Lambda(u_{1}u-uu_{-1})=A(1-{\mathcal{S}})^{-1}(u_{1}-u_{-1})=A(u+u_{-1}+\gamma_{1})$
(24) $\displaystyle=$ $\displaystyle
u(u_{1}u_{2}+u_{1}^{2}+uu_{1}-uu_{-1}-u_{-1}^{2}-u_{-2}u_{-1})+\gamma_{1}F,$
$\displaystyle G_{2}$ $\displaystyle=$
$\displaystyle\Lambda^{2}(u_{1}u-uu_{-1})=u(u_{1}u_{2}u_{3}+u_{1}u_{2}^{2}+2u_{1}^{2}u_{2}+uu_{1}u_{2}+u_{1}^{3}+2uu_{1}^{2}+u^{2}u_{1}$
$\displaystyle-u^{2}u_{-1}-2uu_{-1}^{2}-u_{-1}^{3}-uu_{-1}u_{-2}-2u_{-1}^{2}u_{-2}-u_{-1}u_{-2}^{2}-u_{-1}u_{-2}u_{-3})+\gamma_{1}G_{1}+\gamma_{2}F,\ldots$

where $\gamma_{k}\in\mathbb{C}$ are arbitrary constants ($\mathbb{C}={\rm
Ker}(B)$).

To find a recursion operator for a given equation is a difficult problem.
There is a regular way to solve it if the equation has a Lax representation. A
discussion of this problem and many explicit examples of pseudo-difference
recursion operators can be found in [20, 22].

###  3.1 Testing for integrability: symmetry approach

The goal of the symmetry approach is to find necessary conditions for the
existence of an infinite dimensional Lie algebra of symmetries for a given
equation. Originally, it was proposed and developed by A.B. Shabat and his
team, and applied to study of partial differential equations [1]-[3]. The
formalism enables them to develop an explicit test for integrability and solve
a number of classification problems by producing complete lists of integrable
partial differential equations. Later on the symmetry approach has been
extended to some non-evolutionary PDEs [10], integro-differential equations
[8, 9] and recently to partial-difference and differential-difference
equations [17, 16]. The method is inspired by the observation that the
existence of an infinite algebra of symmetries implies existence of a formal
solution $\Lambda$ of equation (23) in terms of a formal series. The
conditions of solvability of the equation can be explicitly formulated and
provide us with necessary conditions of integrability.

In the case of differential difference equations, the only result in this
aspect so far is obtained by Adler [16].

######  Theorem 1 (Adler [16]).

If an evolutionary differential-difference equation

$u_{t}=F(u_{n},\ldots,u_{m}),\qquad F(u_{n},\ldots,u_{m})\in{\mathcal{F}},$
(26)

admits symmetries

$u_{\tau}=G(u_{p},\ldots,u_{q})$ (27)

with $q$ arbitrarily large then equation (23) admits a solution
$\Lambda_{L}\in{\mathfrak{F}}_{L}$ of the form

$\Lambda_{L}=F_{*}+\sum_{k=0}^{\infty}a^{(-k)}{\mathcal{S}}^{-k},\qquad\
a^{(-k)}\in{\mathcal{F}}.$

If equation (26) admits symmetries (27) with $\ -p$ arbitrarily large then
equation (23) admits a solution $\Lambda_{M}\in{\mathfrak{F}}_{M}$ of the form

$\Lambda_{M}=F_{*}+\sum_{k=0}^{\infty}b^{(k)}{\mathcal{S}}^{k},\qquad\
b^{(k)}\in{\mathcal{F}}.$

We call the solutions $\Lambda_{L}$ and $\Lambda_{M}$ of (23) formal recursion
operators (formal symmetries in [16]) for the equation. Let us consider the
implications from the first part of the above statement. We try to find a
formal series $\Lambda_{L}$ satisfying equation (23) for a function
$F=F(u_{n},\ldots,u_{m})$. The substitution of $\Lambda_{L},F,F_{*}$ in (23)
results in a formal Laurent series, each coefficient of which should vanish.
Collecting the coefficients at the powers ${\mathcal{S}}^{m-k},\ k=0,1,\ldots$
we obtain a triangular system of difference equations to determine the
coefficients $a^{(-k)}$ of $\Lambda_{L}$. This system is of the form:

${\mathcal{S}}^{m-k}:\ \ {\mathcal{M}}_{m,k}(a^{(-k)})=C_{m,k},\qquad\qquad
k=0,1,\ldots$ (28)

where

${\mathcal{M}}_{m,k}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\frac{\partial
F}{\partial u_{m}}{\mathcal{S}}^{m}-{\mathcal{S}}^{-k}\left(\frac{\partial
F}{\partial u_{m}}\right)$

and the terms $C_{m,k}$ depend on the function $F(u_{n},\ldots,u_{m})$, its
partial derivatives and the coefficients $a^{(0)},a^{(-1)},\ldots,a^{(1-k)}$
only. For example

$\displaystyle C_{m,0}=X_{F}\left(\frac{\partial F}{\partial
u_{m}}\right)=\sum\limits_{i=n}^{m}{\mathcal{S}}^{i}(F)\frac{\partial^{2}F}{\partial
u_{i}\partial u_{m}},$ (29) $\displaystyle C_{m,1}=X_{F}\left(\frac{\partial
F}{\partial u_{m-1}}+a^{(0)}\delta_{m,1}\right)+\frac{\partial F}{\partial
u_{m-1}}\left(a^{(0)}-{\mathcal{S}}^{m-1}(a^{(0)})\right).$ (30)

According to Theorem 1, for integrable equation (20) a solution of the
triangular system (28) exists and $a^{(-k)}\in{\mathcal{F}}$. Thus the
necessary integrability conditions for equation (20) are conditions of
solvability in ${\mathcal{F}}$ of the system (28) with respect to the
coefficients $a^{(-k)}$. The latter can be formulated as the conditions that
$C_{m,k}$ belong to the image spaces of the linear difference operators
${\mathcal{M}}_{m,k}$, i.e., $C_{m,k}\in\mbox{Im}{\mathcal{M}}_{m,k},\
k=0,1,\ldots$. In the case $k=0$ it reduces to the problem of membership in
the space $\mbox{Im}\,({\mathcal{S}}-1)$, which has a well known solution.
Namely, if $a\in\mathbb{C}\bigoplus\mbox{Im}\,({\mathcal{S}}-1)$ then
$\delta_{u}(a)=0$. Here $\delta_{u}$ is the variational derivative

$\delta_{u}(a)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\sum_{n\in\mathbb{Z}}{\mathcal{S}}^{-n}\left(\frac{\partial
a}{\partial u_{n}}\right)=\frac{\partial}{\partial
u_{0}}\sum_{n\in\mathbb{Z}}{\mathcal{S}}^{n}(a).$

There is an algorithmic way to solve the membership problem for the spaces
$\mbox{Im}{\mathcal{M}}_{m,k}$ and if
$C_{m,k}\in\mbox{Im}{\mathcal{M}}_{m,k},\ k=0,1,\ldots$ to find the
coefficients $a^{(-k)}\in{\mathcal{F}}$ recursively.

######  Example 2.

Let us consider equation (20) with $F=f(u)(u_{1}-u_{-1})$, where
$f(u)\in{\mathcal{F}}$. In this case $m=1,\ \frac{\partial F}{\partial
u_{1}}=f(u)$ and

$C_{1,0}=X_{F}(f(u))=f^{\prime}(u)f(u)(u_{1}-u_{-1}),\quad{\mathcal{M}}_{1,0}=f(u)({\mathcal{S}}-1).$

The first necessary integrability condition
$C_{1,0}\in\mbox{Im}\,{\mathcal{M}}_{1,0}$ leads to

$f^{\prime}(u)(u_{1}-u_{-1})\in\mbox{Im}\,({\mathcal{S}}-1).$

Thus

$\delta_{u}\left(f^{\prime}(u)(u_{1}-u_{-1})\right)=f^{\prime\prime}(u)u_{1}+{\mathcal{S}}^{-1}(f^{\prime}(u))-f^{\prime\prime}(u)u_{-1}-{\mathcal{S}}(f^{\prime}(u))=0$

Taking the partial derivative with respect to $u_{1}$ we get
$f^{\prime\prime}(u)={\mathcal{S}}(f^{\prime\prime}(u))$, therefore
$f^{\prime\prime}(u)$ is a constant (an element of $\mathbb{C}$) and thus
$f(u)=\alpha u^{2}+\beta u+\gamma$, where $\alpha,\beta,\gamma\in\mathbb{C}$
are arbitrary constants. The resulting equation

$u_{t}=(\alpha u^{2}+\beta u+\gamma)(u_{1}-u_{-1})$

is known to be integrable.

In this example the first integrability condition enables us to give a
complete description of all integrable differential-difference equations of
the form $u_{t}=f(u)(u_{1}-u_{-1})$.

In Theorem 1 the order of local formal recursion operators depends on the
given equation and there is no simple way to find expressions for the
coefficients $a^{(-k)},b^{(k)}$ explicitly. In Section 5 using symbolic
representation we will proof the existence of the universal (canonical) quasi-
local formal recursion operators and present explicit recursive formulae for
its coefficients.

###  3.2 Approximate symmetries and integrability

Approximate symmetries proved to be successful in the case of partial
differential and integro-differential equations [8, 9]. Our definition of
approximate symmetries is based on the degree grading of the polynomial ring
${\mathcal{R}}$ defined by (12).

In order to define approximate symmetries let us consider an evolutionary
differential-difference equations

$u_{t}=F,\qquad F\in{\mathcal{R}}.$ (31)

Then $F$ can be uniquely represented as a sum of its homogeneous components

$F=F^{(0)}+\ldots+F^{(N)},$

where $F^{(k)}\in{\mathcal{R}}^{k}$ or zero, $N$ is the degree of the
polynomial $F$. It follows from Definition 4 that a polynomial
$G=G^{(0)}+\ldots+G^{(M)}$ is a symmetry if the Lie bracket $[F,G]=0$
vanishes. Due to the degree grading structure of the Lie algebra (14), the
latter is equivalent to a sequence of homogeneous equations

$\sum\limits_{k=0}^{p}[F^{(k)},G^{(p-k)}]=0,\qquad p=0,1,2,\ldots,N+M\,.$ (32)

Here we assume that $F^{(k)}=0$ if $k\not\in\\{0,\ldots N\\}$ and $G^{(k)}=0$
if $k\not\in\\{0,\ldots M\\}$. If all $N+M+1$ equations are satisfied, then
$G$ is a symmetry. If in the (32) the first $s+2$ equations with $0\leqslant
p\leqslant s+1$ are satisfied, then $G$ is called $s$–approximate symmetry (or
approximate symmetry of degree $s$) of the equation (we ignore the rest
equations). It follows from the Jacobi identity that the Lie bracket of two
$s$–approximate symmetries is also a $s$–approximate symmetry and therefore
approximate symmetries of degree $s$ form a closed Lie algebra
${\mathfrak{A}}_{F}^{s}$

${\mathfrak{A}}_{F}^{s}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{G\in{\mathcal{R}}\;|\;\pi_{k}([F,G])=0\
\mbox{for}\ k=0,1,\ldots,s\\}.$

In other words, the move from symmetries to approximate symmetries of degree
$s$ is the transition from definitions and computations made in terms of the
ring ${\mathcal{R}}$ to the quotient ring
${\mathcal{R}}\diagup{\mathcal{I}}^{s+1}$, where

${\mathcal{I}}=\langle{\bf u}\rangle\subset{\mathcal{R}}$ (33)

is the maximal ideal generated by the variables ${\bf u}$. Namely, we say that
$G\in{\mathcal{R}}$ is $s$–approximate symmetry of equation (31) if
$[F,G]\in{\mathcal{I}}^{s+1}$. We will also need difference operators and
formal series with coefficients in the quotient rings
${\mathcal{R}}\diagup{\mathcal{I}}^{s+1}$, but their definitions will be more
natural in symbolic representation which will be introduced in the next
section.

######  Remark 1.

There are no obstructions to replace the polynomial ring
${\mathcal{R}}=\mathbb{C}[{\bf u}]$ by the ring $\bar{{\mathcal{R}}}$ of
formal series

$\bar{{\mathcal{R}}}=\mathbb{C}[[{\bf
u}]]=\\{\sum_{k=0}^{\infty}f^{(k)}\,|\,f^{(k)}\in{\mathcal{R}}^{k}\\}$ (34)

in variables ${\bf u}$ and consider equations and their symmetries given by
the Maclaurin expansion or just formal series. The above definition of
$s$–approximate symmetries remains correct since only a finite number of
equations (32)

$\pi_{k}([F,G])=0,\qquad k=0,1,\ldots,s,\quad F,G\in\bar{{\mathcal{R}}}$

has to be verified.

######  Definition 6.

A differential-difference equation $u_{t}=F,\ F\in\bar{{\mathcal{R}}}$ is
called $s$–approximate integrable if its Lie algebra ${\mathfrak{A}}_{F}^{s}$
is infinite dimensional and contains $s$–approximate symmetries of arbitrary
high total order. The equation is called formally integrable, if it is
$s$–approximate integrable for arbitrary large $s$.

Compare Definitions 5 and 6 we conclude that integrabe equations are formally
integrable. The converse may not be true since we do not assume any
convergence of formal series for the equation and its formal symmetries.
Conditions of $s$–approximate integrability can be explicitly written and
verified. They are strong necessary conditions for integrability and proved to
be suitable for classification of integrable equation. In next section we will
formulate criteria of $s$–approximate integrability using symbolic
representation, which enable us to test for integrability of a given equation
as well as to progress in solution of classification problem for integrable
differential-difference equations.

In what follows, we will restrict ourselves by equations $u_{t}=F$ and
symmetries $G$ without a constant term ($\pi_{0}(F)=0,\ \pi_{0}(G)=0$). Let
${\mathcal{R}}^{\prime}$ denote a subspace of formal series without a constant
term

${\mathcal{R}}^{\prime}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(1-\pi_{0})\bar{{\mathcal{R}}}=\bigoplus\limits_{n=1}^{\infty}{\mathcal{R}}^{n}\,.$
(35)

Having $N$ linearly independent symmetries containing a constant term we can
always construct $N-1$ linear combinations without constant term. A constant
term in $F$ can often be removed by a simple invertible transformation of
variables. Thus the restriction to the linear space ${\mathcal{R}}^{\prime}$
(35) of formal series with no constant terms does not really affect the
generality, but considerably reduces unnecessary stipulations in each case.

##  4 Symbolic representation

Symbolic representation is widely used in theory of pseudo-differential
operators. It has been first applied in the area of integrable systems by
Gel’fand and Dickey [4] and further developed in works of Beukers, Sanders &
Wang [5, 6] and Mikhailov & Novikov [8, 9]. In this section, we will extend
the methods of symbolic representation to the ring of difference polynomials,
difference operators and formal series. Similar to the differential case, the
symbolic representation can be viewed as a simplified notation for a Fourier
transform ($Z$-transform).

###  4.1 Symbolic representation of difference polynomials

To define the symbolic representation
$\hat{{\mathcal{R}}}=\oplus\hat{{\mathcal{R}}}^{n}$ of the degree graded
difference ring (and Lie algebra)
$\bar{{\mathcal{R}}}=\oplus{\mathcal{R}}^{n}$ of formal series, we first
define an isomorphism of the $\mathbb{C}$–linear spaces
$\varphi:{\mathcal{R}}^{n}\mapsto\hat{{\mathcal{R}}}^{n}$ and then extend it
to the difference ring and Lie algebra isomorphism equipping
$\hat{{\mathcal{R}}}$ with the multiplication, derivation and Lie bracket. The
isomorphism of the $\mathbb{C}$–linear spaces
$\varphi:{\mathcal{R}}^{n}\mapsto\hat{{\mathcal{R}}}^{n}$ is uniquely defined
by its action on monomials.

######  Definition 7.

The symbolic form of a difference monomial terms is defined as

$\varphi\,:\,\alpha\mapsto\alpha,\quad\varphi\,:\,\alpha
u_{i_{1}}u_{i_{2}}\cdots u_{i_{n}}\in{\mathcal{R}}^{n}\ \mapsto\
\hat{u}^{n}\alpha\langle\xi_{1}^{i_{1}}\xi_{2}^{i_{2}}\cdots\xi_{n}^{i_{n}}\rangle_{{\Sigma}_{n}}\in{\hat{\cal
R}}^{n},\quad\alpha\in\mathbb{C},$

where $\langle\cdot\rangle_{{\Sigma}_{n}}$ denotes the average over the
permutation group ${{\Sigma}_{n}}$ of $n$ elements $\xi_{1},\ldots,\xi_{n}$:

$\langle
a(\xi_{1},\cdots,\xi_{n})\rangle_{{\Sigma}_{n}}=\frac{1}{n!}\sum_{\sigma\in{\Sigma}_{n}}a(\xi_{\sigma(1)},\cdots,\xi_{\sigma(n)}).$

Notations $\xi_{1},\xi_{2},\ldots$ are reserved for the variables in symbolic
representation. We will omit ${{\Sigma}_{n}}$ in the group average
$\langle\cdot\rangle_{{\Sigma}_{n}}$, assuming that the average is taken over
the permutation group of $n$ variables $\xi_{k}$ where $n$ is shown as the
degree of $\hat{u}^{n}$.

A few examples:

$\displaystyle u_{k}{\,\xmapsto{\varphi}\,}\hat{u}\xi_{1}^{k},\ \ \
u^{n}{\,\xmapsto{\varphi}\,}\hat{u}^{n},\ \ \
u_{1}u_{2}{\,\xmapsto{\varphi}\,}\hat{u}^{2}\langle\xi_{1}\xi_{2}^{2}\rangle_{{\Sigma}_{2}}=\frac{\hat{u}^{2}}{2}(\xi_{1}\xi_{2}^{2}+\xi_{1}^{2}\xi_{2}),$
$\displaystyle\alpha uu_{p}^{2}+\beta
u_{q}^{3}{\,\xmapsto{\varphi}\,}\hat{u}^{3}\left(\frac{\alpha}{3}(\xi_{2}^{p}\xi_{3}^{p}+\xi_{1}^{p}\xi_{2}^{p}+\xi_{1}^{p}\xi_{3}^{p})+\beta\xi_{1}^{q}\xi_{2}^{q}\xi_{3}^{q}\right),\
\ \alpha,\beta\in\mathbb{C}.$

With this isomorphism a homogeneous polynomial $f\in{\mathcal{R}}^{n}$ is in
one-to-one correspondence with a term
$\hat{f}=\hat{u}^{n}a(\xi_{1},\ldots,\xi_{n})\in{\hat{\cal R}}^{n}$ in which
the coefficient function $a(\xi_{1},\ldots,\xi_{n})$ is $n$-variable symmetric
Laurent polynomials, i.e., $a(\xi_{1},\ldots,\xi_{n})\in\Xi_{n},$ where
$\Xi_{n}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\mathbb{C}[\xi_{1},\xi_{1}^{-1},\ldots,\xi_{n},\xi_{n}^{-1}]^{\Sigma_{n}}$.

The projector $\pi_{k}$ (15) selects the $k$-th homogeneous component of an
element $f\in\bar{{\mathcal{R}}},\ \pi_{k}(f)\in{\mathcal{R}}^{k}$. Its
symbolic representation $\hat{\pi}_{k}$ is induced by the condition
$\hat{\pi}_{k}\varphi=\varphi\pi_{k}$. Let

$f=\sum_{n\geqslant
0}f^{(n)}\in\bar{{\mathcal{R}}},\quad\pi_{k}(f)=f^{(k)}\in{\mathcal{R}}^{k},\quad\varphi(f^{(n)})=\hat{u}^{n}a_{n}(\xi_{1},\ldots,\xi_{n}),$

then

$\hat{\pi}_{k}\left(\sum_{n\geqslant
0}\hat{u}^{n}a_{n}(\xi_{1},\ldots,\xi_{n})\right)=\hat{u}^{k}a_{k}(\xi_{1},\ldots,\xi_{n}).$

The action of automorphisms ${\mathcal{S}},{\mathcal{T}}$ in symbolic
representation is given by

${\mathcal{S}}(f)\quad{\,\xmapsto{\varphi}\,}\quad\hat{u}^{n}a(\xi_{1},\ldots,\xi_{n})(\xi_{1}\cdots\xi_{n})\,,\quad{\mathcal{T}}(f)\quad{\,\xmapsto{\varphi}\,}\quad\hat{u}^{n}a(1/\xi_{1},\ldots,1/\xi_{n})\,,$

and thus $\varphi\,:\,{\mathcal{S}}^{k}(f)\ \mapsto\
\hat{u}^{n}a(\xi_{1},\ldots,\xi_{n})(\xi_{1}\cdots\xi_{n})^{k}$.

######  Definition 8.

Let $f\in{\mathcal{R}}^{n},\ \varphi(f)=\hat{u}^{n}a(\xi_{1},\ldots,\xi_{n})$
and $g\in{\mathcal{R}}^{m},\ \varphi(g=\hat{u}^{m}b(\xi_{1},\ldots,\xi_{m})$,
then $\varphi(fg)=\varphi(f)\star\varphi(g)$ where

$\varphi(f)\star\varphi(g)=\hat{u}^{n+m}\langle
a(\xi_{1},\ldots,\xi_{n})b(\xi_{n+1},\ldots,\xi_{n+m})\rangle_{{\Sigma}_{n+m}}.$
(36)

If $f\in{\mathcal{R}}^{0}=\mathbb{C}$, then $\varphi(fg)=f\varphi(g)$. The
representation of difference monomials (Definition 7) can be deduced from
$\varphi:u_{k}\mapsto\hat{u}\xi_{1}^{k}$ and this multiplication rule (36).

The linear space $\hat{{\mathcal{R}}}=\oplus\hat{{\mathcal{R}}}^{n}$ equipped
with the $\star$ multiplication is isomorphic to the graded ring
$\bar{{\mathcal{R}}}$.

###  4.2 Difference operators in the symbolic representation

We assign the symbol $\eta$ corresponding to the shift operator
${\mathcal{S}}$ in the symbolic representation with the action

$\eta(\hat{u}^{p}a(\xi_{1},\ldots,\xi_{p}))=\hat{u}^{p}\xi_{1}\xi_{2}\cdots\xi_{p}a(\xi_{1},\ldots,\xi_{p}).$

and the composition rule (corresponding to ${\mathcal{S}}\circ
f={\mathcal{S}}(f){\mathcal{S}}$):

$\eta\circ\hat{u}^{n}a(\xi_{1},\ldots,\xi_{n})=\hat{u}^{n}(\prod_{j=1}^{n}\xi_{j})a(\xi_{1},\ldots,\xi_{n})\eta\,,$

and thus
$\eta^{k}\circ\hat{u}^{n}a(\xi_{1},\ldots,\xi_{n})=\hat{u}^{n}(\prod_{j=1}^{n}\xi_{j})^{k}a(\xi_{1},\ldots,\xi_{n})\eta^{k}$.

Now we can extend the symbolic representation to difference operators with
coefficients in $\bar{{\mathcal{R}}}$

$\varphi\,:\,A=\sum\limits_{k=p}^{q}f_{(k)}{\mathcal{S}}^{k}\
\mapsto\hat{A}=\sum\limits_{k=p}^{q}\varphi(f_{(k)})\eta^{k},\qquad
f_{(k)}\in\bar{{\mathcal{R}}}.$ (37)

Here the coefficients $f_{(k)}$ are formal series

$f_{(k)}=\alpha_{k}+\sum_{n=1}^{\infty}f_{(k)}^{(n)},\qquad\alpha_{k}\in\mathbb{C},\quad
f_{(k)}^{(n)}\in{\mathcal{R}}^{n},$

and thus

$\varphi(f_{(k)})=\alpha_{k}+\sum_{n=1}^{\infty}\hat{u}^{n}A_{k,n}(\xi_{1},\ldots,\xi_{n}),\quad\
\ A_{k,n}(\xi_{1},\ldots,\xi_{n})\in\Xi_{n}.$

After substitution of $\varphi(f_{(k)})$ in (37) and the change of the order
of summation, the symbolic representation operator $\hat{A}=\varphi(A)$ can
also be written in the form

$\hat{A}=\sum\limits_{n=0}^{\infty}\hat{u}^{n}A_{n}(\xi_{1},\ldots,\xi_{n},\eta),\qquad
A_{n}(\xi_{1},\ldots,\xi_{n},\eta)=\sum\limits_{k=p}^{q}A_{k,n}(\xi_{1},\ldots,\xi_{n})\eta^{k}\,.$
(38)

In the non-commutative ring of difference operators in the symbolic
representation there is a natural degree grading (in powers $\hat{u}^{n}$).
The projector $\hat{\pi}_{s}$ on the homogeneous component can be extended to
operators (38)

$\hat{\pi}_{s}(\hat{A})=\hat{u}^{s}A_{s}(\xi_{1},\ldots,\xi_{s},\eta).$

Symbolic representation enables us to solve immediately the problem to find
the pre-image of the Fréchet derivative. For example, let $F=u(u_{1}-u_{-1})$,
then $F_{*}=u{\mathcal{S}}+(u_{1}-u_{-1})-u{\mathcal{S}}^{-1}$ and

$\varphi(F)=\hat{u}^{2}\frac{1}{2}(\xi_{1}+\xi_{2}-\xi_{1}^{-1}-\xi_{2}^{-1}),\quad\varphi(F_{*})=\hat{u}(\xi_{1}+\eta-\xi_{1}^{-1}-\eta^{-1})$

In general for $f\in{\mathcal{R}}^{n}$ we have a symbol
$\varphi(f)=\hat{u}^{n}a(\xi_{1},\ldots,\xi_{n})$, where $a$ is a symmetric
Laurent polynomial, and

$f_{*}{\,\xmapsto{\varphi}\,}\left(\hat{u}^{n}a(\xi_{1},\ldots,\xi_{n})\right)_{*}=n\hat{u}^{n-1}a(\xi_{1},\ldots,\xi_{n-1},\eta)\,.$

Similar to the differential polynomial case [8], the symbol of the Fréchet
derivative is always symmetric with respect to all permutations of its
variables, including the variable $\eta$.

######  Proposition 1.

An operator (38) is a symbolic representation of the Fréchet derivative of an
element of $\bar{{\mathcal{R}}}$ if and only if each term
$\hat{u}^{n}A_{n}(\xi_{1},\ldots,\xi_{n},\eta)$ is a Laurent polynomial in its
variables and is invariant with respect to all permutations of its variables,
including the variable $\eta$.

Given the Fréchet derivative $\hat{f_{*}}$ in the symbolic representation, we
can immediately reconstruct $\varphi(f)+\alpha$ by replacing
$\hat{u}^{n-1}\rightarrow\hat{u}^{n}/n$ and $\eta\rightarrow\xi_{n}$ in each
term, where $\alpha\in\mathbb{C}$ is an arbitrary constant.

The composition rule for difference operators in symbolic representation (38)
follows from

$\hat{u}^{n}A_{n}(\xi_{1},\ldots,\xi_{n},\eta)\circ\hat{u}^{m}B_{m}(\xi_{1},\ldots,\xi_{m},\eta)=\hat{u}^{n+m}\langle
A_{n}(\xi_{1},\ldots,\xi_{n},\eta\prod\limits_{i=1}^{m}\xi_{i+n})B_{m}(\xi_{n+1},\ldots,\xi_{n+m},\eta)\rangle$
(39)

and the linearity. In particular, the action of difference operators on
elements of $\hat{{\mathcal{R}}}$ follows from

$\hat{u}^{n}A_{n}(\xi_{1},\ldots,\xi_{n},\eta)(\hat{u}^{m}b_{m}(\xi_{1},\ldots,\xi_{m}))=\hat{u}^{n+m}\langle
A_{n}(\xi_{1},\ldots,\xi_{n},\prod\limits_{i=1}^{m}\xi_{i+n})b_{m}(\xi_{n+1},\ldots,\xi_{n+m})\rangle.$
(40)

Now we are going to define the action of evolutionary derivations on elements
of the ring and difference operators in symbolic representation. A
differential-difference equation

$u_{t}=f,\qquad f=\sum_{m\geqslant 0}f^{(m)},\qquad
f^{(m)}\in{\mathcal{R}}^{m}$

defines the evolutionary derivation $\partial_{t}=X_{f}=\sum_{m\geqslant
0}X_{f^{(m)}}$. Let
$\varphi(f^{(m)})=\hat{u}^{m}b_{m}(\xi_{1},\ldots,\xi_{m})$ and for an element
$g\in{\mathcal{R}}^{n},\
\hat{g}=\varphi(g)=\hat{u}^{n}a(\xi_{1},\ldots,\xi_{n})$. Then

$\hat{g}_{t}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\varphi(X_{f}(g))=\sum\limits_{m=0}^{\infty}\hat{u}^{n+m-1}n\langle
a(\xi_{1},\ldots,\xi_{n-1},\prod_{i=0}^{m-1}\xi_{n+i})b_{m}(\xi_{n},\ldots,\xi_{n+m-1})\rangle_{\Sigma_{n+m-1}}\,.$

Similarly for a difference operator $\hat{A}=\varphi(A)$ (38) we obtain

$\hat{A}_{t}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\varphi(X_{f}(A))=\sum\limits_{m=0}^{\infty}\left(\sum\limits_{n=1}^{\infty}\hat{u}^{n+m-1}n\langle
A_{n}(\xi_{1},\ldots,\xi_{n-1},\prod_{i=0}^{m-1}\xi_{n+i},\eta)b_{m}(\xi_{n},\ldots,\xi_{n+m-1})\rangle_{\Sigma_{n+m-1}}\right)\,.$
(41)

Finally we consider the symbolic representation of the Lie bracket. Let
$f\in{\mathcal{R}}^{n},\
f{\,\xmapsto{\varphi}\,}\hat{u}^{n}a(\xi_{1},\ldots,\xi_{n})$ and
$g\in{\mathcal{R}}^{m},\
g{\,\xmapsto{\varphi}\,}\hat{u}^{m}b(\xi_{1},\ldots,\xi_{m})$, then in
symbolic representation the Lie bracket $[f,g]$ (17) takes form

$\displaystyle[f,\ g]$ $\displaystyle{\,\xmapsto{\varphi}\,}$
$\displaystyle\hat{u}^{n+m-1}\left\langle
mb(\xi_{1},\ldots,\xi_{m-1},\xi_{m}\cdots\xi_{n+m-1})a(\xi_{m},\ldots,\xi_{n+m-1})\right.$
(42)
$\displaystyle\left.-na(\xi_{1},\ldots,\xi_{n-1},\xi_{n}\cdots\xi_{n+m-1})b(\xi_{n},\ldots,\xi_{n+m-1})\right\rangle_{{\Sigma}_{n+m-1}}$

In particular, if $f\in{\mathcal{R}}^{1},\
f{\,\xmapsto{\varphi}\,}\hat{u}\omega(\xi_{1})$ and $g\in{\mathcal{R}}^{m},\
g{\,\xmapsto{\varphi}\,}\hat{u}^{m}b(\xi_{1},\ldots,\xi_{m})$, then

$[f,g]{\,\xmapsto{\varphi}\,}-\hat{u}^{m}\left(\omega(\xi_{1}\cdots\xi_{m})-\omega(\xi_{1})-\cdots-\omega(\xi_{m})\right)\
b(\xi_{1},\ldots,\xi_{m}).$ (43)

######  Proposition 2.

Let $u_{t}=F$ be a linear equation ($F\in{\mathcal{R}}^{1}$), then its linear
space of symmetries coincides with ${\mathcal{R}}^{1}$.

###### Proof.

Let us assume that $G=G^{(1)}+G^{(m)}+G^{(m+1)}+\cdots$ for some $m>1$, where
$G^{(k)}=\pi_{k}(G)$ is a symmetry, i.e. $[F,G]=0$ and thus $[F,G^{(m)}]=0$.
It follows from (43) with $f=F,\ g=G^{(m)}$ that
$b(\xi_{1},\ldots,\xi_{m})=0$, and therefore $G^{(m)}=0$. ∎

######  Proposition 3.

Let $G\in{\mathcal{R}}^{\prime}$ be a symmetry of equation
$u_{t}=F\in{\mathcal{R}}^{\prime}$ with a non-zero linear term
$F^{(1)}=\pi_{1}(F)\neq 0$. Then $G$ also has a non-zero linear term
$\pi_{1}(G)\neq 0$.

###### Proof.

Let us assume that $G=G^{(m)}+G^{(m+1)}+\cdots$ and $G^{(m)}\neq 0$ for some
$m>1$. Thus $\pi_{m}([F,G])=[F^{(1)},G^{(m)}]=0$. A contradiction follows from
(43) with $f=F^{(1)},\ g=G^{(m)}$, so that $b(\xi_{1},\ldots,\xi_{m})=0$, and
therefore $G^{(m)}=0$. ∎

######  Proposition 4.

Any two symmetries $G_{1},G_{2}\in{\mathcal{R}}^{\prime}$ of equation
$u_{t}=F\in{\mathcal{R}}^{\prime}$ with a non-zero linear term
$F^{(1)}=\pi_{1}(F)\neq 0$ commute $[G_{1},G_{2}]=0$.

###### Proof.

The commutator of two symmetries $H=[G_{1},G_{2}]$ is a symmetry and it does
not have a linear part $\pi_{1}(H)=0$. It follows from Proposition 3 that
$H=0$. ∎

###  4.3 Symmetries in the symbolic representation.

Symbolic representation enables us to reduce the problem of description of
symmetries for a given differential-difference equation

$u_{t}=F,\qquad
F{\,\xmapsto{\varphi}\,}\hat{u}\omega(\xi_{1})+\hat{u}^{2}a_{2}(\xi_{1},\xi_{2})+\hat{u}^{3}a_{3}(\xi_{1},\xi_{2},\xi_{3})+\cdots,\quad\omega(\xi_{1})\neq
0$ (44)

to the multivariate polynomial factorisation problem.

######  Theorem 2.

Let $G\in{\mathcal{R}}^{\prime}$ be a symmetry of equation (44). Then the
coefficients $A_{k}$ of its symbolic representation

$G{\,\xmapsto{\varphi}\,}\hat{u}\Omega(\xi_{1})+\hat{u}^{2}A_{2}(\xi_{1},\xi_{2})+\hat{u}^{3}A_{3}(\xi_{1},\xi_{2},\xi_{3})+\cdots$
(45)

can be determined recursively:

$\displaystyle
A_{2}(\xi_{1},\xi_{2})=\frac{G^{\Omega}(\xi_{1},\xi_{2})}{G^{\omega}(\xi_{1},\xi_{2})}a_{2}(\xi_{1},\xi_{2});$
(46) $\displaystyle
A_{m}(\xi_{1},...,\xi_{m})=\frac{1}{G^{\omega}(\xi_{1},...,\xi_{m})}\bigg{(}G^{\Omega}(\xi_{1},...,\xi_{m})a_{m}(\xi_{1},...,\xi_{m})$
$\displaystyle\quad\qquad+\sum_{j=2}^{m-1}j\left\langle
A_{j}(\xi_{1},...,\xi_{j-1},\xi_{j}\ldots\xi_{m})a_{m+1-j}(\xi_{j},...,\xi_{m})\right.$
$\displaystyle\quad\qquad\left.-a_{j}(\xi_{1},...,\xi_{j-1},\xi_{j}\ldots\xi_{m})A_{m+1-j}(\xi_{j},...,\xi_{m})\right\rangle_{\varSigma_{m}}\bigg{)},\quad
m=3,4,\cdots$ (47)

where

$G^{\varkappa}(\xi_{1},...,\xi_{m})=\varkappa(\prod_{i=1}^{m}\xi_{i})-\sum_{i=1}^{m}\varkappa(\xi_{i}),\quad\varkappa=\omega,\Omega.$
(48)

###### Proof.

The proof of the Theorem is straightforward. Using (42) we can compute the Lie
bracket between $F$ and $G$. It is obvious that its linear part vanishes. When
the Lie bracket vanishes up to ${\hat{\cal R}}^{2}$, we have

$\hat{u}^{2}\bigg{(}\omega(\xi_{1}\xi_{2})A_{2}(\xi_{1},\xi_{2})+a_{2}(\xi_{1},\xi_{2})(\Omega(\xi_{1})+\Omega(\xi_{2}))-\Omega(\xi_{1}\xi_{2})a_{2}(\xi_{1},\xi_{2})-A_{2}(\xi_{1},\xi_{2})(\omega(\xi_{1})+\omega(\xi_{2}))\bigg{)}=0,$

which leads to the expression of $A_{2}(\xi_{1},\xi_{2})$ as (46). The Lie
bracket vanishing up to ${\hat{\cal R}}^{m}$ is equivalent to formula (47). ∎

Theorem 2 states that a symmetry $G$ of equation (44) is uniquely determined
by its linear part $\Omega(\xi_{1})$. For a given Laurent polynomial
$\Omega(\xi_{1})$ all coefficients $A_{n}(\xi_{1},...,\xi_{n})$ in the formal
series (45) can be found recursively. It does not mean that any evolutionary
equation has a symmetry. The terms in (45) must represent symbols of
difference polynomials, i.e. the coefficients $A_{m}(\xi_{1},\ldots,\xi_{m})$
must be symmetric Laurent polynomials. In general, the coefficients $A_{k}$,
presented in Theorem 2 are symmetric rational functions (46), (47) – they have
denominators $G^{\omega}$ (except $\omega(\xi_{1})={\rm const}\neq 0$, see
remark below). In order to define symbols of difference polynomials, these
denominators must cancel with appropriate factors in the numerators.
Factorisation properties of the Laurent polynomials $G^{\Omega}$ (48) impose
constraints on possible choices of $\Omega(\xi_{1})$. We call a linear term
$\hat{u}\Omega(\xi_{1}),\,\,\Omega(\xi_{1})\in\Xi_{1}$ admissible for the
equation with the symbolic representation (44) if it is the linear term of a
symmetry (45). A linear combination of symmetries is again a symmetry, thus
the set of all admissible linear terms forms a vector space over $\mathbb{C}$.
We denote this space by $V_{F}$. For integrable equations (Definition 5) the
algebra of its symmetries and the vector space $V_{F}$ are infinite
dimensional.

If the coefficients $A_{k},\ k=2,3,\ldots,s$ (46), (47) are Laurent
polynomials, then $G$ (45) is $s$–approximate symmetry of the equation. For
equations with a polynomial function $F$ the sequence of the coefficients
$A_{m}$ usually truncates, resulting in a polynomial symmetry (Example 4).

######  Remark 2.

If $\omega(\xi_{1})$ is a nonzero constant $\omega(\xi_{1})=\alpha\neq 0$,
then $G^{\omega}(\xi_{1},\cdots,\xi_{m})=(1-m)\alpha$ is also a non-zero
constant. In this case it follows from Theorem 2 that all coefficients
$A_{m}(\xi_{1},\ldots,\xi_{m}),\ m=2,3,\ldots$ are symmetric Laurent
polynomials and therefore equation

$\hat{u}_{t}=\alpha\hat{u}+\hat{u}^{2}a_{2}(\xi_{1},\xi_{2})+\hat{u}^{3}a_{3}(\xi_{1},\xi_{2},\xi_{3})+\cdots,\qquad\alpha\in\mathbb{C}^{*}$
(49)

admits a formal symmetry (45) for any choice of a Laurent polynomial
$\Omega(\xi_{1})$. Therefore equation (49) is formally integrable for any
choice of the coefficients $a_{k}(\xi_{1},\ldots,\xi_{k})\in\Xi_{k}$. It is
not surprising, since there exist formal and formally invertible change of
variables

$\hat{v}=\hat{u}+\hat{u}^{2}b_{2}(\xi_{1},\xi_{2})+\hat{u}^{3}b_{3}(\xi_{1},\xi_{2},\xi_{3})+\cdots,\qquad
b_{k}(\xi_{1},\ldots,\xi_{k})\in\Xi_{k},$

such that in terms of the new variable $\hat{v}$ equation (49) and its
symmetry become linear

$\hat{v}_{t}=\alpha\hat{v},\qquad\hat{v}_{\tau}=\Omega(\xi_{1})\hat{v},$

and thus integrable.

######  Example 3.

Consider the Narita-Itoh-Bogoyavlensky equation [19]

$u_{t}=f=u\sum_{i=1}^{n}(u_{i}-u_{-i})$ (50)

The right hand side of the equation does not contain a linear term, but it can
be created by a shift $u_{i}\to u_{i}+1,\,\,i\in\mathbb{Z}$, and so we can
consider

$u_{t}=\sum_{i=1}^{n}(u_{i}-u_{-i})+u\sum_{i=1}^{n}(u_{i}-u_{-i}).$ (51)

The symbolic representation of the equation is

$\hat{u}_{t}=\hat{u}\omega(\xi_{1})+\hat{u}^{2}a_{2}(\xi_{1},\xi_{2}),$
$\omega(\xi_{1})=P(\xi_{1})-P(\xi_{1}^{-1}),\quad
P(\xi_{1}):=\xi_{1}^{n}+\xi_{1}^{n-1}+\cdots+1=\frac{\xi_{1}^{n+1}-1}{\xi_{1}-1},$
$a_{2}(\xi_{1},\xi_{2})=\frac{1}{2}(P(\xi_{1})+P(\xi_{2})-P(\xi_{1}^{-1})-P(\xi_{2}^{-1})).$

It is known that equation (51) possesses a symmetry with linear term of the
form $\hat{u}\Omega_{k}(\xi_{1})$ [24], where

$\Omega_{k}(\xi_{1})=(P(\xi_{1}))^{k}-(P(\xi_{1}^{-1}))^{k},\quad
k=2,3,\ldots$

that is, $\hat{u}\Omega_{k}(\xi_{1})\in V_{f}$ for $k\in\mathbb{N}$.

Taking an admissible linear term for a given equation, one can use Theorem 2
to determine the symmetry starting with this linear term.

######  Example 4.

Let us consider the Volterra equation

$u_{t}=u(u_{1}-u_{-1})\in{\mathcal{R}}^{2}$ (52)

In order to introduce a linear term to this equation we make a change of
variables $u_{i}\to u_{i}+1$:

$u_{t}=u_{1}-u_{-1}+u(u_{1}-u_{-1})$

In the symbolic representation the equation can be written as
$\hat{u}_{t}=\hat{u}\omega(\xi_{1})+\hat{u}^{2}a_{2}(\xi_{1},\xi_{2}),$ where

$\omega(\xi_{1})=\xi_{1}-\frac{1}{\xi_{1}},\quad
a_{2}(\xi_{1},\xi_{2})=\frac{1}{2}\left(\xi_{1}+\xi_{2}-\frac{1}{\xi_{1}}-\frac{1}{\xi_{2}}\right)$

We compute a symmetry starting with
$\Omega(\xi_{1})=\xi_{1}^{2}-\frac{1}{\xi_{1}^{2}}\in\hat{{\mathcal{R}}}_{1}$.
Its quadratic terms are

$\displaystyle
A_{2}(\xi_{1},\xi_{2})=\frac{{G^{\Omega}(\xi_{1},\xi_{2})}}{G^{\omega}(\xi_{1},\xi_{2})}a_{2}(\xi_{1},\xi_{2})=\frac{1}{\xi_{1}\xi_{2}}(1+\xi_{1})(1+\xi_{2})(\xi_{1}\xi_{2}+1)a_{2}(\xi_{1},\xi_{2})$

For cubic terms we then obtain

$A_{3}(k_{1},k_{2},k_{3})=\frac{1}{\xi_{1}^{2}\xi_{2}^{2}\xi_{3}^{2}}(\xi_{1}\xi_{2}\xi_{3}-1)\left\langle\xi_{1}^{2}\xi_{2}+\xi_{1}\xi_{2}\xi_{3}^{2}+\xi_{1}\xi_{2}^{2}\xi_{3}^{2}+\xi_{1}\xi_{2}^{2}\xi_{3}^{3}\right\rangle_{\varSigma_{3}}$

and all terms of degrees higher than $3$ vanish. In standard variables this
symmetry is

$\displaystyle
u_{\tau}=u_{2}-u_{-2}+uu_{2}+uu_{1}+u_{1}^{2}+u_{1}u_{2}-u_{-1}u_{-2}-uu_{-2}-u_{-1}^{2}-uu_{-1}$
$\displaystyle\quad+u^{2}u_{1}+uu_{1}^{2}-uu_{-1}^{2}-u_{-1}u^{2}+uu_{1}u_{2}-uu_{-1}u_{-2}.$

After changing variable $u_{i}\to u_{i}-1$, we get the symmetry for the
Volterra chain (compare with $G_{1}$ in Example 1)

$\displaystyle
u_{\tau}=u(u_{1}u_{2}+u_{1}^{2}+uu_{1}-uu_{-1}-u_{-1}^{2}-u_{-1}u_{-2})-4u(u_{1}-u_{-1}).$

Theorem 2 can be used as a test for integrability if $\Omega(\xi_{1})$ is
assumed. In this case the integrability conditions are conditions of Laurent
polynomiality of the coefficient functions
$A_{2}(\xi_{1},\xi_{2}),A_{3}(\xi_{1},\xi_{2},\xi_{3}),$ etc. A negative
result (i.e. the coefficient functions fail to be Laurent polynomials) might
be inconclusive if the assumption about $\Omega(\xi_{1})$ was wrong.

Most interesting integrable systems possess an infinite hierarchy of local
conservation laws. Let us recall that a difference polynomial (or a formal
series) $\rho$ is a density of a local conservation law for the equation
$u_{t}=F$ (44) if $\rho_{t}\in({\mathcal{S}}-1){\mathcal{R}}^{\prime}$. In
order to exclude trivial densities, i.e. elements of
$({\mathcal{S}}-1){\mathcal{R}}^{\prime}$, the densities are defined on the
quotient space (the $\mathbb{C}$– linear space of functionals)
$\rho\in{\mathcal{R}}^{\prime}\diagup({\mathcal{S}}-1){\mathcal{R}}^{\prime}$.
In the symbolic representation the condition that a term
$\hat{u}^{k}a_{k}(\xi_{1},\ldots,\xi_{k})$ is in the image of
$({\mathcal{S}}-1)$ means that $a_{k}(\xi_{1},\ldots,\xi_{k})$ can be
presented as a product of $\xi_{1}\xi_{2}\cdots\xi_{k}-1$ and a Laurent
polynomial.

The existence of local conservation laws imposed constraints on the linear
part of equations and their symmetries.

######  Proposition 5.

Suppose equation $u_{t}=F$ (44) possesses a conserved density $\rho$ without a
linear term, then $\omega(\xi)+\omega(\xi^{-1})=0$.

###### Proof.

Let the conserved density $\rho=\rho^{(k)}+\rho^{(k+1)}+\cdots$ have a
nontrivial contribution with lowest degree $k\geq 2$ and
$\rho^{(k)}{\,\xmapsto{\varphi}\,}\hat{u}^{k}a(\xi_{1},...,\xi_{k})$, where
the coefficient $a(\xi_{1},...,\xi_{k})$ is not divisible by
$\xi_{1}\xi_{2}\cdots\xi_{k}-1$ and a Laurent polynomial (otherwise
$\rho^{(k)}\in\mbox{Im}(S-1)$). Then

$X_{F^{(1)}}(\rho^{(k)})\in({\mathcal{S}}-1){\mathcal{R}}^{\prime},\qquad
X_{F^{(1)}}(\rho^{(k)})\ {\,\xmapsto{\varphi}\,}\
\hat{u}^{k}a(\xi_{1},...,\xi_{k})\left(\omega(\xi_{1})+\cdots\omega(\xi_{k})\right),$

and should exists a Laurent polynomial $b\in\Xi_{k}$ such that
$\omega(\xi_{1})+\cdots\omega(\xi_{k})=(\xi_{1}\xi_{2}\cdots\xi_{k}-1)b(\xi_{1},...,\xi_{k})$.
Setting $\xi_{1}=\ldots=\xi_{k}=1$ in the latter equation we find
$k\omega(1)=0$, and thus $\omega(1)=0$. Choosing now
$\xi_{1}=\xi,\xi_{2}=\xi^{-1}$ and $\xi_{\ell}=1$ for $\ell>2$ we have
$\omega(\xi)+\omega(\xi^{-1})+(k-2)\omega(1)=0$, and therefore
$\omega(\xi)+\omega(\xi^{-1})=0$. ∎

######  Remark 3.

If an evolutionary equation (44) possesses at least two conserved densities in
${\mathcal{R}}^{\prime}$, then we can omit the condition “possesses a conserve
density $\rho$ without a linear term”, since there always exists a linear
combination of the densities which does not have a linear term.

For a given equation (44), to find the vector space $V_{F}$ of its admissible
linear terms is a non-trivial problem. In the differential case this problem
was completely solved for scalar polynomial homogeneous evolutionary partial
differential equations [6], for systems of two-component equations [21], as
well as for odd order non-evolutionary equations [23]. In next session we are
going to formulate the necessary integrability conditions in the universal
form independent on the structure of the vector space of its admissible linear
terms.

##  5 Integrability conditions for differential-difference equations

In the case of partial differential equations universal integrability
conditions can be formulated in terms of a formal recursion operator [1]-[3].
Namely, the existence of an infinite hierarchy of symmetries implies the
existence of a first order formal pseudo-differential series with the
coefficients in the corresponding differential field, satisfying the same
equations as the recursion operator. Universality means that this fact does
not depend on unknown a priory possible gaps in the hierarchy of symmetries.
Later on this theory has been reformulated in the symbolic representation [8]
which enable us to tackle some integro-differential and non-evolutionary
equations [9, 10, 11]. Universality follows from the existence of fractional
powers of formal pseudo-differential series. In the differential-difference
case a fractional power represented by a difference formal series with
coefficients in the difference field ${\mathcal{F}}$ or ring
$\bar{{\mathcal{R}}}$ may not exist [17]. To tackle the problem we introduce
in this section a quasi-local extension of the difference ring
$\bar{{\mathcal{R}}}$. It will enable us to formulate universal integrability
conditions for differential-difference equations in the symbolic
representation.

###  5.1 Quasi-local extension of the difference ring $\hat{{\mathcal{R}}}$.

In Section 4.2 we have shown that formal difference series with coefficients
from $\bar{{\mathcal{R}}}$ in the symbolic representation take the form

$\hat{A}=\sum\limits_{n=0}^{\infty}\hat{u}^{n}A_{n}(\xi_{1},\ldots,\xi_{n},\eta),\qquad
A_{n}(\xi_{1},\ldots,\xi_{n},\eta)\in\Xi_{n}[\eta^{\pm 1}],$ (53)

where $\Xi_{n}[\eta^{\pm 1}]=\mathbb{C}[\xi_{1}^{\pm 1},\ldots,\xi_{n}^{\pm
1}]^{S_{n}}[\eta^{\pm 1}]$ is a set of Laurent polynomials in the variable
$\eta$, whose coefficients are symmetric Laurent polynomials in variables
$\xi_{1},\ldots,\xi_{n}$. The composition law for difference operators in the
symbolic representation is given by (39).

Here we define a set of formal series

${\mathfrak{A}}=\\{\sum\limits_{n=0}^{\infty}\hat{u}^{n}A_{n}(\xi_{1},\ldots,\xi_{n},\eta)\,|\,A_{n}(\xi_{1},\ldots,\xi_{n},\eta)\in\mathbb{C}(\xi_{1},\ldots,\xi_{n},\eta)^{S_{n}}\\},$
(54)

where $A_{n}(\xi_{1},\ldots,\xi_{n},\eta)$ are rational functions in its
variables, symmetric with respect to permutations of the $\xi$–variables. The
natural addition and the composition rule (39) define on ${\mathfrak{A}}$ a
structure of a non-commutative ring. Obviously, difference operators in the
symbolic representation and formal difference series, such as (53) belong to
${\mathfrak{A}}$, but in general elements of ${\mathfrak{A}}$ do not represent
formal difference series or difference operators.

######  Definition 9.

Let $A_{n}=A_{n}(\xi_{1},\ldots,\xi_{n},\eta)$ be a rational function of its
variables. The term $\hat{u}^{n}A_{n}$ is called L–local (M–local), if the
coefficients $A_{n,k}(\xi_{1},\ldots,\xi_{n})$ of its power expansion in the
variable $\eta$ at infinity $A_{n}=\sum_{k\leqslant
p_{n}}A_{n,k}(\xi_{1},\ldots,\xi_{n})\eta^{k}$ (resp. at zero
$A_{n}=\sum_{k\geqslant q_{n}}A_{n,k}(\xi_{1},\ldots,\xi_{n})\eta^{k}$) are
symmetric Laurent polynomials in the variables $\xi_{1},\ldots,\xi_{n}$.
A formal series

$A=\sum\limits_{n=0}^{\infty}\hat{u}^{n}A_{n}(\xi_{1},\ldots,\xi_{n},\eta)$
(55)

is called L–local (M–local) if all its terms are L–local (resp. M–local). The
formal series $A$ (55) is called local if it is L and M local.

######  Example 5.

The following terms are local, they both M–local and L–local:

$\hat{u}A_{1}(\xi_{1},\eta)=\hat{u}\frac{\eta(\eta+\xi_{1})}{\eta-1},\quad\hat{u}^{2}A_{2}(\xi_{1},\xi_{2},\eta)=\hat{u}^{2}\frac{\eta(\eta\xi_{1}\xi_{2}^{2}+\eta\xi_{1}^{2}\xi_{2}-\eta\xi_{1}^{2}-\eta\xi_{2}^{2}-\eta\xi_{1}-\eta\xi_{2}-2\xi_{1}\xi_{2})}{2(\eta-1)(\eta\xi_{1}-1)(\eta\xi_{2}-1)}.$

They correspond to the first two terms of the canonical formal recursion
operator (we define it in Section 5.2)
$\Lambda=\eta+\hat{u}A_{1}(\xi_{1},\eta)+\hat{u}^{2}A_{2}(\xi_{1},\xi_{2},\eta)+\cdots$
for the Volterra chain $u_{t}=u_{1}-u_{-1}+u(u_{1}-u_{-1})$.

The term $\hat{u}^{2}(\eta+\xi_{1}+\xi_{2})^{-1}$ is L–local, but not M–local.

Let $\hat{A}\in{\mathfrak{A}}$ be a formal series of the form

$A=\eta^{N}+\sum_{p\geq 1}\hat{u}^{p}a_{p}(\xi_{1},\ldots,\xi_{p},\eta),$ (56)

where $N$ is a positive integer, and let us formally seek its $N$–th root

$B=\eta+\sum_{p\geq 1}\hat{u}^{p}b_{p}(\xi_{1},\ldots,\xi_{p},\eta)$ (57)

such that $B^{N}=A$. Using the composition rule (39) and taking projections on
the homogeneous components $\hat{\pi}_{s}(B^{N}-A)=0,\,\,s=0,1,2,\cdots$, we
obtain:

$\displaystyle\hat{\pi}_{1}:$
$\displaystyle\eta^{N-1}\Theta_{N}(\xi_{1})b_{1}(\xi_{1},\eta)-a_{1}(\xi_{1},\eta)=0,$
(58) $\displaystyle\hat{\pi}_{s}:$
$\displaystyle\eta^{N-1}\Theta_{N}(\xi_{1}\xi_{2}\cdots\xi_{s})b_{s}(\xi_{1},\ldots,\xi_{s},\eta)+f_{s}-a_{s}(\xi_{1},\ldots,\xi_{s},\eta)=0,$
(59)

where function $\Theta_{N}$ is defined as

$\Theta_{N}(\xi)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1+\xi+\cdots+\xi^{N-1}=(1-\xi^{N})(1-\xi)^{-1},$
(60)

and the functions $f_{s}$ depend only on $b_{1},\ldots,b_{s-1}$ and $\eta$.
For example

$f_{2}=\sum_{n=0}^{N-2}\left\langle\
\sum_{m=0}^{N-n-2}\xi_{1}^{n}\xi_{2}^{n+m}b_{1}(\xi_{1},\eta\xi_{2})b_{1}(\xi_{2},\eta)\right\rangle_{\Sigma_{2}}\eta^{N-2}.$

Relations (58), (59) form a triangular system of equations which enable us to
find the rational functions
$b_{1}(\xi_{1},\eta),b_{2}(\xi_{1},\xi_{2},\eta),\ldots$ successively

$b_{1}(\xi_{1},\eta)=\frac{a_{1}(\xi_{1},\eta)\eta^{1-N}}{\Theta_{N}(\xi_{1})},\quad
b_{2}(\xi_{1},\xi_{2},\eta)=\frac{a_{2}(\xi_{1},\xi_{2},\eta)-f_{2}}{\eta^{N-1}\Theta_{N}(\xi_{1}\xi_{2})},\ldots\
.$

For every $A$ of the form (56) we can find a unique formal series (57)
satisfying the equation $B^{N}=A$.

Let $A$ be a local series. Then from the relations (58), (59) it follows that
the elements of $B$ are generally no longer local. If $\Theta_{N}(\xi_{1})$
does not divide $a_{1}(\xi_{1},\eta)$ then the coefficients of the power
expansion of $b_{1}(\xi_{1},\eta)$ in $\eta$ as $\eta\to 0$ and in $\eta^{-1}$
as $\eta\to\infty$ contain $\Theta_{N}(\xi_{1})$ in their denominators and
thus fail to be Laurent polynomials in $\xi_{1}$ and therefore they do not
represent symbols of difference polynomials. Similarly, the coefficients of
the expansions of $b_{2}(\xi_{1},\xi_{2},\eta)$ may contain
$\Theta_{N}(\xi_{1}),\ \Theta_{N}(\xi_{2})$ and $\Theta_{N}(\xi_{1}\xi_{2})$
in their denominators, etc. It motivates us to define $\Theta_{N}$-quasi-local
extension of the difference ring $\hat{{\mathcal{R}}}$.

The action of the pseudo-difference operator
$\theta_{N}=\Theta_{N}^{-1}(\eta)$ on
$\hat{u}^{k}a_{k}(\xi_{1},\ldots,\xi_{k})\in\hat{{\mathcal{R}}}$ is given by

$\theta_{N}(\eta)(\hat{u}^{k}a_{k}(\xi_{1},\ldots,\xi_{k}))=\hat{u}^{k}\frac{a_{k}(\xi_{1},\ldots,\xi_{k})}{\Theta_{N}(\prod_{i=1}^{k}\xi_{i})}.$

Let us define the sequence of the ring extensions

$\check{{\mathcal{R}}}_{(0)}=\hat{{\mathcal{R}}},\quad\check{{\mathcal{R}}}_{(s+1)}=\overline{\check{{\cal
R}}_{(s)}\bigcup\theta_{N}(\check{{\cal R}}_{(s)})},\qquad s=0,1,2\ldots\ .$

Here the horizontal line denotes the ring closure as Abelian groups and with
respect to the $\star$ product (36). The index $s$ in $\check{{\cal R}}_{(s)}$
shows the maximal “nesting” degree of $\theta_{N}$. Obviously

$\check{{\mathcal{R}}}_{(0)}=\hat{{\mathcal{R}}}\subset\check{{\mathcal{R}}}_{(1)}\subset\check{{\mathcal{R}}}_{(2)}\subset\cdots\
.$

The quasi-local extension of the ring $\hat{{\mathcal{R}}}$ is defined as the
limit

$\check{{\mathcal{R}}}=\lim\limits_{s\to\infty}\check{{\mathcal{R}}}_{(s)}\,.$
(61)

Saying that $a\in\check{{\mathcal{R}}}$ we mean that there exists such non-
negative integer $s$ that $a\in\check{{\mathcal{R}}}_{(s)}$. Elements of
$\check{{\mathcal{R}}}_{(s)},\ s\geqslant 1$ are called quasi-local. The
quasi-local extension defined above depends on the choice of the integer $N$.

######  Definition 10.

An element $\hat{u}^{p}a(\xi_{1},\ldots,\xi_{p},\eta)\in{\mathfrak{A}}$ is
called $\ell$-quasi-local if the first $\ell$ terms
$\hat{u}^{p}a_{i}(\xi_{1},\ldots,\xi_{p})$ of its power expansion in
$\eta^{-1}$ at $\eta\to\infty$

$\hat{u}^{p}a(\xi_{1},\ldots,\xi_{p},\eta)=\hat{u}^{p}a_{1}(\xi_{1},\ldots,\xi_{p})\eta^{q}+\hat{u}^{p}a_{2}(\xi_{1},\ldots,\xi_{p})\eta^{q-1}+\cdots$

are quasi-local.

A formal series $A=\phi(\eta)+\sum_{p\geq
1}\hat{u}^{p}a_{p}(\xi_{1},\ldots,\xi_{p},\eta),\,\,\phi(\eta)\in\mathbb{C}[\eta,\eta^{-1}]$
is called $\ell$-quasi-local if all its terms are $\ell$-quasi-local. It is
call quasi-local, if it is $\ell$-quasi-local for all $\ell$.

Above we defined the Laurent quasi-locality considering power series
expansions in $\eta^{-1}$. Similarly we could define the Maclaurin quasi-local
formal series using the power expansion in $\eta$ (cf. Definition 9). In the
next Section 5.2, as well as in applications to the problem of classification
of integrable equations of the form (75) in Section 6.1 it will be sufficient
to use concepts of Laurent quasi-locality only (which will be addressed as
quasi-locality for shortness if $N$ is defined).

The above computation of the $N$-th root of a formal series $A$ (56) can be
recast in the following Proposition.

######  Proposition 6.

Let

$A=\eta^{N}+\sum_{p\geq 1}\hat{u}^{p}a_{p}(\xi_{1},\ldots,\xi_{p},\eta)$

be a formal series whose first $k$ terms
$\hat{u}a_{1}(\xi_{1},\eta),\ldots,\hat{u}^{k}a_{k}(\xi_{1},\ldots,\xi_{k},\eta)$
are $\ell$-quasi-local. Then there exists a unique formal series

$B=\eta+\sum_{p\geq 1}\hat{u}^{p}b_{p}(\xi_{1},\ldots,\xi_{p},\eta)$

satisfying the equation $B^{N}=A$, and first $k$ terms of series $B$ are
$\ell$-quasi-local.

The above proposition admits an immediate generalisation:

######  Proposition 7.

Let $P(\eta)=\sum\limits_{k\leqslant N}c_{k}\eta^{k},\ c_{N}\neq 0,\ N\neq 0$
and

$A=P(\eta)+\sum_{p\geq 1}\hat{u}^{p}a_{p}(\xi_{1},\ldots,\xi_{p},\eta)$

be a formal series whose first $k$ terms
$\hat{u}a_{1}(\xi_{1},\eta),\ldots,\hat{u}^{k}a_{k}(\xi_{1},\ldots,\xi_{k},\eta)$
are $\ell$-quasi-local. Then there exists a unique formal series

$B=\eta+\sum_{p\geq 1}\hat{u}^{p}b_{p}(\xi_{1},\ldots,\xi_{p},\eta)$

satisfying the equation $P(B)=A,$ and first $k$ terms
$\hat{u}b_{1}(\xi_{1},\eta),\ldots,\hat{u}^{k}b_{k}(\xi_{1},\ldots,\xi_{k},\eta)$
are $\ell$-quasi-local.

Clearly, if formal series $A$ in Propositions 6 and 7 is local or quasi-local,
then the series $B$ is quasi-local.

###  5.2 Canonical formal recursion operator

We now proceed to the construction of the universal form of necessary
integrability conditions for finite order evolutionary differential-difference
equations, i.e., equations whose right hand side is either a polynomial or a
formal series in a finite number of variables $u_{-n},\ldots,u_{n}$:

$u_{t}=f=f(u_{-n},\ldots,u_{n}),\qquad f=\sum_{i\geq 1}f^{(i)},\qquad\ \
f^{(1)}\neq 0,\ \ f^{(i)}\in{\cal R}^{i}\cap\mathbb{C}[u_{-n},\ldots,u_{n}].\
$ (62)

In symbolic representation equation (62) takes the form

$\hat{u}_{t}=\hat{f}=\hat{u}\omega(\xi_{1})+\sum_{i\geq
2}\hat{u}^{i}a_{i}(\xi_{1},\ldots,\xi_{i}),\qquad a_{i}\in\Xi_{i}.$ (63)

We shall assume that $\omega(\xi_{1})\neq const$ (see Remark 2).

######  Definition 11.

A quasi-local formal series

$\hat{\Lambda}=\phi(\eta)+\sum_{p\geq
1}\hat{u}^{p}\phi_{p}(\xi_{1},\ldots,\xi_{p},\eta),\quad\phi(\eta)\in\mathbb{C}(\eta),$

is called a formal recursion operator for equation (63) if $\hat{\Lambda}$
satisfies the equation

$\hat{\Lambda}_{t}-\hat{f}_{*}\circ\hat{\Lambda}+\hat{\Lambda}\circ\hat{f}_{*}=0\,.$
(64)

Equation (64) is linear in $\hat{\Lambda}$ and for any rational function
$\phi(\eta)$ it has a unique solution in terms of a formal series with
rational coefficients. Namely, the following theorem holds:

######  Theorem 3.

Let

$\Lambda=\phi(\eta)+\sum_{p\geq
1}\hat{u}^{p}\phi_{p}(\xi_{1},\ldots,\xi_{p},\eta),\quad\phi(\eta)\in\mathbb{C}(\eta),\
\phi_{p}(\xi_{1},\ldots,\xi_{p},\eta)\in\mathbb{C}(\xi_{1},\ldots,\xi_{p},\eta)$
(65)

be a formal series with rational coefficients satisfying equation (64). Then,
for any choice of a rational function $\phi(\eta)$, the coefficients of the
series can be recursively determined from the following system:

$\displaystyle\phi_{1}(\xi_{1},\eta)$ $\displaystyle=$ $\displaystyle
2\frac{(\phi(\xi_{1}\eta)-\phi(\eta))}{G^{\omega}(\xi_{1},\eta)}a_{2}(\xi_{1},\eta),$
(66) $\displaystyle\phi_{p}(\xi_{1},\ldots,\xi_{p},\eta)$ $\displaystyle=$
$\displaystyle(p+1)\frac{(\phi(\xi_{1}\cdots\xi_{p}\eta)-\phi(\eta))a_{p+1}(\xi_{1},\ldots,\xi_{p},\eta)}{G^{\omega}(\xi_{1},\ldots,\xi_{p},\eta)}+\frac{1}{G^{\omega}(\xi_{1},\ldots,\xi_{p},\eta)}\times$
$\displaystyle\times\bigg{[}\sum_{s=1}^{p-1}s\langle\phi_{s}(\xi_{1},\ldots,\xi_{s-1},\xi_{s}\cdots\xi_{p},\eta)a_{p-s+1}(\xi_{s},\ldots,\xi_{p})\rangle+$
$\displaystyle+\sum_{s=2}^{p}s\big{(}\langle\phi_{p-s+1}(\xi_{1},\ldots,\xi_{p-s+1},\xi_{p-s+2}\cdots\xi_{p}\eta)a_{s}(\xi_{p-s+2},\ldots,\xi_{p},\eta)\rangle-$
$\displaystyle-\langle
a_{s}(\xi_{1},\ldots,\xi_{s-1},\xi_{s}\cdots\xi_{p}\eta)\phi_{p-s+1}(\xi_{s},\ldots,\xi_{p},\eta)\rangle\big{)}\bigg{]},\quad
p=2,3\ldots.$

###### Proof.

The proof follows immediately from the observation that equations

$\hat{\pi}_{p}(D_{t}(\Lambda)-\hat{f}_{*}\circ\Lambda+\Lambda\circ\hat{f}_{*})=0,\,\,p=1,2,\ldots$

can be solved recursively with respect to
$\phi_{p}(\xi_{1},\ldots,\xi_{p},\eta),\,\,p=1,2,\ldots$. ∎

Theorem 3 does not mean that any equation (63) possesses a formal recursion
operator, since it does not guarantee that the formal series obtained is
quasi-local. Below we are going to show that for integrable equations, i.e.,
equations possessing an infinite hierarchy of symmetries, the obtained series
must be quasi-local. Therefore conditions of quasi-locality of the terms
$\hat{u}^{p}\phi_{p}(\xi_{1},\ldots,\xi_{p},\eta),p=1,2,\ldots$ obtained in
Theorem 3 are necessary integrability conditions for equation (63).

Let $\hat{\Lambda}$ be a formal recursion operator, then powers of
$\hat{\Lambda}$ and linear combinations of powers with constant coefficients
are also formal recursion operators. Indeed, they satisfy equation (64) and
are quasi-local. A constant is a (trivial) recursion operator. Moreover, for
any formal recursion operator $\hat{\Lambda}$ with non-constant $\phi(\eta)$
there exist a unique quasi-local formal series

$\Lambda=\eta+\sum_{p\geq 1}\hat{u}^{p}\phi_{p}(\xi_{1},\ldots,\xi_{p},\eta)$
(68)

satisfying the equation $\hat{\Lambda}=\phi(\Lambda)$ (Proposition 7). It is
easy to see that $\Lambda$ also satisfies equation (64). A formal recursion
operator with $\phi(\eta)=\eta$ we say it is canonical.

The following Theorem shows that the existence of a formal recursion operator
follows from integrability of equation (63).

######  Theorem 4.

Let the algebra of symmetries of equation (63) be infinite dimensional. Then a
formal series (65) satisfying equation (64) is quasi-local.

###### Proof.

Let $G_{k},\ k=1,2,\ldots$ be an infinite sequence of symmetries. It follows
from Proposition 3 that symmetries have non-vanishing linear part
$\hat{u}\Omega_{k}(\xi_{1})=\hat{\pi}_{1}(G_{k})$ and the linear space of the
Laurent polynomials
$\\{\Omega_{k}(\xi)=\sum_{m=M_{k}}^{N_{k}}c_{k,m}\xi^{m}\,|\,c_{k,m}\in\mathbb{C},\
M_{k},N_{k}\in\mathbb{Z}\\}$ is infinite dimensional. Let the order of the
symmetry $G_{k}$ be defined as
$\deg^{+}_{\xi}(\Omega_{k}(\xi))\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=N_{k}$.
Without loss of generality we can assume that the sequence
$N_{1}<N_{2}<N_{3}<\cdots$ is unbounded (otherwise we can apply the reflection
operator ${\mathcal{T}}$ to the equation and its symmetries). Let $\hat{G}$ be
a symmetry of order $N$

$\hat{G}=\hat{u}\Omega(\xi_{1})+\sum_{p\geq
2}\hat{u}^{p}A_{p}(\xi_{1},\ldots,\xi_{p}),\qquad\deg^{+}_{\xi}(\Omega(\xi))=N.$

By Definition 4 we have $[G,f]=0$ and therefore

$([G,f])_{*}=(G_{*})_{t}+G_{*}\circ f_{*}-(f_{*})_{\tau}-f_{*}\circ G_{*}=0,$

where $\partial_{\tau}=X_{G}$ is the derivation defined by the evolutionary
equation $u_{\tau}=G$. In symbolic representation it reads

$(\hat{G}_{*})_{t}-\hat{f}_{*}\circ\hat{G}_{*}+\hat{G}_{*}\circ\hat{f}_{*}=(\hat{f}_{*})_{\tau}$
(69)

where

$\hat{G}_{*}=\Omega(\eta)+\sum_{p\geq
2}p\hat{u}^{p-1}A_{p}(\xi_{1},\ldots,\xi_{p-1},\eta)$

is a local formal series. Its coefficients are symmetric Laurent polynomials
in all variables and
$\deg^{+}_{\eta}(A_{p}(\xi_{1},\ldots,\xi_{p-1},\eta))\leqslant N$
(Proposition 1, Theorem 2). Let us represent the coefficients of $\hat{f}_{*}$
and $\hat{G}_{*}$ as power series in $\eta^{-1}$

$\begin{array}[]{ll}\hat{f}_{*}=\sum\limits_{p\geqslant
1}\,\sum\limits_{k\leqslant
n}pa_{p,k}(\xi_{1},\ldots,\xi_{p-1})\eta^{k}\hat{u}^{p-1}&\omega(\xi_{1})=\sum\limits_{k\leqslant
n}a_{1,k}(\xi_{1})\eta^{k},\\\ &\\\ \hat{G}_{*}=\sum\limits_{p\geqslant
1}\,\sum\limits_{k\leqslant
N}pA_{p,k}(\xi_{1},\ldots,\xi_{p-1})\eta^{k}\hat{u}^{p-1}&\Omega(\xi_{1})=\sum\limits_{k\leqslant
N}A_{1,k}(\xi_{1})\eta^{k}\end{array}$ (70)

and substitute these expansions in equation (69). We notice that the degree of
$\eta$ in the right hand side of the equation is
$\deg^{+}_{\eta}(\hat{f}_{*})_{\tau}\leqslant n$ but the degree of the left
hand side is $N+n$. Thus, at least first $N$ terms
$pA_{p,k}(\xi_{1},\ldots,\xi_{p-1})\eta^{k}\hat{u}^{p-1},\ k=N,N-1,\ldots,1,\
p\in\mathbb{N}$ of the expansion $\hat{G}_{*}$ satisfy the homogeneous linear
equation (64) with $\phi(\xi)=\Omega(\xi)$. The solution of the equation
exists and is unique (Theorem 3). Thus we can identify these terms with
$\phi_{p-1,k}(\xi_{1},\ldots,\xi_{p-1})\eta^{k}\hat{u}^{p-1}$ in the expansion
of $\phi_{p-1}(\xi_{1},\ldots,\xi_{p-1},\eta)$. Since the Fréchet derivative
$\hat{G}_{*}$ of a symmetry $G$ is local, the obtained solution $\Lambda$ is
$N$-local. It follows from Proposition 7 that there exist $N$-quasi-local
(canonical) series of the form (68). Moreover this series in quasi-local since
$N$ can be taken arbitrary large. ∎

Theorem 4 is constructive, and it provides necessary integrability conditions
for equation (63), independent on the symmetry structure of the equation. The
fact of existence of a formal recursion operator can also be proved using
Adler’s theorem [16]. It follows from Adler’s Theorem as well as from Theorem
3 that for equations of order $N$ the coefficients of the formal recursion
operator $\Lambda$ (65) belong to $\Theta_{N}$-quasi-local extension. Adler’s
Theorem also suggests that there exists a rational function $\phi(\xi_{1})$
such that $\Lambda$ (65) is local. We conjecture that
$\phi(\xi_{1})=\omega(\xi_{1})_{+}$, that is, the polynomial part of the
Laurent polynomial $\omega(\xi_{1})$, results in a local $\Lambda$. We have
verified it for a number of equations.

Theorem 3 shows the advantage of symbolic representation. It provides explicit
recurrence formulae (66) and (3) for the coefficients of a formal recursion
operator. We can use it to tackle the classification problem of integrable
differential-difference equations. For a given family of equations of form
(63) the process is as follows:

  * •

Use (66) and (3) to find a few first coefficients
$\phi_{p}(\xi_{1},\ldots,\xi_{p},\eta)$.

  * •

Find constraints on the equations imposed by the quasi-locality conditions of
$\hat{u}^{p}\phi_{p}(\xi_{1},\ldots,\xi_{p},\eta)$.

We illustrate the procedure in the following simple examples.

######  Example 6.

Let us describe all integrable equations of the form

$u_{t}=u_{2}+\alpha u+u(u_{2}+\beta u_{1}+\gamma
u),\quad\alpha,\beta,\gamma\in\mathbb{C}.$ (71)

Its symbolic representation is of the form (63) with

$\omega(\xi_{1})=\xi_{1}^{2}+\alpha,\quad
a_{2}(\xi_{1},\xi_{2})=\frac{1}{2}(\xi_{1}^{2}+\xi_{2}^{2})+\frac{\beta}{2}(\xi_{1}+\xi_{2})+\gamma$

and $a_{s}(\xi_{1},\ldots,\xi_{s})=0,\,\,s>2$. Using Theorem 3 we recursively
compute the coefficients $\phi_{1},\phi_{2}$ of the formal recursion operator
starting with $\phi(\eta)=\eta$. The first coefficient reads as

$\phi_{1}(\xi_{1},\eta)=\frac{\eta\left(\xi_{1}-1\right)\left(\eta^{2}+\beta\eta+\xi_{1}^{2}+\beta\xi_{1}+2\gamma\right)}{\eta^{2}(\xi_{1}^{2}-1)-\xi_{1}^{2}-\alpha},$

and its power expansion in $\eta$ at $\eta\to\infty$ is of the form

$\phi_{1}(\xi_{1},\eta)=\frac{\eta+\beta}{\xi_{1}+1}+\frac{\xi_{1}^{4}+\beta\xi_{1}^{3}+2\gamma\xi_{1}^{2}-\beta\xi_{1}+\alpha-2\gamma}{\left(\xi_{1}-1\right)\left(\xi_{1}+1\right){}^{2}}\eta^{-1}+O(\eta^{-2}).$

We see that the element $\hat{u}\phi_{1}(\xi_{1},\eta)$ is $2$-quasi-local as

$\hat{u}\frac{\eta+\beta}{\xi_{1}+1}\in\check{{\mathcal{R}}}_{(1)},$

and the ring extension is performed by using the operator
$\theta_{2}=(1+\eta)^{-1}$. The third term in the expansion contains
$\xi_{1}-1$ in the denominator, and therefore

$\hat{u}\frac{\xi_{1}^{4}+\beta\xi_{1}^{3}+2\gamma\xi_{1}^{2}-\beta\xi_{1}+\alpha-2\gamma}{\left(\xi_{1}-1\right)\left(\xi_{1}+1\right){}^{2}}\eta^{-1}$

is quasi-local if and only if $\xi_{1}-1$ divides
$\xi_{1}^{4}+\beta\xi_{1}^{3}+2\gamma\xi_{1}^{2}-\beta\xi_{1}+\alpha-2\gamma$.
The latter occurs if and only if $\alpha=-1$. Then, if $\alpha=-1$, the first
term of the formal recursion operator reads as

$\hat{u}\phi_{1}(\xi_{1},\eta)=\hat{u}\frac{\eta\left(\eta^{2}+\beta\eta+\xi_{1}^{2}+\beta\xi_{1}+2\gamma\right)}{(\eta-1)(\eta+1)\left(\xi_{1}+1\right)},$

and it is easy to see that this term is $\Theta_{2}$-quasi-local.

Let $\alpha=-1$. We now consider the power expansion in $\eta$ at
$\eta\to\infty$ of the second coefficient $\phi_{2}(\xi_{1},\xi_{2},\eta)$:

$\phi_{2}(\xi_{1},\xi_{2},\eta)=-\frac{\xi_{1}+\xi_{2}}{2\left(\xi_{1}+1\right)\left(\xi_{2}+1\right)\left(\xi_{1}\xi_{2}+1\right)}\eta-\frac{\beta\left(\xi_{1}+\xi_{2}+2\right)}{2\left(\xi_{1}+1\right)\left(\xi_{2}+1\right)\left(\xi_{1}\xi_{2}+1\right)}$
$+\frac{P(\xi_{1},\xi_{2},\beta,\gamma)}{2\left(\xi_{1}\xi_{2}-1\right)\xi_{1}\xi_{2}\left(\xi_{1}+1\right)\left(\xi_{2}+1\right)\left(\xi_{1}\xi_{2}+1\right){}^{2}}+O(\eta^{-2}),$

where $P(\xi_{1},\xi_{2},\beta,\gamma)$ is a polynomial in its variables. The
third term in this expansion is the obstruction to quasi-locality of
$\hat{u}^{2}\phi_{2}(\xi_{1},\xi_{2},\eta)$, unless $\xi_{1}\xi_{2}-1$ divides
$P(\xi_{1},\xi_{2},\beta,\gamma)$. We have

$P(\xi_{1},\xi_{1}^{-1},\beta,\gamma)=-\left(1+\xi_{1}^{-1}\right){}^{2}\left(2(\gamma+1)\xi_{1}+\beta(1+\xi_{1}^{2})\right).$

So the division occurs if and only if $\beta=0$ and $\gamma=-1$. The latter
implies $\Theta_{2}$-quasi-locality of the element
$\hat{u}^{2}\phi_{2}(\xi_{1},\xi_{2},\eta)$. The resulting equation (71) is

$u_{t}=u_{2}-u+u(u_{2}-u)=(u+1)(u_{2}-u).$

Upon the change of variables $u_{k}\to u_{k}-1,\,\,k\in\mathbb{Z}$, it becomes
the stretched Burgers equation

$u_{t}=u(u_{2}-u).$

######  Example 7.

Let us find all integrable equations of the form

$u_{t}=u_{2}+\alpha u_{1}-\alpha u_{-1}-u_{-2}+u(u_{2}+\beta u_{1}-\beta
u_{-1}-u_{-2}),\quad\alpha,\beta\in\mathbb{C}.$ (72)

Its symbolic representation is of the form (63), where

$\omega(\xi)=\xi^{2}+\alpha\xi-\alpha\xi^{-1}-\xi^{-2},\quad
a_{2}(\xi_{1},\xi_{2})=\frac{1}{2}(\xi_{1}^{2}+\xi_{2}^{2}-\xi_{1}^{-2}-\xi_{2}^{-2}+\beta(\xi_{1}+\xi_{2}-\xi_{1}^{-1}-\xi_{2}^{-1}))$

and $a_{s}(\xi_{1},\ldots,\xi_{s})=0,\,\,s>2$. Using the theorem 3 we
recursively compute the coefficients $\phi_{1},\phi_{2},\phi_{3}$ of the
formal recursion operator starting with $\phi(\eta)=\eta$. We have

$\phi_{1}(\xi_{1},\eta)=\frac{\eta\left(\beta\eta^{2}\xi_{1}+\beta\eta\xi_{1}^{2}+\eta^{3}\xi_{1}+\eta^{2}+\eta\xi_{1}^{3}+\xi_{1}^{2}\right)}{(\eta-1)\left(\alpha\eta\xi_{1}+\eta^{2}\xi_{1}^{2}+\eta^{2}\xi_{1}+\eta\xi_{1}^{2}+2\eta\xi_{1}+\eta+\xi_{1}+1\right)},$

and it is easy to see that this term is quasi-local as all coefficients of its
power expansion at $\eta\to\infty$ (as well as at $\eta\to 0$) are
$\Theta_{2}$-quasi-local.

The direct computation shows that the next coefficient
$\phi_{2}(\xi_{1},\xi_{2},\eta)$ is of the form

$\phi_{2}=\frac{\Phi_{2}(\xi_{1},\xi_{2},\eta,\alpha,\beta)}{\left(\eta\xi_{1}-1\right)\left(\eta\xi_{2}-1\right)\left(\alpha\eta\xi_{1}\xi_{2}+\eta^{2}\xi_{1}^{2}\xi_{2}^{2}+\eta^{2}\xi_{1}\xi_{2}+\eta\xi_{1}\xi_{2}^{2}+\eta\xi_{1}+\eta\xi_{1}^{2}\xi_{2}+\eta\xi_{2}+\xi_{1}\xi_{2}+1\right)},$

where $\Phi_{2}(\xi_{1},\xi_{2},\eta,\alpha,\beta)$ is a polynomial in its
arguments. From this it follows that the second term
$\hat{u}^{2}\phi_{2}(\xi_{1},\xi_{2},\eta)$ is quasi-local.

The quasi-locality condition of next coefficient
$\phi_{3}(\xi_{1},\xi_{2},\xi_{3},\eta)$ imposes restrictions on parameters
$\alpha,\beta$. The function $\phi_{3}$ can be represented as

$\phi_{3}=\frac{\Phi_{3}(\xi_{1},\xi_{2},\xi_{3},\eta,\alpha,\beta)}{\Psi_{3}(\xi_{1},\xi_{2},\xi_{3},\eta,\alpha)},$

where $\Phi_{3},\Psi_{3}$ are polynomials in their arguments. The polynomial
$\Psi_{3}$ contains the irreducible factor

$\displaystyle(\xi_{1}\xi_{2}\xi_{3}\eta)^{2}G^{\omega}(\xi_{1},\xi_{2},\xi_{3},\eta)$
$\displaystyle=$
$\displaystyle\left(\xi_{1}^{2}\xi_{2}^{2}\xi_{3}^{2}-1\right)\left(\eta^{4}\xi_{1}^{2}\xi_{2}^{2}\xi_{3}^{2}+1\right)+\alpha\eta\xi_{1}\xi_{2}\xi_{3}\left(\xi_{1}\xi_{2}\xi_{3}-1\right)\left(\eta^{2}\xi_{1}\xi_{2}\xi_{3}+1\right)$
$\displaystyle+$
$\displaystyle\eta^{2}(-\alpha\xi_{2}^{2}\xi_{3}^{2}\xi_{1}^{3}-\alpha\xi_{2}^{2}\xi_{3}^{3}\xi_{1}^{2}-\alpha\xi_{2}^{3}\xi_{3}^{2}\xi_{1}^{2}+\alpha\xi_{2}\xi_{3}^{2}\xi_{1}^{2}+\alpha\xi_{2}^{2}\xi_{3}\xi_{1}^{2}+\alpha\xi_{2}^{2}\xi_{3}^{2}\xi_{1}$
$\displaystyle-$
$\displaystyle\xi_{2}^{2}\xi_{3}^{2}\xi_{1}^{4}-\xi_{2}^{2}\xi_{3}^{4}\xi_{1}^{2}+\xi_{2}^{2}\xi_{1}^{2}-\xi_{2}^{4}\xi_{3}^{2}\xi_{1}^{2}+\xi_{3}^{2}\xi_{1}^{2}+\xi_{2}^{2}\xi_{3}^{2}).$

The presence of this factor results in violation of the quasi-locality of the
term $\hat{u}^{3}\phi_{3}$, unless it cancels out by the numerator $\Phi_{3}$.
The cancellation takes place if and only if $\beta=\alpha$ and $\alpha=0$ or
$\alpha=1$. If $\alpha=0$ then the resulting equation is

$u_{t}=u_{2}-u_{-2}+u(u_{2}-u_{-2})=(u+1)(u_{2}-u_{-2}),$

which upon the change of variables $u_{k}\to u_{k}-1,\,\,k\in\mathbb{Z}$,
becomes the stretched Volterra equation

$u_{t}=u(u_{2}-u_{-2}).$

In the case $\alpha=1$ we have

$u_{t}=u_{2}+u_{1}-u_{-1}-u_{-2}+u(u_{2}+u_{1}-u_{-1}-u_{-2})=(u+1)(u_{2}+u_{1}-u_{-1}-u_{-2}),$

and after the same change of variables $u_{k}\to u_{k}-1,\,\,k\in\mathbb{Z}$,
we obtain the Narita-Itoh-Bogoyavlensky equation (50) when $n=2$, that is,

$u_{t}=u(u_{2}+u_{1}-u_{-1}-u_{-2}).$ (73)

##  6 Classification of integrable differential-difference equations

Here we apply the previous section results to the problem of classification of
anti-symmetric quasi-linear integrable differential-difference equations of
order $(-n,n)$

$u_{t}=u_{n}f(u_{n-1},\ldots,u_{1-n})-u_{-n}f(u_{1-n},\ldots,u_{n-1})+g(u_{n-1},\ldots,u_{1-n})-g(u_{1-n},\ldots,u_{n-1}),$
(74)

where $f,g$ are polynomial functions or formal series. Quasi-linear equations
are called equivalent if they are related by invertible transformations
$u_{k}\mapsto\alpha u_{k}+\beta,\ t\mapsto\gamma t,\
\alpha,\gamma\in\mathbb{C}^{*},\ \beta\in\mathbb{C}$. The equivalence classes
may contain equations with $f(0,\ldots,0)=0$ (see Example 4). In the
classification list it is sufficient to present a single representative from
each equivalence class. Integrable equations are members of infinite hierarchy
of symmetries. Each hierarchy has a seed which is hierarchy member of a
minimal possible order. Thus instead of presenting all integrable equations of
a certain fixed order, we only present the seeds of integrable hierarchies
removing the ones possessing lower order symmetries.

In this section we give a complete list for equations of the form (74) when
$n=3$ satisfying necessary integrability conditions - the quasi-locality
conditions for the canonical formal recursion operator. The integrability for
each equation from the list is proved by either using difference substitutions
or presenting Lax representations. Moreover, we investigate the higher order
integrable analogue for each equation from the list. Similar to the Narita-
Itoh-Bogoyavlensky lattice (50), this is a family of integrable equations for
any specific $n\in\mathbb{N}$, and for any two different $n$, the
corresponding flows do not commute (cf. Section 6.2). Finally we present a Lax
representation for a new integrable differential-difference hierarchy.

###  6.1 Classification results

In this session we present the exhaustive list of integrable differential-
difference equations of the form

$u_{t}=u_{3}f(u_{2},u_{1},u)-u_{-3}f(u_{-2},u_{-1},u)+g(u_{2},u_{1},u)-g(u_{-2},u_{-1},u),\qquad
f(0,0,0)=1,$ (75)

where $f,g$ are polynomial functions or formal power series. We omit equations
admitting a symmetry of order $(1,-1)$, which have been studied in detail in
[13, 14].

######  Theorem 5.

Every integrable differential-difference equation (75) with no symmetries of
order $(-1,1)$ can be obtained from one of the equations in the following list

$\displaystyle u_{t}$ $\displaystyle=$ $\displaystyle u(u_{3}-u_{-3}),$ (76)
$\displaystyle u_{t}$ $\displaystyle=$ $\displaystyle u^{2}(u_{3}-u_{-3}),$
(77) $\displaystyle u_{t}$ $\displaystyle=$
$\displaystyle(u^{2}+u)(u_{3}-u_{-3}),$ (78) $\displaystyle u_{t}$
$\displaystyle=$ $\displaystyle
u(u_{1}u_{2}u_{3}-uu_{1}u_{2}+uu_{-1}u_{-2}-u_{-1}u_{-2}u_{-3}),$ (79)
$\displaystyle u_{t}$ $\displaystyle=$ $\displaystyle
u(u_{2}u_{3}-u_{1}u_{2}+uu_{1}-uu_{-1}+u_{-1}u_{-2}-u_{-2}u_{-3}),$ (80)
$\displaystyle u_{t}$ $\displaystyle=$ $\displaystyle
u\left(\frac{u_{3}u_{1}}{u_{2}}-\frac{u_{-3}u_{-1}}{u_{-2}}\right)+u^{2}\left(\frac{u_{2}}{u_{1}}-\frac{u_{-2}}{u_{-1}}\right),$
(81) $\displaystyle u_{t}$ $\displaystyle=$ $\displaystyle
u\left(\frac{u_{3}}{u_{2}}-\frac{u_{-3}}{u_{-2}}\right)+u\left(\frac{u_{2}}{u_{1}}-\frac{u_{-2}}{u_{-1}}\right)+u_{1}-u_{-1},$
(82) $\displaystyle u_{t}$ $\displaystyle=$ $\displaystyle
u\left(u_{3}+u_{2}+u_{1}-u_{-1}-u_{-2}-u_{-3}\right),$ (83) $\displaystyle
u_{t}$ $\displaystyle=$ $\displaystyle
u\left(u_{1}u_{2}u_{3}-u_{-1}u_{-2}u_{-3}\right),$ (84) $\displaystyle u_{t}$
$\displaystyle=$ $\displaystyle
u^{2}\left(u_{1}u_{2}u_{3}-u_{-1}u_{-2}u_{-3}\right),$ (85) $\displaystyle
u_{t}$ $\displaystyle=$
$\displaystyle(u^{2}+u)\left(u_{1}u_{2}u_{3}-u_{-1}u_{-2}u_{-3}\right),$ (86)
$\displaystyle u_{t}$ $\displaystyle=$ $\displaystyle
u(u_{1}u_{3}+uu_{2}-uu_{-2}-u_{-1}u_{-3}),$ (87) $\displaystyle u_{t}$
$\displaystyle=$ $\displaystyle u(u_{2}u_{3}+uu_{1}-uu_{-1}-u_{-2}u_{-3}),$
(88) $\displaystyle u_{t}$ $\displaystyle=$ $\displaystyle
u^{2}(u_{1}u_{2}u_{3}-u_{-1}u_{-2}u_{-3})-u(u_{1}u_{2}-u_{-1}u_{-2}),$ (89)
$\displaystyle u_{t}$ $\displaystyle=$ $\displaystyle
u(u_{1}u_{3}+uu_{2}-uu_{-2}-u_{-1}u_{-3})-u(u_{2}+u_{1}-u_{-1}-u_{-2}),$ (90)
$\displaystyle u_{t}$ $\displaystyle=$ $\displaystyle
u(u_{2}u_{3}+uu_{1}-uu_{-1}-u_{-2}u_{-3})-u(u_{2}+u_{1}-u_{-1}-u_{-2}),$ (91)
$\displaystyle u_{t}$ $\displaystyle=$
$\displaystyle(u^{2}+1)(u_{3}\sqrt{u_{1}^{2}+1}\sqrt{u_{2}^{2}+1}-u_{-3}\sqrt{u_{-1}^{2}+1}\sqrt{u_{-2}^{2}+1}),$
(92)

by shift $u_{k}\mapsto u_{k}+const$, re-scaling transformations $u_{k}\to\mu
u_{k},\,k\in\mathbb{Z},\,\,t\to\nu t,\,\,\mu,\nu\in\mathbb{C}^{*}$ and, where
necessary, a power expansion.

The proof of this classification theorem relies on the following result:

######  Proposition 8.

Let

$u_{t}=\sum_{p\geq 1}f_{p},\quad f_{i}\in{\cal R}^{i}\quad\mbox{and}\quad
u_{t}=\sum_{p\geq 1}\tilde{f}_{p},\quad\tilde{f}_{i}\in{\cal R}^{i}$

be two integrable formal differential-difference equations of form (75), such
that

  * •

The linear terms are
$f_{1}=\tilde{f}_{1}=u_{3}+c_{2}u_{2}+c_{1}u_{1}-c_{1}u_{-1}-c_{2}u_{-2}-u_{-3}$;

  * •

The quadratic and cubic terms coincide: $f_{2}=\tilde{f}_{2},\quad
f_{3}=\tilde{f}_{3}$.

Then the formal differential-difference equations coincide, i.e.
$f_{p}=\tilde{f}_{p},\quad\forall p\in\mathbb{N}.$

###### Proof.

Since the formal differential-difference equations are integrable, they
possess the canonical formal recursion operators

$\Lambda=\eta+\sum_{p>0}\hat{u}^{p}\phi_{p}(\xi_{1},\ldots,\xi_{p},\eta),\quad\tilde{\Lambda}=\eta+\sum_{p>0}\hat{u}^{p}\tilde{\phi}_{p}(\xi_{1},\ldots,\xi_{p},\eta),$

such that all their terms are quasi-local. Moreover, since the linear,
quadratic and cubic terms of the formal differential-difference equations
coincide, the linear and quadratic terms of the formal recursion operators
also coincide, i.e.

$\phi_{1}(\xi_{1},\eta)=\tilde{\phi}_{1}(\xi_{1},\eta),\quad\phi_{2}(\xi_{1},\xi_{2},\eta)=\tilde{\phi}_{2}(\xi_{1},\xi_{2},\eta).$

Consider cubic elements of $\Lambda$ and $\tilde{\Lambda}$:
$\hat{u}^{3}\phi_{3}(\xi_{1},\xi_{2},\xi_{3},\eta)$ and
$\hat{u}^{3}\tilde{\phi}_{3}(\xi_{1},\xi_{2},\xi_{3},\eta)$, and let
$\hat{u}^{4}a_{4}(\xi_{1},\xi_{2},\xi_{3},\xi_{4})$ and
$\hat{u}^{4}\tilde{a}_{4}(\xi_{1},\xi_{2},\xi_{3},\xi_{4})$ be the symbolic
representations of $f_{4}$ and $\tilde{f}_{4}$. Then from (3) it follows that

$\phi_{3}(\xi_{1},\xi_{2},\xi_{3},\eta)-\tilde{\phi}_{3}(\xi_{1},\xi_{2},\xi_{3},\eta)=4\frac{\eta(\xi_{1}\xi_{2}\xi_{3}-1)(a_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)-\tilde{a}_{4}(\xi_{1},\xi_{2},\xi_{3},\eta))}{\omega(\xi_{1}\xi_{2}\xi_{3}\eta)-\omega(\xi_{1})-\omega(\xi_{2})-\omega(\xi_{3})-\omega(\eta)}$
(93)

since all the lower terms coincide. Here

$\omega(x)=x^{3}+c_{2}x^{2}+c_{1}x-c_{1}x^{-1}-c_{2}x^{-2}-x^{-3}.$

We can rewrite the right hand side of (93) as

$4\eta(\xi_{1}\xi_{2}\xi_{3}-1)\frac{\hat{a}_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)}{g_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)},$

where

$\displaystyle\hat{a}_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)$ $\displaystyle=$
$\displaystyle\xi_{1}^{3}\xi_{2}^{3}\xi_{3}^{3}\eta^{3}\left(a_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)-\tilde{a}_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)\right),$
$\displaystyle g_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)$ $\displaystyle=$
$\displaystyle\xi_{1}^{3}\xi_{2}^{3}\xi_{3}^{3}\eta^{3}G^{\omega}(\xi_{1},\xi_{2},\xi_{3},\eta).$

Here both $\hat{a}_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)$ and
$g_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)$ are polynomials in their arguments. One
can show that the polynomial $g_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)$ is
irreducible for any choice of parameters $c_{1},c_{2}\in\mathbb{C}$. Moreover,
the total degree of $g_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)$ is $24$, while the
total degree of $\hat{a}_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)$ is less than $24$
since the equations are of form (75). Therefore, the polynomial
$g_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)$ cannot divide
$\hat{a}_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)$. It follows from Theorem 4 that
$\hat{u}^{3}(\phi_{3}(\xi_{1},\xi_{2},\xi_{3},\eta)-\tilde{\phi}_{3}(\xi_{1},\xi_{2},\xi_{3},\eta))$
is quasi-local, while the expression
$4\hat{u}^{3}\eta(\xi_{1}\xi_{2}\xi_{3}-1)\frac{\hat{a}_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)}{g_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)}$
is quasi-local if and only if $\hat{a}_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)=0$.
Therefore,
$a_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)=\tilde{a}_{4}(\xi_{1},\xi_{2},\xi_{3},\eta)$,
and thus $f_{4}=\tilde{f}_{4}$.

By the same argument, we can show that if
$f_{i}=\tilde{f}_{i},\,\,i=1,\ldots,k$, then $f_{k+1}=\tilde{f}_{k+1}$, for
$k\geq 4$. ∎

Sketch of the proof of the theorem 5: The symbolic representation of a generic
equation (or formal series) (75) is of the form (63) with

$\omega(\xi)=P_{1}(\xi)-P_{1}(\xi^{-1}),\quad
a_{s}(\xi_{1},\ldots,\xi_{s})=P_{s}(\xi_{1},\ldots,\xi_{s})-P_{s}(\xi_{1}^{-1},\ldots,\xi_{s}^{-1}),\quad
s=2,3,\ldots,$

where

$P_{1}(\xi)=\xi^{3}+\alpha\xi^{2}+\beta\xi,\quad\alpha,\beta\in\mathbb{C},$
$P_{s}(\xi_{1},\ldots,\xi_{s})=\left\langle\sum_{i_{1}=0}^{3}\sum_{i_{2},\ldots,i_{s}=0}^{2}c_{i_{1}\ldots
i_{s}}\xi_{1}^{i_{1}}\cdots\xi_{s}^{i_{s}}\right\rangle,\quad c_{i_{1}\cdots
i_{s}}\in\mathbb{C}.$

The algorithm can be split into two steps.

Step 1. The coefficients $\phi_{1},\phi_{2},\phi_{3}$ of the formal recursion
operator with $\phi(\eta)=\eta$ can be found explicitly (Theorem 3). It is
easy to show that terms $\hat{u}\phi_{1},\hat{u}^{2}\phi_{2}$ are quasi-local
for any $\alpha,\beta$ and constants $c_{i_{1}i_{2}},c_{i_{1}i_{2}i_{3}}$. The
requirement of the quasi-locality of the term
$\hat{u}^{3}\phi_{3}(\xi_{1},\xi_{3},\xi_{3},\eta)$ results in the system of
polynomial equations on $\alpha,\beta$ and
$c_{i_{1}i_{2}},c_{i_{1}i_{2}i_{3}},c_{i_{1}i_{2}i_{3}i_{4}}$ \- the necessary
integrability conditions. The action of the re-scaling group $u_{k}\to\mu
u_{k},\,k\in\mathbb{Z},\,\,t\to\nu t,\,\,\mu,\nu\in\mathbb{C}^{*}$ on
constants $\alpha,\beta$ and
$c_{i_{1}i_{2}},c_{i_{1}i_{2}i_{3}},c_{i_{1}i_{2}i_{3}i_{4}}$ is of the form

$\alpha\to\alpha,\quad\beta\to\beta,\quad c_{i_{1}\cdots
i_{s}}\to\mu^{s-1}\nu^{-1}c_{i_{1}\cdots i_{s}},$

and modulo the action of this group the set of solutions of the system of
integrability conditions is finite. Thus we obtain the finite list of
$3$-approximate integrable equations of the form (75).

Step 2. By Proposition 8 the requirement of quasi-locality of
$\hat{u}^{s}\phi_{s}(\xi_{1},\ldots,\xi_{s},\eta),\,s\geq 4$ uniquely
determines the terms $\hat{u}^{s}a_{s}(\xi_{1},\ldots,\xi_{s}),\,\,s\geq 4$
and imposes further restrictions on the constants
$\alpha,\beta,c_{i_{1}i_{2}},c_{i_{1}i_{2}i_{3}},c_{i_{1}i_{2}i_{3}i_{4}}$.
The obtained sequence of coefficients $a_{s}(\xi_{1},\ldots,\xi_{s})$ either
truncates at $s=5$ or continues indefinitely. In the former case this leads to
polynomial equations of the above, and in the latter case, results in
equations (81), (82) and (92).

Step 3. Integrability of every equation from the list is shown below either by
transforming to a known integrable equation or by providing the Lax
representation. $\square$

The equations in Theorem 5 can be split into the following four lists:

  * List 1:

Equations related to the stretched Volterra equation: (76)–(81). It is obvious
that (76), (77) and (78) are from the Volterra equation of the form
$u_{t}=(\alpha+\beta u+\gamma
u^{2})(u_{1}-u_{-1}),\alpha,\beta,\gamma\in\mathbb{C}.$ The other equations in
this list are transformed into (76), for which we write as

$w_{t}=w(w_{3}-w_{-3})$ (94)

for clarity, by the following transformations:

$\eqref{eq1}:w=uu_{1}u_{2};\quad\eqref{eq4}:w=uu_{1};\quad\eqref{ser3}:w=\frac{uu_{2}}{u_{1}}.$

  * List 2:

Linearisable equations: (82), which is related to the linear equation
$w_{t}=w_{3}-w_{-3}$ by the transformation $u=ww_{1}w_{2}$.

  * List 3:

Equations related to the Narita-Itoh-Bogoyavlensky equation: (83)–(88).
Equation (83) is the well-known Narita-Itoh-Bogoyavlensky chain. All other are
related to it. To be clear, we write it in different variable

$w_{t}=w\left(w_{3}+w_{2}+w_{1}-w_{-1}-w_{-2}-w_{-3}\right).$ (95)

The transformations are as follows:

$\eqref{bg1}:w=uu_{1}u_{2};\ \eqref{bg11}:w=uu_{1}u_{2}u_{3};\
\eqref{bg12}:w=uu_{1}u_{2}(u_{3}+1);\ \eqref{eq51}:w=uu_{2};\
\eqref{eq31}:w=uu_{1}.$

  * List 4:

Other equations: (89)–(92). Equations (89) and (90) appeared in [26] as
discrete Sawada-Kotera equations and they are related by $u\to uu_{1}$.
Equations (91) and (92) are new to best of our knowledge. We are going to show
their integrability in Section 6.3 by presenting their Lax representations.

###  6.2 Integrable hierarchies of higher orders

The Narita-Itoh-Bogoyavlensky (NIB) lattice (50) is a family of integrable
equations of order $(-n,n),\ n\in\mathbb{N}$. For any two distinct values of
$n$, the corresponding flows do not commute and belong to different integrable
hierarchies. We shall call them $n$–relatives of the NIB family. Equations
(52), (73) and (83) are $1-,\ 2-$ and $3$–relatives respectively. In this
section, we explore higher order relatives of all integrable equations listed
in Theorem 5.

  * List 1:

Equations (76), (77) and (78) are particular cases of the equation

$u_{t}=(\alpha+\beta u+\gamma
u^{2})(u_{n}-u_{-n}),\quad\alpha,\beta,\gamma\in\mathbb{C}$

which is obtained from the integrable Volterra type equation
$u_{t}=(\alpha+\beta u+\gamma u^{2})(u_{1}-u_{-1})$ by stretching of the
discrete variable.

The other equations in the List 1 can be transformed into (94) and their
integrable higher order relatives can transformed into

$w_{t}=w(w_{n}-w_{-n}).$ (96)

Equation (79) is the $3$–relative of the family

$\displaystyle
u_{t}=u\left(\prod_{k=1}^{n}u_{k}-\prod_{k=1}^{n}u_{-k}\right)-u^{2}\left(\prod_{k=1}^{n-1}u_{k}-\prod_{k=1}^{n-1}u_{-k}\right).$

The latter can be mapped into (96) by the transformation
$w=\prod_{k=0}^{n-1}u_{k}$. When $n=2$, it reduces to equation
${\rm(E.1^{\prime})}$ in [25].

The family

$\displaystyle
u_{t}=u\sum_{i=0}^{n-1}(-1)^{i}\left(u_{n-1-i}u_{n-i}-u_{i+1-n}u_{i-n}\right),$

is transformed to (96) by setting $w=uu_{1}$. It reduces to equation
${\rm(E.1^{\prime})}$ in [25] when $n=2$ and to equation (80) when $n=3$.

Equation (81) is the $1$–relative in the family

$\displaystyle
u_{t}=u\left(\prod_{l=1}^{n}\frac{u_{2l-1}}{u_{2l}}u_{2n+1}+\prod_{l=0}^{n-1}\frac{u_{2l}}{u_{2l+1}}u_{2n}-\prod_{l=0}^{n-1}\frac{u_{-2l}}{u_{-1-2l}}u_{-2n}-\prod_{l=1}^{n}\frac{u_{1-2l}}{u_{-2l}}u_{-2n-1}\right),$

which reduces to $w_{t}=w(w_{2n+1}-w_{-2n-1})$ by the transformation
$w=\prod_{l=0}^{n-1}\frac{u_{2l}}{u_{2l+1}}u_{2n}$.

  * List 2:

Equation (82) can be linearised. In general, we let
$u=\prod_{k=0}^{n-1}w_{k}$, where $w$ satisfies a linear equation
$w_{t}=w_{n}-w_{-n}$. Note that $\frac{u_{k+1}}{u_{k}}=\frac{w_{n+k}}{w_{k}}$
and $\frac{u_{-k}}{u_{1-k}}=\frac{w_{-k}}{w_{n-k}}$ for $k>0$. Thus

$\displaystyle
u_{t}=\sum_{k=0}^{n-1}\frac{u}{w_{k}}(w_{n+k}-w_{k-n})=u\sum_{k=0}^{n-1}(\frac{u_{k+1}}{u_{k}}-\frac{w_{-1-k}}{w_{n-1-k}})=u\sum_{k=0}^{n-1}(\frac{u_{k+1}}{u_{k}}-\frac{u_{-1-k}}{u_{-k}}).$
(97)

Thus, $1$–relative of the family (97) is a linear equation, $2$–relative is a
special case of ${\rm(E.8)}$ in [25] and $3$–relative is (82).

  * List 3:

As we mentioned at the beginning of this section, equation (83) is
$3$–relative of the NIB family (50), which here we write in different variable
for convenience

$w_{t}=w\left(w_{n}+\cdots+w_{1}-w_{-1}-\cdots-w_{-n}\right).$ (98)

The families corresponding to equations (84)–(88) we denote as
$\eqref{bg1}_{n}-\eqref{eq31}_{n}$. They are can be transformed to (98) by
polynomial maps:

$\displaystyle\eqref{bg1}_{n}:\quad
u_{t}=u\left(\prod_{j=1}^{n}u_{j}-\prod_{j=1}^{n}u_{-j}\right),\quad\quad\quad
w=\prod_{j=0}^{n-1}u_{j};$ (99) $\displaystyle\eqref{bg11}_{n}:\quad
u_{t}=u^{2}\left(\prod_{j=1}^{n}u_{j}-\prod_{j=1}^{n}u_{-j}\right),\quad\quad\
\ w=\prod_{j=0}^{n}u_{j};$ (100) $\displaystyle\eqref{bg12}_{n}:\quad
u_{t}=(u^{2}+u)\\!\\!\left(\prod_{j=1}^{n}u_{j}-\prod_{j=1}^{n}u_{-j}\\!\\!\right),\quad
w=\prod_{j=0}^{n-1}u_{j}(u_{n}+1);$ (101) $\displaystyle\eqref{eq51}_{n}:\quad
u_{t}=u\sum_{i=0}^{\lfloor{\frac{n-1}{2}}\rfloor}\left(u_{\lfloor{\frac{n}{2}}\rfloor-i}u_{n-i}-u_{i-\lfloor{\frac{n}{2}}\rfloor}u_{i-n}\right),\quad\quad
w=uu_{\lceil{\frac{n}{2}}\rceil};$ (102) $\displaystyle\eqref{eq31}_{n}:\quad
u_{t}=u\sum_{l=0}^{\lfloor{\frac{n-1}{2}}\rfloor}(u_{n-2l-1}u_{n-2l}-u_{2l+1-n}u_{2l-n}),\quad\
w=uu_{1}.$ (103)

Here $\lfloor\cdot\rfloor$ and $\lceil\cdot\rceil$ are floor and ceiling
functions respectively, and these can be checked by direct computation. For
example, for (101), we have

$\displaystyle w_{t}$ $\displaystyle=$ $\displaystyle
w\sum_{k=0}^{n-1}(u_{k}+1)\left(\prod_{j=1}^{n}u_{j+k}-\prod_{j=1}^{n}u_{k-j}\right)+wu_{n}\left(\prod_{j=1}^{n}u_{n+j}-\prod_{j=1}^{n}u_{n-j}\right)$
$\displaystyle=$ $\displaystyle
w\sum_{k=0}^{n-1}\left(w_{k}-\prod_{j=0}^{n-1}u_{j+k}+\prod_{j=0}^{n-1}u_{j+1+k}-w_{k-n}\right)+w\left(w_{n}-\prod_{j=1}^{n}u_{n+j}-w+\prod_{j=0}^{n-1}u_{j}\right),$

which is (98) after straightforward simplification.

The families (84) and (85) are two known modifications of the Narita-Itoh-
Bogoyavlensky family [19]. The family (101) can be found in a recent paper
[27] on discrete integrable equations of higher order.

  * List 4:

Equation (89) and its family

$\displaystyle
u_{t}=u^{2}\left(\prod_{k=1}^{n}u_{k}-\prod_{k=1}^{n}u_{-k}\right)-u\left(\prod_{k=1}^{n-1}u_{k}-\prod_{k=1}^{n-1}u_{-k}\right).$
(104)

have been previously found by Adler and Postnikov [26], where the authors also
presented the corresponding fractional Lax representation. This family can be
viewed as an inhomogeneous deformation of the modified Narita-Itoh-
Bogoyavlensky family (100). When $n=2l+1,l\geq 1$ we can use the
transformation $w=uu_{1}$ which maps the family (104) into the family

$\displaystyle
w_{t}=w\sum_{i=0}^{1}\left(\prod_{k=0}^{l}w_{2k+i}-\prod_{k=0}^{l}w_{-2k-i}-\prod_{k=1}^{l}w_{2k-i}+\prod_{k=1}^{l}w_{-2k+i}\right).$
(105)

Equation (90) is $1$–relative of the family (105).

It seems that equation (91) has not appeared in the literature previously. It
belongs to a new family of integrable equations111After we have completed this
work, we found out that this equation and the family (106) were known to V.E.
Adler. He kindly sent us his unpublished notes, also containing their Lax
representations. Under his permission, we present the Lax representation in
Section 7 for completeness.

$\displaystyle u_{t}$ $\displaystyle=$ $\displaystyle
u({\mathcal{S}}^{2n-1}-1)\left((u-1)\prod_{l=1}^{n-1}u_{-l}+(u_{1-2n}-1)\prod_{l=n}^{2n-2}u_{-l}\right).$
(106)

Its $1$–relative reduces to the Volterra chain (52), while $2$–relative
coincides with (91). We also explicitly check that the $3-$ and $4$–relatives
of the family, namely

$\displaystyle
u_{t}=u({\mathcal{S}}^{5}-1)\left((u-1)u_{-1}u_{-2}+u_{-3}u_{-4}(u_{-5}-1)\right),$
$\displaystyle
u_{t}=u({\mathcal{S}}^{7}-1)\left((u-1)u_{-1}u_{-2}u_{-3}+u_{-4}u_{-5}u_{-6}(u_{-7}-1)\right),$

possess quasi-local canonical formal recursion operators.

Equation (92) is another new equation. Its family and Lax representation we
discuss in the next Section 6.3.

######  Remark 4.

We have already seen that one low order equation may belong to several
integrable families. For example the Volterra equation (52) is $1$–relative in
(50) and (106) families. Equation (88) belongs to the family (103) as well as
the family

$u_{t}=u\left((1+{\mathcal{S}}^{-\lceil\frac{n}{2}\rceil})\prod_{i=0}^{\lfloor{\frac{n-1}{2}}\rfloor}u_{n-i}-(1+{\mathcal{S}}^{\lceil\frac{n}{2}\rceil})\prod_{i=0}^{\lfloor{\frac{n-1}{2}}\rfloor}u_{i-n}\right),\quad
w=\prod_{i=0}^{\lfloor{\frac{n-1}{2}}\rfloor}u_{i}.$

which has the same $w$ ancestor (98).

###  6.3 Integrable deformation of the Narita-Itoh-Bogoyavlensky lattice

In this section, we study the integrability of the equation

$\displaystyle
u_{t}=(1+u^{2})(u_{n}\prod_{k=1}^{n-1}\sqrt{1+u_{k}^{2}}-u_{-n}\prod_{k=1}^{n-1}\sqrt{1+u_{-k}^{2}}),\quad
n\in\mathbb{N}.$ (107)

It can be viewed as an inhomogeneous deformation of the Narita-Itoh-
Bogoyavlensky equation (100). Indeed, after the re-scaling
$u_{k}\to\varepsilon^{-1}u_{k},\ t\to\varepsilon^{n+1}t$ and in the limit
$\varepsilon\to 0$ it turns into (100). In the case $n=2$ its integrability
was established in [28].

######  Theorem 6.

Equation (107) possesses a Lax representation $L_{t}=[A,L]$ with a rational
(pseudo-difference) operator $L=Q^{-1}P$, where

$\displaystyle Q=u-wu_{1}{\mathcal{S}}^{-1},\quad
P=(uw_{1}{\mathcal{S}}-u_{1}){\mathcal{S}}^{n-1},\qquad w=\sqrt{1+u^{2}},$

and a skew-symmetric difference operator $A=L_{+}-(L_{+})^{\dagger}$. Here
$L_{+}$ denotes the polynomial part of the Laurent representation for the
rational operator $L$.

Proof. Note that

$Q^{-1}=(1-\frac{wu_{1}}{u}{\mathcal{S}}^{-1})^{-1}\frac{1}{u}=-(1+\frac{wu_{1}}{u}{\mathcal{S}}^{-1}+\frac{wu_{1}}{u}{\mathcal{S}}^{-1}\frac{wu_{1}}{u}{\mathcal{S}}^{-1}+\cdots)\frac{1}{u}.$

Thus

$\displaystyle
L_{+}=a^{(n)}{\mathcal{S}}^{n}+a^{(n-1)}{\mathcal{S}}^{n-1}\cdots+a^{(1)}{\mathcal{S}},$
$\displaystyle a^{(n)}=w_{1},\ a^{(n-1)}=uu_{1},\ a^{(n-l)}=ww_{-1}\cdots
w_{2-l}u_{1}u_{1-l},\ 2\leq l\leq n-1.$

These are the coefficients of positive shifts in $A$. For the negative parts,
we have

$a^{(-l)}=-{\mathcal{S}}^{-l}a^{(l)}=-a^{(l)}_{-l}.$

The Lax equation $L_{t}=[A,L]$ implies that there exists a difference operator
$B$ such that

$\displaystyle P_{t}=BP-PA,\qquad Q_{t}=BQ-QA,$ (108)

where the operator $B=\sum_{l=-n}^{n}b^{(l)}{\mathcal{S}}^{l}$ can be
determined by $A$, $P$ and $Q$. To do so, we write down the equivalent
equations for (108) according to the orders of ${\mathcal{S}}$. Using the
equation for the operator $Q$, we get

$\displaystyle{\mathcal{S}}^{n}:$ $\displaystyle b^{(n)}u_{n}=ua^{(n)};$ (109)
$\displaystyle{\mathcal{S}}^{l}:$ $\displaystyle
b^{(l+1)}u_{l+2}w_{l+1}-b^{(l)}u_{l}-u_{1}wa_{-1}^{(l+1)}+ua^{(l)}=0,\ 1\leq
l\leq n-1\ \mbox{or}\ -n\leq l\leq-2;$ (110) $\displaystyle{\mathcal{S}}^{0}:$
$\displaystyle u_{t}=-b^{(1)}u_{2}w_{1}+b^{(0)}u+u_{1}wa_{-1}^{(1)};$ (111)
$\displaystyle{\mathcal{S}}^{-1}:$ $\displaystyle
u_{1t}w+u_{1}w_{t}=b^{(0)}u_{1}w-b^{(-1)}u_{-1}+ua^{(-1)};$ (112)
$\displaystyle{\mathcal{S}}^{-n-1}:$ $\displaystyle
b^{(-n)}u_{1-n}w_{-n}=u_{1}wa_{-1}^{(-n)}=-u_{1}ww_{-n}.$ (113)

From (109), it follows that $b^{(n)}=\frac{uw_{1}}{u_{n}}$. We substitute it
into (110) for $l=n-1$ and obtain

$\displaystyle
b^{(n-1)}=\frac{1}{u_{n-1}}\left(b^{(n)}u_{n+1}w_{n}-u_{1}wa_{-1}^{(n)}+ua^{(n-1)}\right)$
$\displaystyle\quad=\frac{1}{u_{n-1}}\left(\frac{uw_{1}}{u_{n}}u_{n+1}w_{n}-u_{1}w2+u^{2}u_{1}\right)=\frac{uu_{n+1}w_{1}w_{n}}{u_{n}u_{n-1}}-\frac{u_{1}}{u_{n-1}}.$

When $1\leq l\leq n-2$ notice that $-u_{1}wa_{-1}^{(l+1)}+ua^{(l)}=0.$ Thus in
this case (110) becomes

$b^{(l)}u_{l}=b^{(l+1)}u_{l+2}w_{l+1},$

which leads to

$\displaystyle b^{(l)}=\frac{u_{n-1}u_{n}}{u_{l}u_{l+1}}w_{l+1}\cdots
w_{n-1}b^{(n-1)}=\frac{1}{u_{l}u_{l+1}}\left(\prod_{j=l+1}^{n-1}w_{j}\right)\left(uu_{n+1}w_{1}w_{n}-u_{1}u_{n}\right).$

Similarly, from (113), we get $b^{(-n)}=-\frac{u_{1}w}{u_{1-n}}$. Substituting
it into (110) for $l=-n$, we have

$\displaystyle
b^{(-n+1)}=\frac{1}{u_{2-n}w_{1-n}}\left(b^{(-n)}u_{-n}+u_{1}wa_{-1}^{(1-n)}-ua^{(-n)}\right)$
$\displaystyle\quad=\frac{1}{u_{2-n}w_{1-n}}\left(-\frac{u_{1}w}{u_{1-n}}u_{-n}-u_{1}wu_{-n}u_{1-n}+uw_{1-n}\right)=\frac{uu_{1-n}-u_{1}u_{-n}ww_{1-n}}{u_{1-n}u_{2-n}}\
.$ (114)

When $1-n\leq l\leq-2$, notice that

$\displaystyle-
u_{1}wa_{-1}^{(l+1)}+ua^{(l)}=u_{1}w{\mathcal{S}}^{l}a^{(-l-1)}-u{\mathcal{S}}^{l}a^{(-l)}=u_{1}w\left(\prod_{k=0}^{n+l-1}w_{l-k}\right)u_{l+1}u_{-n}-u\left(\prod_{k=0}^{n+l-2}w_{l-k}\right)u_{l+1}u_{1-n}$
$\displaystyle\qquad=-\left(\prod_{k=0}^{n+l-2}w_{l-k}\right)u_{l+1}(uu_{1-n}-u_{1}u_{-n}ww_{1-n}).$
(115)

Thus combining (114) and (115), using (110) we obtain, for $2-n\leq l\leq-1$,

$\displaystyle
b^{(l)}=\frac{1}{u_{l}u_{l+1}}\left(\prod_{j=2-n}^{l}w_{j}\right)\left(uu_{1-n}-u_{1}u_{-n}ww_{1-n}\right).$

We now eliminate $b^{(0)}$ from (111) and (112) and get

$\displaystyle\qquad
u_{1t}w+u_{1}w_{t}-\frac{u_{1}w}{u}u_{t}=wu_{1t}-\frac{u_{1}}{uw}u_{t}$
$\displaystyle=\frac{u_{1}w}{u}\left(b^{(1)}u_{2}w_{1}-u_{1}wa_{-1}^{(1)}\right)-b^{(-1)}u_{-1}+ua^{(-1)}=\frac{u_{1}u_{2}ww_{1}}{u}b^{(1)}-\frac{u_{1}^{2}w^{2}}{u}a_{-1}^{(1)}-b^{(-1)}u_{-1}-ua_{-1}^{(1)}$
$\displaystyle=\frac{ww_{1}}{u}\left(\prod_{j=2}^{n-1}w_{j}\right)\left(uu_{n+1}w_{1}w_{n}-u_{1}u_{n}\right)-\frac{1}{u}\left(\prod_{j=1}^{n-2}w_{-j}\right)\left(uu_{1-n}-u_{1}u_{-n}ww_{1-n}\right)$
$\displaystyle\quad-\frac{u_{1}^{2}w^{2}+u^{2}}{u}\left(\prod_{j=1}^{n-2}w_{-j}\right)uu_{1-n}$
$\displaystyle=\left(w{\mathcal{S}}-\frac{u_{1}}{uw}\right)w^{2}\left(\left(\prod_{j=1}^{n-1}w_{j}\right)u_{n}-\left(\prod_{j=1}^{n-1}w_{-j}\right)u_{-n}\right),$

which is satisfied by the given equation. Finally, we check the obtained $B$
is consistent with the equation for the operator $P$ in (108) by directly
computation, and thus we proved the statement. $\Box$

######  Remark 5.

In [28], Garifullin and Yamilov established the integrability properties of
the equation

$\displaystyle
u_{t}=(u^{2}-1)\left(\sqrt{u_{1}^{2}-1}u_{2}-\sqrt{u_{-1}^{2}-1}u_{-2}\right),$

which is the equation (107) when $n=2$ under the scaling transformation. They
provided its Lax pair as $L\psi=0$ and $\psi_{t}=A\psi$ with

$\displaystyle
L=uw^{\prime}_{1}{\mathcal{S}}^{2}+u_{1}{\mathcal{S}}-\lambda\left(u_{1}w^{\prime}{\mathcal{S}}^{-1}-u\right);\qquad
w^{\prime}=\sqrt{u^{2}-1},$ $\displaystyle
A=\frac{w^{\prime}}{u}\left(w^{\prime}(u_{1}{\mathcal{S}}+u_{-1}{\mathcal{S}}^{-1})-\lambda^{-1}u_{-1}{\mathcal{S}}+\lambda
u_{1}{\mathcal{S}}^{-1}\right).$

This is the same as the Lax representation given in the theorem (after
rescaling and simple gauge). Let
$P=uw^{\prime}_{1}{\mathcal{S}}^{2}+u_{1}{\mathcal{S}}$ and
$Q=u_{1}w^{\prime}{\mathcal{S}}^{-1}-u$. If we eliminate $\lambda$ in $A$, we
get

$\displaystyle A=\frac{w^{\prime 2}u_{1}}{u}{\mathcal{S}}+\frac{w^{\prime
2}u_{-1}}{u}{\mathcal{S}}^{-1}-\frac{w^{\prime}u_{-1}}{u}{\mathcal{S}}P^{-1}Q+\frac{w^{\prime}u_{1}}{u}{\mathcal{S}}^{-1}Q^{-1}P$
$\displaystyle=\frac{w^{\prime 2}u_{1}}{u}{\mathcal{S}}+\frac{w^{\prime
2}u_{-1}}{u}{\mathcal{S}}^{-1}-\frac{1}{u}{\mathcal{S}}^{-1}(u_{1}w^{\prime}{\mathcal{S}}^{-1}-u)+P^{-1}Q+\frac{1}{u}(uw^{\prime}_{1}{\mathcal{S}}^{2}+u_{1}{\mathcal{S}})+Q^{-1}P$
$\displaystyle=w^{\prime}_{1}{\mathcal{S}}^{2}+uu_{1}{\mathcal{S}}+uu_{-1}{\mathcal{S}}^{-1}-w^{\prime}_{-1}{\mathcal{S}}^{-2}+P^{-1}Q+Q^{-1}P,$

where the nonlocal part commutes with the fractional operator $Q^{-1}P$ and
thus we can discard it.

We prove that the hierarchy of commuting symmetries is well defined for any
$n\in\mathbb{N}$. To do so, we use the $r$-matrix approach [29]. We consider
the Lie algebra denoted by ${\mathfrak{g}}$ of the formal Laurent series of
the shift operator with the commutator $[A,B]=AB-BA$, where
$A,B\in{\mathfrak{g}}$. It is easy to see that any element

$B=b^{(m)}{\mathcal{S}}^{m}+b^{(m-1)}{\mathcal{S}}^{m-1}+\cdots\in{\mathfrak{g}}$

admits a unique decomposition of the form

$B=B_{+}-(B_{+})^{\dagger}+H,$

where $B_{+}$ is a difference operator with positive powers of
${\mathcal{S}}$. We denote the antisymmetric part $B_{+}-(B_{+})^{\dagger}$ of
any element $B$ as ${\mathfrak{g}}_{+}$ and the other part $H$ as
${\mathfrak{g}}_{-}$. It is obvious that these both parts form Lie
subalgebras. Thus we have the decomposition of the Lie algebra

${\mathfrak{g}}={\mathfrak{g}}_{+}\oplus{\mathfrak{g}}_{-}$

into the direct sum of two Lie subalgebras. We define the projections

$\pi_{\pm}:{\mathfrak{g}}\rightarrow{\mathfrak{g}}_{\pm}$

and the $r$-matrix $r=\frac{1}{2}(\pi_{+}-\pi_{-}).$ We now formulate the
statement generating commuting symmetries, which can be proved in the standard
way in the $r$-matrix approach [29].

Corollary. The flows defined by the Lax equations
$\partial_{t_{p}}L=[\pi_{+}(L^{p}),\ L]$ commute with each other.

Proof. Let $A^{(p)}=\pi_{+}(L^{p})$. Using Lax equations, we have

$\displaystyle\partial_{t_{q}}\partial_{t_{p}}L-\partial_{t_{p}}\partial_{t_{q}}L=[\partial_{t_{q}}A^{(p)}-\partial_{t_{p}}A^{(q)}-[A^{(q)},A^{(p)}],L].$

So it is sufficient to show that

$\partial_{t_{q}}A^{(p)}-\partial_{t_{p}}A^{(q)}-[A^{(q)},A^{(p)}]=0.$

For $l\in\mathbb{Z}$, we have $\partial_{t_{p}}L^{l}=[A^{(p)},L^{l}]$ since

$\displaystyle[\partial_{t_{p}}L^{l},\
L]=-[L^{l},\partial_{t_{p}}L]=-[L^{l},[A^{(p)},L]]=[[A^{(p)},L^{l}],L]\ .$

Thus

$\displaystyle\partial_{t_{q}}A^{(p)}-\partial_{t_{p}}A^{(q)}-[A^{(q)},A^{(p)}]$
$\displaystyle=\pi_{+}(\partial_{t_{q}}L^{p})-\pi_{+}(\partial_{t_{p}}L^{q})-[A^{(q)},A^{(p)}]=\pi_{+}([A^{(q)},L^{p}])-\pi_{+}([A^{(p)},L^{q}])-[A^{(q)},A^{(p)}]$
$\displaystyle=\pi_{+}([-\pi_{-}(L^{q}),L^{p}])-\pi_{+}([-\pi_{-}(L^{p}),L^{q}])-[L^{q}-\pi_{-}(L^{q}),L^{p}-\pi_{-}(L^{p})]$
$\displaystyle=\pi_{+}(-[\pi_{-}(L^{q}),\pi_{-}(L^{p})])=0.$

This leads to
$\partial_{t_{q}}\partial_{t_{p}}L=\partial_{t_{p}}\partial_{t_{q}}L$ as
required. $\diamond$

##  7 Summary and Discussion

In order to give an exhaustive description of all integrable differential-
difference equations of certain type one needs to find strong and verifiable
necessary integrability conditions. All previous attempts to tackle this
problem were based on the integrability conditions dependent of the symmetry
structure of equations which may not be known in advance. In this paper, we
developed an approach to establish the universal integrability conditions by
introducing the notion of quasi-locality in the context of symbolic
representation. We proved that if an equation of the form

$u_{t}=f=f(u_{-n},\ldots,u_{n}),\qquad f=\sum_{i\geq 1}f^{(i)},\qquad
f^{(i)}\in{\cal R}^{i},\qquad\ \ f^{(1)}\neq 0,$

possesses an infinite dimensional algebra of its symmetries, then there exists
a unique quasi-local formal recursion operator with symbolic representation

$\eta+\sum_{p\geq 1}\hat{u}^{p}\phi_{p}(\xi_{1},\ldots,\xi_{p},\eta).$

Moreover, the recursive formulae for all terms
$\phi_{p}(\xi_{1},\ldots,\xi_{p},\eta)$ are explicitly given. This is achieved
by developing symbolic representation for the difference polynomial ring,
difference operators and formal series. The requirement of quasi-locality for
all terms $\phi_{p}(\xi_{1},\ldots,\xi_{p},\eta)$ leads to the necessary
integrability conditions, which are independent on the structure of the
symmetry algebra.

We applied our new approach to classification of integrable equations of the
form (74). We reproduced the integrable equations of such type in [15] for
$n=2$, and obtained a complete list of integrable equations for $n=3$, which
includes 17 equations which are complimentary to the lower order hierarchies.
For each equation in the list we found an infinite family of integrable
equations of arbitrary high order. Integrability of the families obtained we
proved in each case either by providing a transformations to a known
integrable family, or by presenting a Lax representation.

Here, for completeness, we would like present a fractional Lax representation

$L_{t}=[A,L],\ L=Q^{-1}P,\ \Leftrightarrow\ P_{t}=BP-PA,\quad Q_{t}=BQ-QA$

for the new family of equations (106) found by Adler [18] in which

$\displaystyle
P=\left(\prod_{l=0}^{n-1}u_{l}\right){\mathcal{S}}^{2n}+{\mathcal{S}};\ \
A=-\left(\prod_{l=-n}^{n-2}u_{l}\right){\mathcal{S}}^{2n-1}+\sum_{j=0}^{2n-2}\left((1-u_{j-n})\prod_{l=n+1}^{2n-1}u_{j-l}\right)+{\mathcal{S}}^{1-2n};$
$\displaystyle Q=\left(\prod_{l=0}^{n-2}u_{l}\right){\mathcal{S}}^{2n-1}+1;\ \
B=-\left(\prod_{l=0}^{2n-2}u_{l}\right){\mathcal{S}}^{2n-1}+\sum_{j=0}^{2n-2}\left((1-u_{j-2n+1})\prod_{l=n}^{2n-2}u_{j-l}\right)+{\mathcal{S}}^{1-2n}.$

The global classification problem of integrable differential-difference
equations still remains a very challenging problem. In the case of scalar
polynomial evolutionary equations, we believe that there are new integrable
hierarchies of high orders starting from any order. Thus it is impossible to
achieve the global classification result as it was done for scalar evolution
PDEs [6, 7]. The higher the order $n$ is in the equation, the more integrable
equations there are even after we remove the ones being symmetries of lower
order ones. Thus it is important to develop an approach to identify the
transformations between integrable equations and to develop the concept of
integrable families which have been discussed, but not yet defined in this
paper.

Integrable differential-difference equations are generalised symmetries for
discrete integrable equations. The authors of [25] constructed the autonomous
quad-equations which admit as symmetries five-point differential-difference
equations belonging to classification lists in [15]. Recently it was shown
that there exist multi-points integrable discrete equations on a plain lattice
related to Bäcklund-Darboux transformations for the Narita-Itoh-Bogoyavlensky
equation (50) [27, 30]. It would be interesting to construct discrete
integrable equations for families discussed in Section 6.2, in particular, for
the new integrable families (106) and (107).

## Acknowledgments

All authors would like to thank V.E. Adler for useful discussions and sending
us his unpublished research notes. The paper is supported by EPSRC small grant
scheme EP/V050451/1, and partially by grants EP/P012655/1 and EP/P012698/1.
AVM is grateful to the Ministry of Sciences and Higher Education RF (agreement
075-02-2021-1397) for partial support.

## References

  * [1] V. V. Sokolov and A. B. Shabat.  Classification of integrable evolution equations.  In Mathematical physics reviews, Vol. 4, volume 4 of Soviet Sci. Rev. Sect. C: Math. Phys. Rev., pages 221–280. Harwood Academic Publ., Chur, 1984.
  * [2] A. V. Mikhailov, A. B. Shabat, and R. I. Yamilov.  A symmetric approach to the classification of nonlinear equations. Complete lists of integrable systems.  Uspekhi Mat. Nauk, 42(4(256)):3–53, 1987.
  * [3] A. V. Mikhailov, A. B. Shabat, and V. V. Sokolov.  The symmetry approach to classification of integrable equations.  In What is integrability?, Springer Ser. Nonlinear Dynamics, pages 115–184. Springer, Berlin, 1991.
  * [4] I. M. Gel’fand, L. A. Dikii.  Asymptotic properties of the resolvent of Sturm-Liouville equations, and the algebra of Korteweg-de Vries equations.  Uspehi Mat. Nauk, 30(5(185)):67–100, 1975.  English translation: Russian Math. Surveys, 30 (1975), no. 5, 77–113.
  * [5] F. Beukers, J. A. Sanders, Jing Ping Wang.  One symmetry does not imply integrability.  J. Differential Equations, 146(1):251–260, 1998.
  * [6] J. A. Sanders, Jing Ping Wang.  On the integrability of homogeneous scalar evolution equations.  J. Differential Equations, 147(2):410–434, 1998.
  * [7] J. A. Sanders, Jing Ping Wang.  On the integrability of non-polynomial scalar evolution equations.  J. Differential Equations, 166(1):132–150, 2000.
  * [8] A. V. Mikhailov, V. S. Novikov.  Perturbative symmetry approach.  J. Phys. A, 35(22):4775–4790, 2002.
  * [9] A. V. Mikhailov, V. S. Novikov.  Classification of integrable Benjamin-Ono-type equations.  Moscow Mathematical Journal, 3(4):1293–1305, 2003.
  * [10] A. V. Mikhailov, V. S. Novikov, Jing Ping Wang.  On classification of integrable non-evolutionary equations.  Stud. Appl. Math., 118:419–457, 2007.
  * [11] A. V. Mikhailov, V. S. Novikov and Jing Ping Wang.  Symbolic representation and classification of integrable systems. In Algebraic Theory of Differential Equations, 156-216, CUP, eds. M.A.H. MacCallum and A.V. Mikhailov, 2009.
  * [12] V. V. Sokolov.  Algebraic Structures in Integrability.  World Scientific, 2020.
  * [13] R. I. Yamilov.  Classification of discrete evolution equations.  Russian Math. Surveys, 38(6):155-156, 1983.
  * [14] R. I. Yamilov.  Symmetries as integrability criteria for differential difference equations.  J. Phys. A, 39(45):R541-R623, 2006.
  * [15] R. N. Garifullin, R. I. Yamilov, D. Levi.  Classification of five-point differential-difference equations I, II.  J. Phys. A, 50(12):125201, 2017; 51(6):065204, 2018.
  * [16] V. E. Adler.  Necessary integrability conditions for evolutionary lattice equations.  Theor Math Phys,181:1367–1382, 2014.
  * [17] A. V. Mikhailov, Jing Ping Wang, P. Xenitidis.  Recursion operators, conservation laws, and integrability conditions for difference equations.  Theor Math Phys, 167:421–443, 2011.
  * [18] V. E. Adler.  Private Communications.
  * [19] O. I. Bogoyavlenskii.  Algebraic constructions of integrable dynamical systems-extensions of the Volterra system.  Russian Mathematical Surveys, 46(3):1-64, 1991.
  * [20] S. Carpentier, A. V. Mikhailov, Jing Ping Wang.  Rational recursion operators for integrable differential-difference equations.  Communications in Mathematical Physics 370(3): 807–851, 2019.
  * [21] A. V. Mikhailov, V. S. Novikov, Jing Ping Wang, G. Zhao. “Integrability of two-component systems of partial differential equations”, in preparation.
  * [22] F. Khanizadeh, A. V. Mikhailov, and Jing Ping Wang.  Darboux transformations and recursion operators for differential–difference equations.  Theoretical and Mathematical Physics, 177(3):1606–1654, 2013.
  * [23] V. S. Novikov and Jing Ping Wang.  Symmetry structure of integrable nonevolutionary equations.  Stud. Appl. Math., 119(4):393–428, 2007.
  * [24] Jing Ping Wang.  Recursion operator of the Narita-Itoh-Bogoyavlensky lattice.  Stud. Appl. Math., 129(3):309–327, 2012.
  * [25] R. N. Garifullin, G. Gubbiotti and R. I. Yamilov.  Integrable discrete autonomous quad-equations admitting, as generalized symmetries, known five-point differential-difference equations.  Journal of Nonlinear Mathematical Physics, 26(3):333–357, 2019.
  * [26] V. E. Adler, V. V. Postnikov.  Differential-difference equations associated with the fractional Lax operators.  Journal of Physics A: Mathematical and Theoretical, 44(41):415203, 2011.
  * [27] V. E. Adler and V. V. Postnikov.  On discrete $2D$ integrable equations of higher order.  Journal of Physics A: Mathematical and Theoretical, 47(4):045206, 2014.
  * [28] R. N. Garifullin and R. I. Yamilov.  On integrability of a discrete analogue of Kaup-Kupershmidt equation.  Ufa Mathematical Journal, 9(3): 158–164, 2017.
  * [29] M. Blaszak and K. Marciniak.  R-matrix approach to lattice integrable systems.  Journal of Mathematical Physics, 35(9):4661-4682, 1994.