From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
Chenghua Liu, Boning Meng
cs.CC
Aug 14, 2026 · v2
TL;DR
The authors formalized the decidability and structural proofs in Lean; during formalization they found a gap in a corollary of Young's isomorphism theorem and repaired it.
Abstract
In a landmark JACM paper recognized with the 2021 Gödel Prize, Cai and Chen established a complexity dichotomy for counting CSPs over arbitrary finite domains with algebraic complex weights. Their tractability criterion consists of three conditions on the infinite family of functions obtained from CSP instances by summing out some variables: the Block Orthogonality and Type Partition conditions, and a Mal'tsev polymorphism condition on support and row-equivalence relations. They left open whether this criterion is decidable from the finite set of constraint functions. We resolve this question by giving a total exact algorithm for every $q$-element domain ($q\ge 1$), with algebraic weights encoded exactly. We also prove that the Block Orthogonality condition implies the other two conditions, reducing the tractability criterion to a single structural property. We obtain similar decidability and structural results for Lin's tractability criterion for $\#\mathrm{CSP}^{d}$, where each variable occurs a multiple of $d$ times. Our method first shows that every failure of Block Orthogonality can be witnessed by a generated function of arity at most $q^2+1$. At each such arity, we reduce checking infinitely many generated functions to finitely many exact algebraic tests, using tensor products and a pinned extension of Young's all-instance isomorphism theorem. For the structural implication, we use powers of generated functions to control complex cancellation and construct functions whose supports encode row equivalence. These constructions yield the Type Partition and Mal'tsev polymorphism conditions.
Problem
Cai and Chen's Gödel Prize-winning dichotomy for complex-weighted counting CSPs uses a tractability criterion made of three conditions (Block Orthogonality, Type Partition, Mal'tsev). The conditions range over an infinite family of generated functions, and Cai and Chen left open whether the criterion is decidable.
Approach
Any failure of Block Orthogonality is shown to have a witness among generated functions of arity at most q^2+1. At each such arity, the condition is expressed as polynomial identities, which are decided using multiplicative characters, tensor products, and a pinned all-instance extension of Young's isomorphism theorem. Powers of generated functions control cancellation and realize row equivalence as supports, which yields the Mal'tsev and Type Partition conditions. The proof was formalized in Lean with AI assistance.
Results
The paper gives a total exact algorithm that decides the criterion for every q-element domain, and proves that Block Orthogonality alone implies the full criterion. Analogous results hold for Lin's #CSP^d criterion. The Lean formalization exposed and led to the repair of a gap involving a corollary of Young's theorem, for which an explicit counterexample is given.