2021/09/05 by Alexandr Kazda, Kazda, Alexandr, Michael Kompatscher +1
Mathematics · #03C05 #08A70 #20B05 #Advanced Algebra and Geometry #Advanced Topics in Algebra #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Finite Group Theory Research #Rings and Algebras (math.RA)
paper · pdf · doi:10.48550/arxiv.2109.02065
openalex publication_date 2021/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
For some Maltsev conditions Σ it is enough to check if a finite algebra \mathbf A satisfies Σ locally on subsets of bounded size, in order to decide, whether \mathbf A satisfies Σ (globally). This local-global property is the main known source of tractability results for deciding Maltsev conditions. In this paper we investigate the local-global property for the existence of a G-term, i.e. an n-ary term that is invariant under permuting its variables according to a permutation group G ≤ Sym(n). Our results imply in particular that all cyclic loop conditions (in the sense of Bodirsky, Starke, and Vucaj) have the local-global property (and thus can be decided in polynomial time), while symmetric terms of arity n>2 fail to have it.