# Satisfiability of commutative vs. non-commutative CSPs††thanks: This work
was supported by UKRI EP/X024431/1 and NSERC Discovery grant. For the purpose
of Open Access, the authors have applied a CC BY public copyright licence to
any Author Accepted Manuscript version arising from this submission. All data
is provided in full in the results section of this paper.

Andrei A. Bulatov
SFU
<EMAIL_ADDRESS>Stanislav Živný
University of Oxford
<EMAIL_ADDRESS>
###### Abstract

The Mermin-Peres magic square is a celebrated example of a system of Boolean
linear equations that is not (classically) satisfiable but is satisfiable via
linear operators on a Hilbert space of dimension four. A natural question is
then, for what kind of problems such a phenomenon occurs? Atserias, Kolaitis,
and Severini answered this question for all Boolean Constraint Satisfaction
Problems (CSPs): For 2-SAT, Horn-SAT, and Dual Horn-SAT, classical
satisfiability and operator satisfiability is the same and thus there is no
gap; for all other Boolean CSPs, the two notions differ as there is a gap,
i.e., there are unsatisfiable instances that are satisfied via operators on a
finite-dimensional Hilbert space. We generalize their result to CSPs on
_arbitrary finite_ domains: CSPs of so-called bounded-width have no
satisfiability gap, whereas all other CSPs have a satisfiability gap.

##  1 Introduction

Symmetry leads to efficient computation. This phenomenon has manifested itself
in several research areas that have one aspect in common, namely a model of
computation with local constraints that restrict the solution space of the
problem of interest. An elegant way to describe such problems is in the
framework of Constraint Satisfaction Problems (CSPs). CSPs have driven some of
the most influential developments in theoretical computer science, from NP-
completeness to the PCP theorem to semidefinite programming algorithms to the
Unique Games Conjecture. The mathematical structure of tractable decision CSPs
[15, 57], infinite-domain CSPs [7, 8], optimization CSPs [53], as well as
approximable CSPs [50, 10], is now known to be linked to certain forms of
higher-order symmetries of the solution spaces. A recently emerging research
direction links CSPs with foundational topics in physics and quantum
computation [18, 17, 2, 47, 41].

#### Constraint Satisfaction Problems

CSPs capture some of the most fundamental computational problems, including
graph and hypergraph colorings, linear equations, and variants and
generalizations of satisfiability. Informally, one is given a set of variables
and a set of constraints, each depending only on constantly many variables.
Given a CSP instance, the goal is to find an assignment of values to all the
variables so that all constraints are satisfied. For example, if the domain is
$\\{r,g,b\\}$ and the constraints are of the form $R(x,y)$, where
$R=\\{(r,g),(g,r),(g,b),(b,g),(r,b),(b,r)\\}$ is the binary disequality
relation on $\\{r,g,b\\}$, we obtain the classic graph 3-Colorability problem.
If the domain is $\\{r,g,b,o\\}$ and the constraints are of the form $R(x,y)$,
where $R=\\{(r,g),(g,r),(g,b),(b,g),(b,o),(o,b),(o,r),(r,o)\\}$, we obtain a
variant of the graph 4-Colorability problem in which adjacent vertices must be
assigned different colors and, additionally, red and blue vertices must not be
adjacent and green and orange vertices must not be adjacent.

Back in 1978, Schaefer famously classified all Boolean CSPs as solvable in
polynomial time or NP-hard [51].111We call a CSP _Boolean_ if the domain of
all variables is of size two. Some papers call such CSPs binary. We use the
term _binary_ for a relation of arity two and for CSPs whose constraints
involve binary relations. The tractable cases are the standard textbook
problems, namely 2-SAT, Horn-SAT, dual Horn-SAT, and system of linear
equations on a two-element set.222There are also two trivial, uninteresting
cases called 0-valid and 1-valid. Hell and Nešetřil studied a special case of
CSPs known as graph homomorphisms [28]. These are CSPs in which all
constraints involve the same binary symmetric relation, i.e., a graph. The
above-mentioned 3-Colorability problem is the homomorphism problem to $K_{3}$,
the undirected clique on three vertices, say $\\{r,g,b\\}$. The above-
mentioned variant of 4-Colorability is the homomorphism problem to $C_{4}$,
the undirected cycle on four vertices, say $\\{r,g,b,o\\}$. Generalizing
greatly the classic result of Karp that $k$-Colorability is solvable in
polynomial time for $k\leq 2$ and NP-hard for $k\geq 3$ and other concrete
problems such as the (tractable) variant of 4-Colorability above, Hell and
Nešetřil obtained in 1990 a complete classification of such CSPs [27].
Motivated by these two results and the quest to identify the largest subclass
of NP that could exhibit a dichotomy and thus avoid NP-intermediate cases,
Feder and Vardi famously conjectured that _all_ CSPs on finite domains admit a
dichotomy; i.e., are either solvable in polynomial time or are NP-hard [23].

Following the so-called algebraic approach to CSPs, pioneered by Jeavons,
Cohen an Gyssens [30] and Bulatov, Jeavons, and Krokhin [12], the conjecture
was resolved in the affirmative in 2017 by Bulatov [15] and, independently, by
Zhuk [56, 57]. The algebraic approach allows for a very clean and precise
characterization of what makes certain CSPs computationally tractable — this
is captured by the notion of polymorphisms, which can be thought of as
multivariate symmetries of solutions spaces of CSPs. Along the way to the
resolution of the Feder-Vardi dichotomy conjecture, the algebraic approach has
been successfully used to establish other results about CSPs, e.g.,
characterizing the power of local consistency algorithms for CSPs [11, 3],
characterizing robustly solvable CSPs [25, 20, 4], classifying the complexity
of exact optimization CSPs [53, 37], the tremendous progress on classifying
the complexity of CSPs on infinite domains [7], and very recently using SDPs
for robustly solving certain promise CSPs [9].

#### Operator Constraint Satisfaction Problems

Consider the following instance of a Boolean CSP, consisting in nine variables
$x_{1},\ldots,x_{9}$ over the Boolean domain $\\{-1,+1\\}$ and the following
six constraints:

$\begin{split}x_{1}x_{2}x_{3}=+1,\qquad x_{1}x_{4}x_{7}=+1,\\\
x_{4}x_{5}x_{6}=+1,\qquad x_{2}x_{5}x_{8}=+1,\\\ x_{7}x_{8}x_{9}=+1,\qquad
x_{3}x_{6}x_{9}=-1.\end{split}$ (1)

Graphically, this system of equations can be represented by a square, where
each equation on the left of (1) comes from a row, and each equation on the
right of (1) comes from a column.

$x_{1}$ | $x_{2}$ | $x_{3}$
---|---|---
$x_{4}$ | $x_{5}$ | $x_{6}$
$x_{7}$ | $x_{8}$ | $x_{9}$
$+1$
---
$+1$
$+1$
$+1$ | $+1$ | $-1$
---|---|---

$+1$ $+1$ $+1$

The system of equations (1) has no solution in the Boolean domain
$\\{-1,+1\\}$: By multiplying the left-hand sides of all equations we get $+1$
because every variable occurs twice in the system and $x_{i}^{2}=+1$ for every
$1\leq i\leq 9$. However, by multiplying the right-hand sides of all
equations, we get $-1$. Note that this argument used implicitly the assumption
that the variables commute pairwise even if they do not appear in the same
equation, which is true over $\\{-1,+1\\}$. Thus, this argument does not hold
if one assumes that only variables occurring in the same equation commute
pairwise. In fact, Mermin famously established that the system (1) has a
solution consisting of linear operators on a Hilbert space of dimension four
[44, 45] and the construction is now know as the Mermin-Peres magic square
[48]. This construction proves the Bell-Kochen-Specker theorem on the
impossibility to explain quantum mechanics via hidden variables [6, 34].

Any Boolean CSP instance, just like the one above, can be associated with a
certain non-local game with two players, say Alice and Bob, who are unable to
communicate while the game is in progress. Alice is given a constraint at
random and must return a satisfying assignment to the variables in the
constraint. Bob is given a variable from the constraint and must return an
assignment to the variable. The two players win if they assign the same value
to the chosen variable. With shared randomness, Alice and Bob can play the
game perfectly if and only the instance is satisfiable [18]. The Mermin-Peres
construction [44, 48] was the first example of an instance where the players
can play perfectly by sharing an entangled quantum state although the instance
is not satisfiable. We note that [44, 48] were looking at quantum
contextuality scenarios rather than non-local games and it was Aravind who
reformulated the construction in the above-described game setting [1], cf.
also [16]. The game was introduced for any Boolean CSP by Cleve and Mittal
[18] and further studied by Cleve, Liu, and Slofstra [17].

Every Boolean relation can be identified with its characteristic function,
which has a unique representation as a multilinear polynomial via the Fourier
transform. The multilinear polynomial representation of Boolean relations (and
thus also Boolean CSPs) makes it possible to consider _relaxations_ of
satisfiability in which the variables take values in a suitable space, rather
than in $\\{-1,+1\\}$. Such relaxations of satisfiability have been considered
in the foundations of physics long ago, playing an important role in our
understanding of the differences between classical and quantum theories. In
detail, given a Boolean CSP instance, a classical assignment assigns to every
variable a value from $\\{-1,+1\\}$. An operator assignment assigns to every
variable a linear operator $A$ on a finite-dimensional Hilbert space (which
means, up to a choice of basis, a matrix with complex entries) so that
$A^{2}=I$ and each $A$ is self-adjoint, i.e., $A=A^{*}$ and thus in particular
$A$ is normal, meaning that $AA^{*}=A^{*}A$.333$A^{*}$ denotes the conjugate
transpose; all concepts are fully defined and details provided in Section 2.
Furthermore, it is required that operators assigned to variables from the
scope of some constraint pairwise commute.

Ji showed that for Boolean CSPs corresponding to 2-SAT there is no difference
between (classical) satisfiability and satisfiability via operators [31].
Later, Atserias, Kolaitis, and Severini established a complete classification
for all Boolean CSPs parameterized by the set of allowed constraint relations.
In particular, they showed that only CSPs whose relations come from 2-SAT,
Horn-SAT, or Dual Horn-SAT have “no satisfiability gap” in the sense that
(classic) satisfiability is equivalent to operator satisfiability; for all
other Boolean CSPs, there is a satisfiability gap in the sense that there are
instances that are not (classically) satisfiable but are satisfiable via
operators just as in the Mermin-Peres magic square. The “no-gap” part of the
result is established by the substitution method [18]. The “gap” part of the
result is established by showing that reductions between CSPs based on
primitive positive formulas, which preserve complexity and were used to
establish Schaefer’s classification of Boolean CSPs, preserve satisfiability
gaps.

#### Contributions

As our main contribution, we generalize the result of Atserias et al. [2] from
Boolean CSPs to CSPs on _arbitrary finite_ domains. As has been done in, e.g,
[24, 19], we represent a finite domain of size $d$ by the $d$-th roots of
unity, and require that each operator $A$ in an operator assignment should be
normal (i.e. $AA^{*}=A^{*}A$) and should satisfy $A^{d}=I$. The representation
of non-Boolean CSPs relies on multi-dimensional Fourier transform. Our main
result proves that CSPs of _bounded width_ (on arbitrary finite domains) do
not have a satisfiability gap, meaning that classical satisfiability is
equivalent to satisfiability via operators (Theorem 9); and all other CSPs do
have a satisfiability gap, meaning that classical satisfiability is not
equivalent to satisfiability via operators (Theorem 19).

######  Theorem (Main result, informal statement).

Let $\Gamma$ be an arbitrary finite set of relations on a finite domain. If
${\rm CSP}(\Gamma)$ has bounded width then classical and operator
satisfiability are the same for ${\rm CSP}(\Gamma)$. Otherwise, classical and
operator satisfiability are not the same for ${\rm CSP}(\Gamma)$.

The proof relies on several ingredients. Firstly, we observe that results
establishing that primitive positive definability preserve satisfiability gaps
[2] can be lifted from Boolean to arbitrary finite domains. Secondly, for CSPs
of bounded width we show that there is no difference between classical and
operator satisfiability by simulating the inference by the so-called Singleton
Linear Arc Consistency (SLAC) algorithm in polynomial equations. We note that
while there are several (seemingly stronger) algorithms for CSPs of bounded
width, our proof relies crucially on the special structure of SLAC and the
breakthrough result of Kozik that SLAC solves all CSPs of bounded width [38].
Thirdly, to prove that CSPs of unbounded width have satisfiability gaps we use
the algebraic approach to CSPs, namely, we show that not only primitive
positive definitions but also other reductions, namely going to the core,
adding constants, and restrictions to subalgebras and factors, preserve
satisfiability gaps. Finally, for all odd $d$ we give an explicit construction
of a CSP instance with a satisfiability gap, which is a generalization of the
Mermin-Peres square.

We note that that there is a significant hurdle to go from Boolean CSPs to
CSPs over arbitrary finite domains. While any non-Boolean CSP can be
Booleanized via indicator variables and extra constraints, such constructions
do not immediately imply classifications of non-Boolean CSPs as the “encoding
constraints” are intended to be used in only a particular way. Indeed, while
the complexity of Boolean CSPs was established by Schaefer in 1978 [51] and
the complexity of CSPs on three-element domains was established by Bulatov in
2002 [13, 14], the dichotomy for all finite domains was only established in
2017 [15, 56, 57]. Similarly for other variants of CSPs and different notions
of tractability, results on Boolean domains, including the work of Atserias et
al. [2], rely crucially on the explicit knowledge of the structure of
relations on Boolean domains (established by Post [49]), which is not known
for non-Boolean CSPs. Indeed, on the tractability side, the structure of
relations in tractable Boolean CSPs is simple and very well understood; on the
intractability side, reductions based only on primitive positive definitions
suffice for a complete classification of Boolean CSPs. Neither of these two
facts is true for non-Boolean CSPs.

We find it fascinating that bounded width is the borderline for satisfiability
gaps for CSPs, thus linking a notion coming from a natural combinatorial
algorithm for CSPs with a foundational topic in quantum computation. This is
yet another result confirming how fundamental the notion of bounded width is,
capturing not only the power of the local consistency algorithm [40, 43, 11,
3] as conjectured in [23] with links to Datalog, pebble games, and logic [23,
36], but also robust solvability of CSPs [4], exact solvability of valued CSPs
by LP [54] and SDP [55] relaxations, and now also satisfiability via
operators.

#### Related work

The present article is concerned with distinguishing classical satisfiability
from satisfiability over finite-dimensional operators. Atserias et al. [2]
also considered satisfiability over infinite-dimensional bounded operators and
obtained a complete classification of Boolean CSPs, relying on a breakthrough
result of Slofstra, who established that there is system of linear equations
that is not satisfiable via finite-dimensional operators but is satisfiable
via infinite-dimensional bounded operators [52]. We believe that our methods
can be used for the infinite-dimensional case as well but leave it for future
work. Very recently, Paddock and Slofstra [47] streamlined the results of
Atserias et al. [2]. Moreover, [47] gives an overview of other notions of
satisfiability and their relationship, including the celebrated MIP∗=RE result
of Ji et al. [32, 33]. We note that the notion of quantum homomorphism from
the work of Mančinska and Roberson [42] is different from ours as it requires
that the operators $A$ should be idempotent, i.e., $A^{2}=A$. Recent work of
Culf, Mousavi, and Spirig studies approximability of operator CSPs [19].

##  2 Preliminaries

We denote by $[r]$ the set $\\{1,2,\ldots,r\\}$.

#### CSPs

An instance of the _constraint satisfaction problem_ (CSP) is a triple
${\mathcal{P}}=(V,D,{\mathcal{C}})$, where $V$ is a set of variables, $D$ is a
set of domain values, and ${\mathcal{C}}$ is a set of constraints. Every
constraint in ${\mathcal{C}}$ is a pair $\langle{\bf s},R\rangle$, where ${\bf
s}\in V^{r}$ is the constraint scope and $R\subseteq D^{r}$ is the constraint
relation of arity $r=ar(R)$. Given a CSP instance ${\mathcal{P}}$, the task is
to determine whether there is an assignment $s:V\to D$ that assigns to every
variable from $V$ a value from $D$ in such a way that all the constraints are
satisfied; i.e., $(s(v_{1}),\ldots,s(v_{r}))\in R$ for every constraint
$\langle(v_{1},\ldots,v_{r}),R\rangle\in{\mathcal{C}}$. An assignment
satisfying all the constraints is also called a _solution_.

Let $D$ be a fixed finite set. A finite set $\Gamma$ of relations over $D$ is
called a _constraint language_ over $D$. We denote by ${\rm CSP}(\Gamma)$ the
class of CSP instances in which all constraint relations belong to $\Gamma$. A
mapping $\varrho:D\to D$ is an _endomorphism_ or _unary polymorphism_ of
$\Gamma$ if, for any $R\in\Gamma$ (say, $r$-ary) and any
$(a_{1},\ldots,a_{r})\in R$, the tuple
$(\varrho(a_{1}),\ldots,\varrho(a_{r}))$ belongs to $R$.

#### Bounded width

Intuitively, CSPs of bounded width are those CSPs for which unsatisfiable
instances can be refuted via local propagation. An obvious obstruction to
bounded width, in addition to NP-hard CSPs, is CSPs encoding systems of linear
equations [23]. A celebrated result of Barto and Kozik established that CSPs
of bounded width are precisely those CSPs that cannot simulate, in a precise
sense, linear equations [3]. While bounded width has several characterizations
[40, 43, 11, 3, 39],444One characterization implies that checking whether a
constraint language has bounded width is decidable [39]. we will rely on the
result of Kozik [38] that established that every CSP of bounded width can be
solved through constraint propagation of a very restricted type, so-called
_Singleton Linear Arc-Consistency_ (SLAC).

In order to explain SLAC, we need to start with _Arc-Consistency_ (AC). AC is
one of the basic levels of local consistency notions. It is a property of a
CSP and also an algorithm turning an instance ${\mathcal{P}}\in{\rm
CSP}(\Gamma)$ into an equivalent subinstance ${\mathcal{P}}^{\prime}\in{\rm
CSP}(\Gamma)$ that satisfies the AC property. Intuitively, given an instance
${\mathcal{P}}=(V,D,{\mathcal{C}})\in{\rm CSP}(\Gamma)$, the AC algorithm
starts with setting the domain $D_{v}=D$ for every variable $v\in V$. Then, it
prunes the sets $\\{D_{v}\\}_{v\in V}$ in an iterative fashion, terminating
(in polynomial time in the size of ${\mathcal{P}}$) with a maximal subinstance
of ${\mathcal{P}}$ that satisfies the AC condition; namely, for every variable
$v\in V$, every value $a\in D_{v}$, and every constraint $\langle{\bf
s},R\rangle\in{\mathcal{C}}$ such that ${\bf s}[i]=v$ for some $i$, there is a
tuple ${\bf a}\in R$ with ${\bf a}[i]=a$. The resulting subinstance
${\mathcal{P}}^{\prime}$ is _equivalent_ to ${\mathcal{P}}$ in the sense that
${\mathcal{P}}$ has a solution if and only if ${\mathcal{P}}^{\prime}$ has a
solution. We say that AC _solves_ an instance ${\mathcal{P}}$ if
${\mathcal{P}}$ has a solution whenever ${\mathcal{P}}^{\prime}$ is
consistent; i.e., none of the sets $D_{v}$ in ${\mathcal{P}}^{\prime}$ is
empty. AC is not strong enough to solve all CSPs of bounded width (e.g.,
2-SAT) but its full power is understood [23, 21].

Equivalently, Arc-Consistency can be described in terms of a Datalog program
[35]. In general, a Datalog program derives facts about an instance
${\mathcal{P}}\in{\rm CSP}(\Gamma)$ using a fixed set of rules that depend on
the constraint language $\Gamma$. The rules are defined using relations from
$\Gamma$ called _extensional databases_ (EDBs) as well as a number of
auxiliary relations called _intensional databases_ (IDBs). Each rule consists
of a _head_ , which is a single IDB, and the _body_ , which is a sequence of
IDBs and EDBs. The execution of the program updates the head IDB whenever the
body of the rule is satisfied, that is, every EDB and IDB in the body is
satisfied. The computation of the program ends when no relation can be
updated, or when the goal predicate is reached. If we require that a Datalog
program should only include unary IDBs and that every rule should have at most
one EDB then the power of the program for CSPs amounts to AC. In detail, the
AC Datalog program has a unary relation (IDB) $T_{S}(v)$ for each subset
$S\subseteq D$. Then for every
$\langle(v_{1},\ldots,v_{r}),R\rangle\in{\mathcal{C}}$ and for any IDBs
$T_{S_{1}},\ldots,T_{S_{m}},T_{S}$ the program contains the rule

$T_{S}(v_{i}):-R(v_{1},\ldots,v_{r}),T_{S_{1}}(v_{i_{1}}),\ldots,T_{S_{m}}(v_{i_{m}})$

if for any ${\bf a}\in R$ such that ${\bf a}[i_{j}]\in S_{j}$ we have ${\bf
a}[i]\in S$. The Arc-Consistency algorithm is _Linear_ if $m=1$ for every rule
in the corresponding Datalog program.

The Singleton Arc-Consistency (SAC) algorithm is a modification of the AC
algorithm [22]. SAC updates the sets $\\{D_{v}\\}_{v\in V}$ as follows: it
removes $a$ from $D_{v}$ if the current instance augmented with the constraint
fixing the value $a$ to the variable $v$ is found inconsistent by the AC
algorithm. Finally, the Singleton Linear Arc-Consistency algorithm is a
modification of SAC (due to Kozik [38] and Zhuk [57]) that uses the Linear AC
algorithm rather than the AC algorithm. Kozik has shown that SLAC solves all
CSPs of bounded width [38]. As with AC, SLAC is not only an algorithm but also
a condition (of the instance ${\mathcal{P}}^{\prime}$ produced by the
algorithm). We say that an instance ${\mathcal{P}}$ is SLAC-consistent if the
SLAC algorithm, given in Figure 1, does not change the instance.

  * Input:

A CSP instance ${\mathcal{P}}=(V,D,{\mathcal{C}})$.

  * Output:

A SLAC-consistent instance ${\mathcal{P}}^{\prime}$ equivalent to
${\mathcal{P}}$

  * 1.

for each $v\in V$ set $D_{v}=U_{d}$

  * 2.

${\mathcal{P}}^{\prime}={\mathcal{P}}+\sum_{v\in V}\langle v,D_{v}\rangle$

  * 3.

until the process stabilizes

    * 3.1

pick a variable $v\in V$

    * 3.2

for each $a\in D_{v}$ do

      * 3.2.1

run Linear Arc-Consistency on ${\mathcal{P}}^{\prime}+\langle
v,\\{a\\}\rangle$

      * 3.2.2

if the problem is inconsistent, set $D_{v}=D_{v}-\\{a\\}$

    * endfor

  * enduntil

  * 4.

return ${\mathcal{P}}^{\prime}$

Figure 1: SLAC.

#### Multi-dimensional Fourier transform

Let $U_{d}$ be the set of $d$-th roots of unity, that is,
$U_{d}=\\{\lambda_{k}=e^{\frac{2\pi i}{d}k}\mid 0\leq k<d\\}$. The _Fourier
transform_ (FT) of a function $f:U_{d}^{n}\to U_{d}$ is defined, for ${\bf
a}\in U_{d}^{n}$, as $FT(f,{\bf a})=\sum_{{\bf b}\in U_{d}^{n}}f({\bf
b})\lambda_{1}^{{\bf a}\cdot{\bf b}}$. Then it is not hard to see that $f({\bf
a})=\sum_{{\bf b}\in U_{d}^{n}}FT(f,{\bf b})\lambda_{1}^{{\bf a}\cdot{\bf
b}}$, which gives rise to a representation of $f$ by a polynomial

$f(\overline{x})=\sum_{{\bf b}\in U_{d}^{n}}FT(f,{\bf b})\overline{x}^{{\bf
b}^{\prime}},$

where ${\bf b}^{\prime}=(k_{1},\ldots,k_{n})$ and ${\bf
b}[j]=\lambda_{k_{j}}$. This representation is unique [46].

#### Linear operators and Hilbert spaces

Let $V$ be a complex vector space. A _linear operator_ on $V$ is a linear map
from $V$ to $V$. The identity linear operator on $V$ is denoted by $I$. The
linear operator that is identically $0$ is denoted by $0$. Let $A$ and $B$ be
two linear operators. Then, their pointwise addition is denoted by $A+B$,
their composition is denoted by $AB$, and the pointwise scaling of $A$ by a
scalar $c\in{\mathbb{C}}$ is denoted by $cA$. All of these are linear
operators and thus we can plug linear operators in polynomials. Note that if
$A_{1},\ldots,A_{n}$ pairwise commute (i.e., $A_{i}A_{j}=A_{j}A_{i}$ for every
$i,j\in[n]$) then $P(A_{1},\ldots,A_{n})$ is well defined. We denote by
${\mathbb{C}}[x_{1},\ldots,x_{n}]$ the ring of polynomials with complex
coefficients and commuting variables $x_{1},\ldots,x_{n}$.

A _Hilbert space_ is a complex vector space with an inner product whose norm
induces a complete metric. All Hilbert spaces of finite dimension $d$ are
isomorphic to ${\mathbb{C}}^{d}$ with the standard complex inner product.
Thus, after the choice of basis, linear operators on a $d$-dimensional Hilbert
space can be identified with matrices in ${\mathbb{C}}^{d\times d}$, and
operator composition becomes matrix multiplication. All Hilbert spaces in this
paper will be of finite dimension; thus we will freely switch between the
operator and matrix terminology.

A _diagonal_ matrix has all off-diagonal entries equal to $0$. For a matrix
$A$, we denote by $A^{*}$ its conjugate transpose. Recall that
$(AB)^{*}=B^{*}A^{*}$. A matrix $A$ is _unitary_ if $A^{*}A=AA^{*}=I$, where
$I$ is the identity matrix. Two matrices $A$ and $B$ _commute_ if $AB=BA$. A
collection of matrices $A_{1},\ldots,A_{r}$ _pairwise commute_ if
$A_{i}A_{j}=A_{j}A_{i}$ for all $i,j\in[r]$. A linear operator $A$ is called
_normal_ if it commutes with $A^{*}$; i.e., $AA^{*}=A^{*}A$.

We will use the following form of the so-called _strong spectral theorem_.

######  Theorem 1 ([26]).

Let $A_{1},\ldots,A_{r}$ be normal matrices. If $A_{1},\ldots,A_{r}$ pairwise
commute then there exists a unitary matrix $U$ and diagonal matrices
$E_{1},\ldots,E_{r}$ such that $A_{i}=U^{-1}E_{i}U$ for every $i\in[r]$.

##  3 Operator CSP

In order to relax the notion of satisfiability, we first consider CSPs on
$U_{d}$ for some $d$ and represent CSPs via polynomials. Let $\Gamma$ be a
constraint language over $U_{d}$. Every constraint $\langle{\bf s},R\rangle$
of an instance ${\mathcal{P}}=(V,U_{d},{\mathcal{C}})$ of ${\rm CSP}(\Gamma)$
is represented by a polynomial $P_{R}({\bf s})$ that represents the
characteristic function $f_{R}$ of $R$:

$f_{R}({\bf s})=\left\\{\begin{array}[]{ll}\lambda_{0},&\text{if $R({\bf s})$
is true,}\\\ \lambda_{1},&\text{otherwise}.\end{array}\right.$

We note that our choice of the polynomial representation is somewhat arbitrary
but other choices lead to the same results. (For instance, [2] studied the
$d=2$ case and used $\lambda_{1}$ to represent true.)

An operator $A$ over a Hilbert space ${\mathcal{H}}$ is a _normal operator of
order $d$_ if $A$ is normal and $A^{d}=I$. Operator assignment to the instance
${\mathcal{P}}$ over a Hilbert space ${\mathcal{H}}$ is a mapping that assigns
to every variable from $V$ an operator $A_{v}$ over ${\mathcal{H}}$ such that

  * (a)

$A_{v}$ is a normal operator of order $d$ for every $v\in V$;

  * (b)

the operators $A_{v_{1}},\ldots,A_{v_{r}}$ pairwise commute for every
constraint $\langle(v_{1},\ldots,v_{r}),R\rangle\in{\mathcal{C}}$.

We call an operator assignment $\\{A_{v}\\}$ _satisfying for ${\mathcal{P}}$_
if $P_{R}(A_{v_{1}},\ldots,A_{v_{r}})=I$ for every constraint
$\langle(v_{1},\ldots,v_{r}),R\rangle\in{\mathcal{C}}$. We say that ${\rm
CSP}(\Gamma)$ has a _satisfiability gap_ if there are instances of ${\rm
CSP}(\Gamma)$ that are not satisfiable over $U_{d}$ but are satisfiable by an
operator assignment over a finite-dimensional Hilbert space.

We shall repeatedly use the following simple lemma.

######  Lemma 2.

Let $x_{1},\ldots,x_{r}$ be variables, let $Q_{1},\ldots,Q_{m},Q$ be
polynomials in ${\mathbb{C}}[x_{1},\ldots,x_{r}]$, and let ${\mathcal{H}}$ be
a Hilbert space. If every assignment over $U_{d}$ that satisfies the equations
$Q_{1}=\dots=Q_{m}=0$ also satisfies the equation $Q=0$, then every fully
commuting operator assignment over ${\mathcal{H}}$ that satisfies the
equations $Q_{1}=\dots=Q_{m}=0$ also satisfies the equation $Q=0$.

The proof of this lemma is very similar to that of the analogous claim in [2,
Lemma 3], where it was established for $d=2$. The main difference is to use
$A^{d}=I$ rather than $A^{2}=I$. For the sake of completeness we give the
proof here.

###### Proof.

Suppose that the conditions of the lemma hold and $A_{1},\ldots,A_{r}$ are
pairwise commuting operators such that the equations $Q_{1}=\dots=Q_{m}=0$ are
true when these matrices are assigned to $x_{1},\ldots,x_{r}$. Then, since
$A_{1},\ldots,A_{r}$ are normal and commute, by Theorem 1 there is a unitary
matrix $U$ such that $E_{i}=UA_{i}U^{-1}$ is a diagonal matrix. Then,
$E_{i}^{d}=I$, because $A_{i}^{d}=I$. Therefore, every diagonal entry
$E_{i}(jj)$ belongs to $U_{d}$. For every equation $Q_{\ell}$ we have
$Q_{\ell}(A_{1},\ldots,A_{r})=0$ implying
$Q_{\ell}(E_{1},\ldots,E_{r})=UQ_{\ell}(A_{1},\ldots,A_{r})U^{-1}=0$. Since
every $E_{i}$ is diagonal, for every $j$ it also holds
$Q_{\ell}(E_{1}(jj),\ldots,E_{r}(jj))=0$. By the conditions of the lemma we
also have $Q((E_{1}(jj),\ldots,E_{r}(jj))=0$, and
$Q(A_{1},\ldots,A_{r})=U^{-1}Q(E_{1},\ldots,E_{r})U=0$. ∎

##  4 Overview of results and techniques

In this section, we give an overview of how our main result is proved. All
definitions and details are provided in the main part of the paper comprizing
of Sections 5–8.

#### Bounded width

One direction of our main result is the following.

######  Theorem 3.

Let $\Gamma$ be a constraint language over $U_{d}$. If ${\rm CSP}(\Gamma)$ has
bounded width then it has no satisfiability gap.

The main idea behind the proof of Theorem 3 is to simulate the inference
provided by SLAC by inference in polynomial equations. Let ${\mathcal{S}}$ be
a SLAC-program solving ${\rm CSP}(\Gamma)$. In order to prove Theorem 3 we
take an instance ${\mathcal{P}}=(V,U_{d},{\mathcal{C}})$ of ${\rm
CSP}(\Gamma)$ that is not SLAC-consistent, and therefore has no solution, as
${\rm CSP}(\Gamma)$ has bounded width, and prove that it also has no operator
solution. We will prove it by contradiction, assuming ${\mathcal{P}}$ has an
operator solution $\\{A_{v}\\}$ and then using the rules of a SLAC-program
solving ${\rm CSP}(\Gamma)$ to infer stronger and stronger conditions on
$\\{A_{v}\\}$ that eventually lead to a contradiction.

Recall that every rule of a SLAC-program has the form $(x\in S)\wedge
R(x,y,z_{1},\ldots,z_{r}))\to(y\in S^{\prime})$ for some variables $x,y\in V$,
a constraint $\langle(x,y,z_{1},\ldots,z_{r}),R\rangle$, and sets
$S,S^{\prime}\subseteq U_{d}$. Therefore, we need to show how to encode unary
relations and rules of a SLAC-program through polynomials. For any $S\subseteq
U_{d}$, the unary constraint restricting the domain of a variable $x$ to the
set $S$ is represented by the polynomial

$Dom_{S}(x)=\prod_{k\in S}(\lambda_{k}-x)+1.$

Similarly, the rule $(x\in S)\wedge R(x,y,z_{1},\ldots,z_{r}))\to(y\in
S^{\prime})$ of the SLAC program is represented by

$Rule_{S,R,S^{\prime}}(x,y,z_{1},\ldots,z_{r})=(Dom_{\overline{S}}(x)-1)(P_{R}(x,y,z_{1},\ldots,z_{r})-\lambda_{1})(Dom_{S^{\prime}}(y)-1).$

To give an idea of how Theorem 3 is proved, we sketch the proof of the
following.

######  Lemma 4.

Let $(v_{1}\in S_{1})\to\dots\to(v_{\ell}\in S_{\ell})$ be a derivation in the
SLAC-program ${\mathcal{S}}$ and $\\{A_{v}\\}$ an operator assignment for
${\mathcal{P}}$. Then for each $i=2,\ldots,\ell$

$(Dom_{\overline{S}_{1}}(A_{v_{1}})-I)(Dom_{S_{i}}(A_{v_{i}})-I)=0.$

###### Sketch.

First, one shows via Lemma 2 that any operator assignment is a zero of
$Rule_{S,R,S^{\prime}}$ (cf. Lemma 11). This can be used to establish the
claim for $i=2$ (cf. Lemma 12). The rest of the proof is done by induction on
$i$. In the induction case we have equations

$(Dom_{\overline{S}_{1}}(A_{v_{1}})-I)(Dom_{S_{i}}(A_{v_{i}})-I)=0,$ (2)

and

$(Dom_{\overline{S}_{i}}(A_{v_{i}})-I)(Dom_{S_{i+1}}(A_{v_{i+1}})-I)=0.$ (3)

The idea is to multiply (2) by $(Dom_{S_{i+1}}(A_{v_{i+1}})-I)$ on the right,
multiply (3) by $(Dom_{\overline{S}_{1}}(A_{v_{1}})-I)$ on the left and
subtract. The problem is, however, that

$Dom_{S_{i}}(A_{v_{i}})-Dom_{\overline{S}_{i}}(A_{v_{i}})$

is not a constant polynomial. So, we also need to prove that any polynomial of
the form

$Dom_{S}(x)-Dom_{\overline{S}}(x)$

is invertible modulo $x^{d}-1$. The polynomial has the form

$p(x)=\prod_{k\in S}(x-\lambda_{k})-\prod_{k\not\in S}(x-\lambda_{k}).$

As is easily seen, if $S\neq U_{d}$ and $S\neq\mathchar 3391\relax$, then
$\lambda_{k}$ is not a root of $p(x)$ for any $\lambda_{k}\in U_{d}$.
Therefore the greatest common divisor of $p(x)$ and $x^{d}-1$ has degree 0,
and hence there exists $q(x)$ such that

$p(x)q(x)=c+r(x)(x^{d}-1).$

Thus before subtracting equations (2) and (3) we also multiply them by
$q(A_{v_{i}})$. Then we get

$\displaystyle(Dom_{\overline{S}_{1}}(A_{v_{1}})-I)(Dom_{S_{i}}(A_{v_{i}})q(A_{v_{i}})-q(A_{v_{i}})Dom_{\overline{S}_{i}}(A_{v_{i}}))(Dom_{S_{i+1}}(A_{v_{i+1}})-I)$
$\displaystyle=$ $\displaystyle 0$
$\displaystyle(Dom_{\overline{S}_{1}}(A_{v_{1}})-I)q(A_{v_{i}})(Dom_{S_{i}}(A_{v_{i}})-Dom_{\overline{S}_{i}}(A_{v_{i}}))(Dom_{S_{i+1}}(A_{v_{i+1}})-I)$
$\displaystyle=$ $\displaystyle 0$ $\displaystyle
c(Dom_{\overline{S}_{1}}(A_{v_{1}})-I)(Dom_{S_{i+1}}(A_{v_{i+1}})-I)$
$\displaystyle=$ $\displaystyle 0.$

The first transformation uses the fact that $A_{v_{i}}$ commutes with itself,
while the second one uses the property $A_{v_{i}}^{d}=I$. The result follows.
∎

To complete the proof of Theorem 3 note that the lack of SLAC-consistency
means that for some $v\in V$ the statement
$(v=\lambda_{k})\to(v\neq\lambda_{k})$ can be derived from ${\mathcal{P}}$ for
every $\lambda_{k}\in U_{d}$. By Lemma 4, for any operator assignment
$\\{A_{w}\\}$ and any $\lambda_{k}\in U_{d}$ the operator $A_{v}$ satisfies
the equation $\prod_{j\neq k}(A_{v}-\lambda_{j}I)=0$. By reverse induction on
the size of $S$, one can show that for any $S\subseteq U_{d}$ these equations
imply $\prod_{j\in S}(A_{v}-\lambda_{j}I)=0$. Then for $S=\mathchar
3391\relax$ we get $I=0$, witnessing that ${\mathcal{P}}$ has no satisfying
operator assignment.

#### Magic squares modulo $d$

Here we construct a CSP that is not satisfied over $U_{d}$ but is satisfied
over normal operators of order $d$. The construction is similar to the Mermin-
Peres magic square [44, 45, 48].

Let let $g,f:{\mathbb{Z}}_{d}\to{\mathbb{Z}}_{d}$ be any function. By
$A_{g,f}$ we denote the $d\times d$ matrix such that $A_{g,f}(x,y)\neq 0$ if
and only if $y=x+g(x)$ (addition is modulo $d$), in which case
$A_{g,f}(x,y)=\lambda_{1}^{f(x)}$. For instance,

$A_{1,x}=\left(\begin{array}[]{cccccc}0&1&0&0&\cdots&0\\\
0&0&\lambda_{1}&0&\cdots&0\\\ 0&0&0&\lambda_{1}^{2}&\cdots&0\\\
\vdots&\vdots&\vdots&\vdots&&\vdots\\\
\lambda_{1}^{d-1}&0&0&0&\cdots&0\end{array}\right).$

We remark that the solutions to the Mermin-Peres magic square constructed from
Pauli matrices

$\sigma_{x}=\left(\begin{array}[]{cc}0&1\\\
1&0\end{array}\right),\quad\sigma_{y}=\left(\begin{array}[]{cc}0&-i\\\
i&0\end{array}\right),\quad\sigma_{z}=\left(\begin{array}[]{cc}1&0\\\
0&-1\end{array}\right)$

fit into this framework: $I\otimes\sigma_{z}=A_{0,2x},\sigma_{z}\otimes
I=A_{0,x-x^{2}},\sigma_{z}\otimes\sigma_{z}=A_{0,3x-x^{2}},\sigma_{x}\otimes
I=A_{2,0},I\otimes\sigma_{x}=A_{2x+1,0},\sigma_{x}\otimes\sigma_{x}=A_{3+2x,0},-\sigma_{x}\otimes\sigma_{z}=A_{2,2x+2},-\sigma_{z}\otimes\sigma_{x}=A_{2x+1,x-x^{2}+2},-\sigma_{y}\otimes\sigma_{y}=A_{3+2x,3x-x^{2}}$,
respectively, assuming $\lambda_{1}=i$. Also, $A_{0,0}$ is the identity
matrix. In this section $g(x)$ is always a constant, and we use the notation
$A_{p,f}$ for $g(x)=p\in{\mathbb{Z}}_{d}$.

As is easily seen, multiplication of matrices $A_{p,f}$ satisfies the
following identity:

$A_{p_{1},f_{1}}\cdot
A_{p_{2},f_{2}}=A_{p_{1}+p_{2},f_{1}(x)+f_{2}(x+p_{1})}.$

Since every row of $A_{p,f}$ contains exactly one nonzero entry, the same is
true for any Kronecker product of such matrices. Therefore, a convenient way
to represent elements of a product

$A_{\overline{p},f}=A_{p_{1},f_{1}}\otimes\dots\otimes A_{p_{k},f_{k}},$

$f(x_{1},\ldots,x_{k})=f_{1}(x_{1})+\cdots+f_{k}(x_{k})$, is to specify the
only nonzero element in row $(x_{1},\ldots,x_{k})$. We denote this element
$A_{\overline{p},f}(x_{1},\ldots,x_{k})$. Note that this element is in the
column $(x_{1}+p_{1},\ldots,x_{k}+p_{k})$ and is equal to
$\lambda_{1}^{f(x_{1},\ldots,x_{k})}$.

Consider the following Kronecker products of $d+1$ matrices

$\displaystyle B_{\ell}$
$\displaystyle=A_{(0,\ldots,0,-1,0,\ldots,0),-x_{\ell}},$ $\displaystyle
C_{\ell}$ $\displaystyle=A_{(1,\ldots,1),x_{\ell}-1},$

where the nonzero entry for the matrix $B_{\ell}$ is in position $\ell$. The
magic square (or rather rectangle) for an odd $d>2$ is then constructed as
follows:

$M_{d}=\left(\begin{array}[]{cccc}(B_{1}\cdot C_{1})^{-1}&\cdots&(B_{d+1}\cdot
C_{d+1})^{-1}&B_{1}\cdot C_{1}\cdot\dots\cdot B_{d+1}\cdot C_{d+1}\\\
B_{1}&\cdots&B_{d+1}&(B_{1}\cdot\dots\cdot B_{d+1})^{-1}\\\
C_{1}&\cdots&C_{d+1}&(C_{1}\cdot\dots\cdot C_{d+1})^{-1}\end{array}\right)$

In Section 6 we prove that the matrices above satisfy the required properties
(cf. Proposition 14).

#### Unbounded width

The second direction of our main result is the following.

######  Theorem 5.

Let $\Gamma$ be a constraint language over $U_{d}$. If ${\rm CSP}(\Gamma)$
does not have bounded width then ${\rm CSP}(\Gamma)$ has a satisfiability gap.

The overall idea of proving Theorem 5 is to “implement” the “magic rectangle”
from above in ${\rm CSP}(\Gamma)$ provided ${\rm CSP}(\Gamma)$ does not have
bounded width. We achieve this in several steps via a chain of reductions that
lies at the heart of the algebraic approach to CSPs [12]. The reductions are
shown in Figure 2. They are known to preserve satisfiability; we show that
they also preserve satisfiability gaps.

The most basic reduction (used in the chain in several places) is that of
primitive positive definitions. Let $\Gamma$ be a constraint language over
$U_{d}$, let $r$ be an integer, and let $x_{1},\ldots,x_{r}$ be variables
ranging over the domain $U_{d}$. A primitive positive formula (_pp-formula_)
over $\Gamma$ is a formula of the form

$\phi(x_{1},\ldots,x_{r})=\exists y_{1}\cdots\exists y_{s}(R_{1}({\bf
z}_{1})\wedge\cdots\wedge R_{m}({\bf z}_{m})),$ (4)

where $R_{i}\in\Gamma$ is a relation over $U_{d}$ of arity $r_{i}$ and each
${\bf z}_{i}$ is an $r_{i}$-tuple of variables from
$\\{x_{1},\ldots,x_{r}\\}\cup\\{y_{1},\ldots,y_{s}\\}$. A relation $R\subseteq
U_{d}^{r}$ is primitive positive definable (_pp-definable_) from $\Gamma$ if
there exists a pp-formula $\phi(x_{1},\ldots,x_{r})$ over $\Gamma$ such that
$R$ is equal to the set of models of $\phi$, that is, the set of $r$-tuples
$(a_{1},\ldots,a_{r})\in U_{d}^{r}$ that make the formula $\phi$ true over
$U_{d}$ if $a_{i}$ is substituted for $x_{i}$ in $\phi$ for every $i\in[r]$.

${\rm CSP}(\Gamma)\ \leftrightarrow\ {\rm
CSP}(\mathsf{core}(\Gamma))\leftrightarrow\ {\rm
CSP}(\mathsf{core}(\Gamma)^{*})\ \leftarrow\ {\rm
CSP}(\mathsf{core}(\Gamma)^{*}\vrule
height=7.0pt,depth=3.0pt,width=0.4pt\lower 3.0pt\hbox{$\scriptstyle B$})\
\leftarrow\ {\rm CSP}(\mathsf{core}(\Gamma)^{*}\vrule
height=7.0pt,depth=3.0pt,width=0.4pt\lower 3.0pt\hbox{$\scriptstyle B$}/\lower
2.0pt\hbox{$\scriptstyle\theta$})$ Figure 2: Reductions between CSPs
corresponding to derivative languages.

######  Theorem 6.

Let $\Gamma$ be a constraint language over $U_{d}$ and let $R$ be pp-definable
from $\Gamma$. Then, if ${\rm CSP}(\Gamma\cup\\{R\\})$ has a satisfiability
gap then so does ${\rm CSP}(\Gamma)$.

Let $R\subseteq U_{d}^{r}$ be a pp-definable formula over $\Gamma$ via the pp-
formula $\phi(x_{1},\ldots,x_{r})$ as in (4). Given an instance
${\mathcal{P}}\in{\rm CSP}(\Gamma\cup\\{R\\})$, one can turn it into an
instance ${\mathcal{P}}^{\prime}\in{\rm CSP}(\Gamma)$ that is equivalent to
${\mathcal{P}}$. Intuitively, each constraint $\langle{\bf u},R\rangle$ of
${\mathcal{P}}$ is replaced with constraints from its pp-definition in (4)
over fresh new variables. This construction is known as the _gadget
construction_ in the CSP literature and it is known that ${\mathcal{P}}$ has a
solution over $U_{d}$ if and only if ${\mathcal{P}}^{\prime}$ has a solution
over $U_{d}$ [12, 5]. Thus, to prove Theorem 6, it suffices to show the
following lemma, whose proof is a simple generalization of the special case
for $d=2$ proved in [2].

######  Lemma 7.

Let $\Gamma$ be a constraint language over $U_{d}$ and let $R$ be pp-definable
from $\Gamma$. Furthermore, let ${\mathcal{P}}\in{\rm CSP}(\Gamma\cup\\{R\\})$
and let ${\mathcal{P}}^{\prime}\in{\rm CSP}(\Gamma)$ be the gadget
construction replacing constraints involving $R$ in ${\mathcal{P}}$. If there
is a satisfying operator assignment for ${\mathcal{P}}$ then there is a
satisfying operator assignment for ${\mathcal{P}}^{\prime}$.

If ${\rm CSP}(\Gamma\cup\\{R\\})$ has a satisfiability gap then there is an
unsatisfiable instance ${\mathcal{P}}\in{\rm CSP}(\Gamma\cup\\{R\\})$ with a
satisfying operator assignment. By [12] (cf. also [5]),
${\mathcal{P}}^{\prime}$ is unsatisfiable. By Lemma 7,
${\mathcal{P}}^{\prime}$ has a satisfying operator assignment. Hence
${\mathcal{P}}^{\prime}$ establishes that ${\rm CSP}(\Gamma)$ has a
satisfiability gap, and Theorem 6 is proved.

Pp-definitions are the starting point of the algebraic approach to CSPs [12]
and suffice for dealing with Boolean CSPs, not only in [2] but also in all
papers on Boolean (variants of) CSPs. For CSPs over larger domains, more tools
are needed.

A constraint language $\Gamma$ is a _core_ language if all its endomorphisms
are permutations; that is, $\Gamma$ has no endomorphisms that are not
automorphisms. There always exists an endomorphism $\varrho$ of $\Gamma$ such
that $\varrho(\Gamma)$ is core and $\varrho\circ\varrho=\varrho$ [12]. We will
denote this core language by $\mathsf{core}(\Gamma)$, as it (up to an
isomorphism) does not depend on the choice of $\varrho$.

A constraint language $\Gamma$ is called _idempotent_ if it contains all the
_constant_ relations, that is, relations of the form $C_{a}=\\{(a)\\}$, $a\in
U_{d}$. For an arbitrary language $\Gamma$ over $U_{d}$ we use
$\Gamma^{*}=\Gamma\cup\\{C_{a}\mid a\in U_{d}\\}$. A unary relation (a set)
$B\subseteq U_{d}$ pp-definable in $\Gamma$ is called a _subalgebra_ of
$\Gamma$. For a subalgebra $B$ we introduce the _restriction_ $\Gamma\vrule
height=7.0pt,depth=3.0pt,width=0.4pt\lower 3.0pt\hbox{$\scriptstyle B$}$ of
$\Gamma$ to $B$ defined as $\Gamma\vrule
height=7.0pt,depth=3.0pt,width=0.4pt\lower 3.0pt\hbox{$\scriptstyle
B$}=\\{R\cap B^{ar(R)}\mid R\in\Gamma\\}$.

An equivalence relation $\theta$ pp-definable in $\Gamma$ is said to be a
_congruence_ of $\Gamma$. The equivalence class of $\theta$ containing $a\in
U_{d}$ will be denoted by $a/\lower 2.0pt\hbox{$\scriptstyle\theta$}$, and the
set of all equivalence classes, the _factor-set_ , by $U_{d}/\lower
2.0pt\hbox{$\scriptstyle\theta$}$. Congruences of a constraint language allow
one to define a _factor-language_ as follows. For a congruence $\theta$ of the
language $\Gamma$ the factor language $\Gamma/\lower
2.0pt\hbox{$\scriptstyle\theta$}$ is the language over $U_{d}/\lower
2.0pt\hbox{$\scriptstyle\theta$}$ given by $\Gamma/\lower
2.0pt\hbox{$\scriptstyle\theta$}=\\{R/\lower
2.0pt\hbox{$\scriptstyle\theta$}\mid R\in\Gamma\\}$, where $R/\lower
2.0pt\hbox{$\scriptstyle\theta$}=\\{(a_{1}/\lower
2.0pt\hbox{$\scriptstyle\theta$},\ldots,a_{n}/\lower
2.0pt\hbox{$\scriptstyle\theta$})\mid(a_{1},\ldots,a_{n})\in R\\}$.

All the languages above are related to each other by the reducibility of the
corresponding CSPs, as Figure 2 indicates (cf. Proposition 20). In Section 8,
we show that all arrows in Figure 2 preserve satisfiability gaps. To relate
these reductions with bounded width and magic squares we use the following
result.

######  Proposition 8 ([11, 3, 5]).

For a constraint language $\Gamma$ over $U_{d}$, ${\rm CSP}(\Gamma)$ does not
have bounded width if and only there exists a language $\Delta$ pp-definable
in $\Gamma$, a subalgebra $B$ of $\mathsf{core}(\Delta)^{*}$, a congruence
$\theta$ of $\mathsf{core}(\Delta)^{*}\vrule
height=7.0pt,depth=3.0pt,width=0.4pt\lower 3.0pt\hbox{$\scriptstyle B$}$, and
an Abelian group ${\mathbb{A}}$ of prime order $p$ such that
$\mathsf{core}(\Delta)^{*}\vrule height=7.0pt,depth=3.0pt,width=0.4pt\lower
3.0pt\hbox{$\scriptstyle B$}/\lower 2.0pt\hbox{$\scriptstyle\theta$}$ contains
relations $R_{3,a},R_{p+2}$ for every $a\in{\mathbb{A}}$ given by
$R_{3,a}=\\{(x,y,z)\mid x+y+z=a\\}$ and $R_{p+2}=\\{(a_{1},\ldots,a_{p+2})\mid
a_{1}+\dots+a_{p+2}=0\\}$.666The relations $R_{3,a},R_{p+2}$ are chosen here
because they are needed for our purpose. In fact, they can be replaced with
any relations expressible by linear equations over ${\mathbb{A}}$.

To prove Theorem 5, suppose that ${\rm CSP}(\Gamma)$ does not have bounded
width. By Proposition 8 there is a language $\Delta$ pp-definable in $\Gamma$,
a subalgebra $B$ of $\mathsf{core}(\Delta)^{*}$, a congruence $\theta$ of
$\mathsf{core}(\Delta)^{*}\vrule height=7.0pt,depth=3.0pt,width=0.4pt\lower
3.0pt\hbox{$\scriptstyle B$}$, and an Abelian group ${\mathbb{A}}$ of prime
order $p$ such that $\mathsf{core}(\Delta)^{*}\vrule
height=7.0pt,depth=3.0pt,width=0.4pt\lower 3.0pt\hbox{$\scriptstyle B$}/\lower
2.0pt\hbox{$\scriptstyle\theta$}$ contains relations $R_{3,a},R_{p+2}$ for
every $a\in{\mathbb{A}}$. As reductions preserve satisfiability gaps, it
suffices to prove that ${\rm CSP}(\Delta_{p})$, where
$\Delta_{p}=\\{R_{3,a}\mid a\in{\mathbb{A}}\\}\cup\\{R_{p+2}\\}$, has a
satisfiability gap. For $p=2$ the Mermin-Peres magic square from [44] provides
a gap instance of ${\rm CSP}(\\{R_{3,1},R_{3,-1}\\})$, and our construction
above provides a gap instance for ${\rm CSP}(\Delta_{p})$ for all odd $p>2$.
Note that in both cases the group ${\mathbb{A}}$ is the multiplicative group
of roots of unity.

To give an idea of the gap-preservation proofs, we sketch how a satisfiability
gap is preserved from subalgebras. Let $\Gamma$ be a constraint language over
the set $U_{d}$ and let $B$ be its subalgebra. We show that if ${\rm
CSP}(\Gamma\vrule height=7.0pt,depth=3.0pt,width=0.4pt\lower
3.0pt\hbox{$\scriptstyle B$})$ has a satisfiability gap then so does ${\rm
CSP}(\Gamma)$.

Let $\Delta=\Gamma\vrule height=7.0pt,depth=3.0pt,width=0.4pt\lower
3.0pt\hbox{$\scriptstyle B$}$. Then by Theorem 6 we may assume
$\Delta\subseteq\Gamma$ and $B\in\Gamma$. Let $e=|B|$ and $\pi:U_{e}\to U_{d}$
a bijection between $U_{e}$ and $B$. Let
${\mathcal{P}}=(V,U_{e},{\mathcal{C}})$ be a gap instance of ${\rm
CSP}(\pi^{-1}(\Delta))$ and the instance
${\mathcal{P}}^{\pi}=(V,U_{d},{\mathcal{C}}^{\pi})$ constructed as follows:
For every $\langle{\bf s},R\rangle\in{\mathcal{C}}$ the instance
${\mathcal{P}}^{\pi}$ contains $\langle{\bf s},\pi(R)\rangle$. As is easily
seen, ${\mathcal{P}}^{\pi}$ has no classic solution. Therefore, it suffices to
show that for any satisfying operator assignment $\\{A_{v}\mid v\in V\\}$ for
${\mathcal{P}}$, the assignment $C_{v}=\pi(A_{v})$ is a satisfying operator
assignment for ${\mathcal{P}}^{\pi}$.

By a technical lemma that shows that injective maps on finite sets that are
interpolated by polynomials preserve normal operators that pairwise commute
(cf. Lemma 22), the $C_{v}$’s are normal, satisfy the condition $C_{v}^{d}=I$,
and locally commute. For $\langle{\bf s},R\rangle\in{\mathcal{C}}$, ${\bf
s}=(v_{1},\ldots,v_{k})$, let
$f^{\pi}_{R}(x_{1},\ldots,x_{k})=f_{R}(\pi^{-1}(x_{1}),\ldots,\pi^{-1}(x_{k}))$.
It can be shown that $\pi^{-1}(C_{v})=A_{v}$, and therefore
$f^{\pi}_{R}(C_{v_{1}},\ldots,C_{v_{k}})=I$. For any $a_{1},\ldots,a_{k}\in
U_{d}$, if $(a_{1},\ldots,a_{k})\in\pi(R)$ then $a_{1},\ldots,a_{k}\in B$.
Therefore, $f^{\pi}_{R}(a_{1},\ldots,a_{k})=1$ then
$f_{\pi(R)}(a_{1},\ldots,a_{k})=1$. By Lemma 2 this implies
$f_{\pi(R)}(C_{v_{1}},\ldots,C_{v_{k}})=I$.

The other reductions use similar ideas, carefully relying on the spectral
theorem given in Theorem 1 to simultaneously diagonalize the restriction of an
operator assignment to the scope of a constraint, Lemma 2 that relates
polynomial equations over $U_{d}$ and operators, and the above mentioned
result on preservation of operator assignments by certain polynomials (Lemma
22).

##  5 Bounded width and no gaps

In this section we prove the first direction of our main result.

######  Theorem 9.

Let $\Gamma$ be a constraint language over $U_{d}$. If ${\rm CSP}(\Gamma)$ has
bounded width then it has no satisfiability gap.

The main idea behind the proof of Theorem 9 is to simulate the inference
provided by SLAC by inference in polynomial equations. Let ${\mathcal{S}}$ be
a SLAC-program solving ${\rm CSP}(\Gamma)$. In order to prove Theorem 9 we
take an instance ${\mathcal{P}}=(V,U_{d},{\mathcal{C}})$ of ${\rm
CSP}(\Gamma)$ that is not SLAC-consistent, and therefore has no solution, as
${\rm CSP}(\Gamma)$ has bounded width, and prove that it also has no
satisfying operator assignment. We will prove it by contradiction, assuming
${\mathcal{P}}$ has a satisfying operator assignment $\\{A_{v}\\}$ and then
using the rules of a SLAC-program solving ${\rm CSP}(\Gamma)$ to infer
stronger and stronger conditions on $\\{A_{v}\\}$ that eventually lead to a
contradiction. We start with a series of lemmas that will help to express the
restrictions on $\\{A_{v}\\}$.

The following lemma introduces a restriction that is satisfied by any operator
assignment.

######  Lemma 10.

Let ${\mathcal{P}}=(V,U_{d},{\mathcal{C}})\in{\rm CSP}(\Gamma)$. For any
operator assignment $\\{A_{v}\\}$ for ${\mathcal{P}}$ we have

$\prod_{k=0}^{d-1}(\lambda_{k}I-A_{v})=0.$

###### Proof.

Note that the equation $\prod_{k=0}^{d-1}(\lambda_{k}-x)=0$ is true for any
$x\in U_{d}$, that is, it follows from the empty set of equations. By Lemma 2,
it also holds for any fully commuting operator assignment. However, as the
equation contains only one variable any operator assignment is fully
commuting, and the result follows. ∎

Recall that every rule of a SLAC-program has the form $(x\in S)\wedge
R(x,y,z_{1},\ldots,z_{r}))\to(y\in S^{\prime})$ for some variables $x,y\in V$,
a constraint $\langle(x,y,z_{1},\ldots,z_{r}),R\rangle$, and sets
$S,S^{\prime}\subseteq U_{d}$. Therefore, we need to show how to encode unary
relations and rules of a SLAC-program through polynomials. For any $S\subseteq
U_{d}$, we represent the unary constraint restricting the domain of a variable
$x$ to the set $S$ by the polynomial

$Dom_{S}(x)=\prod_{k\in S}(\lambda_{k}-x)+1.$

Similarly, the rule $(x\in S)\wedge R(x,y,z_{1},\ldots,z_{r}))\to(y\in
S^{\prime})$ of the SLAC program is represented by

$Rule_{S,R,S^{\prime}}(x,y,z_{1},\ldots,z_{r})=(Dom_{\overline{S}}(x)-1)(P_{R}(x,y,z_{1},\ldots,z_{r})-\lambda_{1})(Dom_{S^{\prime}}(y)-1).$

As the next lemma shows, any operator assignment is a zero of
$Rule_{S,R,S^{\prime}}$.

######  Lemma 11.

Let ${\mathcal{P}}=(V,U_{d},{\mathcal{C}})\in{\rm CSP}(\Gamma)$. For any
operator assignment $\\{A_{v}\\}$ for ${\mathcal{P}}$ and any rule $(x\in
S)\wedge R(x,y,z_{1},\ldots,z_{r}))\to(y\in S^{\prime})$ of the SLAC program
for ${\rm CSP}(\Gamma)$ we have

$\displaystyle Rule_{S,R,S^{\prime}}(A_{x},A_{y},A_{z_{1}},\ldots,A_{z_{r}})$
$\displaystyle=$
$\displaystyle(Dom_{\overline{S}}(A_{x})-I)(P_{R}(A_{x},A_{y},A_{z_{1}},\ldots,A_{z_{r}})-\lambda_{1}I)(Dom_{S^{\prime}}(A_{y})-I)=0.$

###### Proof.

Note that the equation $Rule_{S,R,S^{\prime}}(x,y,z_{1},\ldots,z_{r})=0$ is
true for any $x,y,z_{1},\ldots,z_{r}\in U_{d}$, that is, it follows from the
empty set of equations. By Lemma 2, it also holds for any fully commuting
operator assignment. However, as all the variables $x,y,z_{1},\ldots,z_{r}$
belong to the scope of the same constraint, the operators
$A_{x},A_{y},A_{z_{1}},\ldots,A_{z_{r}}$ pairwise commute. The result follows.
∎

Now, assume ${\mathcal{P}}=(V,U_{d},{\mathcal{C}})$ is not SLAC-consistent and
$D_{v}$ denote the domain of $v\in V$ obtained after establishing SLAC-
consistency. This means that for some $v\in V$ there is a derivation of
$D_{v}=\mathchar 3391\relax$ using only facts $R({\bf s})$ for $\langle{\bf
s},R\rangle\in{\mathcal{C}}$ and $T_{B}(x_{i})\wedge R(x_{1},\ldots,x_{k})\to
T_{C}(x_{j})$ for the rules of the SLAC-program. Moreover, this derivation can
be subdivided into sections of the form $(v=a)\to(v\neq a)$, each of which is
linear. The latter condition means that each such section looks like a chain
$(v=a)\to(v_{1}\in S_{1})\to\dots\to(v_{\ell}\in S_{\ell})\to(v\in
D_{v}-\\{a\\})$, where each step is by a rule of the form $((v_{i}\in
S_{i})\wedge R_{i}(v_{i},v_{i+1},u_{1},\ldots,u_{r}))\to(v_{i+1}\in S_{i+1})$.

######  Lemma 12.

For any satisfying operator assignment $\\{A_{v}\\}$ for ${\mathcal{P}}$ and
any rule $(x\in S)\wedge R(x,y,z_{1},\ldots,z_{r}))\to(y\in S^{\prime})$ of
the SLAC program for ${\rm CSP}(\Gamma)$ if
$R(x,y,z_{1},\ldots,z_{r})\in{\mathcal{C}}$ then

$(Dom_{\overline{S}}(A_{x})-I)(Dom_{S^{\prime}}(A_{y})-I)=I.$

###### Proof.

By Lemma 11, the equation

$(Dom_{\overline{S}}(A_{x})-I)(P_{R}(A_{x},A_{y},A_{z_{1}},\ldots,A_{z_{r}})-\lambda_{1}I)(Dom_{S^{\prime}}(A_{y})-I)=0$

holds as well as the equation

$P_{R}(A_{x},A_{y},A_{z_{1}},\ldots,A_{z_{r}})-I=0.$

Multiplying the latter one by $(Dom_{\overline{S}}(A_{x})-I)$ on the left, and
by $(Dom_{S^{\prime}}(A_{y})-I)$ on the right and subtracting it from the
first equation we obtain

$-(Dom_{\overline{S}}(A_{x})-I)(1-\lambda_{1})I(Dom_{S^{\prime}}(A_{y})-I)=0.$

The result follows. ∎

######  Lemma 13.

Let $(v_{1}\in S_{1})\to\dots\to(v_{\ell}\in S_{\ell})$ be a derivation in the
SLAC-program ${\mathcal{S}}$ and $\\{A_{v}\\}$ a satisfying operator
assignment for ${\mathcal{P}}$. Then for each $i=2,\ldots,\ell$

$(Dom_{\overline{S}_{1}}(A_{v_{1}})-I)(Dom_{S_{i}}(A_{v_{i}})-I)=0.$

###### Proof.

We proceed by induction on $i$. For $i=2$ the equation holds by Lemma 12. In
the induction case we have equations

$(Dom_{\overline{S}_{1}}(A_{v_{1}})-I)(Dom_{S_{i}}(A_{v_{i}})-I)=0,$ (5)

and

$(Dom_{\overline{S}_{i}}(A_{v_{i}})-I)(Dom_{S_{i+1}}(A_{v_{i+1}})-I)=0.$ (6)

The idea is to multiply (5) by $(Dom_{S_{i+1}}(A_{v_{i+1}})-I)$ on the right,
multiply (6) by $(Dom_{\overline{S}_{1}}(A_{v_{1}})-I)$ on the left and
subtract. The problem is, however, that

$Dom_{S_{i}}(A_{v_{i}})-Dom_{\overline{S}_{i}}(A_{v_{i}})$

is not a constant polynomial. So, we also need to prove that any polynomial of
the form

$Dom_{S}(x)-Dom_{\overline{S}}(x)$

is invertible modulo $x^{d}-1$. The polynomial has the form

$p(x)=\prod_{k\in S}(x-\lambda_{k})-\prod_{k\not\in S}(x-\lambda_{k}).$

As is easily seen, assuming that the product of an empty set of factors equals
1, $\lambda_{k}$ is not a root of $p(x)$ for any $\lambda_{k}\in U_{d}$.
Therefore the greatest common divisor of $p(x)$ and $x^{d}-1$ has degree 0,
and hence there exists $q(x)$ such that

$p(x)q(x)=c+r(x)(x^{d}-1).$

Thus before subtracting equations (5) and (6) we also multiply them by
$q(A_{v_{i}})$. Then we get

$\displaystyle(Dom_{\overline{S}_{1}}(A_{v_{1}})-I)(Dom_{S_{i}}(A_{v_{i}})q(A_{v_{i}})-q(A_{v_{i}})Dom_{\overline{S}_{i}}(A_{v_{i}}))(Dom_{S_{i+1}}(A_{v_{i+1}})-I)$
$\displaystyle=$ $\displaystyle 0$
$\displaystyle(Dom_{\overline{S}_{1}}(A_{v_{1}})-I)q(A_{v_{i}})(Dom_{S_{i}}(A_{v_{i}})-Dom_{\overline{S}_{i}}(A_{v_{i}}))(Dom_{S_{i+1}}(A_{v_{i+1}})-I)$
$\displaystyle=$ $\displaystyle 0$ $\displaystyle
c(Dom_{\overline{S}_{1}}(A_{v_{1}})-I)(Dom_{S_{i+1}}(A_{v_{i+1}})-I)$
$\displaystyle=$ $\displaystyle 0.$

The first transformation uses the fact that $A_{v_{i}}$ commutes with itself,
while the second one uses the property $A_{v_{i}}^{d}=I$. The result follows.
∎

###### Proof of Theorem 9.

To complete the proof of Theorem 9 note that the lack of SLAC-consistency
means that for some $v\in V$ the statement
$(v=\lambda_{k})\to(v\neq\lambda_{k})$ can be derived from ${\mathcal{P}}$ for
every $\lambda_{k}\in U_{d}$. By Lemma 13, for any operator assignment
$\\{A_{w}\\}$ and any $\lambda_{k}\in U_{d}$ the operator $A_{v}$ satisfies
the equation

$\prod_{j\neq k}(A_{v}-\lambda_{j}I)=0.$

We show that for any $S\subseteq U_{d}$ these equations imply

$\prod_{j\in S}(A_{v}-\lambda_{j}I)=0.$

Then for $S=\mathchar 3391\relax$ we get $I=0$, witnessing that
${\mathcal{P}}$ has no satisfying operator assignment.

We proceed by (reverse) induction on the size of $S$. Suppose the statement is
true for all sets of size $r$ and let $S\subseteq U_{d}$ be such that
$|S|=r-1$. Without loss fo generality, assume that
$S=\\{\lambda_{0},\ldots,\lambda_{r-1}\\}$. Let
$S_{1}=S\cup\\{\lambda_{r}\\},S_{2}=S\cup\\{\lambda_{r+1}\\}$. Consider

$\prod_{j\in S_{1}}(A_{v}-\lambda_{j}I)=0$ (7)

and

$\prod_{j\in S_{2}}(A_{v}-\lambda_{j}I)=0.$ (8)

Subtracting (8) from (7) we obtain

$(A_{v}-\lambda_{r}I-A_{v}+\lambda_{r+1}I)\prod_{j=0}^{r-1}(A_{v}-\lambda_{j}I)=(\lambda_{r+1}-\lambda_{r})I\prod_{j=0}^{r-1}(A_{v}-\lambda_{j}I)=0,$

implying the equation for $S$. ∎

##  6 Magic square modulo $d$

Here we construct a CSP that is not satisfied over $U_{d}$ but is satisfied
over normal operators of order $d$. The construction is similar to the Mermin-
Peres magic square [44, 45, 48].

Let let $g,f:{\mathbb{Z}}_{d}\to{\mathbb{Z}}_{d}$ be any function. By
$A_{g,f}$ we denote the $d\times d$ matrix such that $A_{g,f}(x,y)\neq 0$ if
and only if $y=x+g(x)$ (addition is modulo $d$), in which case
$A_{g,f}(x,y)=\lambda_{1}^{f(x)}$. For instance,

$A_{1,x}=\left(\begin{array}[]{cccccc}0&1&0&0&\cdots&0\\\
0&0&\lambda_{1}&0&\cdots&0\\\ 0&0&0&\lambda_{1}^{2}&\cdots&0\\\
\vdots&\vdots&\vdots&\vdots&&\vdots\\\
\lambda_{1}^{d-1}&0&0&0&\cdots&0\end{array}\right).$

We remark that the solutions to the Mermin-Peres magic square constructed from
Pauli matrices

$\sigma_{x}=\left(\begin{array}[]{cc}0&1\\\
1&0\end{array}\right),\quad\sigma_{y}=\left(\begin{array}[]{cc}0&-i\\\
i&0\end{array}\right),\quad\sigma_{z}=\left(\begin{array}[]{cc}1&0\\\
0&-1\end{array}\right)$

fit into this framework: $I\otimes\sigma_{z}=A_{0,2x},\sigma_{z}\otimes
I=A_{0,x-x^{2}},\sigma_{z}\otimes\sigma_{z}=A_{0,3x-x^{2}},\sigma_{x}\otimes
I=A_{2,0},I\otimes\sigma_{x}=A_{2x+1,0},\sigma_{x}\otimes\sigma_{x}=A_{3+2x,0},-\sigma_{x}\otimes\sigma_{z}=A_{2,2x+2},-\sigma_{z}\otimes\sigma_{x}=A_{2x+1,x-x^{2}+2},-\sigma_{y}\otimes\sigma_{y}=A_{3+2x,3x-x^{2}}$,
respectively, assuming $\lambda_{1}=i$. Also, $A_{0,0}$ is the identity
matrix. In this section $g(x)$ is always a constant, and we use the notation
$A_{p,f}$ for $g(x)=p\in{\mathbb{Z}}_{d}$.

As is easily seen, multiplication of matrices $A_{p,f}$ satisfies the
following identity:

$A_{p_{1},f_{1}}\cdot
A_{p_{2},f_{2}}=A_{p_{1}+p_{2},f_{1}(x)+f_{2}(x+p_{1})}.$ (9)

Indeed, for $x\in[d]$ the only nonzero element of the $x$-th row of
$C=A_{p_{1},f_{1}}\cdot A_{p_{2},f_{2}}$ is the element

$A_{p_{1},f_{1}}(x,x+p_{1})\cdot
A_{p_{2},f_{2}}(x+p_{1},x+p_{1}+p_{2})=\lambda^{f_{1}(x)}\cdot\lambda^{f_{2}(x+p_{1})}=\lambda^{f_{1}(x)+f_{2}(x+p_{1})}.$

We will also use the mixed-product rule for Kronecker product $\otimes$.

$(A\otimes B)\cdot(C\otimes D)=(A\cdot C)\otimes(B\cdot D).$

Since every row of $A_{p,f}$ contains exactly one nonzero entry, the same is
true for any Kronecker product of such matrices. Therefore, a convenient way
to represent elements of a product

$A_{\overline{p},f}=A_{p_{1},f_{1}}\otimes\dots\otimes A_{p_{k},f_{k}},$

$f(x_{1},\ldots,x_{k})=f_{1}(x_{1})+\cdots+f_{k}(x_{k})$, is to specify the
only nonzero element in row $(x_{1},\ldots,x_{k})$. We denote this element
$A_{\overline{p},f}(x_{1},\ldots,x_{k})$. Note that this element is in the
column $(x_{1}+p_{1},\ldots,x_{k}+p_{k})$ and is equal to
$\lambda^{f(x_{1},\ldots,x_{k})}$.

Consider the following Kronecker products of $d+1$ matrices

$\displaystyle B_{\ell}$
$\displaystyle=A_{(0,\ldots,0,-1,0,\ldots,0),-x_{\ell}},$ $\displaystyle
C_{\ell}$ $\displaystyle=A_{(1,\ldots,1),x_{\ell}-1},$

where the nonzero entry for the matrix $B_{\ell}$ is in position $\ell$. The
magic square (or rather rectangle) for an odd $d>2$ is then constructed as
follows:

$M_{d}=\left(\begin{array}[]{cccc}(B_{1}\cdot C_{1})^{-1}&\cdots&(B_{d+1}\cdot
C_{d+1})^{-1}&B_{1}\cdot C_{1}\cdot\dots\cdot B_{d+1}\cdot C_{d+1}\\\
B_{1}&\cdots&B_{d+1}&(B_{1}\cdot\dots\cdot B_{d+1})^{-1}\\\
C_{1}&\cdots&C_{d+1}&(C_{1}\cdot\dots\cdot C_{d+1})^{-1}\end{array}\right)$

We now prove that the matrices above satisfy the required properties.

######  Proposition 14.

If $d$ is odd then for the entries of the matrix $M_{d}$ it holds that

  * (a)

every entry $D$ of $M_{d}$ is normal and satisfies $D^{d}=I$;

  * (b)

the matrices in each row and each column of $M_{d}$ commute;

  * (c)

the product of the matrices in every row and every column of $M_{d}$ except
for the last column is the identity matrix;

  * (d)

the product of matrices in the last column of $M_{d}$ is a scalar matrix, but
not the identity matrix.

###### Proof.

We start with (b) for matrices $B_{\ell},C_{\ell}$, which will also allow us
to find the remaining matrices. By the mixed product rule and because
$A_{0,0}=I$, in order to verify $B_{\ell}\cdot C_{\ell}=C_{\ell}\cdot
B_{\ell}$ it suffices to show that

$A_{-1,-x}\cdot A_{1,x-1}=A_{0,x-1-(x+1)}=A_{0,-2}=A_{1,x-1}\cdot A_{-1,-x}.$

This also implies

$B_{\ell}\cdot C_{\ell}=A_{(1,\ldots,1,0,1,\ldots,1),-2}\quad\text{and}\quad
D_{\ell}=(B_{\ell}\cdot C_{\ell})^{-1}=A_{(-1,\ldots,-1,0,-1,\ldots,-1),2}.$

For $B_{\ell}\cdot B_{j}$ and $C_{\ell}\cdot C_{j}$, $\ell\neq j$, we have

$\displaystyle B_{\ell}\cdot B_{j}(x_{1},\ldots,x_{d})$ $\displaystyle=$
$\displaystyle
B_{\ell}(x_{1},\ldots,x_{d})B_{j}(x_{1},\ldots,x_{\ell-1},x_{\ell}-1,x_{\ell+1},\ldots,x_{d})$
$\displaystyle=$ $\displaystyle\lambda^{-x_{\ell}-x_{j}},$ $\displaystyle=$
$\displaystyle
B_{j}(x_{1},\ldots,x_{d})B_{\ell}(x_{1},\ldots,x_{j-1},x_{j}-1,x_{j+1},\ldots,x_{d})$
$\displaystyle=$ $\displaystyle B_{j}\cdot B_{\ell}(x_{1},\ldots,x_{d+1});$
$\displaystyle C_{\ell}\cdot C_{j}(x_{1},\ldots,x_{d})$ $\displaystyle=$
$\displaystyle C_{\ell}(x_{1},\ldots,x_{d})C_{j}(x_{1}+1,\ldots,x_{d}+1)$
$\displaystyle=$ $\displaystyle\lambda^{x_{\ell}-1+(x_{j}+1)-1},$
$\displaystyle=$ $\displaystyle\lambda^{x_{j}-1+(x_{\ell}+1)-1},$
$\displaystyle=$ $\displaystyle C_{j}\cdot C_{\ell}(x_{1},\ldots,x_{d}).$

This also implies that

$B_{\ell}\cdot
B_{j}=A_{(0,\ldots,0,-1,0,\ldots,0,-1,0,\ldots,0),-x_{\ell}-x_{j}},\quad
C_{\ell}\cdot C_{j}=A_{(2,\ldots,2),x_{\ell}+x_{j}-1}.$

Therefore,

$\displaystyle B_{1}\cdot\ldots\cdot B_{d+1}$
$\displaystyle=A_{(-1,\ldots,-1),-(x_{1}+\dots+x_{d+1})}$ $\displaystyle
C_{1}\cdot\ldots\cdot C_{d+1}$
$\displaystyle=A_{(d+1,\ldots,d+1),x_{1}-1+(x_{2}+1)-1+\dots+(x_{d+1}+d)-1}$
$\displaystyle=A_{(d+1,\ldots,d+1),x_{1}+x_{2}+\dots+x_{d+1}-1+\frac{d(d+1)}{2}}$
$\displaystyle=A_{(1,\ldots,1),x_{1}+x_{2}+\dots+x_{d+1}-1},$

which implies

$\displaystyle F=(B_{1}\cdot\ldots\cdot B_{d+1})^{-1}$
$\displaystyle=A_{(1,\ldots,1),(x_{1}+\dots+x_{d+1})+1}$ $\displaystyle
G=(C_{1}\cdot\ldots\cdot C_{d+1})^{-1}$
$\displaystyle=A_{(-1,\ldots,-1),-(x_{1}+x_{2}+\dots+x_{d+1})}.$

Finally,

$\displaystyle E=B_{1}\cdot C_{1}\cdot\ldots\cdot B_{d+1}\cdot C_{d+1}$
$\displaystyle=A_{(0,1,\ldots,1),-2}\cdot\ldots\cdot A_{(1,\ldots,1,0),-2}$
$\displaystyle=A_{(d,\ldots,d),-2(d+1)}$ $\displaystyle=A_{(0,\ldots,0),-2}.$

(a) By Fuglede’s theorem if two normal operators commute, their product is
normal. By what is proved above it suffices to show that $B_{\ell},C_{\ell}$
are normal. Indeed, the only case that does not follows from this is the
matrix $E$, but this matrix is diagonal. Then by the mixed-product rule and
the equalities $(A^{*})^{-1}=(A^{-1})^{*}$, $(A\otimes B)^{*}=A^{*}\otimes
B^{*}$ it suffices to check that matrices $A_{0,0},A_{-1,-x},A_{1,x-1}$ are
normal. Note first that $(A_{p,f})^{*}=A_{-p,-f}$. Then we have that $A_{0,0}$
is the identity matrix,

$\displaystyle A_{-1,-x}\cdot(A_{-1,-x})^{*}$ $\displaystyle=A_{-1,-x}\cdot
A_{1,x}=A_{0,-x+x-1}=A_{0,-1}$ $\displaystyle=A_{0,x-(x+1)}=A_{1,x}\cdot
A_{-1,-x}=(A_{-1,-x})^{*}\cdot A_{-1,-x};$ $\displaystyle
A_{1,x-1}\cdot(A_{1,x-1})^{*}$ $\displaystyle=A_{1,x-1}\cdot
A_{-1,-x+1}=A_{0,x-1+(-(x+1)+1)}=A_{0,-1}$
$\displaystyle=A_{0,-x+1+((x-1)-1)}=A_{-1,-x+1}\cdot
A_{1,x-1}=(A_{1,x-1})^{*}\cdot A_{1,x-1}.$

Next, we need to find
$B^{d}_{\ell},C^{d}_{\ell},D_{\ell}^{d},E^{d},F^{d},G^{d}$:

$\displaystyle B_{\ell}^{d}$
$\displaystyle=(A_{(0,\ldots,,0,-1,0,\ldots,0),-x_{\ell}})^{d}$
$\displaystyle=A_{(0,\ldots,0),-x_{\ell}+(-x_{\ell}-1)+\dots+(-x_{\ell}-(d-1))}$
$\displaystyle=A_{(0,\ldots,0),-\frac{(d-1)d}{2}}$
$\displaystyle=A_{(0,\ldots,0),0};$ $\displaystyle C_{i}^{d}$
$\displaystyle=(A_{(1,\ldots,1),x_{\ell}})^{d}$
$\displaystyle=A_{(0,\ldots,0),x_{\ell}+(x_{\ell}+1)+\dots+(x_{\ell}+(d-1))}$
$\displaystyle=A_{(0,\ldots,0),\frac{(d-1)d}{2}}$
$\displaystyle=A_{(0,\ldots,0),0};$ $\displaystyle D_{i}^{d}$
$\displaystyle=(A_{(-1,\ldots,-1,0,-1,\ldots,-1),2})^{d}=A_{(0,\ldots,0),0};$
$\displaystyle E^{d}$
$\displaystyle=(A_{(0,\ldots,0),-2})^{d}=A_{(0,\ldots,0),0}.$

Since $B_{\ell},B_{j}$ commute, as do $C_{i},C_{j}$, we have

$\displaystyle F^{d}$ $\displaystyle=(B_{1}\cdot\ldots\cdot
B_{d+1})^{-d}=B_{1}^{-d}\cdot\ldots\cdot B_{d+1}^{-d}=A_{(0,\ldots,0),0};$
$\displaystyle G^{d}$ $\displaystyle=(C_{1}\cdot\ldots\cdot
C_{d+1})^{-d}=C_{1}^{-d}\cdot\ldots\cdot C_{d+1}^{-d}=A_{(0,\ldots,0),0}.$

(b) We have verified that $B_{i},C_{i}$ commute, and so do $B_{i},B_{j}$, and
$C_{i},C_{j}$. This means that $D_{i}$ commutes with $B_{i},C_{i}$, and also
$F$ commutes with each of $B_{1},\ldots,B_{d+1}$, and $G$ commutes with each
of $C_{1},\ldots,C_{d+1}$. Matrices $D_{i}$ and $E$ are scalar, so they
commute with each other, and $E$ commutes with $F,G$. It remains to verify
that $F,G$ commute, as well. We have

$\displaystyle F\cdot G$
$\displaystyle=A_{(1,\ldots,1),(x_{1}+\dots+x_{d+1})+1}\cdot
A_{(-1,\ldots,-1),-(x_{1}+x_{2}+\dots+x_{d+1})}$
$\displaystyle=A_{(0,\ldots,0),(x_{1}+\dots+x_{d+1})+1-((x_{1}+1)+(x_{2}+1)+\dots+(x_{d+1}+1))}$
$\displaystyle=A_{(0,\ldots,0),-(d+1)+1}$ $\displaystyle=A_{(0,\ldots,0),0}.$

On the other hand,

$\displaystyle G\cdot F$
$\displaystyle=A_{(-1,\ldots,-1),-(x_{1}+\dots+x_{d+1})}\cdot
A_{(1,\ldots,1),(x_{1}+x_{2}+\dots+x_{d+1})+1}$
$\displaystyle=A_{(0,\ldots,0),-(x_{1}+\dots+x_{d+1})+((x_{1}-1)+(x_{2}-1)+\dots+(x_{d+1}-1))+1}$
$\displaystyle=A_{(0,\ldots,0),1-(d+1)}$ $\displaystyle=A_{(0,\ldots,0),0}.$

(c) follows from the construction.

(d) By (b) we have that

$E\cdot F\cdot G=A_{(0,\ldots,0),-2}\cdot
A_{(0,\ldots,0),0}=A_{(0,\ldots,0),-2},$

as required. ∎

##  7 Reductions through pp-definitions

In this section we prove that the so-called primitive positive definitions, a
key tool in the algebraic approach to CSPs [12], not only give rise to
(polynomial-time) reductions that preserve satisfiability over $U_{d}$ but
also preserve satisfiability over operators. This was established for the
special case of Boolean domains (i.e., for $d=2$) in [2] and the same idea
works for larger domains. We will need this result later in Section 8 to prove
that CSPs of unbounded width admit a satisfiability gap.

Let $\Gamma$ be a constraint language over $U_{d}$, let $r$ be an integer, and
let $x_{1},\ldots,x_{r}$ be variables ranging over the domain $U_{d}$. A
primitive positive formula (_pp-formula_) over $\Gamma$ is a formula of the
form

$\phi(x_{1},\ldots,x_{r})=\exists y_{1}\cdots\exists y_{s}(R_{1}({\bf
z}_{1})\wedge\cdots\wedge R_{m}({\bf z}_{m})),$ (10)

where $R_{i}\in\Gamma$ is a relation over $U_{d}$ of arity $r_{i}$ and each
${\bf z}_{i}$ is an $r_{i}$-tuple of variables from
$\\{x_{1},\ldots,x_{r}\\}\cup\\{y_{1},\ldots,y_{s}\\}$. A relation $R\subseteq
U_{d}^{r}$ is primitive positive definable (_pp-definable_) from $\Gamma$ if
there exists a pp-formula $\phi(x_{1},\ldots,x_{r})$ over $\Gamma$ such that
$R$ is equal to the set of models of $\phi$, that is, the set of $r$-tuples
$(a_{1},\ldots,a_{r})\in U_{d}^{r}$ that make the formula $\phi$ true over
$U_{d}$ if $a_{i}$ is substituted for $x_{i}$ in $\phi$ for every $i\in[r]$.

Our goal in this section is to prove the following result.

######  Theorem 15.

Let $\Gamma$ be a constraint language over $U_{d}$ and let $R$ be pp-definable
from $\Gamma$. Then, if ${\rm CSP}(\Gamma\cup\\{R\\})$ has a satisfiability
gap then so does ${\rm CSP}(\Gamma)$.

Let $R\subseteq U_{d}^{r}$ be a pp-definable formula over $\Gamma$ via the pp-
formula $\phi(x_{1},\ldots,x_{r})$ as in (10). Given an instance
${\mathcal{P}}\in{\rm CSP}(\Gamma\cup\\{R\\})$ we describe a construction of
an instance ${\mathcal{P}}^{\prime}\in{\rm CSP}(\Gamma)$ that is, in some
sense, equivalent to ${\mathcal{P}}$. We start with the instance
${\mathcal{P}}$. For every constraint $\langle{\bf u},R\rangle$ of
${\mathcal{P}}$ with ${\bf u}=(u_{1},\ldots,u_{r})$, we introduce $s$ fresh
new variables $t_{1},\ldots,t_{s}$ for the quantified variables in (10);
furthermore, we replace $\langle{\bf u},R\rangle$ by $m$ constraints
$\langle{\bf w}_{i},R_{i}\rangle$, $i\in[m]$, where ${\bf w}_{i}$ is the tuple
of variables obtained from ${\bf z}_{i}$ in (10) by replacing $x_{j}$ by
$u_{j}$, $j\in[r]$, and by replacing $y_{j}$ by $t_{j}$, $j\in[s]$. The
collection of variables $u_{1},\ldots,u_{r},t_{1},\ldots,t_{s}$ is called the
_block_ of the constraint $\langle{\bf u},R\rangle$ in
${\mathcal{P}}^{\prime}$. This construction is known as the _gadget
construction_ in the CSP literature and it is known that ${\mathcal{P}}$ has a
solution over $U_{d}$ if and only if ${\mathcal{P}}^{\prime}$ has a solution
over $U_{d}$ [12, 5]. Thus, in order to prove Theorem 15, it suffices to show
the following lemma.

######  Lemma 16.

Let $\Gamma$ be a constraint language over $U_{d}$ and let $R$ be pp-definable
from $\Gamma$. Furthermore, let ${\mathcal{P}}\in{\rm CSP}(\Gamma\cup\\{R\\})$
and let ${\mathcal{P}}^{\prime}\in{\rm CSP}(\Gamma)$ be the gadget
construction replacing constraints involving $R$ in ${\mathcal{P}}$. If there
is a satisfying operator assignment for ${\mathcal{P}}$ then there is a
satisfying operator assignment for ${\mathcal{P}}^{\prime}$.

Indeed, if ${\rm CSP}(\Gamma\cup\\{R\\})$ has a satisfiability gap then there
is an unsatisfiable instance ${\mathcal{P}}\in{\rm CSP}(\Gamma\cup\\{R\\})$
that has a satisfying operator assignment. By the results in [12] (cf. also
[5]), ${\mathcal{P}}^{\prime}$ is unsatisfiable. By Lemma 16,
${\mathcal{P}}^{\prime}$ has a satisfying operator assignment. Hence
${\mathcal{P}}^{\prime}$ establishes that ${\rm CSP}(\Gamma)$ has a
satisfiability gap, as required to prove Theorem 15.

We will frequently use (below and also in Section 8) the following
observations. We give a proof of them for the sake of completeness.

######  Lemma 17.

Let $f$ be a polynomial and $A,B$ operators in a finite-dimensional Hilbert
space.
(1) If $A,B$ commute, then so do $f(A),f(B)$.
(2) If $A$ is normal, then so is $f(A)$.
(3) If $U$ is a unitary operator, then $Uf(A)U^{-1}=f(UAU^{-1})$.

###### Proof.

Let $f(x)=\sum_{i=0}^{k}\alpha_{i}x^{i}$.
(1) We have

$\displaystyle f(A)f(B)$
$\displaystyle=\left(\sum_{i=0}^{k}\alpha_{i}A^{i}\right)\left(\sum_{i=0}^{k}\alpha_{i}B^{i}\right)=\sum_{i,j=0}^{k}\alpha_{i}\alpha_{j}A^{i}B^{j}$
$\displaystyle=\sum_{i,j=0}^{k}\alpha_{j}\alpha_{i}B^{j}A^{i}=\left(\sum_{i=0}^{k}\alpha_{i}B^{i}\right)\left(\sum_{i=0}^{k}\alpha_{i}A^{i}\right)=f(B)f(A).$

(2) The operator $A$ is normal if it commutes with its conjugate transpose
$A^{*}$. Since for any operators $B,C$ it holds that $(B+C)^{*}=B^{*}+C^{*}$
and $(B^{k})^{*}=(B^{*})^{k}$, we obtain $f(A^{*})=f(A)^{*}$. The result then
follows from item (1).

(3) We have

$\displaystyle Uf(A)U^{-1}$
$\displaystyle=U\left(\sum_{i=0}^{k}\alpha_{i}A^{i}\right)U^{-1}=\sum_{i=0}^{k}U\alpha_{i}A^{i}U^{-1}=\sum_{i=0}^{k}\alpha_{i}(UAU^{-1})(UAU^{-1})\dots(UAU^{-1})$
$\displaystyle=\sum_{i=0}^{k}\alpha_{i}(UAU^{-1})^{i}=f(UAU^{-1}).$

∎

###### Proof of Lemma 16.

Let ${\mathcal{P}}=(V,U_{d},{\mathcal{C}})$ and let $\\{A_{v}\\}_{v\in V}$ be
an operator assignment that is satisfying for ${\mathcal{P}}$ over a finite-
dimensional Hilbert space ${\mathcal{H}}$. We may assume that
${\mathcal{H}}={\mathbb{C}}^{p}$ for some positive integer $p$ and thus
$\\{A_{v}\\}_{v\in V}$ are $p\times p$ matrices. We will construct an operator
assignment that is satisfying for ${\mathcal{P}}^{\prime}$; it will be an
operator assignment over the same space and an extension of the original
assignment.

Given a constraint $\langle(u_{1},\ldots,u_{r}),R\rangle\in{\mathcal{C}}$, the
operators $\\{A_{u_{i}}\\}_{1\leq i\leq r}$ pairwise commute by assumption.
Since they are also normal, by Theorem 1 there is a unitary matrix $U$ such
that $E_{i}=UA_{u_{i}}U^{-1}$ is a diagonal matrix for each $i\in[r]$. Since
$A_{u_{i}}^{d}=I$, we have $E_{u_{i}}^{d}=I$. Thus every diagonal entry
$E_{u_{i}}(jj)$ belongs to $U_{d}$. Since
$P_{R}(A_{u_{1}},\ldots,A_{u_{r}})=I$, we have
$P_{R}(E_{u_{1}},\ldots,E_{u_{r}})=UP_{R}(A_{u_{1}},\ldots,A_{u_{r}})U^{-1}=I$
by Lemma 17. As $E_{u_{i}}$ is a diagonal matrix, we have that
$P_{R}(E_{u_{1}}(jj),\ldots,E_{u_{r}}(jj))=1=\lambda_{0}$ for every $j\in[p]$.
Thus the tuple $(E_{u_{1}}(jj),\ldots,E_{u_{r}}(jj))\in R$ for every
$j\in[p]$. For each $j\in[p]$, let $b(j)=(b_{1}(j),\ldots,b_{s}(j))\in
U_{d}^{s}$ be a tuple of witnesses to the existentially quantified variables
$y_{1},\ldots,y_{s}$ in the formula pp-defining $R$ in (10) when
$E_{u_{i}}(jj)$ is substituted for $x_{i}$. For $i\in[s]$, let $B_{i}$ be the
diagonal matrix with $B_{i}(jj)=b_{i}(j)$ for every $j\in[d]$. Now let
$C_{i}=U^{-1}B_{i}U$. Since $U$ is unitary we have $U^{-1}=U^{*}$ and thus
each $C_{i}$ is normal:
$C_{i}C_{i}^{*}=U^{*}B_{i}U(U^{*}B_{i}U)^{*}=U^{*}B_{i}UU^{*}B_{i}^{*}U=U^{*}B_{i}B_{i}^{*}U=U^{*}B_{i}^{*}B_{i}U=U^{*}B_{i}^{*}UU^{*}B_{i}U=(U^{*}B_{i}U)^{*}U^{*}B_{i}U=C_{i}^{*}C_{i}$.
Since $b_{i}(j)\in U_{d}$, we have $C_{i}^{d}=I$. Also
$E_{1},\ldots,E_{r},B_{1},\ldots,B_{s}$ pairwise commute since they are all
diagonal matrices. Hence, $A_{i},\ldots,A_{r},C_{1},\ldots,C_{s}$ also
pairwise commute since they all are simultaneously similar via $U$. As each
conjunct in (10) is satisfied by the assignment sending $x_{i}$ to
$E_{u_{i}}(jj)$ and $y_{i}$ to $b_{i}(j)$ for all $j\in[d]$, we can conclude
that the matrices that are assigned to the variables in the conjuncts make the
corresponding polynomial evaluate to $I$. But this means that the assignment
to the variables in the block of the constraint
$\langle(u_{1},\ldots,u_{r}),R\rangle$ makes a satisfying operator assignment
for the constraint of ${\mathcal{P}}^{\prime}$ that has come from the
conjunct. As different constraints involving $R$ in ${\mathcal{P}}$ produce
their own sets of fresh variables, the operator assignments do not affect each
other. ∎

We do not know whether the converse of Lemma 16 holds; this is not known even
in the case of $d=2$ [2]. The obvious idea would be to take the restriction of
the operator assignment that is satisfying for ${\mathcal{P}}^{\prime}$ but it
is not clear why this should be satisfying for ${\mathcal{P}}$, because there
is no guarantee that the operators assigned to variable in the scope of a
constraint of ${\mathcal{P}}$ of the form $\langle{\bf s},R\rangle$ commute.
However, under a slight technical assumption on $\Gamma$ — namely, that it
includes the full binary relation888This is a special case of the so-called
_commutativity gadget_ [2]. on $U_{d}$ — one can enforce commutativity within
a constraint scope and thus project an operator assignment. While this result
is not needed for our main result, we include it for completeness.

Let $R_{T}=U_{d}^{2}$ denote the full binary relation on $U_{d}$. For an
instance ${\mathcal{P}}^{\prime}$ as defined above (and in the statement of
Lemma 16), we denote by ${\mathcal{P}}^{\prime\prime}$ the instance obtained
from ${\mathcal{P}}^{\prime}$ by adding, for every constraint
$\langle(u_{1},\ldots,u_{r}),R\rangle$ of ${\mathcal{P}}$, constraints of the
form $\langle(u_{i},u_{j}),R_{T}\rangle$. for every $i\neq j\in[r]$.

######  Lemma 18.

Let $\Gamma$ be a constraint language over $U_{d}$ with $R_{T}\in\Gamma$ and
let $R$ be pp-definable from $\Gamma$. Furthermore, let ${\mathcal{P}}\in{\rm
CSP}(\Gamma\cup\\{R\\})$ and let ${\mathcal{P}}^{\prime\prime}\in{\rm
CSP}(\Gamma)$ be defined as above. Then, we have the following:
(1) If there is a satisfying operator assignment for ${\mathcal{P}}$ then
there is a satisfying operator assignment for ${\mathcal{P}}^{\prime\prime}$.
(2) If there is a satisfying operator assignment for
${\mathcal{P}}^{\prime\prime}$ then there is a satisfying operator assignment
for ${\mathcal{P}}$.

###### Proof.

(1) follows from Lemma 16: The satisfying operator assignment for
${\mathcal{P}}^{\prime}$ constructed in the proof of Lemma 16 is also a
satisfying operator assignment or ${\mathcal{P}}^{\prime\prime}$. Indeed, the
constraints already present in ${\mathcal{P}}^{\prime}$ are by assumption
satisfied in ${\mathcal{P}}^{\prime\prime}$. Regarding the extra constraints
in ${\mathcal{P}}^{\prime\prime}$ not present in ${\mathcal{P}}^{\prime}$,
each such constraint involves the $R_{T}$ relation and the two variables in
the scope of the constraint come from the block of some constraint in
${\mathcal{P}}^{\prime}$. The proof of Lemma 16 established that the
constructed operators pairwise commute on these variables. Also, as
$P_{R_{T}}(a,b)=1$ for any $a,b\in U_{d}$, the polynomial constraints are
satisfied as they evaluate to $I$.

For (2), take a satisfying operator assignment for
${\mathcal{P}}^{\prime\prime}$ and consider its restriction $\\{A_{v}\\}_{v\in
V}$ onto the variables of ${\mathcal{P}}$. Any two operators whose variables
appear within the scope of some constraint of ${\mathcal{P}}$ necessarily
commute since the two variables are in the block of some constraint in
${\mathcal{P}}^{\prime\prime}$. It remains to show that the polynomial
constraints of ${\mathcal{P}}$ are satisfied, that is, that
$P_{R}(A_{u_{1}},\ldots,A_{u_{r}})=I$ for every constraint
$\langle(u_{1},\ldots,u_{r}),R\rangle$ of ${\mathcal{P}}$. For this, we use
Lemma 2. Let $\phi$ be the formula pp-defining $R$ as in (10). We define
several polynomials over variables $x_{1},\ldots,x_{r},y_{1},\ldots,y_{s}$
that correspond to the variables in (10). For every $i\in[m]$, let $Q_{i}$ be
the polynomial $P_{R_{i}}({\bf z}_{i})-1$ so that the equation $Q_{i}=0$
ensures $P_{R_{i}}({\bf z}_{i})=1$, where $P_{R_{i}}$ is the characteristic
polynomial of $R_{i}$, and ${\bf z}_{i}$ is the tuple of variables from
$x_{1},\ldots,x_{r},y_{1},\ldots,y_{s}$ that correspond to the variables of
the same name that appear in the conjunct $R_{i}({\bf z}_{i})$ of (10). Let
$Q$ be the polynomial $P_{R}(x_{1},\ldots,x_{r})-1$, where $P_{R}$ is the
characteristic polynomial of $R$. By the construction of the polynomials and
the choice of $\phi$, every assignment over $U_{d}$ that satisfies all
equations $Q_{1}=\cdots=Q_{m}=0$ also satisfies $Q=0$. By Lemma 2, we get
$P_{R}(A_{u_{1}},\ldots,A_{u_{r}})-I=0$, as required. ∎

##  8 Unbounded width and gaps

In this section we prove the second direction of our main result.

######  Theorem 19.

Let $\Gamma$ be a constraint language over $U_{d}$. If ${\rm CSP}(\Gamma)$
does not have bounded width then ${\rm CSP}(\Gamma)$ has a satisfiability gap.

The overall idea of proving Theorem 19 is to “implement” the “magic rectangle”
from Section 6 in ${\rm CSP}(\Gamma)$ provided ${\rm CSP}(\Gamma)$ does not
have bounded width. We achieve this in several steps via a chain of reductions
that has been used since the inception of the algebraic method to the CSP
[12]. While more direct constructions have been developed later, see, e.g.,
[5], we find this original approach to be better suited for operator CSPs.

###  8.1 Bounded width, Abelian groups, and the magic square

We start by introducing several definitions.

A constraint language $\Gamma$ over $U_{d}$ is said to be a _core language_ if
its every endomorphism is a permutation. This term comes from finite model
theory where it is used for relational structures that do not have
endomorphisms (homomorphisms to themselves) that are not automorphisms. Such
structures, and therefore languages, have a number of useful properties that
we will exploit later. The standard way to convert a constraint language
$\Gamma$ into a core language is to repeat the following procedure until the
resulting language is a core language: Pick an endomorphism $\varrho$ of
$\Gamma$ that is not a permutation and set

$\varrho(\Gamma)=\\{\varrho(R)\mid R\in\Gamma\\},\quad\text{where
}\varrho(R)=\\{(\varrho(a_{1}),\ldots,\varrho(a_{n}))\mid(a_{1},\ldots,a_{n})\in
R\\}.$

There always exists an endomorphism $\varrho$ of $\Gamma$ such that
$\varrho(\Gamma)$ is core [12, 5] and $\varrho$ is _idempotent_ , that is,
$\varrho\circ\varrho=\varrho$. We will denote this core language by
$\mathsf{core}(\Gamma)$, as it (up to an isomorphism) does not depend on the
choice of $\varrho$. Note that the fact that $\varrho$ is idempotent implies
that it acts as identity on its image.

The language $\Gamma$ is called _idempotent_ if it contains all the _constant_
relations, that is, relations of the form $C_{a}=\\{(a)\\}$, $a\in U_{d}$. For
an arbitrary language $\Gamma$ over $U_{d}$ we use
$\Gamma^{*}=\Gamma\cup\\{C_{a}\mid a\in U_{d}\\}$. A unary relation (a set)
$B\subseteq U_{d}$ pp-definable in $\Gamma$ is called a _subalgebra_ of
$\Gamma$. For a subalgebra $B$ we introduce the _restriction_ $\Gamma\vrule
height=7.0pt,depth=3.0pt,width=0.4pt\lower 3.0pt\hbox{$\scriptstyle B$}$ of
$\Gamma$ to $B$ defined as follows

$\Gamma\vrule height=7.0pt,depth=3.0pt,width=0.4pt\lower
3.0pt\hbox{$\scriptstyle B$}=\\{R\cap B^{ar(R)}\mid R\in\Gamma\\}.$

An equivalence relation $\theta$ pp-definable in $\Gamma$ is said to be a
_congruence_ of $\Gamma$. The equivalence class of $\theta$ containing $a\in
U_{d}$ will be denoted by $a/\lower 2.0pt\hbox{$\scriptstyle\theta$}$, and the
set of all equivalence classes, the _factor-set_ , by $U_{d}/\lower
2.0pt\hbox{$\scriptstyle\theta$}$. Congruences of a constraint language allow
one to define a _factor-language_ as follows. For a congruence $\theta$ of the
language $\Gamma$ the factor language $\Gamma/\lower
2.0pt\hbox{$\scriptstyle\theta$}$ is the language over $U_{d}/\lower
2.0pt\hbox{$\scriptstyle\theta$}$ given by

$\Gamma/\lower 2.0pt\hbox{$\scriptstyle\theta$}=\\{R/\lower
2.0pt\hbox{$\scriptstyle\theta$}\mid R\in\Gamma\\},\quad\text{where }R/\lower
2.0pt\hbox{$\scriptstyle\theta$}=\\{(a_{1}/\lower
2.0pt\hbox{$\scriptstyle\theta$},\ldots,a_{n}/\lower
2.0pt\hbox{$\scriptstyle\theta$})\mid(a_{1},\ldots,a_{n})\in R\\}.$

In order to fit core languages, subalgebras, and factor-languages in our
framework where the domain is the set of roots of unity, we let
$e=|\varrho(U_{d})|$, $e=|B|$ or $e=|U_{d}/\lower
2.0pt\hbox{$\scriptstyle\theta$}|$, respectively, arbitrarily choose a
bijection $\pi:\varrho(U_{d})\to U_{e}$, $\pi:B\to U_{e}$, and
$\pi:U_{d}/\lower 2.0pt\hbox{$\scriptstyle\theta$}\to U_{e}$, and replace
$\varrho(\Gamma)$, $\Gamma\vrule height=7.0pt,depth=3.0pt,width=0.4pt\lower
3.0pt\hbox{$\scriptstyle B$}$, and $\Gamma/\lower
2.0pt\hbox{$\scriptstyle\theta$}$ with $\pi(\varrho(\Gamma))$,
$\pi(\Gamma\vrule height=7.0pt,depth=3.0pt,width=0.4pt\lower
3.0pt\hbox{$\scriptstyle B$})$, and $\pi(\Gamma/\lower
2.0pt\hbox{$\scriptstyle\theta$})$, respectively.

All the languages above are connected with each other in terms of the
reducibility of the corresponding CSPs, as Figure 3 and the following
statements indicate.

######  Proposition 20 ([12, 5]).

Let $\Gamma$ be a constraint language over $U_{d}$. Then

  * (1)

For any endomorphism $\varrho$ of $\Gamma$, ${\rm CSP}(\Gamma)$ and ${\rm
CSP}(\mathsf{core}(\Gamma))$ are polynomial-time interreducible.

  * (2)

If $\Gamma$ is a core language, ${\rm CSP}(\Gamma)$ and ${\rm
CSP}(\Gamma^{*})$ are polynomial-time interreducible.

  * (3)

If $B$ is a subalgebra of $\Gamma$ then ${\rm CSP}(\Gamma\vrule
height=7.0pt,depth=3.0pt,width=0.4pt\lower 3.0pt\hbox{$\scriptstyle B$})$ is
polynomial-time reducible to ${\rm CSP}(\Gamma)$.

  * (4)

If $\theta$ is a congruence of $\Gamma$ then ${\rm CSP}(\Gamma/\lower
2.0pt\hbox{$\scriptstyle\theta$})$ is polynomial-time reducible to ${\rm
CSP}(\Gamma)$.

${\rm CSP}(\Gamma)\ \leftrightarrow\ {\rm
CSP}(\mathsf{core}(\Gamma))\leftrightarrow\ {\rm
CSP}(\mathsf{core}(\Gamma)^{*})\ \leftarrow\ {\rm
CSP}(\mathsf{core}(\Gamma)^{*}\vrule
height=7.0pt,depth=3.0pt,width=0.4pt\lower 3.0pt\hbox{$\scriptstyle B$})\
\leftarrow\ {\rm CSP}(\mathsf{core}(\Gamma)^{*}\vrule
height=7.0pt,depth=3.0pt,width=0.4pt\lower 3.0pt\hbox{$\scriptstyle B$}/\lower
2.0pt\hbox{$\scriptstyle\theta$})$ Figure 3: Reductions between CSPs
corresponding to derivative languages

Finally, to relate the reductions above with bounded width and the magic
square we apply the following result that can be extracted from the known
results on the algebraic approach to CSPs [11, 3, 5].

######  Proposition 21 ([11, 3, 5]).

For a constraint language $\Gamma$ over $U_{d}$, ${\rm CSP}(\Gamma)$ does not
have bounded width if and only there exists a language $\Delta$ pp-definable
in $\Gamma$, a subalgebra $B$ of $\mathsf{core}(\Delta)^{*}$, a congruence
$\theta$ of $\mathsf{core}(\Delta)^{*}\vrule
height=7.0pt,depth=3.0pt,width=0.4pt\lower 3.0pt\hbox{$\scriptstyle B$}$, and
an Abelian group ${\mathbb{A}}$ of prime order $p$ such that
$\mathsf{core}(\Delta)^{*}\vrule height=7.0pt,depth=3.0pt,width=0.4pt\lower
3.0pt\hbox{$\scriptstyle B$}/\lower 2.0pt\hbox{$\scriptstyle\theta$}$ contains
relations $R_{3,a},R_{p+2}$ for every $a\in{\mathbb{A}}$ given by

$R_{3,a}=\\{(x,y,z)\mid x+y+z=a\\},\quad\text{and}\quad
R_{p+2}=\\{(a_{1},\ldots,a_{p+2})\mid a_{1}+\dots+a_{p+2}=0\\}.$

###  8.2 Proof of Theorem 19

In this section we prove that the connections shown in Figure 3 hold in terms
of satisfiability gaps. We start with a helpful observation. As any mapping on
a finite set of complex numbers can be interpolated by a polynomial, we may
apply such mappings to operators as well (we assume that such an interpolating
polynomial is of the lowest degree possible, and so is unique). A polynomial
$\varrho$ is said to _interpolate_ a set $B\subseteq U_{d}$ if
$\varrho(\lambda)=1$ if $\lambda\in B$ and $\varrho(\lambda)=0$ if $\lambda\in
U_{d}-B$.

######  Lemma 22.

Let $d,e\in\mathchar 2894\relax$, $e\leq d$. Let $\pi:U_{e}\to U_{d}$ be an
injective mapping and $\varrho$ a unary polynomial that interpolates $B={\sf
Im}\;(\pi)$. Let $A_{1},\ldots,A_{k}$ be pairwise commuting normal operators
of order $e$. Then $C_{i}=\pi(A_{i})$, $i\in[k]$, are pairwise commuting
normal operators of order $d$, and $\varrho(C_{i})=I$. Conversely, let
$C_{1},\ldots,C_{k}$ be pairwise commuting normal operators of order $d$ such
that $\varrho(C_{i})=I$. Then for $A_{i}=\pi^{-1}(C_{i})$, $i\in[k]$, it holds
that the $A_{i}$’s are pairwise commuting normal operators of order $e$, and
the eigenvalues of the $C_{i}$’s belong to $B$.

###### Proof.

That the $C_{i}$’s are normal and pairwise commute follow from Lemma 17. Let
the $A_{i}$’s be $\ell$-dimensional and $U$ a unitary operator guaranteed by
Theorem 1 such that $UA_{i}U^{-1}$ is diagonal for all $i\in[k]$, and let

$UA_{i}U^{-1}=\left(\begin{array}[]{ccc}\mu_{i1}&\dots&0\\\
\vdots&\ddots&\vdots\\\ 0&\dots&\mu_{i\ell}\end{array}\right).$

Then,

$\displaystyle C_{i}^{d}$ $\displaystyle=$
$\displaystyle(\pi(A_{i}))^{d}=U^{-1}U(\pi(A_{i}))^{d}U^{-1}U=U^{-1}(\pi(UA_{i}U^{-1}))^{d}U$
$\displaystyle=$ $\displaystyle
U^{-1}\left(\begin{array}[]{ccc}(\pi(\mu_{i1}))^{d}&\dots&0\\\
\vdots&\ddots&\vdots\\\
0&\dots&(\pi(\mu_{i\ell}))^{d}\end{array}\right)U=U^{-1}\left(\begin{array}[]{ccc}1&\dots&0\\\
\vdots&\ddots&\vdots\\\ 0&\dots&1\end{array}\right)U=I,$

because $\pi(\mu_{ij})\in U_{d}$ and by Lemma 17. In a similar way, as
$\pi(\mu_{ij})\in B$,

$\varrho(C_{i})=U^{-1}\left(\begin{array}[]{ccc}\varrho(\mu_{i1})&\dots&0\\\
\vdots&\ddots&\vdots\\\ 0&\dots&\varrho(\mu_{i\ell})\end{array}\right)U=I.$

For the second part of the claim we first need verify that all the eigenvalues
of the $C_{i}$’s belong to $B$. Let $U$ be a unitary operator that
diagonalizes the $C_{i}$’s and

$UC_{i}U^{-1}=\left(\begin{array}[]{ccc}\mu_{i1}&\dots&0\\\
\vdots&\ddots&\vdots\\\ 0&\dots&\mu_{i\ell}\end{array}\right),$

assuming that the $C_{i}$’s are $\ell$-dimensional. Then we have

$I=\varrho(C_{i})=U^{-1}U\varrho(C_{i})U^{-1}U=U^{-1}\varrho(UC_{i}U^{-1})U=U^{-1}\left(\begin{array}[]{ccc}\varrho(\mu_{i1})&\dots&0\\\
\vdots&\ddots&\vdots\\\ 0&\dots&\varrho(\mu_{i\ell})\end{array}\right)U,$

implying $\varrho(\mu_{ij})=1$. Then we proceed as in the first part of the
claim. ∎

Next we consider the four connections from Figure 3 one by one and prove that
each of them preserves the satisfiability gap.

Step 1 (Reductions to a core). Let $\Gamma$ be a constraint language over the
set $U_{d}$ and $\varrho:U_{d}\to U_{d}$ an idempotent endomorphism of
$\Gamma$. Then ${\rm CSP}(\Gamma)$ has a satisfiability gap if and only if
${\rm CSP}(\varrho(\Gamma))$ does.

Suppose that $|{\sf Im}\;(\varrho)|=e$, let $\pi^{\prime}:{\sf
Im}\;(\varrho)\to U_{e}$ be any bijection between $U_{e}$ and ${\sf
Im}\;(\varrho)$, and $\pi=\pi^{\prime}\circ\varrho$. Let $\Delta=\\{\pi(R)\mid
R\in\Gamma\\}$, we show that ${\rm CSP}(\Delta)$ has a satisfiability gap if
and only if ${\rm CSP}(\Gamma)$ does.

Let ${\mathcal{P}}=(V,U_{e},{\mathcal{C}})$ be a gap instance of ${\rm
CSP}(\Delta)$, and let ${\mathcal{P}}^{\pi}=(V,U_{d},{\mathcal{C}}^{\pi})$ be
the corresponding instance of ${\rm CSP}(\Gamma)$, where for each $\langle{\bf
s},R\rangle\in{\mathcal{C}}$ the set ${\mathcal{C}}^{\pi}$ includes
$\langle{\bf s},Q\rangle$ with $Q\in\Gamma$ and $\pi(Q)=R$. As is easily seen,
${\mathcal{P}}^{\pi}$ has no solution, because for any solution $\varphi$ of
${\mathcal{P}}^{\pi}$ the mapping $\pi\circ\varphi$ is a solution of
${\mathcal{P}}$. Let $\\{A_{v}\mid v\in V\\}$ be an $\ell$-dimensional
satisfying operator assignment for ${\mathcal{P}}$. We prove that
$\\{\pi^{\prime-1}(A_{v})\mid v\in V\\}$ is a satisfying operator assignment
for ${\mathcal{P}}^{\pi}$. Let $C_{v}=\pi^{\prime-1}(A_{v})$.

By Lemma 22, the $C_{v}$’s are normal, $C_{v}^{d}=I$, $v\in V$, and for any
constraint $\langle{\bf s},R\rangle\in{\mathcal{C}}$ and any $v,w\in{\bf s}$,
$C_{v},C_{w}$ commute. Now, let $\langle{\bf s},R\rangle\in{\mathcal{C}}$,
${\bf s}=(v_{1},\ldots,v_{k})$, $\langle{\bf s},Q\rangle$ be the corresponding
constraint of ${\mathcal{P}}^{\pi}$, and $f_{R},f_{Q}$ be the polynomials
representing $R,Q$ over $U_{e},U_{d}$ respectively. We have
$f_{R}(A_{v_{1}},\ldots,A_{v_{k}})=I$, and we need to show that
$f_{Q}(C_{v_{1}},\ldots,C_{v_{k}})=I$. Let $U$ diagonalize
$A_{v_{1}},\ldots,A_{v_{k}}$ and

$UA_{v_{i}}U^{-1}=\left(\begin{array}[]{ccc}\mu_{i1}&\dots&0\\\ &\ddots&\\\
0&\dots&\mu_{i\ell}\end{array}\right).$

Then $(\mu_{1j},\ldots,\mu_{kj})\in R$ for $j\in[\ell]$, because

$I=f_{R}(A_{v_{1}},\ldots,A_{v_{k}})=f_{R}(UA_{v_{1}}U^{-1},\ldots,UA_{v_{k}}U^{-1})=\left(\begin{array}[]{ccc}f_{R}(\mu_{11},\ldots,\mu_{k1})&\dots&0\\\
&\ddots&\\\ 0&\dots&f_{R}(\mu_{1\ell},\ldots,\mu_{k\ell})\end{array}\right).$

Therefore,
$(\pi^{\prime-1}(\mu_{1j}),\ldots,\pi^{\prime-1}(\mu_{kj}))\in\varrho(Q)$ for
$j\in[\ell]$, and, as $\varrho$ is an endomorphism,
$(\pi^{\prime-1}(\mu_{1j}),\ldots,\pi^{\prime-1}(\mu_{kj}))\in Q$ and so
$f_{Q}(\pi^{\prime-1}(\mu_{1j}),\ldots,\pi^{\prime-1}(\mu_{kj}))=\lambda_{0}=1$.
Since

$UC_{v_{i}}U^{-1}=U\pi^{\prime-1}(A_{v_{i}})U^{-1}=\pi^{\prime-1}(UA_{v_{i}}U^{-1})=\left(\begin{array}[]{ccc}\pi^{\prime-1}(\mu_{i1})&\dots&0\\\
&\ddots&\\\ 0&\dots&\pi^{\prime-1}(\mu_{i\ell})\end{array}\right),$

we also have $f_{Q}(C_{v_{1}},\ldots,C_{v_{k}})=\lambda_{0}=1$.

Now, let ${\mathcal{P}}^{\pi}=(V,U_{d},{\mathcal{C}}^{\pi})$ be a gap instance
of ${\rm CSP}(\Gamma)$, $\\{C_{v}\mid v\in V\\}$ an $\ell$-dimensional
satisfying operator assignment for ${\mathcal{P}}^{\pi}$, and
${\mathcal{P}}=(V,U_{e},{\mathcal{C}})$, ${\mathcal{C}}=\\{\langle{\bf
s},R\rangle\mid\langle{\bf s},Q\rangle\in{\mathcal{C}}^{\pi},R=\pi(Q)\\}$, the
corresponding instance of ${\rm CSP}(\Delta)$. Then again ${\mathcal{P}}$ has
no solution over $U_{e}$, and it remains to prove that $\\{A_{v}\mid v\in
V\\}$, $A_{v}=\pi(C_{v})$ is a satisfying operator assignment for
${\mathcal{P}}=(V,{\mathcal{C}})$. For $\langle{\bf
s},R\rangle\in{\mathcal{C}}$, ${\bf s}=(v_{1},\ldots,v_{k})$, let
$f_{R},f_{Q}$ be polynomials representing $R$ and $Q\in\Gamma$ with
$\pi(Q)=R$, respectively.

First, we show that the $C_{v}$’s can be replaced with $\varrho(C_{v})$. Since
for any $\langle{\bf s},Q\rangle\in{\mathcal{C}}^{\pi}$, ${\bf
s}=(v_{1},\ldots,v_{k})$, and any $a_{1},\ldots,a_{k}\in U_{d}$, we have that
$f_{Q}(\varrho(a_{1}),\ldots,\varrho(a_{k}))=1$ whenever
$f_{Q}(a_{1},\ldots,a_{k})=1$, by Lemma 2
$f_{Q}(\varrho(C_{v_{1}}),\ldots,\varrho(C_{v_{k}}))=I$ whenever
$f_{Q}(C_{v_{1}},\ldots,C_{v_{k}})=I$. Thus, we assume
$A_{v}=\pi^{\prime}(C_{v})$ for $v\in V$.

That $A_{v}$ is normal, $A_{v}^{e}=I$, $v\in V$, and the $A_{v}$’s locally
commute follows from Lemma 22. Let
$f^{\pi}_{Q}(x_{1},\ldots,x_{k})=f_{Q}(\pi^{\prime-1}(x_{1}),\ldots,\pi^{\prime-1}(x_{k}))$.
As is easily seen, for any $a_{1},\ldots,a_{k}\in U_{e}$, if
$f^{\pi}_{Q}(a_{1},\ldots,a_{k})=1$ then $f_{R}(a_{1},\ldots,a_{k})=1$. Hence,
by Lemma 2 $f_{R}(A_{v_{1}},\ldots,A_{v_{k}})=I$ whenever
$f^{\pi}_{Q}(A_{v_{1}},\ldots,A_{v_{k}})=I$. Finally, we prove that
$\pi^{\prime-1}(A_{v})=C_{v}$; this implies that
$f^{\pi}_{Q}(A_{v_{1}},\ldots,A_{v_{k}})=I$ completing the proof. Let $U$
diagonalize $C_{v}$ and

$UC_{v}U^{-1}=\left(\begin{array}[]{ccc}\mu_{1}&\dots&0\\\ &\ddots&\\\
0&\dots&\mu_{\ell}\end{array}\right).$

Then

$\displaystyle\pi^{\prime-1}(A_{v})$ $\displaystyle=$
$\displaystyle\pi^{\prime-1}(\pi^{\prime}(C_{v}))=U^{-1}U\pi^{\prime-1}(\pi^{\prime}(C_{v}))U^{-1}U=U^{-1}\pi^{\prime-1}(\pi^{\prime}(UC_{v}U^{-1}))U$
$\displaystyle=$ $\displaystyle
U^{-1}\left(\begin{array}[]{ccc}\pi^{\prime-1}(\pi^{\prime}(\mu_{1}))&\dots&0\\\
&\ddots&\\\
0&\dots&\pi^{\prime-1}(\pi^{\prime}(\mu_{\ell}))\end{array}\right)U=U^{-1}\left(\begin{array}[]{ccc}\mu_{1}&\dots&0\\\
&\ddots&\\\ 0&\dots&\mu_{\ell}\end{array}\right)U=C_{v}.$

Step 2 (Adding constant relations). Let $\Gamma$ be a core language. Then
${\rm CSP}(\Gamma)$ has a satisfiability gap if and only if ${\rm
CSP}(\Gamma^{*})$ does.

Since $\Gamma\subseteq\Gamma^{*}$, if ${\rm CSP}(\Gamma)$ has a satisfiability
gap, so does ${\rm CSP}(\Gamma^{*})$. We prove that if ${\rm CSP}(\Gamma^{*})$
has a satisfiability gap then ${\rm CSP}(\Gamma)$ has a satisfiability gap.

We will use the following relation $R_{\Gamma}$ that is known to be pp-
definable in $\Gamma$ [29]:

$R_{\Gamma}=\\{(\varrho(\lambda_{0}),\ldots,\varrho(\lambda_{d-1}))\mid\text{$\varrho$
is an endomorphism of $\Gamma$}\\}.$

As $\Gamma$ is a core language, for any $(a_{1},\ldots,a_{d})\in R_{\Gamma}$
it holds that $\\{a_{1},\ldots,a_{d}\\}=U_{d}$. By Theorem 15 we may assume
that $R_{\Gamma}\in\Gamma$.

Let ${\mathcal{P}}=(V,U_{d},{\mathcal{C}})$ be a gap instance of ${\rm
CSP}(\Gamma^{*})$. We construct an instance
${\mathcal{P}}^{\prime}=(V^{\prime},U_{d},{\mathcal{C}}^{\prime})$ of ${\rm
CSP}(\Gamma)$ as follows.

  * •

$V^{\prime}=V\cup\\{v_{a}|a\in U_{d}\\}$;

  * •

${\mathcal{C}}^{\prime}$ consists of three parts: $\\{C=\langle{\bf
s},R\rangle\in{\mathcal{C}}\mid R\in\Gamma\\}$,
$\\{\langle(v_{a_{1}},\ldots,v_{a_{n}}),R_{\Gamma}\rangle\\}$, and
$\\{\langle(v,v_{a}),=_{d}\rangle\mid\langle(v),C_{a}\rangle\in{\mathcal{C}}\\}$,
where $=_{d}$ denotes the equality relation on $U_{d}$.

It is known [29] that ${\mathcal{P}}^{\prime}$ has a classic solution if and
only if ${\mathcal{P}}$ has one. If $\varphi:V\to U_{d}$ is a solution of
${\mathcal{P}}$ then we can extend it to a solution of
${\mathcal{P}}^{\prime}$ by mapping $v_{a}$ to $a$. Conversely, let
$\varphi:V^{\prime}\to U_{d}$ be a solution of ${\mathcal{P}}^{\prime}$. The
restriction of $\varphi$ to $V$ may not be a solution of ${\mathcal{P}}$,
because for some constraint $\langle(v),C_{a}\rangle\in{\mathcal{C}}$ it may
be the case that $\varphi(v)=\varphi(v_{a})\neq a$. This can be fixed as
follows. As $\varphi$ is a solution,
$(\varphi(v_{\lambda_{0}}),\ldots,\varphi(v_{\lambda_{d-1}}))\in R_{\Gamma}$,
hence, the mapping $\varrho:U_{d}\to U_{d}$ given by
$\varrho(a)=\varphi(v_{a})$ is an endomorphism of $\Gamma$. As $\Gamma$ is a
core language, $\varrho$ is a permutation on $U_{d}$ and $\varrho^{s}$ is the
identity permutation for some $s$. Then $\varrho^{s-1}$ is the inverse
$\varrho^{-1}$ of $\varrho$ and is also an endomorphism of $\Gamma$. Therefore
$\varphi^{\prime}=\varrho^{-1}\circ\varphi$ is also a solution of
${\mathcal{P}}^{\prime}$ and $\varphi^{\prime}(v_{a})=a$ for $a\in U_{d}$.
Thus, $\varphi^{\prime}\vrule height=7.0pt,depth=3.0pt,width=0.4pt\lower
3.0pt\hbox{$\scriptstyle V$}$ is a solution of ${\mathcal{P}}$.

Now, suppose that $\\{A_{v}\mid v\in V\\}$ is an $\ell$-dimensional satisfying
operator assignment for ${\mathcal{P}}$. First, we observe that if
${\mathcal{C}}$ contains a constraint $\langle(v),C_{a}\rangle$ then $A_{v}$
is the scalar operator $aI$. Indeed, let $f_{a}(x)$ be a polynomial
representing $C_{a}$, that is, $f_{a}(a)=\lambda_{0}$ and
$f_{a}(b)=\lambda_{1}$ for $b\in U_{d}-\\{a\\}$. Let also $U$ be a unitary
operator that diagonalizes $A_{v}$ and $\mu_{1},\ldots,\mu_{\ell}$ the
eigenvalues of $A_{v}$. Then, as $f_{a}(A_{v})=I$ we obtain

$I=UIU^{-1}=Uf_{a}(A_{v})U^{-1}=f_{a}(UA_{v}U^{-1})=\left(\begin{array}[]{ccc}f_{a}(\mu_{1}))&\dots&0\\\
&\ddots&\\\ 0&\dots&f_{a}(\mu_{\ell}))\end{array}\right)$

implying that $f_{a}(\mu_{i})=\lambda_{0}$ for $i\in[\ell]$. Thus, $a$ is the
only eigenvalue of $A_{v}$ and

$A_{v}=U^{-1}aIU=aI.$

All such operators pairwise commute regardless of the value of $a$. Therefore
$v_{a}$ can be assigned $aI$ for $a\in U_{d}$, and the resulting assignment is
a satisfying operator assignment for ${\mathcal{P}}^{\prime}$.

Step 3 (Satisfiability gap from subalgebras). Let $\Gamma$ be a constraint
language over the set $U_{d}$ and let $B$ be its subalgebra. Then if ${\rm
CSP}(\Gamma\vrule height=7.0pt,depth=3.0pt,width=0.4pt\lower
3.0pt\hbox{$\scriptstyle B$})$ has a satisfiability gap then so does ${\rm
CSP}(\Gamma)$.

Let $\Delta=\Gamma\vrule height=7.0pt,depth=3.0pt,width=0.4pt\lower
3.0pt\hbox{$\scriptstyle B$}$. Then by Theorem 15 we may assume
$\Delta\subseteq\Gamma$ and $B\in\Gamma$. Let $e=|B|$ and $\pi:U_{e}\to U_{d}$
a bijection between $U_{e}$ and $B$.

Let ${\mathcal{P}}=(V,U_{e},{\mathcal{C}})$ be a gap instance of ${\rm
CSP}(\pi^{-1}(\Delta))$ and the instance
${\mathcal{P}}^{\pi}=(V,U_{d},{\mathcal{C}}^{\pi})$ constructed as follows.
For every $\langle{\bf s},R\rangle\in{\mathcal{C}}$ the instance
${\mathcal{P}}^{\pi}$ contains $\langle{\bf s},\pi(R)\rangle$. As is easily
seen, ${\mathcal{P}}^{\pi}$ has no classic solution. Therefore, it suffices to
show that for any $\ell$-dimensional satisfying operator assignment
$\\{A_{v}\mid v\in V\\}$ for ${\mathcal{P}}$, the assignment
$C_{v}=\pi(A_{v})$ is a satisfying operator assignment for
${\mathcal{P}}^{\pi}$.

By Lemma 22, the $C_{v}$’s are normal, satisfy the condition $C_{v}^{d}=I$,
and locally commute. For $\langle{\bf s},R\rangle\in{\mathcal{C}}$, ${\bf
s}=(v_{1},\ldots,v_{k})$, let
$f^{\pi}_{R}(x_{1},\ldots,x_{k})=f_{R}(\pi^{-1}(x_{1}),\ldots,\pi^{-1}(x_{k}))$.
As in Step 1, it can be shown that $\pi^{-1}(C_{v})=A_{v}$, and therefore
$f^{\pi}_{R}(C_{v_{1}},\ldots,C_{v_{k}})=I$. For any $a_{1},\ldots,a_{k}\in
U_{d}$, if $(a_{1},\ldots,a_{k})\in\pi(R)$ then $a_{1},\ldots,a_{k}\in B$.
Therefore, if $f^{\pi}_{R}(a_{1},\ldots,a_{k})=1$ then
$f_{\pi(R)}(a_{1},\ldots,a_{k})=1$. By Lemma 2 this implies
$f_{\pi(R)}(C_{v_{1}},\ldots,C_{v_{k}})=I$.

Step 4 (Satisfiability gap from homomorphic images). Let $\Gamma$ be a
constraint language over the set $U_{d}$ and $\theta$ a congruence of
$\Gamma$. Then if ${\rm CSP}(\Gamma/\lower 2.0pt\hbox{$\scriptstyle\theta$})$
has a satisfiability gap then so does ${\rm CSP}(\Gamma)$.

Let $\varrho:U_{d}\to U_{d}/\lower 2.0pt\hbox{$\scriptstyle\theta$}$ be the
natural mapping $a\mapsto a/\lower 2.0pt\hbox{$\scriptstyle\theta$}$ and
$\pi^{\prime}:U_{d}/\lower 2.0pt\hbox{$\scriptstyle\theta$}\to U_{e}$, where
$e=|U_{d}/\lower 2.0pt\hbox{$\scriptstyle\theta$}|$, a bijection. Finally, let
$\pi=\pi^{\prime}\circ\varrho$ and $\Delta=\pi(\Gamma)$. For $R\in\Delta$ let
$\pi^{-1}(R)$ be the full preimage of $R$ under $\pi$. Since $\theta$ is pp-
definable in $\Gamma$, so is $\pi^{-1}(R)$ for any $R\in\Delta$. Indeed, if
$R=\pi(Q)$ for some $Q\in\Gamma$, then

$\pi^{-1}(R)(x_{1},\ldots,x_{k})=\exists y_{1},\ldots,y_{k}\ \
Q(y_{1},\ldots,y_{k})\wedge\bigwedge_{i\in[k]}\theta(x_{i},y_{i}).$

Using Theorem 15 we may assume that $\pi^{-1}(R)\in\Gamma$ for $R\in\Delta$.
Let $\pi^{*}:U_{e}\to U_{d}$ assign to $a\in U_{e}$ a representative of the
$\theta$-class $\pi^{\prime-1}(a)$. Thus, in a certain sense, $\pi^{*}$ is an
inverse of $\pi$.

Suppose that ${\mathcal{P}}=(V,U_{e},{\mathcal{C}})$ is a gap instance of
${\rm CSP}(\Delta)$ and let
${\mathcal{P}}^{\pi}=(V,U_{d},{\mathcal{C}}^{\pi})$ be given by
${\mathcal{C}}^{\pi}=\\{\langle{\bf s},\pi^{-1}(R)\rangle\mid\langle{\bf
s},R\rangle\in{\mathcal{C}}\\}$. We prove that ${\mathcal{P}}^{\pi}$ is a gap
instance of ${\rm CSP}(\Gamma)$. Firstly, observe that ${\mathcal{P}}^{\pi}$
has no classic solution, because for any solution $\varphi$ of
${\mathcal{P}}^{\pi}$ the mapping $\pi\circ\varphi$ is a solution of
${\mathcal{P}}$. Let $\\{A_{v}\mid v\in V\\}$ be a satisfying operator
assignment for ${\mathcal{P}}$. We set $C_{v}=\pi^{*}(A_{v})$ and prove that
$\\{C_{v}\mid v\in V\\}$ is a satisfying operator assignment for
${\mathcal{P}}^{\pi}$. By Lemma 22, the $C_{v}$’s are normal, satisfy the
condition $C_{v}^{d}=I$, and locally commute. For $\langle{\bf
s},R\rangle\in{\mathcal{C}}$, ${\bf s}=(v_{1},\ldots,v_{k})$, let
$f^{\pi}_{R}(x_{1},\ldots,x_{k})=f_{R}(\pi(x_{1}),\ldots,\pi(x_{k}))$. As
before, it is easy to see that $\pi(C_{v})=A_{v}$ for $v\in V$, and therefore
$f^{\pi}_{R}(C_{v_{1}},\ldots,C_{v_{k}})=I$. Finally, for any
$(a_{1},\ldots,a_{k})\in U_{d}$, if
$f^{\pi}_{R}(a_{1},\ldots,a_{k})=f_{R}(\pi(a_{1}),\ldots,\pi(a_{k}))=1$, then
$(\pi(a_{1}),\ldots,\pi(a_{k}))\in R$, and so
$(a_{1},\ldots,a_{k})\in\pi^{-1}(R)$ and
$f_{\pi^{-1}(R)}(a_{1},\ldots,a_{k})=1$. By Lemma 2 this implies that
$f_{\pi^{-1}(R)}(C_{v_{1}},\ldots,C_{v_{k}})=I$.

###### Proof of Theorem 19..

Suppose that ${\rm CSP}(\Gamma)$ does not have bounded width. Then by
Proposition 21 there exists a language $\Delta$ pp-definable in $\Gamma$, a
subalgebra $B$ of $\mathsf{core}(\Delta)^{*}$, a congruence $\theta$ of
$\mathsf{core}(\Delta)^{*}\vrule height=7.0pt,depth=3.0pt,width=0.4pt\lower
3.0pt\hbox{$\scriptstyle B$}$, and an Abelian group ${\mathbb{A}}$ of prime
order $p$ such that $\mathsf{core}(\Delta)^{*}\vrule
height=7.0pt,depth=3.0pt,width=0.4pt\lower 3.0pt\hbox{$\scriptstyle B$}/\lower
2.0pt\hbox{$\scriptstyle\theta$}$ contains relations $R_{3,a},R_{p+2}$ for
every $a\in{\mathbb{A}}$ given by

$R_{3,a}=\\{(x,y,z)\mid x+y+z=a\\},\quad\text{and}\quad
R_{p+2}=\\{(a_{1},\ldots,a_{p+2})\mid a_{1}+\dots+a_{p+2}=0\\}.$

By what is proved above it suffices to prove that ${\rm CSP}(\Delta_{p})$,
$\Delta_{p}=\\{R_{3,a}\mid a\in{\mathbb{A}}\\}\cup\\{R_{p+2}\\}$, has a
satisfiability gap. However, if $p=2$, the Mermin-Peres magic square from [44]
provides a gap instance of ${\rm CSP}(\\{R_{3,1},R_{3,-1}\\})$, and the
construction from Proposition 14 provides a gap instance for ${\rm
CSP}(\Delta_{p})$ when $p>2$. Note that in both cases the group ${\mathbb{A}}$
is the multiplicative group of roots of unity. ∎

## References

  * [1] Padmanabhan K Aravind.  Bell’s theorem without inequalities and only two distant observers.  Found. Phys., 15:397–405, 2002.  doi:10.1023/A:1021272729475.
  * [2] Albert Atserias, Phokion G. Kolaitis, and Simone Severini.  Generalized satisfiability problems via operator assignments.  J. Comput. Syst. Sci., 105:171–198, 2019.  arXiv:1704.01736, doi:10.1016/J.JCSS.2019.05.003.
  * [3] Libor Barto and Marcin Kozik.  Constraint satisfaction problems solvable by local consistency methods.  J. ACM, 61(1):3:1–3:19, 2014.  doi:10.1145/2556646.
  * [4] Libor Barto and Marcin Kozik.  Robustly solvable constraint satisfaction problems.  SIAM J. Comput., 45(4):1646–1669, 2016.  arXiv:1512.01157, doi:10.1137/130915479.
  * [5] Libor Barto, Andrei Krokhin, and Ross Willard.  Polymorphisms, and how to use them.  In Andrei Krokhin and Stanislav Živný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1–44. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2017.  doi:10.4230/DFU.Vol7.15301.1.
  * [6] John S Bell.  On the problem of hidden variables in quantum mechanics.  Rev. Mod. Phys., 38(3):447, 1966.  doi:10.1103/RevModPhys.38.447.
  * [7] Manuel Bodirsky.  Complexity of infinite-domain constraint satisfaction, volume 52.  Cambridge University Press, 2021.
  * [8] Manuel Bodirsky and Jakub Rydval.  On the descriptive complexity of temporal constraint satisfaction problems.  J. ACM, 70(1):2:1–2:58, 2023.  doi:10.1145/3566051.
  * [9] Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep.  SDPs and robust satisfiability of promise CSP.  In Proc. 55th Annual ACM Symposium on Theory of Computing (STOC’23), pages 609–622. ACM, 2023.  arXiv:2211.08373, doi:10.1145/3564246.3585180.
  * [10] Jonah Brown-Cohen and Prasad Raghavendra.  Combinatorial optimization algorithms via polymorphisms.  CoRR, abs/1501.01598, 2015.  arXiv:1501.01598.
  * [11] Andrei Bulatov.  Bounded relational width.  Unpublished manuscript, 2009.  URL: https://www2.cs.sfu.ca/~abulatov/papers/relwidth.pdf.
  * [12] Andrei Bulatov, Peter Jeavons, and Andrei Krokhin.  Classifying the complexity of constraints using finite algebras.  SIAM J. Comput., 34(3):720–742, 2005.  doi:10.1137/S0097539700376676.
  * [13] Andrei A. Bulatov.  A Dichotomy Theorem for Constraints on a Three-Element Set.  In Proc. 43rd Symposium on Foundations of Computer Science (FOCS’02), pages 649–658. IEEE Computer Society, 2002.  doi:10.1109/SFCS.2002.1181990.
  * [14] Andrei A. Bulatov.  A dichotomy theorem for constraint satisfaction problems on a 3-element set.  J. ACM, 53(1):66–120, 2006.  doi:10.1145/1120582.1120584.
  * [15] Andrei A. Bulatov.  A dichotomy theorem for nonuniform CSPs.  In Proc. 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS’17), pages 319–330, 2017.  arXiv:1703.03021, doi:10.1109/FOCS.2017.37.
  * [16] Richard Cleve, Peter Høyer, Benjamin Toner, and John Watrous.  Consequences and limits of nonlocal strategies.  In Proc. 19th Annual IEEE Conference on Computational Complexity (CCC’04), pages 236–249. IEEE Computer Society, 2004.  doi:10.1109/CCC.2004.1313847.
  * [17] Richard Cleve, Li Liu, and William Slofstra.  Perfect commuting-operator strategies for linear system games.  J. Math. Phys., 58(1), 2017.  arXiv:1606.02278, doi:10.1063/1.4973422.
  * [18] Richard Cleve and Rajat Mittal.  Characterization of binary constraint system games.  In Proc. 41st International Colloquium on Automata, Languages, and Programming (ICALP’14), volume 8572 of Lecture Notes in Computer Science, pages 320–331. Springer, 2014.  doi:10.1007/978-3-662-43948-7\\_27.
  * [19] Eric Culf, Hamoon Mousavi, and Taro Spirig.  Approximation algorithms for noncommutative constraint satisfaction problems.  2023\.  arXiv:2312.16765.
  * [20] Víctor Dalmau and Andrei A. Krokhin.  Robust Satisfiability for CSPs: Hardness and Algorithmic Results.  ACM Trans. Comput. Theory, 5(4):15:1–15:25, 2013.  doi:10.1145/2540090.
  * [21] Víctor Dalmau and Justin Pearson.  Closure functions and width 1 problems.  In Proc. 4th International Conference on Principles and Practice of Constraint Programming (CP’99), volume 1713 of Lecture Notes in Computer Science, pages 159–173. Springer, 1999.  doi:10.1007/978-3-540-48085-3\\_12.
  * [22] Romuald Debruyne and Christian Bessière.  Some Practicable Filtering Techniques for the Constraint Satisfaction Problem.  In Proc. 15th International Joint Conference on Artificial Intelligence (IJCAI’97), pages 412–417. Morgan Kaufmann, 1997.
  * [23] Tomás Feder and Moshe Y. Vardi.  The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory.  SIAM J. Comput., 28(1):57–104, 1998.  doi:10.1137/S0097539794266766.
  * [24] Michel X. Goemans and David P. Williamson.  Approximation algorithms for Max-3-Cut and other problems via complex semidefinite programming.  J. Comput. Syst. Sci., 68(2):442–470, 2004.  doi:10.1016/J.JCSS.2003.07.012.
  * [25] Venkatesan Guruswami and Yuan Zhou.  Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set.  Theory Comput., 8(1):239–267, 2012.  doi:10.4086/TOC.2012.V008A011.
  * [26] Paul R Halmos.  Introduction to Hilbert space and the theory of spectral multiplicity.  Courier Dover Publications, 2017.
  * [27] Pavol Hell and Jaroslav Nešetřil.  On the complexity of H-coloring.  J. Comb. Theory, Ser. B, 48(1):92–110, 1990.  doi:10.1016/0095-8956(90)90132-J.
  * [28] Pavol Hell and Jaroslav Nešetřil.  Graphs and homomorphisms, volume 28 of Oxford Lecture Series in Mathematics and its Applications.  OUP Oxford, 2004.
  * [29] Peter Jeavons, David A. Cohen, and Marc Gyssens.  How to determine the expressive power of constraints.  Constraints, 4(2):113–131, 1999.  doi:10.1023/A:1009890709297.
  * [30] Peter G. Jeavons, David A. Cohen, and Marc Gyssens.  Closure properties of constraints.  J. ACM, 44(4):527–548, 1997.  doi:10.1145/263867.263489.
  * [31] Zhengfeng Ji.  Binary constraint system games and locally commutative reductions.  2013\.  arXiv:1310.3794.
  * [32] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen.  MIP∗=RE.  Technical report, 2020.  arXiv:2001.04383.
  * [33] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen.  MIP∗ = RE.  Commun. ACM, 64(11):131–138, 2021.  doi:10.1145/3485628.
  * [34] Simon Kochen and E. P. Specker.  The problem of hidden variables in quantum mechanics.  J. Mathematics and Mechanics, 17(1):59–87, 1967.  URL: http://www.jstor.org/stable/24902153.
  * [35] Phokion G. Kolaitis and Moshe Y. Vardi.  On the expressive power of datalog: Tools and a case study.  J. Comput. Syst. Sci., 51(1):110–134, 1995.  doi:10.1006/jcss.1995.1055.
  * [36] Phokion G. Kolaitis and Moshe Y. Vardi.  Conjunctive-query containment and constraint satisfaction.  J. Comput. Syst. Sci., 61(2):302–332, 2000.  doi:10.1006/jcss.2000.1713.
  * [37] Vladimir Kolmogorov, Andrei A. Krokhin, and Michal Rolínek.  The complexity of general-valued CSPs.  SIAM J. Comput., 46(3):1087–1110, 2017.  arXiv:1502.07327, doi:10.1137/16M1091836.
  * [38] Marcin Kozik.  Solving CSPs Using Weak Local Consistency.  SIAM J. Comput., 50(4):1263–1286, 2021.  arXiv:1605.00565, doi:10.1137/18M117577X.
  * [39] Marcin Kozik, Andrei Krokhin, Matt Valeriote, and Ross Willard.  Characterizations of several Maltsev conditions.  Algebra universalis, 73(3):205–224, 2015.  doi:10.1007/s00012-015-0327-2.
  * [40] Benoit Larose and Lázló Zádori.  Bounded width problems and algebras.  Algebra Univers., 56:439–466, 2007.  doi:10.1007/s00012-007-2012-6.
  * [41] Laura Mančinska and David E. Roberson.  Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs.  In Proc. 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS’20), pages 661–672. IEEE, 2020.  doi:10.1109/FOCS46700.2020.00067.
  * [42] Laura Mančinska and David E. Roberson.  Quantum homomorphisms.  J. Comb. Theory, Ser. B, 118:228–267, 2016.  doi:10.1016/J.JCTB.2015.12.009.
  * [43] Miklós Maróti and Ralph McKenzie.  Existence theorems for weakly symmetric operations.  Algebra Univers., 59(3-4):463–489, 2008.  doi:10.1007/s00012-008-2122-9.
  * [44] N. David Mermin.  Simple unified form for the major no-hidden-variables theorems.  Phys. Rev. Lett., 65(27):3373, 1990.  doi:10.1103/PhysRevLett.65.3373.
  * [45] N. David Mermin.  Hidden variables and the two theorems of John Bell.  Rev. Mod. Phys., 65(3):803, 1993.  doi:10.1103/RevModPhys.65.803.
  * [46] Ryan O’Donnell.  Analysis of Boolean Functions.  Cambridge University Press, 2014.
  * [47] Connor Paddock and William Slofstra.  Satisfiability problems and algebras of boolean constraint system games.  2023\.  arXiv:2310.07901.
  * [48] Asher Peres.  Incompatible results of quantum measurements.  Phys. Lett., 151(3-4):107–108, 1990.  doi:10.1016/0375-9601(90)90172-K.
  * [49] E.L. Post.  The two-valued iterative systems of mathematical logic, volume 5 of Annals of Mathematical Studies.  Princeton University Press, 1941.  doi:10.2307/2268608.
  * [50] Prasad Raghavendra.  Optimal algorithms and inapproximability results for every CSP?  In Proc. 40th Annual ACM Symposium on Theory of Computing (STOC’08), pages 245–254. ACM, 2008.  doi:10.1145/1374376.1374414.
  * [51] Thomas Schaefer.  The complexity of satisfiability problems.  In Proc. 10th Annual ACM Symposium on the Theory of Computing (STOC’78), pages 216–226, 1978.  doi:10.1145/800133.804350.
  * [52] William Slofstra.  Tsirelson’s problem and an embedding theorem for groups arising from non-local games.  J. Am. Math. Soc., 33(1):1–56, 2020.  doi:10.1090/jams/929.
  * [53] Johan Thapper and Stanislav Živný.  The complexity of finite-valued CSPs.  J. ACM, 63(4):37:1–37:33, 2016.  arXiv:1210.2987, doi:10.1145/2974019.
  * [54] Johan Thapper and Stanislav Živný.  The power of Sherali–Adams relaxations for general-valued CSPs.  SIAM J. Comput., 46(4):1241–1279, 2017.  arXiv:1606.02577, doi:10.1137/16M1079245.
  * [55] Johan Thapper and Stanislav Živný.  The limits of SDP relaxations for general-valued CSPs.  ACM Trans. Comput. Theory, 10(3):12:1–12:22, 2018.  arXiv:1612.01147, doi:10.1145/3201777.
  * [56] Dmitriy Zhuk.  A proof of CSP dichotomy conjecture.  In Proc. 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS’17), pages 331–342, 2017.  arXiv:1704.01914, doi:10.1109/FOCS.2017.38.
  * [57] Dmitriy Zhuk.  A proof of the CSP dichotomy conjecture.  J. ACM, 67(5):30:1–30:78, 2020.  arXiv:1704.01914, doi:10.1145/3402029.