# A discrete Darboux–Lax scheme for integrable difference equations

X. Fisenko<EMAIL_ADDRESS>S. Konstantinou-Rizos
<EMAIL_ADDRESS>P. Xenitidis<EMAIL_ADDRESS>School of
Mathematics, Computer Science and Engineering, Liverpool Hope University, L19
9JD Liverpool, UK

###### Abstract

We propose a discrete Darboux–Lax scheme for deriving auto-Bäcklund
transformations and constructing solutions to quad-graph equations that do not
necessarily possess the 3D consistency property. As an illustrative example we
use the Adler–Yamilov type system which is related to the nonlinear
Schrödinger (NLS) equation [19]. In particular, we construct an auto-Bäcklund
transformation for this discrete system, its superposition principle, and we
employ them in the construction of the one- and two-soliton solutions of the
Adler–Yamilov system.

PACS numbers: 02.30.Ik, 02.90.+p, 03.65.Fd.

Mathematics Subject Classification 2020: 37K60, 39A36, 35Q55, 16T25.

Keywords: Darboux transformations, Bäcklund transformations, quad-graph
equations, partial

Keywords: difference equations, integrable lattice equations, 3D-consistency,
soliton solutions.

##  1 Introduction

It has become understood over the past few decades that integrable systems of
partial difference equations (P$\Delta$Es) are interesting in their own right,
see for instance [15] and references therein. On the one hand, they may model
various natural phenomena, as well as processes in industry and the IT sector.
On the other hand, they have many interesting algebro-geometric properties [6,
15], and are related to many important equations of Mathematical Physics such
as the Yang–Baxter equation and the tetrahedron equation [1, 9, 16, 25].
Moreover, they can be derived from the discretisation of nonlinear partial
differential equations (PDEs). One such approach is provided by the Darboux
transformations of integrable nonlinear PDEs of evolution type [19, 30];
namely, the resulting relations from the permutability of two Darboux
transformations can be interpreted as a P$\Delta$E.

In this paper, we focus on a special class of P$\Delta$Es, the so-called quad-
graph equations, or systems thereof. Quad-graph systems are equations of
P$\Delta$Es defined on an elementary quadrilateral of the two-dimensional
lattice. In particular, they are systems of the form

$Q(f_{00},f_{10},f_{01},f_{11};\alpha,\beta)=0,$ (1)

where $Q$ is a function of its arguments $f_{ij}$, $i,j=0,1$, and may also
depend on parameters $\alpha$ and $\beta$. Schematically, equation (2) can be
represented on the square, where $f_{00}$, $f_{10}$, $f_{01}$ and $f_{11}$ are
placed on vertices of the square and the parameters $\alpha$, $\beta$ are
placed on the edges as in Figure 2. Equation (2) can be thought as a partial
difference equation (P$\Delta$E) by identifying $f$ with a function of two
discrete variables $n,m\in\mathbb{Z}$, and $f_{ij}$ with its shifts in the $n$
and $m$ direction, i.e. $f_{ij}=f(n+i,m+j)$.

.8 (0 0) (1 0) (1 1) (0 1) (0 0)

(0 0) f:0.0 r:0.05 (1 0) f:0.0 r:0.05 (0 1) f:0.0 r:0.05 (1 1) f:0.0 r:0.05

(-.1 -.3) $f$ (.9 -.3) $f_{10}$ (-.1 1.1) $f_{01}$ (.9 1.1) $f_{11}$ (0.44
-.2) $\alpha$ (-.15 .45) $\beta$

Figure 1: Quad–graph equation.

Quad-graph equations have attracted the interest of many researchers in the
field of discrete integrable systems, see [15] for a review. This led to the
developement of methods for solving them, e.g. [2, 13, 15, 24, 26],
classifying them, e.g. [3, 7, 28], analysing their integrability properties,
e.g. [22, 27, 21, 29], and relating them to the theory of Yang–Baxter and
tetrahedron maps, e.g. [11, 25]. Of particular interest are the so-called
3D-consistent equations which can be extended to the three-dimensional lattice
in a consistent way. For such equations a Lax representation and a Bäcklund
transformation can be constructed in a systematic manner by employing the 3D
consistency of the system [15].

In this paper, we propose a discrete Darboux–Lax scheme for deriving Bäcklund
transformations and constructing solutions for quad-graph equations which are
not necessarily 3D consistent but have a Lax representation. More precisely,
we employ gauge-type transformations of the Lax pair and demonstrate how they
give rise to Bäcklund transformations for the discrete system. As an
illustrative example we use the Adler–Yamilov system which was derived as a
discretisation of the NLS equation via a Darboux transformation in [19].

The paper is organised as follows. In the next section we provide all the
necessary definitions for the text to be self-contained. More specifically,
after fixing our notation, we give the definitions of the integrability of a
system of P$\Delta$Es in the sense of the existence of a Lax pair, and of the
Bäcklund transformation. In Section 3 we present the discrete Darboux–Lax
scheme for constructing Bäcklund transformations and solving integrable
P$\Delta$Es which do not necessarily possess the 3D consistency property. In
Section 4 we apply our results to the Adler–Yamilov system given in [19] and
derive the one- and two-soliton solutions by using the associated Bäcklund
transformation and the corresponding Bianchi diagram. Finally, the closing
section contains a summary of the obtained results and a discussion on how
they can be extended and generalised.

##  2 Integrability of difference equations

Let us start this section by introducing our notation. In what follows we deal
with systems of equations which involve unknown functions depending on the two
discrete variables $n$ and $m$. The dependence of a function $f=f(n,m)$ on
these variables will be denoted with indices in the following way.

$f_{ij}=f(n+i,m+j),\quad{\mbox{for all }}i,j\in{\mathbb{Z}}$

We also denote by $\mathcal{S}$ and $\mathcal{T}$ the shift operators in the
$n$ and $m$ direction, respectively. Their action on a function $f$ is defined
as

${\mathcal{S}}^{k}(f_{00})=f_{k0},\quad{\mathcal{T}}^{\ell}(f_{00})=f_{0\ell}.$

We denote vectors with bold face letters, e.g.
$\textbf{f}_{00}=(f_{00}^{(1)},f_{00}^{(2)},\ldots f_{00}^{(k)})$. For systems
of equations we also use bold letters. In particular, a system of quad-graph
equations will be denoted by

$\textbf{Q}({\textbf{f}}_{00},\textbf{f}_{10},\textbf{f}_{01},\textbf{f}_{11})=0.$
(2)

Finally, we denote matrices with roman uppercase letters. For instance
$\rm{L}(\mathbf{f}_{00},\mathbf{f}_{10};\alpha,\lambda)$ denotes a matrix with
elements depending on $\mathbf{f}_{00}$, $\mathbf{f}_{10}$, $\alpha$ and
$\lambda$. The semicolon in the arguments of the matrix is used to separate
the fields $(\mathbf{f}_{00},\mathbf{f}_{10})$ from the parameters $\alpha$,
$\lambda$. By $\lambda$ we denote the spectral parameter throughout the text.

With our notation, let ${\rm{{L}}}(\mathbf{f}_{00},\mathbf{f}_{10};\lambda)$
and ${\rm{M}}(\mathbf{f}_{00},\mathbf{f}_{01};\lambda)$ be two $k\times k$
invertible matrices which depend on a function $\bf{f}$ and the spectral
parameter $\lambda$.111Matrices ${\rm{L}}$, ${\rm{M}}$ may also depend on
parameters but, as they do not play any role in our discussion in this and the
following section, we suppress this dependence. Let also $\Psi=\Psi(n,m)$ be
an auxiliary $k\times k$ matrix, and consider the following overdetermined
linear system.

${\cal{S}}(\Psi)={\rm{L}}(\mathbf{f}_{00},\mathbf{f}_{10};\lambda)\Psi,\qquad{\cal{T}}(\Psi)={\rm{M}}(\mathbf{f}_{00},\mathbf{f}_{01};\lambda)\Psi.$
(3)

For given $\bf{f}$, this system has a solution $\Psi$ provided that the two
equations are consistent, i.e. the compatibility condition
${\cal{T}}\left({\cal{S}}(\Psi)\right)={\cal{S}}\left({\cal{T}}(\Psi)\right)$
holds. The latter condition can be written explicitly as

${\rm{L}}(\mathbf{f}_{01},\mathbf{f}_{11};\lambda){\rm{M}}(\mathbf{f}_{00},\mathbf{f}_{01};\lambda)={\rm{M}}(\mathbf{f}_{10},\mathbf{f}_{11};\lambda){\rm{L}}(\mathbf{f}_{00},\mathbf{f}_{10};\lambda).$
(4)

If the above equation holds if and only if $\bf{f}$ satisfies (2), then we say
that system of P$\Delta$Es (2) is _integrable_ , system (3) is a _Lax pair_
for (2), and equation (4) is called a _Lax representation_ for (2). Moreover,
matrices ${\rm{{L}}}(\mathbf{f}_{00},\mathbf{f}_{10};\lambda)$ and
${\rm{M}}(\mathbf{f}_{00},\mathbf{f}_{01};\lambda)$ are referred to as _Lax
matrices_ , and without loss of generality we assume that they have constant
determinants.

We close this section by giving the definition of Bäcklund transformation for
quad-graph equations. Such transformations are related to the notion of
integrability as it will become evident in the next section where we explore
their connection to Lax pairs via the Darboux–Lax scheme.

######  Definition 2.1.

Let
${\bf{Q}}[{\bf{f}}]:={\bf{Q}}({\bf{f}}_{00},{\bf{f}}_{10},{\bf{f}}_{01},{\bf{f}}_{11})=0$
and
${\bf{P}}[{\bf{g}}]:={\bf{P}}({\bf{g}}_{00},{\bf{g}}_{10},{\bf{g}}_{01},{\bf{g}}_{11})=0$
be two systems of quad-graph equations. Let also

$\mathcal{B}(\mathbf{f}_{00},\mathbf{f}_{10},\mathbf{f}_{01},\mathbf{g}_{00},\mathbf{g}_{10},\mathbf{g}_{01};\varepsilon)=0$
(5)

be a system of P$\Delta$Es. If system $\mathcal{B}=0$ can be integrated for
$\bf{g}$ provided that $\bf{f}$ is a solution of $\mathbf{Q}[{\bf{f}}]=0$, and
the resulting ${\bf{g}}(n,m)$ is a solution to $\mathbf{P}[{\bf{g}}]=0$, and
vice versa, then system (5) is called a (hetero-) Bäcklund transformation for
equations ${\bf{Q}}[{\bf{f}}]=0$ and ${\bf{P}}[{\bf{g}}]=0$. If
$\mathbf{Q}[{\bf{a}}]=\mathbf{P}[{\bf{a}}]$, then (5) is called an auto-
Bäcklund transformation for equation ${\bf{Q}}[{\bf{f}}]=0$.

##  3 Discrete Darboux–Lax scheme

It is well known that for quad-graph systems which possess the 3D consistency
property a Lax representation can be derived algorithmically [23, 5, 8, 15]
and a Bäcklund transformation can be constructed systematically [2, 15].
However, there do exist quad-graph systems which have a Lax pair but do not
possess the 3D consistency property. For this kind of systems we propose here
a scheme for constructing Darboux and Bäcklund transformations. It should be
emphasized here that this scheme works for _any_ system of difference
equations irrespectively of their 3D consistency.

For the integrable quad-graph system

$\mathbf{Q}(\mathbf{f}_{00},\mathbf{f}_{10},\mathbf{f}_{01},\mathbf{f}_{11})=0\quad\Longleftrightarrow\quad{\rm{L}}(\mathbf{f}_{01},\mathbf{f}_{11};\lambda){\rm{M}}(\mathbf{f}_{00},\mathbf{f}_{01};\lambda)={\rm{M}}(\mathbf{f}_{10},\mathbf{f}_{11};\lambda){\rm{L}}(\mathbf{f}_{00},\mathbf{f}_{10};\lambda),$
(6)

we define the discrete Darboux transformation as follows.

######  Definition 3.1.

A discrete Darboux transformation for the integrable P$\Delta$E (6) is a
gauge-like, spectral parameter-dependent transformation that leaves Lax
matrices $\rm{L}$ and $\rm{M}$ covariant. That is, a transformation which
involves an invertible matrix $\rm{B}$ such that

$\displaystyle{\rm{L}}(\mathbf{f}_{00},\mathbf{f}_{10};\lambda)\longmapsto{\rm{L}}(\tilde{\mathbf{f}}_{00},\tilde{\mathbf{f}}_{10};\lambda)={\cal{S}}({\rm{B}}){\rm{L}}(\mathbf{f}_{00},\mathbf{f}_{10};\lambda){\rm{B}}^{-1},$
(7a)
$\displaystyle{\rm{M}}(\mathbf{f}_{00},\mathbf{f}_{01};\lambda)\longmapsto{\rm{M}}(\tilde{\mathbf{f}}_{00},\tilde{\mathbf{f}}_{01};\lambda)={\cal{T}}({\rm{B}}){\rm{M}}(\mathbf{f}_{00},\mathbf{f}_{01};\lambda){\rm{B}}^{-1}.$
(7b)

A consequence of the above definition is the following proposition.

######  Proposition 3.2.

The Darboux transformation maps fundamental solutions of the linear system

${\cal{S}}(\Psi)={\rm{L}}(\mathbf{f}_{00},\mathbf{f}_{10};\lambda)\Psi,\quad{\cal{T}}(\Psi)={\rm{M}}(\mathbf{f}_{00},\mathbf{f}_{01};\lambda)\Psi,$
(8)

to fundamental solutions of the linear system

${\cal{S}}(\tilde{\Psi})={\rm{L}}(\tilde{\mathbf{f}}_{00},\tilde{\mathbf{f}}_{10};\lambda)\tilde{\Psi},\quad{\cal{T}}(\tilde{\Psi})={\rm{M}}(\tilde{\mathbf{f}}_{00},\tilde{\mathbf{f}}_{01};\lambda)\tilde{\Psi},$
(9)

via the relation $\tilde{\Psi}={\rm{B}}\Psi$.

###### Proof.

Let $\Psi=\Psi(n,m)$ be a fundamental solution of the linear problem (8). We
set $\tilde{\Psi}={\rm{B}}\Psi$ and then we shift in the $n$ direction to find
that

${\cal{S}}(\tilde{\Psi})={\cal{S}}({\rm{B}}){\cal{S}}(\Psi)\stackrel{{\scriptstyle\eqref{linear-
sys-1}}}{{=}}{\cal{S}}({\rm{B}}){\rm{L}}(\mathbf{f}_{00},\mathbf{f}_{10};\lambda)\Psi\stackrel{{\scriptstyle\eqref{Darboux-
def-L}}}{{=}}{\rm{L}}(\tilde{\mathbf{f}}_{00},\tilde{\mathbf{f}}_{10};\lambda){\rm{B}}\Psi={\rm{L}}(\tilde{\mathbf{f}}_{00},\tilde{\mathbf{f}}_{10};\lambda)\tilde{\Psi}.$

Similarly, starting with $\tilde{\Psi}={\rm{B}}\Psi$ we shift in the $m$
direction and employ (8) and (7b) to find that
${\cal{T}}(\tilde{\Psi})={\rm{M}}(\tilde{\mathbf{f}}_{00},\tilde{\mathbf{f}}_{01};\lambda)\tilde{\Psi}$.
Moreover, the solution $\tilde{\Psi}$ is fundamental, since $\Psi$ is
fundamental and $\det(\tilde{\Psi})=\det{\rm{B}}\det{\Psi}\neq 0$. ∎

Using the above definition of the discrete Darboux transformation and
corresponding Darboux matrix, we propose the following approach for the
construction of a Darboux matrix and Bäcklund transformation, as well as for
the derivation of the superposition principle for the Bäcklund transformation.

  * •

We start by assuming an initial form for matrix $\rm{B}$. The simplest
assumption we can make is that matrix ${\rm{B}}$ depends linearly on the
spectral parameter, i.e.

${\rm{B}}=\lambda{\rm{B}}^{(1)}+{\rm{B}}^{(0)},$ (10)

where matrices ${\rm{B}}^{(1)}$ and ${\rm{B}}^{(0)}$ do not depend on
$\lambda$.

  * •

We determine the elements of these two matrices by employing equations (7)
written as

${\rm{L}}(\tilde{\mathbf{f}},\tilde{\mathbf{f}}_{10};\lambda){\rm{B}}={\cal{S}}({\rm{B}}){\rm{L}}(\mathbf{f},\mathbf{f}_{10};\lambda),\quad{\rm{M}}(\tilde{\mathbf{f}},\tilde{\mathbf{f}}_{01};\lambda){\rm{B}}={\cal{T}}({\rm{B}}){\rm{M}}(\mathbf{f},\mathbf{f}_{01};\lambda).$
(11)

In our calculations we also have to take into account that $\det({\rm{B}})$ is
a constant, an obvious consequence of (11) and our assumption that the Lax
matrices have constant determinants.

  * •

The derived Darboux matrix will depend in general on the ‘old’ and the ‘new’
fields $\bf{f}$ and $\tilde{\bf{f}}$, as well as the spectral parameter
$\lambda$, and a parameter $\varepsilon$. It may also depend on some
auxilliary function, a potential, $g(n,m)$. That is,

${\rm{B}}=\lambda{\rm{B}}^{(1)}(\mathbf{f}_{00},\tilde{\mathbf{f}}_{00},g;\varepsilon)+{\rm{B}}^{(0)}(\mathbf{f}_{00},\tilde{\mathbf{f}}_{00},g;\varepsilon).$

  * •

In the construction of the Darboux matrix (10) there will be some algebraic
relations that define the Darboux matrix elements, as well as some difference
equations for its elements. These difference equations will be of the form

$\mathcal{B}^{(n)}(\mathbf{f}_{00},\mathbf{f}_{10},\tilde{\mathbf{f}}_{00},\tilde{\mathbf{f}}_{10},g;\varepsilon)=0,\qquad\mathcal{B}^{(m)}(\mathbf{f}_{00},\mathbf{f}_{01},\tilde{\mathbf{f}}_{00},\tilde{\mathbf{f}}_{01},g;\varepsilon)=0,$
(12)

and constitute the $n$\- and the $m$-part, respectively, of an auto-Bäcklund
transformation that relates the ‘old’ and the ‘new’ fields. In what follows,
we will denote this transformation simply with
${\mathcal{B}}(\mathbf{f},\tilde{\mathbf{f}},g;\varepsilon)=0$.

  * •

The Bianchi commuting diagram, aka superposition principle, for the auto-
Bäcklund transformation (12) follows from the permutation of four Darboux
matrices according to the diagram in Figure 2.

.6 0.01 t:F (0 0) (1.5 1.5) (3 0) (1.5 -1.5) (0 0) (0 0) f:0.0 r:0.08 (1.5
1.5) f:0.0 r:0.08 (3 0) f:0.0 r:0.08 (1.5 -1.5) f:0.0 r:0.08 (.8 .8) (.85 .85)
(2.25 .75) (2.3 .7) (.8 -.8) (.85 -.85) (2.25 -.75) (2.3 -.7) (-0.3 -0.1)
$\bf{f}$ (1.4 1.65) $\tilde{\bf{f}}$ (3.15 -.1)
$\tilde{\hat{\bf{f}}}=\hat{\tilde{\bf{f}}}$ (1.4 -1.85) $\hat{\bf{f}}$ (-0.75
0.9)${\rm{B}}(\mathbf{f},\tilde{\mathbf{f}},g_{1};\varepsilon_{1},\lambda)$
(-0.78
-1.1)${\rm{B}}(\mathbf{f},\hat{\mathbf{f}},g_{2};\varepsilon_{2},\lambda)$
(2.2
0.9)${\rm{B}}(\tilde{\mathbf{f}},\hat{\tilde{\mathbf{f}}},g_{12};\varepsilon_{2},\lambda)$
(2.3
-1.1)${\rm{B}}(\hat{\mathbf{f}},\tilde{\hat{\mathbf{f}}},g_{21};\varepsilon_{1},\lambda)$

Figure 2: Bianchi commuting diagram. It should be noted that $g_{12}\neq
g_{21}$.

More precisely, starting with a solution $\bf{f}$ of (6) we can construct two
new solutions $\tilde{\bf{f}}$ and $\hat{\bf{f}}$ using the Bäcklund
transformations
${\mathcal{B}}(\mathbf{f},\tilde{\mathbf{f}},g_{1};\varepsilon_{1})=0$ and
${\mathcal{B}}(\mathbf{f},\hat{\mathbf{f}},g_{2};\varepsilon_{2})=0$,
respectively. Then, we can use the Bäcklund transformation with initial
solution $\tilde{\bf{f}}$, a new potential $g_{12}$ and parameter
$\varepsilon_{2}$ to derive a new solution $\hat{\tilde{\mathbf{f}}}$, i.e.
${\mathcal{B}}(\tilde{\mathbf{f}},\hat{\tilde{\mathbf{f}}},g_{12};\varepsilon_{2})=0$.
In the same fashion, we can start with $\hat{\bf{f}}$, a new potential
$g_{21}$ and parameter $\varepsilon_{1}$ to derive solution
$\tilde{\hat{\mathbf{f}}}$, i.e.
${\mathcal{B}}(\hat{\mathbf{f}},\tilde{\hat{\mathbf{f}}},g_{21};\varepsilon_{1})=0$.
By requiring $\tilde{\hat{\mathbf{f}}}=\hat{\tilde{\bf{f}}}$, according to
Figure 2, we can construct this solution algebraically and it follows from the
commutativity of the corresponding Darboux matrices,

${\rm{B}}(\tilde{\mathbf{f}},\hat{\tilde{\mathbf{f}}},g_{12};\varepsilon_{2},\lambda){\rm{B}}(\mathbf{f},\tilde{\mathbf{f}},g_{1};\varepsilon_{1},\lambda)={\rm{B}}(\hat{\mathbf{f}},\tilde{\hat{\mathbf{f}}},g_{21};\varepsilon_{1},\lambda){\rm{B}}(\mathbf{f},\hat{\mathbf{f}},g_{2};\varepsilon_{2},\lambda).$
(13)

##  4 The Adler–Yamilov system

From the discussion in the previous section it is already obvious that
multidimensional consistency is not essential for this method of derivation of
Bäcklund transformations. In this section, we demonstrate the application of
our scheme using as an illustrative example the Adler–Yamilov system related
to the nonlinear Schrödinger equation [19].

The Adler–Yamilov system can be written as

$p_{10}-p_{01}-\frac{\alpha-\beta}{1+p_{00}q_{11}}p_{00}=0,\qquad
q_{10}-q_{01}+\frac{\alpha-\beta}{1+p_{00}q_{11}}q_{11}=0,$ (14)

where $\alpha$, $\beta$ are complex parameters. Moreover, using matrix

${\rm{L}}(f,g;a,\lambda)=\lambda{\rm{L}}^{(1)}+{\rm{L}}^{(2)}(f,g;a)=\lambda\begin{pmatrix}1&0\\\
0&0\end{pmatrix}+\begin{pmatrix}a+fg&f\\\ g&1\end{pmatrix},$

a Lax pair for (14) can be written as

$\displaystyle{\cal{S}}(\Psi)={\rm{L}}(p_{00},q_{10};\alpha,\lambda)\Psi=\left(\lambda\begin{pmatrix}1&0\\\
0&0\end{pmatrix}+\begin{pmatrix}\alpha+p_{00}q_{10}&p_{00}\\\
q_{10}&1\end{pmatrix}\right)\Psi,$ (15a)
$\displaystyle{\cal{T}}(\Psi)={\rm{L}}(p_{00},q_{01};\beta,\lambda)\Psi=\left(\lambda\begin{pmatrix}1&0\\\
0&0\end{pmatrix}+\begin{pmatrix}\beta+p_{00}q_{01}&p_{00}\\\
q_{01}&1\end{pmatrix}\right)\Psi.$ (15b)

###  4.1 The discrete Darboux–Lax scheme for the Adler–Yamilov system

We start with our choice (10) for the initial form of the Darboux matrix
$\rm{B}$,

${\rm{B}}=\lambda{\rm{B}}^{(1)}+{\rm{B}}^{(0)}=\lambda\begin{pmatrix}f^{(1)}_{00}&f^{(2)}_{00}\\\
f^{(3)}_{00}&f^{(4)}_{00}\end{pmatrix}+\begin{pmatrix}g^{(1)}_{00}&g^{(2)}_{00}\\\
g^{(3)}_{00}&g^{(4)}_{00}\end{pmatrix},$ (16)

and the determining equations (11), which now become

$\displaystyle\left(\lambda{\rm{L}}^{(1)}+{\rm{L}}^{(2)}(\tilde{p}_{00},\tilde{q}_{10};\alpha)\right)\left(\lambda{\rm{B}}^{(1)}+{\rm{B}}^{(0)}\right)=\left(\lambda{\cal{S}}\left({\rm{B}}^{(1)}\right)+{\cal{S}}\left({\rm{B}}^{(0)}\right)\right)\left(\lambda{\rm{L}}^{(1)}+{\rm{L}}^{(2)}(p_{00},q_{10};\alpha)\right),$
(17a)
$\displaystyle\left(\lambda{\rm{L}}^{(1)}+{\rm{L}}^{(2)}(\tilde{p}_{00},\tilde{q}_{01};\beta)\right)\left(\lambda{\rm{B}}^{(1)}+{\rm{B}}^{(0)}\right)=\left(\lambda{\cal{T}}\left({\rm{B}}^{(1)}\right)+{\cal{T}}\left({\rm{B}}^{(0)}\right)\right)\left(\lambda{\rm{L}}^{(1)}+{\rm{L}}^{(2)}(p_{00},q_{01};\beta)\right).$
(17b)

Since all the matrices involved in (17) are independent of $\lambda$, we
collect the coefficients of the different powers of the spectral parameter.
The $\lambda^{2}$ terms yield equations

${\rm{L}}^{(1)}{\rm{B}}^{(1)}={\cal{S}}\left({\rm{B}}^{(1)}\right){\rm{L}}^{(1)},\quad{\rm{L}}^{(1)}{\rm{B}}^{(1)}={\cal{T}}\left({\rm{B}}^{(1)}\right){\rm{L}}^{(1)},$

which lead to

$f^{(1)}_{00}=c_{1}\in{\mathbb{R}},\quad f^{(2)}_{00}=f^{(3)}_{00}=0.$ (18)

The $\lambda$ terms in relations (17) are

${\rm{L}}^{(1)}{\rm{B}}^{(0)}+{\rm{L}}^{(2)}(\tilde{p}_{00},\tilde{q}_{10};\alpha){\rm{B}}^{(1)}={\cal{S}}\left({\rm{B}}^{(1)}\right){\rm{L}}^{(2)}(p_{00},q_{10};\alpha)+{\cal{S}}\left({\rm{B}}^{(0)}\right){\rm{L}}^{(1)},$
${\rm{L}}^{(1)}{\rm{B}}^{(0)}+{\rm{L}}^{(2)}(\tilde{p}_{00},\tilde{q}_{01};\beta){\rm{B}}^{(1)}={\cal{T}}\left({\rm{B}}^{(1)}\right){\rm{L}}^{(2)}(p_{00},q_{01};\beta)+{\cal{T}}\left({\rm{B}}^{(0)}\right){\rm{L}}^{(1)},$

which in view of (18) imply

$f^{(4)}_{00}=c_{2}\in{\mathbb{R}},\quad
g^{(2)}_{00}=c_{1}p_{00}-c_{2}\tilde{p}_{00},\quad
g^{(3)}_{00}=c_{1}\tilde{q}_{00}-c_{2}q_{00},$ (19)
$\left({\cal{S}}-1\right)\left(g^{(1)}_{00}\right)=c_{1}\left(\tilde{p}_{00}\tilde{q}_{10}-p_{00}q_{10}\right),\quad\left({\cal{T}}-1\right)\left(g^{(1)}_{00}\right)=c_{1}\left(\tilde{p}_{00}\tilde{q}_{01}-p_{00}q_{01}\right).$
(20)

The $\lambda$ independent terms,

${\rm{L}}^{(2)}(\tilde{p}_{00},\tilde{q}_{10};\alpha){\rm{B}}^{(0)}={\cal{S}}\left({\rm{B}}^{(0)}\right){\rm{L}}^{(2)}(p_{00},q_{10};\alpha),\quad{\rm{L}}^{(2)}(\tilde{p}_{00},\tilde{q}_{01};\beta){\rm{B}}^{(0)}={\cal{T}}\left({\rm{B}}^{(0)}\right){\rm{L}}^{(2)}(p_{00},q_{01};\beta),$
(21)

determine $g^{(4)}_{00}$ and provide us with the corresponding auto-Bäcklund
transformation. Specifically, the $(2,2)$-elements of the above relations
yield

$\left({\cal{S}}-1\right)\left(g^{(4)}_{00}\right)=c_{2}\left(p_{00}q_{10}-\tilde{p}_{00}\tilde{q}_{10}\right),\quad\left({\cal{T}}-1\right)\left(g^{(4)}_{00}\right)=c_{2}\left(p_{00}q_{01}-\tilde{p}_{00}\tilde{q}_{01}\right).$
(22)

The remaining entries of (21) in view of (20) and (22) become

$\displaystyle
c_{1}\left(p_{10}+p_{00}(\alpha+p_{00}q_{10})\right)-c_{2}\left(\tilde{p}_{10}+\tilde{p}_{00}(\alpha+\tilde{p}_{00}\tilde{q}_{10})\right)=g^{(4)}_{00}\tilde{p}_{00}-g^{(1)}_{00}p_{00},$
(23a) $\displaystyle
c_{1}\left(p_{01}+p_{00}(\beta+p_{00}q_{01})\right)-c_{2}\left(\tilde{p}_{01}+\tilde{p}_{00}(\beta+\tilde{p}_{00}\tilde{q}_{01})\right)=g^{(4)}_{00}\tilde{p}_{00}-g^{(1)}_{00}p_{00},$
(23b)
$\displaystyle\tilde{q}_{10}=\frac{c_{1}\tilde{q}_{00}-c_{2}(q_{00}-\alpha
q_{10})-g^{(4)}_{00}q_{10}}{c_{1}(\alpha+p_{00}q_{10})-c_{2}\tilde{p}_{00}q_{10}-g^{(1)}_{00}},\quad\tilde{q}_{01}=\frac{c_{1}\tilde{q}_{00}-c_{2}(q_{00}-\beta
q_{01})-g^{(4)}_{00}q_{01}}{c_{1}(\beta+p_{00}q_{01})-c_{2}\tilde{p}_{00}q_{01}-g^{(1)}_{00}},$
(23c)

which play the role of the Bäcklund transformation.

Finally we require the determinant of the Darboux matrix $\rm{B}$, which in
view of (18) and (19) can be written as
$\det\left({\rm{B}}\right)=c_{1}c_{2}\lambda^{2}+\left(c_{2}g^{(1)}_{00}+c_{1}g^{(4)}_{00}\right)\lambda+g^{(1)}_{00}g^{(4)}_{00}-\left(c_{1}p_{00}-c_{2}\tilde{p}_{00}\right)\left(c_{1}\tilde{q}_{00}-c_{2}q_{00}\right)$,
to be constant. This requirement implies the relations

$c_{2}g^{(1)}_{00}+c_{1}g^{(4)}_{00}=\kappa,\quad
g^{(1)}_{00}g^{(4)}_{00}-\left(c_{1}p_{00}-c_{2}\tilde{p}_{00}\right)\left(c_{1}\tilde{q}_{00}-c_{2}q_{00}\right)=\varepsilon,\quad\kappa,\varepsilon\in{\mathbb{R}}.$
(24)

It should be noted that the first relation in (24) may also be viewed as a
consequence of (20) and (22).

Summarizing, so far we have shown that the Darboux matrix $\rm{B}$ has the
form

${\rm{B}}=\lambda{\rm{B}}^{(1)}+{\rm{B}}^{(0)}=\lambda\begin{pmatrix}c_{1}&0\\\
0&c_{2}\end{pmatrix}+\begin{pmatrix}g^{(1)}_{00}&c_{1}p_{00}-c_{2}\tilde{p}_{00}\\\
c_{1}\tilde{q}_{00}-c_{2}q_{00}&g^{(4)}_{00}\end{pmatrix},$ (25)

where potentials $g^{(1)}$ and $g^{(4)}$ are determined by (20), (22) and
(24), and the Bäcklund transformation is given by (23).

We consider now two cases: (i) $c_{1}=0$ and $c_{2}\neq 0$, and (ii)
$c_{1}\neq 0$ and $c_{2}=0$.

#### First case: $c_{1}=0$ and $c_{2}\neq 0$

If $c_{1}=0$ and $c_{2}\neq 0$, then we can choose $c_{2}=1$ without loss of
generality. Then equations (20) imply that $g^{(1)}_{00}$ is a constant and we
choose $g^{(1)}_{00}=1$.222It means we choose $\kappa=1$ in the first relation
of (24). Moreover, the second relation in (24) implies

$g^{(4)}_{00}=\tilde{p}_{00}q_{00}+\varepsilon,\quad\varepsilon\in{\mathbb{R}}.$
(26)

With these choices, the Darboux matrix becomes

${\rm{B}}(q_{00},\tilde{p}_{00};\varepsilon)=\lambda\begin{pmatrix}0&0\\\
0&1\end{pmatrix}+\begin{pmatrix}1&-\tilde{p}_{00}\\\
-q_{00}&\varepsilon+\tilde{p}_{00}q_{00}\end{pmatrix},$ (27)

and relations (23) become

$\displaystyle\tilde{p}_{10}=p_{00}+\frac{\alpha-\varepsilon}{1+\tilde{p}_{00}q_{10}}\tilde{p}_{00},\quad\tilde{q}_{10}=q_{00}-\frac{\alpha-\varepsilon}{1+\tilde{p}_{00}q_{10}}q_{10},$
(28a)
$\displaystyle\tilde{p}_{01}=p_{00}+\frac{\beta-\varepsilon}{1+\tilde{p}_{00}q_{01}}\tilde{p}_{00},\quad\tilde{q}_{01}=q_{00}-\frac{\beta-\varepsilon}{1+\tilde{p}_{00}q_{01}}q_{01}.$
(28b)

In view of the above choices and system (28), relations (22) hold identically.

System (28) is an auto-Bäcklund transformation for the Adler–Yamilov system
(14). Indeed, if we shift equations (28a) in the $m$ direction, and equations
(28b) in the $n$ direction, respectively, then it can be readily verified that
the two expressions for $\tilde{p}_{11}$ and the two expressions for
$\tilde{q}_{11}$ coincide modulo the Adler–Yamilov system (14). Conversely, we
rearrange the above system for $p_{00}$, $q_{10}$ and $q_{01}$,

$\displaystyle
q_{10}=\frac{q_{00}-\tilde{q}_{10}}{\alpha-\varepsilon-\tilde{p}_{00}(q_{00}-\tilde{q}_{10})},\quad
p_{00}=\tilde{p}_{10}-\tilde{p}_{00}\left(\alpha-\varepsilon-\tilde{p}_{00}(q_{00}-\tilde{q}_{10})\right),$
(29a) $\displaystyle
q_{01}=\frac{q_{00}-\tilde{q}_{01}}{\beta-\varepsilon-\tilde{p}_{00}(q_{00}-\tilde{q}_{01})},\quad
p_{00}=\tilde{p}_{01}-\tilde{p}_{00}\left(\beta-\varepsilon-\tilde{p}_{00}(q_{00}-\tilde{q}_{01})\right).$
(29b)

If we shift the first equation in (29a) in the $m$ direction and the first
equation in (29b) in the $n$ direction, then the resulting expressions for
$q_{11}$ coincide provided that $\tilde{p}$ and $\tilde{q}$ satisfy system
(14). Moreover, subtracting the two expressions for $p_{00}$ in (29) we end up
with

$\tilde{p}_{10}-\tilde{p}_{01}-\tilde{p}_{00}\left(\tilde{p}_{00}(\tilde{q}_{10}-\tilde{q}_{01})+\alpha-\beta\right)=0,$

which holds on solutions of (14).

Finally, according to Figure 2 and relation (13), the superposition principle
for the auto-Bäcklund transformation (28) follows from

${\rm{B}}(\tilde{q}_{00},\hat{\tilde{p}}_{00};\varepsilon_{2}){\rm{B}}(q_{00},\tilde{p}_{00};\varepsilon_{1})={\rm{B}}(\hat{q}_{00},\tilde{\hat{p}}_{00};\varepsilon_{1}){\rm{B}}(q_{00},\hat{p}_{00};\varepsilon_{2}),$

and can be written as

$\hat{\tilde{p}}_{00}=-\,\frac{\tilde{p}_{00}-\hat{p}_{00}}{\varepsilon_{1}-\varepsilon_{2}+(\tilde{p}_{00}-\hat{p}_{00})q_{00}},\quad\tilde{q}_{00}-\hat{q}_{00}=\left(\varepsilon_{1}-\varepsilon_{2}+(\tilde{p}_{00}-\hat{p}_{00})q_{00}\right)q_{00}.$
(30)

#### Second case: $c_{1}\neq 0$ and $c_{2}=0$

If $c_{2}=0$ and $c_{1}\neq 0$, we choose $c_{1}=1$, relations (22) imply that
$g^{(4)}_{00}=1$, and the determinant of $\rm{B}$ implies that
$g^{(1)}_{00}=p_{00}\tilde{q}_{00}+\varepsilon$. In view of these choices, we
arrive at a Darboux matrix which can be written in terms of matrix (27) as

${\rm{C}}(p_{00},\tilde{q}_{00};\varepsilon)=(\lambda+\varepsilon)\left({\rm{B}}(\tilde{q}_{00},p_{00};\varepsilon)\right)^{-1},$
(31)

whereas relations (23) yield actually system (29) with the roles of new and
old fields interchanged, i.e. system (29) accompanied by the interchange
$(p,q)\leftrightarrow(\tilde{p},\tilde{q})$. Thus in this case we end up with
the inverse of the Darboux and Bäcklund transformations we derived previously.

###  4.2 Derivation of soliton solutions

We employ the auto-Bäcklund transformation (28) and its superposition
principle (30) in the derivation of soliton solutions of the Adler–Yamilov
system (14).

Figure 3: The one soliton solution of the Adler–Yamilov system and the
potential $1/g_{00}$. In both cases $\alpha=8$, $\beta=4$, $\varepsilon=1$ and
$c=-2$.

More precisely, we start with the solution333This solution can be constructed
starting with the zero solution $p_{00}=q_{00}=0$ and using the second
transformation we discussed in subsection 4.1 with $\varepsilon=0$.

$p_{00}=0,\quad q_{00}=\alpha^{-n}\beta^{-m}.$ (32)

With this seed solution, the first equation in (28a) and the first one in
(28b) become

$\tilde{p}_{10}=\frac{\alpha-\varepsilon}{1+\tilde{p}_{00}\alpha^{-n-1}\beta^{-m}}\tilde{p}_{00},\quad\tilde{p}_{01}=\frac{\beta-\varepsilon}{1+\tilde{p}_{00}\alpha^{-n}\beta^{-m-1}}\tilde{p}_{00}.$
(33)

We can linearise these Ricatti equations by setting
$\tilde{p}_{00}=\alpha^{n}\beta^{m}/g_{00}$,

$(\alpha-\varepsilon)g_{10}=\alpha
g_{00}+1,\quad(\beta-\varepsilon)g_{01}=\beta g_{00}+1.$

The general solution of this linear system is

$g_{00}=\frac{\alpha^{n}}{(\alpha-\varepsilon)^{n}}\frac{\beta^{m}}{(\beta-\varepsilon)^{m}}c-\frac{1}{\varepsilon},$
(34)

where $c\in{\mathbb{R}}$ is the arbitrary constant of integration, and thus

$\tilde{p}_{00}=\frac{\varepsilon\,\alpha^{n}\beta^{m}(\alpha-\varepsilon)^{n}(\beta-\varepsilon)^{m}}{c\,\varepsilon\,\alpha^{n}\beta^{m}-(\alpha-\varepsilon)^{n}(\beta-\varepsilon)^{m}}.$
(35a) Using the seed solution (32) and the updated potential (35a), we can use
either the equation for $\tilde{q}_{10}$ in (28a) or the equation for
$\tilde{q}_{01}$ in (28b) to determine $\tilde{q}_{00}$. Both ways lead to
$\tilde{q}_{00}=\frac{c\,\varepsilon^{2}}{c\,\varepsilon\,\alpha^{n}\beta^{m}-(\alpha-\varepsilon)^{n}(\beta-\varepsilon)^{m}}.$
(35b)

This two-parameter family of solutions yields the one-soliton solution of
(14): even though both functions in (35) diverge, their product represents a
soliton. This interpretation is motivated by the relation of the Adler–Yamilov
system to the nonlinear Schrödinger equation [19], and it is evident from the
plot of the product $|\tilde{p}_{00}\tilde{q}_{00}|$. We also plot the
potential $1/g_{00}$ which is a kink. See Figure 3.

Figure 4: The two-soliton solution of the Adler–Yamilov system: solution (37)
with $\alpha=8$, $\beta=4$, $\varepsilon_{1}=1$, $c_{1}=-2$,
$\varepsilon_{2}=3$ and $c_{2}=8$. It should be noted that this solution
requires the combination of a non-singular solution, i.e. the pair
$(\tilde{p},\tilde{q})$ which corresponds to the one-soliton solution (35),
and a singular one which is $(\hat{p},\hat{q})$.

Having constructed the two-parameter family of solutions (35), we may use it
along with the superposition principle (30) to determine a third solution and
in particular the two-soliton solution of system (14). Starting with the same
seed solution, the two solutions $(\tilde{p}_{00},\tilde{q}_{00})$ and
$(\hat{p}_{00},\hat{q}_{00})$ involved in (30) follow from (35) by replacing
parameters $(\varepsilon,c)$ with $(\varepsilon_{1},c_{1})$ and
$(\varepsilon_{2},c_{2})$, respectively. In order to make the presentation
more comprehensible, let us introduce the shorthand notation

$\delta_{0}:=\alpha^{n}\beta^{m},\quad\delta_{1}:=(\alpha-\varepsilon_{1})^{n}(\beta-\varepsilon_{1})^{m},\quad\delta_{2}:=(\alpha-\varepsilon_{2})^{n}(\beta-\varepsilon_{2})^{m}.$

In terms of this notation, the seed solution is $p_{00}=0$,
$q_{00}=1/\delta_{0}$, and the two solutions we described can be written as

$\tilde{p}_{00}=\frac{\varepsilon_{1}\,\delta_{0}\delta_{1}}{c_{1}\,\varepsilon_{1}\,\delta_{0}-\delta_{1}},\leavevmode\nobreak\
\leavevmode\nobreak\
\tilde{q}_{00}=\frac{c_{1}\,\varepsilon_{1}^{2}}{c_{1}\,\varepsilon_{1}\,\delta_{0}-\delta_{1}},\quad\mbox{and}\quad\hat{p}_{00}=\frac{\varepsilon_{2}\,\delta_{0}\delta_{2}}{c_{2}\,\varepsilon_{2}\,\delta_{0}-\delta_{2}},\leavevmode\nobreak\
\leavevmode\nobreak\
\hat{q}_{00}=\frac{c_{2}\,\varepsilon_{2}^{2}}{c_{2}\,\varepsilon_{2}\,\delta_{0}-\delta_{2}},$
(36)

respectively. With these formulae at our disposal, the first relation in (30)
yields

$\hat{\tilde{p}}_{00}=\frac{\varepsilon_{1}\varepsilon_{2}\delta_{0}\left(c_{1}\delta_{2}-c_{2}\delta_{1}\right)+(\varepsilon_{1}-\varepsilon_{2})\delta_{1}\delta_{2}}{c_{1}c_{2}\varepsilon_{1}\varepsilon_{2}(\varepsilon_{1}-\varepsilon_{2})\delta_{0}-c_{1}\varepsilon_{1}^{2}\delta_{2}+c_{2}\varepsilon_{2}^{2}\delta_{1}}.$
(37a) To find $\hat{\tilde{q}}_{00}$ we work in the same way we derived (35b)
and according to the Bianchi diagram. More precisely, we can use the second
equation either in (28a) or in (28b) with $\tilde{q}$ replaced by
$\hat{\tilde{q}}$, $(p,q)$ replaced by $(\tilde{p},\tilde{q})$ given in (36),
and parameter $\varepsilon$ replaced by $\varepsilon_{2}$ (alternatively, we
can replace $(p,q)$ with $(\hat{p},\hat{q})$ given in (36), and parameter
$\varepsilon$ with $\varepsilon_{1}$), to find
$\hat{\tilde{q}}_{00}=\frac{c_{1}c_{2}\varepsilon_{1}^{2}\varepsilon_{2}^{2}(\varepsilon_{1}-\varepsilon_{2})}{c_{1}c_{2}\varepsilon_{1}\varepsilon_{2}(\varepsilon_{1}-\varepsilon_{2})\delta_{0}-c_{1}\varepsilon_{1}^{2}\delta_{2}+c_{2}\varepsilon_{2}^{2}\delta_{1}}.$
(37b)

This four-parameter family of solutions yields the two-soliton solution of
(14) in the same way we interpreted (35) as the one-soliton solution of the
Adler–Yamilov system. See the plots of the product
$|\hat{\tilde{p}}_{00}\hat{\tilde{q}}_{00}|$ in Figure 4.

##  5 Conclusions

In this paper we proposed a new method for deriving Bäcklund transformations
and constructing solutions for nonlinear integrable P$\Delta$Es which admit
Lax representation but do not necessarily possess the 3D consistency property.
Specifically, in our approach we consider Darboux transformations which leave
the given Lax pair covariant, and by construction lead to Bäcklund
transformations for the corresponding discrete system. The permutability of
four Darboux matrices according to the Bianchi diagram in Figure 2 leads to
the nonlinear superposition principle of the related Bäcklund transformation.
Moreover, the latter transformation and its superposition principle can be
used in the construction of interesting solutions to P$\Delta$Es starting from
some simple ones. As an illustrative example we used the Adler–Yamilov system
(14). For this system we constructed Darboux and corresponding Bäcklund
transformations. With the use of transformation (28) and its superposition
principle (30) we constructed the one- and two-soliton solutions starting with
the seed solution $p_{00}=0,q_{00}=\alpha^{-n}\beta^{-m}$.

In the illustrative example we considered in Section 4, the Lax representation
(6) involves matrices $\rm{L}$ and $\rm{M}$ which have the same form, see
(15). The natural question arises as to whether our method can be employed to
the case of integrable P$\Delta$Es with Lax representation (6) where matrices
${\rm{L}}$ and $\rm{M}$ do not have the same form. The answer to this question
is positive, the corresponding transformations may involve auxiliary functions
(potentials), and this derivation is similar to the generic construction we
presented in subsection 4.1, see Darboux matrix (25) and relations (20), (22),
(23)and (24).

Moreover our considerations can be extended to the generalized symmetries of
the discrete system. Generalized symmetries are (integrable) differential-
difference equations involving shifts in one lattice direction and are
compatible with the P$\Delta$E. Their Lax pair is semi-discrete and its
discrete part coincides with the one of the two equations of the fully
discrete Lax pair (3), see for instance [12]. This relation allows us to
extend the Darboux and Bäcklund transformations for the P$\Delta$E to
corresponding ones for the differential-difference equations and employ the
Bäcklund transformation and its superposition principle in the construction of
solutions for the symmetries. We will demonstrate this method and its
extensions in our future work in details using the Hirota KdV equation as an
illustrative example, as well as systems appeared in [4, 10, 22].

In fact our results can be used and extended in various ways.

  1. 1.

Apply our method to construct solutions to all the NLS type equations derived
in [19].

In [19] we classified Darboux transformations related to NLS type equations
and constructed integrable discretisations of the latter, namely integrable
systems of nonlinear P$\Delta$Es. By employing the discrete Darboux–Lax scheme
we proposed in Section 3, one could derive Bäcklund transformations and
construct soliton solutions to these nonlinear P$\Delta$Es.

  2. 2.

Study the solutions of the associated PDEs.

The Adler–Yamilov system (14) constitutes a discretisation of the NLS equation
via its Darboux transformation [19]. In this paper, we constructed soliton
solutions to this system, so one could consider the continuum limits of these
solutions to construct solutions to the NLS equation. This procedure could be
applied to other NLS type equations which appeared in [19].

  3. 3.

Study the corresponding Yang–Baxter maps.

In [18, 20] matrix refactorisation problems of Darboux matrices for integrable
PDEs were considered in order to derive solutions to the Yang–Baxter equation
and the entwining Yang–Baxter equation. Since the generator of Yang–Baxter
maps is a matrix refactorisation problem (13) it makes sense to understand how
Bäcklund transformations for P$\Delta$Es are related to Yang–Baxter maps. In
our future work, we plan to show that Yang–Baxter and entwining Yang–Baxter
maps are superpositions of Bäcklund transformations of P$\Delta$Es.

  4. 4.

Extend the results to the case of discrete systems on a 3D lattice.

One can extend the results employed in this paper to the case of 3D lattice
integrable systems. It is expected that the superposition of Bäcklund
transformations related to these systems are solutions to the tetrahedron
equation.

  5. 5.

Extend the results to the case of Grassmann algebras.

Grassmann extensions of Darboux transformations were employed in the
construction of noncommutative versions of discrete systems, see for instance
[14, 30] . However it was realised in [17] that quad-graph systems may lose
their 3D consistency property in the Grassmann extension. The method we
presented here could be generalised and employed in the construction of
Bäcklund transformations and the derivation of solutions to Grassmann extended
quad-graph systems which appeared in the literature.

##  6 Acknowledgements

Xenia Fisenko’s work was supported by the Ministry of Research and Higher
Education (Regional Mathematical Centre “Centre of Integrable Systems,”
Agreement No. 075-02-2021-1397). Sotiris Konstantinou-Rizos’s work was funded
by the Russian Science Foundation (grant No. 20-71-10110).

## References

  * [1] V. Adler, A. Bobenko, and Y. Suris. 2005 Geometry of Yang-Baxter maps: pencils of conics and quadrirational mappings Comm. Anal. Geom. 12 967–1007.
  * [2] J. Atkinson, J. Hietarinta and F. Nijhoff. 2007 Seed and soliton solutions for Adler’s lattice equation J. Phys. A: Math. Theor. 40 F1–F8.
  * [3] J. Atkinson and M. Nieszporski. 2014 Multi-Quadratic Quad Equations: Integrable Cases from a Factorized-Discriminant Hypothesis Int. Math. Res. Not. 2014 4215–4240.
  * [4] G. Berkeley, A.V. Mikhailov, and P. Xenitidis. 2016 Darboux transformations with tetrahedral reduction group and related integrable systems J. Math. Phys. 57, 092701.
  * [5] A. Bobenko and Y. Suris. 2002 Integrable systems on quad-graphs Int. Math. Res. Notices 11 573–611.
  * [6] A. Bobenko and Y. Suris. 2008 _Discrete Differential Geometry. Integrable Structure._ Graduate Studies in Mathematics 98 American Mathematical Society.
  * [7] R. Boll. 2011 Classification of 3D Consistent Quad-Equations J. Nonlinear Math. Phys. 18 337–365
  * [8] T. Bridgman, W. Hereman, G.R.W. Quispel and P. van der Kamp. 2013 Symbolic Computation of Lax Pairs of Partial Difference Equations using Consistency Around the Cube Found. Comput. Math. 13517–544.
  * [9] V. Caudrelier, N. Crampé, C. Zhang. 2014 Integrable Boundary for Quad-Graph Systems: Three-Dimensional Boundary Consistency SIGMA 014 (24 pp).
  * [10] A. Fordy and P. Xenitidis. 2017 $\mathbb{Z}_{N}$ graded discrete Lax pairs and integrable difference equations. J. Phys. A: Math. Theor. 50 165205\.
  * [11] A. Fordy and P. Xenitidis. 2017 $\mathbb{Z}_{N}$ graded discrete Lax pairs and Yang–Baxter maps. Proc. R. Soc. A. 473 20160946\.
  * [12] A. Fordy and P. Xenitidis. 2020 Symmetries of ${\mathbb{Z}}_{N}$ graded discrete integrable systems J Phys A: Math Theor 53 235201 (30pp).
  * [13] W. Fu. 2020 Direct linearization approach to discrete integrable systems associated with $Z_{N}$ graded Lax pairs. Proc. R. Soc. A. 476.
  * [14] G.G. Grahovski, A.V. Mikhailov. 2013 Integrable discretisations for a class of nonlinear Scrödinger equations on Grassmann algebras, Phys. Lett. A 377 3254–3259.
  * [15] J. Hietarinta, N. Joshi, F. Nijhoff. 2016 _Discrete Systems and Integrability_ Cambridge texts in applied mathematics, Cambridge University Press.
  * [16] P. Kassotakis, M. Nieszporski, V. Papageorgiou, A. Tongas 2019 Tetrahedron maps and symmetries of three dimensional integrable discrete equations, J. Math. Phys. 60 123503\.
  * [17] S. Konstantinou-Rizos. 2020 On the 3D consistency of a Grassmann extended lattice Boussinesq system, J. Nuc. Phys. B 951 114878\.
  * [18] S. Konstantinou-Rizos and A.V. Mikhailov. 2013 Darboux transformations, finite reduction groups and related Yang–Baxter maps. J. Phys. A: Math. Theor. 46 425201\.
  * [19] S. Konstantinou-Rizos, A.V. Mikhailov and P. Xenitidis. 2015 Reduction groups and related integrable difference systems of nonlinear Schrödinger type J. Math. Phys. 56 082701\.
  * [20] S. Konstantinou-Rizos, G. Papamikos. 2019 Entwining Yang–Baxter maps related to NLS type equations, J. Phys. A: Math. Theor. 52 485201\.
  * [21] S.B. Lobb, F.W. Nijhoff. 2009 Lagrangian multiforms and multidimensional consistency, J. Phys. A: Math. Theor. 42 454013\.
  * [22] A.V. Mikhailov and P. Xenitidis. 2014 Second Order Integrability Conditions for Difference Equations: An Integrable Equation. Lett. Math. Phys. 104 431–450.
  * [23] F. Nijhoff. 2002 Lax pair for the Adler (lattice Krichever-Novikov) system Phys. Lett. A 297 49–58.
  * [24] F. Nijhoff, J. Atkinson and J. Hietarinta. 2010 A Constructive Approach to the Soliton Solutions of Integrable Quadrilateral Lattice Equations Commun. Math. Phys. 297 283–304.
  * [25] V. Papageorgiou, A. Tongas. 2007 Yang–Baxter maps and multi-field integrable lattice equations J. Phys. A: Math. Theor. 40 12677\.
  * [26] Y. Shi 2020 $Z_{N}$ graded discrete integrable systems and Darboux transformations. J. Phys. A: Math. Theor. 53 044003\.
  * [27] P. Xenitidis. 2018 Determining the symmetries of difference equations. Proc. R. Soc. A. 474 20180340\.
  * [28] P. Xenitidis. 2019 On consistent systems of difference equations. J. Phys. A: Math. Theor. 52 455201.
  * [29] P. Xenitidis, F. Nijhoff and S. Lobb. 2011 On the Lagrangian formulation of multidimensionally consistent systems. Proc. R. Soc. A. 467 3295–3317.
  * [30] L.L. Xue, D. Levi and Q.P. Liu. 2013 Supersymmetric KdV equation: Darboux transformation and discrete systems J. Phys. A: Math. Theor. (FTC) 46 502001\.


#  comp-syn: Perceptually Grounded Word Embeddings with Color

Bhargav Srinivasa Desikan
University of Chicago
Knowledge Lab
<EMAIL_ADDRESS>
Tasker Hull
Psiphon Inc, Toronto
<EMAIL_ADDRESS>
Ethan O. Nadler
Stanford University
KIPAC & Department of Physics
<EMAIL_ADDRESS>
Douglas Guilbeault
University of California, Berkeley
Haas Business School
<EMAIL_ADDRESS>
Aabir Abubaker Kar
University of Chicago
Knowledge Lab
<EMAIL_ADDRESS>
Mark Chu
Columbia University
<EMAIL_ADDRESS>
Donald Ruggiero Lo Sardo
Sony CSL Paris
<EMAIL_ADDRESS>

###### Abstract

Popular approaches to natural language processing create word embeddings based
on textual co-occurrence patterns, but often ignore embodied, sensory aspects
of language. Here, we introduce the Python package comp-syn, which provides
grounded word embeddings based on the perceptually uniform color distributions
of Google Image search results. We demonstrate that comp-syn significantly
enriches models of distributional semantics. In particular, we show that (1)
comp-syn predicts human judgments of word concreteness with greater accuracy
and in a more interpretable fashion than word2vec using low-dimensional
word–color embeddings, and (2) comp-syn performs comparably to word2vec on a
metaphorical vs. literal word-pair classification task. comp-syn is open-
source on PyPi and is compatible with mainstream machine-learning Python
packages. Our package release includes word–color embeddings for over 40,000
English words, each associated with crowd-sourced word concreteness judgments.

##  1 Introduction

The embodied cognition paradigm seeks to ground semantic processing in bodily,
affective, and social experiences. This paradigm explains how sensory
information contributes to semantic processing, either through metaphors
involving references to sensory experience [Lakoff and Turner, 1989, Gallese
and Lakoff, 2005] or through the simulation of sensory experience in mental
imagery [Bergen, 2012]. For example, color is pervasive in linguistic
metaphors (e.g., “her bank accounts are in the _red_ ”), and primes a range of
affective and interpretative responses [Mehta and Zhu, 2009, Elliot and Maier,
2014].

Extant methods in computational linguistics are limited in their ability to
advance the embodied cognition paradigm due to their focus on text, which
often precludes multi-modal analyses of images and other forms of sensory
data—including color—involved in human meaning-making activities.
Distributional semantics is a particularly prominent approach, wherein textual
co-occurrence patterns are used to embed words in a high-dimensional space;
the resulting “distance” between word embeddings correlates with semantic
similarity [Landauer and Dumais, 1997]. Although leveraging neural networks
[Mikolov et al., 2013] and syntactic information [Levy and Goldberg, 2014] has
led to recent progress, popular models like word2vec lack firm grounding in
their use of sensory information. Moreover, high-dimensional word embeddings
created by neural networks are difficult to interpret [Şenel et al., 2018] and
require long training periods [Ji et al., 2019]. Thus, it remains difficult to
reconcile models of distributional semantics with theories of embodied
semantics.

To address these limitations, _multi-modal_ approaches to distributional
semantics combine text and image data. However, these models continue to infer
semantic associations using high-dimensional word-plus-image embeddings; their
interpretability therefore remains an issue [Bruni et al., 2014, Socher et
al., 2014, Lu et al., 2019]. With respect to color, multi-modal models operate
in standard colorspaces like RGB that are not perceptually uniform
[International Commission On Illumination, 1978] and embed color in a manner
that combines it with complex, multidimensional spatial information.

Here, we introduce a novel word embedding method based on color that is
explicitly interpretable with respect to theories of embodied cognition. We
build on work which shows that color distributions in online images reflect
both affective and semantic similarities among words in abstract domains
(e.g., in the domain of academic disciplines), while also characterizing human
judgments of concept concreteness [Brysbaert et al., 2014, Guilbeault et al.,
2020]. We present the Python package comp-syn111Short for “Computational
Synaesthesia.”, which allows users to explore word–color embeddings based on
the perceptually uniform color distributions of Google Image search results.
We provide embeddings for a set of 40,000 common English words, and we
benchmark the performance of our model using crowd-sourced human concreteness
ratings [Brysbaert et al., 2014]. We show that comp-syn complements the
performance of text-based distributional semantics models by providing an
interpretable embedding that both (1) predicts human judgments of concept
concreteness, and (2) distinguishes metaphorical and literal word pairs.

##  2 Python Package: comp-syn

comp-syn is an open-source Python package available on GitHub and downloadable
through PyPi. The code follows Python best practices and uses industry
standard packages for scientific computing, facilitating easy integration with
Python code bases; we provide complete details in the Supplementary Material.
comp-syn creates word–color embeddings by computing the perceptually uniform
$J_{z}A_{z}B_{z}$ [Safdar et al., 2017] color distributions of their
corresponding top $100$ Google Image search results. We represent these
distributions by their mean and (optionally) standard deviation in $8$ evenly-
segmented $J_{z}A_{z}B_{z}$ bins, yielding 8 to 16-dimensional word–color
embeddings. The details of our code, image searches and methods for generating
word–color embeddings are described in the Appendices.

We use Google rather than a curated image database such as ImageNet [Deng et
al., 2009] because popular datasets are heavily biased toward concrete
objects, which limits their applicability in abstract semantic domains.
Moreover, Google Image search results reflect content that users interact with
most frequently [Jing and Baluja, 2008], underscoring their relevance for
connecting distributional properties of words and images to human semantic
processing. To ensure that our approach is entirely unsupervised, we do not
select particular features of images when measuring their color distributions.
This approach avoids importing pre-determined semantic notions into our
analysis and connects our method to cognitive theories that attribute
aesthetic relevance to recognizable features in both the background and
foreground of images [Riley, 1995, Elliot and Maier, 2014, Guilbeault et al.,
2020].

Model | Embedding based on | Dimension | Concreteness prediction | Metaphor task
---|---|---|---|---
comp-syn |  Perceptually uniform color distributions |  $8$–$16$ |  Linear: $R^{2}=0.96$ Nonlinear: $\ln\mathcal{L}=86$ |  $92\%$ test set accuracy
word2vec | Textual co-occurrence | $\sim 300$ |  Linear: $R^{2}=0.17$ Nonlinear: $\ln\mathcal{L}=76$ |  $95\%$ test set accuracy
Table 1:  Comparison of comp-syn and word2vec and summary of our main results.

##  3 Results

Table 1 summarizes our main results, which we now describe in turn.

Figure 1: The semantic coherence of comp-syn. (A) Word pair color similarity
in comp-syn, measured using the Jensen-Shannon divergence between their
perceptually uniform color distributions, correlates with word2vec cosine
similarity ($N>10^{6}$ pairs). This holds for both concrete (blue) and
abstract (magenta) word pairs, rated according to crowd-sourced human
judgments. Data represent average color similarity in $40$ equally-sized bins
of word2vec similarity. (B) Word pair similarity vs. human concreteness
judgments ($N>10^{7}$ pairs). comp-syn similarity monotonically decreases with
word pair concreteness, while word2vec similarity is a nonlinear function of
word pair concreteness. Data represent average word pair similarity in
word2vec (gray) and comp-syn (black) in $40$ equally-sized bins of summed word
pair concreteness.

###  3.1 Comparison to word2vec Similarity

We begin by demonstrating that pairwise word similarity is highly correlated
in comp-syn and word2vec, illustrating the semantic coherence of our color
embeddings. We calculate pairwise distances between each of the 40,000 words
in our dataset and 500 randomly-selected words from the same set, yielding
over $10^{7}$ distinct pairs. We compare the cosine similarity between word
pairs in the Mikolov et al. [Mikolov et al., 2013] word2vec model with the
Jensen-Shannon (JS) divergence between $J_{z}A_{z}B_{z}$ distributions in
comp-syn. Fig. 1A shows that JS divergence in comp-syn is significantly
correlated with cosine similarity in word2vec ($p<0.00001$, $\mathrm{JT}=773$,
Jonckheere-Terpstra test). This implies that our low-dimensional,
interpretable embedding captures aspects of the key information contained in a
widely-used distributional semantics model.

###  3.2 Relation to Human Concreteness Judgments

Next, we examine the relation between our word–color embeddings and human
concreteness judgments [Brysbaert et al., 2014]. We label word pairs with
summed concreteness ratings in the highest (lowest) quartile of our data as
“concrete” (“abstract”). Fig. 1A shows that abstract word pairs are more
similar in colorspace than concrete word pairs, even at fixed word2vec
similarity ($p=0.001$, $\mathrm{DF}=77$, Dickey-Fuller test). Moreover, as
shown in Fig. 1B, comp-syn captures concreteness judgments in a more
interpretable fashion than word2vec. In particular, because abstract words are
more similar in colorspace (on average), there is a monotonic relationship
between color similarity and concreteness; indeed, a linear model of comp-syn
similarity accounts for nearly all of the variance in word pair concreteness
($R^{2}=0.96$). On the other hand, word2vec similarity is a nonlinear function
of word pair concreteness. Although nonlinear functions of word2vec similarity
also predict concreteness well ($R^{2}>0.99$), comp-syn versions of the same
nonlinear models are significantly more accurate (log-likelihood difference
$\Delta\ln\mathcal{L}\sim 10$ in favor of comp-syn) and less complex (Bayesian
information criterion $\Delta\mathrm{BIC}\sim 20$, also in favor of comp-syn).

To qualitatively explore the relationship between our word–color embeddings
and human concreteness judgment, Fig. 3A shows the perceptually uniform color
distributions associated with some of the most and least concrete words in our
corpus. These _colorgrams_ illustrate that concrete words (e.g., “pyramid”)
are often associated with color distributions that are peaked in specific
regions of colorspace, while abstract words (e.g., “concept”) feature more
variegated color distributions. The spatial and textural features of the
images reflect these properties, and exploring the relationship between these
aspects of _colorgrams_ , is an interesting avenue for future study.

Figure 2: Classifying metaphorical vs. literal adjective-noun pairs with comp-
syn. (A) Test set classification accuracy for comp-syn (magenta) and word2vec
(gray) as a function of PCA embedding dimension. (B) Average similarity of
metaphorical and literal adjective-noun pairs in word2vec (left panel) and
comp-syn (right panel). Error bars indicate $95\%$ confidence intervals.

###  3.3 Metaphor Pair Analysis

The results above suggest that our word–color embeddings encode complementary
information about concept concreteness relative to purely textual embeddings.
This raises the question of what can be learned from cases in which word2vec
and comp-syn provide conflicting similarity predictions when evaluated on the
same pair of words. Here, we address this question by demonstrating that comp-
syn significantly enriches metaphorical word pair classification, which often
requires extensive manual tagging due to subtle uses of both sensory and
abstract features [Lakoff and Johnson, 2008, Bethard et al., 2009, Indurkhya
and Ojha, 2013, Dodge et al., 2015, Winter, 2019].

We trained a gradient-boosted tree classifier implemented via XGBoost [Chen
and Guestrin, 2016] to label adjective-noun pairs as either metaphorical or
literal, using over $8000$ word pairs from Tsvetkov et al. [Tsvetkov et al.,
2014] and Gutiérrez et al. [Gutiérrez et al., 2016]. This dataset encompasses
a statistically representative range of metaphorical and literal contexts for
each adjective [Gutiérrez et al., 2016]. To compare embeddings, we compressed
word2vec’s 300-dimensional word vector differences using PCA to match the
dimensionality of comp-syn, following Bolukbasi et al. [Bolukbasi et al.,
2016]. Fig. 2A shows that a classifier trained using only word2vec achieves a
limiting test set accuracy of $95\%$, compared to $92\%$ for comp-syn.
Importantly, comp-syn outperforms word2vec at low embedding dimensions,
indicating that it captures semantic content in an interpretable fashion. This
analysis does not demonstrate either model’s best-case performance on this
task; rather, it highlights the complementary information provided by comp-
syn.

Strikingly, word2vec and comp-syn distances provide qualitatively different
information when distinguishing literal and metaphorical adjective-noun pairs.
Fig. 2B shows that literal adjective-noun pairs are more similar than
metaphorical pairs in word2vec ($p<0.001$, Wilcoxon rank sum); the reverse
holds in comp-syn, where literal pairs are significantly _less_ similar than
metaphorical pairs ($p<0.001$, Wilcoxon rank sum). This is a consequence of
the fact that images associated with concrete words are more variable in
colorspace [Guilbeault et al., 2020]. In this way, comp-syn reveals
differences in color similarity between literal and metaphorical adjective-
noun pairs that are of interest for cognitive theory [Indurkhya and Ojha,
2013]. Particularly, our findings suggest that metaphors can exploit color
similarities between words that are dissimilar in textual embeddings, which
may help facilitate cognitive processing of semantic relations among concepts
from distinct domains [Guilbeault et al., 2020].

Qualitative inspection of specific adjective-noun word pairs highlights some
notable differences between textual and word–color embeddings. Fig. 3B
provides visual representations of the color distributions for word pairs in
our metaphorical vs. literal dataset that are most and least similar in comp-
syn. Interestingly, while metaphorical pairs are more similar than literal
pairs in comp-syn, the _least_ similar metaphorical pairs explicitly invoke
color, e.g., “deep orange”. Algorithmically, this is due to the fact that
comp-syn embeddings associated with color terms are unusually coherent. On the
other hand, the color distributions associated with the most similar pairs in
word2vec (e.g., “bushy beard”) often noticeably contrast, while word2vec’s
least similar pairs (e.g., “rough customer”) do not strongly invoke color.
These findings point to an important direction for future research enabled by
the grounded nature of comp-syn: how do linguistic metaphors leverage sensory
information to characterize colorspace itself (e.g., in the use of spatial
information in the popular metaphor “deep purple”)?

Figure 3: (A) Examples of the most and least concrete terms, visualized using
our word–color embedding method. (B) Examples of the most and least similar
adjective-noun pairs according to comp-syn word–color embeddings. We represent
each term using a _colorgram_ , i.e., a composite image produced by averaging
the perceptually uniform colors of pixels across Google Image search results.

##  4 Conclusion and Future Work

We have presented comp-syn, a new Python package that provides perceptually
grounded color-based word embeddings. These embeddings are interpretable with
respect to theories of embodied cognition because (1) comp-syn represents
color in a fashion that emulates human perception, and (2) comp-syn leverages
Google Image search results that human users dynamically interact with and
produce. By linking comp-syn with human concreteness judgments for 40,000
common English words, our package provides a multi-modal playground for
exploring grounded semantics. We demonstrated that comp-syn enriches popular
distributional semantics models in both word concreteness prediction and
metaphorical word-pair classification. A myriad of comp-syn applications
await, including color-based classification of text genres and the
characterization of sensory imagery in everyday language.

## Acknowledgements

The authors gratefully acknowledge the support of the Complex Systems Summer
School hosted at the Institute of American Indian Arts and the Santa Fe
Institute, where this project was initiated. D.G. gratefully acknowledges
financial support from the Institute on Research and Innovation in Science.
This research received support from the National Science Foundation (NSF)
under grant no. NSF DGE-1656518 through the NSF Graduate Research Fellowship
received by E.O.N. D.G. and T.H. acknowledge intellectual support from the
Institute for Advanced Learning (IAL) in Ontario, Canada.

## References

  * [Bergen, 2012]  Benjamin K Bergen.  2012\.  Louder than words: The new science of how the mind makes meaning.  Basic Books.
  * [Bethard et al., 2009]  Steven Bethard, Vicky Lai, and James Martin.  2009\.  Topic model analysis of metaphor frequency for psycholinguistic stimuli.  Proceedings of the Workshop on Computational Approaches to Linguistic Creativity, pages 9–16.
  * [Bolukbasi et al., 2016]  Tolga Bolukbasi, Kai-Wei Chang, James Zou, Venkatesh Saligrama, and Adam Kalai.  2016\.  Man is to computer programmer as woman is to homemaker? debiasing word embeddings.  In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16, page 4356–4364, Red Hook, NY, USA. Curran Associates Inc.
  * [Bruni et al., 2014]  Elia Bruni, Nam-Khanh Tran, and Marco Baroni.  2014\.  Multimodal distributional semantics.  Journal of artificial intelligence research, 49:1–47.
  * [Brysbaert et al., 2014]  Marc Brysbaert, Amy Beth Warriner, and Victor Kuperman.  2014\.  Concreteness ratings for 40 thousand generally known english word lemmas.  Behavior research methods, 46(3):904–911.
  * [Chen and Guestrin, 2016]  Tianqi Chen and Carlos Guestrin.  2016\.  XGBoost: A scalable tree boosting system.  In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, pages 785–794, New York, NY, USA. ACM.
  * [Clark, 2018]  Alex Clark.  2018\.  Pillow python imaging library.  Pillow—Pillow (PIL Fork) 5.4. 1 documentation.
  * [Deng et al., 2009]  Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  2009\.  Imagenet: A large-scale hierarchical image database.  2009 IEEE Conference on Computer Vision and Pattern Recognition.
  * [Dodge et al., 2015]  Ellen Dodge, Jisup Hong, and Elise Stickles.  2015\.  Metanet: Deep semantic automatic metaphor analysis.  Proceedings of the Third Workshop on Metaphor in NLP, pages 40–49.
  * [Elliot and Maier, 2014]  Andrew Elliot and Markus Maier.  2014\.  Color psychology: Effects of perceiving color on psychological functioning in humans.  Annual Review of Psychology, 65:95–120.
  * [Gallese and Lakoff, 2005]  Vittorio Gallese and George Lakoff.  2005\.  The brain’s concepts: The role of the sensory-motor system in conceptual knowledge.  Cognitive neuropsychology, 22(3-4):455–479.
  * [Guilbeault et al., 2020]  Douglas Guilbeault, Ethan O Nadler, Mark Chu, Donald Ruggiero Lo Sardo, Aabir Abubaker Kar, and Bhargav Srinivasa Desikan.  2020\.  Color associations in abstract semantic domains.  Cognition, 201:104306.
  * [Gutiérrez et al., 2016]  E. Dario Gutiérrez, Ekaterina Shutova, Tyler Marghetis, and Benjamin Bergen.  2016\.  Literal and metaphorical senses in compositional distributional semantic models.  In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 183–193, Berlin, Germany, August. Association for Computational Linguistics.
  * [Hunter, 2007]  John D Hunter.  2007\.  Matplotlib: A 2d graphics environment.  Computing in science & engineering, 9(3):90–95.
  * [Indurkhya and Ojha, 2013]  Bipin Indurkhya and Amitash Ojha.  2013\.  An empirical study on the role of perceptual similarity in visual metaphors and creativity.  Metaphor and Symbol, 28.
  * [International Commission On Illumination, 1978]  International Commission On Illumination.  1978\.  Recommendations on uniform color spaces, color-difference equations, psychometric color terms.  Color Research & Application, 15.
  * [Ji et al., 2019]  S. Ji, N. Satish, S. Li, and P. K. Dubey.  2019\.  Parallelizing word2vec in shared and distributed memory.  IEEE Transactions on Parallel and Distributed Systems, 30(9):2090–2100.
  * [Jing and Baluja, 2008]  Yushi Jing and Shumeet Baluja.  2008\.  Pagerank for product image search.  In Proceedings of the 17th international conference on World Wide Web, pages 307–316.
  * [Jones et al., 2001]  Eric Jones, Travis Oliphant, Pearu Peterson, et al.  2001\.  Scipy: Open source scientific tools for python.
  * [Lakoff and Johnson, 2008]  George Lakoff and Mark Johnson.  2008\.  Metaphors we live by.  University of Chicago press.
  * [Lakoff and Turner, 1989]  George Lakoff and Mark Turner.  1989\.  More than cool reason: A field guide to poetic metaphor.  University of Chicago press.
  * [Landauer and Dumais, 1997]  Thomas K Landauer and Susan T Dumais.  1997\.  A solution to plato’s problem: The latent semantic analysis theory of acquisition, induction, and representation of knowledge.  Psychological review, 104(2):211.
  * [Levy and Goldberg, 2014]  Omer Levy and Yoav Goldberg.  2014\.  Dependency-based word embeddings.  In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 302–308.
  * [Lu et al., 2019]  Jiasen Lu, Dhruv Batra, Devi Parikh, and Stefan Lee.  2019\.  Vilbert: Pretraining task-agnostic visiolinguistic representations for vision-and-language tasks.  In Advances in Neural Information Processing Systems, pages 13–23.
  * [Mehta and Zhu, 2009]  Ravi Mehta and Rui Zhu.  2009\.  Blue or red? exploring the effect of color on cognitive task performances.  Science, 323:1226–1229.
  * [Mikolov et al., 2013]  Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.  2013\.  Distributed representations of words and phrases and their compositionality.  In Advances in neural information processing systems, pages 3111–3119.
  * [Miller, 1998]  George A Miller.  1998\.  WordNet: An electronic lexical database.  MIT press.
  * [Pérez and Granger, 2007]  Fernando Pérez and Brian E Granger.  2007\.  Ipython: a system for interactive scientific computing.  Computing in science & engineering, 9(3):21–29.
  * [Riley, 1995]  Charles Riley.  1995\.  Color Codes: Modern Theories of Color in Philosophy, Painting and Architecture, Literature, Music, and Psychology.  UPNE.
  * [Safdar et al., 2017]  Muhammad Safdar, Guihua Cui, Youn Jin Kim, and Ming Ronnier Luo.  2017\.  Perceptually uniform color space for image signals including high dynamic range and wide gamut.  Optics express, 25(13):15131–15151.
  * [Socher et al., 2014]  Richard Socher, Andrej Karpathy, Quoc V Le, Christopher D Manning, and Andrew Y Ng.  2014\.  Grounded compositional semantics for finding and describing images with sentences.  Transactions of the Association for Computational Linguistics, 2:207–218.
  * [Tsvetkov et al., 2014]  Yulia Tsvetkov, Leonid Boytsov, Anatole Gershman, Eric Nyberg, and Chris Dyer.  2014\.  Metaphor detection with cross-lingual model transfer.  In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 248–258, Baltimore, Maryland, June. Association for Computational Linguistics.
  * [Virtanen et al., 2020]  Pauli Virtanen, Ralf Gommers, Travis E Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al.  2020\.  Scipy 1.0: fundamental algorithms for scientific computing in python.  Nature methods, 17(3):261–272.
  * [Walt et al., 2011]  Stéfan van der Walt, S Chris Colbert, and Gael Varoquaux.  2011\.  The numpy array: a structure for efficient numerical computation.  Computing in science & engineering, 13(2):22–30.
  * [Winter, 2019]  Bodo Winter.  2019\.  Sensory Linguistics.  John Benjamins Publishing Company.
  * [Şenel et al., 2018]  L. K. Şenel, İ. Utlu, V. Yücesoy, A. Koç, and T. Çukur.  2018\.  Semantic structure and interpretability of word embeddings.  IEEE/ACM Transactions on Audio, Speech, and Language Processing, 26(10):1769–1779.

##  Appendix A comp-syn Code

comp-syn is an open source Python package, available on GitHub and
downloadable through PyPi at https://github.com/comp-syn/comp-syn. It uses
NumPy [Walt et al., 2011] and scipy [Jones et al., 2001] for computational
purposes, matplotlib [Hunter, 2007] for visualisations, and Pillow [Clark,
2018] to load and manipulate images in Python. We provide documentation and
extensive examples of code use through Jupyter/IPython notebooks [Pérez and
Granger, 2007].

With a focus on community-based development, our code is PEP8 compliant,
heavily commented and documented, includes continuous code integration and
testing via Travis CI, and uses GitHub as a platform for issue tracking and
ideation. comp-syn is structured so that it is easily compatible with
contemporary deep learning, natural language processing and computational
linguistics Python packages, and particularly with NumPy and SciPy as standard
tools for scientific computing [Virtanen et al., 2020].

comp-syn includes the following modules:

  * •

datahelper.py \- loader functions for scraping and organising image data;

  * •

analysis.py \- analysis functions for computing word–color embeddings;

  * •

logger.py \- logger functions;

  * •

visualisation.py \- visualisation functions;

  * •

vectors.py \- word–color embedding loader and manager;

  * •

wordnet-functions.py \- WordNet functions to facilitate web scraping and
linking with concreteness measures.

##  Appendix B Data Distribution

Along with the software, we also release word–color embeddings for the nearly
40,000 English language words. Our corpus of word–color embeddings is linked
to crowd-sourced human judgments of concept concreteness from Brysbaert et al.
[Brysbaert et al., 2014], and terms used for analysis are also linked to
WordNet [Miller, 1998]. These embeddings can easily be downloaded and loaded
into Python pipelines for various natural language processing tasks, including
jointly training or enhancing distributional semantics models. The data is
stored in the json file concreteness-color-embeddings.json and can be loaded
using the vectors.py module class LoadVectorsFromDisk. Once loaded, each
Vector object has the following information based on the top $100$ Google
Image results for each word:

  * •

rgb-dist \- the average RGB distribution, computed in $8$ evenly-segmented
bins;

  * •

jzazbz-dist \- the average perceptually uniform $J_{z}A_{z}B_{z}$
distribution, computed in $8$ evenly-segmented bins;

  * •

jzazbz-dist-std \- the standard deviation over the perceptually uniform
$J_{z}A_{z}B_{z}$ distribution, computed in $8$ evenly-segmented bins;

  * •

colorgram \- a composite image created by pixel-wise averaging over the top
$100$ images, representing the word’s “average image”;

  * •

rgb-vector \- the mean RGB coordinates, averaged over the top $100$ images;

  * •

jzazbz-vector \- the mean $J_{z}A_{z}B_{z}$ coordinates, averged over the top
$100$ images

  * •

concreteness-mean \- the mean of the concreteness scores for the word from
[Brysbaert et al., 2014];

  * •

concreteness-sd \- the standard deviation of the concreteness scores for the
word from [Brysbaert et al., 2014].

##  Appendix C Methods

###  C.1 Google Image Search

To generate word–color embeddings, we collect the top $100$ Google Image
search results for each of the 40,000 terms in our analysis. The Google Image
searches were run from 10 servers running in a commercial datacenter in New
York, USA. These servers were created and used only for this experiment, so
that results would not be overly-personalized. Additional search parameters
were included as query strings safe=off&site=&tbm=isch&source=hp&gs_l=img.

###  C.2 Word–Color Embeddings

We use the PIL Python module to convert each image into an $m\times n\times 3$
array of sRGB values, where $m$ and $n$ are the intrinsic image dimensions.
For computational efficiency, we then compress each image into an anti-aliased
$300\times 300\times 3$ array. Next, we transform sRGB pixel values into their
counterparts in the perceptually uniform $J_{z}A_{z}B_{z}$ colorspace.222comp-
syn efficiently computes color embeddings in multiple colorspaces if desired,
including more traditional (non-perceptually uniform) options such as RGB and
HSV. Unlike in standard colorspace, Euclidean distances in $J_{z}A_{z}B_{z}$
coordinates linearly correspond to differences in human color perception
[Safdar et al., 2017]. Moreover, our use of the $J_{z}A_{z}B_{z}$ colorspace
rather than a standard colorspace like RGB increases the semantic coherence of
our word–color embeddings [Guilbeault et al., 2020].

We measure the color distribution of each image in 8 evenly-segmented
$J_{z}A_{z}B_{z}$ subvolumes spanning the range of $J_{z}A_{z}B_{z}$
coordinates that maps to all possible RGB tuples: $J_{z}\in[0,0.167]$,
$A_{z}\in[-0.1,0.11]$, $B_{z}\in[-0.156,0.115]$. Next, we average
$J_{z}A_{z}B_{z}$ distributions over all $100$ images for each term to obtain
an aggregate, 8-dimensional color mean embedding. We also compute the standard
deviation over the $100$ images in each $J_{z}A_{z}B_{z}$ subvolumes to obtain
an aggregate, 8-dimensional color variability embedding. These color mean and
variability embeddings can be concatenated to create a 16-dimensional
embedding. The details of our compression, binning, and averaging steps do not
affect our results [Guilbeault et al., 2020].

To compare word–color embeddings, we use the Jensen-Shannon (JS) divergence to
measure the similarity of aggregate $J_{z}A_{z}B_{z}$ distributions. In
particular, for $J_{z}A_{z}B_{z}$ distributions $C_{i}$ and $C_{j}$ associated
with terms $i$ and $j$, the JS divergence is given by

$D_{\mathrm{JS}}(C_{1}~{}||~{}C_{2})\equiv\frac{1}{2}\left[D_{\mathrm{KL}}(C_{1}~{}||~{}\bar{C}_{12})+D_{\mathrm{KL}}(C_{2}~{}||~{}\bar{C}_{12})\right],$
(1)

where $D_{\rm{KL}}$ is the Kullback-Leibler divergence and
$\bar{C}_{12}\equiv(C_{1}+C_{2})/2$. The JS divergence is a measure of the
distance between two color distributions, such that lower values correspond to
more similar distributions in perceptually uniform colorspace. We choose this
metric because it is a well-defined distance measure that satisfies the
triangle inequality and allows us to avoid undefined values associated with
empty $J_{z}A_{z}B_{z}$ bins. Terms with relatively high mutual JS divergences
usually exhibit _colorgrams_ with perceptibly different average colors.

##  Appendix D Best Practices for Usage

We caution that our word–color embeddings are _distributions_ rather than
_vectors_. Thus, their components are positive semidefinite, and different
embeddings must be compared using similarity measures designed for
distributions such as JS divergence. On the other hand, word2vec embeddings
are vectors with components that can be positive or negative, and are compared
using similarity measures designed for vectors such as cosine similarity.
Importantly, unlike word2vec embeddings, our word–color embeddings cannot be
composed by vector addition. We are exploring algebraic techniques for word
composition in colorspace; these techniques must respect the underlying
mathematical structure of $J_{z}A_{z}B_{z}$ (and other) colorspaces, which are
not closed under standard binary operations like addition or multiplication.


* [73] Marius Leordeanu, Rahul Sukthankar and Martial Hebert  “Unsupervised learning for graph matching”  In _International Journal of Computer Vision_ 96, 2012, pp. 28–45
  * [74] Kang Li, Xiaodong Wu, Danny Z Chen and Milan Sonka  “Optimal surface segmentation in volumetric images-a graph-theoretic approach”  In _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 28.1, 2005, pp. 119–134
  * [75] Jiangyu Liu and Jian Sun  “Parallel Graph-cuts by Adaptive Bottom-up Merging”  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 2010, pp. 2181–2188
  * [76] Lei Liu, Yun Sheng, Guixu Zhang and Hassan Ugail  “Graph cut based mesh segmentation using feature points and geodesic distance”  In _Proceedings of the International Conference on Cyberworlds (CW)_ , 2015, pp. 115–120
  * [77] Eric Maire and Philip John Withers  “Quantitative X-ray tomography”  In _International materials reviews_ 59.1, 2014, pp. 1–43
  * [78] Leland McInnes, John Healy and James Melville  “Umap: Uniform manifold approximation and projection for dimension reduction”  In _arXiv:1802.03426_ , 2018
  * [79] Fausto Milletari, Nassir Navab and Seyed-Ahmad Ahmadi  “V-net: Fully convolutional neural networks for volumetric medical image segmentation”  In _International Conference on 3D Vision_ , 2016, pp. 565–571
  * [80] Shervin Minaee et al.  “Image segmentation using deep learning: A survey”  In _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2021
  * [81] Rajmund Mokso et al.  “GigaFRoST: the gigabit fast readout system for tomography”  In _Journal of synchrotron radiation_ 24.6, 2017, pp. 1250–1259
  * [82] Sebastian Nowozin et al.  “Decision tree fields”  In _International Conference on Computer Vision_ , 2011, pp. 1668–1675
  * [83] F. Pedregosa et al.  “Scikit-learn: Machine Learning in Python”  In _Journal of Machine Learning and Research_ 12, 2011, pp. 2825–2830
  * [84] Bo Peng, Lei Zhang and David Zhang  “A survey of graph theoretical approaches to image segmentation”  In _Pattern Recognition_ 46.3, 2013, pp. 1020–1038
  * [85] Sida Peng et al.  “Deep snake for real-time instance segmentation”  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 8533–8542
  * [86] Yi Peng et al.  “JF-Cut: A parallel graph cut approach for large-scale image and video”  In _IEEE Transactions on Image Processing_ 24.2, 2015, pp. 655–666
  * [87] Marius Reichardt et al.  “3D virtual Histopathology of Cardiac Tissue from Covid-19 Patients based on Phase-Contrast X-ray Tomography”  In _eLife._ , 2021
  * [88] Carsten Rother, Vladimir Kolmogorov, Victor Lempitsky and Martin Szummer  “Optimizing binary MRFs via extended roof duality”  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 2007, pp. 1–8
  * [89] Alexander Shekhovtsov and Václav Hlaváč  “A distributed mincut/maxflow algorithm combining path augmentation and push-relabel”  In _International Journal of Computer Vision_ 104.3, 2013, pp. 315–342
  * [90] Amber L Simpson et al.  “A large annotated medical image dataset for the development and evaluation of segmentation algorithms”  In _arXiv:1902.09063_ , 2019
  * [91] Petter Strandmark and Fredrik Kahl  “Parallel and Distributed Graph Cuts by Dual Decomposition”  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 2010, pp. 2085–2092
  * [92] Paul Swoboda et al.  “A study of lagrangean decompositions and dual ascent solvers for graph matching”  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 1607–1616
  * [93] Nima Tajbakhsh et al.  “Embracing imperfect datasets: A review of deep learning solutions for medical image segmentation”  In _Medical Image Analysis_ 63, 2020, pp. 101693
  * [94] Lorenzo Torresani, Vladimir Kolmogorov and Carsten Rother  “Feature correspondence via graph matching: Models and global optimization”  In _European Conference on Computer Vision_ , 2008, pp. 596–609
  * [95] Tanmay Verma and Dhruv Batra  “MaxFlow Revisited: An Empirical Comparison of Maxflow Algorithms for Dense Vision Problems”  In _British Machine Vision Conference_ , 2012, pp. 1–12
  * [96] Vibhav Vineet and P J Narayanan  “CUDA cuts: Fast graph cuts on the GPU”  In _IEEE Conference on Computer Vision and Pattern Recognition Workshops_ , 2008, pp. 1–8
  * [97] Yao Wang and Reinhard Beichel  “Graph-based segmentation of lymph nodes in CT data”  In _International Symposium on Visual Computing_ , 2010, pp. 312–321
  * [98] University Waterloo  “Max-flow problem instances in vision” Accessed 2021-02-05, https://vision.cs.uwaterloo.ca/data/maxflow
  * [99] Udaranga Wickramasinghe, Edoardo Remelli, Graham Knott and Pascal Fua  “Voxel2mesh: 3d mesh model generation from volumetric data”  In _International Conference on Medical Image Computing and Computer Assisted Intervention_ , 2020, pp. 299–308  Springer
  * [100] Xiaodong Wu and Danny Z Chen  “Optimal net surface problems with applications”  In _International Colloquium on Automata, Languages, and Programming_ , 2002, pp. 1029–1042
  * [101] Yin Yin et al.  “LOGISMOS—layered optimal graph image segmentation of multiple objects and surfaces: cartilage segmentation in the knee joint”  In _IEEE Transactions on Medical Imaging_ 29.12, 2010, pp. 2023–2037
  * [102] Miao Yu, Shuhan Shen and Zhanyi Hu  “Dynamic Graph Cuts in Parallel”  In _IEEE Transactions on Image Processing_ 26.8 Institute of ElectricalElectronics Engineers Inc., 2017
  * [103] Miao Yu, Shuhan Shen and Zhanyi Hu  “Dynamic Parallel and Distributed Graph Cuts”  In _IEEE Transactions on Image Processing_ 25.12, 2015, pp. 5511–5525

|  Patrick M. Jensen was born in Copenhagen, Denmark, in 1994. He received his
B.Sc.Eng degree in 2017 and M.Sc.Eng degree in 2019, both in applied
mathematics, at the Technical University of Denmark (DTU), Kgs. Lyngby,
Denmark. He is currently pursuing a Ph.D. in 3D image analysis at the Visual
Computing group at the Department of Applied Mathematics and Computer Science,
Technical University of Denmark. His research interests lie in 3D image
segmentation.
---|---
|  Niels Jeppesen is an image analysis and machine learning specialist at
FORCE Technology with a Ph.D. degree in image analysis of 3D structures from
the Department of Applied Mathematics and Computer Science, Technical
University of Denmark (DTU), Kgs. Lyngby, Denmark. His research interests lie
in min-cut/max-flow algorithms and quantitative analysis of structures in 3D
images. He applies these methods for automated quality control of structures
and materials, in particular, in the wind turbine industry.
---|---
|  Anders Bjorholm Dahl is professor in 3D image analysis, and a head of the
Section for Visual Computing at the Department of Applied Mathematics and
Computer Science, Technical University of Denmark (DTU), Kgs. Lyngby, Denmark.
He is heading The Center for Quantification of Imaging Data from MAX IV,
focusing on quantitative analysis of 3D images. His research is focused on
image segmentation and its applications.
---|---
|  Vedrana Andersen Dahl is an associate professor at the Department of
Applied Mathematics and Computer Science, Technical University of Denmark
(DTU), Kgs. Lyngby, Denmark. Her primary research interest is in the use of
geometric models for the analysis of volumetric data. This includes volumetric
segmentation and methods based on deformable meshes. She developed analysis
tools with applications in material science, industrial inspection, and
biomedicine.
---|---