Ross Willard

This is the first of three papers motivated by the author’s desire to understand and explain “algebraically” one aspect of Dmitriy Zhuk’s proof of the CSP Dichotomy Theorem. In this paper, we study abelian congruences in varieties having a weak difference term. Each class of the congruence supports an abelian group structure; if the congruence is minimal, each class supports the structure of a vector space over a division ring determined by the congruence. A construction due to J. Hagemann, C. Herrmann and R. Freese in the congruence modular setting extends to varieties with a weak difference term, and provides a “universal domain” for the abelian groups or vector spaces that arise from the classes of the congruence within a single class of the centralizer of the congruence. The construction also supports an extension of Freese’s similarity relation (between subdirectly irreducible algebras) from the congruence modular setting to varieties with a weak difference term.

There is a gap in our proof [Trans. Amer. Math. Soc. 368 (2016), pp. 2115–2143, Lemma 6.2]. We direct readers to a paper that fills the gap.

We extend the validity of Kiss's characterization of the commutator from congruence modular varieties to varieties with a difference term. This fixes a recently discovered gap in our paper [A finite basis theorem for difference-term varieties with a finite residual bound, Trans. Amer. Math. Soc., 368 (2016), 2115--2143]. We also prove some related properties of Kiss terms in varieties with a difference term.

The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable if the model-complete core of the template has a pseudo-Siggers polymorphism, and NP-complete otherwise. One of the important questions related to the dichotomy conjecture is whether, similarly to the case of finite structures, the condition of having a pseudo-Siggers polymorphism can be replaced by the condition of having polymorphisms satisfying a fixed set of identities of height 1, i.e., identities which do not contain any nesting of functional symbols. We provide a negative answer to this question by constructing for each non-trivial set of height 1 identities a structure within the range of the conjecture whose polymorphisms do not satisfy these identities, but whose CSP is tractable nevertheless. An equivalent formulation of the dichotomy conjecture characterizes tractability of the CSP via the local satisfaction of non-trivial height 1 identities by polymorphisms of the structure. We show that local satisfaction and global satisfaction of non-trivial height 1 identities differ for $\omega$-categorical structures with less than doubly exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures.

The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable if the model-complete core of the template has a pseudo-Siggers polymorphism, and is NP-complete otherwise. One of the important questions related to the dichotomy conjecture is whether, similarly to the case of finite structures, the condition of having a pseudo-Siggers polymorphism can be replaced by the condition of having polymorphisms satisfying a fixed set of identities of height 1, i.e., identities which do not contain any nesting of functional symbols. We provide a negative answer to this question by constructing for each nontrivial set of height 1 identities a structure within the range of the conjecture whose polymorphisms do not satisfy these identities, but whose CSP is tractable nevertheless. An equivalent formulation of the dichotomy conjecture characterizes tractability of the CSP via the local satisfaction of nontrivial height 1 identities by polymorphisms of the structure. We show that local satisfaction and global satisfaction of nontrivial height 1 identities differ for ω \omega -categorical structures with less than doubly exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures.

The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable when the model-complete core of the template has a pseudo-Siggers polymorphism, and NP-complete otherwise. One of the important questions related to this conjecture is whether, similarly to the case of finite structures, the condition of having a pseudo-Siggers polymorphism can be replaced by the condition of having polymorphisms satisfying a fixed set of identities of height 1, i.e., identities which do not contain any nesting of functional symbols. We provide a negative answer to this question by constructing for each non-trivial set of height 1 identities a structure whose polymorphisms do not satisfy these identities, but whose CSP is tractable nevertheless. An equivalent formulation of the dichotomy conjecture characterizes tractability of the CSP via the local satisfaction of non-trivial height 1 identities by polymorphisms of the structure. We show that local satisfaction and global satisfaction of non-trivial height 1 identities differ for $\omega$-categorical structures with less than double exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures.