the semiring $(\\{0,1\\},\vee,\wedge)$ (cf. the proof of Proposition 17), the
fact that $\mathscr{H}$ is conic follows from the fact that $\bigvee_{i\in
V}x_{i}=0$ means that $x_{i}=0$ for each $i\in V$. (Observe also that the
vectors in $\mathscr{H}$ are nonzero, as they are the indicator vectors of
nonempty sets.) To show that ${\mathscr{S}}$ is conic, take $L\in\mathbb{N}$
and $M\in{\mathscr{S}}^{(L)}$, and notice first that $M\neq
O_{L,{\aleph_{0}}}$ by C3 in Definition 7. Take now $V\subseteq[L]$. If
$\sum_{i\in V}M^{T}\mathbf{e}_{i}=\mathbf{0}_{\aleph_{0}}$, using that
$MM^{T}$ is a diagonal matrix by C2, we find

$\displaystyle 0=(\sum_{i\in V}M^{T}\mathbf{e}_{i})^{T}(\sum_{j\in
V}M^{T}\mathbf{e}_{j})=\sum_{i,j\in
V}\mathbf{e}_{i}^{T}MM^{T}\mathbf{e}_{j}=\sum_{i\in
V}\mathbf{e}_{i}^{T}MM^{T}\mathbf{e}_{i}=\sum_{i\in
V}\|M^{T}\mathbf{e}_{i}\|^{2},$

which means that $M^{T}\mathbf{e}_{i}=\mathbf{0}_{\aleph_{0}}$ for any $i\in
V$, as required. As for $\mathscr{M}_{\operatorname{BA}}$, we shall see in
Section 10 (cf. Example 43) that this minion can be obtained as the semi-
direct product of ${\mathscr{Q}_{\operatorname{conv}}}$ and
${\mathscr{Z}_{\operatorname{aff}}}$. Then, the fact that
$\mathscr{M}_{\operatorname{BA}}$ is conic is a direct consequence of the fact
that semi-direct products of minions are always conic (cf. Proposition 40).
Finally, the element $(1,-1,1)\in{\mathscr{Z}_{\operatorname{aff}}}$ witnesses
that ${\mathscr{Z}_{\operatorname{aff}}}$ is not conic. ∎

It turns out that Lemma 33 can be slightly strengthened if we are dealing with
conic minions, in that the level $k$ for which it holds can be decreased down
to $2$. As a consequence, the algebraic description of the Sherali-Adams and
Sum-of-Squares hierarchies in terms of the tensorisation construction can be
extended to lower levels, cf. Remark 51. As in Section 8, the letter $d$ shall
denote the depth of the relevant minion in all results of this section.
(Recall that a conic minion is linear, by definition).

######  Lemma 37.

Let ${\mathscr{M}}$ be a conic minion, let $2\leq 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. 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.

Take $\alpha,\beta\in[r]$ such that $x_{\alpha}=x_{\beta}$ and $a_{\alpha}\neq
a_{\beta}$, and consider the tuple
$\mathbf{j}=(\alpha,\dots,\alpha,\beta)\in[r]^{k}$. Using that $k\geq 2$, we
have $\mathbf{x}_{\mathbf{j}}\not\prec\mathbf{a}_{\mathbf{j}}$, since
$x_{j_{k-1}}=x_{\alpha}=x_{\beta}=x_{j_{k}}$ and $a_{j_{k-1}}=a_{\alpha}\neq
a_{\beta}=a_{j_{k}}$. From Lemma 32 and Lemma 30 we obtain

$\displaystyle\mathbf{0}_{d}=E_{\mathbf{a}_{\mathbf{j}}}\ast\xi(\mathbf{x}_{\mathbf{j}})=E_{\mathbf{a}_{\mathbf{j}}}\ast
Q_{/\pi_{\mathbf{j}}}=E_{\mathbf{a}_{\mathbf{j}}}\ast P_{\mathbf{j}}\ast
Q=\sum_{\begin{subarray}{c}\mathbf{b}\in R^{\mathbf{A}}\\\
\mathbf{b}_{\mathbf{j}}=\mathbf{a}_{\mathbf{j}}\end{subarray}}E_{\mathbf{b}}\ast
Q.$

Using that ${\mathscr{M}}$ is a conic minion, we deduce that
$E_{\mathbf{b}}\ast Q=\mathbf{0}_{d}$ for any $\mathbf{b}\in R^{\mathbf{A}}$
such that $\mathbf{b}_{\mathbf{j}}=\mathbf{a}_{\mathbf{j}}$. In particular,
$E_{\mathbf{a}}\ast Q=\mathbf{0}_{d}$, as required. ∎

The following result shows that hierarchies of tests built on conic minions
only give a nonzero weight to those assignments that yield partial
homomorphisms.

######  Proposition 38.

Let ${\mathscr{M}}$ be a conic minion, let $k\in\mathbb{N}$, let
$\mathbf{X},\mathbf{A}$ be two $k$-enhanced $\sigma$-structures such that
$k\geq\min(2,\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. Let $R\in\sigma$ have arity $r$, and take $\mathbf{x}\in
X^{k}$, $\mathbf{a}\in A^{k}$, and $\mathbf{i}\in[k]^{r}$. If
$\mathbf{x}_{\mathbf{i}}\in R^{\mathbf{X}}$ and
$\mathbf{a}_{\mathbf{i}}\not\in R^{\mathbf{A}}$, then
$E_{\mathbf{a}}\ast\xi(\mathbf{x})=\mathbf{0}_{d}$.

###### Proof.

From $\mathbf{x}_{\mathbf{i}}\in R^{\mathbf{X}}$ we have
$\mathbf{x}_{\mathbf{i}}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\in
R^{\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$
and, thus,
$\xi(\mathbf{x}_{\mathbf{i}}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\in
R^{\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$.
It follows that there exists ${Q}\in{\mathscr{M}}^{(|R^{\mathbf{A}}|)}$ such
that $\xi(\mathbf{x}_{\mathbf{i}_{\mathbf{j}}})={Q}_{/\pi_{\mathbf{j}}}$ for
each $\mathbf{j}\in[r]^{k}$. Proposition 36 then yields

$\displaystyle\Pi_{\mathbf{i}_{\mathbf{j}}}\overset{\tiny
k}{\ast}\xi(\mathbf{x})$
$\displaystyle=\xi(\mathbf{x}_{\mathbf{i}_{\mathbf{j}}})={Q}_{/\pi_{\mathbf{j}}}=P_{\mathbf{j}}\overset{\tiny
1}{\ast}{Q}.$ (26)

Consider, for each $\alpha\in[k]$, the set
$S_{\alpha}=\\{\beta\in[r]:i_{\beta}=\alpha\\}$, and fix an element
$\hat{\beta}\in[r]$. The tuple $\mathbf{j}\in[r]^{k}$ defined by setting
$j_{\alpha}=\min S_{\alpha}$ if $S_{\alpha}\neq\emptyset$,
$j_{\alpha}=\hat{\beta}$ otherwise satisfies
$\mathbf{i}_{\mathbf{j}_{\mathbf{i}}}=\mathbf{i}$. Indeed, for any
$\beta\in[r]$, we have $S_{i_{\beta}}\neq\emptyset$ since $\beta\in
S_{i_{\beta}}$, so $j_{i_{\beta}}=\min S_{i_{\beta}}\in S_{i_{\beta}}$, which
means that $i_{j_{i_{\beta}}}=i_{\beta}$, as required. We obtain

$\displaystyle E_{\mathbf{a}_{\mathbf{i}_{\mathbf{j}}}}\ast
P_{\mathbf{j}}\ast{Q}$ $\displaystyle=\sum_{\begin{subarray}{c}\mathbf{b}\in
R^{\mathbf{A}}\\\
\mathbf{b}_{\mathbf{j}}=\mathbf{a}_{\mathbf{i}_{\mathbf{j}}}\end{subarray}}E_{\mathbf{b}}\ast{Q}=\sum_{\begin{subarray}{c}\mathbf{b}\in
R^{\mathbf{A}}\\\ \mathbf{x}_{\mathbf{i}}\prec\mathbf{b}\\\
\mathbf{b}_{\mathbf{j}}=\mathbf{a}_{\mathbf{i}_{\mathbf{j}}}\end{subarray}}E_{\mathbf{b}}\ast{Q},$
(27)

where the first equality comes from Lemma 30 and the second from Lemma 33 or
Lemma 37 (depending on whether $k\geq\operatorname{armax}(\sigma)$ or $k\geq
2$). We claim that the sum on the right-hand side of (27) equals
$\mathbf{0}_{d}$. Indeed, let $\mathbf{b}\in A^{r}$ satisfy
$\mathbf{x}_{\mathbf{i}}\prec\mathbf{b}$ and
$\mathbf{b}_{\mathbf{j}}=\mathbf{a}_{\mathbf{i}_{\mathbf{j}}}$. Since
$\mathbf{i}_{\mathbf{j}_{\mathbf{i}}}=\mathbf{i}$, for any $\alpha\in[r]$ we
have $x_{i_{\alpha}}=x_{i_{j_{i_{\alpha}}}}$ and, hence,
$b_{\alpha}=b_{j_{i_{\alpha}}}$. It follows that
$\mathbf{b}=\mathbf{b}_{\mathbf{j}_{\mathbf{i}}}=\mathbf{a}_{\mathbf{i}_{\mathbf{j}_{\mathbf{i}}}}=\mathbf{a}_{\mathbf{i}}\not\in
R^{\mathbf{A}}$, which proves the claim. Combining this with (26), (27), and
Lemma 34, we find

$\displaystyle\mathbf{0}_{d}$
$\displaystyle=E_{\mathbf{a}_{\mathbf{i}_{\mathbf{j}}}}\ast
P_{\mathbf{j}}\ast{Q}=E_{\mathbf{a}_{\mathbf{i}_{\mathbf{j}}}}\ast(P_{\mathbf{j}}\overset{\tiny
1}{\ast}Q)=E_{\mathbf{a}_{\mathbf{i}_{\mathbf{j}}}}\ast(\Pi_{\mathbf{i}_{\mathbf{j}}}\overset{\tiny
k}{\ast}\xi(\mathbf{x}))=E_{\mathbf{a}_{\mathbf{i}_{\mathbf{j}}}}\ast\Pi_{\mathbf{i}_{\mathbf{j}}}\ast\xi(\mathbf{x})$
$\displaystyle=\sum_{\begin{subarray}{c}\mathbf{b}\in A^{k}\\\
\mathbf{b}_{\mathbf{i}_{\mathbf{j}}}=\mathbf{a}_{\mathbf{i}_{\mathbf{j}}}\end{subarray}}E_{\mathbf{b}}\ast\xi(\mathbf{x})$

so, in particular, $E_{\mathbf{a}}\ast\xi(\mathbf{x})=\mathbf{0}_{d}$ since
${\mathscr{M}}$ is a conic minion. ∎

The next result shows that hierarchies of tests built on conic minions are
“sound in the limit”, in the sense that they correctly classify all instances
whose domain size is less than or equal to the hierarchy level.

######  Proposition 39.

Let ${\mathscr{M}}$ be a conic minion, let $2\leq k\in\mathbb{N}$, let
$\mathbf{X},\mathbf{A}$ be two $k$-enhanced $\sigma$-structures such that
$|X|\leq k$, and suppose that
$\operatorname{Test}_{{\mathscr{M}}}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$.
Then $\mathbf{X}\to\mathbf{A}$.

###### 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}$,
and assume without loss of generality that $X=[\ell]$ with $\ell\in[k]$. Take
the tuple $\mathbf{v}=(1,\dots,\ell,\ell,\dots,\ell)\in[\ell]^{k}$, and notice
that $\xi(\mathbf{v})\neq O_{n^{k},d}$ since ${\mathscr{M}}$ is a conic
minion. Therefore, there exists some $\mathbf{a}\in A^{k}$ such that
$E_{\mathbf{a}}\ast\xi(\mathbf{v})\neq\mathbf{0}_{d}$. Consider the function
$f:X\to A$ defined by $x\to a_{x}$ for each $x\in X$. We claim that $f$ yields
a homomorphism from $\mathbf{X}$ to $\mathbf{A}$.

Let $R\in\sigma$ be a relation symbol of arity $r$, take a tuple
$\mathbf{x}\in R^{\mathbf{X}}$, and suppose, for the sake of contradiction,
that $f(\mathbf{x})\not\in R^{\mathbf{A}}$. Notice that
$\mathbf{x}\in[\ell]^{r}\subseteq[k]^{r}$ and that
$f(\mathbf{x})=\mathbf{a}_{\mathbf{x}}$. Since $\mathbf{x}\in R^{\mathbf{X}}$,
we have
$\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\in
R^{\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$.
Being $\xi$ a homomorphism, this implies that
$\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, $\exists Q\in{\mathscr{M}}^{(|R^{\mathbf{A}}|)}$ such that
$\xi(\mathbf{x}_{\mathbf{i}})=Q_{/\pi_{\mathbf{i}}}$ for each
$\mathbf{i}\in[r]^{k}$. Observe that

$\displaystyle
E_{\mathbf{a}_{\mathbf{x}_{\mathbf{i}}}}\ast\xi({\mathbf{x}_{\mathbf{i}}})$
$\displaystyle=E_{\mathbf{a}_{\mathbf{x}_{\mathbf{i}}}}\ast{Q}_{/\pi_{\mathbf{i}}}=E_{\mathbf{a}_{\mathbf{x}_{\mathbf{i}}}}\ast(P_{\mathbf{i}}\overset{\tiny
1}{\ast}{Q})=E_{\mathbf{a}_{\mathbf{x}_{\mathbf{i}}}}\ast
P_{\mathbf{i}}\ast{Q}=\sum_{\begin{subarray}{c}\mathbf{c}\in R^{\mathbf{A}}\\\
\mathbf{c}_{\mathbf{i}}=\mathbf{a}_{\mathbf{x}_{\mathbf{i}}}\end{subarray}}E_{\mathbf{c}}\ast{Q}=\sum_{\begin{subarray}{c}\mathbf{c}\in
R^{\mathbf{A}}\\\
\mathbf{c}_{\mathbf{i}}=\mathbf{a}_{\mathbf{x}_{\mathbf{i}}}\\\
\mathbf{x}\prec\mathbf{c}\end{subarray}}E_{\mathbf{c}}\ast{Q},$ (28)

where the fourth equality comes from Lemma 30 and the fifth from Lemma 37. On
the other hand, noting that $\mathbf{v}_{\mathbf{x}}=\mathbf{x}$, Proposition
36 and Lemma 34 yield

$\displaystyle
E_{\mathbf{a}_{\mathbf{x}_{\mathbf{i}}}}\ast\xi({\mathbf{x}_{\mathbf{i}}})$
$\displaystyle=E_{\mathbf{a}_{\mathbf{x}_{\mathbf{i}}}}\ast\xi(\mathbf{v}_{\mathbf{x}_{\mathbf{i}}})=E_{\mathbf{a}_{\mathbf{x}_{\mathbf{i}}}}\ast(\Pi_{\mathbf{x}_{\mathbf{i}}}\overset{\tiny
k}{\ast}\xi(\mathbf{v}))$
$\displaystyle=E_{\mathbf{a}_{\mathbf{x}_{\mathbf{i}}}}\ast\Pi_{\mathbf{x}_{\mathbf{i}}}\ast\xi(\mathbf{v})=\sum_{\begin{subarray}{c}\mathbf{b}\in{A}^{k}\\\
\mathbf{b}_{\mathbf{x}_{\mathbf{i}}}=\mathbf{a}_{\mathbf{x}_{\mathbf{i}}}\end{subarray}}E_{\mathbf{b}}\ast\xi(\mathbf{v}).$
(29)

If
$E_{\mathbf{a}_{\mathbf{x}_{\mathbf{i}}}}\ast\xi({\mathbf{x}_{\mathbf{i}}})=\mathbf{0}_{d}$,
using that ${\mathscr{M}}$ is a conic minion, we would deduce from (9) that
$E_{\mathbf{b}}\ast\xi(\mathbf{v})=\mathbf{0}_{d}$ for any $\mathbf{b}\in
A^{k}$ such that
$\mathbf{b}_{\mathbf{x}_{\mathbf{i}}}=\mathbf{a}_{\mathbf{x}_{\mathbf{i}}}$;
in particular, $E_{\mathbf{a}}\ast\xi(\mathbf{v})=\mathbf{0}_{d}$, a
contradiction. Therefore,
$E_{\mathbf{a}_{\mathbf{x}_{\mathbf{i}}}}\ast\xi({\mathbf{x}_{\mathbf{i}}})\neq\mathbf{0}_{d}$.
Then, it follows from (28) that, for each $\mathbf{i}\in[r]^{k}$, there exists
some $\mathbf{c}=(c_{1},\dots,c_{r})\in R^{\mathbf{A}}$ such that
$\mathbf{c}_{\mathbf{i}}=\mathbf{a}_{\mathbf{x}_{\mathbf{i}}}$ and
$\mathbf{x}\prec\mathbf{c}$. Choose $\mathbf{i}$ so that
$\\{\mathbf{x}\\}=\\{\mathbf{x}_{\mathbf{i}}\\}$. Since $\mathbf{c}\in
R^{\mathbf{A}}$ and $\mathbf{a}_{\mathbf{x}}\not\in R^{\mathbf{A}}$, we have
$\mathbf{c}\neq\mathbf{a}_{\mathbf{x}}$; so, $c_{p}\neq a_{x_{p}}$ for some
$p\in[r]$. From $x_{p}\in\\{\mathbf{x}\\}=\\{\mathbf{x}_{\mathbf{i}}\\}$, we
obtain $x_{p}=x_{i_{t}}$ for some $t\in[k]$. Since
$\mathbf{x}\prec\mathbf{c}$, this yields $c_{p}=c_{i_{t}}$. Therefore,
$c_{i_{t}}=c_{p}\neq a_{x_{p}}=a_{x_{i_{t}}}$, so
$\mathbf{c}_{\mathbf{i}}\neq\mathbf{a}_{\mathbf{x}_{\mathbf{i}}}$, a
contradiction. We conclude that $f(\mathbf{x})\in R^{\mathbf{A}}$, so $f$
yields a homomorphism from $\mathbf{X}$ to $\mathbf{A}$, as claimed. ∎

##  10 The semi-direct product of minions

Is it possible for multiple linear minions to “join forces”, to obtain a new
linear minion corresponding to a stronger relaxation? The natural way to do so
is to take as the elements of the new linear minion block matrices, whose
blocks are the elements of the original minions. Let ${\mathscr{M}}$ and
${\mathscr{N}}$ be two linear minions that we wish to “merge”. A zero row in a
matrix of ${\mathscr{M}}$ corresponds to zero weight assigned to the variable
associated with the row by the relaxation given by ${\mathscr{M}}$. Ideally,
we would like to preserve this information when we run the relaxation given by
the second minion ${\mathscr{N}}$. In other words, we require that zero rows
in ${\mathscr{M}}$ should be associated with zero rows in ${\mathscr{N}}$. For
this to make sense (i.e., for the resulting object to be a linear minion), we
need to assume that ${\mathscr{M}}$ is conic. Under this assumption, it turns
out that the new linear minion is conic, too. Therefore, this construction
yields a method to transform a linear minion into a conic one, by taking its
product with a fixed conic minion (for instance,
${\mathscr{Q}_{\operatorname{conv}}}$). Equivalently, the semi-direct product
provides a way to turn a hierarchy of linear tests into a more powerful
hierarchy of conic tests – which enjoys the appealing properties described in
Section 9.

######  Proposition 40.

Let ${\mathscr{M}}$ be a conic minion with semiring $\mathcal{S}$ and depth
$d$, let ${\mathscr{N}}$ be a linear minion with semiring $\mathcal{S}$ and
depth $d^{\prime}$, and consider, for each $L\in\mathbb{N}$, the set
$({\mathscr{M}}\ltimes{\mathscr{N}})^{(L)}=\\{[\begin{array}[]{cc}M&N\end{array}]:M\in{\mathscr{M}}^{(L)},N\in{\mathscr{N}}^{(L)},\mbox{
and }N^{T}\mathbf{e}_{i}=\mathbf{0}_{d^{\prime}}\mbox{ for any }i\in[L]\mbox{
such that }M^{T}\mathbf{e}_{i}=\mathbf{0}_{d}\\}$. Then
${\mathscr{M}}\ltimes{\mathscr{N}}=\bigcup_{L\in\mathbb{N}}({\mathscr{M}}\ltimes{\mathscr{N}})^{(L)}$
is a conic minion with semiring $\mathcal{S}$ and depth $d+d^{\prime}$.

######  Definition 41.

Let ${\mathscr{M}}$ and ${\mathscr{N}}$ be a conic minion and a linear minion,
respectively, over the same semiring. The _semi-direct product_ of
${\mathscr{M}}$ and ${\mathscr{N}}$ is the conic minion
${\mathscr{M}}\ltimes{\mathscr{N}}$ described in Proposition 40.

######  Remark 42.

If the minions ${\mathscr{M}}$ and ${\mathscr{N}}$ in Definition 41 have
different semirings $\mathcal{S}$ and $\mathcal{S}^{\prime}$, we cannot in
general use the definition to build their semi-direct product. However, it is
immediate to check that a linear minion over $\mathcal{S}$ is also a linear
minion over any semiring of which $\mathcal{S}$ is a sub-semiring. Hence, if
$\mathcal{S}$ is a sub-semiring of $\mathcal{S}^{\prime}$ (or vice-versa),
${\mathscr{M}}\ltimes{\mathscr{N}}$ is well defined (see Example 43 below). In
general, however, we might not be able to find a common semiring of which
$\mathcal{S}$ and $\mathcal{S}^{\prime}$ are both sub-semirings. In
particular, it is not true in general that the direct sum of semirings admits
homomorphic injections from the components, see [51]. To be able to define
${\mathscr{M}}\ltimes{\mathscr{N}}$ also in this case, we would need to
redefine linear minions by allowing each of the $d$ columns of the matrices in
a linear minion of depth $d$ to contain entries from a possibly different
semiring. In this way, the requirement in Definition 41 can be circumvented –
which, for example, makes it possible to define the minion
$\mathscr{H}\ltimes{\mathscr{Z}_{\operatorname{aff}}}$ (see Remark 52).

######  Example 43.

Since $\mathbb{Z}$ is a sub-semiring of $\mathbb{Q}$, we can view
${\mathscr{Q}_{\operatorname{conv}}}$ and ${\mathscr{Z}_{\operatorname{aff}}}$
as a conic minion and a linear minion over the same semiring $\mathbb{Q}$,
respectively. It is easy to check that their semi-direct product
${\mathscr{Q}_{\operatorname{conv}}}\ltimes{\mathscr{Z}_{\operatorname{aff}}}$
is precisely the minion $\mathscr{M}_{\operatorname{BA}}$ from [30].

###### Proof of Proposition 40.

We start by showing that ${\mathscr{M}}\ltimes{\mathscr{N}}$ is a linear
minion of depth $d+d^{\prime}$. Notice that each set
$({\mathscr{M}}\ltimes{\mathscr{N}})^{(L)}$ consists of
$L\times(d+d^{\prime})$ matrices having entries in $\mathcal{S}$. Given
$\pi:[L]\to[L^{\prime}]$ and
$[\begin{array}[]{cc}M&N\end{array}]\in({\mathscr{M}}\ltimes{\mathscr{N}})^{(L)}$,
we claim that
$P[\begin{array}[]{cc}M&N\end{array}]=[\begin{array}[]{cc}PM&PN\end{array}]$
belongs to $({\mathscr{M}}\ltimes{\mathscr{N}})^{(L^{\prime})}$, where $P$ is
the $L^{\prime}\times L$ matrix corresponding to $\pi$ as per Definition 16.
First, since ${\mathscr{M}}$ and ${\mathscr{N}}$ are both linear minions, we
have that $PM=M_{/\pi}\in{\mathscr{M}}^{(L^{\prime})}$ and
$PN=N_{/\pi}\in{\mathscr{N}}^{(L^{\prime})}$. Let $j\in[L^{\prime}]$ be such
that $(PM)^{T}\mathbf{e}_{j}=\mathbf{0}_{d}$. We find

$\displaystyle\mathbf{0}_{d}$
$\displaystyle=M^{T}P^{T}\mathbf{e}_{j}=\sum_{i\in\pi^{-1}(j)}M^{T}\mathbf{e}_{i}.$

Using that ${\mathscr{M}}$ is conic, we obtain
$M^{T}\mathbf{e}_{i}=\mathbf{0}_{d}$ for each $i\in\pi^{-1}(j)$. By the
definition of $({\mathscr{M}}\ltimes{\mathscr{N}})^{(L)}$, this means that
$N^{T}\mathbf{e}_{i}=\mathbf{0}_{d^{\prime}}$ for each $i\in\pi^{-1}(j)$.
Therefore,

$\displaystyle\mathbf{0}_{d^{\prime}}$
$\displaystyle=\sum_{i\in\pi^{-1}(j)}N^{T}\mathbf{e}_{i}=N^{T}P^{T}\mathbf{e}_{j}=(PN)^{T}\mathbf{e}_{j},$

which proves the claim. It follows that ${\mathscr{M}}\ltimes{\mathscr{N}}$ is
indeed a linear minion.

To show that ${\mathscr{M}}\ltimes{\mathscr{N}}$ is conic, we first note that
no element of ${\mathscr{M}}\ltimes{\mathscr{N}}$ is the all-zero matrix,
since ${\mathscr{M}}$ is conic. If $\sum_{i\in
V}[\begin{array}[]{cc}M&N\end{array}]^{T}\mathbf{e}_{i}=\mathbf{0}_{d+d^{\prime}}$
for some $L\in\mathbb{N}$,
$[\begin{array}[]{cc}M&N\end{array}]\in({\mathscr{M}}\ltimes{\mathscr{N}})^{(L)}$,
and $V\subseteq[L]$, we find in particular that $\sum_{i\in
V}M^{T}\mathbf{e}_{i}=\mathbf{0}_{d}$, which implies that
$M^{T}\mathbf{e}_{i}=\mathbf{0}_{d}$ for each $i\in V$ by the fact that
${\mathscr{M}}$ is conic. By the definition of
$({\mathscr{M}}\ltimes{\mathscr{N}})^{(L)}$, this yields
$N^{T}\mathbf{e}_{i}=\mathbf{0}_{d^{\prime}}$ for each $i\in V$, so

$\displaystyle[\begin{array}[]{cc}M&N\end{array}]^{T}\mathbf{e}_{i}$
$\displaystyle=\left[\begin{array}[]{cc}M^{T}\mathbf{e}_{i}\\\
N^{T}\mathbf{e}_{i}\end{array}\right]=\left[\begin{array}[]{cc}\mathbf{0}_{d}\\\
\mathbf{0}_{d^{\prime}}\end{array}\right]=\mathbf{0}_{d+d^{\prime}}$

for each $i\in V$, as required. ∎

The next result – crucial for the characterisation of the
$\operatorname{BA}^{k}$ hierarchy in Theorem 15, cf. the proof of Proposition
50 – shows that homomorphisms corresponding to the semi-direct product of two
minions factor into homomorphisms corresponding to the components.

######  Proposition 44.

Let ${\mathscr{M}}$ be a conic minion with semiring $\mathcal{S}$ and depth
$d$, let ${\mathscr{N}}$ be a linear minion with semiring $\mathcal{S}$ and
depth $d^{\prime}$, let $k\in\mathbb{N}$, and let $\mathbf{X},\mathbf{A}$ be
$k$-enhanced $\sigma$-structures such that
$k\geq\operatorname{armax}(\sigma)$. Then there exists a homomorphism
$\vartheta:\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbb{F}_{{\mathscr{M}}\ltimes{\mathscr{N}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
if and only if there exist homomorphisms
$\xi:\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbb{F}_{{\mathscr{M}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
and
$\zeta:\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbb{F}_{{\mathscr{N}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
such that, for any $\mathbf{x}\in X^{k}$ and $\mathbf{a}\in A^{k}$,
$E_{\mathbf{a}}\ast\xi(\mathbf{x})=\mathbf{0}_{d}$ implies
$E_{\mathbf{a}}\ast\zeta(\mathbf{x})=\mathbf{0}_{d^{\prime}}$.

###### Proof.

To prove the “if” part, take two homomorphisms $\xi$ and $\zeta$ as in the
statement of the proposition, and consider the map

$\displaystyle\vartheta:X^{k}$
$\displaystyle\to({\mathscr{M}}\ltimes{\mathscr{N}})^{(n^{k})}$
$\displaystyle\mathbf{x}$
$\displaystyle\mapsto[\begin{array}[]{cc}\xi(\mathbf{x})&\zeta(\mathbf{x})\end{array}].$

Observe that $\vartheta$ is well defined since we are assuming that
$E_{\mathbf{a}}\ast\xi(\mathbf{x})=\mathbf{0}_{d}$ implies
$E_{\mathbf{a}}\ast\zeta(\mathbf{x})=\mathbf{0}_{d^{\prime}}$ for any
$\mathbf{x}\in X^{k}$ and $\mathbf{a}\in A^{k}$. We claim that $\vartheta$
yields a homomorphism from
$\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
to
$\mathbb{F}_{{\mathscr{M}}\ltimes{\mathscr{N}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$.
To this end, take $R\in\sigma$ of arity $r$ and $\mathbf{x}\in
R^{\mathbf{X}}$, so
$\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\in
R^{\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$.
We need to show that
$\vartheta(\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\in
R^{\mathbb{F}_{{\mathscr{M}}\ltimes{\mathscr{N}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$;
equivalently, we need to find some
$W\in({\mathscr{M}}\ltimes{\mathscr{N}})^{(m)}$ such that
$\vartheta(\mathbf{x}_{\mathbf{i}})=W_{/\pi_{\mathbf{i}}}$ for each
$\mathbf{i}\in[r]^{k}$, where $m=|R^{\mathbf{A}}|$. Using that $\xi$ is a
homomorphism, we have that
$\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}⃝}}})}$,
so there exists $Q\in{\mathscr{M}}^{(m)}$ for which
$\xi(\mathbf{x}_{\mathbf{i}})=Q_{/\pi_{\mathbf{i}}}$ for each
$\mathbf{i}\in[r]^{k}$. Similarly, using that $\zeta$ is a homomorphism, we
can find $Z\in{\mathscr{N}}^{(m)}$ for which
$\zeta(\mathbf{x}_{\mathbf{i}})=Z_{/\pi_{\mathbf{i}}}$ for each
$\mathbf{i}\in[r]^{k}$. We now show that
$[\begin{array}[]{cc}Q&Z\end{array}]\in({\mathscr{M}}\ltimes{\mathscr{N}})^{(m)}$.
To this end, take $\mathbf{a}\in R^{\mathbf{A}}$ such that $E_{\mathbf{a}}\ast
Q=\mathbf{0}_{d}$; we need to prove that $E_{\mathbf{a}}\ast
Z=\mathbf{0}_{d^{\prime}}$. Using the assumption that $k\geq r$, let us pick
the tuple $\mathbf{j}=(1,2,\dots,r,1,1,\dots,1)\in[r]^{k}$. Notice that this
choice guarantees that $\\{\mathbf{b}\in
R^{\mathbf{A}}:\mathbf{b}_{\mathbf{j}}=\mathbf{a}_{\mathbf{j}}\\}=\\{\mathbf{a}\\}$.
Hence,

$\displaystyle E_{\mathbf{a}_{\mathbf{j}}}\ast\xi(\mathbf{x}_{\mathbf{j}})$
$\displaystyle=E_{\mathbf{a}_{\mathbf{j}}}\ast
Q_{/\pi_{\mathbf{j}}}=E_{\mathbf{a}_{\mathbf{j}}}\ast P_{\mathbf{j}}\ast
Q=\sum_{\begin{subarray}{c}\mathbf{b}\in R^{\mathbf{A}}\\\
\mathbf{b}_{\mathbf{j}}=\mathbf{a}_{\mathbf{j}}\end{subarray}}E_{\mathbf{b}}\ast
Q=E_{\mathbf{a}}\ast Q,$

where the third equality follows from Lemma 30. Similarly,
$E_{\mathbf{a}_{\mathbf{j}}}\ast\zeta(\mathbf{x}_{\mathbf{j}})=E_{\mathbf{a}}\ast
Z$. Then, from our assumption $E_{\mathbf{a}}\ast Q=\mathbf{0}_{d}$ it follows
that
$E_{\mathbf{a}_{\mathbf{j}}}\ast\xi(\mathbf{x}_{\mathbf{j}})=\mathbf{0}_{d}$.
Using the hypothesis of the proposition, we deduce that
$E_{\mathbf{a}_{\mathbf{j}}}\ast\zeta(\mathbf{x}_{\mathbf{j}})=\mathbf{0}_{d^{\prime}}$,
and we thus conclude that $E_{\mathbf{a}}\ast Z=\mathbf{0}_{d^{\prime}}$, as
wanted. Call $W=[\begin{array}[]{cc}Q&Z\end{array}]$. For each
$\mathbf{i}\in[r]^{k}$, we find

$\displaystyle\vartheta(\mathbf{x}_{\mathbf{i}})=[\begin{array}[]{cc}\xi(\mathbf{x}_{\mathbf{i}})&\zeta(\mathbf{x}_{\mathbf{i}})\end{array}]=[\begin{array}[]{cc}Q_{/\pi_{\mathbf{i}}}&Z_{/\pi_{\mathbf{i}}}\end{array}]=[\begin{array}[]{cc}P_{\mathbf{i}}\overset{\tiny
1}{\ast}Q&P_{\mathbf{i}}\overset{\tiny
1}{\ast}Z\end{array}]=P_{\mathbf{i}}\overset{\tiny
1}{\ast}[\begin{array}[]{cc}Q&Z\end{array}]=W_{/\pi_{\mathbf{i}}},$

as required. This concludes the proof that $\vartheta$ is a homomorphism.

Conversely, let
$\vartheta:\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbb{F}_{{\mathscr{M}}\ltimes{\mathscr{N}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
be a homomorphism. For each $\mathbf{x}\in X^{k}$, write
$\vartheta(\mathbf{x})\in({\mathscr{M}}\ltimes{\mathscr{N}})^{(n^{k})}$ as
$\vartheta(\mathbf{x})=[\begin{array}[]{cc}M_{(\mathbf{x})}&N_{(\mathbf{x})}\end{array}]$,
where $M_{(\mathbf{x})}\in{\mathscr{M}}^{(n^{k})}$ and
$N_{(\mathbf{x})}\in{\mathscr{N}}^{(n^{k})}$. Using the same argument as in
the previous part of the proof, we check that the assignment
$\mathbf{x}\mapsto M_{(\mathbf{x})}$ (resp. $\mathbf{x}\mapsto
N_{(\mathbf{x})}$) yields 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}⃝}}})$
(resp. to
$\mathbb{F}_{{\mathscr{N}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$),
and that the implication $E_{\mathbf{a}}\ast\xi(\mathbf{x})=\mathbf{0}_{d}$
$\;\Rightarrow\;$
$E_{\mathbf{a}}\ast\zeta(\mathbf{x})=\mathbf{0}_{d^{\prime}}$ is met for each
$\mathbf{x}\in X^{k}$ and $\mathbf{a}\in A^{k}$. ∎

######  Remark 45.

In recent work [55], Dalmau and Opršal used the notion of conic minions in the
context of reductions between PCSPs. For a minion ${\mathscr{M}}$, they
construct a new minion $\omega({\mathscr{M}})$ that they use to characterise
the applicability of arc-consistency reductions. If ${\mathscr{M}}$ is linear,
$\omega({\mathscr{M}})$ coincides with the semi-direct product between
$\mathscr{H}$ and ${\mathscr{M}}$ (cf. Remark 42). It is not hard to show that
a linear minion ${\mathscr{M}}$ satisfies
${\mathscr{M}}\to\mathscr{H}\ltimes{\mathscr{M}}$ if and only if it is
homomorphically equivalent to a conic minion. Using this fact, it can be
shown161616Personal communication with Jakub Opršal. that the $k$-consistency
reductions from [55] and the $k$-th level of a hierarchy of minion tests as
defined in this paper are equivalent for conic minions.

##  11 A proof of Theorem 15

In this section, we prove Theorem 15 using the machinery developed in Sections
7, 8, 9, and 10.

######  Theorem (Theorem 15 restated – 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}$

The five parts of the theorem will be formally stated and proved separately,
in Propositions 46, 47, 48, 49, and 50. The statements in Propositions 47 and
49, concerning $\operatorname{SA}^{k}$ and $\operatorname{SoS}^{k}$, are
actually slightly stronger than Theorem 15, as they do not require that the
level $k$ of the hierarchy be at least the maximum arity of the template (cf.
Remark 51).

######  Proposition 46.

Let $k\in\mathbb{N}$ and let $\mathbf{X},\mathbf{A}$ be $k$-enhanced
$\sigma$-structures such that $k\geq\operatorname{armax}(\sigma)$. Then
$\operatorname{BW}^{k}(\mathbf{X},\mathbf{A})=\operatorname{Test}_{\mathscr{H}}^{k}(\mathbf{X},\mathbf{A})$.

###### Proof.

Given two sets $S,T$, an integer $p\in\mathbb{N}$, and two tuples
$\textbf{s}=(s_{1},\dots,s_{p})\in S^{p},\textbf{t}=(t_{1},\dots,t_{p})\in
T^{p}$ such that $\textbf{s}\prec\textbf{t}$, we shall consider the function
$f_{\textbf{s},\textbf{t}}:\\{\textbf{s}\\}\to T$ defined by
$f_{\textbf{s},\textbf{t}}(s_{\alpha})=t_{\alpha}$ for each $\alpha\in[p]$.
Also, we denote by $\epsilon:\emptyset\to\mathbf{A}$ the empty mapping.

Suppose $\operatorname{BW}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ and let
$\mathcal{F}$ be a nonempty collection of partial homomorphisms from
$\mathbf{X}$ to $\mathbf{A}$ witnessing it. Recall from Section 4.1 that the
space of tensors $\mathcal{T}^{n\cdot\mathbf{1}_{k},1}(\\{0,1\\})$ can be
identified with $\mathcal{T}^{n\cdot\mathbf{1}_{k}}(\\{0,1\\})$. Define the
map $\xi:X^{k}\to\mathcal{T}^{n\cdot\mathbf{1}_{k}}(\\{0,1\\})$ by setting,
for $\mathbf{x}\in X^{k}$ and $\mathbf{a}\in A^{k}$,
$E_{\mathbf{a}}\ast\xi(\mathbf{x})=1$ if $\mathbf{x}\prec\mathbf{a}$ and
$f_{\mathbf{x},\mathbf{a}}\in\mathcal{F}$,
$E_{\mathbf{a}}\ast\xi(\mathbf{x})=0$ otherwise. We claim that $\xi$ yields a
homomorphism from
$\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
to
$\mathbb{F}_{\mathscr{H}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$.
Take $R\in\sigma$ of arity $r$ and $\mathbf{y}\in R^{\mathbf{X}}$, so
$\mathbf{y}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\in
R^{\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$.
We need to show that
$\xi(\mathbf{y}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\in
R^{\mathbb{F}_{\mathscr{H}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$.
Since $k\geq r$, we can write $\mathbf{y}=\mathbf{x}_{\mathbf{i}}$ for some
$\mathbf{x}\in X^{k}$, $\mathbf{i}\in[k]^{r}$. Given $\mathbf{a}\in
R^{\mathbf{A}}$, consider the set $B_{\mathbf{a}}=\\{\mathbf{b}\in
A^{k}:\mathbf{b}_{\mathbf{i}}=\mathbf{a}\mbox{ and
}\mathbf{x}\prec\mathbf{b}\\}$. We define a vector
$\mathbf{q}\in\mathcal{T}^{|R^{\mathbf{A}}|}(\\{0,1\\})$ by letting, for each
$\mathbf{a}\in R^{\mathbf{A}}$, the $\mathbf{a}$-th entry of $\mathbf{q}$ be
$1$ if $f_{\mathbf{x},\mathbf{b}}\in\mathcal{F}$ for some $\mathbf{b}\in
B_{\mathbf{a}}$, $0$ otherwise. We now show that
$\mathbf{q}\in\mathscr{H}^{(|R^{\mathbf{A}}|)}$; i.e., that $\mathbf{q}$ is
not identically zero. Observe first that, since $\mathcal{F}$ is nonempty and
closed under restrictions, it contains the empty mapping $\epsilon$. Applying
the extension property to $\epsilon$, we find that there exists some
$f\in\mathcal{F}$ whose domain is $\\{\mathbf{x}\\}$ – that is, there exists
some $\mathbf{c}\in A^{k}$ such that $\mathbf{x}\prec\mathbf{c}$ and
$f_{\mathbf{x},\mathbf{c}}=f\in\mathcal{F}$. Notice that $\mathbf{y}\in
R^{\mathbf{X}}\cap\\{\mathbf{x}\\}^{r}=R^{\mathbf{X}[\\{\mathbf{x}\\}]}$
(where we recall that $\mathbf{X}[\\{\mathbf{x}\\}]$ is the substructure of
$\mathbf{X}$ induced by $\\{\mathbf{x}\\}$). Using that
$f_{\mathbf{x},\mathbf{c}}$ is a partial homomorphism, we obtain
$\mathbf{c}_{\mathbf{i}}=f_{\mathbf{x},\mathbf{c}}(\mathbf{x}_{\mathbf{i}})=f_{\mathbf{x},\mathbf{c}}(\mathbf{y})\in
R^{\mathbf{A}}$. We then conclude that
$\mathbf{e}_{\mathbf{c}_{\mathbf{i}}}\ast\mathbf{q}=1$, so
$\mathbf{q}\in\mathscr{H}^{(|R^{\mathbf{A}}|)}$, as required. If we manage to
show that $\mathbf{q}_{/\pi_{{\bm{\ell}}}}=\xi(\mathbf{y}_{{\bm{\ell}}})$ for
any ${\bm{\ell}}\in[r]^{k}$, we can conclude that
$\xi(\mathbf{y}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\in
R^{\mathbb{F}_{\mathscr{H}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$,
thus proving the claim. Recall from Proposition 17 that $\mathscr{H}$ is a
linear minion on the semiring $(\\{0,1\\},\vee,\wedge)$. For $\mathbf{a}\in
A^{k}$, using Lemma 30, we find

$\displaystyle
E_{\mathbf{a}}\ast\mathbf{q}_{/\pi_{{\bm{\ell}}}}=E_{\mathbf{a}}\ast
P_{{\bm{\ell}}}\ast\mathbf{q}=\sum_{\begin{subarray}{c}\mathbf{c}\in
R^{\mathbf{A}}\\\
\mathbf{c}_{{\bm{\ell}}}=\mathbf{a}\end{subarray}}E_{\mathbf{c}}\ast\mathbf{q}=\bigvee_{\begin{subarray}{c}\mathbf{c}\in
R^{\mathbf{A}}\\\
\mathbf{c}_{{\bm{\ell}}}=\mathbf{a}\end{subarray}}E_{\mathbf{c}}\ast\mathbf{q}.$
(30)

It follows that the expression in (30) equals $1$ if

$\displaystyle\exists\mathbf{c}\in R^{\mathbf{A}}\,\mbox{ s.t.
}\,\mathbf{c}_{{\bm{\ell}}}=\mathbf{a}\,\mbox{ and
}\,f_{\mathbf{x},\mathbf{b}}\in\mathcal{F}\,\mbox{ for some }\,\mathbf{b}\in
B_{\mathbf{c}},$ ($\star$)

$0$ otherwise. On the other hand,
$E_{\mathbf{a}}\ast\xi(\mathbf{y}_{{\bm{\ell}}})$ equals $1$ if

$\displaystyle\mathbf{y}_{{\bm{\ell}}}\prec\mathbf{a}\,\mbox{ and
}\,f_{\mathbf{y}_{{\bm{\ell}}},\mathbf{a}}\in\mathcal{F},$ ($\bullet$)

$0$ otherwise. We now show that the conditions ($\star$ ‣ 11) and ($\bullet$ ‣
11) are equivalent, which concludes the proof of the claim. Suppose that
($\star$ ‣ 11) holds. Since $\mathbf{b}\in B_{\mathbf{c}}$, we have
$\mathbf{x}\prec\mathbf{b}$, which yields
$\mathbf{x}_{\mathbf{i}_{\bm{\ell}}}\prec\mathbf{b}_{\mathbf{i}_{\bm{\ell}}}$
as “$\prec$” is preserved under projections. Using the restriction property
applied to $f_{\mathbf{x},\mathbf{b}}$, we find that
$f_{\mathbf{x}_{\mathbf{i}_{{\bm{\ell}}}},\mathbf{b}_{\mathbf{i}_{{\bm{\ell}}}}}\in\mathcal{F}$.
Then, ($\bullet$ ‣ 11) follows by observing that
$\mathbf{x}_{\mathbf{i}_{\bm{\ell}}}=\mathbf{y}_{\bm{\ell}}$ and, since
$\mathbf{b}\in B_{\mathbf{c}}$ and $\mathbf{c}_{\bm{\ell}}=\mathbf{a}$,
$\mathbf{b}_{\mathbf{i}_{\bm{\ell}}}=\mathbf{a}$. Suppose now that ($\bullet$
‣ 11) holds. Using the extension property applied to
$f_{\mathbf{y}_{{\bm{\ell}}},\mathbf{a}}=f_{\mathbf{x}_{\mathbf{i}_{{\bm{\ell}}}},\mathbf{a}}$
we find that $f_{\mathbf{x},\mathbf{b}}\in\mathcal{F}$ for some $\mathbf{b}\in
A^{k}$ such that $\mathbf{x}\prec\mathbf{b}$ and
$\mathbf{b}_{\mathbf{i}_{{\bm{\ell}}}}=\mathbf{a}$. Since
$f_{\mathbf{x},\mathbf{b}}$ is a partial homomorphism from $\mathbf{X}$ to
$\mathbf{A}$, $R^{\mathbf{A}}\ni
f_{\mathbf{x},\mathbf{b}}(\mathbf{y})=f_{\mathbf{x},\mathbf{b}}(\mathbf{x}_{\mathbf{i}})=\mathbf{b}_{\mathbf{i}}$.
Calling $\mathbf{c}=\mathbf{b}_{\mathbf{i}}$, we obtain ($\star$ ‣ 11).

Conversely, suppose that
$\xi:\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbb{F}_{\mathscr{H}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
is a homomorphism witnessing that
$\operatorname{Test}_{\mathscr{H}}^{k}(\mathbf{X},\mathbf{A})$ accepts, and
consider the collection
$\mathcal{F}=\\{f_{\mathbf{x},\mathbf{a}}:\mathbf{x}\in
X^{k},\mathbf{a}\in\operatorname{supp}(\xi(\mathbf{x}))\\}\cup\\{\epsilon\\}$.
Notice that $\mathcal{F}$ is well defined by virtue of Lemma 32, as
$\mathbf{a}\in\operatorname{supp}(\xi(\mathbf{x}))$ implies that
$\mathbf{x}\prec\mathbf{a}$, and it is nonempty. We claim that any function
$f_{\mathbf{x},\mathbf{a}}\in\mathcal{F}$ is a partial homomorphism from
$\mathbf{X}$ to $\mathbf{A}$. (Notice that $\epsilon$ is trivially a partial
homomorphism.) Indeed, given $R\in\sigma$ of arity $r$ and $\mathbf{y}\in
R^{\mathbf{X}[\\{\mathbf{x}\\}]}=R^{\mathbf{X}}\cap\\{\mathbf{x}\\}^{r}$, we
can write $\mathbf{y}=\mathbf{x}_{\mathbf{i}}$ for some
$\mathbf{i}\in[k]^{r}$. Then,
$f_{\mathbf{x},\mathbf{a}}(\mathbf{y})=f_{\mathbf{x},\mathbf{a}}(\mathbf{x}_{\mathbf{i}})=\mathbf{a}_{\mathbf{i}}\in
R^{\mathbf{A}}$, where we have used Proposition 38 (which applies to
$\mathscr{H}$ since, by Proposition 21, $\mathscr{H}$ is a conic minion). To
show that $\mathcal{F}$ is closed under restrictions, take $f\in\mathcal{F}$
and $V\subseteq\operatorname{dom}(f)$; we need to show that
$f|_{V}\in\mathcal{F}$. The cases $f=\epsilon$ or $V=\emptyset$ are trivial,
so we can assume $f=f_{\mathbf{x},\mathbf{a}}$ (which means that
$\operatorname{dom}(f)=\\{\mathbf{x}\\}$) and write
$V=\\{\mathbf{x}_{\bm{\ell}}\\}$ for some ${\bm{\ell}}\in[k]^{k}$. Observe
that
$f_{\mathbf{x},\mathbf{a}}|_{V}=f_{\mathbf{x}_{\bm{\ell}},\mathbf{a}_{\bm{\ell}}}$.
We claim that $E_{\mathbf{a}_{\bm{\ell}}}\ast\xi(\mathbf{x}_{\bm{\ell}})=1$.
Otherwise, using Proposition 36 and Lemma 34, we would have

$\displaystyle 0$
$\displaystyle=E_{\mathbf{a}_{\bm{\ell}}}\ast\xi(\mathbf{x}_{\bm{\ell}})=E_{\mathbf{a}_{\bm{\ell}}}\ast(\Pi_{\bm{\ell}}\overset{\tiny
k}{\ast}\xi(\mathbf{x}))=E_{\mathbf{a}_{\bm{\ell}}}\ast\Pi_{\bm{\ell}}\ast\xi(\mathbf{x})=\bigvee_{\begin{subarray}{c}\mathbf{b}\in
A^{k}\\\
\mathbf{b}_{\bm{\ell}}=\mathbf{a}_{\bm{\ell}}\end{subarray}}E_{\mathbf{b}}\ast\xi(\mathbf{x}).$

This would imply that $E_{\mathbf{b}}\ast\xi(\mathbf{x})=0$ whenever
$\mathbf{b}\in A^{k}$ is such that
$\mathbf{b}_{\bm{\ell}}=\mathbf{a}_{\bm{\ell}}$; in particular,
$E_{\mathbf{a}}\ast\xi(\mathbf{x})=0$, a contradiction. So
$E_{\mathbf{a}_{\bm{\ell}}}\ast\xi(\mathbf{x}_{\bm{\ell}})=1$, as claimed, and
it follows that
$f_{\mathbf{x}_{\bm{\ell}},\mathbf{a}_{\bm{\ell}}}\in\mathcal{F}$. We now
claim that $\mathcal{F}$ has the extension property up to $k$. Take
$f\in\mathcal{F}$ and $V\subseteq X$ such that $|V|\leq k$ and
$\operatorname{dom}(f)\subseteq V$; we need to show that there exists
$g\in\mathcal{F}$ such that $g$ extends $f$ and $\operatorname{dom}(g)=V$. If
$f=\epsilon$ and $V=\emptyset$, the claim is trivial; if $f=\epsilon$ and
$V\neq\emptyset$, we can write $V=\\{\mathbf{x}\\}$ for some $\mathbf{x}\in
X^{k}$, and the claim follows by noticing that, by the definition of
$\mathscr{H}$, $\operatorname{supp}(\xi(\mathbf{x}))\neq\emptyset$. Therefore,
we can assume that $f\neq\epsilon$, so $f=f_{\mathbf{x},\mathbf{a}}$ for some
$\mathbf{x}\in X^{k}$, $\mathbf{a}\in\operatorname{supp}(\xi(\mathbf{x}))$.
Since $V\neq\emptyset$, we can write $V=\\{\mathbf{y}\\}$ for some
$\mathbf{y}\in X^{k}$. Then, $\operatorname{dom}(f)\subseteq V$ becomes
$\\{\mathbf{x}\\}\subseteq\\{\mathbf{y}\\}$, so
$\mathbf{x}=\mathbf{y}_{\bm{\ell}}$ for some ${\bm{\ell}}\in[k]^{k}$. Using
Proposition 36 and Lemma 34, we find

$\displaystyle
1=E_{\mathbf{a}}\ast\xi(\mathbf{x})=E_{\mathbf{a}}\ast\xi(\mathbf{y}_{\bm{\ell}})=E_{\mathbf{a}}\ast\Pi_{\bm{\ell}}\ast\xi(\mathbf{y})=\bigvee_{\begin{subarray}{c}\mathbf{b}\in
A^{k}\\\
\mathbf{b}_{\bm{\ell}}=\mathbf{a}\end{subarray}}E_{\mathbf{b}}\ast\xi(\mathbf{y}),$

which implies that $E_{\mathbf{b}}\ast\xi(\mathbf{y})=1$ for some
$\mathbf{b}\in A^{k}$ such that $\mathbf{b}_{\bm{\ell}}=\mathbf{a}$. It
follows that $f_{\mathbf{y},\mathbf{b}}\in\mathcal{F}$. Notice that
$\operatorname{dom}(f_{\mathbf{y},\mathbf{b}})=\\{\mathbf{y}\\}=V$, and
$f_{\mathbf{y},\mathbf{b}}|_{\\{\mathbf{x}\\}}=f_{\mathbf{x},\mathbf{a}}$, so
the claim is true. Hence, $\mathcal{F}$ witnesses that
$\operatorname{BW}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$. ∎

######  Proposition 47.

Let $k\in\mathbb{N}$ and let $\mathbf{X},\mathbf{A}$ be $k$-enhanced
$\sigma$-structures such that $k\geq\min(2,\operatorname{armax}(\sigma))$.
Then
$\operatorname{SA}^{k}(\mathbf{X},\mathbf{A})=\operatorname{Test}_{{\mathscr{Q}_{\operatorname{conv}}}}^{k}(\mathbf{X},\mathbf{A})$.

###### Proof.

Suppose $\operatorname{SA}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ and let
the rational numbers $\lambda_{R,\mathbf{x},\mathbf{a}}$ witness it, for
$R\in\sigma$, $\mathbf{x}\in R^{\mathbf{X}}$, and $\mathbf{a}\in
R^{\mathbf{A}}$. Consider the map
$\xi:X^{k}\to\mathcal{T}^{n\cdot\mathbf{1}_{k}}(\mathbb{Q})$ defined by
$E_{\mathbf{a}}\ast\xi(\mathbf{x})=\lambda_{R_{k},\mathbf{x},\mathbf{a}}$ for
any $\mathbf{x}\in X^{k}$, $\mathbf{a}\in A^{k}$. We claim that $\xi$ yields a
homomorphism from
$\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
to
$\mathbb{F}_{{\mathscr{Q}_{\operatorname{conv}}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$.
Notice first that, for any $\mathbf{x}\in X^{k}$, $\xi(\mathbf{x})$ is an
entrywise nonnegative tensor in the space
$\mathcal{T}^{n\cdot\mathbf{1}_{k}}(\mathbb{Q})$ (which can be identified with
$\mathcal{T}^{n\cdot\mathbf{1}_{k},1}(\mathbb{Q})$). Moreover, using
$\clubsuit 1$, we find

$\displaystyle\sum_{\mathbf{a}\in
A^{k}}E_{\mathbf{a}}\ast\xi(\mathbf{x})=\sum_{\mathbf{a}\in
R_{k}^{\mathbf{A}}}\lambda_{R_{k},\mathbf{x},\mathbf{a}}=1.$

It follows that
$\xi(\mathbf{x})\in{\mathscr{Q}_{\operatorname{conv}}}^{(n^{k})}$. We now
prove that $\xi$ yields a homomorphism from
$\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
to
$\mathbb{F}_{{\mathscr{Q}_{\operatorname{conv}}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$.
Take a symbol $R\in\sigma$ of arity $r$ and a tuple $\mathbf{x}\in
R^{\mathbf{X}}$, so that
$\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\in
R^{\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$.
We need to show that
$\xi(\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\in
R^{\mathbb{F}_{{\mathscr{Q}_{\operatorname{conv}}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$.
Equivalently, we seek some vector
$\mathbf{q}\in{\mathscr{Q}_{\operatorname{conv}}}^{(|R^{\mathbf{A}}|)}$ such
that $\xi(\mathbf{x}_{\mathbf{i}})=\mathbf{q}_{/\pi_{\mathbf{i}}}$ for any
$\mathbf{i}\in[r]^{k}$. Consider the vector
$\mathbf{q}\in\mathcal{T}^{|R^{\mathbf{A}}|}(\mathbb{Q})$ defined by
$E_{\mathbf{a}}\ast\mathbf{q}=\lambda_{R,\mathbf{x},\mathbf{a}}$ for any
$\mathbf{a}\in R^{\mathbf{A}}$. Similarly as before, $\clubsuit 1$ implies
that $\mathbf{q}\in{\mathscr{Q}_{\operatorname{conv}}}^{(|R^{\mathbf{A}}|)}$.
For $\mathbf{i}\in[r]^{k}$ and $\mathbf{a}\in A^{k}$, we have

$\displaystyle E_{\mathbf{a}}\ast\xi(\mathbf{x}_{\mathbf{i}})$
$\displaystyle=\lambda_{R_{k},\mathbf{x}_{\mathbf{i}},\mathbf{a}}=\sum_{\begin{subarray}{c}\mathbf{b}\in
R^{\mathbf{A}}\\\
\mathbf{b}_{\mathbf{i}}=\mathbf{a}\end{subarray}}\lambda_{R,\mathbf{x},\mathbf{b}}=\sum_{\begin{subarray}{c}\mathbf{b}\in
R^{\mathbf{A}}\\\
\mathbf{b}_{\mathbf{i}}=\mathbf{a}\end{subarray}}E_{\mathbf{b}}\ast\mathbf{q}=E_{\mathbf{a}}\ast
P_{\mathbf{i}}\ast\mathbf{q}=E_{\mathbf{a}}\ast\mathbf{q}_{/\pi_{\mathbf{i}}},$

where the second equality is $\clubsuit 2$ and the fourth follows from Lemma
30. We deduce that $\xi$ is a homomorphism, as claimed, which means that
$\operatorname{Test}_{{\mathscr{Q}_{\operatorname{conv}}}}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$.

Conversely, suppose that $\xi$ is a homomorphism from
$\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
to
$\mathbb{F}_{{\mathscr{Q}_{\operatorname{conv}}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
witnessing that
$\operatorname{Test}_{{\mathscr{Q}_{\operatorname{conv}}}}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$.
We associate with any pair $(R,\mathbf{x})$ such that $R\in\sigma$ and
$\mathbf{x}\in R^{\mathbf{X}}$ a vector
$\mathbf{q}_{R,\mathbf{x}}\in{\mathscr{Q}_{\operatorname{conv}}}^{(|R^{\mathbf{A}}|)}$
defined as follows. Using that
$\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\in
R^{\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$
and $\xi$ is a homomorphism, we deduce that
$\xi(\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\in
R^{\mathbb{F}_{{\mathscr{Q}_{\operatorname{conv}}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$
– i.e., there exists
$\mathbf{q}\in{\mathscr{Q}_{\operatorname{conv}}}^{(|R^{\mathbf{A}}|)}$ such
that
$\xi(\mathbf{x}_{\mathbf{i}})=\mathbf{q}_{/\pi_{\mathbf{i}}}=P_{\mathbf{i}}\ast\mathbf{q}$
for each $\mathbf{i}\in[r]^{k}$, where $r$ is the arity of $R$. We set
$\mathbf{q}_{R,\mathbf{x}}=\mathbf{q}$. We now build a solution to
$\operatorname{SA}^{k}(\mathbf{X},\mathbf{A})$ as follows: For any
$R\in\sigma$, $\mathbf{x}\in R^{\mathbf{X}}$, and $\mathbf{a}\in
R^{\mathbf{A}}$, we set
$\lambda_{R,\mathbf{x},\mathbf{a}}=E_{\mathbf{a}}\ast\mathbf{q}_{R,\mathbf{x}}$.
Notice that each $\lambda_{R,\mathbf{x},\mathbf{a}}$ is a rational number in
the interval $[0,1]$. Moreover, for $R\in\sigma$ and $\mathbf{x}\in
R^{\mathbf{X}}$, we have

$\displaystyle\sum_{\mathbf{a}\in
R^{\mathbf{A}}}\lambda_{R,\mathbf{x},\mathbf{a}}$
$\displaystyle=\sum_{\mathbf{a}\in
R^{\mathbf{A}}}E_{\mathbf{a}}\ast\mathbf{q}_{R,\mathbf{x}}=1$

since $\mathbf{q}_{R,\mathbf{x}}\in{\mathscr{Q}_{\operatorname{conv}}}$, thus
yielding $\clubsuit 1$. Observe that, for any $\mathbf{y}\in X^{k}$, we have
$\mathbf{q}_{R_{k},\mathbf{y}}=\xi(\mathbf{y})$. Indeed, letting
$\mathbf{j}=(1,\dots,k)\in[k]^{k}$, we have

$\displaystyle\mathbf{q}_{R_{k},\mathbf{y}}$
$\displaystyle=\Pi_{\mathbf{j}}\ast\mathbf{q}_{R_{k},\mathbf{y}}=P_{\mathbf{j}}\ast\mathbf{q}_{R_{k},\mathbf{y}}=\mathbf{q}_{{R_{k},\mathbf{y}}_{/\pi_{\mathbf{j}}}}=\xi(\mathbf{y}_{\mathbf{j}})=\xi(\mathbf{y}),$
(31)

where the first equality follows from the fact that the contraction by
$\Pi_{\mathbf{j}}$ acts as the identity (cf. the proof of Proposition 36) and
the second from Remark 35. Then, $\clubsuit 2$ follows by noticing that, for
$\mathbf{i}\in[r]^{k}$ and $\mathbf{b}\in A^{k}$,

$\displaystyle\sum_{\begin{subarray}{c}\mathbf{a}\in R^{\mathbf{A}}\\\
\mathbf{a}_{\mathbf{i}}=\mathbf{b}\end{subarray}}\lambda_{R,\mathbf{x},\mathbf{a}}=\sum_{\begin{subarray}{c}\mathbf{a}\in
R^{\mathbf{A}}\\\
\mathbf{a}_{\mathbf{i}}=\mathbf{b}\end{subarray}}E_{\mathbf{a}}\ast\mathbf{q}_{R,\mathbf{x}}=E_{\mathbf{b}}\ast
P_{\mathbf{i}}\ast\mathbf{q}_{R,\mathbf{x}}=E_{\mathbf{b}}\ast\xi(\mathbf{x}_{\mathbf{i}})=E_{\mathbf{b}}\ast\mathbf{q}_{R_{k},\mathbf{x}_{\mathbf{i}}}=\lambda_{R_{k},\mathbf{x}_{\mathbf{i}},\mathbf{b}},$

where the second and fourth equalities follow from Lemma 30 and (31),
respectively. Recall from Proposition 21 that
${\mathscr{Q}_{\operatorname{conv}}}$ is a conic minion. Using either Lemma 33
or Lemma 37 (depending on whether $k\geq\operatorname{armax}(\sigma)$ or
$k\geq 2$), if $\mathbf{a}\in R^{\mathbf{A}}$ is such that
$\mathbf{x}\not\prec\mathbf{a}$, we obtain

$\displaystyle\lambda_{R,\mathbf{x},\mathbf{a}}$
$\displaystyle=E_{\mathbf{a}}\ast\mathbf{q}_{R,\mathbf{x}}=0,$

thus showing that $\clubsuit 3$ is satisfied, too. It follows that
$\operatorname{SA}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$, as required. ∎

######  Proposition 48.

Let $k\in\mathbb{N}$ and let $\mathbf{X},\mathbf{A}$ be $k$-enhanced
$\sigma$-structures such that $k\geq\operatorname{armax}(\sigma)$. Then
$\operatorname{AIP}^{k}(\mathbf{X},\mathbf{A})=\operatorname{Test}_{{\mathscr{Z}_{\operatorname{aff}}}}^{k}(\mathbf{X},\mathbf{A})$.

###### Proof.

The proof is analogous to that of Proposition 47, the only difference being
that Lemma 37 cannot be applied in this case since
${\mathscr{Z}_{\operatorname{aff}}}$ is not a conic minion (cf. Proposition
21). As a consequence, unlike in Proposition 47, we need to assume that
$k\geq\operatorname{armax}(\sigma)$. ∎

The proof of Theorem 15 for $\operatorname{SoS}^{k}$, given in Proposition 49
below, follows the same scheme as that of Proposition 47. There is, however,
one additional complication due to the fact that the objects in the minion
${\mathscr{S}}$ are matrices having infinitely many columns and finite, but
arbitrarily large, $\operatorname{csupp}$. We deal with this technical issue
through the orthonormalisation argument we already used for the proof of
Proposition 8: We find an orthonormal basis for the finitely generated vector
space defined as the sum of the row-spaces of the matrices in ${\mathscr{S}}$
appearing as images of a given homomorphism.

######  Proposition 49.

Let $k\in\mathbb{N}$ and let $\mathbf{X},\mathbf{A}$ be $k$-enhanced
$\sigma$-structures such that $k\geq\min(2,\operatorname{armax}(\sigma))$.
Then
$\operatorname{SoS}^{k}(\mathbf{X},\mathbf{A})=\operatorname{Test}_{{\mathscr{S}}}^{k}(\mathbf{X},\mathbf{A})$.

###### Proof.

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

$\displaystyle
E_{\mathbf{a}}\ast\xi(\mathbf{x})=\begin{bmatrix}{\bm{\lambda}}_{R_{k},\mathbf{x},\mathbf{a}}\\\
\mathbf{0}_{\aleph_{0}}\end{bmatrix}\hskip 28.45274pt\mathbf{x}\in
X^{k},\mathbf{a}\in A^{k}.$

We claim that $\xi$ yields a homomorphism from
$\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}$
to
$\mathbb{F}_{{\mathscr{S}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$.
First of all, we need to show that $\xi(\mathbf{x})\in{\mathscr{S}}^{(n^{k})}$
for each $\mathbf{x}\in X^{k}$. The requirement C1 is trivially satisfied
since, by construction, the $j$-th entry of
$E_{\mathbf{a}}\ast\xi(\mathbf{x})$ is zero whenever $j>\omega$. Given
$\mathbf{a},\mathbf{a}^{\prime}\in A^{k}$,

$\displaystyle(E_{\mathbf{a}}\ast\xi(\mathbf{x}))^{T}(E_{\mathbf{a}^{\prime}}\ast\xi(\mathbf{x}))$
$\displaystyle={\bm{\lambda}}_{R_{k},\mathbf{x},\mathbf{a}}\cdot{\bm{\lambda}}_{R_{k},\mathbf{x},\mathbf{a}^{\prime}}.$

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

$\displaystyle\sum_{\mathbf{a}\in
A^{k}}(E_{\mathbf{a}}\ast\xi(\mathbf{x}))^{T}(E_{\mathbf{a}}\ast\xi(\mathbf{x}))$
$\displaystyle=\sum_{\mathbf{a}\in
A^{k}}\|{\bm{\lambda}}_{R_{k},\mathbf{x},\mathbf{a}}\|^{2}=1$

by $\spadesuit 1$, so C3 is also satisfied. Therefore,
$\xi(\mathbf{x})\in{\mathscr{S}}^{(n^{k})}$. To show that $\xi$ is in fact a
homomorphism, take $R\in\sigma$ of arity $r$ and $\mathbf{x}\in
R^{\mathbf{X}}$, so
$\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\in
R^{\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$.
We need to show that
$\xi(\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\in
R^{\mathbb{F}_{{\mathscr{S}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$.
Consider the matrix
$Q\in\mathcal{T}^{|R^{\mathbf{A}}|,{\aleph_{0}}}(\mathbb{R})$ defined by

$\displaystyle
Q^{T}\mathbf{e}_{\mathbf{a}}=\begin{bmatrix}{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}\\\
\mathbf{0}_{\aleph_{0}}\end{bmatrix}\hskip 28.45274pt\mathbf{a}\in
R^{\mathbf{A}}.$

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 $\spadesuit 2$ and C3 from $\spadesuit 1$. Therefore,
$Q\in{\mathscr{S}}^{(|R^{\mathbf{A}}|)}$. We now claim that
$\xi(\mathbf{x}_{\mathbf{i}})=Q_{/\pi_{\mathbf{i}}}$ for each
$\mathbf{i}\in[r]^{k}$. Indeed, observe that, for each $\mathbf{a}\in A^{k}$,

$\displaystyle E_{\mathbf{a}}\ast Q_{/\pi_{\mathbf{i}}}$
$\displaystyle=E_{\mathbf{a}}\ast P_{\mathbf{i}}\ast
Q=\big{(}\sum_{\begin{subarray}{c}\mathbf{b}\in R^{\mathbf{A}}\\\
\mathbf{b}_{\mathbf{i}}=\mathbf{a}\end{subarray}}E_{\mathbf{b}}\big{)}\ast
Q=Q^{T}\big{(}\sum_{\begin{subarray}{c}\mathbf{b}\in R^{\mathbf{A}}\\\
\mathbf{b}_{\mathbf{i}}=\mathbf{a}\end{subarray}}\mathbf{e}_{\mathbf{b}}\big{)}=\sum_{\begin{subarray}{c}\mathbf{b}\in
R^{\mathbf{A}}\\\
\mathbf{b}_{\mathbf{i}}=\mathbf{a}\end{subarray}}Q^{T}\mathbf{e}_{\mathbf{b}}$
$\displaystyle=\begin{bmatrix}\sum_{\begin{subarray}{c}\mathbf{b}\in
R^{\mathbf{A}}\\\
\mathbf{b}_{\mathbf{i}}=\mathbf{a}\end{subarray}}{\bm{\lambda}}_{R,\mathbf{x},\mathbf{b}}\\\
\mathbf{0}_{\aleph_{0}}\end{bmatrix}=\begin{bmatrix}{\bm{\lambda}}_{R_{k},\mathbf{x}_{\mathbf{i}},\mathbf{a}}\\\
\mathbf{0}_{\aleph_{0}}\end{bmatrix}=E_{\mathbf{a}}\ast\xi(\mathbf{x}_{\mathbf{i}}),$

where the second and sixth equalities are obtained using Lemma 30 and
$\spadesuit 3$, respectively. It follows that the claim is true, so
$\xi(\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\in
R^{\mathbb{F}_{{\mathscr{S}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$,
which concludes the proof that $\xi$ is a homomorphism and that
$\operatorname{Test}_{{\mathscr{S}}}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$.

Conversely, let
$\xi:\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbb{F}_{{\mathscr{S}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
be a homomorphism witnessing that
$\operatorname{Test}_{{\mathscr{S}}}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$.
Take $R\in\sigma$ of arity $r$ and $\mathbf{x}\in R^{\mathbf{X}}$. We have
that
$\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\in
R^{\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}}$,
so
$\xi(\mathbf{x}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})\in
R^{\mathbb{F}_{{\mathscr{S}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})}$
since $\xi$ is a homomorphism. As a consequence, we can fix a matrix
$Q_{R,\mathbf{x}}\in{\mathscr{S}}^{(|R^{\mathbf{A}}|)}$ satisfying
$\xi(\mathbf{x}_{\mathbf{i}})={Q_{R,\mathbf{x}}}_{/\pi_{\mathbf{i}}}$ for each
$\mathbf{i}\in[r]^{k}$. Consider the set
$S=\\{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)\subseteq\mathbb{R}^{\aleph_{0}}$, and
observe that
$\dim(\mathcal{U})\leq|S|\leq\sum_{R\in\sigma}|R^{\mathbf{X}}|\cdot|R^{\mathbf{A}}|=\omega$.
Choose 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, we find a projection matrix
${Z}\in\mathbb{R}^{{\aleph_{0}},\omega}$ 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{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}={Z}^{T}Q_{R,\mathbf{x}}^{T}\mathbf{e}_{\mathbf{a}}\in\mathbb{R}^{\omega}\hskip
28.45274ptR\in\sigma,\mathbf{x}\in R^{\mathbf{X}},\mathbf{a}\in
R^{\mathbf{A}}.$ (32)

We claim that (32) witnesses that
$\operatorname{SoS}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$. Take
$R\in\sigma$ of arity $r$ and $\mathbf{x}\in R^{\mathbf{X}}$. Recall from
Proposition 21 that ${\mathscr{S}}$ is a conic minion. Using either Lemma 33
or Lemma 37 (depending on whether $k\geq\operatorname{armax}(\sigma)$ or
$k\geq 2$), given $\mathbf{a}\in R^{\mathbf{A}}$ such that
$\mathbf{x}\not\prec\mathbf{a}$, we find

$\displaystyle{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}$
$\displaystyle={Z}^{T}Q_{R,\mathbf{x}}^{T}\mathbf{e}_{\mathbf{a}}={Z}^{T}\mathbf{0}_{\aleph_{0}}=\mathbf{0}_{\omega},$

so $\spadesuit 4$ holds. $\spadesuit 1$ follows from

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

where the second equality is true since
$Q_{R,\mathbf{x}}^{T}\mathbf{e}_{\mathbf{a}}\in
S\subseteq\mathcal{U}\subseteq\mathcal{V}$ and the fourth follows from C3.
Similarly, using C2, we find that, if $\mathbf{a}\neq\mathbf{a}^{\prime}\in
R^{\mathbf{A}}$,

$\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,$

so $\spadesuit 2$ holds. We now show that
$Q_{R_{k},\mathbf{y}}=\xi(\mathbf{y})$ for any $\mathbf{y}\in X^{k}$. Indeed,
using the same argument as in (31), letting
$\mathbf{j}=(1,\dots,k)\in[k]^{k}$, we have

$\displaystyle Q_{R_{k},\mathbf{y}}$
$\displaystyle=\Pi_{\mathbf{j}}\overset{\tiny
k}{\ast}Q_{R_{k},\mathbf{y}}=Q_{{R_{k},\mathbf{y}}_{/\pi_{\mathbf{j}}}}=\xi(\mathbf{y}_{\mathbf{j}})=\xi(\mathbf{y}).$
(33)

Given $\mathbf{i}\in[r]^{k}$ and $\mathbf{b}\in A^{k}=R_{k}^{\mathbf{A}}$, we
have

$\displaystyle\sum_{\begin{subarray}{c}\mathbf{a}\in R^{\mathbf{A}}\\\
\mathbf{a}_{\mathbf{i}}=\mathbf{b}\end{subarray}}{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}$
$\displaystyle=\sum_{\begin{subarray}{c}\mathbf{a}\in R^{\mathbf{A}}\\\
\mathbf{a}_{\mathbf{i}}=\mathbf{b}\end{subarray}}{Z}^{T}Q_{R,\mathbf{x}}^{T}\mathbf{e}_{\mathbf{a}}=\sum_{\begin{subarray}{c}\mathbf{a}\in
R^{\mathbf{A}}\\\
\mathbf{a}_{\mathbf{i}}=\mathbf{b}\end{subarray}}E_{\mathbf{a}}\ast
Q_{R,\mathbf{x}}\ast{Z}=E_{\mathbf{b}}\ast P_{\mathbf{i}}\ast
Q_{R,\mathbf{x}}\ast{Z}=E_{\mathbf{b}}\ast{Q_{R,\mathbf{x}}}_{/\pi_{\mathbf{i}}}\ast{Z}$
$\displaystyle=E_{\mathbf{b}}\ast\xi(\mathbf{x}_{\mathbf{i}})\ast{Z}=E_{\mathbf{b}}\ast
Q_{R_{k},\mathbf{x}_{\mathbf{i}}}\ast{Z}={Z}^{T}Q_{R_{k},\mathbf{x}_{\mathbf{i}}}^{T}\mathbf{e}_{\mathbf{b}}={\bm{\lambda}}_{R_{k},\mathbf{x}_{\mathbf{i}},\mathbf{b}},$

where the third and sixth equalities follow from Lemma 30 and (33),
respectively. This shows that $\spadesuit 3$ holds, too, so that (32) yields a
solution for $\operatorname{SoS}^{k}(\mathbf{X},\mathbf{A})$, as claimed. ∎

######  Proposition 50.

Let $k\in\mathbb{N}$ and let $\mathbf{X},\mathbf{A}$ be $k$-enhanced
$\sigma$-structures such that $k\geq\operatorname{armax}(\sigma)$. Then
$\operatorname{BA}^{k}(\mathbf{X},\mathbf{A})=\operatorname{Test}_{\mathscr{M}_{\operatorname{BA}}}^{k}(\mathbf{X},\mathbf{A})$.

###### Proof.

Recall from Section 4.2 that
$\operatorname{BA}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ is equivalent to
the existence of a rational nonnegative solution (denoted by the superscript
$(\operatorname{B})$) and an integer solution (denoted by the superscript
$(\operatorname{A})$) to the system (5), such that

$\displaystyle\lambda^{(\operatorname{B})}_{R,\mathbf{x},\mathbf{a}}=0\hskip
9.95863pt\Rightarrow\hskip
14.22636pt\lambda^{(\operatorname{A})}_{R,\mathbf{x},\mathbf{a}}=0$ (34)

for each $R\in\sigma$, $\mathbf{x}\in R^{\mathbf{X}}$, and $\mathbf{a}\in
R^{\mathbf{A}}$. Note that requiring (34) for each $R\in\sigma$ is equivalent
to only requiring it for $R=R_{k}$. Indeed, take some $R\in\sigma$ of arity
$r$, $\mathbf{x}\in R^{\mathbf{X}}$, and $\mathbf{a}\in R^{\mathbf{A}}$, and
consider the tuple $\mathbf{i}=(1,2,\dots,r,1,1,\dots,1)\in[r]^{k}$, which is
well defined as $k\geq r$. Noting that $\\{\mathbf{b}\in
R^{\mathbf{A}}:\mathbf{b}_{\mathbf{i}}=\mathbf{a}_{\mathbf{i}}\\}=\\{\mathbf{a}\\}$,
we find from $\clubsuit 2$ that

$\displaystyle\lambda^{(\operatorname{B})}_{R,\mathbf{x},\mathbf{a}}=\sum_{\begin{subarray}{c}\mathbf{b}\in
R^{\mathbf{A}}\\\
\mathbf{b}_{\mathbf{i}}=\mathbf{a}_{\mathbf{i}}\end{subarray}}\lambda^{(\operatorname{B})}_{R,\mathbf{x},\mathbf{b}}=\lambda^{(\operatorname{B})}_{R_{k},\mathbf{x}_{\mathbf{i}},\mathbf{a}_{\mathbf{i}}}$

and, similarly,
$\lambda^{(\operatorname{A})}_{R,\mathbf{x},\mathbf{a}}=\lambda^{(\operatorname{A})}_{R_{k},\mathbf{x}_{\mathbf{i}},\mathbf{a}_{\mathbf{i}}}$.
As a consequence, if (34) holds for $R_{k}$, it also holds for $R$. Therefore,
it follows from Propositions 47 and 48 that
$\operatorname{BA}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ is equivalent to
the existence of homomorphisms
$\xi:\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbb{F}_{{\mathscr{Q}_{\operatorname{conv}}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
and
$\zeta:\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbb{F}_{{\mathscr{Z}_{\operatorname{aff}}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$
such that
$\operatorname{supp}(\zeta(\mathbf{x}))\subseteq\operatorname{supp}(\xi(\mathbf{x}))$
for each $\mathbf{x}\in X^{k}$. By virtue of Proposition 44, this happens
precisely when
$\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbb{F}_{{{\mathscr{Q}_{\operatorname{conv}}}\ltimes{\mathscr{Z}_{\operatorname{aff}}}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$.
Since
$\mathscr{M}_{\operatorname{BA}}={{\mathscr{Q}_{\operatorname{conv}}}\ltimes{\mathscr{Z}_{\operatorname{aff}}}}$
(cf. Example 43), this is equivalent to
$\mathbf{X}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}}\to\mathbb{F}_{\mathscr{M}_{\operatorname{BA}}}(\mathbf{A}^{\textsuperscript{\raisebox{-0.5pt}{\raisebox{-.1pt}{\tinyk}⃝}}})$;
i.e., to
$\operatorname{Test}_{\mathscr{M}_{\operatorname{BA}}}^{k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$.
∎

######  Remark 51.

The characterisations of $\operatorname{SA}^{k}$ and $\operatorname{SoS}^{k}$
in Propositions 47 and 49 hold for any higher level than the first, unlike the
characterisation of $\operatorname{AIP}^{k}$ in Proposition 48. This is due to
the fact that ${\mathscr{Q}_{\operatorname{conv}}}$ and ${\mathscr{S}}$ are
conic minions, so Lemma 37 applies, while ${\mathscr{Z}_{\operatorname{aff}}}$
is not. As for $\operatorname{BW}^{k}$, Proposition 46 requires
$k\geq\operatorname{armax}(\sigma)$ even if $\mathscr{H}$ is a conic minion.
The reason for this lies in the definition of the bounded width hierarchy.
Essentially, any constraint whose scope has more than $k$ distinct variables
does not appear among the constraints of the partial homomorphisms witnessing
acceptance of $\operatorname{BW}^{k}$, while it does appear in the
requirements of $\operatorname{SA}^{k}$ and $\operatorname{SoS}^{k}$. Finally,
assuming $k\geq\operatorname{armax}(\sigma)$ is also required in the
characterisation of $\operatorname{BA}^{k}$ in Proposition 50, in order to
make use of Proposition 44 and of the characterisation of
$\operatorname{AIP}^{k}$.

######  Remark 52.

As it was shown in Section 9, hierarchies of relaxations built on conic
minions (such as $\operatorname{BW}^{k}$, $\operatorname{SA}^{k}$,
$\operatorname{SoS}^{k}$, and $\operatorname{BA}^{k}$) are “sound in the
limit”, in that their $k$-th level correctly classifies instances $\mathbf{X}$
with $|X|\leq k$ (cf. Proposition 39). This is not the case for the non-conic
hierarchy $\operatorname{AIP}^{k}$, as it was established in the follow-up
work [42]. In [19], a stronger affine hierarchy was proposed, which – contrary
to $\operatorname{AIP}^{k}$ – requires that the variables in the relaxation
should be partial homomorphisms and is thus sound in the limit. By virtue of
Proposition 38, this requirement can be captured by taking the semi-direct
product of any conic minion and ${\mathscr{Z}_{\operatorname{aff}}}$. In
particular, it follows that the hierarchy in [19] is not stronger than the
hierarchy built on the minion
$\mathscr{H}\ltimes{\mathscr{Z}_{\operatorname{aff}}}$ (cf. Remark 42). In
recent work [46], a different algorithm for $\operatorname{(P)CSPs}$ has been
proposed. The relationship of [46] with our work is an interesting direction
for future research.

## Acknowledgements

The authors are grateful to Marcin Kozik, Jakub Opršal, and Caterina Viola for
useful discussions on $\operatorname{SDP}$ relaxations.

##  Appendix A Notes on relaxations and hierarchies

In this appendix, we discuss some basic properties of the relaxations, and
hierarchies thereof, presented in Section 4.2.

###  A.1 $\mbox{SA}^{\mbox{k}}$

The hierarchy defining $\operatorname{SA}^{k}$ given by the system (5)
slightly differs from the one described in [39]. For completeness, we report
below the hierarchy in [39] and we show that it is equivalent to the one
adopted in this work.

Given two $\sigma$-structures $\mathbf{X},\mathbf{A}$, introduce a variable
$\mu_{V}(f)$ for every subset $V\subseteq X$ with $1\leq|V|\leq k$ and every
function $f:V\to A$, and a variable $\mu_{R,\mathbf{x}}(f)$ for every
$R\in\sigma$, every $\mathbf{x}\in R^{\mathbf{X}}$, and every
$f:\\{\mathbf{x}\\}\to A$. The $k$-th level of the hierarchy defined in [39]
is given by the following constraints:

$\displaystyle\begin{array}[]{lll}\mbox{($\varheart
1$)}&\displaystyle\sum_{f:V\to A}\mu_{V}(f)=1&V\subseteq X\mbox{ such that
}1\leq|V|\leq k\\\ \mbox{($\varheart 2$)}&\displaystyle\mu_{U}(f)=\sum_{g:V\to
A,\;g|_{U}=f}\mu_{V}(g)&U\subseteq V\subseteq X\mbox{ such that }1\leq|V|\leq
k,U\neq\emptyset,f:U\to A\\\ \mbox{($\varheart
3$)}&\displaystyle\mu_{U}(f)=\sum_{g:\\{\mathbf{x}\\}\to
A,\;g|_{U}=f}\mu_{R,\mathbf{x}}(g)&R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},U\subseteq\\{\mathbf{x}\\}\mbox{ such that }1\leq|U|\leq
k,f:U\to A\\\ \mbox{($\varheart
4$)}&\displaystyle\mu_{R,\mathbf{x}}(f)=0&R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},f:\\{\mathbf{x}\\}\to A\mbox{ such that }f(\mathbf{x})\not\in
R^{\mathbf{A}}.\end{array}$ (39)

######  Lemma 53.

Let $k\in\mathbb{N}$, let $\mathbf{X},\mathbf{A}$ be two $\sigma$-structures,
and let $\tilde{\mathbf{X}}$ (resp. $\tilde{\mathbf{A}}$) be the structure
obtained from $\mathbf{X}$ (resp. $\mathbf{A}$) by adding the relation
$R_{k}^{\tilde{\mathbf{X}}}=X^{k}$ (resp. $R_{k}^{\tilde{\mathbf{A}}}=A^{k}$).
Then the system (39) applied to $\mathbf{X}$ and $\mathbf{A}$ is equivalent to
the system (5) applied to $\tilde{\mathbf{X}}$ and $\tilde{\mathbf{A}}$.

###### Proof.

Let $\lambda$ be a solution to (5) applied to $\tilde{\mathbf{X}}$ and
$\tilde{\mathbf{A}}$. Given $V\subseteq X$ with $1\leq|V|\leq k$ and $f:V\to
A$, let $\mathbf{x}\in X^{k}$ be such that $V=\\{\mathbf{x}\\}$ and set
$\mu_{V}(f)=\lambda_{R_{k},\mathbf{x},f(\mathbf{x})}$. We claim that this
assignment does not depend on the choice of $\mathbf{x}$; i.e., we claim that
$\lambda_{R_{k},\mathbf{x},f(\mathbf{x})}=\lambda_{R_{k},\mathbf{y},f(\mathbf{y})}$
whenever $\mathbf{x},\mathbf{y}\in X^{k}$ are such that
$\\{\mathbf{x}\\}=\\{\mathbf{y}\\}$. The latter condition implies that
$\mathbf{x}=\mathbf{y}_{\mathbf{i}}$ and $\mathbf{y}=\mathbf{x}_{\mathbf{j}}$
for some $\mathbf{i},\mathbf{j}\in[k]^{k}$. Using $\clubsuit 2$ and $\clubsuit
3$, we find

$\displaystyle\lambda_{R_{k},\mathbf{y},f(\mathbf{y})}$
$\displaystyle=\lambda_{R_{k},\mathbf{x}_{\mathbf{j}},f(\mathbf{x}_{\mathbf{j}})}=\sum_{\begin{subarray}{c}\mathbf{a}\in
A^{k}\\\
\mathbf{a}_{\mathbf{j}}=f(\mathbf{x}_{\mathbf{j}})\end{subarray}}\lambda_{R_{k},\mathbf{x},\mathbf{a}}=\sum_{\begin{subarray}{c}\mathbf{a}\in
A^{k}\\\ \mathbf{a}_{\mathbf{j}}=f(\mathbf{x}_{\mathbf{j}})\\\
\mathbf{x}\prec\mathbf{a}\end{subarray}}\lambda_{R_{k},\mathbf{x},\mathbf{a}}=\lambda_{R_{k},\mathbf{x},f(\mathbf{x})}+\sum_{\begin{subarray}{c}\mathbf{a}\in
A^{k}\\\ \mathbf{a}_{\mathbf{j}}=f(\mathbf{x}_{\mathbf{j}})\\\
\mathbf{x}\prec\mathbf{a}\\\ \mathbf{a}\neq
f(\mathbf{x})\end{subarray}}\lambda_{R_{k},\mathbf{x},\mathbf{a}}.$

The claim then follows if we show that there is no $\mathbf{a}\in A^{k}$ such
that $\mathbf{a}_{\mathbf{j}}=f(\mathbf{x}_{\mathbf{j}})$,
$\mathbf{x}\prec\mathbf{a}$, and $\mathbf{a}\neq f(\mathbf{x})$. If such
$\mathbf{a}$ exists, using that
$\mathbf{x}=\mathbf{x}_{\mathbf{j}_{\mathbf{i}}}$, we find that for some
$p\in[k]$

$\displaystyle a_{p}$ $\displaystyle\neq
f(x_{p})=f(x_{j_{i_{p}}})=a_{j_{i_{p}}}.$

Since $\mathbf{x}\prec\mathbf{a}$, this implies that $x_{p}\neq
x_{j_{i_{p}}}$, a contradiction. Therefore, the claim is true. Additionally,
given $R\in\sigma$, $\mathbf{x}\in R^{\mathbf{X}}$, and $f:\\{\mathbf{x}\\}\to
A$, we set $\mu_{R,\mathbf{x}}(f)=\lambda_{R,\mathbf{x},f(\mathbf{x})}$ if
$f(\mathbf{x})\in R^{\mathbf{A}}$, $\mu_{R,\mathbf{x}}(f)=0$ otherwise. It is
straightforward to check that $\mu$ satisfies all constraints in the system
(39) applied to $\mathbf{X}$ and $\mathbf{A}$.

Conversely, let $\mu$ be a solution to (39) applied to $\mathbf{X}$ and
$\mathbf{A}$. As in the proof of Proposition 46, given two sets $S,T$, an
integer $p\in\mathbb{N}$, and two tuples $\textbf{s}\in S^{p},\textbf{t}\in
T^{p}$ such that $\textbf{s}\prec\textbf{t}$, we define the map
$f_{\textbf{s},\textbf{t}}:\\{\textbf{s}\\}\to T$ by
$f_{\textbf{s},\textbf{t}}(s_{\alpha})=t_{\alpha}$ for each $\alpha\in[p]$.
For every $R\in\sigma$, $\mathbf{x}\in R^{\mathbf{X}}$, and $\mathbf{a}\in
R^{\mathbf{A}}$, we set
$\lambda_{R,\mathbf{x},\mathbf{a}}=\mu_{R,\mathbf{x}}(f_{\mathbf{x},\mathbf{a}})$
if $\mathbf{x}\prec\mathbf{a}$, $\lambda_{R,\mathbf{x},\mathbf{a}}=0$
otherwise. Additionally, for every $\mathbf{x}\in
X^{k}=R_{k}^{\tilde{\mathbf{X}}}$ and $\mathbf{a}\in
A^{k}=R_{k}^{\tilde{\mathbf{A}}}$, we set
$\lambda_{R_{k},\mathbf{x},\mathbf{a}}=\mu_{\\{\mathbf{x}\\}}(f_{\mathbf{x},\mathbf{a}})$
if $\mathbf{x}\prec\mathbf{a}$, $\lambda_{R_{k},\mathbf{x},\mathbf{a}}=0$
otherwise. It is easily verified that $\lambda$ yields a solution to (5)
applied to $\tilde{\mathbf{X}}$ and $\tilde{\mathbf{A}}$. ∎

We also note that [5] has yet another definition of the Sherali-Adams
hierarchy. However, it was shown in [39, Appendix A] that the hierarchy given
in [5] interleaves with the one in [39] and, by virtue of Lemma 53, with the
hierarchy used in this work. In particular, the class of
$\operatorname{PCSP}$s solved by constant levels of the hierarchy is the same
for all definitions.

###  A.2 SDP

######  Remark 54.

The relaxation defined by (10) is not in semidefinite programming form,
because of the constraint $\vardiamond 4$. However, it can be easily
translated into a semidefinite program by introducing $\omega$ additional
variables ${\bm{\mu}}_{1},\dots,{\bm{\mu}}_{\omega}$ taking values in
$\mathbb{R}^{\omega}$, and requiring that the following constraints are met:

$\displaystyle\begin{array}[]{llllll}\mbox{($\vardiamond
4^{\prime}$)}&\displaystyle{\bm{\mu}}_{p}\cdot{\bm{\mu}}_{q}=\delta_{p,q}&p,q\in[\omega]\\\
\mbox{($\vardiamond
4^{\prime\prime}$)}&\displaystyle\sum_{\begin{subarray}{c}\mathbf{a}\in
R^{\mathbf{A}}\\\
a_{i}=a\end{subarray}}{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}\cdot{\bm{\mu}}_{p}={\bm{\lambda}}_{x_{i},a}\cdot{\bm{\mu}}_{p}&R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},a\in A,i\in[\operatorname{ar}(R)],p\in[\omega]\end{array}$

where $\delta_{p,q}$ is the Kronecker delta. One easily checks that the
requirements $\vardiamond 4^{\prime}$ and $\vardiamond 4^{\prime\prime}$ are
together equivalent to the requirement $\vardiamond 4$, and they are expressed
in semidefinite programming form.

######  Proposition 55.

Let $\mathbf{X},\mathbf{A}$ be two $\sigma$-structures. The system (10)
implies the following facts:

$\displaystyle\begin{array}[]{lllllll}(i)&\displaystyle\|\sum_{a\in
A}{\bm{\lambda}}_{x,a}\|^{2}=1&x\in X;\\\
(ii)&\displaystyle\sum_{\mathbf{a}\in
R^{\mathbf{A}}}\|{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}\|^{2}=\|\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}};\\\ (iii)&\displaystyle\sum_{\begin{subarray}{c}\mathbf{a}\in
R^{\mathbf{A}}\\\
a_{i}=a,\;a_{j}=a^{\prime}\end{subarray}}\|{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}\|^{2}={\bm{\lambda}}_{x_{i},a}\cdot{\bm{\lambda}}_{x_{j},a^{\prime}}&R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},a,a^{\prime}\in
A,i,j\in[\operatorname{ar}(R)].\@@ams@intertext{If, in addition, $\mathbf{X}$
and $\mathbf{A}$ are $2$-enhanced,}\cr(iv)&\displaystyle\sum_{a\in
A}{\bm{\lambda}}_{x,a}=\sum_{a\in
A}{\bm{\lambda}}_{x^{\prime},a}&x,x^{\prime}\in X.\end{array}$

###### Proof.

  * $(i)$

We have

$\displaystyle\|\sum_{a\in A}{\bm{\lambda}}_{x,a}\|^{2}$
$\displaystyle=\left(\sum_{a\in
A}{\bm{\lambda}}_{x,a}\right)\cdot\left(\sum_{a^{\prime}\in
A}{\bm{\lambda}}_{x,a^{\prime}}\right)=\sum_{a,a^{\prime}\in
A}{\bm{\lambda}}_{x,a}\cdot{\bm{\lambda}}_{x,a^{\prime}}=\sum_{a\in
A}\|{\bm{\lambda}}_{x,a}\|^{2}=1,$

where the third equality comes from $\vardiamond 2$ and the fourth from
$\vardiamond 1$.

  * $(ii)$

We have

$\displaystyle\sum_{\mathbf{a}\in
R^{\mathbf{A}}}\|\lambda_{R,\mathbf{x},\mathbf{a}}\|^{2}$
$\displaystyle=\sum_{\mathbf{a},\mathbf{a}^{\prime}\in
R^{\mathbf{A}}}\lambda_{R,\mathbf{x},\mathbf{a}}\cdot\lambda_{R,\mathbf{x},\mathbf{a}^{\prime}}=\left(\sum_{\mathbf{a}\in
R^{\mathbf{A}}}{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}\right)\cdot\left(\sum_{\mathbf{a}^{\prime}\in
R^{\mathbf{A}}}{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}^{\prime}}\right)=\|\sum_{\mathbf{a}\in
R^{\mathbf{A}}}{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}\|^{2}$
$\displaystyle=\|\sum_{a\in A}\sum_{\begin{subarray}{c}\mathbf{a}\in
R^{\mathbf{A}}\\\
a_{1}=a\end{subarray}}{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}\|^{2}=\|\sum_{a\in
A}{\bm{\lambda}}_{x_{1},a}\|^{2}=1,$

where the first equality comes from $\vardiamond 3$, the fifth from
$\vardiamond 4$, and the sixth from part $(i)$ of this proposition.

  * $(iii)$

We have

${\bm{\lambda}}_{x_{i},a}\cdot{\bm{\lambda}}_{x_{j},a^{\prime}}=\left(\sum_{\begin{subarray}{c}\mathbf{a}\in
R^{\mathbf{A}}\\\
a_{i}=a\end{subarray}}{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}\right)\cdot\left(\sum_{\begin{subarray}{c}\mathbf{a}^{\prime}\in
R^{\mathbf{A}}\\\
a^{\prime}_{j}=a^{\prime}\end{subarray}}{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}^{\prime}}\right)=\sum_{\begin{subarray}{c}\mathbf{a},\mathbf{a}^{\prime}\in
R^{\mathbf{A}}\\\
a_{i}=a,\;a^{\prime}_{j}=a^{\prime}\end{subarray}}{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}\cdot{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}^{\prime}}\\\
=\sum_{\begin{subarray}{c}\mathbf{a}\in R^{\mathbf{A}}\\\
a_{i}=a,\;a_{j}=a^{\prime}\end{subarray}}\|{\bm{\lambda}}_{R,\mathbf{x},\mathbf{a}}\|^{2},$

where the first equality comes from $\vardiamond 4$ and the third from
$\vardiamond 3$.

  * $(iv)$

If $\mathbf{X}$ and $\mathbf{A}$ are $2$-enhanced, we have

$\displaystyle\sum_{a\in A}{\bm{\lambda}}_{x,a}$ $\displaystyle=\sum_{a\in
A}\sum_{\begin{subarray}{c}\mathbf{a}\in R_{2}^{\mathbf{A}}\\\
a_{1}=a\end{subarray}}{\bm{\lambda}}_{R_{2},(x,x^{\prime}),\mathbf{a}}=\sum_{\mathbf{a}\in
R_{2}^{\mathbf{A}}}{\bm{\lambda}}_{R_{2},(x,x^{\prime}),\mathbf{a}}=\sum_{a\in
A}\sum_{\begin{subarray}{c}\mathbf{a}\in R_{2}^{\mathbf{A}}\\\
a_{2}=a\end{subarray}}{\bm{\lambda}}_{R_{2},(x,x^{\prime}),\mathbf{a}}=\sum_{a\in
A}{\bm{\lambda}}_{x^{\prime},a},$

where the first and fourth equalities come from $\vardiamond 4$.

∎

We point out that slightly different versions of the “standard
$\operatorname{SDP}$ relaxation” appeared in the literature on
$\operatorname{CSP}$s, some of which use parts $(i)$ through $(iii)$ of
Proposition 55 as constraints defining the relaxation. In particular, certain
versions require that the scalar products
${\bm{\lambda}}_{x,a}\cdot{\bm{\lambda}}_{y,b}$ should be nonnegative for all
choices of $x,y\in X$ and $a,b\in A$. For example, this is the case of the
$\operatorname{SDP}$ relaxation used in [14]. It follows from Proposition 57,
proved in Appendix A.3, that one can enforce nonnegativity of the scalar
products by taking the second level of the $\operatorname{SoS}$ hierarchy of
the $\operatorname{SDP}$ relaxation as defined in this work.

###  A.3 $\mbox{SoS}^{\mbox{k}}$

######  Remark 56.

The relaxation defined by (15) can be easily translated into a semidefinite
program through the procedure described in Remark 54.

######  Proposition 57.

Let $k\in\mathbb{N}$, let $\mathbf{X},\mathbf{A}$ be $2k$-enhanced
$\sigma$-structures, suppose that
$\operatorname{SoS}^{2k}(\mathbf{X},\mathbf{A})=\textsc{Yes}$, and let
${\bm{\lambda}}$ denote a solution. Then ${\bm{\lambda}}$ satisfies the
following additional constraints:

$\begin{array}[]{lllll}\mbox{(i)}&\displaystyle{\bm{\lambda}}_{R_{2k},(\mathbf{x},\mathbf{x}),(\mathbf{a},\mathbf{a})}\cdot{\bm{\lambda}}_{R_{2k},(\mathbf{y},\mathbf{y}),(\mathbf{b},\mathbf{b})}\geq
0&&\begin{array}[]{lll}\mathbf{x},\mathbf{y}\in X^{k},\mathbf{a},\mathbf{b}\in
A^{k}\end{array}\\\\[15.0pt]
\mbox{(ii)}&\displaystyle{\bm{\lambda}}_{R_{2k},(\mathbf{x},\mathbf{x}),(\mathbf{a},\mathbf{a})}\cdot{\bm{\lambda}}_{R_{2k},(\mathbf{y},\mathbf{y}),(\mathbf{b},\mathbf{b})}=0&&\begin{array}[]{ll}\mathbf{x},\mathbf{y}\in
X^{k},\mathbf{a},\mathbf{b}\in A^{k},\\\
\mathbf{a}_{\mathbf{i}}\neq\mathbf{b}_{\mathbf{j}}\mbox{ for some
}\mathbf{i},\mathbf{j}\in[k]^{k}\mbox{ such that
}\mathbf{x}_{\mathbf{i}}=\mathbf{y}_{\mathbf{j}}\end{array}\\\\[15.0pt]
\mbox{(iii)}&\displaystyle\begin{array}[]{llll}{\bm{\lambda}}_{R_{2k},(\mathbf{x},\mathbf{x}),(\mathbf{a},\mathbf{a})}\cdot{\bm{\lambda}}_{R_{2k},(\mathbf{y},\mathbf{y}),(\mathbf{b},\mathbf{b})}=\\\
{\bm{\lambda}}_{R_{2k},(\hat{\mathbf{x}},\hat{\mathbf{x}}),(\hat{\mathbf{a}},\hat{\mathbf{a}})}\cdot{\bm{\lambda}}_{R_{2k},(\hat{\mathbf{y}},\hat{\mathbf{y}}),(\hat{\mathbf{b}},\hat{\mathbf{b}})}\end{array}&&\begin{array}[]{lll}\mathbf{x},\hat{\mathbf{x}},\mathbf{y},\hat{\mathbf{y}}\in
X^{k},\mathbf{a},\hat{\mathbf{a}},\mathbf{b},\hat{\mathbf{b}}\in A^{k},\\\
(\hat{\mathbf{x}},\hat{\mathbf{y}})_{{\bm{\ell}}}=(\mathbf{x},\mathbf{y}),(\hat{\mathbf{a}},\hat{\mathbf{b}})_{{\bm{\ell}}}=(\mathbf{a},\mathbf{b})\\\
\mbox{for some }{\bm{\ell}}\in[2k]^{2k}\mbox{ such that
}|\\{{\bm{\ell}}\\}|=2k.\end{array}\end{array}$

###### Proof.

Observe that, for $\mathbf{x},\mathbf{y}\in X^{k}$ and
$\mathbf{a},\mathbf{b}\in A^{k}$,

$\displaystyle{\bm{\lambda}}_{R_{2k},(\mathbf{x},\mathbf{x}),(\mathbf{a},\mathbf{a})}\cdot{\bm{\lambda}}_{R_{2k},(\mathbf{y},\mathbf{y}),(\mathbf{b},\mathbf{b})}$
$\displaystyle=\left(\sum_{\begin{subarray}{c}\mathbf{c}\in
A^{k}\end{subarray}}{\bm{\lambda}}_{R_{2k},(\mathbf{x},\mathbf{y}),(\mathbf{a},\mathbf{c})}\right)\cdot\left(\sum_{\begin{subarray}{c}\mathbf{c}^{\prime}\in
A^{k}\end{subarray}}{\bm{\lambda}}_{R_{2k},(\mathbf{x},\mathbf{y}),(\mathbf{c}^{\prime},\mathbf{b})}\right)$
$\displaystyle=\sum_{\mathbf{c},\mathbf{c}^{\prime}\in
A^{k}}{\bm{\lambda}}_{R_{2k},(\mathbf{x},\mathbf{y}),(\mathbf{a},\mathbf{c})}\cdot{\bm{\lambda}}_{R_{2k},(\mathbf{x},\mathbf{y}),(\mathbf{c}^{\prime},\mathbf{b})}$
$\displaystyle=\|{\bm{\lambda}}_{R_{2k},(\mathbf{x},\mathbf{y}),(\mathbf{a},\mathbf{b})}\|^{2},$
(40)

where the first and third equalities come from $\spadesuit 3$ and $\spadesuit
2$, respectively. Hence, $(i)$ holds. If, in addition,
$\mathbf{a}_{\mathbf{i}}\neq\mathbf{b}_{\mathbf{j}}$ for some
$\mathbf{i},\mathbf{j}\in[k]^{k}$ such that
$\mathbf{x}_{\mathbf{i}}=\mathbf{y}_{\mathbf{j}}$, we deduce that
$(\mathbf{x}_{\mathbf{i}},\mathbf{y}_{\mathbf{j}})\not\prec(\mathbf{a}_{\mathbf{i}},\mathbf{b}_{\mathbf{j}})$
and, therefore,

$\displaystyle 0$
$\displaystyle=\|{\bm{\lambda}}_{R_{2k},(\mathbf{x}_{\mathbf{i}},\mathbf{y}_{\mathbf{j}}),(\mathbf{a}_{\mathbf{i}},\mathbf{b}_{\mathbf{j}})}\|^{2}=\|\sum_{\begin{subarray}{c}(\mathbf{c},\mathbf{d})\in
A^{2k}\\\
\mathbf{c}_{\mathbf{i}}=\mathbf{a}_{\mathbf{i}},\mathbf{d}_{\mathbf{j}}=\mathbf{b}_{\mathbf{j}}\end{subarray}}{\bm{\lambda}}_{R_{2k},(\mathbf{x},\mathbf{y}),(\mathbf{c},\mathbf{d})}\|^{2}$
$\displaystyle=\sum_{\begin{subarray}{c}(\mathbf{c},\mathbf{d})\in A^{2k}\\\
\mathbf{c}_{\mathbf{i}}=\mathbf{a}_{\mathbf{i}},\mathbf{d}_{\mathbf{j}}=\mathbf{b}_{\mathbf{j}}\end{subarray}}\|{\bm{\lambda}}_{R_{2k},(\mathbf{x},\mathbf{y}),(\mathbf{c},\mathbf{d})}\|^{2}\geq\|{\bm{\lambda}}_{R_{2k},(\mathbf{x},\mathbf{y}),(\mathbf{a},\mathbf{b})}\|^{2},$
(41)

where the first, second, and third equalities come from $\spadesuit 4$,
$\spadesuit 3$, and $\spadesuit 2$, respectively. Combining (A.3) and (A.3),
we obtain $(ii)$. Suppose now that
$\mathbf{x},\hat{\mathbf{x}},\mathbf{y},\hat{\mathbf{y}}\in X^{k}$ and
$\mathbf{a},\hat{\mathbf{a}},\mathbf{b},\hat{\mathbf{b}}\in A^{k}$ are such
that
$(\hat{\mathbf{x}},\hat{\mathbf{y}})_{{\bm{\ell}}}=(\mathbf{x},\mathbf{y})$
and
$(\hat{\mathbf{a}},\hat{\mathbf{b}})_{{\bm{\ell}}}=(\mathbf{a},\mathbf{b})$
for some ${\bm{\ell}}\in[2k]^{2k}$ such that $|\\{{\bm{\ell}}\\}|=2k$. Using
$\spadesuit 3$, we find

$\displaystyle{\bm{\lambda}}_{R_{2k},(\mathbf{x},\mathbf{y}),(\mathbf{a},\mathbf{b})}$
$\displaystyle={\bm{\lambda}}_{R_{2k},(\hat{\mathbf{x}},\hat{\mathbf{y}})_{{\bm{\ell}}},(\hat{\mathbf{a}},\hat{\mathbf{b}})_{{\bm{\ell}}}}=\sum_{\begin{subarray}{c}(\mathbf{c},\mathbf{d})\in
A^{2k}\\\
(\mathbf{c},\mathbf{d})_{{\bm{\ell}}}=(\hat{\mathbf{a}},\hat{\mathbf{b}})_{{\bm{\ell}}}\end{subarray}}{\bm{\lambda}}_{R_{2k},(\hat{\mathbf{x}},\hat{\mathbf{y}}),(\mathbf{c},\mathbf{d})}={\bm{\lambda}}_{R_{2k},(\hat{\mathbf{x}},\hat{\mathbf{y}}),(\hat{\mathbf{a}},\hat{\mathbf{b}})},$

where the last equality is due to the fact that $|\\{{\bm{\ell}}\\}|=2k$.
Hence, $(iii)$ follows from (A.3). ∎

We observe that the relaxation in (15) is formally different from the one
described in [96]. However, it can be shown that the $2k$-th level of the
hierarchy as defined here is at least as tight as the $k$-th level of the
hierarchy as defined in [96]. Let us denote the two relaxations by
$\operatorname{SoS}$ and $\operatorname{SoS}^{\prime}$, respectively. First of
all, each variable in $\operatorname{SoS}^{\prime}$ corresponds to a subset
$S$ of $\mathbf{X}$ and an assignment $f:S\to A$, while in
$\operatorname{SoS}$ the variables correspond to pairs of tuples
$\mathbf{x}\in R^{\mathbf{X}},\mathbf{a}\in R^{\mathbf{A}}$. This is an
inessential difference, as one can check through the same argument used to
prove Lemma 53 – in particular, $\spadesuit 4$ ensures that the only variables
having nonzero weight are those corresponding to well-defined assignments (cf.
Footnote 14). The $k$-th level of $\operatorname{SoS}^{\prime}$ contains
constraints that, in our language, are expressed as $\spadesuit 4$,
$\spadesuit 1$, and parts $(i),(ii),(iii)$ of Proposition 57. By virtue of
Proposition 57, therefore, any solution ${\bm{\lambda}}$ to the $2k$-th level
of $\operatorname{SoS}$ yields a solution to the $k$-th level of
$\operatorname{SoS}^{\prime}$ – which means that the $2k$-th level of
$\operatorname{SoS}$ is at least as tight as the $k$-th level of
$\operatorname{SoS}^{\prime}$.

## References

  * [1] Sanjeev Arora, Satish Rao, and Umesh V. Vazirani.  Expander flows, geometric embeddings and graph partitioning.  Journal of the ACM, 56(2), 2009.  doi:10.1145/1502793.1502794.
  * [2] Kristina Asimi and Libor Barto.  Finitely tractable promise constraint satisfaction problems.  In Proc. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS’21), volume 202 of LIPIcs, pages 11:1–11:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.  arXiv:2010.04618, doi:10.4230/LIPIcs.MFCS.2021.11.
  * [3] Albert Atserias, Andrei A. Bulatov, and Víctor Dalmau.  On the Power of _k_ -Consistency.  In Proc. 34th International Colloquium on Automata, Languages and Programming (ICALP’07), volume 4596 of Lecture Notes in Computer Science, pages 279–290. Springer, 2007.  doi:10.1007/978-3-540-73420-8\\_26.
  * [4] Albert Atserias and Víctor Dalmau.  A combinatorial characterization of resolution width.  J. Comput. Syst. Sci., 74(3):323–334, 2008.  doi:10.1016/j.jcss.2007.06.025.
  * [5] Albert Atserias and Víctor Dalmau.  Promise Constraint Satisfaction and Width.  In Proc. 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA’22), pages 1129–1153, 2022.  arXiv:2107.05886, doi:10.1137/1.9781611977073.48.
  * [6] Albert Atserias and Elitza N. Maneva.  Sherali-Adams Relaxations and Indistinguishability in Counting Logics.  SIAM J. Comput., 42(1):112–137, 2013.  doi:10.1137/120867834.
  * [7] Per Austrin.  Towards Sharp Inapproximability for Any 2-CSP.  SIAM J. Comput., 39(6):2430–2463, 2010.  doi:10.1137/070711670.
  * [8] Per Austrin, Amey Bhangale, and Aditya Potukuchi.  Improved inapproximability of rainbow coloring.  In Proc. 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA’20), pages 1479–1495, 2020.  arXiv:1810.02784, doi:10.1137/1.9781611975994.90.
  * [9] Per Austrin, Venkatesan Guruswami, and Johan Håstad.  (2+$\epsilon$)-Sat is NP-hard.  SIAM J. Comput., 46(5):1554–1573, 2017.  doi:10.1137/15M1006507.
  * [10] Libor Barto.  The collapse of the bounded width hierarchy.  J. Log. Comput., 26(3):923–943, 2016.  doi:10.1093/logcom/exu070.
  * [11] Libor Barto, Diego Battistelli, and Kevin M. Berg.  Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case.  In Proc. 38th International Symposium on Theoretical Aspects of Computer Science (STACS’21), volume 187 of LIPIcs, pages 10:1–10:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.  arXiv:2010.04623, doi:10.4230/LIPIcs.STACS.2021.10.
  * [12] Libor Barto, Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal.  Algebraic approach to promise constraint satisfaction.  J. ACM, 68(4):28:1–28:66, 2021.  arXiv:1811.00970, doi:10.1145/3457606.
  * [13] Libor Barto and Marcin Kozik.  Constraint Satisfaction Problems Solvable by Local Consistency Methods.  J. ACM, 61(1), 2014.  Article No. 3.  doi:10.1145/2556646.
  * [14] Libor Barto and Marcin Kozik.  Robustly solvable constraint satisfaction problems.  SIAM J. Comput., 45(4):1646–1669, 2016.  arXiv:1512.01157, doi:10.1137/130915479.
  * [15] Libor Barto and Marcin Kozik.  Combinatorial Gap Theorem and Reductions between Promise CSPs.  In Proc. 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA’22), pages 1204–1220, 2022.  arXiv:2107.09423, doi:10.1137/1.9781611977073.50.
  * [16] Libor Barto, Andrei Krokhin, and Ross Willard.  Polymorphisms, and how to use them.  In Andrei Krokhin and Stanislav Živný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1–44. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2017.  doi:10.4230/DFU.Vol7.15301.1.
  * [17] Libor Barto, Jakub Opršal, and Michael Pinsker.  The wonderland of reflections.  Isr. J. Math, 223(1):363–398, Feb 2018.  arXiv:1510.04521, doi:10.1007/s11856-017-1621-9.
  * [18] Libor Barto and Michael Pinsker.  Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems).  SIAM J. Comput., 49(2):365–393, 2020.  doi:10.1137/18M1216213.
  * [19] Christoph Berkholz and Martin Grohe.  Linear Diophantine Equations, Group CSPs, and Graph Isomorphism.  In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17), pages 327–339. SIAM, 2017.  arXiv:1607.04287, doi:10.1137/1.9781611974782.21.
  * [20] Amey Bhangale and Subhash Khot.  Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups.  In Proc. 53rd Annual ACM Symposium on Theory of Computing (STOC’21), pages 1615–1628. ACM, 2021.  arXiv:2009.02815, doi:10.1145/3406325.3451003.
  * [21] Amey Bhangale, Subhash Khot, and Don Minzer.  On Approximability of Satisfiable $k$-CSPs: I.  In Proc. 54th Annual ACM Symposium on Theory of Computing (STOC’22), pages 976–988. ACM, 2022.  doi:10.1145/3519935.3520028.
  * [22] Manuel Bodirsky, Florent R. Madelaine, and Antoine Mottet.  A proof of the algebraic tractability conjecture for monotone monadic SNP.  SIAM J. Comput., 50(4):1359–1409, 2021.  doi:10.1137/19M128466X.
  * [23] Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz.  Constraint Satisfaction Problems for Reducts of Homogeneous Graphs.  SIAM J. Comput., 48(4):1224–1264, 2019.  arXiv:1602.05819, doi:10.1137/16M1082974.
  * [24] Joshua Brakensiek and Venkatesan Guruswami.  New hardness results for graph and hypergraph colorings.  In Proc. 31st Conference on Computational Complexity (CCC’16), volume 50 of LIPIcs, pages 14:1–14:27. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.  doi:10.4230/LIPIcs.CCC.2016.14.
  * [25] Joshua Brakensiek and Venkatesan Guruswami.  An algorithmic blend of LPs and ring equations for promise CSPs.  In Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’19), pages 436–455, 2019.  arXiv:1807.05194, doi:10.1137/1.9781611975482.28.
  * [26] Joshua Brakensiek and Venkatesan Guruswami.  Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.  SIAM J. Comput., 50(6):1663–1700, 2021.  arXiv:1704.01937, doi:10.1137/19M128212X.
  * [27] Joshua Brakensiek and Venkatesan Guruswami.  The quest for strong inapproximability results with perfect completeness.  ACM Trans. Algorithms, 17(3):27:1–27:35, 2021.  doi:10.1145/3459668.
  * [28] Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep.  Conditional Dichotomy of Boolean Ordered Promise CSPs.  TheoretiCS, 2, 2023.  arXiv:2102.11854, doi:10.46298/theoretics.23.2.
  * [29] Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep.  SDPs and Robust Satisfiability of Promise CSP.  In Proc. 55th Annual ACM Symposium on Theory of Computing (STOC’23). ACM, 2023.  arXiv:2211.08373.
  * [30] Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Živný.  The power of the combined basic LP and affine relaxation for promise CSPs.  SIAM J. Comput., 49:1232–1248, 2020.  arXiv:1907.04383, doi:10.1137/20M1312745.
  * [31] Alex Brandts, Marcin Wrochna, and Stanislav Živný.  The complexity of promise SAT on non-Boolean domains.  ACM Trans. Comput. Theory, 13(4):26:1–26:20, 2021.  arXiv:1911.09065, doi:10.1145/3470867.
  * [32] Mark Braverman, Subhash Khot, Noam Lifshitz, and Dor Minzer.  An Invariance Principle for the Multi-slice, with Applications.  In Proc. 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS’21), pages 228–236. IEEE, 2021.  arXiv:2110.10725, doi:10.1109/FOCS52979.2021.00030.
  * [33] Mark Braverman, Subhash Khot, and Dor Minzer.  On rich 2-to-1 games.  In Proc. 12th Innovations in Theoretical Computer Science Conference (ITCS’21), volume 185 of LIPIcs, pages 27:1–27:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.ITCS.2021.27.
  * [34] Andrei Bulatov.  Bounded relational width.  Unpublished manuscript, 2009.  URL: https://www2.cs.sfu.ca/~abulatov/papers/relwidth.pdf.
  * [35] Andrei Bulatov, Peter Jeavons, and Andrei Krokhin.  Classifying the complexity of constraints using finite algebras.  SIAM J. Comput., 34(3):720–742, 2005.  doi:10.1137/S0097539700376676.
  * [36] Andrei A. Bulatov.  The complexity of the counting constraint satisfaction problem.  J. ACM, 60(5):34, 2013.  doi:10.1145/2528400.
  * [37] Andrei A. Bulatov.  A dichotomy theorem for nonuniform CSPs.  In Proc. 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS’17), pages 319–330, 2017.  arXiv:1703.03021, doi:10.1109/FOCS.2017.37.
  * [38] Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, and Colin McQuillan.  The expressibility of functions on the Boolean domain, with applications to Counting CSPs.  J. ACM, 60(5):32, 2013.  doi:10.1145/2528401.
  * [39] Silvia Butti and Víctor Dalmau.  Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem.  In Proc. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS’21), volume 202 of LIPIcs, pages 27:1–27:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.  arXiv:2107.02956, doi:10.4230/LIPIcs.MFCS.2021.27.
  * [40] Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer.  Approximate Constraint Satisfaction Requires Large LP Relaxations.  J. ACM, 63(4):34:1–34:22, 2016.  doi:10.1145/2811255.
  * [41] Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, and David Richerby.  The complexity of approximating conservative counting CSPs.  J. Comput. Syst. Sci., 81(1):311–329, 2015.  arXiv:1208.1783, doi:10.1016/j.jcss.2014.06.006.
  * [42] Lorenzo Ciardo and Stanislav Živný.  Approximate graph colouring and crystals.  In Proc. 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA’23), pages 2256–2267, 2023.  arXiv:2210.08293, doi:10.1137/1.9781611977554.ch86.
  * [43] Lorenzo Ciardo and Stanislav Živný.  Approximate graph colouring and the hollow shadow.  In Proc. 55th Annual ACM Symposium on Theory of Computing (STOC’23). ACM, 2023.  arXiv:2211.03168.
  * [44] Lorenzo Ciardo and Stanislav Živný.  CLAP: A New Algorithm for Promise CSPs.  SIAM Journal on Computing, 52(1):1–37, 2023.  arXiv:2107.05018, doi:10.1137/22M1476435.
  * [45] Lorenzo Ciardo and Stanislav Živný.  Hierarchies of minion tests for PCSPs through tensors.  In Proc. 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA’23), pages 568–580, 2023.  arXiv:2207.02277, doi:10.1137/1.9781611977554.ch25.
  * [46] Adam Ó Conghaile.  Cohomology in Constraint Satisfaction and Structure Isomorphism.  In Proc. 47th International Symposium on Mathematical Foundations of Computer Science (MFCS’22), volume 241 of LIPIcs, pages 75:1–75:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.  arXiv:2206.15253, doi:10.4230/LIPIcs.MFCS.2022.75.
  * [47] Nadia Creignou.  A dichotomy theorem for maximum generalized satisfiability problems.  J. Comput. Syst. Sci., 51(3):511–522, 1995.  doi:10.1006/jcss.1995.1087.
  * [48] Nadia Creignou and Miki Hermann.  Complexity of generalized satisfiability counting problems.  Inf. Comput., 125(1):1–12, 1996.  doi:10.1006/inco.1996.0016.
  * [49] Nadia Creignou, Sanjeev Khanna, and Madhu Sudan.  Complexity Classification of Boolean Constraint Satisfaction Problems, volume 7 of SIAM Monographs on Discrete Mathematics and Applications.  SIAM, 2001.
  * [50] Nadia Creignou, Phokion G. Kolaitis, and Heribert Vollmer, editors.  Complexity of Constraints - An Overview of Current Research Themes, volume 5250 of Lecture Notes in Computer Science.  Springer, 2008.  doi:10.1007/978-3-540-92800-3.
  * [51] Louis Dale.  Direct sums of semirings and the Krull-Schmidt theorem.  Kyungpook Mathematical Journal, 17(2):135–141, 1977.  URL: https://koreascience.kr/article/JAKO197725748112087.pdf.
  * [52] Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, and Jakub Opršal.  Robust algorithms with polynomial loss for near-unanimity CSPs.  SIAM J. Comput., 48(6):1763–1795, 2019.  arXiv:1607.04787, doi:10.1137/18M1163932.
  * [53] Víctor Dalmau and Andrei A. Krokhin.  Robust Satisfiability for CSPs: Hardness and Algorithmic Results.  ACM Trans. Comput. Theory, 5(4):15:1–15:25, 2013.  doi:10.1145/2540090.
  * [54] Víctor Dalmau, Andrei A. Krokhin, and Rajsekar Manokaran.  Towards a characterization of constant-factor approximable finite-valued CSPs.  J. Comput. Syst. Sci., 97:14–27, 2018.  arXiv:1610.01019, doi:10.1016/j.jcss.2018.03.003.
  * [55] Victor Dalmau and Jakub Opršal.  Local consistency as a reduction between constraint satisfaction problems.  2023\.  arXiv:2301.05084.
  * [56] Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, and Andrei A. Krokhin.  The approximability of MAX CSP with fixed-value constraints.  J. ACM, 55(4):16:1–16:37, 2008.  doi:10.1145/1391289.1391290.
  * [57] Irit Dinur, Elchanan Mossel, and Oded Regev.  Conditional Hardness for Approximate Coloring.  SIAM J. Comput., 39(3):843–873, 2009.  doi:10.1137/07068062X.
  * [58] Irit Dinur, Oded Regev, and Clifford Smyth.  The hardness of 3-uniform hypergraph coloring.  Comb., 25(5):519–535, September 2005.  doi:10.1007/s00493-005-0032-4.
  * [59] Martin E. Dyer and David Richerby.  An Effective Dichotomy for the Counting Constraint Satisfaction Problem.  SIAM J. Comput., 42(3):1245–1274, 2013.  doi:10.1137/100811258.
  * [60] Alina Ene, Jan Vondrák, and Yi Wu.  Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems.  In Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’13), pages 306–325. SIAM, 2013.  arXiv:1503.03905, doi:10.1137/1.9781611973105.23.
  * [61] Tomás Feder and Moshe Y. Vardi.  The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory.  SIAM J. Comput., 28(1):57–104, 1998.  doi:10.1137/S0097539794266766.
  * [62] M. R. Garey and David S. Johnson.  The complexity of near-optimal graph coloring.  J. ACM, 23(1):43–49, 1976.  doi:10.1145/321921.321926.
  * [63] Mrinalkanti Ghosh and Madhur Tulsiani.  From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems.  Theory Comput., 14(1):1–33, 2018.  arXiv:1608.00497, doi:10.4086/toc.2018.v014a010.
  * [64] Martin Grohe.  The complexity of homomorphism and constraint satisfaction problems seen from the other side.  J. ACM, 54(1):1–24, 2007.  doi:10.1145/1206035.1206036.
  * [65] Venkatesan Guruswami and Sanjeev Khanna.  On the hardness of 4-coloring a 3-colorable graph.  SIAM Journal on Discrete Mathematics, 18(1):30–40, 2004.  doi:10.1137/S0895480100376794.
  * [66] Venkatesan Guruswami and Sai Sandeep.  d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors.  In Proc. 47th International Colloquium on Automata, Languages, and Programming (ICALP’20), volume 168 of LIPIcs, pages 62:1–62:12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.ICALP.2020.62.
  * [67] Pavol Hell, J Nešetřil, and Xuding Zhu.  Duality and polynomial testing of tree homomorphisms.  Transactions of the American Mathematical Society, 348(4):1281–1297, 1996.  doi:10.1090/S0002-9947-96-01537-1.
  * [68] Sangxia Huang.  Improved hardness of approximating chromatic number.  In Proc. 16th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques and the 17th International Workshop on Randomization and Computation (APPROX-RANDOM’13), pages 233–243. Springer, 2013.  arXiv:1301.5216, doi:10.1007/978-3-642-40328-6_17.
  * [69] Anna Huber, Andrei A. Krokhin, and Robert Powell.  Skew Bisubmodularity and Valued CSPs.  SIAM J. Comput., 43(3):1064–1084, 2014.  doi:10.1137/120893549.
  * [70] Peter G. Jeavons, David A. Cohen, and Marc Gyssens.  Closure Properties of Constraints.  J. ACM, 44(4):527–548, 1997.  doi:10.1145/263867.263489.
  * [71] Sanjeev Khanna, Nathan Linial, and Shmuel Safra.  On the hardness of approximating the chromatic number.  Comb., 20(3):393–415, 2000.  doi:10.1007/s004930070013.
  * [72] Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David Williamson.  The approximability of constraint satisfaction problems.  SIAM J. Comput., 30(6):1863–1920, 2000.  doi:10.1137/S0097539799349948.
  * [73] Subhash Khot.  Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring.  In Proc. 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS’01), pages 600–609. IEEE Computer Society, 2001.  doi:10.1109/SFCS.2001.959936.
  * [74] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell.  Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?  SIAM J. Comput., 37(1):319–357, 2007.  doi:10.1137/S0097539705447372.
  * [75] Phokion G. Kolaitis and Moshe Y. Vardi.  On the expressive power of datalog: Tools and a case study.  J. Comput. Syst. Sci., 51(1):110–134, 1995.  doi:10.1006/jcss.1995.1055.
  * [76] Phokion G. Kolaitis and Moshe Y. Vardi.  Conjunctive-query containment and constraint satisfaction.  J. Comput. Syst. Sci., 61(2):302–332, 2000.  doi:10.1006/jcss.2000.1713.
  * [77] Vladimir Kolmogorov, Johan Thapper, and Stanislav Živný.  The power of linear programming for general-valued CSPs.  SIAM J. Comput., 44(1):1–36, 2015.  arXiv:1311.4219, doi:10.1137/130945648.
  * [78] Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra.  Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs.  SIAM J. Comput., 51(2):17–305, 2022.  arXiv:1610.02704, doi:10.1137/17m1152966.
  * [79] Andrei Krokhin and Stanislav Živný, editors.  The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups.  Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017.  doi:10.4230/DFU.Vol7.15301.i.
  * [80] Andrei A. Krokhin, Jakub Opršal, Marcin Wrochna, and Stanislav Živný.  Topology and adjunction in promise constraint satisfaction.  SIAM Journal on Computing, 52(1):37–79, 2023.  arXiv:2003.11351, doi:10.1137/20M1378223.
  * [81] Gábor Kun, Ryan O’Donnell, Suguru Tamaki, Yuichi Yoshida, and Yuan Zhou.  Linear programming, width-1 CSPs, and robust satisfaction.  In Proc. 3rd Innovations in Theoretical Computer Science (ITCS’12), pages 484–495. ACM, 2012.  doi:10.1145/2090236.2090274.
  * [82] Jean B. Lasserre.  An explicit equivalent positive semidefinite program for nonlinear 0-1 programs.  SIAM J. Optim., 12(3):756–769, 2002.  doi:10.1137/S1052623400380079.
  * [83] Monique Laurent.  A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0-1 Programming.  Math. Oper. Res., 28(3):470–496, 2003.  doi:10.1287/moor.28.3.470.16391.
  * [84] James R. Lee, Prasad Raghavendra, and David Steurer.  Lower Bounds on the Size of Semidefinite Programming Relaxations.  In Proc. 47th Annual ACM on Symposium on Theory of Computing (STOC’15), pages 567–576. ACM, 2015.  arXiv:1411.6317, doi:10.1145/2746539.2746599.
  * [85] Lek-Heng Lim.  Tensors and hypermatrices.  In Leslie Hogben, editor, Handbook of Linear Algebra, pages 231–260. CRC Press Boca Raton, 2nd edition, 2014.
  * [86] László Lovász and Alexander Schrijver.  Cones of Matrices and Set-Functions and 0-1 Optimization.  SIAM Journal on Optimization, 1(2):166–190, 1991.  doi:10.1137/0801013.
  * [87] Alan K. Mackworth.  Consistency in networks of relations.  Artif. Intell., 8(1):99–118, 1977.  doi:10.1016/0004-3702(77)90007-8.
  * [88] Anatolii Malcev.  Untersuchungen aus dem Gebiete der mathematischen Logik.  Matematicheskii Sbornik, 43(3):323–336, 1936.  URL: https://www.mathnet.ru/links/2090b73a4fdf4a07674132012862f576/sm5392.pdf.
  * [89] Dániel Marx.  Tractable hypergraph properties for constraint satisfaction and conjunctive queries.  J. ACM, 60(6), 2013.  Article No. 42.  arXiv:0911.0801, doi:10.1145/2535926.
  * [90] Tamio-Vesa Nakajima and Stanislav Živný.  Linearly ordered colourings of hypergraphs.  ACM Trans. Comput. Theory, 13(3–4), 2022.  arXiv:2204.05628, doi:10.1145/3570909.
  * [91] Prasad Raghavendra.  Optimal algorithms and inapproximability results for every CSP?  In Proc. 40th Annual ACM Symposium on Theory of Computing (STOC’08), pages 245–254, 2008.  doi:10.1145/1374376.1374414.
  * [92] Danny Rorabaugh, Claude Tardif, and David L. Wehlau.  Logical compactness and constraint satisfaction problems.  Log. Methods Comput. Sci., 13(1), 2017.  doi:10.23638/LMCS-13(1:1)2017.
  * [93] H. D. Sherali and W. P. Adams.  A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems.  SIAM J. Discret. Math., 3(3):411–430, 1990.  doi:10.1137/0403036.
  * [94] Johan Thapper and Stanislav Živný.  The complexity of finite-valued CSPs.  J. ACM, 63(4):37:1–37:33, 2016.  arXiv:1210.2987, doi:10.1145/2974019.
  * [95] Johan Thapper and Stanislav Živný.  The power of Sherali-Adams relaxations for general-valued CSPs.  SIAM J. Comput., 46(4):1241–1279, 2017.  arXiv:1606.02577, doi:10.1137/16M1079245.
  * [96] Madhur Tulsiani.  CSP gaps and reductions in the Lasserre hierarchy.  In Proc. 41st Annual ACM Symposium on Theory of Computing (STOC’09), pages 303–312. ACM, 2009.  doi:10.1145/1536414.1536457.
  * [97] Dmitriy Zhuk.  A proof of the CSP dichotomy conjecture.  J. ACM, 67(5):30:1–30:78, 2020.  arXiv:1704.01914, doi:10.1145/3402029.
  * [98] Uri Zwick.  Finding almost-satisfying assignments.  In Proc. 13th Annual ACM Symposium on the Theory of Computing (STOC’98), pages 551–560. ACM, 1998.  doi:10.1145/276698.276869.