#  Hierarchies of Minion Tests for PCSPs through Tensors††thanks: An extended
abstract of this work appeared in the Proceedings of the 2023 ACM-SIAM
Symposium on Discrete Algorithms (SODA’23) [45]. The research leading to these
results has received funding from the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation programme (grant
agreement No 714532). The paper reflects only the authors’ views and not the
views of the ERC or the European Commission. The European Union is not liable
for any use that may be made of the information contained therein. This work
was also supported by UKRI EP/X024431/1. 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.

Lorenzo Ciardo
University of Oxford
<EMAIL_ADDRESS>Stanislav Živný
University of Oxford
<EMAIL_ADDRESS>
###### Abstract

We provide a unified framework to study hierarchies of relaxations for
Constraint Satisfaction Problems and their Promise variant. The idea is to
split the description of a hierarchy into an algebraic part, depending on a
_minion_ capturing the “base level”, and a geometric part – which we call
_tensorisation_ – inspired by multilinear algebra. We exploit the geometry of
the tensor spaces arising from our construction to prove general properties of
hierarchies. We identify certain classes of minions, which we call _linear_
and _conic_ , whose corresponding hierarchies have particularly fine features.
We establish that the (combinatorial) bounded width, Sherali-Adams LP, affine
IP, Sum-of-Squares SDP, and combined “LP + affine IP” hierarchies are all
captured by this framework. In particular, in order to analyse the Sum-of-
Squares SDP hierarchy, we also characterise the solvability of the standard
SDP relaxation through a new minion.

##  1 Introduction

What are the limits of efficient algorithms and where is the precise
borderline of tractability? The _constraint satisfaction problem_
($\operatorname{CSP}$) offers a general framework for studying such
fundamental questions for a large class of computational problems [49, 50, 79]
but yet for a class that is amenable to identifying the mathematical structure
governing tractability. Canonical examples of $\operatorname{CSP}$s are
satisfiability or “not-all-equal” satisfiability of 3-CNF formulas (called
3-Sat and 3-Nae-Sat, respectively), linear equations, several variants of
(hyper)graph colourings, and the graph clique problem. All
$\operatorname{CSP}$s can be seen as homomorphism problems between relational
structures [61]: Given two relational structures $\mathbf{X}$ and
$\mathbf{A}$, is there a homomorphism from $\mathbf{X}$ to $\mathbf{A}$?
Intuitively, the structure $\mathbf{X}$ represents the variables of the
$\operatorname{CSP}$ instance and their interactions, whereas the structure
$\mathbf{A}$ represents the constraint language; i.e., the alphabet and the
allowed constraint relations.

The most studied types of $\operatorname{CSP}$s are so-called _non-uniform_
$\operatorname{CSP}$s [70, 61, 76, 16], in which the target structure
$\mathbf{A}$ is fixed whereas the source structure $\mathbf{X}$ is given on
input; this computational problem is denoted by
$\operatorname{CSP}(\mathbf{A})$. From the examples above, 3-Sat, 3-Nae-Sat,
(hyper)graph colourings with constantly many colours, linear equations of
bounded width over finite fields, and linear equations of bounded width over
the rationals are all examples of non-uniform $\operatorname{CSP}$s, all on
finite domains except the last one [23, 18, 22]. For instance, in the graph
$c$-colouring problem the target structure $\mathbf{A}$ is a $c$-clique and
the structure $\mathbf{X}$ is the input graph. The existence of a homomorphism
from a graph to a $c$-clique is equivalent to the existence of a colouring of
the graph with $c$ colours. The graph clique problem is an example of a
$\operatorname{CSP}$ with a fixed class of source structures [64, 89] but an
arbitrary target structure and, thus, it is not a non-uniform
$\operatorname{CSP}$.

We will be concerned with polynomial-time tractability of
$\operatorname{CSP}$s. Studied research directions include investigating
questions such as: Is there a solution [37, 97]? How many solutions are there,
exactly [48, 36, 59] or approximately [38, 41]? What is the maximum number of
simultaneously satisfied constraints, exactly [47, 69, 94] or approximately
[56, 7, 91]? What is the minimum number of simultaneously unsatisfied
constraints [72, 54]? Given an almost satisfiable instance, can one find a
somewhat satisfying solution [53, 14, 52]? In this paper, we will focus on the
following question:

_Given a satisfiable instance, can one find a solution that is satisfying in a
weaker sense_ [9, 12, 26]?

This was formalised as _promise constraint satisfaction problems_
($\operatorname{PCSP}$s) by Austrin, Guruswami and Håstad [9] and Brakensiek
and Guruswami [26]. Let $\mathbf{A}$ and $\mathbf{B}$ be two fixed relational
structures111Unless otherwise stated, we shall use the word “structure” to
mean finite-domain structures; if the domain is allowed to be infinite, we
shall say it explicitly. such that there is a homomorphism from $\mathbf{A}$
to $\mathbf{B}$, indicated by $\mathbf{A}\to\mathbf{B}$. Intuitively, the
structure $\mathbf{A}$ represents the “strict” constraints and the structure
$\mathbf{B}$ represents the corresponding “weak” constraints. An instance of
the $\operatorname{PCSP}$ over the template $(\mathbf{A},\mathbf{B})$, denoted
by $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, is a relational structure
$\mathbf{X}$ such that there is a homomorphism from $\mathbf{X}$ to
$\mathbf{A}$. The task is to find a homomorphism from $\mathbf{X}$ to
$\mathbf{B}$, which exists by the composition of the two promised
homomorphisms. What we described above is the _search_ variant of the PCSP. In
the _decision_ variant, one is given a relational structure $\mathbf{X}$ and
the task is to decide whether there is a homomorphism from $\mathbf{X}$ to
$\mathbf{A}$ or whether there is not a homomorphism from $\mathbf{X}$ to
$\mathbf{B}$. Note that since homomorphisms compose, if
$\mathbf{X}\to\mathbf{A}$ then also $\mathbf{X}\to\mathbf{B}$. Thus, the two
cases cannot happen simultaneously. It is known that the decision variant of
the PCSP reduces to the search variant [12], but it is not known whether there
is a reduction in the other direction for all PCSPs. In this paper, we shall
use the decision variant.

$\operatorname{PCSP}$s are a vast generalisation of $\operatorname{CSP}$s
including problems that cannot be expressed as $\operatorname{CSP}$s. The work
of Barto, Bulín, Krokhin, and Opršal [12] lifted and greatly extended the
algebraic framework developed for $\operatorname{CSP}$s [70, 35, 17] to the
realm of $\operatorname{PCSP}$s. Subsequently, there has been a series of
recent works on the computational complexity of $\operatorname{PCSP}$s
building on [12], including applicability of local consistency and convex
relaxations [25, 30, 39, 44, 5] and complexity of fragments of
$\operatorname{PCSP}$s [66, 80, 2, 11, 31, 27, 15, 90]. Strong results on
$\operatorname{PCSP}$s have also been established via other techniques than
those in [12], mostly analytical methods, e.g., hardness of various
(hyper)graph colourings [73, 58, 68, 8] and other $\operatorname{PCSP}$s [20,
33, 28, 21].

An example of a $\operatorname{PCSP}$, identified in [9], is (in the search
variant) finding a satisfying assignment to a $k$-CNF formula given that a
$g$-satisfying assignment exists; i.e., an assignment that satisfies at least
$g$ literals in each clause. Austrin et al. established that this problem is
NP-hard if $g/k<1/2$ and solvable via a constant level of the Sherali-Adams
linear programming relaxation otherwise [9]. This classification was later
extended to problems over arbitrary finite domains by Brandts et al. [31].

A second example of a $\operatorname{PCSP}$, identified in [26], is (in the
search variant) finding a “not-all-equal” assignment to a monotone $3$-CNF
formula given that a “$1$-in-$3$” assignment is promised to exist; i.e., given
a $3$-CNF formula with positive literals only and the promise that an
assignment exists that satisfies exactly one literal in each clause, the task
is to find an assignment that satisfies one or two literals in each clause.
This problem is solvable in polynomial time via a constant level of the
Sherali-Adams linear programming relaxation [26] but not via a reduction to
finite-domain $\operatorname{CSP}$s [12].

A third example of a $\operatorname{PCSP}$ is the well-known _approximate
graph colouring_ problem: Given a $c$-colourable graph, find a $d$-colouring
of it, for constants $c$ and $d$ with $c\leq d$. This corresponds to
$\operatorname{PCSP}(\mathbf{K}_{c},\mathbf{K}_{d})$, where $\mathbf{K}_{p}$
is the clique on $p$ vertices. Despite a long history dating back to 1976
[62], the complexity of this problem is only understood under stronger
assumptions [57, 66, 32] and for special cases [71, 73, 65, 68, 24, 12, 80].
It is believed that the problem is NP-hard already in the decision variant
[62], i.e., deciding whether a graph is $c$-colourable or not even
$d$-colourable, for each $3\leq c\leq d$. By using the framework developed in
the current work, non-solvability of approximate graph colouring through
standard algorithmic techniques was established in the follow-up works [42,
43].

Like all decision problems, $\operatorname{PCSP}$s can be solved by designing
_tests_. If a test, applied to a given instance of the problem, is positive
then the answer is Yes; if it is negative then the answer is No. The challenge
is then to find tests that are able to guarantee a low number – ideally, zero
– of false positives and false negatives. Clearly, a test is itself a decision
problem. However, its nature may be substantially different, and less
complicated, than the nature of the original problem.

Given a $\operatorname{PCSP}$ template $(\mathbf{A},\mathbf{B})$, we may use
any (potentially infinite) structure $\mathbf{T}$ to make a test for
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$: We simply let the outcome of the
test on an instance structure $\mathbf{X}$ be Yes if
$\mathbf{X}\to\mathbf{T}$, and No if $\mathbf{X}\not\to\mathbf{T}$. In other
words, $\operatorname{CSP}(\mathbf{T})$ is a test for
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$. Let $\mathbf{X}$ be an instance
of $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$. If $\mathbf{X}\to\mathbf{T}$
whenever $\mathbf{X}\to\mathbf{A}$, the test is guaranteed not to generate
false negatives, and we call it _complete_. Since homomorphisms compose, if
$\mathbf{A}\to\mathbf{T}$ the test is automatically complete. If
$\mathbf{X}\to\mathbf{B}$ whenever $\mathbf{X}\to\mathbf{T}$, the test is
guaranteed not to generate false positives, and we call it _sound_. If both of
these conditions hold, we say that the test _solves_
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$. Notice that, in this case, one
obtains a reduction from $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ to
$\operatorname{CSP}(\mathbf{T})$. These two types of computational problems –
the original problem and the test – have different algebraic natures. The
complexity of both $\operatorname{CSP}$s and $\operatorname{PCSP}$s was shown
to be determined by higher-order symmetries of the solution sets of the
problems, known as _polymorphisms_ , denoted by
$\operatorname{Pol}(\mathbf{A})$ for $\operatorname{CSP}(\mathbf{A})$ [35] and
by $\operatorname{Pol}(\mathbf{A},\mathbf{B})$ for
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ [12]. For $\operatorname{CSP}$s,
polymorphisms form _clones_ ; in particular, they are closed under
composition. This means that some symmetries may be obtainable through
compositions of other symmetries, so that one can hope to capture properties
of entire families of $\operatorname{CSP}$s (e.g., bounded width,
tractability, etc.) through the presence of a certain polymorphism and, more
generally, to describe their complexity through universal-algebraic tools. A
chief example of this approach is the positive resolution of the dichotomy
conjecture for $\operatorname{CSP}$s by Bulatov [37] and Zhuk [97],
establishing that finite-domain non-uniform $\operatorname{CSP}$s are either
in P or are NP-complete. For $\operatorname{PCSP}$s, however, polymorphisms
are not closed under composition, and the algebraic structure they are endowed
with – known as _minion_ – is much less rich and, apparently, harder to
understand through the lens of universal algebra.

To make a test $\mathbf{T}$ useful as a polynomial-time algorithm to solve a
$\operatorname{PCSP}$, one requires that $\operatorname{CSP}(\mathbf{T})$
should be tractable. It was conjectured in [25] that every tractable (finite-
domain) $\operatorname{PCSP}$ is solved by a tractable test. In other words,
if the conjecture is true, _tests are the sole source of tractability for
PCSPs_. For the conjecture to be true, one needs to admit tests on infinite
domains: As shown in [12], the $\operatorname{PCSP}$ template
$(\mathbf{1}\textbf{-in-}\mathbf{3},\mathbf{NAE})$ does not admit a finite-
domain tractable test; i.e., there is no (finite) structure $\mathbf{T}$ such
that $\mathbf{1}\textbf{-in-}\mathbf{3}\to\mathbf{T}\to\mathbf{NAE}$ and
$\operatorname{CSP}(\mathbf{T})$ is tractable.

For a PCSP template $(\mathbf{A},\mathbf{B})$, one would ideally aim to build
tests for $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ in a systematic way.
One method to do so is by considering tests associated with minions and, in
particular, their _free structures_. The free structure
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})$ of a minion ${\mathscr{M}}$ generated
by a structure $\mathbf{A}$ [12] is a (potentially infinite) structure
obtained, essentially, by simulating the relations in $\mathbf{A}$ on a domain
consisting of elements of ${\mathscr{M}}$. Then, we define
$\operatorname{Test}_{{\mathscr{M}}}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ if
$\mathbf{X}\to\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})$, and No otherwise. (Note
that $\mathbf{X}$ is the input to the problem; the minion ${\mathscr{M}}$ and
the relational structure $\mathbf{A}$, coming from a $\operatorname{PCSP}$
template, are (fixed) parameters of the test.)

For certain choices of ${\mathscr{M}}$, $\operatorname{Test}_{{\mathscr{M}}}$
is a tractable test; i.e.,
$\operatorname{CSP}(\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}))$ is tractable for
any $\mathbf{A}$. This is the case for the minions
$\mathscr{H}=\operatorname{Pol}(\textsc{Horn-3-Sat})$ (whose elements are
nonempty subsets of a given set), ${\mathscr{Q}_{\operatorname{conv}}}$ (whose
elements are stochastic vectors), and ${\mathscr{Z}_{\operatorname{aff}}}$
(whose elements are affine integers vectors). As it was shown in [12], these
three minions correspond to three well-studied algorithmic relaxations:
$\operatorname{Test}_{\mathscr{H}}$ is Arc Consistency ($\operatorname{AC}$)
[87], $\operatorname{Test}_{{\mathscr{Q}_{\operatorname{conv}}}}$ is the Basic
Linear Programming relaxation ($\operatorname{BLP}$) [81], and
$\operatorname{Test}_{{\mathscr{Z}_{\operatorname{aff}}}}$ is the Affine
Integer Programming relaxation (${\mathscr{Z}_{\operatorname{aff}}}$) [25]. In
[30], the algorithm $\operatorname{BLP}+\operatorname{AIP}$ (which we shall
call $\operatorname{BA}$ in this work) corresponding to a combination of
linear and integer programming was shown to be captured by a certain minion
$\mathscr{M}_{\operatorname{BA}}$. In summary, several widely used algorithms
for $\operatorname{(P)CSPs}$ are minion tests; in particular, Arc Consistency,
which is the simplest example of consistency algorithms, and standard
algorithms based on relaxations.

Convex relaxations have been instrumental in the understanding of the
complexity of many variants of $\operatorname{CSP}$s, including constant
approximability of Min-$\operatorname{CSP}$s [60, 54] and
Max-$\operatorname{CSP}$s [74, 91], robust satisfiability of
$\operatorname{CSP}$s [98, 81, 14], and exact solvability of optimisation
$\operatorname{CSP}$s [77, 95]. An important line of work focused on making
convex relaxations stronger and stronger via the so-called “lift-and-project”
method, which includes the Sherali-Adams LP hierarchy [93], the SDP hierarchy
of Lovász and Schrijver [86], and the (stronger) SDP hierarchy of Lasserre
[82], also known as the Sum-of-Squares hierarchy (see [83] for a comparison of
these hierarchies). The study of the power of various convex hierarchies has
led to several breakthroughs, e.g., [1, 40, 78, 63, 96, 84].

In the same spirit as lift-and-project hierarchies of convex relaxations, the
(combinatorial) $k$-consistency algorithm (also known as the $k$-bounded width
algorithm) has a central role in the study of tractability for constraint
satisfaction problems [61, 3]. Here $k$ is an integer bounding the number of
variables considered in reasoning about partial solutions; the case $k=1$
corresponds to Arc Consistency mentioned above. The notion of local
consistency, in addition to being one of the key concepts in constraint
satisfaction, has also emerged independently in finite model theory [75],
graph theory [67], and proof complexity [4]. The power of local consistency
for CSPs is now fully understood [34, 13, 10]. Recent work identified a
necessary condition on local consistency to solve PCSPs [5].

#### Contributions

The main contribution of this work is the introduction of _a general framework
for refining algorithmic relaxations of $\operatorname{(P)CSPs}$_. Given a
minion ${\mathscr{M}}$, we present a technique to systematically turn
$\operatorname{Test}_{{\mathscr{M}}}$ into the corresponding _hierarchy of
minion tests_ : a sequence of increasingly tighter relaxations
$\operatorname{Test}_{{\mathscr{M}}}^{k}$ for $k\in\mathbb{N}$.

The technique we adopt to build hierarchies of minion tests is inspired by
multilinear algebra. We describe a _tensorisation_ construction that turns a
given structure $\mathbf{X}$ into a structure
$\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
on a different signature, where both the domain and the relations are
multidimensional objects living in tensor spaces. Essentially,
$\operatorname{Test}_{{\mathscr{M}}}^{k}$ works by applying
$\operatorname{Test}_{{\mathscr{M}}}$ to _tensorised_ versions of the
structures $\mathbf{X}$ and $\mathbf{A}$ rather than to $\mathbf{X}$ and
$\mathbf{A}$ themselves. This allows us to study the functioning of the
algorithms in the hierarchy by describing the geometry of a space of tensors –
which can be accomplished by using multilinear algebra. As far as we know,
this approach has not appeared in the literature on Sherali-Adams, bounded
width, Sum-of-Squares, hierarchies of integer programming, and related
algorithmic techniques such as the high-dimensional Weisfeiler-Leman algorithm
[6, 39].222Butti and Dalmau [39] recently characterised for
$\operatorname{CSP}$s when the $k$-th level of the Sherali-Adams LP
programming hierarchy accepts in terms of a construction different from the
one introduced in this work. Unlike the tensorisation, the construction
considered in [39] yields a relational structure whose domain includes the set
of constraints of the original structure.

One key feature of our framework is that it is _modular_ , in that it allows
splitting the description of a hierarchy of minion tests into an _algebraic_
part, corresponding to the minion ${\mathscr{M}}$, and a _geometric_ part,
entirely dependent on the tensorisation construction and hence common to all
hierarchies. By considering certain well-behaved families of minions, which we
call _linear_ and _conic_ , we can then deduce general properties of the
corresponding hierarchies by only focussing on the geometry of spaces of
tensors.

Letting the minion ${\mathscr{M}}$ be $\mathscr{H}$ (resp.,
${\mathscr{Q}_{\operatorname{conv}}}$, ${\mathscr{Z}_{\operatorname{aff}}}$),
we shall retrieve in this way the bounded width hierarchy (resp., the Sherali-
Adams LP hierarchy, the affine integer programming hierarchy). Additionally,
we describe a new minion ${\mathscr{S}}$ capturing the power of the basic
semidefinite programming relaxation ($\operatorname{SDP}$),333In the recent
paper [29], Brakensiek, Guruswami, and Sandeep independently provided a
characterisation for the power of $\operatorname{SDP}$ that is similar to the
one we obtain in the current work. and we show that
$\operatorname{Test}_{{\mathscr{S}}}^{k}$ coincides with the Sum-of-Squares
hierarchy. As a consequence, our framework is able to provide a unified
description of all these four well-known hierarchies of algorithmic
relaxations. In addition to casting _known_ hierarchies of relaxations as
hierarchies of minion tests, this approach can be used to design _new_
hierarchies. In particular, we describe an operation that we call _semi-direct
product_ of minions, which consists in combining multiple minions to form a
new minion associated with a stronger relaxation. In practice, this method can
be used to design an algorithm that combines the features of different known
algorithmic techniques. We show that the minion
$\mathscr{M}_{\operatorname{BA}}$ associated with the $\operatorname{BA}$
relaxation from [30] is the semi-direct product of
${\mathscr{Q}_{\operatorname{conv}}}$ and
${\mathscr{Z}_{\operatorname{aff}}}$, and we formally introduce the
$\operatorname{BA}^{k}$ hierarchy as the hierarchy
$\operatorname{Test}_{\mathscr{M}_{\operatorname{BA}}}^{k}$.

The scope of this framework is potentially not limited to constraint
satisfaction: The multilinear pattern that we found at the core of different
algorithmic hierarchies appears to be transversal to the constraint
satisfaction setting and, instead, inherently connected to the algorithmic
techniques themselves, which can be applied to classes of computational
problems living beyond the realms of
($\operatorname{P}$)$\operatorname{CSP}$s.

#### Subsequent work

The tensorisation methodology introduced in this paper has later been used by
the authors in follow-up work on the applicability of relaxation hierarchies
to specific problems. In particular, they have shown that the approximate
graph colouring problem is not solved by the affine integer programming
hierarchy [42] and not even by the (stronger) hierarchy for the combined basic
linear programming and affine integer programming relaxation [43]. In the very
recent paper [55], various concepts introduced in this work – in particular,
the concept of conic minions – were shown to play an important role for the
description of a certain type of reductions between (P)CSPs (cf. Remark 45).

##  2 Background

#### Notation

We denote by $\mathbb{N}$ the set of positive integers. For $k\in\mathbb{N}$,
we denote by $[k]$ the set $\\{1,\ldots,k\\}$. We indicate by $\mathbf{e}_{i}$
the $i$-th standard unit vector of the appropriate size (which will be clear
from the context); i.e., the $i$-th entry of $\mathbf{e}_{i}$ is $1$, and all
other entries are $0$. $\mathbf{0}_{p}$ and $\mathbf{1}_{p}$ denote the all-
zero and all-one vector of size $p$, respectively, while $I_{p}$ and $O_{p,q}$
denote the $p\times p$ identity matrix and the $p\times q$ all-zero matrix,
respectively. Given a matrix $M$, we let $\operatorname{tr}(M)$ and
$\operatorname{csupp}(M)$ be the trace and the set of indices of nonzero
columns of $M$, respectively. The symbol ${\aleph_{0}}$ denotes the
cardinality of $\mathbb{N}$.

#### Promise CSPs

A signature $\sigma$ is a finite set of relation symbols $R$, each with arity
$\operatorname{ar}(R)\in\mathbb{N}$. A $\sigma$-structure $\mathbf{A}$
consists of a domain (universe) $A$ and, for each $R\in\sigma$, a relation
$R^{\mathbf{A}}\subseteq A^{\operatorname{ar}(R)}$. A $\sigma$-structure
$\mathbf{A}$ is finite if the size $|A|$ of its domain $A$ is finite. In this
case, we often assume that the domain of $\mathbf{A}$ is $A=[n]$.

Let $\mathbf{A}$ and $\mathbf{B}$ be $\sigma$-structures. A _homomorphism_
from $\mathbf{A}$ to $\mathbf{B}$ is a map $h:A\to B$ such that, for each
$R\in\sigma$ with $r=\operatorname{ar}(R)$ and for each
$\mathbf{a}=(a_{1},\ldots,a_{r})\in A^{r}$, if $\mathbf{a}\in R^{\mathbf{A}}$
then $h(\mathbf{a})=(h(a_{1}),\ldots,h(a_{r}))\in R^{\mathbf{B}}$. We denote
the existence of a homomorphism from $\mathbf{A}$ to $\mathbf{B}$ by
$\mathbf{A}\to\mathbf{B}$. A pair of $\sigma$-structures
$(\mathbf{A},\mathbf{B})$ with $\mathbf{A}\to\mathbf{B}$ is called a _promise
constraint satisfaction problem_ ($\operatorname{PCSP}$) _template_. The
$\operatorname{PCSP}$ problem parameterised by the template
$(\mathbf{A},\mathbf{B})$, denoted by
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, is the following computational
problem: The input is a $\sigma$-structure $\mathbf{X}$ and the goal is to
answer Yes if $\mathbf{X}\to\mathbf{A}$ and No if
$\mathbf{X}\not\to\mathbf{B}$. The promise is that it is not the case that
$\mathbf{X}\not\to\mathbf{A}$ and $\mathbf{X}\to\mathbf{B}$. We write
$\operatorname{CSP}(\mathbf{A})$ for
$\operatorname{PCSP}(\mathbf{A},\mathbf{A})$, the classic (non-promise)
constraint satisfaction problem.

#### Relaxations and hierarchies

The following relaxations of $\operatorname{(P)CSPs}$ shall be mentioned in
this paper: Arc Consistency ($\operatorname{AC}$) is a propagation algorithm
that checks for the existence of assignments satisfying the local constraints
of the given $\operatorname{(P)CSP}$ instance [87]; the basic linear
programming ($\operatorname{BLP}$) relaxation looks for compatible probability
distributions on assignments [81]; the affine integer programming
($\operatorname{AIP}$) relaxation turns the constraints into linear equations,
that can be solved over the integers using (a variant of) Gaussian elimination
[25]; the basic semidefinite programming ($\operatorname{SDP}$) relaxation is
essentially a strengthening of $\operatorname{BLP}$, where probabilities are
replaced by vectors satisfying orthogonality requirements [91]; the combined
basic linear programming and affine integer programming ($\operatorname{BA}$)
relaxation is a hybrid algorithm blending $\operatorname{BLP}$ and
$\operatorname{AIP}$ [30].

In this work, we shall mainly focus on algorithmic _hierarchies_. The bounded
width ($\operatorname{BW}^{k}$) hierarchy (also known as local consistency
checking algorithm) refines $\operatorname{AC}$ by propagating local solutions
over bigger and bigger portions of the instance, while the Sherali-Adams LP
($\operatorname{SA}^{k}$), affine integer programming
($\operatorname{AIP}^{k}$), Sum-of-Squares ($\operatorname{SoS}^{k}$), and
combined basic linear programming and affine integer programming
($\operatorname{BA}^{k}$) hierarchies strengthen the $\operatorname{BLP}$,
$\operatorname{AIP}$, $\operatorname{SDP}$, and $\operatorname{BA}$
relaxations, respectively, by looking for compatible distributions over bigger
and bigger assignments.

The five hierarchies mentioned above, as well as the $\operatorname{SDP}$
relaxation, are described in Section 4.2 (see also the discussion in Appendix
A). We refer to [12] for $\operatorname{AC}$, $\operatorname{BLP}$, and
$\operatorname{AIP}$, and to [30] for $\operatorname{BA}$.

#### Algebraic approach to PCSPs

The algebraic theory of $\operatorname{PCSP}$s developed in [12] relies on the
notions of polymorphism and minion. Let $\mathbf{A}$ be a $\sigma$-structure.
For $L\in\mathbb{N}$, the _$L$ -th power_ of $\mathbf{A}$ is the
$\sigma$-structure $\mathbf{A}^{L}$ with domain $A^{L}$ whose relations are
defined as follows: Given $R\in\sigma$ and an $L\times\operatorname{ar}(R)$
matrix $M$ such that all rows of $M$ are tuples in $R^{\mathbf{A}}$, the
columns of $M$ form a tuple in $R^{\mathbf{A}^{L}}$. An $L$-ary _polymorphism_
of a $\operatorname{PCSP}$ template $(\mathbf{A},\mathbf{B})$ is a
homomorphism from $\mathbf{A}^{L}$ to $\mathbf{B}$. Minions were defined in
[12] as sets of functions with certain properties. We shall use here the
abstract definition of minions, as first done in [30], cf. also [44]. A
_minion_ $\mathscr{M}$ consists in the disjoint union of nonempty sets
$\mathscr{M}^{(L)}$ for $L\in\mathbb{N}$ equipped with (so-called _minor_)
operations
$(\cdot)_{/\pi}:\mathscr{M}^{(L)}\rightarrow\mathscr{M}^{(L^{\prime})}$ for
all functions $\pi:[L]\rightarrow[L^{\prime}]$, which satisfy
$M_{/\operatorname{id}}=M$ and, for $\pi:[L]\rightarrow[L^{\prime}]$ and
$\tilde{\pi}:[L^{\prime}]\rightarrow[L^{\prime\prime}]$,
$(M_{/\pi})_{/\tilde{\pi}}=M_{/\tilde{\pi}\circ\pi}$ for all
$M\in\mathscr{M}^{(L)}$.

######  Example 1.

The set $\operatorname{Pol}(\mathbf{A},\mathbf{B})$ of all polymorphisms of a
$\operatorname{PCSP}$ template $(\mathbf{A},\mathbf{B})$ is a minion with the
minor operations defined by
$f_{/\pi}(a_{1},\dots,a_{L^{\prime}})=f(a_{\pi(1)},\dots,a_{\pi(L)})$ for
$f:\mathbf{A}^{L}\to\mathbf{B}$ and $\pi:[L]\to[L^{\prime}]$. In this minion,
the minor operations correspond to identifying coordinates, permuting
coordinates, and introducing dummy coordinates (of polymorphisms).

######  Example 2.

Other examples of minions that shall appear frequently in this work are
${\mathscr{Q}_{\operatorname{conv}}}$, ${\mathscr{Z}_{\operatorname{aff}}}$,
and $\mathscr{H}$, capturing the power of the algorithms $\operatorname{BLP}$,
$\operatorname{AIP}$, and $\operatorname{AC}$, respectively. The $L$-ary
elements of ${\mathscr{Q}_{\operatorname{conv}}}$ are rational vectors of size
$L$ that are stochastic (i.e., whose entries are nonnegative and sum up to
$1$), with the minor operations defined as follows: For
$\mathbf{q}\in{\mathscr{Q}_{\operatorname{conv}}}^{(L)}$ and
$\pi:[L]\to[L^{\prime}]$, $\mathbf{q}_{/\pi}=P\mathbf{q}$, where $P$ is the
$L^{\prime}\times L$ matrix whose $(i,j)$-th entry is $1$ if $\pi(j)=i$, and
$0$ otherwise. ${\mathscr{Z}_{\operatorname{aff}}}$ is defined similarly to
${\mathscr{Q}_{\operatorname{conv}}}$, the only difference being that its
$L$-ary elements are affine integer vectors (i.e., their entries are integer –
possibly negative – numbers and sum up to $1$). $\mathscr{H}$ is the minion of
polymorphisms of the $\operatorname{CSP}$ template Horn-3-Sat, i.e., the
Boolean structure whose four relations are “$x\wedge y\Rightarrow z$”,
“$x\wedge y\Rightarrow\neg z$”, $\\{0\\}$, and $\\{1\\}$. Equivalently (cf.
[12]), $\mathscr{H}$ can be described as follows: For any $L\in\mathbb{N}$,
the $L$-ary elements of $\mathscr{H}$ are Boolean functions of the form
$f_{Z}(x_{1},\dots,x_{L})=\bigwedge_{z\in Z}x_{z}$ for any $Z\subseteq[L]$,
$Z\neq\emptyset$; the minor operations are defined as in Example 1. We shall
also mention the minion $\mathscr{M}_{\operatorname{BA}}$ capturing the
algorithm $\operatorname{BA}$. Its $L$-ary elements are $L\times 2$ matrices
whose first column $\mathbf{u}$ belongs to
${\mathscr{Q}_{\operatorname{conv}}}^{(L)}$ and whose second column
$\mathbf{v}$ belongs to ${\mathscr{Z}_{\operatorname{aff}}}^{(L)}$, and such
that if the $i$-th entry of $\mathbf{u}$ is zero then the $i$-th entry of
$\mathbf{v}$ is also zero, for each $i\in[L]$. The minor operation is defined
on each column individually; i.e.,
$[\begin{array}[]{cc}\mathbf{u}&\mathbf{v}\end{array}]_{/\pi}=[\begin{array}[]{cc}\mathbf{u}_{/\pi}&\mathbf{v}_{/\pi}\end{array}]$.

For two minions $\mathscr{M}$ and $\mathscr{N}$, a _minion homomorphism_
$\xi:\mathscr{M}\rightarrow\mathscr{N}$ is a map that preserves arities and
minors: Given $M\in\mathscr{M}^{(L)}$ and $\pi:[L]\rightarrow[L^{\prime}]$,
$\xi(M)\in\mathscr{N}^{(L)}$ and $\xi(M_{/\pi})=\xi(M)_{/\pi}$. We denote the
existence of a minion homomorphism from $\mathscr{M}$ to $\mathscr{N}$ by
$\mathscr{M}\to\mathscr{N}$.

We will also need the concept of free structure from [12]. Let $\mathscr{M}$
be a minion and let $\mathbf{A}$ be a (finite) $\sigma$-structure. The _free
structure_ of $\mathscr{M}$ generated by $\mathbf{A}$ is a $\sigma$-structure
$\mathbb{F}_{\mathscr{M}}(\mathbf{A})$ with domain $\mathscr{M}^{(|A|)}$
(potentially infinite). Given a relation symbol $R\in\sigma$ of arity $r$, a
tuple $(M_{1},\dots,M_{r})$ of elements of $\mathscr{M}^{(|A|)}$ belongs to
$R^{\mathbb{F}_{\mathscr{M}}(\mathbf{A})}$ if and only if there is some
$Q\in\mathscr{M}^{(|R^{\mathbf{A}}|)}$ such that $M_{i}=Q_{/\pi_{i}}$ for each
$i\in[r]$, where $\pi_{i}:R^{\mathbf{A}}\to A$ maps $\mathbf{a}\in
R^{\mathbf{A}}$ to its $i$-th coordinate $a_{i}$. The definition of free
structure may at this point strike the reader as rather abstract. We shall see
that if we consider certain quite general classes of minions then this object
unveils an interesting geometric description of linear and multilinear nature.

##  3 Overview of results and techniques

Let $(\mathbf{A},\mathbf{B})$ be a $\operatorname{PCSP}$ template. As
discussed in Section 1, any (potentially infinite) structure $\mathbf{T}$ on
the same signature as $\mathbf{A}$ and $\mathbf{B}$ can be viewed as a test
for the computational problem $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$:
Given an instance $\mathbf{X}$, the test returns Yes if
$\mathbf{X}\to\mathbf{T}$, and No otherwise. As the next definition
illustrates, minions provide a systematic method to build tests for
$\operatorname{PCSPs}$.

######  Definition 3.

Let ${\mathscr{M}}$ be a minion. The _minion test_
$\operatorname{Test}_{{\mathscr{M}}}$ is the computational problem defined as
follows: Given two $\sigma$-structures $\mathbf{X}$ and $\mathbf{A}$, return
Yes if $\mathbf{X}\to\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})$, and No
otherwise.

If $\mathbf{X}$ is an instance of $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$
for some template $(\mathbf{A},\mathbf{B})$, we write
$\operatorname{Test}_{{\mathscr{M}}}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ if
$\operatorname{Test}_{{\mathscr{M}}}$ applied to $\mathbf{X}$ and $\mathbf{A}$
returns Yes (i.e., if $\mathbf{X}\to\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})$),
and we write
$\operatorname{Test}_{{\mathscr{M}}}(\mathbf{X},\mathbf{A})=\textsc{No}$
otherwise. Note that, in the expression
“$\operatorname{Test}_{{\mathscr{M}}}(\mathbf{X},\mathbf{A})$”, $\mathbf{X}$
is the input structure of the $\operatorname{PCSP}$, while $\mathbf{A}$ is the
fixed structure from the $\operatorname{PCSP}$ template.

Leaving $\operatorname{SDP}$ aside for the moment, it turns out that the
algebraic structure lying at the core of all relaxations mentioned in Section
2, of seemingly different nature, is the same, as all of them are minion tests
for specific minions.

######  Theorem 4 ([12, 30]).

$\operatorname{AC}=\operatorname{Test}_{\mathscr{H}}$,
$\operatorname{BLP}=\operatorname{Test}_{{\mathscr{Q}_{\operatorname{conv}}}}$,
$\operatorname{AIP}=\operatorname{Test}_{{\mathscr{Z}_{\operatorname{aff}}}}$,
$\operatorname{BA}=\operatorname{Test}_{\mathscr{M}_{\operatorname{BA}}}$.

One reason why minion tests are an interesting type of tests is that they are
always complete.

######  Proposition 5.

$\operatorname{Test}_{{\mathscr{M}}}$ is complete for any minion
${\mathscr{M}}$; i.e., for any $\mathbf{X}$ and $\mathbf{A}$ with
$\mathbf{X}\to\mathbf{A}$, we have
$\mathbf{X}\to\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})$.

A second feature of minion tests is that their soundness can be characterised
algebraically, as stated in the next proposition and shown easily using a
compactness argument from [88], cf. [12].

######  Proposition 6.

Let ${\mathscr{M}}$ be a minion and let $(\mathbf{A},\mathbf{B})$ be a
$\operatorname{PCSP}$ template. Then, $\operatorname{Test}_{{\mathscr{M}}}$
solves $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if and only if
${\mathscr{M}}\to\operatorname{Pol}(\mathbf{A},\mathbf{B})$.

###  3.1 A minion for SDP

The first contribution of this work is to design a minion ${\mathscr{S}}$
capturing the power of $\operatorname{SDP}$, thus showing that, similarly to
$\operatorname{AC}$, $\operatorname{BLP}$, $\operatorname{AIP}$, and
$\operatorname{BLP}+\operatorname{AIP}$, also $\operatorname{SDP}$ is a minion
test.

######  Definition 7.

For $L\in\mathbb{N}$, let ${\mathscr{S}}^{(L)}$ be the set of real
$L\times{\aleph_{0}}$ matrices ${M}$ such that

$\displaystyle\mbox{(C1)}\;\operatorname{csupp}(M)\mbox{ is finite}$
$\displaystyle\mbox{(C2)}\;{M}{M}^{T}\mbox{ is a diagonal matrix}$
$\displaystyle\mbox{(C3)}\;\operatorname{tr}({M}{M}^{T})=1.$ (1)

Given a function $\pi:[L]\rightarrow[L^{\prime}]$ and a matrix
${M}\in{\mathscr{S}}^{(L)}$, we let ${M}_{/\pi}=P{M}$, where $P$ is the
$L^{\prime}\times L$ matrix whose $(i,j)$-th entry is $1$ if $\pi(j)=i$, and
$0$ otherwise. We set
${\mathscr{S}}=\bigsqcup_{L\in\mathbb{N}}{\mathscr{S}}^{(L)}$.

In Section 6, we shall prove that the object defined above is indeed a minion
and that it captures the power of the $\operatorname{SDP}$ relaxation, as
stated below.

######  Proposition 8.

$\operatorname{SDP}=\operatorname{Test}_{{\mathscr{S}}}$. In other words,
given two $\sigma$-structures $\mathbf{X}$ and $\mathbf{A}$,
$\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ if and only if
$\mathbf{X}\to\mathbb{F}_{{\mathscr{S}}}(\mathbf{A})$.

Using Proposition 6, we obtain a characterisation of the power of the SDP
relaxation.

######  Theorem 9.

Let $(\mathbf{A},\mathbf{B})$ be a $\operatorname{PCSP}$ template. Then,
$\operatorname{SDP}$ solves $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if
and only if ${\mathscr{S}}\to\operatorname{Pol}(\mathbf{A},\mathbf{B})$.

###  3.2 Tensorisation

As discussed earlier, minions give a systematic method for designing tests for
$\operatorname{(P)CSPs}$. We now describe a construction, which we call
_tensorisation_ , that provides a technique to systematically refine minion
tests, thus creating hierarchies of progressively stronger algorithms.

Let $S$ be a set and let $k\in\mathbb{N}$. For
$\mathbf{n}=(n_{1},\dots,n_{k})\in\mathbb{N}^{k}$,
$\mathcal{T}^{\mathbf{n}}(S)$ denotes the set of all functions from
$[n_{1}]\times\dots\times[n_{k}]$ to $S$, which we visualise as hypermatrices
or tensors. Many of the tensors appearing in this paper are _cubical_ , which
means that $\mathbf{n}=n\cdot\mathbf{1}_{k}=(n,\dots,n)$ is a constant
tuple.444See Section 4.1 for further details on the terminology for tensors.

For $k\in\mathbb{N}$ and a signature $\sigma$,
$\sigma^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$ is
the signature consisting of the same symbols as $\sigma$ such that each symbol
$R$ of arity $r$ in $\sigma$ has arity $r^{k}$ in
$\sigma^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$.

######  Definition 10.

The _$k$ -th tensor power_ of a $\sigma$-structure $\mathbf{A}$ is the
$\sigma^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$-structure
$\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
having domain $A^{k}$ and relations defined as follows: For each symbol
$R\in\sigma$ of arity $r$ in $\sigma$, we set
$R^{\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}=\left\\{\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}:\mathbf{a}\in
R^{\mathbf{A}}\right\\}$, where, for $\mathbf{a}\in R^{\mathbf{A}}$,
$\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
is the tensor in $\mathcal{T}^{r\cdot\mathbf{1}_{k}}(A^{k})$ defined as
follows: For any $(i_{1},i_{2},\dots,i_{k})\in[r]^{k}$, the
$(i_{1},i_{2},\dots,i_{k})$-th element of
$\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
is $(a_{i_{1}},a_{i_{2}},\dots,a_{i_{k}})$.555Using the terminology for
tensors that we shall introduce in Section 4.1,
$\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
can be more compactly defined as follows:
$E_{\mathbf{i}}\ast\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}=\mathbf{a}_{\mathbf{i}}$
for any $\mathbf{i}\in[r]^{k}$.,666We can visualise
$\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
as the formal Segre outer product of $k$ copies of $\mathbf{a}$ (cf. [85]).

Notice that
$\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny1}⃝}}}=\mathbf{A}$.
Also, the function $R^{\mathbf{A}}\to
R^{\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$
given by
$\mathbf{a}\mapsto\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
is a bijection, so the cardinality of
$R^{\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$
equals the cardinality of $R^{\mathbf{A}}$.

######  Example 11.

Let us describe the third tensor power of the $3$-clique – i.e., the structure
$\mathbf{K}_{3}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny3}⃝}}}$.
The domain of
$\mathbf{K}_{3}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny3}⃝}}}$
is $[3]^{3}$, i.e., the set of tuples of elements in $[3]$ having length $3$.
Let $R$ be the symbol corresponding to the binary edge relation in
$\mathbf{K}_{3}$, so that
$R^{\mathbf{K}_{3}}=\\{(1,2),(2,1),(2,3),(3,2),(3,1),(1,3)\\}$. Then,
$R^{\mathbf{K}_{3}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny3}⃝}}}}$
has arity $2^{3}=8$ and it is a subset of
$\mathcal{T}^{2\cdot\mathbf{1}_{3}}([3]^{3})$. Specifically,
$R^{\mathbf{K}_{3}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny3}⃝}}}}=\\{(1,2)^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny3}⃝}}},(2,1)^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny3}⃝}}},(2,3)^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny3}⃝}}},(3,2)^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny3}⃝}}},(3,1)^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny3}⃝}}},(1,3)^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny3}⃝}}}\\}$
where, e.g.,
$(2,3)^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny3}⃝}}}=\left[\begin{array}[]{@{}cc|cc@{}}(2,2,2)&(2,2,3)&(3,2,2)&(3,2,3)\\\
(2,3,2)&(2,3,3)&(3,3,2)&(3,3,3)\end{array}\right]$.777The vertical line
separates the two $2\times 2$ layers of the $2\times 2\times 2$ tensor.

We say that a $\sigma$-structure $\mathbf{A}$ is _$k$ -enhanced_ if $\sigma$
contains a $k$-ary symbol $R_{k}$ such that $R_{k}^{\mathbf{A}}=A^{k}$.
Observe that any two $\sigma$-structures $\mathbf{A}$ and $\mathbf{B}$ are
homomorphic if and only if the structures $\tilde{\mathbf{A}}$ and
$\tilde{\mathbf{B}}$ obtained by adding $R_{k}$ to their signatures are
homomorphic. Hence, $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is equivalent
to $\operatorname{PCSP}(\tilde{\mathbf{A}},\tilde{\mathbf{B}})$, and
considering $k$-enhanced structures results in no loss of generality. We now
give the main definition of this work.

######  Definition 12.

For a minion ${\mathscr{M}}$ and an integer $k\in\mathbb{N}$, the _$k$ -th
level of the minion test_ $\operatorname{Test}_{{\mathscr{M}}}$, denoted by
$\operatorname{Test}_{{\mathscr{M}}}^{k}$, is the computational problem
defined as follows: Given two $k$-enhanced $\sigma$-structures $\mathbf{X}$
and $\mathbf{A}$, return Yes if
$\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$,
and No otherwise.

Comparing Definition 12 with Definition 3, we see that
$\operatorname{Test}_{{\mathscr{M}}}^{k}(\mathbf{X},\mathbf{A})=\operatorname{Test}_{{\mathscr{M}}}(\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}},\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$.
In other words, the $k$-th level of a minion test is just the minion test
applied to the tensor power of the structures. We have seen (cf. Proposition
5) that a minion test is always complete. It turns out that this property
keeps holding for any level of a minion test.

######  Proposition 13.

$\operatorname{Test}_{{\mathscr{M}}}^{k}$ is complete for any minion
${\mathscr{M}}$ and any integer $k\in\mathbb{N}$.

The proof of Proposition 13 relies on the fact that homomorphisms between
structures are in some sense invariant under the tensorisation construction,
as formally stated in Proposition 28.

It is well known that each of the hierarchies of relaxations mentioned in
Section 2 has the property that higher levels are at least as powerful as
lower levels. As the next result shows, this is in fact a property of all
hierarchies of minion tests.

######  Proposition 14.

Let ${\mathscr{M}}$ be a minion, let $k,p\in\mathbb{N}$ be such that $k>p$,
and let $\mathbf{X},\mathbf{A}$ be two $k$\- and $p$-enhanced
$\sigma$-structures. If
$\operatorname{Test}_{{\mathscr{M}}}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$
then
$\operatorname{Test}_{{\mathscr{M}}}^{p}(\mathbf{X},\mathbf{A})=\textsc{Yes}$.

It follows from Proposition 14 that, if some level of a minion test is sound
for a template $(\mathbf{A},\mathbf{B})$ (equivalently, if it solves
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$), then any higher level is sound
for $(\mathbf{A},\mathbf{B})$ (equivalently, it solves
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$).

The next theorem is the second main result of this paper. It shows that the
framework defined above is general enough to capture each of the five
hierarchies for $\operatorname{(P)CSPs}$ mentioned in Section 2.

######  Theorem 15 (Informal).

If $k\in\mathbb{N}$ is at least the maximum arity of the template,
$\displaystyle\begin{array}[]{lll}\bullet\;\operatorname{BW}^{k}=\operatorname{Test}_{\mathscr{H}}^{k}\\\\[4.0pt]
\bullet\;\operatorname{SA}^{k}=\operatorname{Test}_{{\mathscr{Q}_{\operatorname{conv}}}}^{k}\\\\[4.0pt]
\bullet\;\operatorname{AIP}^{k}=\operatorname{Test}_{{\mathscr{Z}_{\operatorname{aff}}}}^{k}\\\\[4.0pt]
\bullet\;\operatorname{SoS}^{k}=\operatorname{Test}_{{\mathscr{S}}}^{k}\\\\[4.0pt]
\bullet\;\operatorname{BA}^{k}=\operatorname{Test}_{\mathscr{M}_{\operatorname{BA}}}^{k}.\end{array}$

###  3.3 Linear minions

Certain features of the hierarchies of minion tests from Definition 12 – in
particular, the fact that they are complete (Proposition 13) and progressively
stronger (Proposition 14) – hold true for any minion, as they only depend on
basic properties of the tensorisation construction. In order to prove Theorem
15, however, it is necessary to dig deeper by investigating how the
tensorisation construction interacts with the free structure. In other words,
we need to understand the object
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$.
To that end, we isolate a property shared by all minions mentioned in this
work: Their objects can be interpreted as matrices, and their minor operations
can be expressed as matrix multiplications. We call such minions _linear_.

######  Definition 16.

A minion ${\mathscr{M}}$ is _linear_ if there exists a semiring $\mathcal{S}$
with additive identity $0_{\mathcal{S}}$ and multiplicative identity
$1_{\mathcal{S}}$ and a number ${d}\in\mathbb{N}\cup\\{{\aleph_{0}}\\}$
(called _depth_) such that

  1. 1.

the elements of ${\mathscr{M}}^{(L)}$ are $L\times d$ matrices whose entries
belong to $\mathcal{S}$, for each $L\in\mathbb{N}$;

  2. 2.

given $L,L^{\prime}\in\mathbb{N}$, $\pi:[L]\to[L^{\prime}]$, and
$M\in{\mathscr{M}}^{(L)}$, $M_{/\pi}=PM$, where $P$ is the $L^{\prime}\times
L$ matrix such that, for $i\in[L^{\prime}]$ and $j\in[L]$, the $(i,j)$-th
entry of $P$ is $1_{\mathcal{S}}$ if $\pi(j)=i$, and $0_{\mathcal{S}}$
otherwise.

Observe that pre-multiplying a matrix $M$ by $P$ amounts to performing a
combination of the following three elementary operations to the rows of $M$:
swapping two rows, replacing two rows with their sum, and inserting a zero
row. Hence, we may equivalently define a linear minion as a collection of
matrices over $\mathcal{S}$ that is closed under such elementary operations.

As illustrated in the next proposition, the family of linear minions is rich
enough to include the minions associated with all minion tests studied in the
literature on $\operatorname{PCSP}$s, including $\operatorname{SDP}$.

######  Proposition 17.

The following minions are linear:888It is not hard to verify that also the
minion ${\mathscr{C}}$ capturing the power of the $\operatorname{CLAP}$
algorithm from [44] is linear, with $\mathcal{S}=\mathbb{Q}$ and
${d}={\aleph_{0}}$.

$\displaystyle\bullet\;\;\mathscr{H},\mbox{ with
}\mathcal{S}=(\\{0,1\\},\vee,\wedge)\mbox{ and }{d}=1$
$\displaystyle\bullet\;\;{\mathscr{Q}_{\operatorname{conv}}},\mbox{ with
}\mathcal{S}=\mathbb{Q}\mbox{ and }{d}=1$
$\displaystyle\bullet\;\;{\mathscr{Z}_{\operatorname{aff}}},\mbox{ with
}\mathcal{S}=\mathbb{Z}\mbox{ and }{d}=1$
$\displaystyle\bullet\;\;{\mathscr{S}},\mbox{ with
}\mathcal{S}=\mathbb{R}\mbox{ and }{d}={\aleph_{0}}$
$\displaystyle\bullet\;\;\mathscr{M}_{\operatorname{BA}},\mbox{ with
}\mathcal{S}=\mathbb{Q}\mbox{ and }{d}=2.$

Recall that, as per Definition 3, the minion test associated with a minion
${\mathscr{M}}$ works by checking whether a given instance is homomorphic to
the free structure of ${\mathscr{M}}$; in other words,
$\operatorname{Test}_{{\mathscr{M}}}$ for a template $(\mathbf{A},\mathbf{B})$
is essentially $\operatorname{CSP}(\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}))$.
It is then worth checking what the latter object looks like in the case that
${\mathscr{M}}$ is linear. The next remark shows that, in this case,
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})$ has a simple matrix-theoretic
description.

######  Remark 18.

Given a linear minion ${\mathscr{M}}$ with semiring $\mathcal{S}$ and depth
$d$, and a $\sigma$-structure $\mathbf{A}$, the free structure
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})$ of ${\mathscr{M}}$ generated by
$\mathbf{A}$ has the following description:

  * •

The elements of its domain ${\mathscr{M}}^{(|A|)}$ are $|A|\times d$ matrices
having entries in $\mathcal{S}$.

  * •

For $R\in\sigma$ of arity $r$, the elements of
$R^{\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})}$ are tuples of the form
$(P_{1}{Q},\dots,P_{r}{Q})$, where ${Q}\in{\mathscr{M}}^{(|R^{\mathbf{A}}|)}$
is a $|R^{\mathbf{A}}|\times d$ matrix having entries in $\mathcal{S}$ and,
for $i\in[r]$, $P_{i}$ is the $|A|\times|R^{\mathbf{A}}|$ matrix whose
$(a,\mathbf{a})$-th entry is $1_{\mathcal{S}}$ if $a_{i}=a$, and
$0_{\mathcal{S}}$ otherwise.999We shall often write $0$ and $1$ for
$0_{\mathcal{S}}$ and $1_{\mathcal{S}}$ to avoid cumbersome notation. The
relevant semiring $\mathcal{S}$ will always be clear from the context.

###  3.4 Multilinear tests

We say that a test is _multilinear_ if it can be expressed as
$\operatorname{Test}_{{\mathscr{M}}}^{k}$ for some linear minion
${\mathscr{M}}$ and some integer $k$. In the same way as, for a template
$(\mathbf{A},\mathbf{B})$, $\operatorname{Test}_{{\mathscr{M}}}$ is
essentially $\operatorname{CSP}(\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}))$, it
follows from Definition 12 that $\operatorname{Test}_{{\mathscr{M}}}^{k}$ is
essentially
$\operatorname{CSP}(\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}))$,
as it checks for the existence of a homomorphism between the tensor power of
the instance and the free structure of ${\mathscr{M}}$ generated by the tensor
power of $\mathbf{A}$.

In Section 8, we show that, if ${\mathscr{M}}$ is linear,
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
is a space of tensors endowed with relations that can be described through a
tensor operation called _contraction_. Hence, the matrix-theoretic description
in Remark 18 is naturally extended to a tensor-theoretic description. To give
a first glance of this object, we illustrate below the structure of
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
in the case that ${\mathscr{M}}={\mathscr{Q}_{\operatorname{conv}}}$, $k=3$,
and $\mathbf{A}=\mathbf{K}_{3}$.

######  Example 19.

Let us denote
$\mathbb{F}_{{\mathscr{Q}_{\operatorname{conv}}}}(\mathbf{K}_{3}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny3}⃝}}})$
by F. The domain of F is the set of nonnegative tensors in
$\mathcal{T}^{3\cdot\mathbf{1}_{3}}(\mathbb{Q})$ whose entries sum up to $1$.
The relation $R^{\textbf{F}}$ is the set of those tensors
$M\in\mathcal{T}^{2\cdot\mathbf{1}_{3}}(\mathcal{T}^{3\cdot\mathbf{1}_{3}}(\mathbb{Q}))=\mathcal{T}^{6\cdot\mathbf{1}_{3}}(\mathbb{Q})$
such that there exists a stochastic vector
$\mathbf{q}=(q_{1},\dots,q_{6})\in{\mathscr{Q}_{\operatorname{conv}}}^{(6)}$
(which should be interpreted as a probability distribution over the elements
of $R^{\mathbf{K}_{3}}$, i.e., over the directed edges in $\mathbf{K}_{3}$)
for which the $\mathbf{i}$-th block $M_{\mathbf{i}}$ of $M$ satisfies
$M_{\mathbf{i}}=\mathbf{q}_{/\pi_{\mathbf{i}}}$ for each
$\mathbf{i}\in[2]^{3}$. It will follow from the results in Section 8 that, for
example,

$\displaystyle M_{(1,1,1)}$
$\displaystyle=\left[\begin{array}[]{@{}ccc|ccc|ccc@{}}q_{1}+q_{6}&0&0&0&0&0&0&0&0\\\
0&0&0&0&q_{2}+q_{3}&0&0&0&0\\\
0&0&0&0&0&0&0&0&q_{4}+q_{5}\end{array}\right]\\!\\!,$ $\displaystyle
M_{(2,1,2)}$
$\displaystyle=\left[\begin{array}[]{@{}ccc|ccc|ccc@{}}0&0&0&0&q_{1}&0&0&0&q_{6}\\\
q_{2}&0&0&0&0&0&0&0&q_{3}\\\
q_{5}&0&0&0&q_{4}&0&0&0&0\end{array}\right]\\!\\!.$

Figure 1 illustrates the tensor $M\in R^{\textbf{F}}$ corresponding to the
uniform distribution $\mathbf{q}=\frac{1}{6}\cdot\mathbf{1}_{6}$.

Figure 1: A tensor $M\in R^{\textbf{F}}$ from Example 19, corresponding to the
uniform distribution on the set of edges of $\mathbf{K}_{3}$. The opacity of a
cell is proportional to the value of the corresponding entry:  =
$\frac{1}{3}$,  = $\frac{1}{6}$,  = $0$.

In Section 8, we investigate the geometry of
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})$ for a linear minion ${\mathscr{M}}$.
As hinted by Example 19, we shall see that this object is a space of sparse
tensors, whose nonzero entries form regular patterns (cf. Lemma 31). This
feature becomes more evident for higher values of the level $k$. In turn, the
geometry of
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
is reflected in the properties of the homomorphisms $\xi$ from
$\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
to it – which, by virtue of Definition 12, are precisely the solutions sought
by $\operatorname{Test}_{{\mathscr{M}}}^{k}$. For instance, Proposition 36
distils the requirements of the $\operatorname{BW}^{k}$,
$\operatorname{SA}^{k}$, $\operatorname{AIP}^{k}$, $\operatorname{SoS}^{k}$,
and $\operatorname{BA}^{k}$ hierarchies enforcing compatibility between
partial assignments101010Cf. the “closure under restriction” property of
$\operatorname{BW}^{k}$ and the requirements $\clubsuit 2$ and $\spadesuit 3$
in Section 4.2. from $\mathbf{X}$ to $\mathbf{A}$ into the single tensor
equation

$\xi(\mathbf{x}_{\mathbf{i}})=\Pi_{\mathbf{i}}\overset{\tiny
k}{\ast}\xi(\mathbf{x}).$

For $k=1$, the equation is vacuous, since in this case $\Pi_{\mathbf{i}}$ is
the identity matrix and $\mathbf{x}_{\mathbf{i}}=\mathbf{x}$ (cf. Section 4.1
for the notation). As $k$ increases, it produces a progressively richer system
of symmetries that must be satisfied by $\xi$, which corresponds to a
progressively stronger relaxation. Concretely, we shall use all results
obtained in Section 8 on the geometry of
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
to prove Theorem 15.

###  3.5 Conic minions

A primary message of this work is that the tensorisation construction
establishes a correspondence between the algebraic properties of a minion and
the algorithmic properties of the hierarchy of tests built on the minion. For
example, we have seen that if the minion is linear some general properties of
the solutions of the hierarchy can be deduced by studying the geometry of
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$.
Now, the bounded width hierarchy has the property that it only seeks
assignments that are partial homomorphisms; similarly, the Sherali-Adams, Sum-
of-Squares, and $\operatorname{BA}^{k}$ hierarchies only assign a positive
weight to solutions satisfying local constraints. The next definition
identifies the minion property guaranteeing this algorithmic feature.

######  Definition 20.

A linear minion ${\mathscr{M}}$ of depth $d$ is _conic_ if, for any
$L\in\mathbb{N}$ and for any $M\in{\mathscr{M}}^{(L)}$, $(i)$ $M\neq O_{L,d}$,
and $(ii)$ for any $V\subseteq[L]$, the following implication is true:111111As
usual, the sum, product, $0$, and $1$ operations appearing in this definition
are to be meant in the semiring $\mathcal{S}$ associated with the linear
minion ${\mathscr{M}}$.

$\displaystyle\begin{array}[]{ll}\sum_{i\in
V}M^{T}\mathbf{e}_{i}=\mathbf{0}_{d}\quad\Rightarrow\quad
M^{T}\mathbf{e}_{i}=\mathbf{0}_{d}\;\;\forall i\in V.\end{array}$

Paraphrasing Definition 20, a linear minion ${\mathscr{M}}$ is conic if any
matrix in ${\mathscr{M}}$ is nonzero and has the property that, whenever some
of its rows sum up to the zero vector, each of those rows is the zero vector.
All minions appearing in Proposition 17 are conic, with the exception of
${\mathscr{Z}_{\operatorname{aff}}}$.

######  Proposition 21.

$\mathscr{H}$, ${\mathscr{Q}_{\operatorname{conv}}}$, ${\mathscr{S}}$, and
$\mathscr{M}_{\operatorname{BA}}$ are conic minions,121212The minion
${\mathscr{C}}$ associated with the $\operatorname{CLAP}$ algorithm from [44]
can be easily shown to be conic as well. while
${\mathscr{Z}_{\operatorname{aff}}}$ is not.

It turns out that this simple property guarantees that the hierarchies of
tests built on conic minions only look at assignments yielding partial
homomorphisms (cf. Proposition 38). It also follows that conic hierarchies are
not fooled by small instances: Proposition 39 establishes that the $k$-th
level of such hierarchies is able to correctly classify instances on $k$ (or
fewer) elements131313We may informally express this fact by saying that conic
hierarchies are “sound in the limit”. – as it is well known for the bounded
width, Sherali-Adams, and Sum-of-Squares hierarchies. Moreover, we shall see
that any linear minion can be transformed into a conic minion – whose
hierarchy enjoys the features mentioned above – via the _semi-direct product_
construction (cf. Proposition 40).

#### Organisation

The rest of the paper contains full details and proofs of the statements
presented in this Overview. Section 4 includes relevant terminology for
tensors as well as a description of the relaxations and hierarchies used
throughout the paper (see also Appendix A). Section 5 gives some basic results
on minion tests. Section 6 shows that the power of $\operatorname{SDP}$ is
captured by the minion ${\mathscr{S}}$. Sections 7, 8, and 9 are the technical
core of the paper; they provide a description of hierarchies of tests built on
arbitrary minions, linear minions, and conic minions, respectively. Section 10
describes the semi-direct product of minions, needed to capture the
$\operatorname{BA}^{k}$ hierarchy. The machinery assembled in the previous
sections is finally used in Section 11 to prove Theorem 15.

##  4 Preliminaries

###  4.1 Terminology for tensors

#### Tuples

Given a set $S$, two integers $k,\ell\in\mathbb{N}$, a tuple
$\mathbf{s}=(s_{1},\dots,s_{k})\in S^{k}$, and a tuple
$\mathbf{i}=(i_{1},\dots,i_{\ell})\in[k]^{\ell}$, $\mathbf{s}_{\mathbf{i}}$
shall denote the _projection_ of $\mathbf{s}$ onto $\mathbf{i}$, i.e., the
tuple in $S^{\ell}$ defined by
$\mathbf{s}_{\mathbf{i}}=(s_{i_{1}},\dots,s_{i_{\ell}})$. Given two tuples
$\mathbf{s}=(s_{1},\dots,s_{k})\in S^{k}$ and
$\tilde{\mathbf{s}}=(\tilde{s}_{1},\dots,\tilde{s}_{\ell})\in S^{\ell}$, their
_concatenation_ is the tuple
$(\mathbf{s},\tilde{\mathbf{s}})=(s_{1},\dots,s_{k},\tilde{s}_{1},\dots,\tilde{s}_{\ell})\in
S^{k+\ell}$. We also define $\\{\mathbf{s}\\}=\\{s_{1},\dots,s_{k}\\}$. Given
two sets $S,\tilde{S}$ and two tuples $\mathbf{s}=(s_{1},\dots,s_{k})\in
S^{k}$,
$\tilde{\mathbf{s}}=(\tilde{s}_{1},\dots,\tilde{s}_{k})\in\tilde{S}^{k}$, we
write $\mathbf{s}\prec\tilde{\mathbf{s}}$ if, for any $\alpha,\beta\in[k]$,
$s_{\alpha}=s_{\beta}$ implies $\tilde{s}_{\alpha}=\tilde{s}_{\beta}$. The
expression $\mathbf{s}\not\prec\tilde{\mathbf{s}}$ shall mean the negation of
$\mathbf{s}\prec\tilde{\mathbf{s}}$. Notice that the relation “$\prec$” is
preserved under projections: If $\mathbf{s}\prec\tilde{\mathbf{s}}$ and
$\mathbf{i}\in[k]^{\ell}$, then
$\mathbf{s}_{\mathbf{i}}\prec\tilde{\mathbf{s}}_{\mathbf{i}}$.

#### Semirings

A _semiring_ $\mathcal{S}$ consists of a set $S$ equipped with two binary
operations “$+$” and “$\cdot$” such that

  * •

$(S,+)$ is a commutative monoid with an identity element “$0_{\mathcal{S}}$”
(i.e., $(r+s)+t=r+(s+t)$, $0_{\mathcal{S}}+r=r+0_{\mathcal{S}}=r$, and
$r+s=s+r$);

  * •

$(S,\cdot)$ is a monoid with an identity element “$1_{\mathcal{S}}$” (i.e.,
$(r\cdot s)\cdot t=r\cdot(s\cdot t)$ and $1_{\mathcal{S}}\cdot r=r\cdot
1_{\mathcal{S}}=r$);

  * •

“$\cdot$” distributes over “$+$” (i.e., $r\cdot(s+t)=(r\cdot s)+(r\cdot t)$
and $(r+s)\cdot t=(r\cdot t)+(s\cdot t)$);

  * •

“$0_{\mathcal{S}}$” is a multiplicative absorbing element (i.e.,
$0_{\mathcal{S}}\cdot r=r\cdot 0_{\mathcal{S}}=0_{\mathcal{S}}$).

Examples of semirings are $\mathbb{Z}$, $\mathbb{Q}$, and $\mathbb{R}$ with
the usual addition and multiplication operations, or the Boolean semiring
$(\\{0,1\\},\vee,\wedge)$.

Let $V$ be a finite set, and choose an element $s_{v}\in\mathcal{S}$ for each
$v\in V$. We let the formal expression $\sum_{v\in V}s_{v}$ equal
$0_{\mathcal{S}}$ if $V=\emptyset$. To increase the readability, we shall
usually write $0$ and $1$ for $0_{\mathcal{S}}$ and $1_{\mathcal{S}}$; the
relevant semiring $\mathcal{S}$ will always be clear from the context.

#### Tensors

As anticipated in Section 3, given a set $S$, an integer $k\in\mathbb{N}$, and
a tuple $\mathbf{n}=(n_{1},\dots,n_{k})\in\mathbb{N}^{k}$, by
$\mathcal{T}^{\mathbf{n}}(S)$ we denote the set of functions from
$[n_{1}]\times\dots\times[n_{k}]$ to $S$, which we visualise as hypermatrices
or tensors having $k$ _modes_ , where the $i$-th mode has size $n_{i}$ for
$i\in[k]$. If $\mathbf{n}=n\cdot\mathbf{1}_{k}=(n,\dots,n)$ is a constant
tuple, $\mathcal{T}^{\mathbf{n}}(S)$ is a set of _cubical_ tensors, each of
whose modes has the same length $n$. For example, if
$\mathbf{n}=n\cdot\mathbf{1}_{2}=(n,n)$, $\mathcal{T}^{\mathbf{n}}(S)$ is the
set of $n\times n$ matrices having entries in $S$. We sometimes denote an
element of $\mathcal{T}^{\mathbf{n}}(S)$ by $T=(t_{\mathbf{i}})$, where
$\mathbf{i}\in[n_{1}]\times\dots\times[n_{k}]$ and $t_{\mathbf{i}}$ is the
image of $\mathbf{i}$ under $T$. Moreover, given two tuples
$\mathbf{n}\in\mathbb{N}^{k}$ and $\tilde{\mathbf{n}}\in\mathbb{N}^{\ell}$, we
sometimes write $\mathcal{T}^{\mathbf{n},\tilde{\mathbf{n}}}(S)$ for
$\mathcal{T}^{(\mathbf{n},\tilde{\mathbf{n}})}(S)$, where
$(\mathbf{n},\tilde{\mathbf{n}})$ is the concatenation of $\mathbf{n}$ and
$\tilde{\mathbf{n}}$. Whenever $k\geq 2$ and $n_{i}=1$ for some $i\in[k]$, we
can (and will) identify $\mathcal{T}^{\mathbf{n}}(S)$ with
$\mathcal{T}^{\hat{\mathbf{n}}}(S)$, where
$\hat{\mathbf{n}}\in\mathbb{N}^{k-1}$ is obtained from $\mathbf{n}$ by
deleting the $i$-th entry.

#### Contraction

Take a semiring $\mathcal{S}$. For $k,\ell,m\in\mathbb{N}$, take
$\mathbf{n}\in\mathbb{N}^{k}$, $\mathbf{p}\in\mathbb{N}^{\ell}$, and
$\mathbf{q}\in\mathbb{N}^{m}$. The _contraction_ of two tensors
$T=(t_{\mathbf{i}})\in\mathcal{T}^{\mathbf{n},\mathbf{p}}(\mathcal{S})$ and
$\tilde{T}=(\tilde{t}_{\mathbf{i}})\in\mathcal{T}^{\mathbf{p},\mathbf{q}}(\mathcal{S})$,
denoted by $T\overset{\mathrm{\ell}}{\ast}\tilde{T}$, is the tensor in
$\mathcal{T}^{\mathbf{n},\mathbf{q}}(\mathcal{S})$ such that, for
$\mathbf{i}\in[n_{1}]\times\dots\times[n_{k}]$ and
$\mathbf{j}\in[q_{1}]\times\dots\times[q_{m}]$, the
$(\mathbf{i},\mathbf{j})$-th entry of
$T\overset{\mathrm{\ell}}{\ast}\tilde{T}$ is given by

$\displaystyle\sum_{\mathbf{z}\in[p_{1}]\times\dots\times[p_{\ell}]}t_{(\mathbf{i},\mathbf{z})}\tilde{t}_{(\mathbf{z},\mathbf{j})}$

(where the addition and multiplication are meant in the semiring
$\mathcal{S}$). This notation straightforwardly extends to the cases when
$k=0$ or $m=0$, i.e., when we are contracting over all modes of $T$ or
$\tilde{T}$. In such cases, we write $T\ast\tilde{T}$ for
$T\overset{\mathrm{\ell}}{\ast}\tilde{T}$. We shall use the convention of
always contracting from the left to the right, so that the expression
$T_{1}\ast T_{2}\ast T_{3}$ is a synonym for the expression $(T_{1}\ast
T_{2})\ast T_{3}$. The reason for this is that the contraction operation is
not associative in general. For instance, for $T$ and $\tilde{T}$ as above and
$\hat{T}\in\mathcal{T}^{\mathbf{n},\mathbf{q}}(\mathcal{S})$, the expression
$(T\overset{\tiny\ell}{\ast}\tilde{T})\overset{\tiny
k+m}{\ast}\hat{T}=(T\overset{\tiny\ell}{\ast}\tilde{T})\ast\hat{T}$ is well
defined, while changing the order of the contractions results in an expression
that is not well defined in general. On the other hand, it is not hard to
check that the order in which the contractions are performed is irrelevant if
the contractions are taken over disjoint sets of modes.

######  Example 22.

Given two vectors $\mathbf{u},\mathbf{v}\in\mathcal{T}^{p}(\mathbb{R})$ and
two matrices $M\in\mathcal{T}^{n,p}(\mathbb{R})$,
$N\in\mathcal{T}^{p,q}(\mathbb{R})$, we have that $\mathbf{u}\overset{\tiny
1}{\ast}\mathbf{v}=\mathbf{u}\ast\mathbf{v}=\mathbf{u}^{T}\mathbf{v}$ (the dot
product of $\mathbf{u}$ and $\mathbf{v}$), $M\overset{\tiny
1}{\ast}\mathbf{u}=M\ast\mathbf{u}=M\mathbf{u}$ (the matrix-vector product of
$M$ and $\mathbf{u}$), and $M\overset{\tiny 1}{\ast}N=MN$ (the matrix product
of $M$ and $N$).

For $\mathbf{i}\in[n_{1}]\times\dots\times[n_{k}]$, we denote by
$E_{\mathbf{i}}$ the _$\mathbf{i}$ -th standard unit tensor_; i.e., the tensor
in $\mathcal{T}^{\mathbf{n}}(\mathcal{S})$ all of whose entries are
$0_{\mathcal{S}}$, except the $\mathbf{i}$-th entry that is $1_{\mathcal{S}}$.
Given $T\in\mathcal{T}^{\mathbf{n}}(\mathcal{S})$, notice that
$E_{\mathbf{i}}\overset{\tiny k}{\ast}T=E_{\mathbf{i}}\ast T$ is the
$\mathbf{i}$-th entry of $T$. The _support_ of $T$ is the set of indices of
all nonzero entries of $T$; i.e., the set
$\operatorname{supp}(T)=\\{\mathbf{i}\in[n_{1}]\times\dots\times[n_{k}]:E_{\mathbf{i}}\ast
T\neq 0_{\mathcal{S}}\\}$.

######  Remark 23.

The definition of tensors straightforwardly extends to the case that
$n_{i}={\aleph_{0}}$ for some $i\in[k]$.

###  4.2 Relaxations and hierarchies

In this section, we define the standard semidefinite programming relaxation as
well as the bounded width, Sherali-Adams LP, affine integer programming, Sum-
of-Squares, and combined basic linear programming and affine integer
programming hierarchies. We refer to Appendix A for a more detailed
discussion, as well as for a comparison with different formulations of these
algorithms appearing in the literature on $\operatorname{(P)CSPs}$.

Given two $\sigma$-structures $\mathbf{A}$ and $\mathbf{B}$ and a subset
$S\subseteq A$, a _partial homomorphism_ from $\mathbf{A}$ to $\mathbf{B}$
with domain $S$ is a homomorphism from $\mathbf{A}[S]$ to $\mathbf{B}$, where
$\mathbf{A}[S]$ is the substructure of $\mathbf{A}$ _induced_ by $S$ – i.e.,
it is the $\sigma$-structure whose domain is $S$ and, for any $R\in\sigma$,
$R^{\mathbf{A}[S]}=R^{\mathbf{A}}\cap S^{\operatorname{ar}(R)}$. Recall that,
for $k\in\mathbb{N}$, we say that a $\sigma$-structure $\mathbf{A}$ is _$k$
-enhanced_ if the signature $\sigma$ contains a $k$-ary symbol $R_{k}$ such
that $R_{k}^{\mathbf{A}}=A^{k}$.

#### $\mbox{BW}^{\mbox{k}}$

Given two $\sigma$-structures $\mathbf{X},\mathbf{A}$, we say that the $k$-th
level of the _bounded width algorithm_ accepts when applied to $\mathbf{X}$
and $\mathbf{A}$, and we write
$\operatorname{BW}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$, if there exists a
nonempty collection $\mathcal{F}$ of partial homomorphisms from $\mathbf{X}$
to $\mathbf{A}$ with at most $k$-element domains such that $(i)$ $\mathcal{F}$
is closed under restrictions, i.e., for every $f\in\mathcal{F}$ and every
$V\subseteq\operatorname{dom}(f)$, $f|_{V}\in\mathcal{F}$, and $(ii)$
$\mathcal{F}$ has the extension property up to $k$, i.e., for every
$f\in\mathcal{F}$ and every $V\subseteq X$ with $|V|\leq k$ and
$\operatorname{dom}(f)\subseteq V$, there exists $g\in\mathcal{F}$ such that
$g$ extends $f$ and $\operatorname{dom}(g)=V$.

We say that $\operatorname{BW}^{k}$ _solves_ a $\operatorname{PCSP}$ template
$(\mathbf{A},\mathbf{B})$ if $\mathbf{X}\to\mathbf{B}$ whenever
$\operatorname{BW}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$. (Note that the
algorithm is always complete: If $\mathbf{X}\to\mathbf{A}$ then
$\operatorname{BW}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$.)

####  $\mbox{SA}^{\mbox{k}}$, $\mbox{AIP}^{\mbox{k}}$, and
$\mbox{BA}^{\mbox{k}}$

Given two $k$-enhanced $\sigma$-structures $\mathbf{X},\mathbf{A}$, we
introduce a variable $\lambda_{R,\mathbf{x},\mathbf{a}}$ for every
$R\in\sigma$, $\mathbf{x}\in R^{\mathbf{X}}$, $\mathbf{a}\in R^{\mathbf{A}}$.
Consider the following system of equations:

$\displaystyle\begin{array}[]{llllllll}\mbox{($\clubsuit
1$)}&\displaystyle\sum_{\mathbf{a}\in
R^{\mathbf{A}}}\lambda_{R,\mathbf{x},\mathbf{a}}&=&1&R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}}\\\ \mbox{($\clubsuit 2$)}&\displaystyle\sum_{\mathbf{a}\in
R^{\mathbf{A}},\mathbf{a}_{\mathbf{i}}=\mathbf{b}}\lambda_{R,\mathbf{x},\mathbf{a}}&=&\lambda_{R_{k},\mathbf{x}_{\mathbf{i}},\mathbf{b}}&R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},\mathbf{i}\in[\operatorname{ar}(R)]^{k},\mathbf{b}\in A^{k}\\\
\mbox{($\clubsuit
3$)}&\displaystyle\lambda_{R,\mathbf{x},\mathbf{a}}&=&0&R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},\mathbf{a}\in
R^{\mathbf{A}},\mathbf{x}\not\prec\mathbf{a}.\end{array}$ (5)

We say that the $k$-th level of the _Sherali-Adams linear programming
hierarchy_ accepts when applied to $\mathbf{X}$ and $\mathbf{A}$, and we write
$\operatorname{SA}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$, if the system (5)
admits a solution such that all variables take rational nonnegative values.
Similarly, we say that the $k$-th level of the _affine integer programming
hierarchy_ accepts when applied to $\mathbf{X}$ and $\mathbf{A}$, and we write
$\operatorname{AIP}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$, if the system
above admits a solution such that all variables take integer values. Moreover,
we say that the $k$-th level of the _combined basic linear programming and
affine integer programming hierarchy_ accepts when applied to $\mathbf{X}$ and
$\mathbf{A}$, and we write
$\operatorname{BA}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$, if the system
above admits both a solution such that all variables take rational nonnegative
values and a solution such that all variables take integer values, and the
following _refinement condition_ holds: Denoting the rational nonnegative and
the integer solutions by the superscripts $(\operatorname{B})$ and
$(\operatorname{A})$, respectively, we require that
$\lambda^{(\operatorname{A})}_{R,\mathbf{x},\mathbf{a}}=0$ whenever
$\lambda^{(\operatorname{B})}_{R,\mathbf{x},\mathbf{a}}=0$, for each
$R\in\sigma,\mathbf{x}\in R^{\mathbf{X}},\mathbf{a}\in R^{\mathbf{A}}$.

We say that $\operatorname{SA}^{k}$ _solves_ a $\operatorname{PCSP}$ template
$(\mathbf{A},\mathbf{B})$ if $\mathbf{X}\to\mathbf{B}$ whenever
$\operatorname{SA}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$. The definition
for $\operatorname{AIP}^{k}$ and $\operatorname{BA}^{k}$ is analogous. (Note
that the three algorithms are always complete: If $\mathbf{X}\to\mathbf{A}$
then
$\operatorname{SA}^{k}(\mathbf{X},\mathbf{A})=\operatorname{AIP}^{k}(\mathbf{X},\mathbf{A})=\operatorname{BA}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$.)

#### SDP

Given two $\sigma$-structures $\mathbf{X},\mathbf{A}$, let
$\omega=|X|\cdot|A|+\sum_{R\in\sigma}|R^{\mathbf{X}}|\cdot|R^{\mathbf{A}}|$.
We introduce a variable ${\bm{\lambda}}_{x,a}$ taking values in
$\mathbb{R}^{\omega}$ for every $x\in X$, $a\in A$, and a variable
${\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}$ taking values in
$\mathbb{R}^{\omega}$ for every $R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},\mathbf{a}\in R^{\mathbf{A}}$. Consider the following system of
equations:

$\displaystyle\begin{array}[]{llllll}\mbox{($\vardiamond
1$)}&\displaystyle\sum_{a\in A}\|{\bm{\lambda}}_{x,a}\|^{2}&=&1&x\in X\\\
\mbox{($\vardiamond
2$)}&{\bm{\lambda}}_{x,a}\cdot{\bm{\lambda}}_{x,a^{\prime}}&=&0&x\in X,a\neq
a^{\prime}\in A\\\ \mbox{($\vardiamond
3$)}&{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}\cdot{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}^{\prime}}&=&0&R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},\mathbf{a}\neq\mathbf{a}^{\prime}\in R^{\mathbf{A}}\\\
\mbox{($\vardiamond 4$)}&\displaystyle\sum_{\begin{subarray}{c}\mathbf{a}\in
R^{\mathbf{A}}\\\
a_{i}=a\end{subarray}}{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}&=&{\bm{\lambda}}_{x_{i},a}&R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},a\in A,i\in[\operatorname{ar}(R)].\end{array}$ (10)

We say that the _standard semidefinite programming relaxation_ accepts when
applied to $\mathbf{X}$ and $\mathbf{A}$, and we write
$\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$, if the system (10)
admits a solution. We say that $\operatorname{SDP}$ _solves_ a
$\operatorname{PCSP}$ template $(\mathbf{A},\mathbf{B})$ if
$\mathbf{X}\to\mathbf{B}$ whenever
$\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$. (Note that the
algorithm is always complete: If $\mathbf{X}\to\mathbf{A}$ then
$\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$.)

#### $\mbox{SoS}^{\mbox{k}}$

Given two $k$-enhanced $\sigma$-structures $\mathbf{X},\mathbf{A}$, let
$\omega=\sum_{R\in\sigma}|R^{\mathbf{X}}|\cdot|R^{\mathbf{A}}|$. We introduce
a variable ${\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}$ taking values in
$\mathbb{R}^{\omega}$ for every $R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},\mathbf{a}\in R^{\mathbf{A}}$. Consider the following system of
equations:

$\displaystyle\begin{array}[]{lllllll}\mbox{($\spadesuit
1$)}&\displaystyle\sum_{\mathbf{a}\in
R^{\mathbf{A}}}\|{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}\|^{2}&=&1&R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}}\\\ \mbox{($\spadesuit
2$)}&{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}\cdot{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}^{\prime}}&=&0&R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},\mathbf{a}\neq\mathbf{a}^{\prime}\in R^{\mathbf{A}}\\\
\mbox{($\spadesuit 3$)}&\displaystyle\sum_{\mathbf{a}\in
R^{\mathbf{A}},\mathbf{a}_{\mathbf{i}}=\mathbf{b}}{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}&=&{\bm{\lambda}}_{R_{k},\mathbf{x}_{\mathbf{i}},\mathbf{b}}&R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},\mathbf{i}\in[\operatorname{ar}(R)]^{k},\mathbf{b}\in A^{k}\\\
\mbox{($\spadesuit
4$)}&\displaystyle\|{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}\|^{2}&=&0&R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},\mathbf{a}\in
R^{\mathbf{A}},\mathbf{x}\not\prec\mathbf{a}.\end{array}$ (15)

We say that the $k$-th level of the _Sum-of-Squares semidefinite programming
hierarchy_ accepts when applied to $\mathbf{X}$ and $\mathbf{A}$, and we write
$\operatorname{SoS}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$, if the system
(15) admits a solution. We say that $\operatorname{SoS}^{k}$ _solves_ a
$\operatorname{PCSP}$ template $(\mathbf{A},\mathbf{B})$ if
$\mathbf{X}\to\mathbf{B}$ whenever
$\operatorname{SoS}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$. (Note that the
algorithm is always complete: If $\mathbf{X}\to\mathbf{A}$ then
$\operatorname{SoS}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$.)

##  5 Minion tests

In this section, we present some basic results on minion tests (introduced in
Definition 3). In particular, we show that a minion test
$\operatorname{Test}_{{\mathscr{M}}}$ is always complete, and its power can be
characterised algebraically through the existence of a homomorphism from
${\mathscr{M}}$ to the polymorphism minion of the template.

We start off with a simple lemma, implicitly proved in [12] for the case of
minions of operations.

######  Lemma 24.

Let $\mathscr{M}$ be a minion and let $\mathbf{A}$ be a $\sigma$-structure.
Then, $\mathbf{A}\to\mathbb{F}_{\mathscr{M}}(\mathbf{A})$.

###### Proof.

Take a unary element $M\in\mathscr{M}^{(1)}$, and consider the map

$\displaystyle f:A$ $\displaystyle\to\mathscr{M}^{(n)}$ $\displaystyle a$
$\displaystyle\mapsto M_{/\rho_{a}}$

where $\rho_{a}:[1]\to[n]=A$ is defined by $\rho_{a}(1)=a$. Take $R\in\sigma$
of arity $r$, and consider a tuple $\mathbf{a}=(a_{1},\dots,a_{r})\in
R^{\mathbf{A}}$. Let $m=|R^{\mathbf{A}}|$, and consider the function
$\pi:[1]\to[m]$ defined by $\pi(1)=\mathbf{a}$. Let
${Q}=M_{/\pi}\in\mathscr{M}^{(m)}$. For each $i\in[r]$, consider the function
$\pi_{i}:[m]\to[n]$ defined by $\pi_{i}(\mathbf{b})=b_{i}$, where
$\mathbf{b}=(b_{1},\dots,b_{r})\in R^{\mathbf{A}}$. Observe that
$\rho_{a_{i}}=\pi_{i}\circ\pi$ for each $i\in[r]$. We obtain

$\displaystyle f(\mathbf{a})$
$\displaystyle=(f(a_{1}),\dots,f(a_{r}))=(M_{/\rho_{a_{1}}},\dots,M_{/\rho_{a_{r}}})=(M_{/\pi_{1}\circ\pi},\dots,M_{/\pi_{r}\circ\pi})$
$\displaystyle=((M_{/\pi})_{/\pi_{1}},\dots,(M_{/\pi})_{/\pi_{r}})=({Q}_{/\pi_{1}},\dots,{Q}_{/\pi_{r}})\in
R^{\mathbb{F}_{\mathscr{M}}(\mathbf{A})},$

thus showing that $f$ is a homomorphism from $\mathbf{A}$ to
$\mathbb{F}_{\mathscr{M}}(\mathbf{A})$. ∎

######  Proposition (Proposition 5 restated).

$\operatorname{Test}_{{\mathscr{M}}}$ is complete for any minion
${\mathscr{M}}$; i.e., for any $\mathbf{X}$ and $\mathbf{A}$ with
$\mathbf{X}\to\mathbf{A}$, we have
$\mathbf{X}\to\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})$.

###### Proof.

It immediately follows from Lemma 24 that, if $\mathbf{X}$ and $\mathbf{A}$
are two $\sigma$-structures such that $\mathbf{X}\to\mathbf{A}$, then
$\mathbf{X}\to\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})$, thus witnessing that
$\operatorname{Test}_{{\mathscr{M}}}(\mathbf{X},\mathbf{A})$ accepts. ∎

We now prove Proposition 6, which establishes that the power of minion tests
can be characterised algebraically. Our proof follows the lines of [12, Remark
7.13], where the same result is derived from Kőnig’s Lemma for _locally
countable minions_ – i.e., minions ${\mathscr{M}}$ having the property that
${\mathscr{M}}^{(L)}$ is countable for any $L$. Since the minion
${\mathscr{S}}$ described in Definition 7 is not locally countable, we shall
need this stronger version of the result when proving that ${\mathscr{S}}$
provides an algebraic characterisation of the power of $\operatorname{SDP}$
(cf. Theorem 9).

First, we need the following result on compact structures, which is a
consequence of the (uncountable version of the) _compactness theorem of logic_
(cf. [88]). We say that a potentially infinite $\sigma$-structure $\mathbf{B}$
is _compact_ if, for any potentially infinite $\sigma$-structure $\mathbf{A}$,
$\mathbf{A}\to\mathbf{B}$ if and only if $\mathbf{A}^{\prime}\to\mathbf{B}$
for every finite substructure $\mathbf{A}^{\prime}$ of $\mathbf{A}$.

######  Theorem 25 ([92]).

Every (finite) $\sigma$-structure is compact.

######  Proposition (Proposition 6 restated).

Let ${\mathscr{M}}$ be a minion and let $(\mathbf{A},\mathbf{B})$ be a
$\operatorname{PCSP}$ template. Then, $\operatorname{Test}_{{\mathscr{M}}}$
solves $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if and only if
${\mathscr{M}}\to\operatorname{Pol}(\mathbf{A},\mathbf{B})$.

###### Proof.

We first observe that the condition
${\mathscr{M}}\to\operatorname{Pol}(\mathbf{A},\mathbf{B})$ is equivalent to
the condition $\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})\to\mathbf{B}$ by [12,
Lemma 4.4] (see also [44] for the proof for abstract minions).

Suppose that $\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})\to\mathbf{B}$. Given an
instance $\mathbf{X}$, if
$\operatorname{Test}_{{\mathscr{M}}}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ then
$\mathbf{X}\to\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})$, and composing the two
homomorphisms yields $\mathbf{X}\to\mathbf{B}$. Hence,
$\operatorname{Test}_{{\mathscr{M}}}$ is sound on the template
$(\mathbf{A},\mathbf{B})$. Since, as noted above,
$\operatorname{Test}_{{\mathscr{M}}}$ is always complete, we deduce that
$\operatorname{Test}_{{\mathscr{M}}}$ solves
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$.

Conversely, suppose that $\operatorname{Test}_{{\mathscr{M}}}$ solves
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$. Let F be a finite substructure
of $\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})$, and notice that the inclusion map
yields a homomorphism from F to $\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})$.
Hence,
$\operatorname{Test}_{{\mathscr{M}}}(\textbf{F},\mathbf{A})=\textsc{Yes}$, so
$\textbf{F}\to\mathbf{B}$. Since $\mathbf{B}$ is compact by Theorem 25, we
deduce that $\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})\to\mathbf{B}$, as
required. ∎

##  6 A minion for SDP

The goal of this section is to show that the relaxation $\operatorname{SDP}$
is a minion test and that its power can be captured algebraically.141414We
remark that a characterisation for the power of $\operatorname{SDP}$, similar
to the one we describe in this section, was also obtained independently by
Brakensiek, Guruswami, and Sandeep in [29]. To this end, we start by showing
that the object introduced in Definition 7 is indeed a minion. Then, it will
easily follow from its construction that it is in fact a linear minion.

######  Proposition 26.

${\mathscr{S}}$ is a linear minion.

###### Proof.

We first show that ${\mathscr{S}}$ is a minion. Observe that, for
$\pi:[L]\rightarrow[L^{\prime}]$ and ${M}\in{\mathscr{S}}^{(L)}$,
$M_{/\pi}=PM\in\mathcal{T}^{L^{\prime},{\aleph_{0}}}(\mathbb{R})$ and
$\operatorname{csupp}(PM)$ is finite. One easily checks that $(i)$
$P^{T}\mathbf{1}_{L^{\prime}}=\mathbf{1}_{L}$, and $(ii)$ $PP^{T}$ is a
diagonal matrix. Using that both $MM^{T}$ and $PP^{T}$ are diagonal, we find
that $M_{/\pi}(M_{/\pi})^{T}=PMM^{T}P^{T}$ is diagonal, too. Moreover, since
the trace of a diagonal matrix equals the sum of its entries, we obtain

$\displaystyle\operatorname{tr}({M}_{/\pi}({M}_{/\pi})^{T})=\mathbf{1}_{L^{\prime}}^{T}{M}_{/\pi}({M}_{/\pi})^{T}\mathbf{1}_{L^{\prime}}=\mathbf{1}_{L^{\prime}}^{T}P{M}{M}^{T}P^{T}\mathbf{1}_{L^{\prime}}=\mathbf{1}_{L}^{T}{M}{M}^{T}\mathbf{1}_{L}=\operatorname{tr}({M}{M}^{T})=1.$

It follows that ${M}_{/\pi}\in{\mathscr{S}}^{(L^{\prime})}$. Furthermore, one
easily checks that ${M}_{/id}={M}$ and, given
$\tilde{\pi}:[L^{\prime}]\rightarrow[L^{\prime\prime}]$,
$({M}_{/\pi})_{/\tilde{\pi}}={M}_{/\tilde{\pi}\circ\pi}$, which concludes the
proof that ${\mathscr{S}}$ is a minion. The fact that ${\mathscr{S}}$ is
linear directly follows from Definition 16. ∎

Recall from Remark 18 that, for a $\sigma$-structure $\mathbf{A}$, a symbol
$R\in\sigma$ of arity $r$, and a number $i\in[r]$, $P_{i}$ is the
$|A|\times|R^{\mathbf{A}}|$ matrix whose $(a,\mathbf{a})$-th entry is $1$ if
$a_{i}=a$, and $0$ otherwise. In order to show that $\operatorname{SDP}$ is a
minion test corresponding to the minion ${\mathscr{S}}$, we shall use the
following simple description of the entries of $P_{i}$.

######  Lemma 27 ([44]).

Let $\mathbf{A}$ be a $\sigma$-structure, let $R\in\sigma$ of arity $r$, and
let $i\in[r],a\in A$. Then,

$\displaystyle\mathbf{e}_{a}^{T}P_{i}=\sum_{\begin{subarray}{c}\mathbf{a}\in
R^{\mathbf{A}}\\\ a_{i}=a\end{subarray}}\mathbf{e}_{\mathbf{a}}^{T}.$

In order to prove that
$\operatorname{SDP}=\operatorname{Test}_{{\mathscr{S}}}$, we essentially need
to encode the vectors ${\bm{\lambda}}$ witnessing an $\operatorname{SDP}$
solution as rows of matrices belonging to ${\mathscr{S}}$. To this end, we
need to solve the following “size problem”: The vectors ${\bm{\lambda}}$ live
in a vector space having a fixed, finite dimension – namely, the number
$\omega=|X|\cdot|A|+\sum_{R\in\sigma}|R^{\mathbf{X}}|\cdot|R^{\mathbf{A}}|$.
On the other hand, the matrices in ${\mathscr{S}}$ have rows of infinite size,
living in $\mathbb{R}^{\aleph_{0}}$. This issue is easily solved by
considering an $\omega$-dimensional subspace of $\mathbb{R}^{\aleph_{0}}$ and
working in an orthonormal basis of such subspace, through a standard
orthonormalisation argument.

######  Proposition (Proposition 8 restated).

$\operatorname{SDP}=\operatorname{Test}_{{\mathscr{S}}}$. In other words,
given two $\sigma$-structures $\mathbf{X}$ and $\mathbf{A}$,
$\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ if and only if
$\mathbf{X}\to\mathbb{F}_{{\mathscr{S}}}(\mathbf{A})$.

###### Proof.

Suppose that $\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$, and let
the family of vectors
${\bm{\lambda}}_{x,a},{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}\in\mathbb{R}^{\omega}$
witness it, for $x\in X,a\in A,R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},\mathbf{a}\in R^{\mathbf{A}}$, where
$\omega=|X|\cdot|A|+\sum_{R\in\sigma}|R^{\mathbf{X}}|\cdot|R^{\mathbf{A}}|$.
Consider the map $\xi:X\to{\mathscr{S}}^{(n)}$ defined by

$\displaystyle\mathbf{e}_{a}^{T}\xi(x)\mathbf{e}_{j}=\left\\{\begin{array}[]{lllll}\mathbf{e}_{j}^{T}{\bm{\lambda}}_{x,a}&\mbox{
if }j\leq\omega\\\ 0&\mbox{ otherwise}\end{array}\right.\hskip 28.45274ptx\in
X,a\in A,j\in\mathbb{N}.$

We claim that $\xi$ is well defined. For each $x\in X$, we have
$\xi(x)\in\mathcal{T}^{n,{\aleph_{0}}}(\mathbb{R})$. Moreover,
$\xi(x)\mathbf{e}_{j}=\mathbf{0}$ for each $j>\omega$, so C1 is satisfied.
Given $a,a^{\prime}\in A$,

$\displaystyle\mathbf{e}_{a}^{T}\xi(x)\xi(x)^{T}\mathbf{e}_{a^{\prime}}=\sum_{j\in\mathbb{N}}\mathbf{e}_{a}^{T}\xi(x)\mathbf{e}_{j}\mathbf{e}_{j}^{T}\xi(x)^{T}\mathbf{e}_{a^{\prime}}=\sum_{j\leq\omega}\mathbf{e}_{j}^{T}{\bm{\lambda}}_{x,a}{\bm{\lambda}}_{x,a^{\prime}}^{T}\mathbf{e}_{j}={\bm{\lambda}}_{x,a}\cdot{\bm{\lambda}}_{x,a^{\prime}}.$

If $a\neq a^{\prime}$, this quantity is zero by $\vardiamond 2$, so C2 is
satisfied. Finally,

$\displaystyle\operatorname{tr}(\xi(x)\xi(x)^{T})$ $\displaystyle=\sum_{a\in
A}\mathbf{e}_{a}^{T}\xi(x)\xi(x)^{T}\mathbf{e}_{a}=\sum_{a\in
A}\|{\bm{\lambda}}_{x,a}\|^{2}=1$

by $\vardiamond 1$, so C3 is also satisfied and the claim is true. We now show
that $\xi$ yields a homomorphism from $\mathbf{X}$ to
$\mathbb{F}_{{\mathscr{S}}}(\mathbf{A})$. Take $R\in\sigma$ of arity $r$ and
$\mathbf{x}=(x_{1},\dots,x_{r})\in R^{\mathbf{X}}$. Consider the matrix
$Q\in\mathcal{T}^{|R^{\mathbf{A}}|,{\aleph_{0}}}(\mathbb{R})$ defined by

$\displaystyle\mathbf{e}_{\mathbf{a}}^{T}Q\mathbf{e}_{j}=\left\\{\begin{array}[]{lllll}\mathbf{e}_{j}^{T}{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}&\mbox{
if }j\leq\omega\\\ 0&\mbox{ otherwise}\end{array}\right.\hskip
28.45274pt\mathbf{a}\in R^{\mathbf{A}},j\in\mathbb{N}.$

Using the same arguments as above, we check that $Q$ satisfies C1 and that
$\mathbf{e}_{\mathbf{a}}^{T}QQ^{T}\mathbf{e}_{\mathbf{a}^{\prime}}={\bm{\lambda}}_{R,\mathbf{x}\,\mathbf{a}}\cdot{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}^{\prime}}$,
so C2 follows from $\vardiamond 3$ and C3 from point $(ii)$ of Proposition 55.
Therefore, $Q\in{\mathscr{S}}^{(|R^{\mathbf{A}}|)}$. We now claim that
$\xi(x_{i})=Q_{/\pi_{i}}$ for each $i\in[r]$. Indeed, for $a\in A$ and
$j\in[\omega]$, we have

$\displaystyle\mathbf{e}_{a}^{T}\xi(x_{i})\mathbf{e}_{j}$
$\displaystyle=\mathbf{e}_{j}^{T}{\bm{\lambda}}_{x_{i},a}=\sum_{\begin{subarray}{c}\mathbf{a}\in
R^{\mathbf{A}}\\\
a_{i}=a\end{subarray}}\mathbf{e}_{j}^{T}{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}=\sum_{\begin{subarray}{c}\mathbf{a}\in
R^{\mathbf{A}}\\\
a_{i}=a\end{subarray}}\mathbf{e}_{\mathbf{a}}^{T}Q\mathbf{e}_{j}=\mathbf{e}_{a}^{T}P_{i}Q\mathbf{e}_{j}=\mathbf{e}_{a}^{T}Q_{/\pi_{i}}\mathbf{e}_{j},$

where the second and fourth equalities follow from $\vardiamond 4$ and Lemma
27, respectively. Also, clearly,

$\displaystyle\mathbf{e}_{a}^{T}\xi(x_{i})\mathbf{e}_{j}=\mathbf{e}_{a}^{T}Q_{/\pi_{i}}\mathbf{e}_{j}=0$

if $j\in\mathbb{N}\setminus[\omega]$. As a consequence, the claim holds. It
follows that $\xi(\mathbf{x})\in R^{\mathbb{F}_{{\mathscr{S}}}(\mathbf{A})}$,
so that $\xi$ is a homomorphism.

Conversely, let $\xi:\mathbf{X}\to\mathbb{F}_{{\mathscr{S}}}(\mathbf{A})$ be a
homomorphism. For $R\in\sigma$ of arity $r$ and
$\mathbf{x}=(x_{1},\dots,x_{r})\in R^{\mathbf{X}}$, we can fix a matrix
$Q_{R,\mathbf{x}}\in{\mathscr{S}}^{(|R^{\mathbf{A}}|)}$ satisfying
$\xi(x_{i})={Q_{R,\mathbf{x}}}_{/\pi_{i}}$ for each $i\in[r]$. Consider the
sets $S_{1}=\\{\xi(x)^{T}\mathbf{e}_{a}:x\in X,a\in A\\}$ and
$S_{2}=\\{Q_{R,\mathbf{x}}^{T}\mathbf{e}_{\mathbf{a}}:R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},\mathbf{a}\in R^{\mathbf{A}}\\}$, and the vector space
$\mathcal{U}=\operatorname{span}(S_{1}\cup
S_{2})\subseteq\mathbb{R}^{\aleph_{0}}$. Observe that
$\dim\mathcal{U}\leq|S_{1}\cup
S_{2}|\leq|S_{1}|+|S_{2}|\leq|X|\cdot|A|+\sum_{R\in\sigma}|R^{\mathbf{X}}|\cdot|R^{\mathbf{A}}|=\omega$.
Consider a vector space $\mathcal{V}$ of dimension $\omega$ such that
$\mathcal{U}\subseteq\mathcal{V}\subseteq\mathbb{R}^{\aleph_{0}}$. Using the
Gram-Schmidt process,151515We note that the Gram-Schmidt process also applies
to vector spaces of countably infinite dimension. we find a projection matrix
${Z}\in\mathcal{T}^{{\aleph_{0}},\omega}(\mathbb{R})$ such that
${Z}^{T}{Z}=I_{\omega}$ and ${Z}{Z}^{T}\mathbf{v}=\mathbf{v}$ for any
$\mathbf{v}\in\mathcal{V}$. Consider the family of vectors

$\displaystyle\begin{array}[]{lllll}{\bm{\lambda}}_{x,a}={Z}^{T}\xi(x)^{T}\mathbf{e}_{a}&x\in
X,a\in A,\\\
{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}={Z}^{T}Q_{R,\mathbf{x}}^{T}\mathbf{e}_{\mathbf{a}}&R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},\mathbf{a}\in R^{\mathbf{A}}.\end{array}$ (18)

We claim that (18) witnesses that
$\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$. To check
$\vardiamond 1$, observe that

$\displaystyle\sum_{a\in A}\|{\bm{\lambda}}_{x,a}\|^{2}$
$\displaystyle=\sum_{a\in
A}\mathbf{e}_{a}^{T}\xi(x){Z}{Z}^{T}\xi(x)^{T}\mathbf{e}_{a}=\sum_{a\in
A}\mathbf{e}_{a}^{T}\xi(x)\xi(x)^{T}\mathbf{e}_{a}=\operatorname{tr}(\xi(x)\xi(x)^{T})=1,$

where the second equality follows from the fact that
$\xi(x)^{T}\mathbf{e}_{a}\in S_{1}\subseteq\mathcal{U}\subseteq\mathcal{V}$
and the fourth from C3. In a similar way, using C2, we obtain

$\displaystyle{\bm{\lambda}}_{x,a}\cdot{\bm{\lambda}}_{x,a^{\prime}}$
$\displaystyle=\mathbf{e}_{a}^{T}\xi(x){Z}{Z}^{T}\xi(x)^{T}\mathbf{e}_{a^{\prime}}=\mathbf{e}_{a}^{T}\xi(x)\xi(x)^{T}\mathbf{e}_{a^{\prime}}=0,$
$\displaystyle{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}\cdot{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}^{\prime}}$
$\displaystyle=\mathbf{e}_{\mathbf{a}}^{T}Q_{R,\mathbf{x}}{Z}{Z}^{T}Q_{R,\mathbf{x}}^{T}\mathbf{e}_{\mathbf{a}^{\prime}}=\mathbf{e}_{\mathbf{a}}^{T}Q_{R,\mathbf{x}}Q_{R,\mathbf{x}}^{T}\mathbf{e}_{\mathbf{a}^{\prime}}=0$

if $a\neq a^{\prime}\in A$ and $\mathbf{a}\neq\mathbf{a}^{\prime}\in
R^{\mathbf{A}}$. This shows that $\vardiamond 2$ and $\vardiamond 3$ hold.
Finally, to prove $\vardiamond 4$, we observe that

$\displaystyle\sum_{\begin{subarray}{c}\mathbf{a}\in R^{\mathbf{A}}\\\
a_{i}=a\end{subarray}}{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}$
$\displaystyle=\sum_{\begin{subarray}{c}\mathbf{a}\in R^{\mathbf{A}}\\\
a_{i}=a\end{subarray}}{Z}^{T}Q_{R,\mathbf{x}}^{T}\mathbf{e}_{\mathbf{a}}=\big{(}\sum_{\begin{subarray}{c}\mathbf{a}\in
R^{\mathbf{A}}\\\
a_{i}=a\end{subarray}}\mathbf{e}_{\mathbf{a}}^{T}Q_{R,\mathbf{x}}{Z}\big{)}^{T}=\big{(}\mathbf{e}_{a}^{T}P_{i}Q_{R,\mathbf{x}}{Z}\big{)}^{T}=\big{(}\mathbf{e}_{a}^{T}\xi(x_{i}){Z}\big{)}^{T}$
$\displaystyle={Z}^{T}\xi(x_{i})^{T}\mathbf{e}_{a}={\bm{\lambda}}_{x_{i},a},$

where the third equality follows from Lemma 27. Therefore, the claim is true
and the proof is complete. ∎

Using Propositions 8 and 6, we immediately have the following algebraic
characterisation of the power of $\operatorname{SDP}$.

######  Theorem (Theorem 9 restated).

Let $(\mathbf{A},\mathbf{B})$ be a $\operatorname{PCSP}$ template. Then,
$\operatorname{SDP}$ solves $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if
and only if ${\mathscr{S}}\to\operatorname{Pol}(\mathbf{A},\mathbf{B})$.

##  7 Hierarchies of minion tests

In this section, we start studying the _hierarchies of minion tests_
introduced in Definition 12, by describing two properties that are common to
all such hierarchies: They are complete, and they become tighter as the level
increases. A finer description will be available in the next sections, where
we will focus on hierarchies built on minions having a _linear_ or _conic_
form.

The next proposition shows that the tensorisation construction described in
Definition 10 does not alter whether two structures are homomorphic or not. We
let $\operatorname{\operatorname{Hom}}(\mathbf{A},\mathbf{B})$ denote the set
of homomorphisms from $\mathbf{A}$ to $\mathbf{B}$.

######  Proposition 28.

Let $k\in\mathbb{N}$ and let $\mathbf{A},\mathbf{B}$ be two
$\sigma$-structures. Then

  1. $(i)$

$\mathbf{A}\to\mathbf{B}$ if and only if
$\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbf{B}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$;

  2. $(ii)$

if $\mathbf{A}$ is $k$-enhanced, there is a bijection
$\rho:\operatorname{\operatorname{Hom}}(\mathbf{A},\mathbf{B})\to\operatorname{\operatorname{Hom}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}},\mathbf{B}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$.

###### Proof.

Let ${f}:\mathbf{A}\to\mathbf{B}$ be a homomorphism, and consider the function
$f^{\ast}:A^{k}\to B^{k}$ defined by
$f^{\ast}((a_{1},\dots,a_{k}))=({f}(a_{1}),\dots,{f}(a_{k}))$. Take
$R\in\sigma$ of arity $r$, and consider
$\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\in
R^{\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$,
where $\mathbf{a}\in R^{\mathbf{A}}$. Let $\mathbf{b}=f(\mathbf{a})$. Since
${f}$ is a homomorphism, $\mathbf{b}\in R^{\mathbf{B}}$, so
$\mathbf{b}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\in
R^{\mathbf{B}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$.
For any $\mathbf{i}\in[r]^{k}$, we have

$\displaystyle E_{\mathbf{i}}\ast
f^{\ast}\left(\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\right)$
$\displaystyle=f^{\ast}\left(E_{\mathbf{i}}\ast\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\right)=f^{\ast}(\mathbf{a}_{\mathbf{i}})={f}(\mathbf{a}_{\mathbf{i}})=({f}(\mathbf{a}))_{\mathbf{i}}=\mathbf{b}_{\mathbf{i}}=E_{\mathbf{i}}\ast\mathbf{b}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}},$

which yields
$f^{\ast}(\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})=\mathbf{b}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\in
R^{\mathbf{B}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$.
Hence,
$f^{\ast}:\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbf{B}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
is a homomorphism.

Conversely, let
$g:\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbf{B}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
be a homomorphism. We define the function $g_{\ast}:A\to B$ by setting
$g_{\ast}(a)=\mathbf{e}_{1}^{T}g((a,\dots,a))$ for each $a\in A$. Take
$R\in\sigma$ of arity $r$, and consider a tuple
$\mathbf{a}=(a_{1},\dots,a_{r})\in R^{\mathbf{A}}$. Since
$\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\in
R^{\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$
and $g$ is a homomorphism, we have that
$g(\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\in
R^{\mathbf{B}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$.
Therefore,
$g(\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})=\mathbf{b}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
for some $\mathbf{b}=(b_{1},\dots,b_{r})\in R^{\mathbf{B}}$. For each
$j\in[r]$, consider the tuple $\mathbf{i}=(j,\dots,j)\in[r]^{k}$ and observe
that

$\displaystyle
g((a_{j},\dots,a_{j}))=g(\mathbf{a}_{\mathbf{i}})=g\left(E_{\mathbf{i}}\ast\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\right)=E_{\mathbf{i}}\ast
g(\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})=E_{\mathbf{i}}\ast\mathbf{b}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}=\mathbf{b}_{\mathbf{i}}=(b_{j},\dots,b_{j}).$

Hence, we find

$\displaystyle
g_{\ast}(\mathbf{a})=\left(\mathbf{e}_{1}^{T}g((a_{1},\dots,a_{1})),\dots,\mathbf{e}_{1}^{T}g((a_{r},\dots,a_{r}))\right)=\left(b_{1},\dots,b_{r}\right)=\mathbf{b}\in
R^{\mathbf{B}}.$

Therefore, $g_{\ast}:\mathbf{A}\to\mathbf{B}$ is a homomorphism. This
concludes the proof of $(i)$.

To prove $(ii)$, observe first that, if $\mathbf{A}\not\to\mathbf{B}$, then
$\operatorname{\operatorname{Hom}}(\mathbf{A},\mathbf{B})=\operatorname{\operatorname{Hom}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}},\mathbf{B}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})=\emptyset$,
so there is a trivial bijection in this case. If $\mathbf{A}\to\mathbf{B}$,
consider the map
$\rho:\operatorname{\operatorname{Hom}}(\mathbf{A},\mathbf{B})\to\operatorname{\operatorname{Hom}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}},\mathbf{B}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
defined by $f\mapsto f^{\ast}$ and the map
$\rho^{\prime}:\operatorname{\operatorname{Hom}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}},\mathbf{B}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\to\operatorname{\operatorname{Hom}}(\mathbf{A},\mathbf{B})$
defined by $g\mapsto g_{\ast}$. For $f:\mathbf{A}\to\mathbf{B}$ and $a\in A$,
we have

$\displaystyle(f^{\ast})_{\ast}(a)=\mathbf{e}_{1}^{T}f^{\ast}((a,\dots,a))=\mathbf{e}_{1}^{T}(f(a),\dots,f(a))=f(a)$

so that
$\rho^{\prime}\circ\rho=\operatorname{id}_{\operatorname{\operatorname{Hom}}(\mathbf{A},\mathbf{B})}$.
Consider now
$g:\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbf{B}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$,
and take $\mathbf{a}=(a_{1},\dots,a_{k})\in A^{k}$. Using the assumption that
$\mathbf{A}$ is $k$-enhanced, we have $\mathbf{a}\in R_{k}^{\mathbf{A}}$,
which implies
$\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\in
R_{k}^{\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$.
Hence,
$g(\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\in
R_{k}^{\mathbf{B}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$,
so
$g(\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})=\mathbf{b}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
for some $\mathbf{b}=(b_{1},\dots,b_{k})\in R_{k}^{\mathbf{B}}\subseteq
B^{k}$. For $j\in[k]$ and $\mathbf{i}=(j,\dots,j)\in[k]^{k}$, we have

$\displaystyle
g((a_{j},\dots,a_{j}))=g(\mathbf{a}_{\mathbf{i}})=g\left(E_{\mathbf{i}}\ast\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\right)=E_{\mathbf{i}}\ast
g\left(\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\right)=E_{\mathbf{i}}\ast\mathbf{b}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}=\mathbf{b}_{\mathbf{i}}=(b_{j},\dots,b_{j}).$

Letting $\mathbf{i}^{\prime}=(1,\dots,k)\in[k]^{k}$, we obtain

$\displaystyle(g_{\ast})^{\ast}(\mathbf{a})$
$\displaystyle=(g_{\ast}(a_{1}),\dots,g_{\ast}(a_{k}))=\left(\mathbf{e}_{1}^{T}g((a_{1},\dots,a_{1})),\dots,\mathbf{e}_{1}^{T}g((a_{k},\dots,a_{k}))\right)=(b_{1},\dots,b_{k})$
$\displaystyle=\mathbf{b}=\mathbf{b}_{\mathbf{i}^{\prime}}=E_{\mathbf{i}^{\prime}}\ast\mathbf{b}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}=E_{\mathbf{i}^{\prime}}\ast
g\left(\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\right)=g\left(E_{\mathbf{i}^{\prime}}\ast\mathbf{a}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\right)=g(\mathbf{a}_{\mathbf{i}^{\prime}})=g(\mathbf{a}),$

so that
$\rho\circ\rho^{\prime}=\operatorname{id}_{\operatorname{\operatorname{Hom}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}},\mathbf{B}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$,
which concludes the proof of $(ii)$. ∎

######  Remark 29.

Part $(ii)$ of Proposition 28 does not hold in general if we relax the
requirement that $\mathbf{A}$ be $k$-enhanced. More precisely, in this case,
the function
$\rho:\operatorname{\operatorname{Hom}}(\mathbf{A},\mathbf{B})\to\operatorname{\operatorname{Hom}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}},\mathbf{B}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
defined in the proof of Proposition 28 still needs to be injective, but may
not be surjective. Therefore, we have
$\left|\operatorname{\operatorname{Hom}}(\mathbf{A},\mathbf{B})\right|\leq\left|\operatorname{\operatorname{Hom}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}},\mathbf{B}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\right|$,
and the inequality may be strict.

For example, consider the Boolean structure $\mathbf{A}$ having a unique unary
relation $R_{1}^{\mathbf{A}}=A=\\{0,1\\}$. So, $\mathbf{A}$ is $1$-enhanced
but not $2$-enhanced. Observe that
$|\operatorname{\operatorname{Hom}}(\mathbf{A},\mathbf{A})|=4$. The tensorised
structure
$\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny2}⃝}}}$
has domain $\\{0,1\\}^{2}=\\{(0,0),(0,1),\allowbreak(1,0),(1,1)\\}$, and its
(unary) relation is
$R_{1}^{\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny2}⃝}}}}=\\{0^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny2}⃝}}},1^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny2}⃝}}}\\}=\\{(0,0),(1,1)\\}$.
Therefore, each map $f:\\{0,1\\}^{2}\to\\{0,1\\}^{2}$ such that
$f((0,0))\in\\{(0,0),(1,1)\\}$ and $f((1,1))\in\\{(0,0),\allowbreak(1,1)\\}$
yields a proper homomorphism
$\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny2}⃝}}}\to\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny2}⃝}}}$.
It follows that
$\left|\operatorname{\operatorname{Hom}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny2}⃝}}},\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny2}⃝}}})\right|=64$,
so $\operatorname{\operatorname{Hom}}(\mathbf{A},\mathbf{A})$ and
$\operatorname{\operatorname{Hom}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny2}⃝}}},\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tiny2}⃝}}})$
are not in bijection.

It readily follows from Proposition 28 that hierarchies of minion tests are
always complete.

######  Proposition (Proposition 13 restated).

$\operatorname{Test}_{{\mathscr{M}}}^{k}$ is complete for any minion
${\mathscr{M}}$ and any integer $k\in\mathbb{N}$.

###### Proof.

Let $\mathbf{X}$ and $\mathbf{A}$ be two $k$-enhanced $\sigma$-structures and
suppose that $\mathbf{X}\to\mathbf{A}$. Proposition 28 yields
$\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$,
while Lemma 24 yields
$\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$.
The composition of the two homomorphisms witnesses that
$\operatorname{Test}_{{\mathscr{M}}}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$,
as required. ∎

We conclude the section by showing that hierarchies of minion tests become
tighter as the level increases.

######  Proposition (Proposition 14 restated).

Let ${\mathscr{M}}$ be a minion, let $k,p\in\mathbb{N}$ be such that $k>p$,
and let $\mathbf{X},\mathbf{A}$ be two $k$\- and $p$-enhanced
$\sigma$-structures. If
$\operatorname{Test}_{{\mathscr{M}}}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$
then
$\operatorname{Test}_{{\mathscr{M}}}^{p}(\mathbf{X},\mathbf{A})=\textsc{Yes}$.

###### Proof.

Let
$\xi:\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
be a homomorphism witnessing that
$\operatorname{Test}_{{\mathscr{M}}}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$.
Since $k>p$, we can choose two tuples $\mathbf{v}\in[k]^{p}$ and
$\mathbf{w}\in[p]^{k}$ such that $\mathbf{w}_{\mathbf{v}}=(1,\dots,p)$. (For
instance, we may take $\mathbf{v}=(1,\ldots,p)$ and
$\mathbf{w}=(1,\ldots,p,\ldots,p)$.) Consider the map $\tau:A^{k}\to A^{p}$
defined by $\mathbf{a}\mapsto\mathbf{a}_{\mathbf{v}}$. We claim that the map
$\vartheta:X^{p}\to{\mathscr{M}}^{(n^{p})}$ defined by
$\mathbf{x}\mapsto\xi(\mathbf{x}_{\mathbf{w}})_{/\tau}$ yields a homomorphism
from
$\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyp}⃝}}}$
to
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyp}⃝}}})$,
thus witnessing that
$\operatorname{Test}_{{\mathscr{M}}}^{p}(\mathbf{X},\mathbf{A})=\textsc{Yes}$.
To that end, for $R\in\sigma$, take $\mathbf{x}\in R^{\mathbf{X}}$ and observe
that, since $\xi$ is a homomorphism and
$\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\in
R^{\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$,
$\xi(\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\in
R^{\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$.
Therefore, there exists $Q\in{\mathscr{M}}^{(|R^{\mathbf{A}}|)}$ satisfying
$\xi(\mathbf{x}_{\mathbf{i}})=Q_{/\pi_{\mathbf{i}}}$ for each
$\mathbf{i}\in[r]^{k}$. If we manage to show that
$\vartheta(\mathbf{x}_{\mathbf{j}})=Q_{/\pi_{\mathbf{j}}}$ for each
$\mathbf{j}\in[r]^{p}$, we would deduce that
$\vartheta(\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyp}⃝}}})\in
R^{\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyp}⃝}}})}$,
thus proving the claim. Observe that

$\displaystyle\vartheta(\mathbf{x}_{\mathbf{j}})$
$\displaystyle=\xi(\mathbf{x}_{\mathbf{j}_{\mathbf{w}}})_{/\tau}=(Q_{/\pi_{\mathbf{j}_{\mathbf{w}}}})_{/\tau}=Q_{/\tau\,\circ\,\pi_{\mathbf{j}_{\mathbf{w}}}},$

so we are left to show that
$\tau\circ\pi_{\mathbf{j}_{\mathbf{w}}}=\pi_{\mathbf{j}}$. Indeed, given any
$\mathbf{a}\in R^{\mathbf{A}}$,

$\displaystyle(\tau\circ\pi_{\mathbf{j}_{\mathbf{w}}})(\mathbf{a})$
$\displaystyle=\tau(\pi_{\mathbf{j}_{\mathbf{w}}}(\mathbf{a}))=\tau(\mathbf{a}_{\mathbf{j}_{\mathbf{w}}})=\mathbf{a}_{\mathbf{j}_{\mathbf{w}_{\mathbf{v}}}}=\mathbf{a}_{\mathbf{j}}=\pi_{\mathbf{j}}(\mathbf{a}),$

as required. ∎

As noted in Section 3, it follows from Proposition 14 that if a
$\operatorname{PCSP}$ template is solved by some level of a minion test, then
it is also solved by any higher level.

##  8 Hierarchies of linear minion tests

By the Definition 12 of a hierarchy of minion tests,
$\operatorname{Test}_{{\mathscr{M}}}^{k}$ applied to an instance $\mathbf{X}$
of $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ checks for the existence of a
homomorphism from
$\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
to
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$.
Therefore, to describe the hierarchy and get knowledge on its functioning it
is necessary to study the structure
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$.
This is done by investigating how the tensorisation construction interacts
with the free structure of the minion ${\mathscr{M}}$ on which the hierarchy
is built. In this section, we show that, if we consider minions having a
“matrix form” – namely, the _linear minions_ of Definition 16 –
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
is a space of highly structured tensors, which we can describe using the tools
of multilinear algebra. Restricting the focus on this class of minions may
strike as artificial. The next result argues that the choice is in fact quite
natural, as all the minions that have been hitherto utilised in the literature
on $\operatorname{(P)CSPs}$ to capture the power of algorithms (including the
minion ${\mathscr{S}}$ introduced in this work) are linear. In particular, the
machinery we build in this section (and in Section 9, where we consider an
even more specialised minion class) shall be crucial to show that the
framework of hierarchies of minion tests captures various well-known
hierarchies of relaxations (cf. Theorem 15).

######  Proposition (Proposition 17 restated).

The following minions are linear:

$\displaystyle\bullet\;\;\mathscr{H},\mbox{ with
}\mathcal{S}=(\\{0,1\\},\vee,\wedge)\mbox{ and }{d}=1$
$\displaystyle\bullet\;\;{\mathscr{Q}_{\operatorname{conv}}},\mbox{ with
}\mathcal{S}=\mathbb{Q}\mbox{ and }{d}=1$
$\displaystyle\bullet\;\;{\mathscr{Z}_{\operatorname{aff}}},\mbox{ with
}\mathcal{S}=\mathbb{Z}\mbox{ and }{d}=1$
$\displaystyle\bullet\;\;{\mathscr{S}},\mbox{ with
}\mathcal{S}=\mathbb{R}\mbox{ and }{d}={\aleph_{0}}$
$\displaystyle\bullet\;\;\mathscr{M}_{\operatorname{BA}},\mbox{ with
}\mathcal{S}=\mathbb{Q}\mbox{ and }{d}=2.$

###### Proof.

The result for ${\mathscr{Q}_{\operatorname{conv}}}$,
${\mathscr{Z}_{\operatorname{aff}}}$, and $\mathscr{M}_{\operatorname{BA}}$
directly follows from their definitions in Example 2, while the result for
${\mathscr{S}}$ is clear from Proposition 26.

As for $\mathscr{H}$, recall its description given in Example 2. Given
$L\in\mathbb{N}$ and $\emptyset\neq{Z}\subseteq[L]$, we identify the Boolean
function $f_{Z}=\bigwedge_{{z}\in{Z}}x_{z}\in\mathscr{H}^{(L)}$ with the
indicator vector $\mathbf{v}_{Z}\in\\{0,1\\}^{L}$ whose $i$-th entry, for
$i\in[L]$, is $1$ if $i\in{Z}$, and $0$ otherwise. To conclude, we need to
show that, under this identification, the minor operations of $\mathscr{H}$
correspond to the minor operations given in part 3 of Definition 16. In other
words, we claim that the function ${f_{Z}}_{/\pi}$ corresponds to the vector
$P\mathbf{v}_{Z}$ for any $L^{\prime}\in\mathbb{N}$ and any
$\pi:[L]\to[L^{\prime}]$, where $P$ is the $L^{\prime}\times L$ matrix given
in Definition 16. First, observe that

$\displaystyle{f_{Z}}_{/\pi}(x_{1},\dots,x_{L^{\prime}})$
$\displaystyle=f_{Z}(x_{\pi(1)},\dots,x_{\pi(L)})=\bigwedge_{{z}\in{Z}}x_{\pi({z})}=\bigwedge_{t\in\pi({Z})}x_{t}=f_{\pi({Z})}(x_{1},\dots,x_{L^{\prime}}),$

so ${f_{Z}}_{/\pi}=f_{\pi({Z})}$. To conclude, we need to show that
$P\mathbf{v}_{Z}=\mathbf{v}_{\pi({Z})}$, where $\mathbf{v}_{\pi({Z})}$ is the
indicator vector of the nonempty set $\pi({Z})\subseteq[L^{\prime}]$. Notice
that the matrix multiplication is performed in the semiring
$\mathcal{S}=(\\{0,1\\},\vee,\wedge)$. For any $i\in[L^{\prime}]$, we have

$\displaystyle\mathbf{e}_{i}^{T}P\mathbf{v}_{Z}$
$\displaystyle=\bigvee_{j\in[L]}\left((\mathbf{e}_{i}^{T}P\mathbf{e}_{j})\wedge(\mathbf{e}_{j}^{T}\mathbf{v}_{Z})\right)=\bigvee_{\begin{subarray}{c}j\in{Z}\\\
\pi(j)=i\end{subarray}}1=\bigvee_{i\in\pi({Z})}1=\mathbf{e}_{i}^{T}\mathbf{v}_{\pi({Z})},$

as required. ∎

Let ${\mathscr{M}}$ be a linear minion. We have seen in Section 3 (cf. Remark
18) that in this case the structure lying at the core of
$\operatorname{Test}_{{\mathscr{M}}}$ – i.e., the free structure
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A})$ generated by a $\sigma$-structure
$\mathbf{A}$ – consists in a space of matrices with relations defined through
specific matrix products. We now describe the geometry of the structure lying
at the core of the _multilinear test_
$\operatorname{Test}_{{\mathscr{M}}}^{k}$ – which, by virtue of Definition 12,
is
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$.
Given a semiring $\mathcal{S}$, a symbol $R\in\sigma$ of arity $r$, and a
tuple $\mathbf{i}\in[r]^{k}$, consider the tensor
$P_{\mathbf{i}}\in\mathcal{T}^{n\cdot\mathbf{1}_{k},|R^{\mathbf{A}}|}(\mathcal{S})$
defined by

$\displaystyle E_{\mathbf{a}}\ast P_{\mathbf{i}}\ast
E_{\mathbf{a}^{\prime}}=\left\\{\begin{array}[]{cl}1&\mbox{if
}\mathbf{a}^{\prime}_{\mathbf{i}}=\mathbf{a}\\\
0&\mbox{otherwise}\end{array}\right.\hskip
28.45274pt\forall\mathbf{a}\in{A}^{k},\mathbf{a}^{\prime}\in R^{\mathbf{A}}.$
(21)

Observe that the tensor $P_{\mathbf{i}}$ is the multilinear equivalent of the
matrix $P_{i}$ from Remark 18.

Let ${\mathscr{M}}$ be a linear minion with semiring $\mathcal{S}$ and depth
$d$. The domain of
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
is ${\mathscr{M}}^{(n^{k})}$, which we visualise as a subset of
$\mathcal{T}^{n\cdot\mathbf{1}_{k},d}(\mathcal{S})$. Given a symbol
$R\in\sigma$ of arity $r$, consider a block tensor
$M=(M_{\mathbf{i}})_{\mathbf{i}\in[r]^{k}}\in\mathcal{T}^{r\cdot\mathbf{1}_{k}}(\mathcal{T}^{n\cdot\mathbf{1}_{k},d}(\mathcal{S}))=\mathcal{T}^{rn\cdot\mathbf{1}_{k},d}(\mathcal{S})$.
From the definition of free structure, we have that $M\in
R^{\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$
if and only if there exists $Q\in{\mathscr{M}}^{(|R^{\mathbf{A}}|)}$ such that
$M_{\mathbf{i}}=Q_{/\pi_{\mathbf{i}}}=P_{\mathbf{i}}\overset{\tiny 1}{\ast}Q$
for each $\mathbf{i}\in[r]^{k}$.

We now show that the entries of $P_{\mathbf{i}}$ satisfy the following simple
equality, analogous to Lemma 27.

######  Lemma 30.

Let $k\in\mathbb{N}$, let $\mathbf{A}$ be a $\sigma$-structure, let
$R\in\sigma$ of arity $r$, and consider the tuples $\mathbf{a}\in{A}^{k}$ and
$\mathbf{i}\in[r]^{k}$. Then

$\displaystyle E_{\mathbf{a}}\ast
P_{\mathbf{i}}=\sum_{\begin{subarray}{c}\mathbf{b}\in R^{\mathbf{A}}\\\
\mathbf{b}_{\mathbf{i}}=\mathbf{a}\end{subarray}}E_{\mathbf{b}}.$

###### Proof.

For any $\mathbf{a}^{\prime}\in R^{\mathbf{A}}$, we have

$\displaystyle\left(\sum_{\begin{subarray}{c}\mathbf{b}\in R^{\mathbf{A}}\\\
\mathbf{b}_{\mathbf{i}}=\mathbf{a}\end{subarray}}E_{\mathbf{b}}\right)\ast
E_{\mathbf{a}^{\prime}}=\sum_{\begin{subarray}{c}\mathbf{b}\in
R^{\mathbf{A}}\\\
\mathbf{b}_{\mathbf{i}}=\mathbf{a}\end{subarray}}(E_{\mathbf{b}}\ast
E_{\mathbf{a}^{\prime}})=\sum_{\begin{subarray}{c}\mathbf{b}\in
R^{\mathbf{A}}\\\ \mathbf{b}_{\mathbf{i}}=\mathbf{a}\\\
\mathbf{b}=\mathbf{a}^{\prime}\end{subarray}}1=\left\\{\begin{array}[]{cl}1&\mbox{if
}\mathbf{a}^{\prime}_{\mathbf{i}}=\mathbf{a}\\\
0&\mbox{otherwise}\end{array}\right.=(E_{\mathbf{a}}\ast P_{\mathbf{i}})\ast
E_{\mathbf{a}^{\prime}},$

from which the result follows. ∎

The next lemma shows that certain entries of a tensor in the relation
$R^{\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$
(i.e., the interpretation of $R$ in the free structure of ${\mathscr{M}}$
generated by
$\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$)
need to be zero.

######  Lemma 31.

Let ${\mathscr{M}}$ be a linear minion, let $k\in\mathbb{N}$, let $\mathbf{A}$
be a $\sigma$-structure, let $R\in\sigma$ of arity $r$, and suppose
$M=(M_{\mathbf{i}})_{\mathbf{i}\in[r]^{k}}\in
R^{\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$.
Then $E_{\mathbf{a}}\ast M_{\mathbf{i}}=\mathbf{0}_{d}$ for any
$\mathbf{i}\in[r]^{k}$, $\mathbf{a}\in{A}^{k}$ such that
$\mathbf{i}\not\prec\mathbf{a}$.

###### Proof.

Observe that there exists $Q\in{\mathscr{M}}^{(|R^{\mathbf{A}}|)}$ such that
$M_{\mathbf{i}}=Q_{/\pi_{\mathbf{i}}}$ for each $\mathbf{i}\in[r]^{k}$. Using
Lemma 30, we obtain

$\displaystyle E_{\mathbf{a}}\ast M_{\mathbf{i}}$
$\displaystyle=E_{\mathbf{a}}\ast
Q_{/\pi_{\mathbf{i}}}=E_{\mathbf{a}}\ast(P_{\mathbf{i}}\overset{\tiny
1}{\ast}Q)=E_{\mathbf{a}}\ast P_{\mathbf{i}}\ast
Q=\sum_{\begin{subarray}{c}\mathbf{b}\in R^{\mathbf{A}}\\\
\mathbf{b}_{\mathbf{i}}=\mathbf{a}\end{subarray}}E_{\mathbf{b}}\ast
Q=\mathbf{0}_{d},$

where the last equality follows from the fact that
$\mathbf{b}_{\mathbf{i}}=\mathbf{a}$ implies $\mathbf{i}\prec\mathbf{a}$;
indeed, in that case, $i_{\alpha}=i_{\beta}$ implies
$a_{\alpha}=b_{i_{\alpha}}=b_{i_{\beta}}=a_{\beta}$. ∎

It follows from Lemma 31 and the previous discussion that, if ${\mathscr{M}}$
is linear,
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
can be visualised as a space of sparse and highly symmetric tensors (see also
Example 19 and Figure 1). The geometry of this space is reflected in the
properties of the homomorphisms from the $k$-th tensor power of an instance
$\mathbf{X}$ to
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
– which correspond to solutions of $\operatorname{Test}_{{\mathscr{M}}}^{k}$,
cf. Definition 12. Lemma 32, Lemma 33, and Proposition 36 highlight certain
features of such homomorphisms that will be used to prove Theorem 15 in
Section 11.

######  Lemma 32.

Let ${\mathscr{M}}$ be a linear minion, let $k\in\mathbb{N}$, let
$\mathbf{X},\mathbf{A}$ be two $k$-enhanced $\sigma$-structures, and let
$\xi:\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
be a homomorphism. Then $E_{\mathbf{a}}\ast\xi(\mathbf{x})=\mathbf{0}_{d}$ for
any $\mathbf{x}\in X^{k}$, $\mathbf{a}\in A^{k}$ such that
$\mathbf{x}\not\prec\mathbf{a}$.

###### Proof.

From $\mathbf{x}\in X^{k}=R_{k}^{\mathbf{X}}$, we derive
$\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\in
R_{k}^{\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$;
since $\xi$ is a homomorphism, this yields
$\xi(\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\in
R_{k}^{\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$.
Writing
$\xi(\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
in block form as
$\xi(\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})=(\xi(\mathbf{x}_{\mathbf{i}}))_{\mathbf{i}\in[k]^{k}}$
and applying Lemma 31, we obtain
$E_{\mathbf{a}}\ast\xi(\mathbf{x}_{\mathbf{i}})=\mathbf{0}_{d}$ for any
$\mathbf{i}\in[k]^{k}$ such that $\mathbf{i}\not\prec\mathbf{a}$. Write
$\mathbf{x}=(x_{1},\dots,x_{k})$ and $\mathbf{a}=(a_{1},\dots,a_{k})$. Since
$\mathbf{x}\not\prec\mathbf{a}$, there exist $\alpha,\beta\in[k]$ such that
$x_{\alpha}=x_{\beta}$ and $a_{\alpha}\neq a_{\beta}$. Let
$\mathbf{i}^{\prime}\in[k]^{k}$ be the tuple obtained from $(1,\dots,k)$ by
replacing the $\beta$-th entry with $\alpha$. Observe that
$\mathbf{x}_{\mathbf{i}^{\prime}}=\mathbf{x}$ and
$\mathbf{i}^{\prime}\not\prec\mathbf{a}$. Hence,

$\displaystyle\mathbf{0}_{d}=E_{\mathbf{a}}\ast\xi(\mathbf{x}_{\mathbf{i}^{\prime}})=E_{\mathbf{a}}\ast\xi(\mathbf{x}),$

as required. ∎

Using Lemma 32, we obtain some more information on the image of a homomorphism
from
$\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
to
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$.
Given a signature $\sigma$, we let $\operatorname{armax}(\sigma)$ denote the
maximum arity of a relation symbol in $\sigma$.

######  Lemma 33.

Let ${\mathscr{M}}$ be a linear minion, let $k\in\mathbb{N}$, let
$\mathbf{X},\mathbf{A}$ be two $k$-enhanced $\sigma$-structures such that
$k\geq\operatorname{armax}(\sigma)$, and let
$\xi:\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
be a homomorphism. For $R\in\sigma$ of arity $r$, let $\mathbf{x}\in
R^{\mathbf{X}}$ and $\mathbf{a}\in R^{\mathbf{A}}$ be such that
$\mathbf{x}\not\prec\mathbf{a}$. Let $Q\in{\mathscr{M}}^{(|R^{\mathbf{A}}|)}$
be such that $Q_{/\pi_{\mathbf{i}}}=\xi(\mathbf{x}_{\mathbf{i}})$ for each
$\mathbf{i}\in[r]^{k}$. Then $E_{\mathbf{a}}\ast Q=\mathbf{0}_{d}$.

###### Proof.

Write $\mathbf{x}=(x_{1},\dots,x_{r})$ and $\mathbf{a}=(a_{1},\dots,a_{r})$.
Since $\mathbf{x}\not\prec\mathbf{a}$, there exist $\alpha,\beta\in[r]$ such
that $x_{\alpha}=x_{\beta}$ and $a_{\alpha}\neq a_{\beta}$. Using that $k\geq
r$, we can take the tuple $\mathbf{i}=(1,2,\dots,r,r,\dots,r)\in[r]^{k}$.
Consider $\mathbf{x}_{\mathbf{i}}\in X^{k}$, $\mathbf{a}_{\mathbf{i}}\in
A^{k}$. Notice that $x_{i_{\alpha}}=x_{\alpha}=x_{\beta}=x_{i_{\beta}}$ and
$a_{i_{\alpha}}=a_{\alpha}\neq a_{\beta}=a_{i_{\beta}}$, so
$\mathbf{x}_{\mathbf{i}}\not\prec\mathbf{a}_{\mathbf{i}}$. Applying Lemma 32,
we find

$\displaystyle\mathbf{0}_{d}=E_{\mathbf{a}_{\mathbf{i}}}\ast\xi(\mathbf{x}_{\mathbf{i}})=E_{\mathbf{a}_{\mathbf{i}}}\ast
Q_{/\pi_{\mathbf{i}}}=E_{\mathbf{a}_{\mathbf{i}}}\ast P_{\mathbf{i}}\ast Q.$

Using Lemma 30, we conclude that

$\displaystyle\mathbf{0}_{d}$
$\displaystyle=\sum_{\begin{subarray}{c}\mathbf{b}\in R^{\mathbf{A}}\\\
\mathbf{b}_{\mathbf{i}}=\mathbf{a}_{\mathbf{i}}\end{subarray}}E_{\mathbf{b}}\ast
Q=E_{\mathbf{a}}\ast Q,$

where the last equality follows from the fact that
$\mathbf{b}_{\mathbf{i}}=\mathbf{a}_{\mathbf{i}}$ if and only if
$\mathbf{b}=\mathbf{a}$. ∎

If $\mathbf{X}$ and $\mathbf{A}$ are $k$-enhanced $\sigma$-structures, any
homomorphism $\xi$ from
$\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
to
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
must satisfy certain symmetries that ultimately depend on the fact that $\xi$
preserves $R_{k}$. As shown below in Proposition 36, these symmetries can be
concisely expressed through a tensor equation. Given a tuple
$\mathbf{i}\in[k]^{k}$, we let
$\Pi_{\mathbf{i}}\in\mathcal{T}^{n\cdot\mathbf{1}_{2k}}(\mathcal{S})$ be the
tensor defined by

$\displaystyle E_{\mathbf{a}}\ast\Pi_{\mathbf{i}}\ast
E_{\mathbf{a}^{\prime}}=\left\\{\begin{array}[]{ll}1&\mbox{if
}\mathbf{a}^{\prime}_{\mathbf{i}}=\mathbf{a}\\\
0&\mbox{otherwise}\end{array}\right.\hskip
28.45274pt\forall\mathbf{a},\mathbf{a}^{\prime}\in{A}^{k}.$ (24)

The tensor defined above satisfies the following simple identity, which should
be compared to the one in Lemma 30 concerning the tensor $P_{\mathbf{i}}$.

######  Lemma 34.

For any $\mathbf{a}\in{A}^{k}$ and $\mathbf{i}\in[k]^{k}$,

$\displaystyle
E_{\mathbf{a}}\ast\Pi_{\mathbf{i}}=\sum_{\begin{subarray}{c}\mathbf{b}\in{A}^{k}\\\
\mathbf{b}_{\mathbf{i}}=\mathbf{a}\end{subarray}}E_{\mathbf{b}}.$

###### Proof.

For any $\mathbf{a}^{\prime}\in{A}^{k}$, we have

$\displaystyle\left(\sum_{\begin{subarray}{c}\mathbf{b}\in{A}^{k}\\\
\mathbf{b}_{\mathbf{i}}=\mathbf{a}\end{subarray}}E_{\mathbf{b}}\right)\ast
E_{\mathbf{a}^{\prime}}=\sum_{\begin{subarray}{c}\mathbf{b}\in{A}^{k}\\\
\mathbf{b}_{\mathbf{i}}=\mathbf{a}\end{subarray}}(E_{\mathbf{b}}\ast
E_{\mathbf{a}^{\prime}})=\sum_{\begin{subarray}{c}\mathbf{b}\in{A}^{k}\\\
\mathbf{b}_{\mathbf{i}}=\mathbf{a}\\\
\mathbf{b}=\mathbf{a}^{\prime}\end{subarray}}1=\left\\{\begin{array}[]{ll}1&\mbox{if
}\mathbf{a}^{\prime}_{\mathbf{i}}=\mathbf{a}\\\
0&\mbox{otherwise}\end{array}\right.=\left(E_{\mathbf{a}}\ast\Pi_{\mathbf{i}}\right)\ast
E_{\mathbf{a}^{\prime}},$

from which the result follows. ∎

######  Remark 35.

It is clear from the expressions (21) and (24) that, for any
$\mathbf{i}\in[k]^{k}$, $\Pi_{\mathbf{i}}$ coincides with the tensor
$P_{\mathbf{i}}$ associated with the relation symbol $R_{k}$.

######  Proposition 36.

Let ${\mathscr{M}}$ be a linear minion, let $k\in\mathbb{N}$, let
$\mathbf{X},\mathbf{A}$ be two $k$-enhanced $\sigma$-structures, and let
$\xi:X^{k}\to{\mathscr{M}}^{(n^{k})}$ be a map. Then, $\xi$ preserves $R_{k}$
if and only if

$\displaystyle\xi(\mathbf{x}_{\mathbf{i}})=\Pi_{\mathbf{i}}\overset{\tiny
k}{\ast}\xi(\mathbf{x})\hskip 56.9055pt\mbox{for any }\;\mathbf{x}\in
X^{k},\mathbf{i}\in[k]^{k}.$ (25)

###### Proof.

Suppose that $\xi$ preserves $R_{k}$, and take $\mathbf{x}\in
X^{k}=R_{k}^{\mathbf{X}}$. It follows that
$\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\in
R_{k}^{\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$,
so
$\xi(\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\in
R_{k}^{\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$.
This means that there exists
$Q\in{\mathscr{M}}^{(|R_{k}^{\mathbf{A}}|)}={\mathscr{M}}^{(n^{k})}$ such that
$\xi(\mathbf{x}_{\mathbf{i}})=Q_{/\pi_{\mathbf{i}}}=\Pi_{\mathbf{i}}\overset{\tiny
k}{\ast}Q$ for each $\mathbf{i}\in[k]^{k}$ (where we have used Remark 35).
Consider now the tuple $\mathbf{j}=(1,\dots,k)\in[k]^{k}$, and observe that
$\mathbf{x}_{\mathbf{j}}=\mathbf{x}$. Noticing that the contraction by
$\Pi_{\mathbf{j}}$ acts as the identity, we conclude that

$\displaystyle\xi(\mathbf{x})=\xi(\mathbf{x}_{\mathbf{j}})=\Pi_{\mathbf{j}}\overset{\tiny
k}{\ast}{Q}={Q},$

which concludes the proof of (25).

Conversely, suppose (25) holds and take $\mathbf{x}\in
R_{k}^{\mathbf{X}}=X^{k}$. We need to show that
$\xi(\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\in
R_{k}^{\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$.
Take
$Q=\xi(\mathbf{x})\in{\mathscr{M}}^{(n^{k})}={\mathscr{M}}^{(|R_{k}^{\mathbf{A}}|)}$.
Using again Remark 35, we observe that, for any $\mathbf{i}\in[k]^{k}$,

$\displaystyle\xi(\mathbf{x}_{\mathbf{i}})$
$\displaystyle=\Pi_{\mathbf{i}}\overset{\tiny
k}{\ast}\xi(\mathbf{x})=\xi(\mathbf{x})_{/\pi_{\mathbf{i}}}=Q_{/\pi_{\mathbf{i}}},$

whence the result follows. ∎

##  9 Hierarchies of conic minion tests

The machinery developed in Section 8 applies to hierarchies of tests built on
_any_ linear minion. It turns out that certain finer features of hierarchies
of minion tests can be deduced if we assume that the minion is _conic_ ; i.e.,
that, in addition to being linear, it enjoys a sort of nonnegativity
requirement described in Definition 20. As we establish next, all minions
considered in this work are conic, with the notable exception of
${\mathscr{Z}_{\operatorname{aff}}}$.

######  Proposition (Proposition 21 restated).

$\mathscr{H}$, ${\mathscr{Q}_{\operatorname{conv}}}$, ${\mathscr{S}}$, and
$\mathscr{M}_{\operatorname{BA}}$ are conic minions, while
${\mathscr{Z}_{\operatorname{aff}}}$ is not.

###### Proof.

The fact that ${\mathscr{Q}_{\operatorname{conv}}}$ is conic trivially follows
by noting that its elements are nonnegative vectors whose entries sum up to
$1$. Similarly, using the description of $\mathscr{H}$ as a linear minion on