Affine Hierarchies: Exact Coefficient Heights and Algebraic Completeness

When does bounded affine consistency recover a global solution of a constraint satisfaction problem? We determine its arithmetic cost, prove completeness for all finite nilpotent Mal'cev templates, and show that the second level solves every conservative Mal'cev template. For the full saturated hierarchy, the least level mapping affine coefficients modulo M to those modulo N is infinite if a prime of N is absent from M, and otherwise equals the maximum over primes p dividing N of p^max{v_p(N) − v_p(M), 0}. This answers the higher-power questions of Barto, Hadek, and Zhuk. Conditional amplification of matching designs and integral divided-power invariants also give exact arithmetic Nullstellensatz degrees. Explicit certificates determine the full imbalance-eight profile over commutative rings with 2⋅1_R not in 4R, and its first eight multiplier degrees over F_2. Every nilpotent Mal'cev template on n > 1 elements is solved at saturated level at most n^(log_2 3)/3, independently of relation arity, over the integers and finite coefficient rings containing all domain primes. For full finite-group coset languages, nilpotence is also necessary: nonnilpotent groups have sparse unsatisfiable ternary instances surviving every sublinear level over every nonzero unital ring. Cohomological consistency of width three rejects these instances. For class-two groups, the full coset language of arity at least four has exact level one or two according to commutator parity, over the integers and finite rings whose characteristic is a multiple of the group exponent. For templates promised to consist of cosets of a group of class at most two, the integer bound gives a uniform polynomial-time promise algorithm that also constructs a Mal'cev polymorphism, although the group is not supplied. An affine-cocycle argument gives exact binary level 2^(s−1) for generalized dihedral two-groups with rotation exponent 2^s. The group results transfer to isomorphism of coloured structures with bounded colour classes. Every conservative Mal'cev template is solved at saturated level two modulo two, uniformly in its domain, arities, and algebraic depth. This optimal bound yields a uniform ⊕L promise algorithm even when the template is part of an explicitly tabulated input. For all Mal'cev templates, finite affine completeness in two coprime characteristics is equivalent to bounded width. A minimum twelve-element nilpotent algebra has no supernilpotent Mal'cev term reduct, answering Mayr's question, yet its entire compatible language admits basic rounding modulo six.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-19
DOI
https://doi.org/10.5281/zenodo.24368756
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Affine Hierarchies: Exact Coefficient Heights and Algebraic Completeness

Asterios Gkantzounis
Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
preprint

Affine Hierarchies: Exact Coefficient Heights and Algebraic Completeness

Asterios Gkantzounis
preprint en

Abstract

When does bounded affine consistency recover a global solution of a constraint satisfaction problem? We determine its arithmetic cost, prove completeness for all finite nilpotent Mal'cev templates, and show that the second level solves every conservative Mal'cev template. For the full saturated hierarchy, the least level mapping affine coefficients modulo M to those modulo N is infinite if a prime of N is absent from M, and otherwise equals the maximum over primes p dividing N of p^max{v_p(N) − v_p(M), 0}. This answers the higher-power questions of Barto, Hadek, and Zhuk. Conditional amplification of matching designs and integral divided-power invariants also give exact arithmetic Nullstellensatz degrees. Explicit certificates determine the full imbalance-eight profile over commutative rings with 2⋅1_R not in 4R, and its first eight multiplier degrees over F_2. Every nilpotent Mal'cev template on n > 1 elements is solved at saturated level at most n^(log_2 3)/3, independently of relation arity, over the integers and finite coefficient rings containing all domain primes. For full finite-group coset languages, nilpotence is also necessary: nonnilpotent groups have sparse unsatisfiable ternary instances surviving every sublinear level over every nonzero unital ring. Cohomological consistency of width three rejects these instances. For class-two groups, the full coset language of arity at least four has exact level one or two according to commutator parity, over the integers and finite rings whose characteristic is a multiple of the group exponent. For templates promised to consist of cosets of a group of class at most two, the integer bound gives a uniform polynomial-time promise algorithm that also constructs a Mal'cev polymorphism, although the group is not supplied. An affine-cocycle argument gives exact binary level 2^(s−1) for generalized dihedral two-groups with rotation exponent 2^s. The group results transfer to isomorphism of coloured structures with bounded colour classes. Every conservative Mal'cev template is solved at saturated level two modulo two, uniformly in its domain, arities, and algebraic depth. This optimal bound yields a uniform ⊕L promise algorithm even when the template is part of an explicitly tabulated input. For all Mal'cev templates, finite affine completeness in two coprime characteristics is equivalent to bounded width. A minimum twelve-element nilpotent algebra has no supernilpotent Mal'cev term reduct, answering Mayr's question, yet its entire compatible language admits basic rounding modulo six.

Zenodo (CERN European Organization for Nuclear Research)
Technical University of Crete (GR)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon