# Complexity Classification Transfer for CSPs
via Algebraic Products

Manuel Bodirsky, Peter Jonsson, Barnaby Martin,
Antoine Mottet, Žaneta Semanišinová Manuel Bodirsky has received funding from
the ERC under the European Community’s Seventh Framework Programme (Grant
Agreement no. 681988, CSP-Infinity).Peter Jonsson is partially supported by
the Swedish Research Council (VR) under grants 2017-04112 and 2021-04371.

###### Abstract

We study the complexity of infinite-domain constraint satisfaction problems:
our basic setting is that a complexity classification for the CSPs of first-
order expansions of a structure $\mathfrak{A}$ can be transferred to a
classification of the CSPs of first-order expansions of another structure
$\mathfrak{B}$. We exploit a product of structures (the algebraic product)
that corresponds to the product of the respective polymorphism clones and
present a complete complexity classification of the CSP for first-order
expansions of the $n$-fold algebraic power of $({\mathbb{Q}};<)$. This is
proved by various algebraic and logical methods in combination with knowledge
of the polymorphisms of the tractable first-order expansions of
$({\mathbb{Q}};<)$ and explicit descriptions of the expressible relations in
terms of syntactically restricted first-order formulas. By combining our
classification result with general classification transfer techniques, we
obtain surprisingly strong new classification results for highly relevant
formalisms such as Allen’s Interval Algebra, the $n$-dimensional Block
Algebra, and the Cardinal Direction Calculus, even if higher-arity relations
are allowed. Our results confirm the infinite-domain tractability conjecture
for classes of structures that have been difficult to analyse with older
methods. For the special case of structures with binary signatures, the
results can be substantially strengthened and tightly connected to Ord-Horn
formulas; this solves several longstanding open problems from the AI
literature.

###### Contents

  1. 1 Introduction
  2. 2 Constraint Satisfaction Problems
    1. 2.1 Basic Definitions
    2. 2.2 Primitive Positive Constructions
    3. 2.3 Model Theory and Algebra
  3. 3 Algebraic Products
    1. 3.1 Basic Properties
    2. 3.2 $i$-Determined Clauses
  4. 4 Algebraic Powers of $({\mathbb{Q}};<)$
    1. 4.1 First-order Expansions of $({\mathbb{Q}};<)$
    2. 4.2 Polymorphisms
    3. 4.3 Syntactic Normal Forms
      1. 4.3.1 Normalisation
      2. 4.3.2 Definitions via Restricted Clauses
    4. 4.4 Polynomial-time Algorithms
    5. 4.5 Classification in the 2-Dimensional Case
    6. 4.6 Classification in the $n$-Dimensional Case
    7. 4.7 Classification of Binary Relations
  5. 5 Complexity Classification Transfer
  6. 6 Applications
    1. 6.1 Cardinal Direction Calculus
    2. 6.2 Allen’s Interval Algebra
      1. 6.2.1 First-order Expansions of $\\{{\sf m}\\}$
      2. 6.2.2 First-order Expansions of $\\{{\sf s},{\sf f}\\}$
    3. 6.3 Block Algebra
  7. 7 Conclusions and Open Problems

##  1 Introduction

This introductory section is divided into three parts where we describe the
background, present our contributions, and provide an outline of the article,
respectively.

### Background

Constraint satisfaction problems (CSPs) are computational problems that appear
in many areas of computer science, for example in temporal and spatial
reasoning in artificial intelligence [BJ17] or in database theory [KV98,
BtCLW14]. The computational complexity of CSPs is of central interest in these
areas, and a general research goal is to obtain systematic complexity
classification results, in particular about CSPs that are in P and CSPs that
are NP-hard. CSPs can be described elegantly by fixing a structure with a
finite relational signature, the _template_ ; the computational task is to
determine whether a given finite input structure has a homomorphism to the
template. A breakthrough result was obtained by Bulatov [Bul17] and by Zhuk
[Zhu20], which confirmed the famous Feder-Vardi conjecture [FV99]: every CSP
over a finite template (i.e., a structure with a finite domain) is in P, or it
is NP-complete. Moreover, given the template it is possible to decide
algorithmically whether its CSP is in P or whether it is NP-complete.

Most of the CSPs in temporal and spatial reasoning can _not_ be formulated as
CSPs with a finite template. The same is true for many of the CSPs that appear
in database theory (e.g., most of the CSPs in the logic MMSNP, which is a
fragment of existential second-order logic introduced by Feder and Vardi
[FV99], and which is important for database theory [BtCLW14], cannot be
formulated as CSPs with a finite template [MS07]). For CSPs with infinite
templates we may not hope for general classification results [BG08]; however,
we may hope for general classification results if we restrict our attention to
classes of templates that are model-theoretically well behaved. An example of
such a class is the class of all structures with domain ${\mathbb{Q}}$ where
all relations are definable with a first-order formula over the structure
$({\mathbb{Q}};<)$. This class of structures is of fundamental interest in
model theory, and, by a result of Cameron [Cam76], also in the theory of
infinite permutation groups (it is precisely the class of all countable
structures with a highly set-transitive automorphism group). The CSPs for such
structures have been called _temporal CSPs_ because they include many CSPs
that are of relevance in temporal reasoning, such as the Betweenness problem
[Opa79], the And/Or scheduling problem [MSS04], or the satisfiability problem
for Ord-Horn constraints [NB95]. The complexity of temporal CSPs has been
classified by Bodirsky and Kára [BK09], and a temporal CSP is either in P or
it is NP-complete.

Over the past 10 years, many classes of infinite structures have been
classified with respect to the complexity of their CSP. We may divide these
results into _first-_ and _second-generation_ classifications. First-
generation classifications, such as the classification of temporal CSPs
mentioned above, typically use concepts from universal algebra and Ramsey
theory, and essentially proceed by a combinatorial case distinction [BP15a,
BMPP19, KP18, BJP17]. Second-generation classifications also use universal
algebra and Ramsey theory, but they eliminate large parts of the combinatorial
analysis by using arguments for finite structures and the Bulatov-Zhuk theorem
(the first example following this approach is [BM18]; other examples include
[BMM21, MP22, BB21, MNPW21, BK21]). So the idea of second-generation
classifications is to _transfer_ the finite-domain classification to certain
tame classes of infinite structures.

Complexity transfer is also the topic of the present article; however, we
transfer classification results not from finite structures to classes of
infinite structures, but between classes of infinite structures. The key to
systematically relating many classes of infinite structures are various
_product constructions_ , and _logical interpretations_. Examples are _Allen’s
Interval Algebra_ [All83] from temporal reasoning, which has a first-order
interpretation in $({\mathbb{Q}};<)$, or the _rectangle algebra_ [Gue89, MJ90]
and the $r$-dimensional _block algebra_ [BCdC02], which can be obtained as
products of Allen’s Interval Algebra. These links extend to links between
fragments of the respective formalisms. In order to also establish links
between the complexity of the respective CSPs, the logical interpretations
must use _primitive positive_ formulas, rather than full first-order logic.
There are various notions of products of constraint formalisms that have been
studied in the literature; see [WW09, BS03]. In this article we use a certain
product of structures known as the _algebraic product_ ; it has the advantage
that it corresponds to the product of the respective polymorphism clones,
which is essential for the universal algebraic approach.

### Contributions

This article contains both theoretical results and applications of these
results to well-studied formalisms and open problems in the area. Our first
main technical contribution is a complete complexity classification for the
CSPs of first-order expansions of $({\mathbb{Q}};<)\boxtimes({\mathbb{Q}};<)$,
i.e., the algebraic product of $({\mathbb{Q}};<)$ with itself. This result can
then be generalised to first-order expansions of finite algebraic powers of
$(\mathbb{Q};<)$, denoted by $({\mathbb{Q}};<)^{(n)}$. In the proof we use
known results about first-order expansions of $({\mathbb{Q}};<)$ combined with
a mix of algebraic and of logical arguments. On the algebraic side, we use the
fact that the polynomial-time first-order expansions of $({\mathbb{Q}};<)$
have certain polymorphisms. On the logic side, we use highly informative
descriptions of the relations of the templates using syntactically restricted
forms of first-order logic. This combination of methods turned out to be very
powerful in our setting. We believe that combining algebraic and syntactic
arguments will be fruitful for analysing first-order expansions of products of
other structures.

Together with a general classification transfer result from [Bod21], we then
obtain a sequence of new complexity classification results for classes of CSPs
that have been studied in temporal and spatial reasoning. We derive our
applications in two steps: we first derive classification results for
structures with relations of arbitrary arity. With little extra effort, we
then obtain stronger results for the special case that all relations are
binary: binary relations have been studied most intensively in the AI
literature.

Templates with relations of unrestricted arity. We determine the complexity of
the CSP for first-order expansions of the basic relations in three influential
formalisms for spatio-temporal reasoning: Allen’s Interval Algebra [All83],
the Block Algebra [BCdC02], and the Cardinal Direction Calculus [Lig98b]. In
these particular cases, our results show that the so-called _infinite-domain
tractability conjecture_ for reducts of finitely bounded homogeneous
structures [BPP21] holds. The conjecture states that such a structure has a
polynomial-time tractable CSP unless the structure admits a primitive positive
interpretation of a structure which is homomorphically equivalent to $K_{3}$,
the clique with three vertices (note that the CSP for the template $K_{3}$ is
the 3-colourability problem, which is a well-known NP-complete problem). All
the classes of infinite structures discussed so far are first-order
interpretable over $({\mathbb{Q}};<)$ and it can be shown that they fall into
the scope of this conjecture (see, for instance, Theorem 4 from [MP21], Lemma
3.5.4 and Proposition 4.2.19 from [Bod21], and Lemma 3.8 from[BOP18]).
Interestingly, the structures we treat here are notoriously difficult for the
methods underpinning second-generation classification results: e.g., the
unique interpolation property usually fails in this context [BB21].

To make progress with proving the infinite-domain tractability conjecture, one
strategy is to verify it on larger and larger classes of structures. Highly
useful restrictions on classes of interesting structures come from model
theory. The concept of _stability_ and _NIP_ (i.e. not having Shelah’s
independence property [She71]) are central concepts in model theory (see,
e.g., [Sim15, Che19]). We would like to stress the particular role of
structures with a first-order interpretation over $({\mathbb{Q}};<)$ in this
context. All of these structures are NIP. Moreover, it is known that every
homogeneous structure with a finite relational signature which is stable has a
first-order interpretation in $({\mathbb{Q}};<)$ [Lac92]. Therefore, a
complexity classification for CSPs of structures with a first-order
interpretation in $({\mathbb{Q}};<)$ would be an important step forward
concerning the tractability conjecture. Our results represent a step towards
this goal.

Templates with binary relations. Our results concerning first-order expansions
of $({\mathbb{Q}};<)^{(n)}$ can be specialised to the case when only binary
relations are allowed. If $\mathfrak{D}$ is such a structure, then our results
imply that CSP$(\mathfrak{D})$ is in P if and only if every relation in
$\mathfrak{D}$ can be defined by an Ord-Horn formula [NB95]. This allows us to
answer several open questions from the AI literature. In particular, we solve
an open problem from 2002 about the $n$-dimensional cardinal direction
calculus [BC02] (Section 6.1), an open problem from 1999 about fragments of
the rectangle algebra [BCdC99] (Theorem 78) and an open problem from 2002
about the $n$-dimensional block algebra [BCdC02] (Theorem 80). We can also
answer a question in the last paper about integration of the tractable cases
into tractable formalisms that can also handle metric constraints; see the
discussion at the end of Section 6.3. Finally, we obtain short new proofs of
known results about reducts of Allen’s Interval Algebra (Section 6.2). Our
results typically answer more general questions than those asked in the
publications above.

### Outline

The structure of the article is as follows. Section 2 contains the basic
concepts that are needed for a formal definition of the CSPs, and some facts
about constraint satisfaction problems and their computational complexity.
Section 3 contains the definition of the algebraic product together with some
related results. In Section 4, we study $({\mathbb{Q}};<)^{(n)}$, and this
ultimately provides us with a complexity classification of the CSP for first-
order expansions of $({\mathbb{Q}};<)^{(n)}$. We additionally study the
restriction to binary signatures in this section, i.e., signatures where all
relations have arity at most two. The next section is devoted to a condensed
introduction to complexity classification transfer. Thereafter, we combine the
complexity results for $({\mathbb{Q}};<)^{(n)}$ with complexity classification
transfer in order to analyse various spatio-temporal formalisms in Section 6.
We conclude the article with a brief discussion of the results together with
some possible future research directions (Section 7).

Some of the results of the present article have been announced in a conference
paper [BJMM18]. However, one of the central proofs (Lemma 2) is not correct.
The proof in the present article is entirely new; in particular, the syntactic
approach to analysing first-order expansions of products mentioned above did
not appear in the old approach.

##  2 Constraint Satisfaction Problems

In this section we introduce basic concepts that are needed for a formal
definition of the class of constraint satisfaction problems (CSP) together
with some basic facts about CSPs and their computational complexity.

###  2.1 Basic Definitions

Let $\tau$ be a _relational signature_ , i.e., a set of _relation symbols_
$R$, each equipped with an _arity_ $k\in{\mathbb{N}}$. A _$\tau$ -structure_
$\mathfrak{A}$ consists of a set $A$, called the _domain_ of $\mathfrak{A}$,
and a relation $R^{\mathfrak{A}}\subseteq A^{k}$ for each relation symbol
$R\in\tau$ of arity $k$. A structure is called _finite_ if its domain is
finite. Relational structures are often written like
$(A;R_{1}^{\mathfrak{A}},R_{2}^{\mathfrak{A}},\dots)$, with the obvious
interpretation; for example, $({\mathbb{Q}};<)$ denotes the structure whose
domain is the set of rational numbers ${\mathbb{Q}}$ and which carries a
single binary relation $<$ which denotes the usual strict order of the
rationals. Sometimes, we do not distinguish between the symbol $R$ for a
relation and the relation $R^{\mathfrak{A}}$ itself. Let $\mathfrak{A}$ be a
$\tau$-structure and let $\mathfrak{A}^{\prime}$ be a
$\tau^{\prime}$-structure with $\tau\subseteq\tau^{\prime}$. If $\mathfrak{A}$
and $\mathfrak{A}^{\prime}$ have the same domain and
$R^{\mathfrak{A}}=R^{\mathfrak{A}^{\prime}}$ for all $R\in\tau$, then
$\mathfrak{A}$ is called a $\tau$-_reduct_ (or simply _reduct_) of
$\mathfrak{A}^{\prime}$, and $\mathfrak{A}^{\prime}$ is called a
$\tau^{\prime}$-_expansion_ (or simply _expansion_) of $\mathfrak{A}$. If $R$
is a relation over the domain of $\mathfrak{B}$, then we let
$(\mathfrak{A};R)$ denote the expansion of $\mathfrak{A}$ by $R$.

We continue by introducing some logical terminology and machinery. We refer
the reader to [Hod97] for an introduction to first-order logic. We say that a
structure $\mathfrak{B}$ has _quantifier elimination_ if every first-order
formula is equivalent to a quantifier-free formula over $\mathfrak{B}$. Every
quantifier-free formula can be written in _conjunctive normal form_ (CNF),
i.e., as a conjunction of disjunctions of literals, i.e., atomic formulas or
their negations. A disjunction of literals is also called a clause.

Let $\mathfrak{B}$ denote a $\tau$-structure. If $\psi$ is a sentence (i.e. a
first-order formula without free variables), then we write
$\mathfrak{B}\models\psi$ to denote that $\mathfrak{B}$ is a model of (or
satisfies) $\psi$. One can use first-order formulas over the signature $\tau$
to define relations over $\mathfrak{B}$: if $\phi(x_{1},\dots,x_{n})$ is a
first-order $\tau$-formula with free variables $x_{1},\dots,x_{n}$, then the
relation _defined_ by $\phi$ over $\mathfrak{B}$ is the relation
$\\{(b_{1},\dots,b_{n})\in
B^{n}\mid\mathfrak{B}\models\phi(b_{1},\dots,b_{n})\\}$. A first-order
$\tau$-formula is preserved by a map between two $\tau$-structures
$\mathfrak{A}$ and $\mathfrak{B}$ if it preserves the relation defined by the
formula in these structures. A _first-order expansion_ of $\mathfrak{A}$ is a
structure $\mathfrak{A}^{\prime}$ augmented by relations that are first-order
definable in $\mathfrak{A}$. We sometimes say that $\mathfrak{A}^{\prime}$ is
above $\mathfrak{A}$ if $\mathfrak{A}^{\prime}$ is a first-order expansion of
$\mathfrak{A}$. A _first-order reduct_ of $\mathfrak{A}$ is a reduct of a
first-order expansion of $\mathfrak{B}$

If $\mathfrak{A}$ and $\mathfrak{B}$ are $\tau$-structures, then a
_homomorphism_ from $\mathfrak{A}$ to $\mathfrak{B}$ is a function $h\colon
A\to B$ that _preserves_ all the relations, that is, if
$(a_{1},\dots,a_{k})\in R^{\mathfrak{A}}$, then $(h(a_{1}),\dots,h(a_{k}))\in
R^{\mathfrak{B}}$. The structures $\mathfrak{A}$ and $\mathfrak{B}$ are called
_homomorphically equivalent_ if there exists a homomorphism from
$\mathfrak{A}$ to $\mathfrak{B}$ and a homomorphism from $\mathfrak{B}$ to
$\mathfrak{A}$. Relational structures might have an infinite signature;
however, to avoid representational issues and for simplicity we restrict
ourselves to finite signatures in the following definition.

######  Definition 1 (CSPs).

Let $\tau$ be a finite relational signature and let $\mathfrak{B}$ be a
$\tau$-structure. The _constraint satisfaction problem_ for $\mathfrak{B}$,
denoted by $\operatorname{CSP}(\mathfrak{B})$, is the computational problem of
deciding for a given finite $\tau$-structure $\mathfrak{A}$ whether
$\mathfrak{A}$ has a homomorphism to $\mathfrak{B}$ or not.

Note that this definition of constraint satisfaction problems can be used even
if $\mathfrak{B}$ is an infinite structure. Also note that homomorphically
equivalent structures have the same CSP.

######  Example 2.

The structure $(\\{0,1,2\\};\neq)$ is denoted by $K_{3}$. The problem
$\operatorname{CSP}(K_{3})$ is the three-colorability problem for graphs. The
input is a structure with a single binary relation, representing edges in a
graph (ignoring the orientation); homomorphisms from this graph to $K_{3}$
correspond precisely to the proper 3-colorings of the graph.

###  2.2 Primitive Positive Constructions

Three central concepts in the complexity analysis of CSPs are _primitive
positive definitions_ , _primitive positive interpretations_ , and _primitive
positive constructions_. The three concepts are increasingly powerful. Their
definitions build on each other and will be recalled here for the convenience
of the reader.

An _atomic $\tau$-formula_ is a formula of the form $x=y$,
$R(x_{1},\dots,x_{n})$, or the form $\bot$, where $x_{1},\dots,x_{n},x,y$ are
variables, $R$ is a symbol from $\tau$, and $\bot$ is a symbol that stands for
‘false’. A _primitive positive $\tau$-formula_ is a formula
$\phi(x_{1},\dots,x_{n})$ with free variables $x_{1},\dots,x_{n}$ of the form

$\exists y_{1},\dots,y_{l}(\psi_{1}\wedge\cdots\wedge\psi_{m})$

where $\psi_{1},\dots,\psi_{k}$ are atomic $\tau$-formulas over the variables
$x_{1},\dots,x_{n},y_{1},\dots,y_{l}$. Two relational structures
$\mathfrak{A}$ and $\mathfrak{B}$ are called

  * •

_(primitively positive) interdefinable_ if they have the same domain $A=B$,
and if every relation of $\mathfrak{A}$ is (primitively positively) definable
in $\mathfrak{B}$ and vice versa.

  * •

_(primitively positively) bi-definable_ if $\mathfrak{B}$ is isomorphic to a
structure that is (primitively positively) interdefinable with $\mathfrak{A}$.

We will now turn our attention towards methods for complexity analysis.

######  Lemma 3 ([Jea98]).

Let $\mathfrak{A}$ and $\mathfrak{B}$ be structures with finite relational
signatures and the same domain. If every relation of $\mathfrak{A}$ has a
primitive positive definition in $\mathfrak{B}$, then there is a polynomial-
time reduction from $\operatorname{CSP}(\mathfrak{A})$ to
$\operatorname{CSP}(\mathfrak{B})$.

Primitive positive definability can be generalised as follows.

######  Definition 4 (Interpretations).

A _(primitive positive) interpretation_ of a structure $\mathfrak{C}$ in a
structure $\mathfrak{B}$ is a partial surjection $I$ from $B^{d}$ to $C$, for
some finite $d\in{\mathbb{N}}$ called the _dimension_ of the interpretation,
such that the preimage of a relation of arity $k$ defined by an atomic formula
in $\mathfrak{C}$, considered as a relation of arity $dk$ over $B$, is
(primitively positively) definable in $\mathfrak{B}$; in this case, we say
that $\mathfrak{C}$ is (primitively positively) interpretable in
$\mathfrak{B}$.

Primitive positive interpretations preserve the complexity of CSPs in the
following way.

######  Proposition 5 (see, e.g., Theorem 3.1.4 in [Bod21]).

Let $\mathfrak{B}$ and $\mathfrak{C}$ be structures with finite relational
signatures. If $\mathfrak{C}$ has a primitive positive interpretation in
$\mathfrak{B}$, then there is a polynomial-time reduction from
$\operatorname{CSP}(\mathfrak{C})$ to $\operatorname{CSP}(\mathfrak{B})$.

######  Example 6.

Let ${\mathbb{I}}$ be the set of all pairs $(x,y)\in{\mathbb{Q}}^{2}$ such
that $x<y$; i.e., ${\mathbb{I}}$ might be viewed as the set of all closed
intervals $[a,b]$ of rational numbers. Let $\sf m$ be the binary relation over
${\mathbb{I}}$ that contains all pairs $((a_{1},a_{2}),(b_{1},b_{2}))$ such
that $a_{2}=b_{1}$. Then the structure $({\mathbb{I}};{\sf m})$ has a
primitive positive interpretation (of dimension 2) in $({\mathbb{Q}};<)$:

  * •

The preimage of the relation defined by the atomic formula $a=b$ is defined by
the formula $a_{1}=b_{1}\wedge a_{2}=b_{2}\wedge a_{1}<a_{2}$.

  * •

The preimage of the relation defined by the atomic formula ${\sf m}(a,b)$ is
defined by the formula $a_{1}<a_{2}\wedge a_{2}=b_{1}\wedge b_{1}<b_{2}$;

It is straightforward to adapt the construction above to atomic formulas that
are obtained by variable identification by using the equality relation.
Proposition 5 implies that CSP$({\mathbb{I}};{\sf m})$ is in P since
CSP$({\mathbb{Q}};<)$ is in P.

######  Example 7.

The interval algebra [All83] is a formalism that is both well-known and well-
studied in AI. It can be viewed as a relational structure with the domain
${\mathbb{I}}$ introduced in Example 6 and a binary relation symbol for each
binary relation $R\subseteq{\mathbb{I}}^{2}$ such that the relation
$\\{(a_{1},a_{2},b_{1},b_{2})\mid((a_{1},a_{2}),(b_{1},b_{2}))\in R\\}$ is
first-order definable in $({\mathbb{Q}};<)$. We let $\mathfrak{IA}$ denote
this structure and we let $\top$ denote the relation which holds for all pairs
of intervals. Clearly, Allen’s Interval Algebra has a 2-dimensional
interpretation in $({\mathbb{Q}};<)$, but not a primitive positive
interpretation.

The _basic_ relations of Allen’s Interval Algebra are the 13 relations defined
in Table 1: we let $\mathfrak{IA}^{b}$ be the corresponding structure. If
$I=[a,b]\in\mathbb{I}$, then we write $I^{-}$ for $a$ and $I^{+}$ for $b$. It
is well-known that all the basic relations of Allen’s Interval Algebra have a
primitive positive definition over $({\mathbb{I}};{\sf m})$ [AH85]. We
conclude that $\operatorname{CSP}(\mathfrak{IA}^{b})$ is in P since
$\operatorname{CSP}({\mathbb{I}};{\sf m})$ is in P by the previous example.

Basic relation |  | Example | Endpoints
---|---|---|---
$X$ precedes $Y$ | p | XXX | $X^{+}<Y^{-}$
$Y$ preceded by $X$ | p⌣ |  YYY |
$X$ meets $Y$ | m | XXXX | $X^{+}=Y^{-}$
$Y$ is met by $X$ | m⌣ |  YYYY |
$X$ overlaps $Y$ | o | XXXX | $X^{-}<Y^{-}\>\wedge$
|  |  YYYY | $Y^{-}<X^{+}\>\wedge$
$Y$ overlapped by $X$ | o⌣ |  | $X^{+}<Y^{+}\>\wedge$
$X$ during $Y$ | d |  XX | $X^{-}>Y^{-}\>\wedge$
$Y$ includes $X$ | d⌣ | YYYYYY | $X^{+}<Y^{+}$
$X$ starts $Y$ | s | XXX | $X^{-}=Y^{-}\>\wedge$
$Y$ started by $X$ | s⌣ | YYYYYY | $X^{+}<Y^{+}$
$X$ finishes $Y$ | f |  XXX | $X^{+}=Y^{+}\>\wedge$
$Y$ finished by $X$ | f⌣ | YYYYYY | $X^{-}>Y^{-}$
$X$ equals $Y$ | $\equiv$ | XXXX | $X^{-}=Y^{-}\>\wedge$
|  | YYYY | $X^{+}=Y^{+}$
Table 1: Basic relations in the interval algebra.

We finally define primitive positive constructions. We will not use such
constructions in our proofs but it is used in the statement of Theorem 11 and,
thus, in the formulation of the infinite-domain tractability conjecture.

######  Definition 8 (Primitive positive constructions).

A structure $\mathfrak{C}$ has a _primitive positive construction_ in
$\mathfrak{B}$ if $\mathfrak{C}$ is homomorphically equivalent to a structure
$\mathfrak{C}^{\prime}$ with a primitive positive interpretation in
$\mathfrak{B}$.

######  Lemma 9.

Let $\mathfrak{B}$ and $\mathfrak{C}$ be structures with finite relational
signature. If $\mathfrak{C}$ has a primitive positive construction in
$\mathfrak{B}$, then there is a polynomial-time reduction from
$\operatorname{CSP}(\mathfrak{C})$ to $\operatorname{CSP}(\mathfrak{B})$.

###### Proof.

An immediate consequence of Proposition 5 since homomorphically equivalent
structures have the same CSP. ∎

###  2.3 Model Theory and Algebra

This section collects some basic terminology and facts from model theory and
algebra. The set of all first-order $\tau$-sentences that are true in a given
$\tau$-structure $\mathfrak{A}$ is called the first-order theory of
$\mathfrak{A}$. A countable structure $\mathfrak{A}$ is _$\omega$
-categorical_ if all countable models of the first-order theory of
$\mathfrak{A}$ are isomorphic. The structure $({\mathbb{Q}};<)$, and all
structures with an interpretation in $({\mathbb{Q}};<)$, are
$\omega$-categorical: for the structure $({\mathbb{Q}};<)$, this was shown by
Cantor who proved that all countable dense and unbounded linear orders are
isomorphic. All structures that we encounter in the later parts of this
article are $\omega$-categorical.

An _automorphism_ of a structure $\mathfrak{A}$ is a permutation $\alpha$ of
$A$ such that both $\alpha$ and its inverse are homomorphisms. The set of all
automorphisms of a structure $\mathfrak{A}$ is denoted by
$\operatorname{Aut}(\mathfrak{A})$, and forms a group with respect to
composition; the neutral element of the group is the identity map which is
denoted by $\operatorname{id}_{A}$. The set of all permutations of a set $A$
is called the _symmetric group_ and denoted by $\operatorname{Sym}(A)$.
Clearly, $\operatorname{Sym}(A)$ equals $\operatorname{Aut}(A;=)$.

The _orbit_ of $(a_{1},\dots,a_{n})\in A^{n}$ in
$\operatorname{Aut}(\mathfrak{A})$ is the set
$\\{(\alpha(a_{1}),\dots,\alpha(a_{n}))\mid\alpha\in\operatorname{Aut}(\mathfrak{A})\\}$.
A countable structure $\mathfrak{A}$ is $\omega$-categorical if and only if
$\operatorname{Aut}(\mathfrak{A})$ is _oligomorphic_ , i.e., has only finitely
many orbits of $n$-tuples, for all $n\geq 1$ [Hod97, Theorem 6.3.1]. This
implies that structures with a first-order interpretation in an
$\omega$-categorical structure are $\omega$-categorical [Hod97, Theorem
6.3.6]. In particular, first-order reducts of $\omega$-categorical structures
are again $\omega$-categorical. It also follows that first-order expansions of
$\omega$-categorical structures $\mathfrak{B}$ are $\omega$-categorical
themselves since such relations are preserved by all automorphisms of
$\mathfrak{B}$. In an $\omega$-categorical structure $\mathfrak{B}$, a
relation is preserved by all automorphisms of $\mathfrak{B}$ if and only if it
is first-order definable in $\mathfrak{B}$ (see, e.g., [Bod21, Theorem
4.2.9]).

Another important property of $({\mathbb{Q}};<)$ is called _homogeneity_. An
_embedding_ from $\mathfrak{A}$ to $\mathfrak{B}$ is an injective homomorphism
$e$ from $\mathfrak{A}$ to $\mathfrak{B}$ which also preserves the complement
of each relation, i.e., $(a_{1},\dots,a_{k})\in R^{\mathfrak{A}}$ if and only
if $(f(a_{1}),\dots,f(a_{k}))\in R^{\mathfrak{B}}$. A $\tau$-structure
$\mathfrak{A}$ is called a _substructure_ of $\mathfrak{B}$ if $A\subseteq B$
and the identity map $\operatorname{id}_{A}$ is an embedding from
$\mathfrak{A}$ to $\mathfrak{B}$. Now, a relational structure is called
_homogeneous_ (or sometimes _ultrahomogeneous_) if every isomorphism between
finite substructures can be extended to an automorphism of the structure
[Hod97, p. 160]. An $\omega$-categorical structure $\mathfrak{B}$ is
homogeneous if and only if $\mathfrak{B}$ has quantifier elimination [Hod97,
Theorem 6.4.1].

We have seen that a relation $R$ is first-order definable in an
$\omega$-categorical structure $\mathfrak{B}$ if and only if it is preserved
by all automorphisms of $\mathfrak{B}$. Similarly, the question whether a
given relation is primitively positively definable in $\mathfrak{B}$ can be
studied using _polymorphisms_. A polymorphism of a structure $\mathfrak{B}$ is
a homomorphism from $\mathfrak{B}^{k}$ to $\mathfrak{B}$. Here, the structure
$\mathfrak{B}^{k}$ denotes the $k$-fold direct product structure
$\mathfrak{B}\times\cdots\times\mathfrak{B}$; more generally, if
$\mathfrak{B}_{1},\dots,\mathfrak{B}_{k}$ are $\tau$-structures, then
$\mathfrak{C}=\mathfrak{B}_{1}\times\cdots\times\mathfrak{B}_{k}$ is defined
to be the $\tau$-structure with domain $B_{1}\times\cdots\times B_{k}$ and for
every $R\in\tau$ of arity $m$ we have

$\displaystyle R^{\mathfrak{C}}=\\{$
$\displaystyle((a_{1,1},\dots,a_{1,k}),\dots,(a_{m,1},\dots,a_{m,k}))\in
C^{m}\mid$ $\displaystyle(a_{1,1},\dots,a_{m,1})\in
R^{\mathfrak{B}_{1}},\dots,(a_{1,k},\dots,a_{m,k})\in
R^{\mathfrak{B}_{k}}\\}.$

The set of all polymorphisms of a structure $\mathfrak{B}$ is denoted by
$\operatorname{Pol}(\mathfrak{B})$. _Endomorphisms_ are a special case of
polymorphisms with $k=1$: an endomorphism of a structure $\mathfrak{B}$ is
thus a homomorphism from $\mathfrak{B}$ to itself. The set of all
endomorphisms of $\mathfrak{B}$ is denoted by
$\operatorname{End}(\mathfrak{B})$. For every $i\leq n$, the $i$-th projection
of arity $n$ is the operation $\pi^{n}_{i}$ defined by
$\pi^{n}_{i}(x_{1},\dots,x_{n})\coloneqq x_{i}$. The set of all polymorphisms
of a structure $\mathfrak{B}$ forms an _(operation) clone_ : it is closed
under composition and contains all projections. Moreover, an operation clone
$\mathscr{C}$ on a set $B$ is a polymorphism clone of a relational structure
if and only if the operation clone is _closed_ , i.e., for each $k\geq 1$ the
set of $k$-ary operations in $\mathscr{C}$ is closed with respect to the
product topology on $B^{B^{k}}$ where $B$ is taken to be discrete (see, e.g.,
Corollary 6.1.6 in [Bod21]).

An operation clone ${\mathscr{C}}$ is called _oligomorphic_ if the permutation
group ${\mathscr{G}}$ of invertible unary maps in ${\mathscr{C}}$ is
oligomorphic. A relation $R\subseteq B^{n}$ is preserved by all polymorphisms
of an $\omega$-categorical structure $\mathfrak{B}$ if and only if $R$ has a
primitive positive definition in $\mathfrak{B}$ [BN06]. It follows that two
$\omega$-categorical relational structures with the same domain have the same
polymorphisms if and only if they are primitively positively interdefinable.
If ${\mathscr{F}}\subseteq{\mathscr{C}}$, we write

  * •

$\langle{\mathscr{F}}\rangle$ for the smallest subclone of ${\mathscr{C}}$
which contains ${\mathscr{F}}$, and

  * •

$\overline{{\mathscr{F}}}$ for the smallest _(locally, or topologically)
closed_ subset of ${\mathscr{C}}$ that contains ${\mathscr{F}}$: that is,
$\overline{{\mathscr{F}}}$ consists of all operations $f$ such that for every
finite subset $S$ of the domain there exists an operation $g\in{\mathscr{F}}$
which agrees with $f$ on $S$.

If $\sigma\colon\\{1,\dots,n\\}\to\\{1,\dots,k\\}$ and $f\in{\mathscr{C}}$ has
arity $n$, then we write $f_{\sigma}$ for the operation
$f(\pi^{k}_{\sigma(1)},\dots,\pi^{k}_{\sigma(n)})$ which maps
$(x_{1},\ldots,x_{k})$ to $f(x_{\sigma(1)},\dots,x_{\sigma(n)})$. Let
${\mathscr{C}}_{1}$ and ${\mathscr{C}}_{2}$ be two clones and let $\xi$ be a
function from ${\mathscr{C}}_{1}$ to ${\mathscr{C}}_{2}$ that preserves the
arities of the operations. Then $\xi$ is

  * •

a _clone homomorphism_ if for all $f\in{\mathscr{C}}_{1}$ of arity $n$ and
$g_{1},\dots,g_{n}\in{\mathscr{C}}_{1}$ of arity $k$ we have

$\xi(f(g_{1},\dots,g_{n}))=\xi(f)(\xi(g_{1}),\dots,\xi(g_{n}))$

and $\xi(\pi^{n}_{i})=\pi^{n}_{i}$ for all $i\leq n$.

  * •

_minor preserving_ if for all $f\in{\mathscr{C}}_{1}$ of arity $n$ and
$\sigma\colon\\{1,\dots,n\\}\to\\{1,\dots,k\\}$

$\xi(f_{\sigma})=\xi(f)_{\sigma}.$

  * •

_uniformly continuous_ if for every finite subset $F$ of the domain of
${\mathscr{C}}_{2}$ there exists a finite subset $G$ of the domain of
${\mathscr{C}}_{1}$ such that and for every $n\geq 1$ and all
$f,g\in{\mathscr{C}}_{1}$ of arity $n$, if $f|_{G^{n}}=g|_{G^{n}}$, then
$\xi(f)|_{F^{n}}=\xi(g)|_{F^{n}}$.

Note that trivially, every clone homomorphism is minor-preserving. Uniformly
continuous clone homomorphims naturally arise from interpretations.

######  Lemma 10 ([BP15b]).

If $\mathfrak{C}$ has a primitive positive interpretation in $\mathfrak{B}$
then $\operatorname{Pol}(\mathfrak{B})$ has a uniformly continuous clone
homomorphism to $\operatorname{Pol}(\mathfrak{C})$.

The relevance of minor-preserving maps for the complexity of constraint
satisfaction is witnessed by the following theorem.

######  Theorem 11 ([BOP18]).

If $\mathfrak{B}$ is an $\omega$-categorical structure and $\mathfrak{C}$ is a
finite structure, then $\mathfrak{C}$ has a primitive positive construction in
$\mathfrak{B}$ if and only if $\operatorname{Pol}(\mathfrak{B})$ has a
uniformly continuous minor-preserving map to
$\operatorname{Pol}(\mathfrak{C})$.

Note that Theorem 11 in combination with Lemma 9 implies the following.

######  Corollary 12.

Let $\mathfrak{B}$ be an $\omega$-categorical structure and suppose that
$\operatorname{Pol}(\mathfrak{B})$ has a uniformly continuous minor-preserving
map to $\operatorname{Pol}(K_{3})$. Then $\mathfrak{B}$ has a finite-signature
reduct whose $\operatorname{CSP}$ is NP-hard.

The _infinite-domain tractability conjecture_ states that for reducts of
finitely bounded homogeneous structures, and if P $\neq$ NP, then the
condition given in Corollary 12 is not only sufficient, but also necessary for
NP-hardness [BPP21]. Note that $\operatorname{CSP}$s of reducts of finitely
bounded homogeneous structures are always in NP (see, e.g., Proposition 2.3.15
in [Bod21]). The conjecture has also interesting algebraic interpretations in
line with the dichotomy for $\operatorname{CSP}$s of finite structures [BP16,
BKO+19, BOP18]. An operation $f\colon B^{k}\to B$ is called a _weak near
unanimity operation_ if for all $x,y\in B$ the operation $f$ satisfies

$f(y,x,\dots,x)=f(x,y,\dots,x)=\cdots=f(x,\dots,x,y).$

If $\mathscr{C}$ is a clone on a finite domain $B$ without a minor-preserving
map to $\operatorname{Pol}(K_{3})$, then $\mathscr{C}$ contains a weak near
unanimity operation [MM08]. A potential generalisation of this fact to
polymorphism clones of $\omega$-categorical structures $\mathfrak{B}$ involves
the concept of a _pseudo weak near unanimity (pwnu) polymorphism_ , i.e., a
polymorphism $f$ of arity at least two such that there are endomorphisms
$e_{1},\dots,e_{k}$ of $\mathfrak{B}$ such that for all $x,y\in B$

$\displaystyle
e_{1}(f(y,x,\dots,x))=e_{2}(f(x,y,\dots,x))=\cdots=e_{k}(f(x,\dots,x,y)).$ (1)

We note that all of the polynomial-time tractability conditions that we prove
in this article can be phrased in terms of the existence of pwnu
polymorphisms. It is not known whether every polymorphism clone of a reduct of
a finitely bounded homogeneous structure that does not have a uniformly
continuous minor-preserving map to $\operatorname{Pol}(K_{3})$ contains a pwnu
(see Question 21 in [Bod21]). Note that clone homomorphisms preserve
identities such as (1), and it follows from Lemma 10 that first-order
interpretations preserve the existence of pwnu polymorphisms. The same is not
true for minor-preserving maps instead of clone homomorphisms. However, we
have the following; it uses the assumption that
$\overline{\operatorname{Aut}(\mathfrak{B})}=\operatorname{End}(\mathfrak{B})$
which is equivalent to $\mathfrak{B}$ being a _model-complete core_ (see,
e.g., [Bod21, Section 4.5]).

######  Lemma 13.

Let $\mathfrak{C}$ be a homogeneous structure with finite relational signature
and let $\mathfrak{B}$ be a first-order reduct of $\mathfrak{C}$ with a pwnu
polymorphism. If
$\overline{\operatorname{Aut}(\mathfrak{B})}=\operatorname{End}(\mathfrak{B})$,
then $\mathfrak{B}$ does not have a uniformly continuous minor-preserving map
to $\operatorname{Pol}(K_{3})$.

###### Proof.

The assumptions imply that we may apply Corollary 3.6 in [BKO+19]. Hence,
$\mathfrak{B}$ has a uniformly continuous minor-preserving map to
$\operatorname{Pol}(K_{3})$ if and only if there exist $n\in{\mathbb{N}}$ and
$c_{1},\dots,c_{n}\in B$ such that the clone
$\operatorname{Pol}(\mathfrak{B},\\{c_{1}\\},\dots,\\{c_{n}\\})$ has a
continuous clone homomorphism to $\operatorname{Pol}(K_{3})$. But if
$\mathfrak{B}$ has a pwnu polymorphism, then so does every expansion of
$\mathfrak{B}$ by finitely many unary singleton relations (Proposition 10.1.13
in [Bod21]). Since clone homomorphisms preserve the existence of pwnu
polymorphisms and $K_{3}$ does not have such a polymorphism (see, e.g.,
[Bod21, Proposition 6.1.43]), the statement follows. ∎

##  3 Algebraic Products

We devote this section to presenting the algebraic product and for studying
some of its properties: Section 3.1 contains the definition together with some
elementary facts while Section 3.2 describes connections with $i$-determined
clauses (that we introduce in Section 3.1). The algebraic product has been
studied in the past. For instance, Greiner [Gre21] uses it for studying CSPs
of combinations of structures or background theories (a topic we will touch
upon in Section 7), Baader and Rydval [BR20] use it for analysing the
complexity of description logics, and Bodirsky [Bod21] uses it in connection
with Ramsey structures.

###  3.1 Basic Properties

The algebraic product is defined as follows.

######  Definition 14.

Let ${\mathfrak{A}}_{1}$ and ${\mathfrak{A}}_{2}$ be structures with signature
$\tau_{1}$ and $\tau_{2}$, respectively. Then the _algebraic product_
${\mathfrak{A}}_{1}\boxtimes{\mathfrak{A}}_{2}$ is the structure with domain
$A_{1}\times A_{2}$ which has for every atomic $\tau_{1}$-formula
$\phi(x_{1},\dots,x_{k})$ the relation

$\\{((u_{1},v_{1}),\dots,(u_{k},v_{k}))\mid{\mathfrak{A}}_{1}\models\phi(u_{1},\dots,u_{k})\\}$

and analogously for every atomic $\tau_{2}$-formula $\phi$ the relation

$\\{((u_{1},v_{1}),\dots,(u_{k},v_{k}))\mid{\mathfrak{A}}_{2}\models\phi(v_{1},\dots,v_{k})\\}.$

The relation symbol for the atomic $\tau_{i}$-formula $x=y$ will be denoted by
$=_{i}$. Clauses over the signature of
$\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$ where all atomic formulas are
built from symbols that have been introduced for atomic $\tau_{i}$-formulas
are called _$i$ -determined_.

######  Remark 15.

We note that the algebraic product preserves some of the important fundamental
properties of structures. For example, if $\mathfrak{A}_{1}$ and
$\mathfrak{A}_{2}$ are homogeneous, then so is
${\mathfrak{A}}_{1}\boxtimes{\mathfrak{A}}_{2}$ (Proposition 4.2.19 in
[Bod21]), and if $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ are
$\omega$-categorical, then so is
${\mathfrak{A}}_{1}\boxtimes{\mathfrak{A}}_{2}$.

We define the $n$-fold algebraic product
${\mathfrak{A}}_{1}\boxtimes\dots\boxtimes{\mathfrak{A}}_{n}$ in the natural
way together with the $n$-fold algebraic power

$\mathfrak{A}^{(n)}\coloneqq\underbrace{\mathfrak{A}\boxtimes\cdots\boxtimes\mathfrak{A}}_{\mbox{$n$
times}}.$

The forthcoming definitions and statements in this section are presented for
the binary product, but they can easily be generalised to $n$-fold algebraic
products. We continue by studying the polymorphism clone of
${\mathfrak{A}}_{1}\boxtimes{\mathfrak{A}}_{2}$. For $i\in\\{1,2\\}$, let
${\mathscr{C}}_{i}$ be a clone of operations on a set $A_{i}$. If
$f_{1}\in{\mathscr{C}}_{1}$ and $f_{2}\in{\mathscr{C}}_{2}$ both have arity
$k$, then we write $(f_{1},f_{2})$ for the operation on $A_{1}\times A_{2}$
given by

$((a_{1},b_{1}),\dots,(a_{k},b_{k}))\mapsto(f_{1}(a_{1},\dots,a_{k}),f_{2}(b_{1},\dots,b_{k})).$

The _direct product_ ${\mathscr{C}}_{1}\times{\mathscr{C}}_{2}$ of
${\mathscr{C}}_{1}$ and ${\mathscr{C}}_{2}$ is the clone ${\mathscr{D}}$ on
the set $A_{1}\times A_{2}$ whose operations of arity $k$ consist of the set
of all operations $(f_{1},f_{2})$ where $f_{i}\in{\mathscr{C}}_{i}$ is of
arity $k$. Note that this generalises the usual definition of direct products
of permutation groups. If ${\mathscr{C}}_{1}={\mathscr{C}}_{2}={\mathscr{C}}$
then ${\mathscr{D}}$ is called a _direct power_ and we write
${\mathscr{C}}^{2}$ instead of ${\mathscr{C}}\times\mathscr{C}$. Note that the
function
$\theta_{i}\colon{\mathscr{C}}_{1}\times{\mathscr{C}}_{2}\to{\mathscr{C}}_{i}$
given by $(f_{1},f_{2})\mapsto f_{i}$ is a uniformly continuous minor-
preserving map. Also note that if ${\mathscr{C}}_{1}$ and ${\mathscr{C}}_{2}$
are oligomorphic, then so is ${\mathscr{C}}_{1}\times{\mathscr{C}}_{2}$.

The following proposition is one of the important features of the algebraic
product. We present it for two-fold algebraic products but it can obviously be
generalised to the $n$-fold case.

######  Proposition 16.

For all structures $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ we have

$\operatorname{Pol}({\mathfrak{A}}_{1}\boxtimes{\mathfrak{A}}_{2})=\operatorname{Pol}({\mathfrak{A}}_{1})\times\operatorname{Pol}({\mathfrak{A}}_{2}).$

Likewise, we have
$\operatorname{End}(\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2})=\operatorname{End}(\mathfrak{A}_{1})\times\operatorname{End}(\mathfrak{A}_{1})$
and
$\operatorname{Aut}(\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2})=\operatorname{Aut}(\mathfrak{A}_{1})\times\operatorname{Aut}(\mathfrak{A}_{2})$.

###### Proof.

If $f_{i}\in\operatorname{Pol}(\mathfrak{A}_{i})$, for $i\in\\{1,2\\}$, then
clearly $(f_{1},f_{2})$ preserves all relations of
${\mathfrak{A}}_{1}\boxtimes{\mathfrak{A}}_{2}$. Conversely, let
$f\in\operatorname{Pol}({\mathfrak{A}}_{1}\boxtimes{\mathfrak{A}}_{2})$. Pick
$a\in A_{2}$ and define $f_{1}(x_{1},\dots,x_{n})\coloneqq
f((x_{1},a),\dots,(x_{n},a))_{1}$. Since $f$ preserves $=_{1}$, this
definition does not depend on the choice of $a\in A_{2}$. Note that
$f_{1}\in\operatorname{Pol}(\mathfrak{A}_{1})$. The function
$f_{2}\in\operatorname{Pol}(\mathfrak{A}_{2})$ is defined analogously, with
the roles of $1$ and $2$ swapped. Finally, note that $f=(f_{1},f_{2})$. The
statement for endomorphisms and automorphisms of algebraic product structures
is analogous. ∎

Under fairly general assumptions on ${\mathscr{C}}$ it holds that
$\theta_{i}({\mathscr{C}})$, for $i\in\\{1,2\\}$, is closed.

######  Proposition 17.

Let $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ be countable
$\omega$-categorical structures and let
${\mathscr{C}}\subseteq\operatorname{Pol}(\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2})$
be a closed set of operations on $A_{1}\times A_{2}$. If ${\mathscr{C}}$
contains $\alpha f$ for every $f\in{\mathscr{C}}$ and every
$\alpha\in\operatorname{Aut}(\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2})$, then
$\theta_{1}({\mathscr{C}})$ and $\theta_{2}({\mathscr{C}})$ are closed.

###### Proof.

It suffices to show the statement for $i=1$. Let
$f\in\overline{\theta_{1}({\mathscr{C}})}$ be of arity $k$. Fix an enumeration
$p_{0},p_{1},\dots$ of $A_{1}$ and an enumeration $q_{0},q_{1},\dots$ of
$A_{2}$. Then for every $n\in{\mathbb{N}}$ there exists
$g_{n}\in\operatorname{Pol}({\mathscr{C}})$ such that
$\theta_{1}(g_{n})|_{\\{p_{0},\dots,p_{n}\\}^{k}}=f|_{\\{p_{0},\dots,p_{n}\\}^{k}}$.
In the proof we use Kőnig’s tree lemma: if $T$ is a rooted tree with an
infinite number of nodes and each node has a finite number of children, then
$T$ contains a branch of infinite length. To define the tree $T$, let
$S_{n}:=\\{p_{0},\dots,p_{n}\\}\times\\{q_{1},\dots,q_{n}\\}$ and consider the
functions ${\mathcal{F}}\coloneqq\bigcup_{n\in{\mathbb{N}}}{\mathcal{F}}_{n}$
where

${\mathcal{F}}_{n}\coloneqq\\{g_{m}|_{S^{k}_{n}}\mid m\in{\mathbb{N}}\\}.$

For $h_{1},h_{2}\in{\mathcal{F}}$ define $h_{1}\sim h_{2}$ if there exists
$\alpha\in\operatorname{Aut}(\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2})$ such
that $h_{1}=\alpha h_{2}$. The vertices of the tree $T$ that we consider here
are the equivalence classes of the equivalence relation $\sim$. The edges of
$T$ are defined as follows: if $h_{1}\in{\mathcal{F}}_{\ell}$ is the
restriction of $h_{2}\in{\mathcal{F}}_{\ell+1}$, then the equivalence class of
$h_{1}$ and the equivalence class of $h_{2}$ are linked by an edge. Clearly
the tree thus defined is infinite, and by the oligomorphicity of
$\operatorname{Aut}(\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2})$ there are
finitely many $\sim$-classes on ${\mathcal{F}}_{\ell}$, which implies that
each vertex in $T$ has finitely many neighbours. Kőnig’s tree lemma implies
the existence of an infinite path in the tree; using the assumption that
${\mathscr{C}}$ is closed it is straightforward to obtain from the infinite
path an operation $g\in\mathscr{C}$ such that $\theta_{1}(g)=f$. ∎

Another important feature of the algebraic product is that it preserves
certain computational properties.

######  Proposition 18.

For $i\in\\{1,2\\}$, let $\mathfrak{A}_{i}$ be a countable
$\omega$-categorical structure with finite relational signature $\tau_{i}$. If
both $\operatorname{CSP}(\mathfrak{A}_{1})$ and
$\operatorname{CSP}(\mathfrak{A}_{2})$ are in P, then
$\operatorname{CSP}(\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2})$ is in P.

###### Proof.

Without loss of generality, we may assume that the signatures $\tau_{1}$ and
$\tau_{2}$ are disjoint and that $\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$
is a $(\tau_{1}\cup\tau_{2})$-structure. Let $\mathfrak{C}$ be an instance of
$\operatorname{CSP}(\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2})$. For
$i\in\\{1,2\\}$, let $\mathfrak{C}_{i}$ be the $\tau_{i}$-reduct of
$\mathfrak{C}$. For each $i\in\\{1,2\\}$, run an algorithm for
$\operatorname{CSP}(\mathfrak{A}_{i})$ on the input $\mathfrak{C}_{i}$. Accept
the instance $\mathfrak{C}$ if and only if both algorithms accept. ∎

######  Corollary 19.

Let $\mathfrak{A}_{1},\mathfrak{A}_{2},\mathfrak{B}$ be countable
$\omega$-categorical structures with finite relational signature such that
$\operatorname{Pol}(\mathfrak{B})$ contains
$\operatorname{Pol}(\mathfrak{A}_{1})\times\operatorname{Pol}(\mathfrak{A}_{2})$.
If both $\operatorname{CSP}(\mathfrak{A}_{1})$ and
$\operatorname{CSP}(\mathfrak{A}_{2})$ are in P, then
$\operatorname{CSP}(\mathfrak{B})$ is in P, too.

###### Proof.

Since $\operatorname{Pol}(\mathfrak{B})$ contains
$\operatorname{Pol}(\mathfrak{A}_{1})\times\operatorname{Pol}(\mathfrak{A}_{2})=\operatorname{Pol}(\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2})$,
all relations of $\mathfrak{B}$ are primitively positively definable in
$\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$. Hence, there is a polynomial-time
reduction from $\operatorname{CSP}(\mathfrak{B})$ to
$\operatorname{CSP}(\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2})$ by Lemma 3 so
$\operatorname{CSP}(\mathfrak{B})$ is in P by Proposition 18. ∎

We finish this section by a lemma that enables us to use Lemma 13 for first-
order expansions of algebraic products.

######  Lemma 20.

For $i\in\\{1,\dots,n\\}$, let $\mathfrak{A}_{i}$ be a structure such that
$\overline{\operatorname{Aut}(\mathfrak{A}_{i})}=\operatorname{End}(\mathfrak{A}_{i})$.
If $\mathfrak{B}$ is a first-order expansion of
$\mathfrak{A}_{1}\boxtimes\dots\boxtimes\mathfrak{A}_{n}$, then
$\overline{\operatorname{Aut}(\mathfrak{B})}=\operatorname{End}(\mathfrak{B})$.

###### Proof.

Clearly,
$\overline{\operatorname{Aut}(\mathfrak{B})}\subseteq\operatorname{End}(\mathfrak{B})$.
The converse inclusion also holds since

$\displaystyle\operatorname{End}(\mathfrak{B})\subseteq\operatorname{End}(\mathfrak{A}_{1}\boxtimes\dots\boxtimes\mathfrak{A}_{n})$
$\displaystyle=\operatorname{End}(\mathfrak{A}_{1})\times\dots\times\operatorname{End}(\mathfrak{A}_{n})$
(Proposition 16)
$\displaystyle=\overline{\operatorname{Aut}(\mathfrak{A}_{1})}\times\dots\times\overline{\operatorname{Aut}(\mathfrak{A}_{n})}$
$\displaystyle=\overline{\operatorname{Aut}(\mathfrak{A}_{1})\times\dots\times\operatorname{Aut}(\mathfrak{A}_{n})}$
$\displaystyle=\overline{\operatorname{Aut}(\mathfrak{A}_{1}\boxtimes\dots\boxtimes\mathfrak{A}_{n})}$
(Proposition 16) $\displaystyle=\overline{\operatorname{Aut}(\mathfrak{B})}.$

Lemma 20 holds, for instance, for the structure
$(\mathbb{Q};<)\boxtimes(\mathbb{Q};<)$ since
$\overline{\operatorname{Aut}(\mathbb{Q};<)}$ is equal to
$\operatorname{End}(\mathbb{Q};<)$: every endomorphism of $({\mathbb{Q}};<)$
is injective and preserves the complement of $<$, and by the homogeneity of
$(\mathbb{Q};<)$ every restriction of an endomorphism to a finite subset of
$\mathbb{Q}$ can be extended to an automorphism of $(\mathbb{Q};<)$.

###  3.2 $i$-Determined Clauses

In the complexity analysis of first-order expansions of algebraic products
$\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$, we would like to use as much
information about first-order expansions of $\mathfrak{A}_{1}$ and of
$\mathfrak{A}_{2}$ as possible; in this context, $i$-determined clauses are of
particular relevance. In this section we collect several general observations
about definability by (conjunctions of) $i$-determined clauses. Throughout
this section, let $\mathfrak{A}_{i}$ be a $\tau_{i}$-structure for
$i\in\\{1,2\\}$.

We begin by making a definition. If $\phi$ is a conjunction of $i$-determined
clauses over $\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$, then we let
$\hat{\phi}$ denote the $\tau_{i}$-formula obtained from replacing each atomic
formula $R(x_{1},\dots,x_{k})$ by $\psi(x_{1},\dots,x_{k})$ where $\psi$ is
the atomic $\tau_{i}$-formula for which $R$ has been introduced in
$\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$.

######  Lemma 21.

Let $f\in\operatorname{Pol}(\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2})$. A
conjunction of $i$-determined clauses $\phi$ is preserved by $f$ if and only
if $\hat{\phi}$ is preserved by $\theta_{i}(f)$.

###### Proof.

Let $x_{1},\dots,x_{m}$ be the free variables of $\phi$. Let
$((a^{1,1}_{1},a^{1,1}_{2}),\dots,(a^{k,m}_{1},a^{k,m}_{2}))\in(A_{1}\times
A_{2})^{k\times m}$ and let $f$ be of arity $k$. For $j\in\\{1,\dots,k\\}$,
the tuple $((a^{j,1}_{1},a^{j,1}_{2}),\dots,(a^{j,m}_{1},a^{j,m}_{2}))$
satisfies $\phi$ in $\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$ if and only if
$(a^{j,1}_{i},\dots,a^{j,m}_{i})$ satisfies $\hat{\phi}$ in
$\mathfrak{A}_{i}$. Likewise,

$\big{(}f((a^{1,1}_{1},a^{1,1}_{2}),\dots,(a^{k,1}_{1},a^{k,1}_{2})),\dots,f((a^{1,m}_{1},a^{1,m}_{2}),\dots,(a^{k,m}_{1},a^{k,m}_{2}))\big{)}$

satisfies $\phi$ in $\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$ if and only if
$\big{(}\theta_{i}(f)(a^{1,1}_{i},\dots,a^{k,1}_{i}),\dots,\theta_{i}(f)(a^{1,m}_{i},\dots,a^{k,m}_{i})\big{)}$
satisfies $\hat{\phi}$ in $\mathfrak{A}_{i}$. This implies the statement. ∎

We continue by analysing the polymorphisms of first-order expansion of
$\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$ and definability via
$i$-determined clauses. The proof is based on reduced formulas: a quantifier-
free formula $\phi$ in CNF is called reduced if all formulas obtained from
$\phi$ by removing one of the literals from one of the clauses in the formula
are not equivalent to $\phi$. Clearly, every formula is equivalent to a
reduced formula. Reduced formulas $\phi$ have the property that for every
literal in $\phi$ there exists a satisfying assignment for $\phi$ that
satisfies the literal, but satisfies no other literal of the same clause.
Reduced formulas are useful in many contexts and we will encounter them
repeatedly in the sequel.

######  Lemma 22.

Suppose that $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ are structures with
quantifier elimination and let $\mathfrak{B}$ be a first-order expansion of
$\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$. Then, the following are
equivalent.

  1. 1.

Every relation of $\mathfrak{B}$ has a definition by a conjunction of clauses
each of which is either $1$-determined or $2$-determined.

  2. 2.

$\operatorname{Pol}(\mathfrak{B})=\theta_{1}(\operatorname{Pol}(\mathfrak{B}))\times\theta_{2}(\operatorname{Pol}(\mathfrak{B}))$.

  3. 3.

$\operatorname{Pol}(\mathfrak{B})$ contains $(\pi^{2}_{1},\pi^{2}_{2})$.

The implication from 1 to 2 and from 2 to 3 also hold without the assumption
that $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ have quantifier elimination.

###### Proof.

$1\Rightarrow 2$. Clearly,
$\operatorname{Pol}(\mathfrak{B})\subseteq\theta_{1}(\operatorname{Pol}(\mathfrak{B}))\times\theta_{2}(\operatorname{Pol}(\mathfrak{B}))$.
To prove the converse inclusion, let
$g_{1},g_{2}\in\operatorname{Pol}(\mathfrak{B})$ be of arity $k$ and let
$\phi$ be a formula that defines an $m$-ary relation of $\mathfrak{B}$. We
claim that $(\theta_{1}(g_{1}),\theta_{2}(g_{2}))$ preserves $\phi$. Let
$t^{1}=(t^{1}_{1},\dots,t^{1}_{m}),\dots,t^{k}=(t^{k}_{1},\dots,t^{k}_{m})\in
B^{m}$ be tuples that satisfy $\phi$ in $\mathfrak{B}$. Let $\psi$ be a
conjunct of $\phi$; then $\psi$ is $i$-determined, for some $i\in\\{1,2\\}$.
Since $g_{i}\in\operatorname{Pol}(\mathfrak{B})$ we have that
$g_{i}(t^{1},\dots,t^{k})$ satisfies $\psi$. Since for every
$j\in\\{1,\dots,m\\}$ we have

$g_{i}(t^{1}_{j},\dots,t^{k}_{j})_{i}=(\theta_{1}(g_{1}),\theta_{2}(g_{2}))(t^{1}_{j},\dots,t^{k}_{j})_{i}$

and $\psi$ is $i$-determined, we have that
$(\theta_{1}(g_{1}),\theta_{2}(g_{2}))(t^{1},\dots,t^{k})$ satisfies $\psi$ as
well. This implies that $(\theta_{1}(g_{1}),\theta_{2}(g_{2}))$ preserves
$\phi$ and shows that every operation in
$\theta_{1}(\operatorname{Pol}(\mathfrak{B}))\times\theta_{2}(\operatorname{Pol}(\mathfrak{B}))$
is a polymorphism of $\mathfrak{B}$.

$2\Rightarrow 3$. Trivial.

$3\Rightarrow 1$. We show the contrapositive. Arbitrarily choose a relation
$R$ in $\mathfrak{B}$. By assumption, $R$ has a quantifier-free first-order
definition $\phi$ in $\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$ and we may
additionally assume that $\phi$ is written in reduced CNF. Suppose for
contradiction that $\phi$ contains a clause which is neither $1$\- nor
$2$-determined, i.e., a clause $\psi$ that contains a $\tau_{1}$-literal
$\psi_{1}$ and a $\tau_{2}$-literal $\psi_{2}$. By the assumption that $\phi$
is reduced, $\phi$ has for every $i\in\\{1,2\\}$ a satisfying assignment
$\alpha_{i}$ such that $\alpha_{i}$ satisfies $\psi_{i}$ and does not satisfy
all other literals of $\psi$. But then
$x\mapsto(\pi^{2}_{1},\pi^{2}_{2})(\alpha_{2}(x),\alpha_{1}(x))$ satisfies
none of the literals of $\psi$, and hence $(\pi^{2}_{1},\pi^{2}_{2})$ is not
in $\operatorname{Pol}(\mathfrak{B})$. ∎

The final result in this section connects primitive positive definability and
$i$-determined clauses. We will first (in Lemmas 23—25) prove a restricted
result for $\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$ and then extend it to
$n$-fold products $\mathfrak{A}_{1}\boxtimes\dots\boxtimes\mathfrak{A}_{n}$ in
Corollary 26. We use it for defining conjunction replacement and verify its
properties; this concept is important in our algorithmic results (see
Propositions 58 and 63). The proof exploits the so-called _wreath product_ ,
which is a central group-theoretic construction. Let us denote
$\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$ by $\mathfrak{A}$. The wreath
product will be used for concisely describing the automorphism group of
$\mathfrak{A}^{*j}$, where $\mathfrak{A}^{*j}$, $j\in\\{1,2\\}$, denotes the
structure with domain $A_{1}\times A_{2}$ that contains all relations that are
defined by a $j$-determined clause. If $G$ is a permutation group on $A_{1}$
and $H$ is a permutation group on $A_{2}$, then the _action of the
(unrestricted) wreath product $G\ltimes H^{A_{1}}$ on $A_{1}\times A_{2}$_ is
the permutation group

$\\{(a_{1},a_{2})\mapsto(\alpha(a_{1}),\beta_{a_{1}}(a_{2}))\mid\alpha\in
G,\beta_{a_{1}}\in H\text{ for every }a_{1}\in A_{1}\\}.$

######  Lemma 23.

For any structures $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$, let
$\mathfrak{A}$ denote $\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$. Then it
holds that

$\operatorname{Aut}(\mathfrak{A}^{*1})=\operatorname{Aut}(\mathfrak{A}_{1})\ltimes\operatorname{Sym}(A_{2})^{A_{1}}$

and if $\mathfrak{A}_{1}$ is homogeneous then so is $\mathfrak{A}^{*1}$. The
analogous statements hold for $\mathfrak{A}^{*2}$.

###### Proof.

To show that
$\operatorname{Aut}(\mathfrak{A}_{1})\ltimes\operatorname{Sym}(A_{2})^{A_{1}}\subseteq\operatorname{Aut}(\mathfrak{A}^{*1})$,
let $\psi(x_{1},\dots,x_{m})$ be a 1-determined clause and let
$((s_{1},t_{1}),\dots,(s_{m},t_{m}))$ be a tuple that satisfies $\psi$; i.e.,
there exists an atomic $\tau_{1}$-formula $\phi$ such that
$(s_{1},\dots,s_{m})$ satisfies $\phi$. For
$\alpha\in\operatorname{Aut}(\mathfrak{A}_{1})$ and
$\beta_{s_{1}},\dots,\beta_{s_{m}}\in\operatorname{Sym}(A_{2})$, note that

$((\alpha(s_{1}),\beta_{s_{1}}(t_{1})),\dots,(\alpha(s_{m}),\beta_{s_{m}}(t_{m})))$

satisfies $\psi$ since $(\alpha(s_{1}),\dots,\alpha(s_{m}))$ satisfies $\phi$.

To show that
$\operatorname{Aut}(\mathfrak{A}^{*1})\subseteq\operatorname{Aut}(\mathfrak{A}_{1})\ltimes\operatorname{Sym}(A_{2})^{A_{1}}$,
let $\gamma\in\operatorname{Aut}(\mathfrak{A}^{*1})$. Arbitrarily fix $t\in
A_{2}$. The operation $\gamma$ preserves $=_{1}$ so the operation $\alpha$
defined by $s\mapsto\gamma((s,t))_{1}$ is well-defined and it is an
automorphism of $\mathfrak{A}_{1}$. The operation $\gamma$ is bijective so for
every $s\in A_{1}$, the map $\beta_{s}$ defined by $t\mapsto\gamma(s,t)_{2}$
is a member of $\operatorname{Sym}(A_{2})$. Since $\gamma$ equals the map that
sends $(s,t)$ to $(\alpha(s),\beta_{s}(t))$, this shows that
$\gamma\in\operatorname{Aut}(\mathfrak{A}_{1})\ltimes\operatorname{Sym}(A_{2})^{A_{1}}$.

Now suppose that $\mathfrak{A}_{1}$ is homogeneous. Let $\alpha$ be an
isomorphism between $m$-element substructures of $\mathfrak{A}_{1}^{*1}$ that
maps $(s_{j},t_{j})$ to $(s_{j}^{\prime},t^{\prime}_{j})$ for
$j\in\\{1,\dots,m\\}$ and $m\in{\mathbb{N}}$. Note that if $s_{j}=s_{k}$, then
$s_{j}^{\prime}=s_{k}^{\prime}$ because $\alpha$ must preserve the relation
$=_{1}$. Hence, the map $\alpha_{1}$ that sends $s_{j}$ to $s_{j}^{\prime}$ is
a well-defined map between finite subsets of $A_{1}$. Moreover, since $\alpha$
preserves all $i$-determined clauses, the map $\alpha_{1}$ is in fact an
isomorphism between finite substructures of $\mathfrak{A}_{1}$, and hence can
be extended to an automorphism $\beta$ of $\mathfrak{A}_{1}$ by the
homogeneity of $\mathfrak{A}_{1}$. Note that if $p,q$ are distinct and
$s_{p}\neq s_{q}$, then $\alpha(s_{p},t_{p})\neq\alpha(s_{q},t_{q})$, because
$\alpha$ is injective. Hence, for each $s$ in the domain of $\alpha_{1}$ we
may fix a bijection $\gamma_{s}$ of $A_{2}$ such that
$\alpha(s,t^{\prime})=(\beta(s),\gamma_{s}(t^{\prime}))$ for all $t^{\prime}$
such that $(s,t^{\prime})$ lies in the domain of $\alpha$. For all other $s\in
A_{1}$ we may define $\gamma_{s}$ to be the identity. Then the map that sends
$(a,b)$ to $(\beta(a),\gamma_{a}(b))\in\operatorname{Aut}(\mathfrak{A}^{*1})$
extends $\alpha$. We conclude that $\mathfrak{A}^{*1}$ is homogeneous. ∎

######  Lemma 24.

Assume that $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ are countable,
homogeneous, and $\omega$-categorical. A relation $R$ can be defined by a
conjunction of $1$-determined clauses over
$\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$ if and only if it is preserved by
the wreath product

$\operatorname{Aut}(\mathfrak{A}_{1})\ltimes\operatorname{Sym}(A_{2})^{A_{1}}$

in its action on $A_{1}\times A_{2}$; the analogous characterisation holds for
clauses that are $2$-determined.

###### Proof.

The forward implication is an immediate consequence of Lemma 23. Conversely,
suppose that $R$ is preserved by
$\operatorname{Aut}(\mathfrak{A}_{1})\ltimes\operatorname{Sym}(A_{2})^{A_{1}}$.
Recall that
$\operatorname{Aut}(\mathfrak{A}^{*1})=\operatorname{Aut}(\mathfrak{A}_{1})\ltimes\operatorname{Sym}(A_{2})^{A_{1}}$
by Lemma 23. The structure $\mathfrak{A}_{1}$ is homogeneous by assumption so
$\mathfrak{A}^{*1}$ is homogeneous, too. We have assumed that
$\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ are $\omega$-categorical so
$\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$ is $\omega$-categorical by Remark
15. Consequently, $\mathfrak{A}^{*1}$ is $\omega$-categorical since it is a
first-order reduct of $\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$. It follows
that $R$ is first-order definable in $\mathfrak{A}^{*1}$, and even has a
quantifier-free definition because $\mathfrak{A}^{*1}$ is homogeneous. This
implies that $R$ can be defined by a conjunction of $1$-determined clauses
over $\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$. ∎

######  Lemma 25.

Assume the following:

  1. 1.

$\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ are countable, homogeneous, and
$\omega$-categorical,

  2. 2.

$\mathfrak{B}$ is a first-order expansion of
$\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$, and

  3. 3.

$\phi_{1}\wedge\phi_{2}$ is a formula that defines a relation $R$ over
$\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$ such that for some
$i\in\\{1,2\\}$, the formula $\phi_{1}$ is a conjunction of $i$-determined
clauses and such that $R$ is primitively positively definable over
$\mathfrak{B}$.

Then there exists a conjunction $\psi_{1}$ of $i$-determined clauses which is
equivalent to a primitive positive formula over $\mathfrak{B}$ such that
$\psi_{1}\wedge\phi_{2}$ still defines $R$ over
$\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$.

###### Proof.

We prove the statement for $i=1$; the statement for $i=2$ can be proved
analogously. Let $\psi(x_{1},\dots,x_{m})$ be the formula

$\exists
y_{1},\dots,y_{m}\left(R(y_{1},\dots,y_{m})\wedge\bigwedge_{j\in\\{1,\dots,m\\}}x_{j}=_{1}y_{j}\right).$

We first show that the relation $S$ defined by $\psi$ over $\mathfrak{B}$ can
be defined by a conjunction of $i$-determined clauses over
$\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$. We use Lemma 24. Let
$((a^{1}_{1},a^{1}_{2}),\dots,(a^{m}_{1},a^{m}_{2}))\in S$, let
$\alpha\in\operatorname{Aut}(\mathfrak{A}_{1})$, and let
$\pi_{1},\dots,\pi_{m}\in\operatorname{Sym}(A_{2})$ be such that
$\pi_{p}=\pi_{q}$ whenever $a^{p}_{1}=a^{q}_{1}$ for $p,q\in\\{1,\dots,m\\}$.
We have to show that

$t:=\big{(}(\alpha(a^{1}_{1}),\pi_{1}(a^{1}_{2})),\dots,(\alpha(a^{m}_{1}),\pi_{m}(a^{m}_{2}))\big{)}$

satisfies $\psi$ as well. Let $(b^{1}_{1},b^{1}_{2})$, …,
$(b^{m}_{1},b^{m}_{2})\in B$ be the witnesses from $B$ for the existentially
quantified variables of $\psi$ that show that $\psi$ holds for
$((a^{1}_{1},a^{1}_{2}),\dots,(a^{m}_{1},a^{m}_{2}))$. Then the tuple
$((\alpha(b^{1}_{1}),b^{1}_{2}),\dots,(\alpha(b^{m}_{1}),b^{m}_{2}))$ provides
witnesses that show that the same formula holds for $t$:

  * •

$R((\alpha(b^{1}_{1}),b^{1}_{2}),\dots,(\alpha(b^{m}_{1}),b^{m}_{2}))$ holds
in $\mathfrak{B}$ because
$R((b^{1}_{1},b^{1}_{2}),\dots,(b^{m}_{1},b^{m}_{2}))$ holds in $\mathfrak{B}$
and $(\alpha,\operatorname{id})\in\operatorname{Aut}(\mathfrak{B})$, and

  * •

$(\alpha(a^{j}_{1}),\pi(a^{j}_{2}))=_{1}(\alpha(b^{j}_{1}),b^{j}_{2})$ holds
for every $j\in\\{1,\dots,m\\}$ because
$(a^{j}_{1},a^{j}_{2})=_{1}(b^{j}_{1},b^{j}_{2})$.

Lemma 24 shows that there exists a conjunction $\psi_{1}$ of $1$-determined
clauses that is equivalent to $\psi$. Clearly, $\psi_{1}$ implies $\phi_{1}$
(since $\phi_{1}$ is $1$-determined), so $\psi_{1}\wedge\phi_{2}$ defines $R$
in $\mathfrak{B}$ and this concludes the proof. ∎

We continue by generalising the previous lemma to algebraic products involving
more than two structures. To this end, we need a particular notion that
generalizes $i$-determined clauses. Let $S\subseteq\\{1,\dots,n\\}$. A clause
over $\mathfrak{A}_{1}\boxtimes\dots\boxtimes\mathfrak{A}_{n}$ is called _$S$
-determined_ if all atomic formulas in the clause are built from symbols that
have been introduced for atomic $\tau_{i}$-formulas for some $i\in S$.

######  Corollary 26.

Assume the following:

  1. 1.

$\mathfrak{A}_{1},\dots,\mathfrak{A}_{n}$ are countable, homogeneous, and
$\omega$-categorical,

  2. 2.

$\mathfrak{B}$ is a first-order expansion of
$\mathfrak{A}_{1}\boxtimes\dots\boxtimes\mathfrak{A}_{n}$, and

  3. 3.

$\phi_{1}\wedge\phi_{2}$ is a formula that defines a relation $R$ over
$\mathfrak{A}_{1}\boxtimes\dots\boxtimes\mathfrak{A}_{n}$ such that for some
$S\subseteq\\{1,\dots,n\\}$, the formula $\phi_{1}$ is a conjunction of
$S$-determined clauses and such that $R$ is primitively positively definable
over $\mathfrak{B}$.

Then there exists a conjunction $\psi_{1}$ of $S$-determined clauses which is
equivalent to a primitive positive formula over $\mathfrak{B}$ such that
$\psi_{1}\wedge\phi_{2}$ still defines $R$ over
$\mathfrak{A}_{1}\boxtimes\dots\boxtimes\mathfrak{A}_{n}$.

###### Proof.

Assume without loss of generality that $S=\\{1,\dots,p\\}$ for some $p\geq 1$.
We can view the $n$-fold product
$\mathfrak{A}_{1}\boxtimes\dots\boxtimes\mathfrak{A}_{n}$ as
$\mathfrak{B}_{1}\boxtimes\mathfrak{B}_{2}$, where
$\mathfrak{B}_{1}=\mathfrak{A}_{1}\boxtimes\dots\boxtimes\mathfrak{A}_{p}$ and
$\mathfrak{B}_{2}=\mathfrak{A}_{p+1}\boxtimes\dots\boxtimes\mathfrak{A}_{n}$.
Note that $\phi_{1}$ is a conjunction of $1$-determined clauses when
considered as a formula over $\mathfrak{B}_{1}\boxtimes\mathfrak{B}_{2}$. By
Lemma 25, there exists a conjunction $\psi_{1}$ of $1$-determined clauses
which is equivalent to a primitive positive formula over $\mathfrak{B}$ such
that $\psi_{1}\wedge\phi_{2}$ still defines $R$. Since $\psi_{1}$ is
$S$-determined when viewed as a formula over
$\mathfrak{A}_{1}\boxtimes\dots\boxtimes\mathfrak{A}_{n}$, the claim follows.
∎

Let $\mathfrak{A}_{1},\dots\mathfrak{A}_{n}$, $\mathfrak{B}$, $S$, and
$\phi=\phi_{1}\wedge\phi_{2}$ be as in the statement of Corollary 26.
Arbitrarily choose a conjunction $\psi_{1}$ of $S$-determined clauses
equivalent to a primitive positive formula over $\mathfrak{B}$ such that
$\psi_{1}\wedge\phi_{2}$ is equivalent to $\phi$. Note that the existence of
$\psi_{1}$ follows from the corollary. We denote the formula $\psi_{1}$ by
$\operatorname{cr}(\phi,S,\phi_{1})$, where $\operatorname{cr}$ stands for
conjunction replacement.

##  4 Algebraic Powers of $({\mathbb{Q}};<)$

In this section we classify the complexity of the CSP for every first-order
expansion of the structure $({\mathbb{Q}};<)^{(n)}$. We only consider the case
when $n=2$ in Sections 4.2—4.5. This leads to a more intuitive and easily
understandable presentation which we can quite easily generalise to arbitrary
$n\geq 2$ in Section 4.6. We begin by recapitulating some known results
concerning first-order expansions of $({\mathbb{Q}};<)$ in Section 4.1. We
continue by studying the polymorphisms of
$({\mathbb{Q}};<)\boxtimes({\mathbb{Q}};<)$ (Section 4.2), we present
syntactic normal forms of certain relations that are first-order definable in
$({\mathbb{Q}};<)\boxtimes({\mathbb{Q}};<)$ (Section 4.3), and we introduce
polynomial-time algorithms for first-order expansions of
$({\mathbb{Q}};<)\boxtimes({\mathbb{Q}};<)$ (Section 4.4). These results are
combined in Section 4.5 where we classify the complexity of the CSP for every
first-order expansion of $({\mathbb{Q}};<)\boxtimes({\mathbb{Q}};<)$. We
continue by generalising our results from binary products to $n$-fold powers
$({\mathbb{Q}};<)^{(n)}$ (Section 4.6), and finally specialise our results to
binary signatures (Section 4.7).

Recall that
$({\mathbb{Q}};<)\boxtimes({\mathbb{Q}};<)=({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$
is $\omega$-categorical and homogeneous (Remark 15), and therefore has
quantifier elimination. From here until Section 4.5, we let the symbol
$\mathfrak{D}$ denote a first-order expansion of
$({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$.

###  4.1 First-order Expansions of $({\mathbb{Q}};<)$

Let $\mathfrak{B}$ be a first-order reduct of $({\mathbb{Q}};<)$ with a finite
relational signature. The complexity of CSP$(\mathfrak{B})$ for all choices of
$\mathfrak{B}$ has been determined by Bodirsky and Kára [BK09]. For our
purposes, it is sufficient to understand the complexity of all first-order
expansions of $({\mathbb{Q}};<)$ with a finite relational structure. We next
present first-order expansions of $({\mathbb{Q}};<)$ with a polynomial-time
solvable CSP, we describe some of their polymorphisms, and how the relations
can be described with syntactically restricted definitions. We make use of
relational and functional dualities to simplify the presentation.

######  Definition 27.

The _dual_ of a relation $R\subseteq\mathbb{Q}^{k}$ is the relation

$R^{*}\coloneqq\\{(-x_{1},\dots,-x_{k})\mid(x_{1},\dots,x_{k})\in R\\}.$

If $\mathfrak{B}$ is a relational structure with domain $\mathbb{Q}$, then the
_dual_ of $\mathfrak{B}$ is the structure with domain $\mathbb{Q}$ and the
same signature $\tau$ as $\mathfrak{B}$ where $R\in\tau$ denotes
$(R^{\mathfrak{B}})^{*}$. Similarly, if
$f\colon{\mathbb{Q}}^{n}\to{\mathbb{Q}}$ is an operation, then the _dual_ of
$f$ is the operation $f^{*}$ defined as follows.

$(x_{1},\dots,x_{n})\mapsto-f(-x_{1},\dots,-x_{n})$

If ${\mathscr{C}}$ is a operation clone on ${\mathbb{Q}}$, then the _dual_ of
${\mathscr{C}}$ is the operation clone ${\mathscr{C}}^{*}\coloneqq\\{f^{*}\mid
f\in{\mathscr{C}}\\}.$

Now, consider the following first-order expansions of $({\mathbb{Q}};<)$.

  * •

$\mathfrak{U}\coloneqq(\mathbb{Q};<,R^{\min}_{\leq})$ where
$R^{\min}_{\leq}\coloneqq\\{(x,y,z)\in{\mathbb{Q}}^{3}\mid y\leq x\;{\rm
or}\;z\leq x\\}$.

  * •

$\mathfrak{X}\coloneqq(\mathbb{Q};<,X)$ where
$X\coloneqq\\{(x,y,z)\in{\mathbb{Q}}^{3}\mid x=y<z\;{\rm or}\;y=z<x\;{\rm
or}\;z=x<y\\}$

  * •

$\mathfrak{I}\coloneqq(\mathbb{Q};<,R^{\operatorname{mi}},S^{\operatorname{mi}})$
where

$\displaystyle R^{\operatorname{mi}}$
$\displaystyle\coloneqq\\{(x,y,z)\in{\mathbb{Q}}^{3}\mid y\leq x\;{\rm
or}\;z<x\\}\;{\rm and}$ $\displaystyle S^{\operatorname{mi}}$
$\displaystyle\coloneqq\\{(x,y,z)\in{\mathbb{Q}}^{3}\mid y\neq x\;{\rm
or}\;z\leq x\\}.$

  * •

$\mathfrak{L}\coloneqq(\mathbb{Q};<,L,I_{4})$ where

$\displaystyle L$ $\displaystyle\coloneqq\\{(x,y,z)\in{\mathbb{Q}}^{3}\mid
y<x\;{\rm or}\;z<x\;{\rm or}\;x=y=z\\}\;{\rm and}$ $\displaystyle I_{4}$
$\displaystyle\coloneqq\\{(x,y,u,v)\in\mathbb{Q}^{4}\mid x=y\;{\rm
implies}\;u=v\\}.$

We need the following characterisation of primitive positive definability in
these structures in terms of certain polymorphisms. The precise definition of
these operations can be found in [BPR20] but it is not needed in this article;
the properties stated in the next proposition suffice for our purposes.

######  Theorem 28 (Proposition 7.27 in [BPR20]).

For every $k\geq 3$ there are pseudo weak near unanimity polymorphisms
$\min_{k},\operatorname{mx}_{k},\operatorname{mi}_{k},\operatorname{ll}_{k}$
of arity $k$ such that a relation $R\subseteq{\mathbb{Q}}^{m}$ is preserved by
$\min_{k}$ ($\operatorname{mx}_{k}$, $\operatorname{mi}_{k}$,
$\operatorname{ll}_{k}$) and $\operatorname{Aut}({\mathbb{Q}};<)$ if and only
if $R$ has a primitive positive definition in $\mathfrak{U}$ ($\mathfrak{X}$,
$\mathfrak{I}$, $\mathfrak{L}$). The operation $\operatorname{ll}_{k}$ is
injective.

The following result is essentially taken from [BK09] but we formulate it
differently with the aid of polymorphisms.

######  Theorem 29 (Theorem 12.0.1 in [Bod21]).

Let $\mathfrak{B}$ be a first-order expansion of $(\mathbb{Q};<)$. Then
exactly one of the following two cases applies.

  1. 1.

$\mathfrak{B}$ is preserved by the operation $\min_{3}$,
$\operatorname{mx}_{3}$, $\operatorname{mi}_{3}$, or $\operatorname{ll}_{3}$
from Theorem 28, or the dual of one of these operations. In this case, the CSP
of every finite-signature reduct of $\mathfrak{B}$ is in P.

  2. 2.

$\operatorname{Pol}(\mathfrak{B})$ has a uniformly continuous minor-preserving
map to $\operatorname{Pol}(K_{3})$. In this case, $\mathfrak{B}$ has a finite-
signature reduct whose CSP is NP-complete.

Theorem 29 immediately connects first-order expansions of $(\mathbb{Q};<)$
with the infinite-domain tractability conjecture from Section 2.3.

We now describe polymorphisms and syntactic normal forms of the structures
that were described earlier. Clearly, an operation $f$ preserves a relation
$R\subseteq\mathbb{Q}^{k}$ if and only if $f^{*}$ preserves $R^{*}$ so we can
concentrate on the structures $\mathfrak{U}$, $\mathfrak{X}$, $\mathfrak{I}$,
and $\mathfrak{L}$. We start by considering polymorphisms of the structures
$\mathfrak{U}$, $\mathfrak{X}$, and $\mathfrak{I}$.

######  Definition 30.

A binary operation $f$ on ${\mathbb{Q}}$ is called a _$\operatorname{pp}$
-operation_ if $f(a,b)\leq f(a^{\prime},b^{\prime})$ if and only if

  1. 1.

$a\leq 0$ and $a\leq a^{\prime}$, or

  2. 2.

$0<a$, $0<a^{\prime}$, and $b\leq b^{\prime}$.

######  Remark 31.

Note that if $f,g\colon{\mathbb{Q}}^{k}\to{\mathbb{Q}}$ are such that for all
$a,b\in{\mathbb{Q}}^{k}$ we have $f(a)\leq f(b)\Leftrightarrow g(a)\leq g(b)$,
then a relation $R$ which is first-order definable in $({\mathbb{Q}};<)$ is
preserved by $f$ if and only if it is preserved by $g$. To see this, suppose
that $R$ is of arity $k$ and $a^{1},\dots,a^{k}\in R$. Then $s\coloneqq
f(a^{1},\dots,a^{k})$ and $t\coloneqq g(a^{1},\dots,a^{k})$ satisfy the same
atomic formulas over $({\mathbb{Q}};<)$, and hence by the homogeneity of
$({\mathbb{Q}};<)$ there exists $\alpha\in\operatorname{Aut}({\mathbb{Q}};<)$
which maps $s$ to $t$, and since $R$ is first-order definable over
$({\mathbb{Q}};<)$ either both $s$ and $t$ lie in $R$ or none of them lies in
$R$. In particular, $R$ is preserved by a $\operatorname{pp}$-operation if and
only if it is preserved by all $\operatorname{pp}$-operations.

######  Proposition 32 ([BK09]).

Each of the structures $\mathfrak{U}$, $\mathfrak{X}$, and $\mathfrak{I}$ is
preserved by a $\operatorname{pp}$-operation. Equivalently, if a relation
$R\subseteq\mathbb{Q}^{k}$ with a first-order definition in $(\mathbb{Q};<)$
is preserved by $\min_{3}$, $\operatorname{mx}_{3}$ or
$\operatorname{mi}_{3}$, then it is preserved by a
$\operatorname{pp}$-operation.

One should note that if a structure $\mathfrak{B}$ is preserved by a
$\operatorname{pp}$-operation, then this does not imply that
$\operatorname{CSP}(\mathfrak{B})$ is polynomial-time solvable. It does,
however, imply that the relations in $\mathfrak{B}$ can be defined via a
restricted form of definitions.

######  Theorem 33 (Theorem 4 in [BCW14]).

Let $R\subseteq{\mathbb{Q}}^{k}$ be a relation with a first-order definition
in $({\mathbb{Q}};<)$. Then the following are equivalent.

  * •

$R$ is preserved by a (equivalently: every) $\operatorname{pp}$-operation.

  * •

$R$ has a definition by a conjunction of clauses of the form

$y_{1}\neq x\vee\cdots\vee y_{k}\neq x\vee z_{1}\leq x\vee\cdots\vee z_{l}\leq
x$

where it is permitted that $l=0$ or $k=0$.

We conclude this section by another characterisation of $\mathfrak{L}$ via
polymorphisms and presenting a syntactic normal form.

######  Definition 34.

A binary operation $f$ on $\mathbb{Q}$ is called an _$\operatorname{ll}$
-operation_ if $f(a,b)<f(a^{\prime},b^{\prime})$ if and only if

  1. 1.

$a\leq 0$ and $a<a^{\prime}$, or

  2. 2.

$a\leq 0$ and $a=a^{\prime}$ and $b<b^{\prime}$, or

  3. 3.

$a,a^{\prime}>0$ and $b<b^{\prime}$, or

  4. 4.

$a>0$ and $b=b^{\prime}$ and $a<a^{\prime}$.

Note that every $\operatorname{ll}$-operation is injective; this fact will be
important in some of the forthcoming proofs.

######  Definition 35.

A formula is an _ll-Horn clause_ if it is of the form

$x_{1}\neq y_{1}\vee\cdots\vee x_{m}\neq y_{m}\vee z_{1}<z_{0}\vee\cdots\vee
z_{\ell}<z_{0}\vee(z_{0}=z_{1}=\cdots=z_{\ell})$

where it is permitted that $l=0$ or $m=0$, and the final disjunct may be
omitted.

We also need _lexicographic operations_ in order to formulate the final
theorem of this section.

######  Definition 36.

A binary operation $f$ on $\mathbb{Q}$ is called a _$\operatorname{lex}$
-operation_ if $f(a,b)<f(a^{\prime},b^{\prime})$ if and only if

  * •

$a<a^{\prime}$, or

  * •

$a=a^{\prime}$ and $b<b^{\prime}$.

It is called a _twisted $\operatorname{lex}$-operation_ if $f(a,-b)$ is a
$\operatorname{lex}$-operation.

######  Remark 37.

Every relation $R\subseteq{\mathbb{Q}}^{k}$ with a first-order definition in
$({\mathbb{Q}};<)$ that is preserved by an $\operatorname{ll}$-operation is
also preserved by all $\operatorname{lex}$-operations.

######  Theorem 38 ([BK10] and [Mot14]; also see Theorem 12.7.3 and Lemma
12.4.4 in [Bod21]).

Let $R\subseteq\mathbb{Q}^{k}$ be a relation with a first-order definition in
$(\mathbb{Q};<)$. Then the following are equivalent.

  * •

$R$ has a primitive positive definition in $\mathfrak{L}$.

  * •

$R$ is preserved by an (equivalently: every) $\operatorname{ll}$-operation.

  * •

$R$ is preserved by $\operatorname{ll}_{k}$ (from Theorem 28) for some
(equivalently: for all) $k\geq 3$.

  * •

$R$ has a definition by a conjunction of ll-Horn clauses.

Moreover, if $R$ is preserved by a $\operatorname{pp}$-operation and by a
$\operatorname{lex}$-operation, then $R$ is preserved by an
$\operatorname{ll}$-operation.

###  4.2 Polymorphisms

We will now analyse the polymorphism clones of first-order expansions of of
$({\mathbb{Q}};<)\boxtimes({\mathbb{Q}};<)$. This involves a study of
_canonical functions_ (see, e.g., [BP21]) in the product setting.

Let $G$ be a permutation group on a set $A$ and let $H$ be a permutation group
on a set $B$. A function $f\colon A\to B$ is called _canonical with respect to
$(G,H)$_ if for every $m\in{\mathbb{N}}$, $t\in A^{m}$, and $\alpha\in G$
there exists a $\beta\in H$ such that $f\alpha(t)=\beta f(t)$ (where functions
are applied to tuples componentwise). If $f$ is canonical with respect to
$(\operatorname{Aut}(\mathfrak{A})^{n},\operatorname{Aut}(\mathfrak{A}))$ for
some $n\in{\mathbb{N}}$, then we say that $f$ is _canonical over
$\operatorname{Aut}(\mathfrak{A})$_. In other words, $f$ is canonical over
$\operatorname{Aut}(\mathfrak{A})$ if and only if for every $m\in{\mathbb{N}}$
and all $t_{1},\dots,t_{n}\in A^{m}$ the orbit of $f(t_{1},\dots,t_{n})$ in
$\operatorname{Aut}(\mathfrak{A})$ only depends on the orbits of
$t_{1},\dots,t_{n}$ in $\operatorname{Aut}(\mathfrak{A})$. Note that if
$\mathfrak{B}=\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}$, then an operation
$f$ is canonical over $\operatorname{Aut}(\mathfrak{B})$ if $\theta_{1}(f)$ is
canonical over $\mathfrak{A}_{1}$ and $\theta_{2}(f)$ is canonical over
$\mathfrak{A}_{2}$.

An automorphism group $G$ of a structure $\mathfrak{A}$ is called _extremely
amenable_ if every continuous action of $G$ on a compact Hausdorff space has a
fixed point. The reader need not be familiar with this notion since it will
only be used in a black-box fashion via Theorem 39 below; we refer the
interested reader to [KPT05]. A fundamental example of a structure with an
extremely amenable automorphism group is $({\mathbb{Q}};<)$. Moreover, direct
products of extremely amenable groups are extremely amenable [KPT05].

######  Theorem 39 (see, e.g., [BPT13, BP21]).

Let $G$ be an extremely amenable permutation group on a set $A$, let $H$ be an
oligomorphic permutation group on a set $B$, and let $f\colon A\to B$ be a
function. Then

$\overline{\\{\beta f\alpha\mid\alpha\in G,\beta\in H\\}}$

contains a canonical function with respect to $(G,H)$.

The following result will be useful later on when we analyse the polymorphisms
of first-order expansions of powers of $({\mathbb{Q}};<)$. If $f$ is an
operation of arity $k$ and $\alpha_{1},\dots,\alpha_{n}$ are unary operations,
then we write $f(\alpha_{1},\dots,\alpha_{n})$ to denote the function
$(x_{1},\dots,x_{n})\mapsto f(\alpha_{1}(x_{1}),\dots,\alpha_{n}(x_{n}))$. Let
$A$ and $B$ be sets and let $G$ be a permutation group on $A$. We define

$G(B)\coloneqq\\{(\alpha,\operatorname{id}_{B})\mid\alpha\in G\\}\subseteq
G\times\operatorname{Sym}(B).$

######  Lemma 40.

Let $\mathfrak{A}_{1},\mathfrak{A}_{2}$ be $\omega$-categorical structures
such that $\operatorname{Aut}(\mathfrak{A}_{1})$ is extremely amenable and
assume $f\in\operatorname{Pol}(\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2})$ has
arity $n$. Then, the set

$\mathscr{C}\coloneqq\overline{\\{\alpha_{0}f(\alpha_{1},\dots,\alpha_{n})\mid\alpha_{0}\in\operatorname{Aut}(\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2}),\;\alpha_{j}\in\operatorname{Aut}(\mathfrak{A}_{1})(A_{2})\text{
for all }j=1,2,\dots,n\\}}$

contains an operation $g$ such that $\theta_{1}(g)$ is canonical over
$\operatorname{Aut}(\mathfrak{A}_{1})$, and $\theta_{2}(g)=\theta_{2}(f)$. The
symmetric statement holds if the roles of $\mathfrak{A}_{1}$ and
$\mathfrak{A}_{2}$ are exchanged.

###### Proof.

By Theorem 39 there exists an operation

$g^{\prime\prime}\in\overline{\\{\alpha_{0}\theta_{1}(f)(\alpha_{1},\dots,\alpha_{n})\mid\alpha_{0},\alpha_{1},\dots,\alpha_{n}\in\operatorname{Aut}(\mathfrak{A}_{1})\\}}$

which is canonical over $\operatorname{Aut}(\mathfrak{A}_{1})$. By Proposition
17, there exists $g^{\prime}\in\mathscr{C}$ such that
$\theta_{1}(g^{\prime})=g^{\prime\prime}$. Arbitrarily choose
$a^{1},\dots,a^{k}$ in $A_{2}^{n}$. The definition of $\mathscr{C}$ implies
that there is an automorphism
$\alpha\in\operatorname{Aut}(\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2})$ such
that $\theta_{2}(g^{\prime})(a^{i})=\theta_{2}(\alpha)\theta_{2}(f)(a^{i})$
for $i=1,\dots,k$, which we can rewrite as
$\theta_{2}(\alpha^{-1})\theta_{2}(g^{\prime})(a^{i})=\theta_{2}(f)(a^{i})$.
This shows that
$\theta_{2}(f)\in\overline{\\{\beta\theta_{2}(g^{\prime})\mid\beta\in\operatorname{Aut}(\mathfrak{A}_{2})\\}}$.
Let $S:=\overline{\\{\gamma
g^{\prime}\mid\gamma\in\operatorname{Aut}(\mathfrak{A}_{1}\boxtimes\mathfrak{A}_{2})\\}}$.
Note that $\theta_{2}(S)$ contains
$\\{\beta\theta_{2}(g^{\prime})\mid\beta\in\operatorname{Aut}(\mathfrak{A}_{2})\\}$
so $\overline{\theta_{2}(S)}$ contains $\theta_{2}(f)$. Applying Proposition
17 to the set $S$ implies that $\theta_{2}(S)$ is closed. Hence, there exists
$g\in S$ such that $\theta_{2}(g)=\theta_{2}(f)$. Also note that
$\theta_{1}(g)$ is canonical over $\operatorname{Aut}(\mathfrak{A}_{1})$ since
$g^{\prime}$ is canonical over $\operatorname{Aut}(\mathfrak{A}_{1})$. ∎

It can be easily verified that all earlier definitions and statements in this
section can be generalised to $n$-fold algebraic products
$\mathfrak{A}_{1}\boxtimes\cdots\boxtimes\mathfrak{A}_{n}$. In the following,
we focus on the situation when $n=2$ and
$\mathfrak{A}_{1}=\mathfrak{A}_{2}=({\mathbb{Q}};<)$. Here the polymorphisms
can be described more explicitly. Nevertheless, generalised versions of Lemma
42, Lemma 43, Corollary 44 and Lemma 45 for first-order expansions of
$(\mathbb{Q};<)^{(n)}$ can be proved in a similar fashion. The basic idea is
to choose one or two dimensions from $\\{1,\dots,n\\}$ that are referred to in
the statements. For a concrete example, see the proof of Proposition 61 that
is a generalization of Corollary 44. Generalizations of this kind will be
important in Section 4.6.

We continue by introducing some terminology. An operation $f\colon A^{k}\to A$
is called _essentially unary_ if there exists $i\in\\{1,\dots,k\\}$ and a
unary operation $g\colon A\to A$ such that $f(x_{1},\dots,x_{k})=g(x_{i})$ for
all $x_{1},\dots,x_{k}\in A$. Let $S\subseteq{\mathbb{Q}}$. An operation
$f\colon{\mathbb{Q}}^{2}\to{\mathbb{Q}}$ is called _dominated by the first
argument on $S$_ if $f(x,y)<f(x^{\prime},y^{\prime})$ for all $x,x^{\prime}\in
S$ such that $x<x^{\prime}$. If an operation
$f\colon{\mathbb{Q}}^{2}\to{\mathbb{Q}}$ is dominated by the first argument on
all of ${\mathbb{Q}}$, we say that is _dominated by the first argument_.
Examples of operations that are dominated by their first argument are
$\operatorname{lex}$-operations, twisted $\operatorname{lex}$-operations, and
order-preserving operations that only depend on the first argument.

Our aim is now to show that $\operatorname{Pol}(\mathfrak{D})$ contains an
operation with suitable domination properties (Lemma 43). This lemma will be a
cornerstone in the proof of our first result on syntactic normal forms
(Proposition 50). We first note that the binary polymorphisms of
$({\mathbb{Q}};<)$ that are canonical over
$\operatorname{Aut}({\mathbb{Q}};<)$ can be given a succinct characterisation.

######  Lemma 41 (see, e.g., Example 11.4.13 in [Bod21]).

Assume that $f\in\operatorname{Pol}({\mathbb{Q}};<)$ is a binary operation
that is canonical over $\operatorname{Aut}({\mathbb{Q}};<)$. Then, either $f$
is essentially unary, or $f$ is a $\operatorname{lex}$-operation or a twisted
$\operatorname{lex}$-operation, or the operation $(x,y)\mapsto f(y,x)$ is a
$\operatorname{lex}$-operation or a twisted $\operatorname{lex}$-operation.

We now turn our attention to the structure ${\mathfrak{D}}$ and obtain the
following intermediate result by analysing operations $g$ in
$\operatorname{Pol}(\mathfrak{D})$ that are canonical in a particular
dimension. Note that the following statements of Lemma 42, Lemma 43 and
Corollary 44 remain true also if the duals of $\operatorname{ll}$\- or
$\operatorname{pp}$-operations are used.

######  Lemma 42.

If $\operatorname{Pol}(\mathfrak{D})$ contains an operation $f$ such that
$\theta_{1}(f)$ is an $\operatorname{ll}$-operation, then
$\operatorname{Pol}(\mathfrak{D})$ also contains an operation $g$ such that
$\theta_{1}(g)$ is an $\operatorname{ll}$-operation and $\theta_{2}(g)$ or
$(x,y)\mapsto\theta_{2}(g)(y,x)$ is either a $\operatorname{lex}$-operation or
essentially unary (and in particular preserves $\leq_{2}$ and $\neq_{2}$). The
analogous statement holds if $\theta_{1}(f)$ is a
$\operatorname{pp}$-operation.

###### Proof.

Apply Lemma 40 to the operation $f$ for dimension $i=2$ and let
$g\in\operatorname{Pol}(\mathfrak{D})$ be the resulting operation such that
$\theta_{2}(g)$ is canonical and $\theta_{1}(g)=\theta_{1}(f)$. By Lemma 41,
either $\theta_{2}(g)$ is essentially unary, or a
$\operatorname{lex}$-operation, or a twisted $\operatorname{lex}$-operation,
or $(x,y)\mapsto\theta_{2}(g)(y,x)$ is a $\operatorname{lex}$-operation, or a
twisted $\operatorname{lex}$-operation. If $\theta_{2}(g)$ is a twisted
$\operatorname{lex}$-operation, then we consider $g^{\prime}$ defined by
$g^{\prime}(x,y)\coloneqq g(x,g(x,y))$ which is a
$\operatorname{lex}$-operation. The argument if
$(x,y)\mapsto\theta_{2}(g)(y,x)$ is a twisted $\operatorname{lex}$-operation
is similar. We finally note that $\theta_{1}(g^{\prime})$ is an
$\operatorname{ll}$-operation. The same proof works if $\theta_{1}(f)$ is a
$\operatorname{pp}$-operation. ∎

In our final step, we show that if $\operatorname{Pol}(\mathfrak{D})$ contains
an operation that satisfies the preconditions of Lemma 42, then the expanded
structure $(\mathfrak{D},\leq_{1},\neq_{1},\leq_{2},\neq_{2})$ admits a
polymorphism with a certain domination property.

######  Lemma 43.

Let $f\in\operatorname{Pol}(\mathfrak{D})$ be such that $\theta_{1}(f)$ is an
$\operatorname{ll}$-operation or a $\operatorname{pp}$-operation and assume
that $i\in\\{1,2\\}$. Then
$\operatorname{Pol}(\mathfrak{D};\leq_{1},\neq_{1})$ contains an operation $g$
such that $\theta_{2}(g)=\theta_{2}(f)$ and $\theta_{1}(g)$ is dominated by
the $i$-th argument. If $\theta_{1}(f)$ is a $\operatorname{pp}$-operation,
then $g$ can be chosen such that $\theta_{1}(g)$ equals $\pi^{2}_{i}$.

###### Proof.

We begin with the case $i=1$. Define

$\displaystyle U=\overline{\\{\beta
f(\alpha,\operatorname{id}_{{\mathbb{Q}}^{2}})\mid\alpha,\beta\in\operatorname{Aut}({\mathbb{Q}};<)({\mathbb{Q}})\\}}$

and note that $U\subseteq\operatorname{Pol}(\mathfrak{D},\leq_{1},\neq_{1})$
since $f\in\operatorname{Pol}(\mathfrak{D})$ and $\theta_{1}(f)$ preserves
$\leq$ and $\neq$. We claim that $U$ contains an operation $g$ such that
$\theta_{1}(g)$ is dominated by the first argument. To see this, let
$S\subseteq{\mathbb{Q}}$ be finite. If $f$ is an
$\operatorname{ll}$-operation, then choose
$\alpha_{S}\in\operatorname{Aut}({\mathbb{Q}};<)$ so that $\alpha_{S}(x)<0$
for every $x\in S$. Note that
$\theta_{1}(f((\alpha_{S},\operatorname{id}_{\mathbb{Q}}),\operatorname{id}_{{\mathbb{Q}}^{2}}))$
is then dominated by the first argument on $S$. If $T\subseteq S$, then the
homogeneity of $({\mathbb{Q}};<)$ implies that we can choose
$\beta_{S},\beta_{T}\in\operatorname{Aut}({\mathbb{Q}};<)$ such that

$\left((\beta_{S},\operatorname{id}_{\mathbb{Q}})f((\alpha_{S},\operatorname{id}_{\mathbb{Q}}),\operatorname{id}_{{\mathbb{Q}}^{2}})\right)|_{S^{2}}$

is an extension of

$\left((\beta_{T},\operatorname{id}_{\mathbb{Q}})f((\alpha_{T},\operatorname{id}_{\mathbb{Q}}),\operatorname{id}_{{\mathbb{Q}}^{2}})\right)|_{T^{2}}.$

Hence, $U$ contains an operation $g$ such that $\theta_{1}(g)$ is dominated by
the first argument. Moreover, $\theta_{2}(g)=\theta_{2}(f)$ since we have only
applied automorphisms that fix the second dimension, so $g$ satisfies the
statement of the lemma.

If $\theta_{1}(f)$ is a $\operatorname{pp}$-operation, then we proceed in the
same way but in this case the operation $\theta_{1}(g)$ is essentially unary,
and by applying automorphisms and using the fact that
$\operatorname{Pol}(\mathfrak{D})$ is closed we may suppose that
$\theta_{1}(g)$ equals $\pi^{2}_{1}$.

The proof when $i=2$ only requires flipping the inequalities in the definition
of the automorphisms $\alpha_{S}$. ∎

######  Corollary 44.

Let $f\in\operatorname{Pol}(\mathfrak{D})$ be such that $\theta_{1}(f)$ is an
$\operatorname{ll}$\- or a $\operatorname{pp}$-operation. Then there is an
operation
$g\in\operatorname{Pol}(\mathfrak{D};\leq_{1},\neq_{1},\leq_{2},\neq_{2})$
such that $\theta_{i}(g)$ is dominated by the $i$-th argument for both
$i=1,2$. If $\theta_{1}(f)$ is a $\operatorname{pp}$-operation, then we can
choose $g$ such that $\theta_{1}(g)=\pi_{1}^{2}$.

###### Proof.

Lemma 42 implies that there is an operation
$f^{\prime}\in\operatorname{Pol}(\mathfrak{D};\leq_{2},\neq_{2})$ and an index
$j\in\\{1,2\\}$ such that $\theta_{1}(f^{\prime})$ is an
$\operatorname{ll}$-operation or a $\operatorname{pp}$-operation, and
$\theta_{2}(f^{\prime})$ is dominated by the $j$-th argument. Hence, by Lemma
43 applied on $f^{\prime}$, there is
$g\in\operatorname{Pol}(\mathfrak{D};\leq_{1},\neq_{1},\leq_{2},\neq_{2})$
such that $\theta_{i}(g)$ is dominated by the $i$-th argument for both $i$ or
by the $(3-i)$-th argument for both $i$. Without loss of generality, we can
assume that $g$ satisfies the former, because otherwise we can replace $g$ by
the operation obtained from $g$ by flipping arguments. Similarly, if
$\theta_{1}(f)$ is a $\operatorname{pp}$-operation, then we can choose $g$
such that $\theta_{1}(g)$ is the projection $\pi_{1}^{2}$. ∎

We conclude this section with a duality result that reduces the number of
cases that we have to consider in some of the forthcoming proofs.

######  Lemma 45.

Let $\mathfrak{D}$ be a first-order expansion of
$({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$. The map given by
$(x,y)\mapsto(x,-y)$ is an isomorphism between $\mathfrak{D}$ and a structure
which is primitively positively interdefinable with a first-order expansion
$\mathfrak{C}$ of $({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$. For every
$f\in\operatorname{Pol}(\mathfrak{D})$ there exists
$f^{\prime}\in\operatorname{Pol}(\mathfrak{C})$ such that

  * •

$\theta_{1}(f^{\prime})=\theta_{1}(f)$ and

  * •

$\theta_{2}(f^{\prime})=\theta_{2}(f)^{*}$.

###### Proof.

For each relation $R$ of $\mathfrak{D}$, let $\phi$ be the defining formula of
$R$ over $({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$. Replace each atomic
formula of the form $x<_{2}y$ in $\phi$ by the formula $y<_{2}x$. The relation
defined by the formula will be denoted by $R^{\prime}$. The structure
$\mathfrak{C}$ is then the first-order expansion of
$({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$ by all relations of the form
$R^{\prime}$ where $R$ is a relation of $\mathfrak{D}$. Then,
$(x,y)\mapsto(x,-y)$ is an isomorphism between $\mathfrak{D}$ and a structure
which has the same polymorphisms as $\mathfrak{C}$. Indeed, let
$f\in\operatorname{Pol}(\mathfrak{C})$ be of arity $k$. Then, the operation
$f^{\prime}$ defined as

$f^{\prime}((x_{1},y_{1}),\dots,(x_{k},y_{k}))\coloneqq(\theta_{1}(f)(x_{1},\dots,x_{k}),\theta_{2}(f)^{*}(y_{1},\dots,y_{k}))$

is a polymorphism of $\mathfrak{D}$ that satisfies the requirements of the
lemma. ∎

###  4.3 Syntactic Normal Forms

In this section we prove that if
$\theta_{1}(\operatorname{Pol}(\mathfrak{D}))$ and
$\theta_{2}(\operatorname{Pol}(\mathfrak{D}))$ contain certain polymorphisms,
then the relations of $\mathfrak{D}$ can be defined by formulas satisfying
simple syntactic restrictions. These restrictions are all of the same kind:
the relations can be defined by conjunctions of clauses with straightforward
definitions. We start with the case that there exists an
$f\in\operatorname{Pol}(\mathfrak{D})$ such that $\theta_{1}(f)$ is an
$\operatorname{ll}$-operation or a $\operatorname{pp}$-operation (Proposition
50). We then prove a stronger statement if $\theta_{1}(f)$ is a
$\operatorname{pp}$-operation (Proposition 51), and an even stronger result if
additionally there is no binary operation
$g\in\operatorname{Pol}(\mathfrak{D})$ such that $\theta_{2}(g)$ is a
$\operatorname{lex}$-operation (Proposition 55). Finally, we treat the
situation that for both $i\in\\{1,2\\}$ there exists
$f_{i}\in\operatorname{Pol}(\mathfrak{D})$ such that $\theta_{i}(f_{i})$ is an
$\operatorname{ll}$-operation (Proposition 56). These results are collected in
Section 4.3.2. The proofs of Propositions 50 and 51 are based on a particular
normalisation of formulas that we describe in Section 4.3.1.

####  4.3.1 Normalisation

We will now describe a normalisation process for formulas that will be
extensively used in Section 4.3.2. Let $\phi$ be a quantifier-free formula
over $({\mathbb{Q}}^{2};=_{1},<_{1},=_{2},<_{2})$. We may assume that

  * R1.

$\phi$ is in reduced CNF (as defined in Section 3.2),

  * R2.

$\phi$ does not contain literals of the form $x\neq y$, because such literals
can be replaced by $x<_{1}y\vee y<_{1}x\vee x<_{2}y\vee y<_{2}x$, and

  * R3.

$\phi$ does not contain literals of the form $x=y$, because such literals can
be replaced by $x=_{1}y\wedge x=_{2}y$.

  * R4.

$\phi$ does not contain literals of the form $\neg(x<_{i}y)$, for
$i\in\\{1,2\\}$, because such literals can be replaced by $y<_{i}x\vee
y=_{i}x$.

We introduce two rewriting rules R5 and R6, each of which yields a formula
equivalent to the original formula $\phi$. The basis of both rules is the same
and the only difference is in the relation contained in one of the affected
literals. Suppose that $\phi$ contains, for distinct $i,j\in\\{1,2\\}$, a
clause $\alpha$ of the form $(u\circ_{i}v\vee x<_{j}y\vee\beta)$ where
$u,v,x,y$ are (not necessarily distinct) variables,
$\circ_{i}\in\\{<_{i},=_{i},\neq_{i}\\}$ and let $\phi^{\prime}$ be the other
clauses of $\phi$. If

$\displaystyle\phi^{\prime}\wedge\neg\beta\wedge u\circ_{i}v$
$\displaystyle\text{ implies }x=_{j}y,$

then we replace $\alpha$ by the two clauses

$\displaystyle(x<_{j}y\vee x=_{j}y\vee\beta)$ and
$\displaystyle(u\circ_{i}v\vee x\neq_{j}y\vee\beta).$

If the relation $\circ_{i}$ is $<_{i}$, then we will refer to the rewriting
rule as R5, and otherwise (that is, when $\circ_{i}\in\\{=_{i},\neq_{i}\\}$)
we will refer to the rule as R6.

To see that the new formula is equivalent to $\phi$, let $s$ be a solution to
$\phi$. If $s$ satisfies $\beta$, then the two new clauses are satisfied. If
$s$ does not satisfy $\beta$, then it must satisfy $u\circ_{i}v$ or $x<_{j}y$.
In the first case, $s$ satisfies the second new clause, and by assumption it
also satisfies the first new clause. In the latter case, it clearly satisfies
both the first and the second clause. Now suppose that conversely, $s$
satisfies $\phi^{\prime}$ and the two new clauses. If $s$ satisfies $\beta$ or
$x<_{j}y$ then $\alpha$ is satisfied. Otherwise, the first new clause implies
that $x=_{j}y$, and hence the second clause implies that $u\circ_{i}v$, and
hence $\alpha$ is satisfied.

If the formula obtained from applying R5 or R6 is not reduced, we remove
literals to make it reduced. Note that after every application of R5 or R6 the
conditions R1-R4 will still be satisfied.

The reason to split the rewriting rule into two rules R5 and R6 is that only
R5 terminates (i.e. can be applied only finitely many times) on every
quantifier-free CNF formula (Lemma 46). To prove termination of R6 (Lemma 48)
and existence of an equivalent formula to which none of the rewriting rules
above can be applied, we require existence of a certain operation that
preserves the formula. On the way we also prove a syntactic restriction on
such formulas (Lemma 47). Note that Lemma 47 and 48 remain true also if
$\theta_{1}(f)$ is the dual of an $\operatorname{ll}$\- or
$\operatorname{pp}$-operation; it can be proved using the version of Corollary
44 based on duals.

######  Lemma 46.

Let $\phi$ be a quantifier-free CNF formula over
$({\mathbb{Q}}^{2};=_{1},<_{1},=_{2},<_{2})$. Then the rewriting rule R5
applied on $\phi$ terminates.

###### Proof.

Let $\alpha$ be an arbitrary clause over
$({\mathbb{Q}}^{2};=_{1},<_{1},=_{2},<_{2})$. Let $m(\alpha)$ denote the
number of $<_{1}$\- and $<_{2}$-literals in $\alpha$. Assume we apply R5 to
the clause $\alpha=(u<_{i}v\vee x<_{j}y\vee\beta)$ where we assume (without
loss of generality) that $u<_{i}v\not\in\beta$ and $x<_{j}y\not\in\beta$. This
yields two clauses $\alpha_{1}=(x<_{j}y\vee x=_{j}y\vee\beta)$ and
$\alpha_{2}=(u<_{i}v\vee x\neq_{j}y\vee\beta)$. Note that
$m(\alpha_{1})<m(\alpha)$ and $m(\alpha_{2})<m(\alpha)$ and reducing the
formula cannot increase $m(\alpha)$ for any clause $\alpha$.

Now consider a quantifier-free CNF formula $\phi$ over
$({\mathbb{Q}}^{2};=_{1},<_{1},=_{2},<_{2})$. Let $\ell$ be the maximum clause
length of $\phi$ and let $k$ be the number of variables appearing in $\phi$.
Note that R5-rewriting cannot increase $\ell$ or $k$, and for any clause
$\alpha$ in $\phi$, it holds that $0\leq m(\alpha)\leq\ell$. Let $f(\ell,k)$
denote the (finite) number of possible clauses over
$({\mathbb{Q}}^{2};=_{1},<_{1},=_{2},<_{2})$ where clause length is bounded by
$\ell$ and at most $k$ variables are used. Arbitrarily choose a clause
$\alpha$ in $\phi$. If R5 is applied to $\alpha$, then we know that $\alpha$
is replaced by at most two new clauses $\alpha_{1}$ and $\alpha_{2}$ where
$m(\alpha_{1})<m(\alpha)$ and $m(\alpha_{2})<m(\alpha)$. Thus, the clause
$\alpha$ can result in at most $2^{\ell}$ applications of rule R5. Since there
are at most $f(\ell,k)$ clauses in $\phi$, we conclude that R5 can be applied
at most $f(\ell,k)\cdot 2^{\ell}$ times to $\phi$. ∎

The following notation will be practical in several proofs dealing with
syntactic forms. Let $g$ be a binary operation on $\mathbb{Q}$, $\phi$ a
formula over $({\mathbb{Q}}^{2};=_{1},<_{1},=_{2},<_{2})$ and set of variables
$X$ and $s,t:X\rightarrow\mathbb{Q}$ assignments of $\phi$. Then $g(s,t)$
represents the assignment of $\phi$ that assigns to variable $x\in X$ the
value $g(s(x),t(x))$.

######  Lemma 47.

Let $\phi$ be a quantifier-free CNF formula over
$({\mathbb{Q}}^{2};=_{1},<_{1},=_{2},<_{2})$ such that R5 cannot be applied to
$\phi$. Suppose that $\phi$ is preserved by an operation
$f\in\operatorname{Pol}({\mathbb{Q}}^{2};=_{1},<_{1},=_{2},<_{2})$ such that
$\theta_{1}(f)$ is an $\operatorname{ll}$-operation or a
$\operatorname{pp}$-operation. Then $\phi$ does not contain a clause that
contains a $<_{j}$-literal for both $j\in\\{1,2\\}$.

###### Proof.

By Corollary 44, there is
$g\in\operatorname{Pol}({\mathbb{Q}}^{2};=_{1},<_{1},=_{2},<_{2},\leq_{1},\neq_{1},\leq_{2},\neq_{2})$
that preserves $\phi$ such that $\theta_{j}(g)$ is dominated by $j$-th
argument for both $j$.

Suppose for contradiction that $\phi$ contains a clause $\alpha$ of the form
$(u<_{1}v\vee x<_{2}y\vee\beta)$. Since R5 cannot be applied and $\phi$ is
reduced, there are satisfying assignments $s$ and $t$ of $\phi$ such that $s$
satisfies $u<_{1}v$, $y<_{2}x$, and falsifies $\beta$ and $t$ satisfies
$v<_{1}u$, $x<_{2}y$, and falsifies $\beta$. Then the tuple $g(t,s)$ satisfies
$v<_{1}u$ since $\theta_{1}(g)$ is dominated by the first argument, and it
satisfies $y<_{2}x$ since $\theta_{2}(g)$ is dominated by the second argument.
Moreover, all other literals of $\alpha$ are falsified, too, since $g$
preserves $<_{j}$, $=_{j}$, $\leq_{j}$, and $\neq_{j}$ for $j\in\\{1,2\\}$. ∎

######  Lemma 48.

Let $\phi$ be a quantifier-free CNF formula over
$({\mathbb{Q}}^{2};=_{1},<_{1},=_{2},<_{2})$ such that R5 cannot be applied on
$\phi$. Suppose that $\phi$ is preserved by an operation
$f\in\operatorname{Pol}({\mathbb{Q}}^{2};=_{1},<_{1},=_{2},<_{2})$ such that
$\theta_{1}(f)$ is an $\operatorname{ll}$-operation or a
$\operatorname{pp}$-operation. Then the rewriting rule R6 applied to $\phi$
terminates.

###### Proof.

By Lemma 47, $\phi$ does not contain a clause that contains a $<_{j}$-literal
for both $j\in\\{1,2\\}$. Note that by an application of the rewriting rule R6
no such clause can be created. For a clause $\alpha$ in $\phi$, let
$p(\alpha)$ be the number of pairs of a $\\{=_{i},\neq_{i}\\}$-literal and a
$<_{j}$-literal, for distinct $i$ and $j$, that appears in $\alpha$.

Arbitrarily choose a clause $\alpha$ in $\phi$ that admits an application of
R6. Then $\alpha=(u\circ_{i}v\vee x<_{j}y\vee\beta)$ for
$\circ_{i}\in\\{=_{i},\neq_{i}\\}$. After applying R6, $\alpha$ is replaced by
two clauses $\alpha_{1}=(x<_{j}y\vee x=_{j}y\vee\beta)$ and
$\alpha_{2}=(u\circ_{i}v\vee x\neq_{j}y\vee\beta)$. Observe that
$p(\alpha_{1})<p(\alpha)$ and $p(\alpha_{2})<p(\alpha)$ since $\alpha$ does
not contain $<_{3-j}$-literals. Moreover, reducing the formula does not
increase $p(\gamma)$ for any clause $\gamma$ in the formula.

Let $\ell$ be the maximum clause length of $\phi$. For any clause $\gamma$ in
$\phi$, it holds that $0\leq p(\gamma)\leq\ell^{2}/4$. Using an argument
analogous to the one in Lemma 46, we conclude that R6 can be applied only
finitely many times to $\phi$. ∎

If $\phi$ is a reduced formula such that none of the rewriting rules presented
above are applicable, then we call it _normal_. If $\phi$ is a quantifier-free
CNF formula over $({\mathbb{Q}}^{2};=_{1},<_{1},=_{2},<_{2})$ preserved by
$f\in\operatorname{Pol}({\mathbb{Q}}^{2};=_{1},<_{1},=_{2},<_{2})$ where
$\theta_{1}(f)$ is an $\operatorname{ll}$-operation, a
$\operatorname{pp}$-operation, or the dual of such an operation, it is
possible to rewrite it to an equivalent normal formula by first applying R5
until it terminates and then applying R6 until it terminates. Observe that the
resulting formula satisfies conditions R1-R4 and does not admit an application
of R5 (since it does not contain a clause of the required form by Lemma 47) or
R6. Note that if $\phi$ is normal and contains a clause of the form
$(u\circ_{i}v\;\vee\;x<_{j}y\;\vee\;\beta)$, then $\phi$ has a satisfying
assignment that satisfies $u\circ_{i}v$, falsifies $\beta$, and satisfies
$y<_{j}x$, because otherwise we could have applied R5 or R6.

The rewriting rules and Lemma 46 can be generalised in a straightforward
fashion to formulas over $(\mathbb{Q};<)^{(n)}$. To prove a generalised
version of Lemma 47, one needs to use Corollary 44 to produce a polymorphism
with the particular domination property in two distinct dimensions $i$ and $j$
(see the proof of Proposition 61 for more details). The generalised version of
the lemma then shows that there is no clause containing both $<_{i}$-literals
and $<_{j}$-literals for distinct $i$ and $j$ under the assumption that for
all but at most one $p\in\\{1,\dots,n\\}$ there is
$f_{p}\in\operatorname{Pol}(\mathfrak{D})$ such that $\theta_{p}(f_{p})$ is an
$\operatorname{ll}$-operation or a $\operatorname{pp}$-operation.
Subsequently, a generalised version of Lemma 48 can be proved and normal
formulas can be defined. The normalisation process for formulas over
$(\mathbb{Q};<)^{(n)}$ will be used in Section 4.6.

####  4.3.2 Definitions via Restricted Clauses

The following definition is central in our presentation of various syntactic
normal forms.

######  Definition 49.

A clause is _weakly $1$-determined_ if it is of the form

$\psi\vee\bigvee_{i\in\\{1,\dots,k\\}}x_{i}\neq_{2}y_{i}$

where $\psi$ is $1$-determined and $k\geq 0$. Weakly $2$-determined clauses
are defined analogously.

A clause can simultaneously be weakly $1$-determined _and_ weakly
$2$-determined: $x\neq_{1}y\vee u\neq_{2}v$ is one example. Normalised
formulas in the sense of Section 4.3.1 play a key role in our first result
concerning logical definitions based on weakly $s$-determined clauses.

######  Proposition 50.

Suppose that $\operatorname{Pol}(\mathfrak{D})$ contains an operation $f$ such
that $\theta_{1}(f)$ is an $\operatorname{ll}$-operation or a
$\operatorname{pp}$-operation. Then, the following holds for every relation
$R$ in $\mathfrak{D}$: if a normal formula $\phi$ is a definition of $R$ over
$(\mathbb{Q}^{2},<_{1},=_{1},<_{2},=_{2})$, then $\phi$ is a conjunction of
clauses each of which is weakly $i$-determined for some $i\in\\{1,2\\}$.

###### Proof.

By Corollary 44, there is an operation
$g\in\operatorname{Pol}(\mathfrak{D};\leq_{1},\neq_{1},\leq_{2},\neq_{2})$
such that $\theta_{i}(g)$ is dominated by the $i$-th argument for both
$i\in\\{1,2\\}$. Let $\phi$ be a normal formula that defines a relation
$R\in\mathfrak{D}$ over $({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$. Note, in
particular, that $\phi$ cannot be rewritten using rule R5 or R6. Let $\psi$ be
a clause of $\phi$. Properties R1–R4 imply that $\psi$ can be written as

$\psi_{1}\vee\psi_{2}\vee\bigvee_{l\in\\{1,\dots,k\\}\;{\rm
and}\;j\in\\{1,2\\}}x_{l}\neq_{j}y_{l}$

where $\psi_{i}$ for $i\in\\{1,2\\}$ only contains literals of the form
$x=_{i}y$ or $x<_{i}y$.

We show the result by verifying that $\psi_{1}$ or $\psi_{2}$ is the empty
disjunction. Suppose to the contrary that $\psi_{1}$ contains a literal
$\ell_{1}$ and $\psi_{2}$ contains a literal $\ell_{2}$. Since $\phi$ is
reduced, it must have a satisfying assignment $s$ that satisfies $\ell_{1}$
and falsifies all other literals of $\psi$, and there also exists a satisfying
assignment $t$ that satisfies $\ell_{2}$ and falsifies all other literals of
$\psi$. Note that by Lemma 47 it cannot occur that $\ell_{1}$ equals $u<_{1}v$
and $\ell_{2}$ equals $x<_{2}y$, since R5 cannot be applied to $\phi$.
Therefore, we have to consider the following cases.

  1. 1.

Suppose that the literal $\ell_{1}$ is of the form $u=_{1}v$ and the literal
$\ell_{2}$ equals $x<_{2}y$. Since $\phi$ is normal, we may assume (by R6)
that $s$ satisfies $y<_{2}x$. Then $g(t,s)$ satisfies $u\neq_{1}v$ since
$\theta_{1}(g)$ is dominated by the first argument, and it satisfies $y<_{2}x$
because $\theta_{2}(g)$ is dominated by the second argument. Moreover, all
other literals of $\psi$ are falsified. Hence, $g(t,s)$ does not satisfy
$\phi$, which contradicts $g\in\operatorname{Pol}(\mathfrak{D})$.

  2. 2.

The case that the literal $\ell_{1}$ equals $u<_{1}v$ and the literal
$\ell_{2}$ equals $x=_{2}y$, and the case that $\ell_{1}$ equals $u=_{1}v$ and
the literal $\ell_{2}$ equals $x=_{2}y$ can be treated similarly.

If $\psi_{1}$ is empty, then we obtain a clause that is weakly $2$-determined.
Likewise, if $\psi_{2}$ is empty, then $\psi$ is a weakly $1$-determined
clause. ∎

Under additional conditions on polymorphisms, we can define relations by
formulas that are based on weakly $1$-determined clauses together with (not
weakly) $2$-determined clauses.

######  Proposition 51.

Let $f\in\operatorname{Pol}(\mathfrak{D})$ be such that $\theta_{1}(f)$ is a
$\operatorname{pp}$-operation. Then every normal conjunction $\phi$ of weakly
1-determined and weakly 2-determined clauses that is preserved by $f$ is a
conjunction of weakly $1$-determined and of $2$-determined clauses.

###### Proof.

By Corollary 44 there is an operation
$g\in\operatorname{Pol}(\mathfrak{D};\leq_{1},\neq_{1},\leq_{2},\neq_{2})$
such that $\theta_{1}(g)=\pi_{1}^{2}$ and $\theta_{2}(g)$ is dominated by the
second argument. Suppose for contradiction that $\phi$ contains a clause
$\psi$ with a literal $x\neq_{1}y$ and a literal $\chi$ which is of the form
$u<_{2}v$ or $u=_{2}v$. The formula $\phi$ is reduced so it has a satisfying
assignment $s$ which satisfies $x\neq_{1}y$ and falsifies all other literals
of $\psi$, and a satisfying assignment $t$ which satisfies $\chi$ and
falsifies all other literals in $\psi$; in particular, $t$ satisfies
$x=_{1}y$.

We first consider the case that $\chi$ is of the form $u<_{2}v$ and $s$
consequently satisfies $v\leq_{2}u$. Since $\phi$ is normal we may even
suppose that $s$ satisfies $v<_{2}u$. Then $g(t,s)$ satisfies $x=_{1}y$ since
$\theta_{1}(g)=\pi^{2}_{1}$ and it satisfies $v<_{2}u$ since $\theta_{2}(g)$
is dominated by the second argument. Hence, it satisfies neither the literal
$x\neq_{1}y$ nor the literal $u<_{2}v$, nor any of the other literals of
$\psi$ since $f$ preserves $\leq_{i}$ and $\neq_{i}$ for $i\in\\{1,2\\}$. This
is in contradiction to the assumption that $\phi$ is preserved by $g$.

The case that $\chi$ is of the form $u=_{2}v$ similarly leads to a
contradiction. ∎

######  Remark 52.

Note that it is not true that every weakly $2$-determined clause of formula
$\phi$ in Proposition 51 is $2$-determined: For example, consider the clause
$\psi$ of the form $x\neq_{1}y\vee u\neq_{2}v$. The clause $\psi$ is weakly
$2$-determined, but not $2$-determined, and it satisfies the assumptions of
Proposition 51: it is normal, and preserved by a map $(f_{1},f_{2})$ where
$f_{1}$ is a $\operatorname{pp}$-operation and $f_{2}$ is an
$\operatorname{ll}$-operation. To see this, let $s,t$ be two satisfying
assignments of $\psi$. Either one of $s$ and $t$ satisfies $u\neq_{2}v$ and
hence $(f_{1},f_{2})(s,t)$ satisfies it as well by the injectivity of $f_{2}$,
or both $s$ and $t$ satisfy $x\neq_{1}y$ and hence $(f_{1},f_{2})(s,t)$
satisfies it as well since $f_{1}$ preserves $\neq$.

In the next proof we use the notion of the orbit of a $k$-tuple
$(t_{1},\dots,t_{k})\in\mathbb{Q}^{k}$ under
$\operatorname{Aut}(\mathbb{Q};<)$ from Section 2.3. Observe that the
homogeneity of $({\mathbb{Q}};<)$ implies that the orbit of a tuple
$(t_{1},\dots,t_{k})$ under $\operatorname{Aut}({\mathbb{Q}};<)$ is determined
by the weak linear order induced on $(t_{1},\dots,t_{k})$ in
$({\mathbb{Q}};<)$. We need a weak linear order since some of the elements
$t_{1},\dots,t_{k}$ may be equal.

######  Proposition 53.

As in the previous proposition, let $f\in\operatorname{Pol}(\mathfrak{D})$ be
such that $\theta_{1}(f)$ is a $\operatorname{pp}$-operation. Then every
relation of $\mathfrak{D}$ can be defined by a conjunction of $2$-determined
clauses and weakly $1$-determined clauses of the form

$\displaystyle u_{1}\neq_{2}v_{1}\vee\cdots u_{m}\neq_{2}v_{m}\vee
y_{1}\neq_{1}x\vee\cdots\vee y_{k}\neq_{1}x\vee z_{1}\leq_{1}x\vee\cdots\vee
z_{l}\leq_{1}x.$ (2)

(In other words, if we drop the first $m$ literals in and remove subscripts we
obtain a formula as described in Theorem 33.)

###### Proof.

Let $\phi$ be a formula over a finite set of variables $X$ that defines a
relation $R$ from $\mathfrak{D}$. Without loss of generality, we may assume
that $\phi$ is normal. Hence, by Proposition 50 and Proposition 51, $\phi$ is
a conjunction of weakly 1-determined and of 2-determined clauses. Let
$\phi^{\prime}$ be the conjunction of all clauses of the form (2) and of all
$2$-determined clauses with variables from $X$ that are reduced and implied by
$\phi$; since $|X|$ is finite, $\phi^{\prime}$ is a finite formula. We claim
that $\phi^{\prime}$ implies $\phi$, and consequently that $\phi^{\prime}$ is
a definition of $R$ of the required syntactic form.

The $2$-determined conjuncts of $\phi$ are clearly implied by $\phi^{\prime}$.
In the rest of the proof, we prove in two steps that every weakly
$1$-determined conjunct of $\phi$ is implied by $\phi^{\prime}$: Firstly, we
show that we may assume that all weakly $1$-determined clauses of $\phi$ are
of the form (3) and that they are minimal in a particular sense specified
below. Secondly, we show that every such clause is implied by $\phi^{\prime}$,
because the assumption that $R$ is preserved by $f$ would be violated
otherwise.

To proceed with the first step, we claim that every conjunction of weakly
1-determined clauses can be written as a conjunction of formulas of the form

$\chi\vee\neg(y_{1}\circ_{1}y_{2}\wedge\cdots\wedge y_{k}\circ_{k}y_{k+1})$

where $\chi:=\bigvee_{i=1}^{m}u_{i}\neq_{2}v_{i}$ and
$\circ_{1},\dots,\circ_{k}\in\\{=_{1},<_{1}\\}$. To see this, first note that
every orbit of $k+1$-tuples in $\operatorname{Aut}({\mathbb{Q}};<)$ can be
defined by a formula of the form $x_{1}\circ_{1}x_{2}\wedge\cdots\wedge
x_{k}\circ_{k}x_{k+1}$ where $\circ_{1},\dots,\circ_{k}\in\\{=,<\\}$ if the
variables are named appropriately. Hence, every first-order formula in
$(\mathbb{Q};<)$ is equivalent to a conjunction of negations of such formulas.
It follows that every 1-determined clause can be written as a conjunction of
formulas of the form $\neg(y_{1}\circ_{1}y_{2}\wedge\cdots\wedge
y_{k}\circ_{k}y_{k+1})$ for $\circ_{1},\dots,\circ_{k}\in\\{=_{1},<_{1}\\}$.
Using distributivity of disjunction over conjunction we can therefore rewrite
a conjunction of weakly 1-determined clauses into a conjunction of formulas of
the desired form.

We may henceforth assume that every conjunct $\psi$ of $\phi$ that is not
2-determined is of the form

$\chi\vee y_{1}\circ_{1}y_{2}\vee\cdots\vee y_{k}\circ_{k}y_{k+1}$ (3)

where $\circ_{1},\dots,\circ_{k}\in\\{\neq_{1},\geq_{1}\\}$. We may
additionally assume that $\phi$ contains only those clauses of the form (3)
that are minimal in the following sense: a clause $\psi=\chi\vee
y_{1}\circ_{1}y_{2}\vee\cdots\vee y_{k}\circ_{k}y_{k+1}$ is minimal if there
is no clause $\chi\vee y_{1}^{\prime}\circ_{1}y_{2}^{\prime}\vee\cdots\vee
y_{k^{\prime}}^{\prime}\circ_{k^{\prime}}y_{k^{\prime}+1}^{\prime}$ different
from $\psi$ such that it implies $\psi$ and
$y_{1}^{\prime},\dots,y_{k^{\prime}}^{\prime}$ is a subsequence of
$y_{1},\dots,y_{k}$.

We now show that the clause $\psi$ is implied by $\phi^{\prime}$. If
$\circ_{i}$ equals $\neq_{1}$ for every $i\in\\{1,\dots,k\\}$ then $\psi$ is
equivalent to $\chi\vee\neg(y_{1}=_{1}y_{k+1}\wedge\cdots\wedge
y_{k}=_{1}y_{k+1})$ and hence is equivalent to $\chi\vee
y_{1}\neq_{1}y_{k+1}\vee\cdots\vee y_{k}\neq_{1}y_{k+1}$ which is of the form
(2) (for $l=0$). But this formula is then a conjunct of $\phi^{\prime}$ and
there is nothing to be shown.

Otherwise, let $j$ be smallest such that $\circ_{j}$ equals $\geq_{1}$. Then
$\psi$ is equivalent to a formula of the form

$\chi\vee y_{1}\neq_{1}y_{j}\vee\cdots\vee y_{j-1}\neq_{1}y_{j}\vee
y_{j}\geq_{1}y_{j+1}\vee\eta$

where $\eta$ is of the form $y_{j+1}\circ_{j+1}y_{j+2}\vee\cdots\vee
y_{k}\circ_{k}y_{k+1}$ for
$\circ_{j+1},\dots,\circ_{k}\in\\{\neq_{1},\geq_{1}\\}$. The formula

$\displaystyle\chi\vee y_{1}\neq_{1}y_{j}\vee\cdots\vee
y_{j-1}\neq_{1}y_{j}\vee y_{j+1}\leq_{1}y_{j}\vee\cdots\vee
y_{k+1}\leq_{1}y_{j}$ (4)

implies $\psi$. To see this, compare the negations of the formulas: $\neg\psi$
is equivalent to the conjunction of $\neg\chi\wedge
y_{1}=_{1}\dots=_{1}y_{j}\wedge y_{j}<_{1}y_{j+1}$ and the fact that
$y_{j+1},\dots,y_{k}$ is a non-decreasing sequence, while the negation of the
formula (4) is equivalent to

$\neg\chi\wedge y_{1}=_{1}\dots=_{1}y_{j}\wedge
y_{j+1}>_{1}y_{j}\wedge\dots\wedge y_{k}>_{1}y_{j}.$

Therefore, if the formula (4) is a conjunct of $\phi^{\prime}$, then there is
again nothing to be shown.

Otherwise, there must exist an assignment $r$ that satisfies $\phi$ but not
(4). Note that $r(y_{j})<_{1}r(y_{i})$ for every $i\in\\{j+1,\dots,k+1\\}$.
Since $\psi$ was minimal, the clause $\chi\vee\eta$ is not implied by $\phi$
and hence there must also exist an assignment $s$ which satisfies $\phi$, but
does not satisfy $\chi\vee\eta$. Choose
$\alpha\in\operatorname{Aut}(\mathfrak{D})$ such that
$\alpha(r(y_{j}))<_{1}0<_{1}\alpha(r(y_{i}))$ for all
$i\in\\{j+1,\dots,k+1\\}$. Then $t:=f(\alpha(r),s)$ is an assignment that does
not satisfy $\psi$ by the definition of a $\operatorname{pp}$-operation. This
contradicts that $\phi$ defines a relation from $\mathfrak{D}$. ∎

As the following lemma shows, in the case of
$\theta_{1}(\operatorname{Pol}(\mathfrak{D}))$ containing a
$\operatorname{pp}$-operation and
$\theta_{2}(\operatorname{Pol}(\mathfrak{D}))$ containing an
$\operatorname{ll}$-operation, we may restrict to formulas of a very
particular form.

######  Proposition 54.

Let $f_{1},f_{2}\in\operatorname{Pol}(\mathfrak{D})$ be such that
$\theta_{1}(f_{1})$ is a $\operatorname{pp}$-operation and $\theta_{2}(f_{2})$
is an $\operatorname{ll}$-operation. Then every relation of $\mathfrak{D}$ can
be defined by a conjunction of weakly $1$-determined clauses of the form (2)
and $2$-determined clauses

$\displaystyle x_{1}\neq_{2}y_{1}\vee\cdots\vee x_{m}\neq_{2}y_{m}\vee
z_{1}<_{2}z_{0}\vee\cdots\vee
z_{\ell}<_{2}z_{0}\vee(z_{0}=_{2}z_{1}=_{2}\cdots=_{2}z_{\ell}),$ (5)

where it is permitted that $l=0$ or $m=0$, and the final disjunct may be
omitted (in other words, clauses obtained from ll-Horn clauses by adding the
subscript $2$ to all relation symbols).

###### Proof.

Let $R$ be a relation of $\mathfrak{D}$. By Proposition 53, $R$ can be defined
by a formula $\phi_{1}\wedge\phi_{2}$, where $\phi_{1}$ is a conjunction of
weakly $1$-determined clauses of the form (2) and $\phi_{2}$ is a conjunction
of $2$-determined clauses. Recall the operator $\operatorname{cr}$ introduced
at the end of Section 3.2. Let us denote
$\operatorname{cr}(\phi_{1}\wedge\phi_{2},\\{2\\},\phi_{2})$ by $\psi_{2}$;
note that $\psi_{2}$ is a conjunction of $2$-determined clauses preserved by
$\operatorname{Pol}(\mathfrak{D})$. Moreover the formula
$\phi_{1}\wedge\psi_{2}$ still defines $R$. By Lemma 21, $\hat{\psi_{2}}$ is
preserved by an $\operatorname{ll}$-operation. By Theorem 38, $\hat{\psi_{2}}$
may be taken to be a conjunction of $\operatorname{ll}$-Horn clauses and
therefore $\psi_{2}$ would be a conjunction of clauses of the form (5). This
concludes the proof. ∎

We next present an even more restricted syntactic form; in this case it is
sufficient to use $i$-determined clauses, $i\in\\{1,2\\}$, and we do not need
weakly $i$-determined clauses at all.

######  Proposition 55.

Suppose that there exists $f\in\operatorname{Pol}(\mathfrak{D})$ such that
$\theta_{1}(f)$ is a $\operatorname{pp}$-operation, but there is no binary
$g\in\operatorname{Pol}(\mathfrak{D})$ such that $\theta_{2}(g)$ is a
$\operatorname{lex}$-operation. Then every relation of $\mathfrak{D}$ can be
defined by a formula $\phi_{1}\wedge\phi_{2}$ such that $\phi_{i}$ is a
conjunction of $i$-determined clauses for $i=1,2$. Moreover, for every such
definition $\phi_{1}\wedge\phi_{2}$, there is a conjunction $\psi_{1}$ of
$1$-determined clauses of the form

$y_{1}\neq_{1}x\vee\cdots\vee y_{k}\neq_{1}x\vee z_{1}\leq_{1}x\vee\cdots\vee
z_{l}\leq_{1}x$

such that $\psi_{1}\wedge\phi_{2}$ still defines the same relation.

###### Proof.

Lemma 42 implies that $\operatorname{Pol}(\mathfrak{D})$ contains an operation
$f^{\prime}$ such that $\theta_{1}(f^{\prime})$ is a
$\operatorname{pp}$-operation and $\theta_{2}(f^{\prime})$ is either a
$\operatorname{lex}$-operation or it is essentially unary; by assumption, it
cannot be a $\operatorname{lex}$-operation so it must be essentially unary.
Let $i\in\\{1,2\\}$ be such that $\theta_{2}(f^{\prime})$ depends only on the
$i$-th argument. Since $\theta_{2}(f^{\prime})$ preserves $<$, there is
$\alpha\in\operatorname{Aut}(\mathbb{Q};<)$ such that
$\theta_{2}((\operatorname{id}_{\mathbb{Q}},\alpha)f^{\prime})=\pi_{i}^{2}$.
Therefore, we can assume without loss of generality that
$\theta_{2}(f^{\prime})=\pi_{i}^{2}$. By Lemma 43 applied on $f^{\prime}$, we
obtain $g\in\operatorname{Pol}(\mathfrak{D})$ such that
$\theta_{1}(g)=\pi_{3-i}^{2}$ and $\theta_{2}(g)=\pi_{i}^{2}$. This implies
that $(\pi_{1}^{2},\pi_{2}^{2})\in\operatorname{Pol}(\mathfrak{D})$. By Lemma
22, every relation of $\mathfrak{D}$ can be defined by a conjunction of
$1$-determined and $2$-determined clauses.

Let $R$ be a relation of $\mathfrak{D}$. Let $\phi_{1}\wedge\phi_{2}$ be a
definition of $R$ such that $\phi_{i}$ is a conjunction of $i$-determined
clauses, $i=1,2$. Recall the operator $\operatorname{cr}(\cdot)$ introduced at
the end of Section 3.2. Let
$\psi_{1}=\operatorname{cr}(\phi_{1}\wedge\phi_{2},\\{1\\},\phi_{1})$. Then
the formula $\psi_{1}$ is a conjunction of $1$-determined clauses preserved by
$\operatorname{Pol}(\mathfrak{D})$ and $\psi_{1}\wedge\phi_{2}$ defines $R$.
By Lemma 21, $\hat{\psi_{1}}$ is preserved by a $\operatorname{pp}$-operation.
Hence, by Theorem 33, we may assume that $\psi_{1}$ is a conjunction of
clauses of the form

$y_{1}\neq_{1}x\vee\cdots\vee y_{k}\neq_{1}x\vee z_{1}\leq_{1}x\vee\cdots\vee
z_{l}\leq_{1}x.$

This concludes the proof. ∎

Assume that for every $i\in\\{1,2\\}$, the clone
$\operatorname{Pol}(\mathfrak{D})$ contains an operation $f_{i}$ such that
$\theta_{i}(f_{i})$ is an $\operatorname{ll}$-operation or the dual of such an
operation. Then, we may combine the information about syntactically restricted
definitions of the relations of $\mathfrak{D}$ from Proposition 50 with
$\operatorname{ll}$-Horn definability from Theorem 38, and obtain the next
result (Proposition 56). We will use the following notation for simplifying
the presentation. For a formula $\phi$ over
$(\mathbb{Q}^{n};<_{1},=_{1},\dots,<_{n},=_{n})$, we introduce $n$ fresh
variables $x^{1},\dots,x^{n}$ for each variable $x$ that appears in $\phi$.
Then, we let $\operatorname{ve}(\phi)$ (for variable expansion) denote the
formula over $(\mathbb{Q};<)$ resulting from $\phi$ by replacing each atomic
formula of the form $x\circ_{i}y$ by $x^{i}\circ y^{i}$, where
$\circ\in\\{<,\leq,=,\neq\\}$ and $i\in\\{1,\dots,n\\}$.

######  Proposition 56.

Suppose that for every $i\in\\{1,2\\}$ the clone
$\operatorname{Pol}(\mathfrak{D})$ contains an operation $f_{i}$ such that
$\theta_{i}(f_{i})$ is an $\operatorname{ll}$-operation. Then every relation
of $\mathfrak{D}$ has a definition by a conjunction of clauses of the form

$x_{1}\neq_{i_{1}}y_{1}\vee\cdots\vee x_{m}\neq_{i_{m}}y_{m}\vee
z_{1}<_{j}z_{0}\vee\cdots\vee
z_{\ell}<_{j}z_{0}\vee(z_{0}=_{j}z_{1}=_{j}\cdots=_{j}z_{\ell})$

for $i_{1},\dots,i_{m},j\in\\{1,2\\}$ and where the last disjunct may be
omitted. Moreover, $\mathfrak{D}$ has a primitive positive interpretation in
$\mathfrak{L}$.

###### Proof.

Let $R$ be a relation of $\mathfrak{D}$, and let $\phi$ be a definition of
$R$. Without loss of generality, we may assume that $\phi$ is normal and hence
a conjunction of weakly $1$-determined and weakly $2$-determined clauses
(Proposition 50).

Claim. The formula $\operatorname{ve}(\phi)$ over $({\mathbb{Q}};<)$ is
preserved by every $\operatorname{ll}$ operation.

To prove the claim, let $\operatorname{ll}$ be an
$\operatorname{ll}$-operation and let $r^{\prime}$ and $s^{\prime}$ be
satisfying assignments for $\operatorname{ve}(\phi)$. We have to show that
$t^{\prime}(x)\coloneqq\operatorname{ll}(r^{\prime}(x),s^{\prime}(x))$
satisfies $\operatorname{ve}(\phi)$. Let $\psi^{\prime}$ be a conjunct of
$\operatorname{ve}(\phi)$. Then $\psi^{\prime}$ has been created from a
conjunct $\psi$ of $\phi$ with variables $y_{1},\dots,y_{m}$, which must be
weakly $i$-determined, for some $i\in\\{1,2\\}$. We assume henceforth that
$i=1$; the other case can be shown analogously. Note that the maps $r\colon
x\mapsto(r^{\prime}(x^{1}),r^{\prime}(x^{2}))$ and $s\colon
x\mapsto(s^{\prime}(x^{1}),s^{\prime}(x^{2}))$ are satisfying assignments to
$\phi$. Since $\theta_{1}(f_{1})$ is an $\operatorname{ll}$-operation, we may
choose $\alpha\in\operatorname{Aut}(\mathbb{Q};<)$ such that for
$t(x):=(\alpha,\operatorname{id})f_{1}\big{(}r(x),s(x)\big{)}$ we have
$(t(y_{1})_{1},\dots,t(y_{m})_{1})=(t^{\prime}(y^{1}_{1}),\dots,t^{\prime}(y^{1}_{m}))$
(see Remark 31). Therefore, we are done if one of the disjuncts of $\psi$ of
the form $x=_{1}y$, $x<_{1}y$, or $x\neq_{1}y$ is satisfied by $t$, because
then a disjunct of $\psi^{\prime}$ of the form $x^{1}=y^{1}$, $x^{1}<y^{1}$,
or $x^{1}\neq y^{1}$ is satisfied by $t^{\prime}$. Otherwise, since $t$
satisfies $\psi$, there must be a literal of $\psi^{\prime}$ of the form
$x^{2}\neq y^{2}$. We claim that $t^{\prime}$ satisfies this literal. As $t$
satisfies $x\neq_{2}y$, we must have $r(x)\neq_{2}r(y)$ or $s(x)\neq_{2}s(y)$,
so $r^{\prime}(x^{2})\neq r^{\prime}(y^{2})$ or $s^{\prime}(x^{2})\neq
s^{\prime}(y^{2})$. Hence, $t^{\prime}(x^{2})\neq t^{\prime}(y^{2})$ by the
injectivity of $\operatorname{ll}$. $\hfill\diamond$

Note that the first statement of the proposition follows from the claim by
Theorem 38. The claim and Theorem 38 also imply that we obtain a two-
dimensional primitive positive interpretation of $\mathfrak{D}$ in
$\mathfrak{L}$, which proves the second statement of the theorem. ∎

###  4.4 Polynomial-time Algorithms

In this section we present polynomial-time solvability results for
$\operatorname{CSP}(\mathfrak{D})$ when $\mathfrak{D}$ is a first-order
expansion of $({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$ such that
$\theta_{1}(\operatorname{Pol}(\mathfrak{D}))$ and
$\theta_{2}(\operatorname{Pol}(\mathfrak{D}))$ contain sufficiently strong
polymorphisms.

######  Proposition 57.