Lemma (Finite arity test for quotient parity) — iff all 41-ary polymorphisms preserve it
ProvedConsModCount.finite_arity_testconstraint-satisfactioncounting-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1universal-algebra
Let be a finite template on a finite nonempty set containing every unary subset, a three-element set and . Then
Since is finite, this makes decidable.
Differences from the source: none.
Preamble
import Definitions.Def_ConsModCount_Balance import Definitions.Def_ConsModCount_Polymorphism set_option autoImplicit false
Formal statement
namespace ConsModCount
/-- **Lemma (Finite arity test for quotient parity)** (Xie, *Conservative Modular Counting at Every Odd Prime*, STOC 2027 submission (manuscript sha256 c673b4cc…), §13, p.23, PDF p.24). Under the standing
assumption of §§10–13 (`H` conservative): a given relation `Q_C` belongs to `pp(H)` if and only if
every 41-ary polymorphism of `H` preserves `Q_C`. -/
theorem finite_arity_test {D : Type} [Fintype D] [DecidableEq D] [Nonempty D] (H : Template D) (hH : Conservative H)
(C : Finset D) (d : D) (hC : C.card = 3) (hd : d ∈ C) :
PPDefinable H (Q C d) ↔
∀ f : (Fin 41 → D) → D, IsPolymorphism H f → Preserves f (Q C d) := by sorry
end ConsModCount
Source
Xie, Conservative Modular Counting at Every Odd Prime, STOC 2027 submission (manuscript sha256 c673b4cc58550963462480168a22eca7184c16aebf1faa02497d68c5a46d876a), §13, Lemma (Finite arity test for quotient parity), p.23 (PDF p.24)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.