A constraint satisfaction problem asks whether a given conjunction of constraints, each a relation of a fixed finite structure , has a solution. The algebraic approach to its complexity studies the polymorphisms of , the operations preserving all of its relations. Bulatov, Jeavons and Krokhin (SIAM J. Comput. 2005) showed that is NP-complete unless the idempotent polymorphisms generate a Taylor variety, and conjectured that it is solvable in polynomial time in the Taylor case. Proving the hardness side and attacking the tractable side both need structural theorems about finite algebras in Taylor varieties. Timeline:
This mission formalizes the absorption theory and the cyclic-term theorem of Barto–Kozik 2012.
An algebra is a set with finitary basic operations of a fixed signature ; a term operation is an operation given by a term in variables . A subuniverse is a subset closed under all basic operations. Products and powers carry the coordinatewise operations, so a subuniverse of is itself an algebra. is subdirect () if both projections are onto, and linked if any two elements of its first projection are connected by a chain where consecutive elements have a common -neighbour .
An algebra is idempotent if every basic operation satisfies . A -ary term is a Taylor term if for every an identity holds with all , and . A Taylor variety is an idempotent variety with a Taylor term.
A subuniverse absorbs , written , if some term operation satisfies whenever all but at most one lie in . It is proper if , and a minimal absorbing subuniverse, , if , and no proper subalgebra of absorbs . A digraph is smooth if every vertex has an incoming and an outgoing edge. An oriented path has algebraic length equal to its number of forward edges minus its number of backward edges, and has algebraic length if some vertex is joined to itself by an oriented path of algebraic length . A -ary term () is cyclic if it is idempotent and ; a relation is cyclic if it is closed under this rotation of tuples.
Let be a finite idempotent algebra and the variety it generates. Then the following are equivalent:
This characterizes finitely generated Taylor varieties by a single identity, . The substantial implication is Thm 4.2 (a milestone); the others hold because a cyclic term is a Taylor term.
The result itself. Thm 4.1 gives the identity form of the Bulatov–Jeavons–Krokhin conjecture, which is now the theorem of Bulatov and Zhuk: a finite structure has a tractable CSP iff it has a cyclic polymorphism. In Barto–Kozik it also yields short proofs of the Hell–Nešetřil theorem and of the Maróti–McKenzie weak near-unanimity theorem. The Absorption Theorem and the properties of minimal absorbing subuniverses are the basic tools of later work on absorption, including Zhuk's dichotomy proof.
Formalizing it. The results are proved. To our knowledge none of them has a machine-checked proof; the Prove2Me library has no absorption or Taylor-term development. This mission builds a reusable Lean library on Mathlib's model theory: absorption, linkedness, minimal absorbing subuniverses, the loop lemma, and cyclic relations.
The obvious attempt at Thm 4.2, the substantial direction of the goal, composes a Taylor term with itself until it becomes cyclic, and it fails because Taylor identities do not determine the term on most tuples. Barto–Kozik instead reduce to cyclic relations (Lemma 4.4) and pick a minimal counterexample. That needs every milestone for arbitrary finite algebras of the variety, including subalgebras of powers and quotients. The Absorption Theorem is an induction over sets of common neighbours driven by the term of Prop 2.7. The Loop Lemma is an induction on that juggles smooth parts, weak components, algebraic lengths and absorption at once. Bookkeeping for terms over products and powers, and for oriented paths, is heavy in Lean.
L : FirstOrder.Language with [L.IsAlgebraic]; algebras are L.Structures on types with [Finite _]. The paper's signatures are finite; the Lean statements allow any signature, since they involve only term operations.TaylorDatum L is a term t : L.Term (Fin k) with patterns σ j, τ j : Fin k → Bool (false , true , σ j j = false, τ j j = true). IsTaylorAlg T A says that is idempotent and satisfies the identities t(σ j) ≈ t(τ j). These algebras form the Taylor variety axiomatized by those identities, and every algebra of a Taylor variety satisfies such a datum. "Finite algebras in a Taylor variety" means finite algebras satisfying one common datum T. Idempotency is imposed on basic operations, so a nullary symbol forces . Degenerate data are harmless: a Taylor term of arity or , combined with idempotency, also forces .A × B carries the coordinatewise structure prodStructure. Subuniverses of and are L.Substructures, and the algebra is ↥R with Mathlib's induced structure. Subuniverses of are sets of Fin k → A closed coordinatewise (IsSubpower). The rotation is x ∘ finRotate k, i.e. .IsAbsorbing L B includes closure of ; MinAbsorbing requires nonemptiness. In Prop 2.7 the term has positive arity, which rules out a vacuous nullary witness. In Thm 3.6 the absorbing is nonempty, as in the paper's use. Algebraic length is the inductive relation Walk E a b z.∃ T, IsTaylorAlg T A, since is idempotent and satisfies exactly the identities of .namespace BKAbsorption
variable {L : FirstOrder.Language.{u, v}} [L.IsAlgebraic]
/-- Barto–Kozik, Theorem 4.1. Let `A` be a finite idempotent algebra (so the variety `V(A)` it
generates is idempotent and satisfies exactly the identities of `A`). The following are
equivalent:
* `V(A)` is a Taylor variety, i.e. `A` satisfies the identities of some Taylor term;
* `A` has a cyclic term operation (of some arity `k ≥ 2`);
* `A` has a cyclic term operation of arity `p` for every prime `p > |A|`. -/
theorem taylor_iff_cyclic {A : Type w} [L.Structure A] [Finite A] (hid : IsIdempotent L A) :
((∃ T : TaylorDatum L, IsTaylorAlg T A) ↔ ∃ k : ℕ, 2 ≤ k ∧ HasCyclicTermOp L A k) ∧
((∃ k : ℕ, 2 ≤ k ∧ HasCyclicTermOp L A k) ↔
∀ p : ℕ, p.Prime → Nat.card A < p → HasCyclicTermOp L A p) := by sorry
end BKAbsorptionis a signature without relation symbols and a finite idempotent algebra ( for every basic operation), so the variety generated by is idempotent and satisfies exactly the identities of . The following are equivalent: (1) is a Taylor variety, i.e. satisfies the identities of some Taylor term ( of arity with, for each , , , , ); (2) has a cyclic term operation of some arity (an idempotent term operation with ); (3) has a cyclic term operation of arity for every prime .
No open leaves. Every sub-goal is proved or awaiting decomposition.