Source-linked AI summary
The wonderland of reflections
Libor Barto, Jakub Opršal, Michael Pinsker
TL;DR
The paper addresses the limits of algebraic characterizations based on pp-interpretations alone. It extends the comparison to other CSP-relevant constructions using reflection and h1 clone homomorphisms, and gives an equivalence for ω-categorical structures that includes uniformly continuous h1 homomorphisms.
Problem
Earlier algebraic characterizations do not cover homomorphic equivalence and adding singleton relations, despite their relevance to CSP reductions.
Source: §1.1 · p. 2Method
The paper links CSP-relevant relational constructions to polymorphism-clone operators, introducing reflection as a semantic construction.
Source: §1.1 · p. 2, §4 · p. 11Results
For an at most countable ω-categorical structure and its model-complete core expanded by finitely many singleton relations, uniformly continuous h1 clone homomorphisms exist in both directions.
Source: §8 · p. 22Takeaways & Limitations
The characterization extends beyond pp-interpretations to include homomorphic equivalence and adding singleton relations.
Source: §1.1 · p. 2In the ω-categorical setting, adding constants to a model-complete core need not terminate after finitely many steps, so there is no analogous idempotent core.
Source: §1.2 · p. 4
Abstract
from arXiv · showhide
A fundamental fact for the algebraic theory of constraint satisfaction problems (CSPs) over a fixed template is that pp-interpretations between at most countable \omega-categorical relational structures have two algebraic counterparts for their polymorphism clones: a semantic one via the standard algebraic operators H, S, P, and a syntactic one via clone homomorphisms (capturing identities). We provide a similar characterization which incorporates all relational constructions relevant for CSPs, that is, homomorphic equivalence and adding singletons to cores in addition to pp-interpretations. For the semantic part we introduce a new construction, called reflection, and for the syntactic part we find an appropriate weakening of clone homomorphisms, called h1 clone homomorphisms (capturing identities of height 1). As a consequence, the complexity of the CSP of an at most countable $\omega$-categorical structure depends only on the identities of height 1 satisfied in its polymorphism clone as well as the the natural uniformity thereon. This allows us in turn to formulate a new elegant dichotomy conjecture for the CSPs of reducts of finitely bounded homogeneous structures. Finally, we reveal a close connection between h1 clone homomorphisms and the notion of compatibility with projections used in the study of the lattice of interpretability types of varieties.
1. Introduction and Main Results
The introduction seeks algebraic criteria for comparing CSPs that cover the full range of relevant relational constructions, rather than pp-interpretations alone. It develops corresponding semantic and syntactic characterizations and uses them to formulate tractability conjectures for finite and infinite structures.
1.1. The finite case.
- For finite structures, homomorphic equivalence to a pp-power captures obtaining one structure from another through the relevant relational constructions.The paper pairs this account with reflection and an h1 clone homomorphism characterization.Source: §1.1 · p. 3
- The finite tractability conjecture can be stated using h1 clone homomorphisms from the original structure's polymorphism clone to the projection clone.The introduction also relates the core-based criteria to cyclic and Siggers operations.Source: §1.1 · p. 3
1.2. The infinite case.
- For at most countable ω-categorical structures and finite targets, the relational-construction, reflection, and uniformly continuous h1 homomorphism conditions are equivalent.The relational constructions include pp-interpretation, homomorphic equivalence, and adding singleton relations.Source: §1.2 · p. 4
- The proposed dichotomy for reducts of finitely bounded homogeneous structures places a uniformly continuous h1 map to projections and polynomial-time solvability as alternatives.Unlike the finite setting, adding constants to a model-complete core need not terminate after finitely many steps.Source: §1.2 · pp. 4–5
1.3. Coloring of clones by relational structures.
- An h1 clone homomorphism into a relational structure's polymorphism clone is equivalent to colorability by that structure.The paper applies this connection to join properties of varieties defined by identities of height at most 1.Source: §1.3 · p. 5
1.4. Outline of the article.
- The article proceeds from standard definitions and relational constructions to algebraic constructions, h1 homomorphisms, the ω-categorical case, colorings, and a concluding discussion.The final section proves and discusses the introduction's results and conjectures.Source: §1.4 · p. 5
2. Preliminaries
The preliminaries introduce notation for relational structures, their polymorphism clones, and the CSP, while pointing to later sections for new notions.
2. Preliminaries
- The paper says pp-powers, the operator R, h1 clone homomorphisms, and clone colorings will be defined in later sections.It refers readers to for universal algebra and for model theory.Source: §2 · pp. 5–6
2.1. Relational structures and polymorphism clones.
- The section reserves A for a relational structure’s domain and denotes its polymorphism clone by A.The clone consists of finitary operations preserving all relations of the structure; it is closed under composition and contains all projections.Source: §2.1 · p. 6
- The CSP is introduced through membership in a class of finite structures that admit a homomorphism to the template.The passage begins this class definition but does not include its full expression.Source: §2.2 · p. 6
2.2. CSPs.
The section presents CSPs as a homomorphism-membership problem, equivalently expressible through pp-sentences, and fixes a log-space reduction convention. It also introduces the scope of at most countable ω-categorical structures.
2.2. CSPs.
- CSP(A) asks whether a finite structure C has a homomorphism to A.Equivalently, it asks whether a pp-sentence over A is true in A.Source: §2.2 · p. 6
- The paper uses log-space reductions when stating that one computational problem reduces to, or is no harder than, another.The passage says the claims also hold for other meanings of hardness.Source: §2.2 · p. 6
2.3. Notions from the infinite.
- An at most countable structure is ω-categorical when its automorphism group has finitely many orbits on A^n for every n ≥ 1.Finite structures are always ω-categorical; reducts of finitely bounded homogeneous structures are a particularly studied infinite class.Source: §2.3 · p. 6
2.4. pp definitions and interpretations.
The section defines pp-interpretation through pp-definable relations that encode a domain, equality, and the interpreted structure’s relations. It also introduces homomorphic equivalence and model-complete cores.
2.4. pp definitions and interpretations.
- A pp-interpretation maps a pp-definable subset of A^n onto B while encoding equality and each relation of B by pp-definable preimages.The required preimages include the domain of the mapping, equality on B, and every relation in B.Source: §2.4 · p. 6
- Structures with the same signature are homomorphically equivalent when there are homomorphisms in both directions.The passage also defines a model-complete core through automorphisms agreeing locally with each endomorphism.Source: §2.5 · p. 6
2.5. Homomorphic equivalence and cores.
This section describes homomorphic equivalence and cores, then gives operators for constructing function clones from other clones and specifies their action on algebras and function sets.
2.5. Homomorphic equivalence and cores.
- An at most countable ω-categorical structure has a unique ω-categorical model-complete core in its homomorphic-equivalence class.For finite structures, being a core means every endomorphism is an automorphism; adding all unary singleton relations to a finite core yields an idempotent core.Source: §2.5 · p. 7
2.6. HSP and E.
- H, S, P, and Pfin describe clone actions on quotient classes, invariant subsets, powers, and finite powers, respectively.E yields clones obtained by adding functions, and combinations such as HSP have their evident meaning.Source: §2.6 · p. 7
- For classes of algebras, P means products of algebras in the class, while E on algebras or function sets means extending the set of operations or functions.The passage distinguishes products from powers when P is applied to a class.Source: §2.6 · p. 7
2.7. Clone homomorphisms. •
Clone homomorphisms preserve arities, projections, and composition. Varieties can be ordered by clone homomorphisms, yielding the lattice of interpretability types.
2.7. Clone homomorphisms. •
- A clone homomorphism preserves arities, each projection, and composition.The notation ξ(πᵏᵢ) = πᵏᵢ expresses preservation of every coordinate projection.Source: §2.7 · p. 7
2.8. The lattice of interpretability types of varieties.
- A variety is a class of same-signature algebras closed under homomorphic images, subalgebras, and products, and HSP’s theorem characterizes varieties by identities [6].Any generator’s term-operation clone is denoted clo(V).Source: §2.8 · p. 7
- The relation V ≤ W holds when a clone homomorphism maps clo(V) to clo(W); identifying mutually related varieties gives the interpretability-type lattice.The lattice join uses the disjoint union of signatures and the union of defining identities.Source: §2.8 · p. 8
2.9. Topology.
Function clones carry the topology of pointwise convergence, with continuity and uniform continuity characterized by finite sets of inputs and outputs.
2.9. Topology.
- In the pointwise-convergence topology, a sequence of same-arity functions converges when it eventually agrees with its limit on each input tuple.Every function clone thereby gives an abstract topological clone.Source: §2.9 · p. 8
- Continuity requires finite input agreement to ensure output agreement near one function; uniform continuity requires one finite input set to work for every pair.The required output set is finite in both characterizations.Source: §2.9 · p. 8
- Polymorphism clones are exactly the function clones complete in this topology, and clones on finite domains are discrete..Source: §2.9 · p. 8
3. Relational Constructions
The section reviews the CSP reductions and shows that pp-powers together with homomorphic equivalence capture them all. It also gives an example where pp-interpretations alone do not suffice.
3.1. Classical reductions.
- The classical reductions are pp-interpretation, homomorphic equivalence, and adding a singleton unary relation to an ω-categorical model-complete core.They yield, respectively, a log-space reduction, equality of CSPs, and log-space equivalence of CSPs.Source: §3 · p. 8, §3.1 · pp. 8–9
- For countable ω-categorical structures, local homomorphic equivalence is equivalent to full homomorphic equivalence by compactness.Maps from every finite substructure in both directions suffice for CSP equality.Source: §3.1 · p. 8
3.2. pp-powers.
- A pp-power is an isomorphic copy on Aⁿ whose relations are pp-definable from A.The pp-power formulation combines the classical reductions with homomorphic equivalence.Source: §3.2 · p. 9
- Adding a singleton relation to a model-complete core is already covered by homomorphic equivalence and pp-interpretations.The singleton’s automorphism orbit is pp-definable, enabling a pp-power homomorphically equivalent to the expanded structure.Source: §3.2 · p. 10
- B can be pp-constructed from A exactly when B is homomorphically equivalent to a pp-power of A.For at most countable ω-categorical structures, pp-constructability yields a log-space reduction from CSP(B) to CSP(A).Source: §3.2 · p. 10
- Two finite idempotent structures show that homomorphic equivalence to a pp-power can hold even when pp-interpretability fails.The obstruction uses a two-block kernel whose pp-definable blocks would contradict that every pp-definable relation has cardinality a power of 4.Source: §3.2 · p. 11
4. Algebraic Constructions
Reflection is introduced as an algebraic counterpart to homomorphic equivalence. The section relates relational constructions to reflection and characterizes pp-constructability with algebraic operators.
4. Algebraic Constructions
- A reflection of A is formed using maps h1 from B to A and h2 from A to B to induce B’s operations; it is a retraction when h2 composed with h1 is the identity on B.For function clones, a reflection need not remain a clone because it may lack projections or closure under composition.Source: §4 · p. 11
- Reflection generalizes homomorphic images and subalgebras, is transitive, and is preserved by products.The corresponding reflection closures with H, S, and P or Pfin equal closure under those operators together with R.Source: §4 · p. 12
- For at most countable ω-categorical structures, being homomorphically equivalent to a pp-power corresponds to the algebraic class ERPfin A.The proposition relates pp-definability, pp-powers, and pp-interpretability to E, EPfin, and EHSPfin, respectively.Source: §4 · pp. 12–13
- For at most countable ω-categorical structures, B is pp-constructible from A exactly when B belongs to ERPfin A; then CSP(B) is log-space reducible to CSP(A).The characterization combines reflection, expansion, retraction, and finite products.Source: §4 · p. 13
5. Linear Birkhoff
The section characterizes reflection and products syntactically using weakenings of clone homomorphisms that preserve identities of height 1. It extends Birkhoff-style correspondences from all identities to height-1 identities.
5. Linear Birkhoff
- An h1 clone homomorphism preserves identities of height 1, while a strong h1 clone homomorphism also preserves every projection.Height-1 identities equate terms consisting of a single operation applied to variables; height at most 1 also includes variable-to-variable identities.Source: §5 · pp. 13–14
- B ∈ ERP(A) exactly when there is an h1 clone homomorphism from A to B; for finite clones, P can be replaced by Pfin.The corresponding characterizations are B ∈ EHSP(A) via a clone homomorphism and B ∈ ERretP(A) via a strong h1 clone homomorphism.Source: §5 · p. 14
- The proof builds a componentwise action on tuples and uses a map onto B to realize the image clone as a retraction or reflection of that action.When projections are preserved, the map is a retraction; without that condition, it yields a reflection.Source: §5 · pp. 14–15
- A class of algebras is closed under R and P exactly when it is axiomatized by identities of height 1; closure under Rret and P corresponds to identities of height at most 1.This is the section’s analogue of Birkhoff’s HSP theorem.Source: §5 · p. 15
6. Topological Linear Birkhoff
The section extends the algebraic characterizations to topological function clones, where continuity conditions control when infinite powers can be replaced by finite ones. It gives finite-target criteria and a route to infinite-target results under symmetry and orbit conditions.
6.1. Finite goal structures.
- B ∈ EHSPfin(A) exactly when a uniformly continuous clone homomorphism A → B exists, provided B’s domain is finitely generated; for finite B, B ∈ ERPfin(A) exactly when such a map is uniformly continuous and h1.Finiteness is required in the second criterion because the map need not preserve identities, so the proof cannot use the generating process.Source: §6.1 · p. 16
- The finite-generation condition can be necessary: enough disjoint copies of a transformation-monoid action yield an isomorphic monoid outside HSPfin by domain cardinality.The same obstruction applies to clones whose functions depend on at most one variable.Source: §6.1 · pp. 16–17
6.2. Continuity versus uniform continuity.
- For a polymorphism clone of a countable ω-categorical structure, every continuous map preserving outside composition with invertibles is uniformly continuous.The result supplies the uniformity needed for the finite-target characterizations.Source: §6.1 · p. 16, §6.2 · p. 17
- A continuous map from such a clone to a finite-domain clone that preserves height-1 identities modulo outer invertibles places the target in ERPfin(A).The paper notes that R need not preserve identities of height 1 modulo outer invertibles, so this result does not give a matching equivalence.Source: §6.2 · p. 18
6.3. Infinite goal structures.
- For infinite targets, uniform continuity, preservation of height-1 identities modulo inner invertibles, and finitely many orbits of the image invertibles on B imply B ∈ ERPfin(A).Strong h1 clone homomorphisms satisfying the inner-invertible condition send invertibles to invertibles.Source: §6.3 · pp. 18–19
- For at most countable ω-categorical structures, a uniformly continuous map with the inner-invertible identity and finite-orbit conditions makes B pp-constructible from A.The section’s construction represents the image clone as a reflection of an action on a finite power.Source: §6.3 · p. 19
7. Coloring of clones by relational structures
The section connects relational colorings of clones with h1 clone homomorphisms, then uses this connection to translate algebraic properties of varieties into colorability criteria. It also gives closure results for colorings under joins of varieties.
7. Coloring of clones by relational structures
- A variety is congruence n-permutable exactly when its term clone is not strongly colorable by ({0, 1}; ≤); congruence modularity has the analogous criterion using D.D has four elements and the three equivalence relations specified in Proposition 7.3.Source: §7 · p. 20
- A function clone is B-colorable exactly when there is an h1 clone homomorphism from it to the polymorphism clone of B.A coloring maps the lifted structure on FA(B) to B while preserving its relations; a strong coloring additionally fixes the projections.Source: §7 · pp. 20–21
- Congruence n-permutability and congruence modularity correspond to the absence of strong h1 clone homomorphisms to the respective polymorphism clones.The targets are the polymorphism clone of ({0, 1}; ≤) and that of D, respectively.Source: §7 · pp. 20–21
- If a variety is defined by height-1 identities and its term clone has an h1 clone homomorphism to B, then it has a clone homomorphism to B.The same implication holds for identities of height at most 1 and strong h1 clone homomorphisms.Source: §7 · p. 21
- For varieties defined by height-1 identities, B-colorability of both term clones implies B-colorability of their join; the strong version holds for height-at-most-1 identities.The strong version assumes both term clones are strongly B-colorable.Source: §7 · p. 22
8. Back to the Introduction
The section connects the paper’s equivalences and conjectures to its introduction, including uniformly continuous h1 clone homomorphisms between a structure and an expanded model-complete core. It also records open questions about reversing a conjectural implication and about expansions by constants.
8. Back to the Introduction
- Theorem 1.4’s items (i)–(iv) are equivalent to their primed versions, with Taylor’s theorem connecting failure of a clone homomorphism to non-trivial height 1 identities.Theorem 1.8’s statements (i)–(iii) are also linked by the cited corollaries and proposition.Source: §8 · p. 22
- For an at most countable ω-categorical structure A, its model-complete core expanded by finitely many singleton unary relations has uniformly continuous h1 clone homomorphisms both to and from A.This is Corollary 8.1.Source: §8 · p. 22
- The old Conjecture 1.7 implies the new Conjecture 1.9, but the paper leaves open whether the reverse implication holds.The authors note that resolving the reverse implication could provide an approach to disproving Conjecture 1.7.Source: §8 · p. 22
- Problem 8.3 asks whether a uniformly continuous h1 clone homomorphism from A to the projection clone entails a homomorphism from the polymorphism clone of a finite-constant expansion of its core.The problem specifies A as a reduct of a finitely bounded homogeneous structure and its model-complete core B.Source: §8 · p. 22
- The coloring results in Section 1.3 are identified with Proposition 7.4 and consequences of Corollary 7.6 and Propositions 7.2 and 7.3.The passage identifies the results’ sources without restating their content.Source: §8 · p. 22
- The paper relates h1 clone homomorphisms to Maltsev conditions by asking whether each target clone admits an upward-directed class of clones capturing those homomorphisms.Related results find such classes for congruence permutability and n-permutability, while existence for every clone remains a question.Source: §8 · pp. 22–23