Finite simple groups in the primitive positive constructability poset
Abstract
Primitive positive constructions between relational structures are motivated by computational complexity of constraint satisfaction problems. They induce a partial order on equivalence classes of finite relational structures. We show that this order has an infinite third layer, given by the equivalence class of an oriented graph and of infinitely many permutation groups that are abstractly isomorphic to all the finite simple groups in a one-to-one correspondence. More concretely, the two topmost layers of the primitive positive constructability poset are known to consist of a single element each. We consider [Formula: see text], a representative of the element in the second layer, and its polymorphism clone [Formula: see text]. We show that any clone over a finite domain that admits a quasi-Maltsev operation and fully symmetric operations of all arities admits an incoming minion homomorphism from [Formula: see text]. We use this result to show that in the primitive positive contructability poset, the lower covers of [Formula: see text] are represented by the transitive tournament on three vertices and for each finite simple group by the disjoint union of all its primitive group actions.
Fields of Study & Subjects
Rings
Modules
and Algebras
Computability
Logic
AI Algorithms
Publication details
- Journal / source
- International Journal of Algebra and Computation
- Publisher
- World Scientific Pub Co Pte Ltd
- Pages
- 1–28
- Publication date
- 18 July 2026
- Language
- EN