Recognizing Linear and Regular Mal'tsev Conditions in Finite Algebras: EXPTIME Classification, Retracts, and Height-One Frontiers

A strong Mal'tsev condition is linear if each side of each identity is a variable or one symbol applied to variables, and regular if both sides of each identity contain the same variables. We prove that for every linear condition Σ that has a nontrivial model and whose anchored part is not satisfied by projections, deciding whether a finite algebra given by its operation tables satisfies Σ is EXPTIME-complete, even over a fixed signature of binary operations. This covers Mal'tsev and majority terms, answering both cases of Problem 9.4 of Freese and Valeriote, near-unanimity and edge terms of fixed arity, and Jónsson, Gumm and Hagemann–Mitschke chains of fixed length. It is also EXPTIME-complete to decide whether an algebra has a cube term, as conjectured by Kazda and Zhuk, or a near-unanimity term of some arity. For regular conditions we prove EXPTIME-completeness whenever the condition is not satisfied by projections and a constant (for idempotent ones this also follows from work of Freese and Valeriote), and for families of algebras whenever the condition is idempotent, has a finite nontrivial model and is not satisfied by projections. Every other linear condition is decidable in polynomial time or equivalent to one of height one. Such a condition is decidable in polynomial time if it forces a constant or its symbols are at most binary, and it holds in a finite algebra if and only if its idempotent version holds in a retract of minimum size. Using this retract, we show that quasi-Mal'tsev terms and every single height-one identity in one ternary symbol can be recognized in polynomial time; in arity four, all but two can, up to symmetry, and both can on algebras with a quasi-Mal'tsev term. Finally, every hard condition for single algebras requires time 2^(εn) for some ε > 0 on algebras with n elements and O(n) basic operations, unconditionally. Apart from running times and the results cited from the literature, almost all results of the paper are formalized in Lean 4 (version 4.33.1, Mathlib commit 0df444a360ea): 18 packages with 56 source files and about 28,200 lines, checked by the Lean kernel, leanchecker and nanoda, with only the axioms propext, Classical.choice and Quot.sound. Section 14 of the paper states the exact scope. The Lean packages and the Python scripts of Section 13 are part of this record.

Authors

Institutions

Publication Details

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

Recognizing Linear and Regular Mal'tsev Conditions in Finite Algebras: EXPTIME Classification, Retracts, and Height-One Frontiers

Asterios Gkantzounis
Zenodo (CERN European Organization for Nuclear Research)
Advanced Algebra and Logic
preprint

Recognizing Linear and Regular Mal'tsev Conditions in Finite Algebras: EXPTIME Classification, Retracts, and Height-One Frontiers

Asterios Gkantzounis
preprint en

Abstract

A strong Mal'tsev condition is linear if each side of each identity is a variable or one symbol applied to variables, and regular if both sides of each identity contain the same variables. We prove that for every linear condition Σ that has a nontrivial model and whose anchored part is not satisfied by projections, deciding whether a finite algebra given by its operation tables satisfies Σ is EXPTIME-complete, even over a fixed signature of binary operations. This covers Mal'tsev and majority terms, answering both cases of Problem 9.4 of Freese and Valeriote, near-unanimity and edge terms of fixed arity, and Jónsson, Gumm and Hagemann–Mitschke chains of fixed length. It is also EXPTIME-complete to decide whether an algebra has a cube term, as conjectured by Kazda and Zhuk, or a near-unanimity term of some arity. For regular conditions we prove EXPTIME-completeness whenever the condition is not satisfied by projections and a constant (for idempotent ones this also follows from work of Freese and Valeriote), and for families of algebras whenever the condition is idempotent, has a finite nontrivial model and is not satisfied by projections. Every other linear condition is decidable in polynomial time or equivalent to one of height one. Such a condition is decidable in polynomial time if it forces a constant or its symbols are at most binary, and it holds in a finite algebra if and only if its idempotent version holds in a retract of minimum size. Using this retract, we show that quasi-Mal'tsev terms and every single height-one identity in one ternary symbol can be recognized in polynomial time; in arity four, all but two can, up to symmetry, and both can on algebras with a quasi-Mal'tsev term. Finally, every hard condition for single algebras requires time 2^(εn) for some ε > 0 on algebras with n elements and O(n) basic operations, unconditionally. Apart from running times and the results cited from the literature, almost all results of the paper are formalized in Lean 4 (version 4.33.1, Mathlib commit 0df444a360ea): 18 packages with 56 source files and about 28,200 lines, checked by the Lean kernel, leanchecker and nanoda, with only the axioms propext, Classical.choice and Quot.sound. Section 14 of the paper states the exact scope. The Lean packages and the Python scripts of Section 13 are part of this record.

Zenodo (CERN European Organization for Nuclear Research)
Technical University of Crete (GR)
Advanced Algebra and Logic
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