Modular Counting over 3-Element and Conservative Domains

Bulatov, Andrei A.; Kazeminia, Amirhossein

doi:10.4230/LIPIcs.STACS.2026.22

Modular Counting over 3-Element and Conservative Domains

Andrei A. Bulatov Simon Fraser University, Burnaby, Canada Amirhossein Kazeminia University of Oxford, UK

Abstract

In the Constraint Satisfaction Problem (CSP for short) the goal is to decide the existence of a homomorphism from a given relational structure ${\mathcal{G}}$ to a given relational structure ${\mathcal{H}}$ . If the structure ${\mathcal{H}}$ is fixed and ${\mathcal{G}}$ is the only input, the problem is denoted ${\rm CSP}({\mathcal{H}})$ . In its counting version, $\#{\rm CSP}({\mathcal{H}})$ , the task is to find the number of such homomorphisms. The CSP and $\#{\rm CSP}$ have been used to model a wide variety of combinatorial problems and have received a tremendous amount of attention from researchers from multiple disciplines.

In this paper we consider the modular version of the counting CSPs, that is, problems of the form $\#_{p}{\rm CSP}({\mathcal{H}})$ of counting the number of homomorphisms to ${\mathcal{H}}$ modulo a fixed prime number $p$ . Modular counting has been intensively studied during the last decade, although mainly in the case of graph homomorphisms. Here we continue the program of systematic research of modular counting of homomorphisms to general relational structures. The main results of the paper include a new way of reducing modular counting problems to smaller domains and a study of the complexity of such problems over 3-element domains and over conservative domains, that is, relational structures that allow to express (in a certain exact way) every possible unary predicate.

Keywords and phrases:

Constraint Satisfaction Problem, Modular Counting

Funding:

Andrei A. Bulatov: This research is supported by a NSERC Discovery Grant.

Amirhossein Kazeminia: UKRI EP/X024431/1.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Problems, reductions and completeness ; Theory of computation

\rightarrow

Constraint and logic programming

Editors:

Meena Mahajan, Florin Manea, Annabelle McIver, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The Constraint Satisfaction Problem.

In a Constraint Satisfaction Problem (CSP) the goal is to decide the existence of a homomorphism from a given relational structure ${\mathcal{G}}$ to a given relational structure ${\mathcal{H}}$ , [27]. If the target structure is fixed and only ${\mathcal{G}}$ is the input, the problem called a nonuniform CSP and is denoted by ${\rm CSP}({\mathcal{H}})$ , [27]. CSPs and nonuniform CSPs in particular have been used to model a wide variety of combinatorial problems across many disciplines. The complexity of problems of the form ${\rm CSP}({\mathcal{H}})$ for finite relational structures has been thoroughly investigated [37, 15, 2, 11, 36, 10, 48].

In the counting version of the CSP, denoted by $\#{\rm CSP}$ (or $\#{\rm CSP}({\mathcal{H}})$ if we are dealing with a nonuniform problem), the goal is to find the number of homomorphisms from a given structure ${\mathcal{G}}$ to a given structure ${\mathcal{H}}$ , or in the case of a nonuniform problem to a fixed structure ${\mathcal{H}}$ . Counting CSPs have received much attention starting from the seminal work of Valiant [46, 45], to the classification of Boolean [21] counting CSPs and those over graphs [22], to the discovery of the algebraic method for such problems [12], to a complexity classification of unweighted counting CSPs [8, 23], to a sequence of results on weighted counting CSPs [24, 13, 32, 18, 20, 19] culminating at a complete characterization of counting CSPs with complex weights by Cai and Chen [17]. In all the research mentioned above the goal is “exact” counting, that is, finding the exact number of (weighted) homomorphisms between relational structures. Approximate counting is another vast area of research that we do not touch in this paper. Statistical Physics often concerns with the problem of computing partition functions that is closely related to counting CSPs. In this paper we consider another variation of counting problems, counting modulo an integer.

The complexity class the Counting ${\rm CSP}$ belongs to is $\#P$ , the class of problems of counting accepting paths of polynomial time nondeterministic Turing machines. There are several ways to define reductions between counting problems, but the most widely used ones are parsimonious reductions and Turing (polynomial time) reductions. A parsimonious reduction from a counting problem $\#A$ to a counting problem $\#B$ is an algorithm that, given an instance $I$ of $\#A$ produces (in polynomial time) an instance $I^{\prime}$ of $\#B$ such that the answers to $I$ and $I^{\prime}$ are equal. A Turing (or polynomial time) reduction is a polynomial time algorithm that solves $\#A$ using $\#B$ as an oracle.

Modular counting.

While the complexity of and algorithms for exact counting are now well understood, counting modulo an integer has received much attention in the past decade. For an integer $k$ and a relational structure ${\mathcal{H}}$ the problem of counting homomorphisms from a given relational structure to ${\mathcal{H}}$ modulo $k$ is denoted by $\#_{k}{\rm CSP}({\mathcal{H}})$ . Here (and in almost all papers on the subject) the focus is on prime moduli $p$ .

One of the most important features of relational structures affecting the complexity of the corresponding modular counting CSP is the automorphism group, $\mathsf{Aut}({\mathcal{H}})$ , of ${\mathcal{H}}$ . Indeed, it can be easily shown that if $\pi\in\mathsf{Aut}({\mathcal{H}})$ has order $p$ (or is a $p$ -automorphism), then $\#_{p}{\rm CSP}({\mathcal{H}})$ is equivalent, i.e., parsimoniously interreducible, with $\#_{p}{\rm CSP}({\mathcal{H}}^{\pi})$ , where ${\mathcal{H}}^{\pi}$ denotes the substructure of ${\mathcal{H}}$ induced by the set $\mathsf{Fix}(\pi)$ of the fixed points of $\pi$ . Clearly, such a reduction by $p$ -automorphisms can be repeated until the resulting structure is $p$ -rigid, that is, has no $p$ -automorphisms. Such a derivative $p$ -rigid structure is unique up to an isomorphism, as it is shown in [26], and will be denoted by ${\mathcal{H}}^{*p}$ .

A related problem that will be important in this paper is computing partition functions. Let $M$ be a $k\times k$ -matrix with entries from (in the most general case) a semiring ${\mathbb{S}}$ . Let ${\rm EVAL}(M)$ denote the problem of computing the function

Z_{M}(G)=\sum_{\varphi:V\to[k]}\prod_{(u,v)\in E}M[\varphi(u),\varphi(v)]

for a given (di)graph $G=(V,E)$ , called the partition function of $G$ . The complexity of ${\rm EVAL}(M)$ has been extensively studied in Statistical Physics and Theoretical Computer Science, see [47, 4, 14] for some samples. In the case of real or complex matrices the complexity of exact computing of partition functions is well understood [14, 18]. The case of matrices over a finite field that arises from modular counting is wide open and presents challenges that can be glimpsed from the “cancellation phenomenon” observed in [32, 17] and produced by elements of the field of a finite multiplicative order.

Existing results.

A systematic research on modular counting was initiated by Faben in [25], who introduced the complexity classes $\#_{p}P$ of problems of counting, modulo $p$ , accepting paths of polynomial time Turing machines. In the same paper he also proved some key hardness results and gave a complexity classification of $\#_{p}{\rm CSP}({\mathcal{H}})$ for 2-element structures ${\mathcal{H}}$ into polynomial time solvable and $\#_{p}P$ -complete ones. The notion of reduction between modular counting problems is similar to that for exact counting: it is either polynomial time reduction, in the same sense as before, or parsimonious reductions, where the answers to the two instances must be equal modulo $p$ .

Since then most of the effort has been directed at problems $\#_{p}{\rm CSP}({\mathcal{H}})$ where ${\mathcal{H}}$ is a graph. Faben and Jerrum [26] investigated the case when $p=2$ and ${\mathcal{H}}$ is a tree, and, apart from classifying the complexity of the problem in this case, they also posed a conjecture stating that if ${\mathcal{H}}$ is a $p$ -rigid graph, $\#_{p}{\rm CSP}({\mathcal{H}})$ has the same complexity as the exact counting problem $\#{\rm CSP}({\mathcal{H}})$ . In a series of papers [31, 30, 33, 43, 28, 40] the Faben–Jerrum conjecture was confirmed for a number of graph classes and values of $p$ , and then was proved in full generality by Bulatov and Kazeminia in [16].

While modular counting of graph homomorphisms provides some insight into the more general case, many of the complications do not occur in that case as it was demonstrated in [41]. As we will be using some of the results from this paper, we discuss it in some detail. The first observation is that the more general version of the Faben–Jerrum conjecture is not true for general relational structures: for any prime $p$ there exists a $p$ -rigid structure ${\mathcal{H}}$ such that $\#{\rm CSP}({\mathcal{H}})$ is #P-complete, but $\#_{p}{\rm CSP}({\mathcal{H}})$ is polynomial time solvable. This can be fixed to some extent by introducing and exploiting multi-sorted relational structures with a richer structure of automorphisms. We will be using this framework as well, see Section 2.1. Although it is possible to modify the Faben–Jerrum conjecture for general multi-sorted structures in such a way that no counterexample is known so far, there is still little understanding of the general case.

There are two properties of graphs that made the result of [16] possible but fail for general relational structures. One is the structure of automorphisms of direct products of graphs. Due to the results of [35, 16] every automorphism of a direct product of graphs essentially boils down to a combination of automorphisms of the factors and a permutation of the factors. This is no longer true in the general case, even in the case of digraphs, as was demonstrated in [41]. This leads to a failure of the second important property: reductions through primitive positive (pp-) definitions. Let ${\mathcal{H}}$ be a relational structure. Recall that a relation $\mathcal{R}(x_{1},\ldots,x_{k})$ on $H$ , the base set of ${\mathcal{H}}$ , is said to be pp-definable in ${\mathcal{H}}$ if there is a first order formula that represents $\mathcal{R}$ and has the following form

\mathcal{R}(x_{1},\ldots,x_{k})=\exists y_{1},\ldots,y_{m}\ \Phi(x_{1},\ldots,% x_{k},y_{1},\ldots,y_{m}),

where $\Phi$ is a conjunction of predicates from ${\mathcal{H}}$ and equality predicates. If ${\mathcal{H}}$ is a $p$ -rigid graph, then the problem $\#_{p}{\rm CSP}({\mathcal{H}}+\mathcal{R})$ , where ${\mathcal{H}}+\mathcal{R}$ denotes the extension of ${\mathcal{H}}$ by adding the predicate $\mathcal{R}$ , is polynomial time reducible to $\#_{p}{\rm CSP}({\mathcal{H}})$ . Such reductions are known to be a powerful tool in the CSP research, as they allow for the use of polymorphisms, that is, homomorphisms from powers ${\mathcal{H}}^{n}$ to ${\mathcal{H}}$ , to describe the complexity of constraint problems, see [15, 3]. In particular, the existence of a so-called Mal’tsev polymorphism, that is, a polymorphism $m:{\mathcal{H}}^{3}\to{\mathcal{H}}$ satisfying the equations $m(x,y,y)=m(y,y,x)=x$ , makes it possible to represent solutions to a CSP in a compact form that then in some cases can be used to find their number [11, 23]. In the case of general relational structures pp-definitions no longer give rise to reductions between problems and need to be replaced with their modular counterpart. A relation $\mathcal{R}(x_{1},\ldots,x_{k})$ is said to be $p$ -mpp-definable in ${\mathcal{H}}$ for a prime $p$ , it can be represented by a formula

\mathcal{R}(x_{1},\ldots,x_{k})=\exists^{\not\equiv p}y_{1},\ldots,y_{m}\ \Phi% (x_{1},\ldots,x_{k},y_{1},\ldots,y_{m}),

where the requirements on $\Phi$ are the same as before, and which is true for certain values of $x_{1},\ldots,x_{k}$ if and only if the number of values of $y_{1},\ldots,y_{m}$ that make $\Phi(x_{1},\ldots,x_{k},y_{1},\ldots,y_{m})$ true is not divisible by $p$ . Then [41] proves that $\#_{p}{\rm CSP}({\mathcal{H}}+\mathcal{R})$ is polynomial time reducible to $\#_{p}{\rm CSP}({\mathcal{H}})$ for any relational structure ${\mathcal{H}}$ and any relation $\mathcal{R}$ $p$ -mpp-definable in ${\mathcal{H}}$ .

Unfortunately, $p$ -mpp-definitions cannot be captured by polymorphisms, and overcoming this difficulty will be an ongoing theme of this paper. In some cases, however, polymorphisms of $p$ -mpp-definable relations play an important role. For instance, in [41] it was shown that if the set of 2-mpp-definable relations of a structure ${\mathcal{H}}$ has a Mal’tsev polymorphism, then $\#_{2}{\rm CSP}({\mathcal{H}})$ can be solved in polynomial time.

Our contribution.

In this paper we build upon the results of [41] to obtain a complexity classification of $\#_{p}{\rm CSP}({\mathcal{H}})$ for two classes of structures ${\mathcal{H}}$ . We start with a new version of an automorphism and the corresponding rigidity condition.

A binary polymorphism $f$ of a relational structure ${\mathcal{H}}$ is said to be an automorphic polynomial if for every $a\in H$ , $f(a,x)$ is a permutation of $H$ . If, for a prime $p$ , for any $a\in H$ , $f(a,x)$ is the identity mapping or a permutation of order $p$ , and $f(a,x)$ is a permutation of order $p$ for at least one $a\in H$ , $f$ is said to be a $p$ -automorphic polynomial. The existence of a $p$ -automorphic polynomial allows one to reduce a modular counting CSP to a CSP over a smaller structure even when the structure is $p$ -rigid, see Example 12. For a complete version of the following result see Proposition 10 and Corollary 11.

Proposition 1.

Let a relational structure ${\mathcal{H}}$ have a $p$ -automorphic polynomial $f$ . Then there is ${\mathcal{H}}^{f}$ such that the domain of ${\mathcal{H}}^{f}$ has smaller cardinality than ${\mathcal{H}}$ and $\#_{p}{\rm CSP}({\mathcal{H}})$ is polynomial time reducible to $\#_{p}{\rm CSP}({\mathcal{H}}^{f})$ . Moreover, if ${\mathcal{H}}$ satisfies some additional conditions, ${\mathcal{H}}^{f}$ can be chosen such that $\#_{p}{\rm CSP}({\mathcal{H}})$ and $\#_{p}{\rm CSP}({\mathcal{H}}^{f})$ are polynomial time equivalent.

In order to prove Proposition 1, given an instance $(V,{\mathcal{C}})$ of $\#_{p}{\rm CSP}({\mathcal{H}})$ we find permutations of the domain that are specific for each variable from $V$ , have order $p$ , and such that they map every tuple of every constraint to a tuple from the same constraint (so-called consistent permutations). These permutations allow us to reduce the domain ${\mathcal{H}}$ to a smaller structure (in terms of the cardinality of the domain), because similar to automorphisms the elements that are shifted by the permutations can be eliminated from the problem. On the other hand, let $a\in H$ be an element such that $f(a,x)$ is a permutation of order $p$ . Then, if the permutations above do not exist, it implies that the element $a$ cannot be a part of any solution, and therefore can be eliminated. Consistent permutations are found by constructing a derivative CSP, whose domain is the symmetric group on $H$ , and the CSP itself is an instance of a Mal’tsev CSP over that group [11, 5].

Recall that a unary relation pp-definable in a structure ${\mathcal{H}}$ is said to be a subalgebra of ${\mathcal{H}}$ . In the case of modular counting we use $p$ -subalgebras, that is, unary relations $p$ -mpp-definable in ${\mathcal{H}}$ . The two types of relational structures we consider here are

$\blacksquare$

3-element structures, which are the next step after a similar result for 2-element structures from [25], and
$\blacksquare$

$p$ -conservative structures, i.e., structures such that every possible unary relation is a $p$ -subalgebra.

The same types of the CSP have been major milestones in the study of the decision problem, see [6, 7, 1, 9]. They introduced several key ideas that were then used to obtain a dichotomy theorem for the general CSP.

In this paper in both cases our complexity classification is incomplete. The remaining difficulty is the complexity of modular partition functions. When $p=2$ every partition function has a 0-1 matrix, and therefore can be treated as the problem of counting homomorphism to a graph or a bipartite graph. The complexity of this problem is known, see, [16]. If $p\geq 3$ this is no longer possible and the structure of matrices of partition functions becomes more intricate, requiring methods from finite fields. To give the reader a better idea of the difficulties with modular partition functions, recall [8, 23] that in the case of exact counting a necessary and sufficient condition for the problem $\#{\rm CSP}({\mathcal{H}})$ to be solvable in polynomial time is that the structure ${\mathcal{H}}$ is strongly balanced. It means that there is a way to associate integer matrices to relations pp-definable in ${\mathcal{H}}$ , and these matrices must have rank at most 1. In fact, the complexity of $\#{\rm CSP}$ is determined by the complexity of ${\rm EVAL}(M)$ , for the matrices $M$ defined as above. That balancedness is necessary for $\#_{p}{\rm CSP}({\mathcal{H}})$ being solvable in polynomial time is no longer true, and this is due to the fact that the modular version of ${\rm EVAL}(M)$ can be polynomial time solvable even if $M$ does not have rank 1. Some partial results have been obtained in [39].

Let $\langle{\mathcal{H}}\rangle$ and $\langle{\mathcal{H}}\rangle_{p}$ denote the set of all relations that are, respectively, pp-definable and $p$ -mpp-definable in ${\mathcal{H}}$ . In the case of exact counting a necessary condition for tractability of $\#{\rm CSP}({\mathcal{H}})$ is the existence of a Mal’tsev polymorphism of ${\mathcal{H}}$ , mentioned above. No similar property has been known to be true for modular counting. The two main results of this paper claim that for 3-element and $p$ -conservative structures ${\mathcal{H}}$ if $\langle{\mathcal{H}}\rangle_{p}$ has no Mal’tsev polymorphism then $\#_{p}{\rm CSP}({\mathcal{H}})$ is $\#_{p}P$ -hard. If a Mal’tsev polymorphism exists then we identify certain cases, in which the problem is polynomial time solvable.

Theorem 2.

Let ${\mathcal{H}}$ be a $p$ -conservative structure and $p$ a prime. If $\langle{\mathcal{H}}\rangle_{p}$ does not have a Mal’tsev polymorphism then $\#_{p}{\rm CSP}({\mathcal{H}})$ is $\#_{p}P$ -hard. Otherwise, if $p=2$ then $\#_{2}{\rm CSP}({\mathcal{H}})$ is solvable in polynomial time.

In order to state the result for 3-element structures let ${\mathcal{H}}^{f}$ be the structure from Proposition 1 constructed from ${\mathcal{H}}$ using a $p$ -automorphic polynomial $f$ . Note that if ${\mathcal{H}}$ is a 3-element structure, ${\mathcal{H}}^{f}$ has at most 2 elements.

Theorem 3.

Let ${\mathcal{H}}$ be a 3-element structure and $p$ a prime. If one of the following conditions holds:

(a)

${\mathcal{H}}$ has a $p$ -automorphic polynomial $f$ and $\langle{\mathcal{H}}^{f}\rangle_{p}$ has a Mal’tsev polymorphism, or
(b)

${\mathcal{H}}$ does not have a $p$ -automorphic polynomial, $\langle{\mathcal{H}}\rangle_{p}$ has a Mal’tsev polymorphism, and $p=2$ ,

then $\#_{p}{\rm CSP}({\mathcal{H}})$ is solvable in polynomial time. If

(1)

${\mathcal{H}}$ has a $p$ -automorphic polynomial $f$ and $\langle{\mathcal{H}}^{f}\rangle_{p}$ does not have a Mal’tsev polymorphism, or
(2)

${\mathcal{H}}$ does not have a $p$ -automorphic polynomial and $\langle{\mathcal{H}}\rangle_{p}$ does not have a Mal’tsev polymorphism,

then $\#_{p}{\rm CSP}({\mathcal{H}})$ is $\#_{p}P$ -complete.

Since ${\mathcal{H}}^{f}$ has at most 2 elements, the cases when ${\mathcal{H}}$ has a $p$ -automorphic polynomial can be dealt with using an extension of the results by Faben [25], see Proposition 20.

Apart from the introduction of $p$ -automorphic polynomials, the main technical contribution of the paper is the following. The property of relations with a Mal’tsev polymorphism that makes Mal’tsev polymorphisms useful is rectangularity. A relation $\mathcal{R}$ (at least binary) is said to be rectangular if for any partition of the coordinate set of $\mathcal{R}$ into two nonempty parts for any tuples ${\bf a},{\bf b}$ from the first part and ${\bf c},{\bf d}$ from the second part, if $({\bf a},{\bf c}),({\bf b},{\bf c}),({\bf b},{\bf d})\in\mathcal{R}$ , then $({\bf a},{\bf d})\in\mathcal{R}$ . If a structure ${\mathcal{H}}$ has a Mal’tsev polymorphism then any relation $\mathcal{R}\in\langle{\mathcal{H}}\rangle$ is rectangular, a property that is sometimes referred to as strong rectangularity. It is the lack of rectangularity that often makes a counting CSP hard, as it was shown in [12]. In the case of modular counting a similar result is also true, although highly nontrivial, provided a non-rectangular relation is in ${\mathcal{H}}$ , see [16]. The major difficulty though has been to obtain hardness from non-rectangular relations in $\langle{\mathcal{H}}\rangle$ . Here we found a way to use $\langle{\mathcal{H}}\rangle_{p}$ instead, while still using a Mal’tsev polymorphism, although in a different manner than in other versions of counting.

2 Preliminaries

Let $[n]$ denote the set $\{1,2,\ldots,n\}$ . Let $H^{n}$ be the direct product of the set $H$ with itself $n$ times and $H_{1}\times\dots\times H_{n}$ the direct product of sets $H_{1},\ldots,H_{n}$ . We denote the members of $H^{n}$ and $H_{1}\times\dots\times H_{n}$ using bold font, $\mathbf{a}\in H^{n}$ , ${\bf a}\in H_{1}\times\dots\times H_{n}$ . The $i$ -th entry of $\mathbf{a}$ is denoted by $\mathbf{a}[i]$ . For $I=\{i_{1},\ldots,i_{k}\}\subseteq[n]$ , we write ${\rm pr}_{I}{\bf a}$ for the tuple $({\bf a}[i_{1}],\dots,{\bf a}[i_{k}])$ , and for a relation $\mathcal{R}\subseteq H^{n}$ or $\mathcal{R}\subseteq H_{1}\times\dots\times H_{n}$ , we define ${\rm pr}_{I}\mathcal{R}=\{{\rm pr}_{I}{\bf a}\mid{\bf a}\in\mathcal{R}\}$ . The arity of $\mathcal{R}$ , denoted by $\hbox{ar}(\mathcal{R})$ , is defined to be $n$ , the length of the tuples in $\mathcal{R}$ . For ${\bf a}\in H_{1}\times\dots\times H_{s}$ , $s\in[n]$ , let $\mathsf{Ext}_{\mathcal{R}}({\bf a})=\{{\bf b}\in H_{s+1}\times\dots\times H_{n% }|({\bf a},{\bf b})\in\mathcal{R}\}$ , and by $\mathsf{\#ext}_{\mathcal{R}}({\bf a})$ we denote the cardinality of $\mathsf{Ext}_{\mathcal{R}}({\bf a})$ . (Note that we will often use the notation $\mathsf{Ext}$ in a more general sense, when ${\bf a}\in{\rm pr}_{I}\mathcal{R}$ for a set $I\subseteq[n]$ that is not necessarily of the form $I=[s]$ .) For a prime $p$ we denote the cardinality of $\mathsf{Ext}_{\mathcal{R}}({\bf a})$ mod $p$ by $\mathsf{\#_{p}ext}_{\mathcal{R}}({\bf a})$ . Moreover, $\mathsf{pr}^{p}_{I}\mathcal{R}$ denotes the set $\{{\rm pr}_{I}{\bf a}\mid{\bf a}\in\mathcal{R}\text{ and }\mathsf{\#_{p}ext}_{% \mathcal{R}}({\rm pr}_{I}{\bf a})\neq 0\}$ . Often, we treat relations $\mathcal{R}\subseteq H_{1}\times\dots\times H_{n}$ as predicates $\mathcal{R}:H_{1}\times\dots\times H_{n}\to\{0,1\}$ .

2.1 Relational structures

We begin by introducing multi-sorted sets. Let $H=\{H_{i}\}_{{i\in[k]}}$ be a collection of sets. We assume that the sets $H_{1},\ldots,H_{k}$ are disjoint. A mapping $\varphi$ between two multi-sorted sets $G=\{G_{i}\}_{{i\in[k]}}$ and $H=\{H_{i}\}_{{i\in[k]}}$ is defined as a collection of mappings $\varphi=\{\varphi_{i}\}_{{i\in[k]}}$ , where $\varphi_{i}:G_{i}\to H_{i}$ , that is, $\varphi_{i}$ maps elements of the sort $i$ in $G$ to elements of the sort $i$ in $H$ . A mapping $\varphi=\{\varphi_{i}\}_{{i\in[k]}}$ from $\{G_{i}\}_{{i\in[k]}}$ to $\{H_{i}\}_{{i\in[k]}}$ is injective (bijective), if for all $i\in[k]$ , $\varphi_{i}$ is injective (bijective).

A multi-sorted relational signature $\sigma$ over a set of types $[k]$ is a collection of relational symbols. A symbol $\mathcal{R}\in\sigma$ is assigned a positive integer $\ell_{\mathcal{R}}$ , the arity of the symbol denoted $\hbox{ar}(\mathcal{R})$ , and a tuple $(i_{1},\ldots,i_{\ell_{\mathcal{R}}})\in[k]^{\ell_{\mathcal{R}}}$ , the type of the symbol. A multi-sorted relational structure ${\mathcal{H}}$ with signature $\sigma$ is a multi-sorted set $\{H_{i}\}_{i\in[k]}$ and an interpretation $\mathcal{R}^{\mathcal{H}}$ of each $\mathcal{R}\in\sigma$ , where $\mathcal{R}^{\mathcal{H}}$ is a relation or a predicate on $H_{i_{1}}\times...\times H_{i_{\ell_{\mathcal{R}}}}$ . The multi-sorted structure ${\mathcal{H}}$ is finite if $H$ contains finitely many finite domains, and $\sigma$ is finite. All structures in this paper are finite. The set $H$ is said to be the base set or the universe of ${\mathcal{H}}$ . For the base set we will use the same letter as for the structure, only in the regular font. Multi-sorted structures with the same signature and types are called similar.

Let ${\mathcal{H}}=(\{H_{i}\}_{i\in[k]};\mathcal{R}_{1},\dots,\mathcal{R}_{\ell})$ be a relational structure. We use $\mathsf{Sp}({\mathcal{H}})$ to denote its spectrum, that is, an infinite sequence $(n_{1},n_{2},\dots)$ where $n_{j}$ is the number of domains of cardinality $j$ . If the structure is finite, $\mathsf{Sp}({\mathcal{H}})$ is essentially a finite sequence, and we will truncate it by removing the trailing zeroes. Let $\preceq$ denote the colexicographic order on the set of such sequences: $(n_{1},\dots,n_{k})\preceq(n^{\prime}_{1},\dots,n^{\prime}_{\ell})$ , $n_{k},n_{\ell}\neq 0$ if and only if either the sequences are equal, or $k<\ell$ , or for some $i\in[k]$ , $n_{i}<n^{\prime}_{i}$ and $n_{j}=n^{\prime}_{j}$ for $j\in\{i+1,\dots,k\}$ .

Let ${\mathcal{G}},{\mathcal{H}}$ be similar multi-sorted structures with signature $\sigma$ . A homomorphism $\varphi$ from ${\mathcal{G}}$ to ${\mathcal{H}}$ is a mapping $\varphi:G\to H$ such that for any $\mathcal{R}\in\sigma$ with type $(i_{1},\ldots,i_{\ell_{\mathcal{R}}})$ , if $\mathcal{R}^{{\mathcal{G}}}(a_{1},\ldots,a_{\ell_{\mathcal{R}}})$ is true for $(a_{1},\ldots,a_{\ell_{\mathcal{R}}})\in G_{i_{1}}\times...\times G_{i_{\ell_{% \mathcal{R}}}}$ , then $\mathcal{R}^{{\mathcal{H}}}(\varphi_{i_{1}}(a_{1}),\ldots,\varphi_{i_{\ell_{% \mathcal{R}}}}(a_{\ell_{\mathcal{R}}}))$ is true as well. The set of all homomorphisms from ${\mathcal{G}}$ to ${\mathcal{H}}$ is denoted $\mathsf{Hom}({\mathcal{G}},{\mathcal{H}})$ . The cardinality of $\mathsf{Hom}({\mathcal{G}},{\mathcal{H}})$ is denoted by $\mathsf{hom}({\mathcal{G}},{\mathcal{H}})$ . A homomorphism $\varphi$ is an isomorphism if it is bijective and the inverse mapping $\varphi^{-1}$ is a homomorphism from ${\mathcal{H}}$ to ${\mathcal{G}}$ . If ${\mathcal{H}}$ and ${\mathcal{G}}$ are isomorphic, we write ${\mathcal{H}}\cong{\mathcal{G}}$ . A homomorphism of a structure to itself is called an endomorphism, and an isomorphism to itself is called an automorphism. As is easily seen, automorphisms of a structure ${\mathcal{H}}$ form a group denoted $\mathsf{Aut}({\mathcal{H}})$ . Let $\pi$ be an automorphism of ${\mathcal{H}}$ . By $\mathsf{Fix}(\pi)$ we denote the collection $\{\mathsf{Fix}(\pi_{i})\}_{i\in[k]}$ of sets of fixed points of the $\pi_{i}$ ’s. For $\mathcal{Q}\subseteq H_{i_{1}}\times\dots\times H_{i_{\ell}}$ , we use $\pi(\mathcal{Q})$ to denote the set $\{\pi({\bf a})\mid{\bf a}\in\mathcal{Q}\}$ , where $\pi({\bf a})=(\pi_{i_{1}}({\bf a}[1]),\ldots,\pi_{i_{\ell}}({\bf a}[\ell]))$ . For a prime number $p$ we say that $\pi$ has order $p$ or is a $p$ -automorphism if $\pi$ has order $p$ in $\mathsf{Aut}({\mathcal{H}})$ . In other words, each of the $\pi_{i}$ ’s is either the identity mapping or has order $p$ , and at least one of the $\pi_{i}$ ’s is not the identity mapping. The structure ${\mathcal{H}}$ is said to be $p$ -rigid if it has no $p$ -automorphisms.

Proposition 4 ([41]).

Let ${\mathcal{H}}$ be a multi-sorted structure and $p$ a prime. Then up to an isomorphism there exists a unique $p$ -rigid multi-sorted structure ${\mathcal{H}}^{*p}$ such that for any structure ${\mathcal{G}}$ similar to ${\mathcal{H}}$ it holds that $\mathsf{hom}({\mathcal{G}},{\mathcal{H}})=\mathsf{hom}({\mathcal{G}},{\mathcal% {H}}^{*p})$ .

The direct product of multi-sorted $\sigma$ -structures ${\mathcal{H}},{\mathcal{G}}$ , denoted ${\mathcal{H}}\times{\mathcal{G}}$ is the multi-sorted $\sigma$ -structure with the base set $H\times G=\{H_{i}\times G_{i}\}_{{i\in[k]}}$ , the interpretation of $\mathcal{R}\in\sigma$ is given by $\mathcal{R}^{{\mathcal{H}}\times{\mathcal{G}}}((a_{1},b_{1}),\ldots,(a_{k},b_{% k}))=1$ if and only if $\mathcal{R}^{{\mathcal{H}}}(a_{1},\ldots,a_{k})=1$ and $\mathcal{R}^{{\mathcal{G}}}(b_{1},\ldots,b_{k})=1$ . By ${\mathcal{H}}^{\ell}$ we will denote the $\ell$ th power of ${\mathcal{H}}$ , that is, the direct product of $\ell$ copies of ${\mathcal{H}}$ . A substructure ${\mathcal{H}}^{\prime}$ of ${\mathcal{H}}$ induced by a collection of sets $\{H^{\prime}_{i}\}_{i\in[k]}$ , where $H^{\prime}_{i}\subseteq H_{i}$ , is the relational structure given by $(\{H^{\prime}_{i}\}_{{i\in[k]}};\mathcal{R}^{\prime}_{1},\ldots,\mathcal{R}^{% \prime}_{m})$ , where $\mathcal{R}^{\prime}_{j}=\mathcal{R}_{j}\cap(H^{\prime}_{i_{1}}\times\dots% \times H^{\prime}_{i_{\ell}})$ and $(i_{1},\ldots,i_{\ell})$ is the type of $\mathcal{R}_{j}$ .

2.2 The CSP and Modular Counting

There are two standard formulations of the Constraint Satisfaction Problem (CSP). Let ${\mathcal{H}}=(\{H_{i}\}_{i\in[k]};\mathcal{R}^{\mathcal{H}}_{1},\ldots,% \mathcal{R}^{\mathcal{H}}_{\ell})$ be a multi-sorted relational structure. The problem ${\rm CSP}({\mathcal{H}})$ asks, given a relational structure ${\mathcal{G}}=(\{G_{i}\}_{i\in[k]};\mathcal{R}^{\mathcal{G}}_{1},\ldots,% \mathcal{R}^{\mathcal{G}}_{\ell})$ similar to ${\mathcal{H}}$ whether there exists a homomorphism $\varphi$ from ${\mathcal{G}}$ to ${\mathcal{H}}$ .

The other standard definition does not involve relational structures. Let $H=\{H\}_{i\in[k]}$ be a multi-sorted domain and $\Gamma$ a set of multi-sorted relations over $H$ , called a constraint language. An instance ${\mathcal{P}}=(V,\tau,{\mathcal{C}})$ of ${\rm CSP}(\Gamma)$ consists of:

$\blacksquare$

a finite set of variables $V$ ,
$\blacksquare$

a type function $\tau:V\to[k]$ assigning each variable a sort,
$\blacksquare$

a finite set of constraints ${\mathcal{C}}$ , where each constraint is a pair $\langle{\bf s},\mathcal{R}\rangle$ with $\mathcal{R}\in\Gamma$ of arity $m$ and ${\bf s}=(v_{1},\ldots,v_{m})$ a tuple of variables whose sorts match the type of $\mathcal{R}$ .

A solution is a mapping $\varphi:V\to\bigcup_{i\in[k]}H_{i}$ such that for all $v\in V$ , $\varphi(v)\in H_{\tau(v)}$ , and for every constraint $\langle{\bf s},\mathcal{R}\rangle$ , the tuple $(\varphi(v_{1}),\ldots,\varphi(v_{m}))$ belongs to $\mathcal{R}$ .

For a structure ${\mathcal{H}}=(\{H_{i}\}_{i\in[k]};\mathcal{R}^{\mathcal{H}}_{1},\ldots,% \mathcal{R}^{\mathcal{H}}_{\ell})$ , let $\Gamma_{\mathcal{H}}=\{\mathcal{R}^{\mathcal{H}}_{1},\ldots,\mathcal{R}^{% \mathcal{H}}_{\ell}\}$ . It is well known, see e.g. [27] and [3], that the problems ${\rm CSP}({\mathcal{H}})$ and ${\rm CSP}(\Gamma_{\mathcal{H}})$ can be easily translated into each other. The same holds for the counting versions $\#{\rm CSP}({\mathcal{H}})$ and $\#{\rm CSP}(\Gamma_{\mathcal{H}})$ , as well as the modular counting versions $\#_{p}{\rm CSP}({\mathcal{H}})$ and $\#_{p}{\rm CSP}(\Gamma_{\mathcal{H}})$ . The conversion procedure is as follows. Given an instance ${\mathcal{G}}$ of ${\rm CSP}({\mathcal{H}})$ with signature $\sigma$ , construct an instance ${\mathcal{P}}=(V,\tau,{\mathcal{C}})$ of ${\rm CSP}(\Gamma_{\mathcal{H}})$ by setting $V=\bigcup_{i\in[k]}G_{i}$ , with the type function $\tau$ induced by the sorts of ${\mathcal{G}}$ , and for every relation $\mathcal{R}\in\sigma$ and tuple ${\bf s}\in\mathcal{R}^{\mathcal{G}}$ , include the constraint $\langle{\bf s},\mathcal{R}^{\mathcal{H}}\rangle$ in ${\mathcal{C}}$ . Conversely, for a finite constraint language $\Gamma=\{\mathcal{R}_{1},\ldots,\mathcal{R}_{\ell}\}$ over $H$ we can construct a structure ${\mathcal{H}}_{\Gamma}=(H,\mathcal{R}_{1},\ldots,\mathcal{R}_{\ell})$ with an appropriately selected signature. Then any instance of ${\rm CSP}(\Gamma)$ can be transformed into an instance of ${\rm CSP}({\mathcal{H}}_{\Gamma})$ by reversing this construction. This correspondence naturally extends to the counting and modular counting versions.

2.3 Expansions of Relational Structures and the CSP

A (multi-sorted) relational structure ${\mathcal{H}}^{\prime}=(H;\mathcal{R}^{\prime}_{1},\ldots,\mathcal{R}^{\prime}% _{\ell^{\prime}})$ , $H=\{H_{i}\}_{{i\in[k]}}$ , is an expansion of a relational structure ${\mathcal{H}}=(H;\mathcal{R}_{1},\ldots,\mathcal{R}_{\ell})$ , if $\ell^{\prime}\geq\ell$ and $\mathcal{R}^{\prime}_{i}=\mathcal{R}_{i}$ for $i\in[\ell]$ . It will be convenient to denote ${\mathcal{H}}^{\prime}$ by ${\mathcal{H}}+\{\mathcal{R}_{\ell+1},\ldots,\mathcal{R}_{\ell^{\prime}}\}$ or just ${\mathcal{H}}+\mathcal{R}_{\ell^{\prime}}$ if $\ell^{\prime}=\ell+1$ . Several types of expansions are often used in the context of the CSP.

Let ${\mathcal{H}}=(\{{\mathcal{H}}_{i}\}_{i\in[k]};\mathcal{R}_{1},\ldots,\mathcal% {R}_{\ell})$ be a multi-sorted structure with signature $\sigma$ and ${\mathcal{H}}^{=}$ its expansion by adding a family of binary relational symbols $=_{H_{i}}$ (one for each type) interpreted as the equality relation on $H_{i}$ , $i\in[k]$ . A constant relation over a set $\{H_{i}\}_{i\in[k]}$ is a unary relation $C_{H_{i},a}=\{a\}$ , $a\in H_{i},i\in[k]$ (such a predicate can only be applied to variables of type $i$ ). For a structure ${\mathcal{H}}$ by ${\mathcal{H}}^{\mathsf{c}}$ we denote the expansion of ${\mathcal{H}}$ by all the constant relations $C_{H_{i},a}$ , $a\in H_{i},i\in[k]$ .

Proposition 5 ([41]).

Let ${\mathcal{H}}$ be a multi-sorted relational structure and $p$ prime.

(1)

$\#_{p}{\rm CSP}({\mathcal{H}}^{=})$ is polynomial time reducible to $\#_{p}{\rm CSP}({\mathcal{H}})$ ;
(2)

Let ${\mathcal{H}}$ be $p$ -rigid. Then $\#_{p}{\rm CSP}({\mathcal{H}}^{\mathsf{c}})$ is polynomial time reducible to $\#_{p}{\rm CSP}({\mathcal{H}})$ .

Observe that if a relational structure contains all the constant relations, in particular, any structure of the form ${\mathcal{H}}^{\mathsf{c}}$ , it is obviously rigid, as every automorphism should respect every $C_{H_{i},a}$ and map $a$ to $a$ , and therefore also $p$ -rigid for any $p$ .

Using Proposition 4 we may assume that all the structures we are dealing with are $p$ -rigid. Then, by Proposition 5(2) we may assume they contain all the constants, that is, ${\mathcal{H}}={\mathcal{H}}^{\mathsf{c}}$ . We will use this assumption from now on.

Primitive-positive definitions play a central role in the CSP research. It has been proved in multiple circumstances that expanding a relational structure with pp-definable relations does not change the complexity of the corresponding CSP. This has been proved for the decision CSP in [37, 15], the exact counting CSP [12], and in certain cases (where relational structures are expansions of graphs) [16] of modular counting CSP. The reader is referred to [3] for details about primitive positive definitions and their use in the study of the CSP.

Let ${\mathcal{H}}$ be a multi-sorted relational structure with the base set $H$ . A primitive positive (pp-) formula in ${\mathcal{H}}$ is a first-order formula

\exists y_{1},\ldots,y_{s}\Phi(x_{1},\ldots,x_{k},y_{1},\ldots,y_{s}),

where $\Phi$ is a conjunction of atomic formulas of the form $z_{1}=_{H}z_{2}$ or $\mathcal{R}(z_{1},\ldots,z_{\ell})$ , $z_{1},\ldots,z_{\ell}$ $\in\{x_{1},\ldots,x_{k},y_{1},\ldots,y_{s}\}$ , and $\mathcal{R}$ is a predicate of ${\mathcal{H}}$ . Every variable in $\Phi$ is assigned a type $\tau(x_{i}),\tau(y_{j})$ in such a way that for every atomic formula $z_{1}=_{H}z_{2}$ it holds that $\tau(z_{1})=\tau(z_{2})$ , and for any atomic formula $\mathcal{R}(z_{1},\ldots,z_{\ell})$ the sequence $(\tau(z_{1}),\ldots,\tau(z_{\ell}))$ matches the type of $\mathcal{R}$ . We say that ${\mathcal{H}}$ pp-defines a predicate $\mathcal{Q}$ if there exists a pp-formula such that

\mathcal{Q}(x_{1},\ldots,x_{k})=\exists y_{1},\ldots,y_{s}\Phi(x_{1},\ldots,x_% {k},y_{1},\ldots,y_{s}).

The set of all pp-definable relations in the (multi-sorted) relational structure ${\mathcal{H}}$ is denoted by $\langle{\mathcal{H}}\rangle$ .

For ${\bf a}\in\mathcal{Q}$ by $\mathsf{\#ext}_{\Phi}({\bf a})$ we denote the number of assignments ${\bf b}\in H_{\tau(y_{1})}\times\dots\times H_{\tau(y_{s})}$ to $y_{1},\ldots,y_{s}$ such that $\Phi({\bf a},{\bf b})$ is true. We denote the number of such assignments modulo $p$ by $\mathsf{\#_{p}ext}_{\Phi}({\bf a})$ .

As was shown in [41], pp-definitions are not always compatible with modular counting in the sense that will be made precise later. The concept of pp-definitions adapted to modular counting is that of modular pp-definitions, or $p$ -mpp-definitions, where $p$ is the modulus for counting. For a prime number $p$ the $p$ -modular quantifier $\exists^{\not\equiv p}$ is interpreted as follows

	$\displaystyle\mathcal{R}(x_{1},\ldots,x_{k})=$	$\displaystyle\exists^{\not\equiv p}y_{1},\ldots,y_{s}\Phi(x_{1},\ldots,x_{k},y% _{1},\ldots,y_{s})\text{ is true }$
		$\displaystyle\Leftrightarrow\mathsf{\#ext}_{\Phi}(x_{1},\ldots,x_{k})\not% \equiv 0\pmod{p}.$		(1)

A primitive positive formula that uses $p$ -modular quantifiers instead of regular ones is called a $p$ -modular primitive positive (or $p$ -mpp for short). The relation it defines is said to be $p$ -mpp-definable, and the definition itself is called a $p$ -mpp-definition. The set of all $p$ -mpp-definable relations in ${\mathcal{H}}$ is denoted by $\langle{\mathcal{H}}\rangle_{p}$ . Note that modular quantifiers are not as robust as regular ones. In particular, $\exists^{\not\equiv p}x,y$ and $\exists^{\not\equiv p}x\ \exists^{\not\equiv p}y$ may result in a different predicate. The same is of course true for more complicated applications of modular quantifiers, so, one needs to be extra careful with $p$ -mpp-definitions.

If for the $p$ -mpp-definition (1) $\mathsf{\#_{p}ext}_{\Phi}({\bf a})=1$ for all ${\bf a}\in\mathcal{R}$ , the $p$ -mpp definition is said to be strict. By Proposition 5.6 from [16] if $\mathcal{R}$ has a $p$ -mpp-definition, it has a strict $p$ -mpp definition.

Proposition 6 ([41]).

Let ${\mathcal{H}}$ be a be a $\sigma$ -structure (single- or multi-sorted), and $p$ a prime. Let $\mathcal{R}$ be a relation that is $p$ -mpp-definable in ${\mathcal{H}}$ . Then $\#_{p}{\rm CSP}({\mathcal{H}}+\mathcal{R})$ is polynomial time reducible to $\#_{p}{\rm CSP}({\mathcal{H}})$ . In particular, if $\mathcal{R}$ is conjunctive definable in ${\mathcal{H}}$ (that is, $s=0$ in (1) and the specific value of $p$ is irrelevant), $\#_{p}{\rm CSP}({\mathcal{H}}+\mathcal{R})$ is polynomial time reducible to $\#_{p}{\rm CSP}({\mathcal{H}})$ .

Let ${\mathcal{H}}=(\{H_{i}\}_{i\in[k]};\mathcal{R}_{1},\dots,\mathcal{R}_{m})$ be a multi-sorted relational structure. A subset $A\subseteq H_{i}$ is called a subalgebra (of sort $i$ ) if it is pp-definable in ${\mathcal{H}}$ as a unary relation. If $A$ is $p$ -mpp-definable in ${\mathcal{H}}$ , it is said to be $p$ -subalgebra. In other words, $A$ is a $p$ -subalgebra if there exists a relation $\mathcal{Q}(x)$ $p$ -mpp-definable in ${\mathcal{H}}$ , such that $a\in A$ if and only if $\mathcal{Q}(a)$ .

2.4 Polymorphisms and Automorphisms of Products

We will also use polymorphisms of relational structures and constraint languages. Let ${\mathcal{H}}=(H:\mathcal{R}_{1},\ldots,\mathcal{R}_{\ell})$ , $H=\{H_{i}\}_{i\in[k]}$ be a multi-sorted relational structure. An $r$ -ary polymorphism $f$ of ${\mathcal{H}}$ is a homomorphism $f:{\mathcal{H}}^{r}\to{\mathcal{H}}$ . In other words, a collection of mappings $f=\{f_{i}\}_{i\in[k]}$ , $f_{i}:H_{i}^{r}\to H_{i}$ , such that for every $\mathcal{R}_{j}$ , $j\in[\ell]$ , with type $(i_{1},\ldots,i_{s})$ , for any ${\bf a}_{1},\ldots,{\bf a}_{r}\in\mathcal{R}_{j}$

(f_{i_{1}}({\bf a}_{1}[1],{\bf a}_{2}[1],\dots,{\bf a}_{r}[1]),\ldots,f_{i_{s}% }({\bf a}_{1}[s],{\bf a}_{2}[s],\dots,{\bf a}_{r}[s]))\in\mathcal{R}_{j}.

If this condition for $\mathcal{R}_{j}$ holds, $f$ is also said to be a polymorphism of $\mathcal{R}_{j}$ . For a constraint language $\Gamma$ over $H$ the definition of a polymorphism is essentially the same: $f$ is a polymorphism of $\Gamma$ if it is a polymorphism of every relation from $\Gamma$ .

Let $H=\{H_{i}\}_{{i\in[k]}}$ be a multi-sorted set. A collection of mappings $\{e^{s,r}_{i}\}_{i\in[k]}$ , $s\in[r]$ , is said to be the $s$ ’th $r$ -ary projection if $e^{s,r}_{i}(a_{1},\ldots,a_{r})=a_{s}$ for all $a_{1},\ldots,a_{r}\in H_{i}$ and $i\in[k]$ . Projections are polymorphisms of any relation, structure, or constraint language.

A particular type of polymorphisms plays an outsized role in counting CSP research. A ternary polymorphism $m$ of a multi-sorted relational structure ${\mathcal{H}}=(H;\mathcal{R}_{1},\ldots,\mathcal{R}_{\ell})$ , $H=\{H_{i}\}_{i\in[k]}$ , (a constraint language $\Gamma$ over $H$ ) is said to be Mal’tsev if for every $i\in[k]$ the mapping $m_{i}$ satisfies the equations $m_{i}(x,y,y)=m_{i}(y,y,x)=x.$ If ${\mathcal{H}}$ has a Mal’tsev polymorphism, the set of solutions of any instance ${\mathcal{G}}$ of ${\rm CSP}({\mathcal{H}})$ admits a compact representation by a set of solutions whose number is linear in the size of $G$ , see, [11, 23]. Under certain conditions this allows to solve $\#{\rm CSP}({\mathcal{H}})$ in polynomial time.

One other concept that we will refer to in this paper is the rectangularity. A binary relation $\mathcal{R}\subseteq H_{1}\times H_{2}$ is called rectangular if $(a,c),(a,d),(b,c)\in\mathcal{R}$ implies $(b,d)\in\mathcal{R}$ for any $a,b\in H_{1},c,d\in H_{2}$ . A relation $\mathcal{R}\subseteq H_{i_{1}}\times\dots\times H_{i_{n}}$ for $n\geq 2$ is rectangular if for every $\mathchar 3391\relax\neq I\subsetneq[n]$ , the relation $R$ is rectangular when viewed as a binary relation, a subset of ${\rm pr}_{I}\mathcal{R}\times{\rm pr}_{[n]-I}\mathcal{R}$ . A relational structure ${\mathcal{H}}$ is strongly rectangular if every relation $\mathcal{R}\in\langle{\mathcal{H}}\rangle$ of arity at least 2 is rectangular. The following lemma provides a connection between strong rectangularity and Mal’tsev polymorphisms and was first observed in [34] although in a different language.

Lemma 7 ([34], see also [23]).

A relational structure is strongly rectangular if and only if it has a Mal’tsev polymorphism.

We introduce a modular version of this concept, strongly $p$ -rectangular structures. A relational structure ${\mathcal{H}}$ is said to be strongly $p$ -rectangular, if every $\mathcal{R}\in\langle{\mathcal{H}}\rangle_{p}$ is rectangular. It is shown in [41] that a relational structure can be strongly rectangular, but not strongly $p$ -rectangular.

Also, it was shown in [41] that if a relational structure is strongly 2-rectangular and admits a Mal’tsev polymorphism, then the corresponding modular counting CSP problem modulo 2 is tractable. This result highlights the algorithmic significance of Mal’tsev polymorphisms: their presence enables efficient algorithms, while their absence plays a central role in establishing hardness.

Theorem 8 ([41, 42]).

Let ${\mathcal{H}}$ be a 2-rigid, strongly 2-rectangular multi-sorted relational structure, and $\langle{\mathcal{H}}\rangle_{2}$ has a Mal’tsev polymorphism. Then $\#_{2}{\rm CSP}({\mathcal{H}})$ can be solved in time $O(n^{5})$ .

Another part polymorphisms will be playing in this paper is their connection to automorphisms of powers of structures. Let ${\mathcal{H}}$ be a multi-sorted structure with the base set $H=\{H_{i}\}_{{i\in[k]}}$ and ${\mathcal{H}}^{r}$ its direct power. A mapping $f:{\mathcal{H}}^{r}\to{\mathcal{H}}^{r}$ of ${\mathcal{H}}^{r}$ to itself is a collection of mappings $\{f_{i}\}_{{i\in[k]}}:H_{i}^{r}\to H_{i}^{r}$ each of which can also be represented as $f_{i}=(f^{1}_{i},\ldots,f^{r}_{i})$ , where $f_{i}^{j}:H_{i}^{r}\to H_{i}$ . Rearranging these mapping we obtain collections $f^{j}=\{f^{j}_{i}\}_{{i\in[k]}}$ , $j\in[r]$ , where each $f^{j}$ is a mapping of $H^{r}$ to $H$ . The following lemma is straightforward from the definitions.

Lemma 9.

In the notation above $f$ is a homomorphism of ${\mathcal{H}}^{r}$ to itself if and only if $f^{j}$ is a polymorphism of ${\mathcal{H}}$ for every $j\in[r]$ .

Clearly, $f$ is an automorphism of ${\mathcal{H}}^{r}$ if and only if the $f^{j}$ are such that $f$ is bijective.

3 Automorphic Polynomials

In this section we introduce a new automorphism-like construction that allows one to reduce $\#_{p}{\rm CSP}({\mathcal{H}})$ to a CSP over a smaller structure that we will extensively use in the future. A binary polymorphism $f$ of a (multi-sorted) relational structure ${\mathcal{H}}=(\{H_{i}\}_{i\in[k]};\mathcal{R}_{1},\ldots,\mathcal{R}_{\ell})$ is said to be an automorphic polynomial if for any domain $H_{i}$ of ${\mathcal{H}}$ and any $a\in H_{i}$ , $f_{i}(a,x)$ viewed as a mapping from $H_{i}$ to $H_{i}$ is a permutation of $H_{i}$ . If, for a prime $p$ , for any domain $H_{i}$ and any $a\in H_{i}$ , $f_{i}(a,x)$ is the identity mapping or a permutation of order $p$ , and $f_{i}(a,x)$ is a permutation of order $p$ for at least one domain $H_{i}$ and at least one $a\in H_{i}$ , $f$ is said to be a $p$ -automorphic polynomial.

Let ${\mathcal{H}}=(\{H_{i}\}_{i\in[k]},\mathcal{R}_{1},\ldots,\mathcal{R}_{\ell})$ and $f$ its $p$ -automorphic polynomial. Let also $i\in[k]$ and $a\in H_{i}$ be such that $f_{i}(a,x)$ is a permutation of $H_{i}$ of order $p$ . Then a structure ${\mathcal{H}}^{\prime}$ is constructed as follows:

$\blacksquare$

The domains are the same as those of ${\mathcal{H}}$ , except $H_{i}$ . The domain $H_{i}$ is replaced with two domains: $H^{\prime}_{i}=H_{i}-\{a\}$ and $H^{\prime\prime}_{i}=H_{i}-B$ , where $B$ is the union of all nontrivial orbits of $f_{i}(a,x)$ .
$\blacksquare$

Every relation $\mathcal{R}_{j}$ containing $i$ in its type is replaced with $\mathcal{R}^{\prime}_{j}$ and $\mathcal{R}^{\prime\prime}_{j}$ that are obtained from $\mathcal{R}_{j}$ by replacing $H_{i}$ with $H^{\prime}_{i}$ (respectively $H^{\prime\prime}_{i}$ ) restricting to tuples that do not contain $a$ (respectively, do not contain elements from $B$ ).

We repeat this construction for every $H_{i}$ and $a\in H_{i}$ such that $f_{i}(a,x)$ is a permutation of $H_{i}$ of order $p$ . The resulting structure is denoted ${\mathcal{H}}^{f}$ .

Proposition 10.

Suppose that a relational structure ${\mathcal{H}}$ has a $p$ -automorphic polynomial $f$ and ${\mathcal{H}}^{f}$ is as above. Then $\mathsf{Sp}({\mathcal{H}}^{f})\preceq\mathsf{Sp}({\mathcal{H}})$ and $\#_{p}{\rm CSP}({\mathcal{H}})$ is polynomial time reducible to $\#_{p}{\rm CSP}({\mathcal{H}}^{f})$ .

Proof (sketch).

Let ${\mathcal{H}}=(\{H_{i}\}_{i\in[k]},\mathcal{R}_{1},\ldots,\mathcal{R}_{\ell})$ . The first claim of the proposition is obvious, so we focus on the second claim. We will construct an auxiliary problem from an instance ${\mathcal{P}}=(V,\tau,{\mathcal{C}})$ of $\#_{p}{\rm CSP}({\mathcal{H}})$ . Let $C=\langle{\bf s}_{C},\mathcal{R}_{j_{C}}\rangle$ be a constraint in ${\mathcal{P}}$ and ${\sf Sym}(\mathcal{R}_{j_{C}})$ the symmetric group on $\mathcal{R}_{j_{C}}$ as a set. We introduce an instance $s({\mathcal{P}})$ with domains ${\sf Sym}(\mathcal{R}_{j_{C}})$ , constraints that are derivative from the constraints of ${\mathcal{P}}$ and will allow us to conclude that either the $p$ -automorphic polynomial $f$ can be used to reduce ${\mathcal{P}}$ to a problem with smaller domains that are parts of ${\mathcal{H}}^{f}$ , or that ${\mathcal{P}}$ does not have solutions that are equal to certain elements of the domains and therefore, again, can be reduced to a problem with smaller domains.

More precisely, $s({\mathcal{P}})=(V^{\prime},\tau^{\prime},{\mathcal{C}}^{\prime})$ is constructed as follows.

$\blacksquare$

$V^{\prime}=\{v_{C}\mid C=\langle{\bf s}_{C},\mathcal{R}_{j_{C}}\rangle\in{% \mathcal{C}}\}$ and the domain of $v_{C}\in V^{\prime}$ is ${\sf Sym}(\mathcal{R}_{j_{C}})$ , that is, $\tau^{\prime}(v_{C})=j_{C}$ ;

\blacksquare

for any constraints $C_{1},C_{2}\in{\mathcal{C}}$ , $C_{q}=\langle{\bf s}_{C_{q}},\mathcal{R}_{j_{C_{q}}}\rangle$ such that ${\bf s}_{C_{1}}[s]={\bf s}_{C_{2}}[t]$ for some $s, t$ , introduce the constraint $\langle(v_{C_{1}},v_{C_{2}}),\mathcal{S}^{uv}_{st}\rangle\in{\mathcal{C}}^{\prime}$ , where $u=j_{C_{1}},v=j_{C_{2}}$ ,

	$\displaystyle\mathcal{S}^{uv}_{st}=\{(\varphi_{1},\varphi_{2})\mid$	$\displaystyle\varphi_{q}\in{\sf Sym}(\mathcal{R}_{j_{C_{q}}}),q\in\{1,2\},% \text{ and }\varphi_{1}({\bf a}_{1})[s]=\varphi_{2}({\bf a}_{2})[t]$
		$\displaystyle\text{ for any }{\bf a}_{1}\in\mathcal{R}_{j_{C_{1}}},{\bf a}_{2}% \in\mathcal{R}_{j_{C_{2}}}\text{ such that }{\bf a}_{1}[s]={\bf a}_{2}[t]\}.$

For an instance ${\mathcal{P}}=(V,\tau,{\mathcal{C}})$ of ${\rm CSP}({\mathcal{H}})$ , a collection $\{\varphi_{C}\mid C\in{\mathcal{C}}\}$ of permutations $\varphi_{C}:\mathcal{R}_{j_{C}}\to\mathcal{R}_{j_{C}}$ is said to be a consistent collection of permutations if for any $C_{1},C_{2}$ , $C_{q}=\langle{\bf s}_{C_{q}},\mathcal{R}_{j_{C_{q}}}\rangle$ , $q\in\{1,2\}$ and any ${\bf a}_{1}\in\mathcal{R}_{j_{C_{1}}},{\bf a}_{2}\in\mathcal{R}_{j_{C_{2}}}$ such that ${\rm pr}_{{\bf s}_{C_{1}}\cap{\bf s}_{C_{2}}}{\bf a}_{1}={\rm pr}_{{\bf s}_{C_% {1}}\cap{\bf s}_{C_{2}}}{\bf a}_{2}$ it holds that ${\rm pr}_{{\bf s}_{C_{1}}\cap{\bf s}_{C_{2}}}\varphi_{C_{1}}({\bf a}_{1})={\rm pr% }_{{\bf s}_{C_{1}}\cap{\bf s}_{C_{2}}}\varphi_{C_{2}}({\bf a}_{2})$ . It can be shown that each solution of $s({\mathcal{P}})$ provides a collection $\varphi=\{\varphi_{C}\}_{C\in{\mathcal{C}}}$ of consistent permutations for ${\mathcal{P}}$ .

Finding solutions to $s({\mathcal{P}})$ can also be done in polynomial time, because as every ${\sf Sym}(\mathcal{R}_{j})$ is a group, we can introduce a Mal’tsev operation $m=\{m_{j}\}_{i\in[\ell]}$ on the collection of ${\sf Sym}(\mathcal{R}_{j})$ , $j\in[\ell]$ , as follows: $m_{j}(x,y,z)=xy^{-1}z$ , where multiplication and inverse are as in the group ${\sf Sym}(\mathcal{R}_{j})$ . Then for any $u,v\in[\ell]$ and any $s\in[\hbox{ar}(\mathcal{R}_{u})],t\in[\hbox{ar}(\mathcal{R}_{v})]$ such that the types of the corresponding coordinates match, the mapping $m$ is a polymorphism of $\mathcal{S}^{uv}_{st}$ . By the results of [11] for any instance ${\mathcal{P}}$ of $\#_{p}{\rm CSP}({\mathcal{H}})$ the problem $s({\mathcal{P}})$ can be solved in polynomial time. Moreover, for any $C_{0}=\langle{\bf s}_{0},\mathcal{R}_{j_{0}}\rangle\in{\mathcal{C}}$ and $\varphi_{0}\in{\sf Sym}(\mathcal{R}_{j_{0}})$ , we can verify in polynomial time whether or not there is a consistent collection of mappings $\varphi=\{\varphi_{C}\}_{C\in{\mathcal{C}}}$ such that $\varphi_{C_{0}}=\varphi_{0}$ . With that in mind the following transformation of ${\mathcal{P}}$ can be performed in polynomial time.

Now, let ${\mathcal{H}}^{\prime}$ be constructed as explained before the proposition. Let $C_{0}=\langle{\bf s}_{0},\mathcal{R}_{j_{0}}\rangle\in{\mathcal{C}}$ be such that for some $v\in{\bf s}_{0}$ the type of $v$ is $H_{i}$ , say, ${\bf s}_{0}[s]=v$ , and there is ${\bf a}\in\mathcal{R}_{j_{0}}$ with ${\bf a}[s]=a$ . If there are no such $C_{0}$ and ${\bf a}$ , then $H_{i}$ can be either completely eliminated or it can be reduced by removing $a$ from it. Thus, ${\mathcal{P}}$ itself can be considered as an instance of $\#_{p}{\rm CSP}({\mathcal{H}}^{\prime})$ . Otherwise let $\varphi_{0}\in{\sf Sym}(\mathcal{R}_{j_{0}})$ be given by $\varphi_{0}({\bf x})=f({\bf a},{\bf x})$ . It is possible to verify whether or not there exists a solution $\varphi$ of $s({\mathcal{P}})$ such that $\varphi_{C_{0}}=\varphi_{0}$ . If such a solution exists, $H_{i}$ can be reduced by eliminating all the nontrivial orbits of $f_{i}(a,x)$ , since for any solution $\psi$ of ${\mathcal{P}}$ with $\psi(v)$ belonging to such an orbit, the mappings $\varphi(\psi),\varphi^{2}(\psi),\ldots,\varphi^{p-1}(\psi)$ are also different solutions of ${\mathcal{P}}$ and together they contribute 0 modulo $p$ into the number of solutions of ${\mathcal{P}}$ . Suppose such a solution does not exist. As is easily seen, if there is a solution $\psi$ of ${\mathcal{P}}$ such that $\psi({\bf s}_{0})={\bf a}$ , then the mappings $\varphi_{C}\in{\sf Sym}(\mathcal{R}_{j_{C}})$ , $C=\langle{\bf s},\mathcal{R}_{j_{C}}\rangle\in{\mathcal{C}}$ , given by $\varphi_{C}({\bf x})=f(\psi({\bf s}),{\bf x})$ , form a solution of $s({\mathcal{P}})$ with $\varphi_{C_{0}}=\varphi_{0}$ . Therefore, there is no such solution $\psi$ and the tuple ${\bf a}$ can be removed from $\mathcal{R}_{j_{0}}$ . Repeating this procedure for every ${\bf a}\in\mathcal{R}_{j_{0}}$ with ${\bf a}[s]=a$ we can either reduce the domain of $v$ by eliminating nontrivial orbits of $f_{i}(a,x)$ , or by eliminating $a$ . In both cases after applying this transformation to all constraints of ${\mathcal{P}}$ we obtain an instance of $\#_{p}{\rm CSP}({\mathcal{H}}^{\prime})$ .

Finally, repeating this construction for every $H_{i}$ and $a\in H_{i}$ such that $f_{i}(a,x)$ is a permutation of $H_{i}$ of order $p$ we arrive to an instance the required problem $\#_{p}{\rm CSP}({\mathcal{H}}^{f})$ . $\hfill\blacktriangleleft$

While Proposition 10 may help to prove that $\#_{p}{\rm CSP}({\mathcal{H}})$ is solvable in polynomial time, in order to prove hardness we also need the reverse reduction, which exists only under additional assumptions. The case we need is the following.

Corollary 11.

Let ${\mathcal{H}}$ be a 3-element single-sorted structure such that there is a 2-automorphic polynomial $f$ of ${\mathcal{H}}$ and for $a\in H$ the mapping $f(a,x)$ is a permutation of $H$ of order 2. Then, if $\{a\}$ and $H-\{a\}$ are 2-subalgebras of ${\mathcal{H}}$ , the structure ${\mathcal{H}}^{f}$ from Proposition 10 can be chosen such that $\#_{p}{\rm CSP}({\mathcal{H}})$ and $\#_{p}{\rm CSP}({\mathcal{H}}^{f})$ are polynomial time interreducible.

Proof.

In order to prove Corollary 11 we only need to show that the problem $\#_{p}{\rm CSP}({\mathcal{H}}^{f})$ is polynomial time reducible to $\#_{p}{\rm CSP}({\mathcal{H}})$ . Let $\mathcal{R}_{j}$ be a relation of ${\mathcal{H}}$ of arity $r$ . Then

\mathcal{R}^{\prime}_{j}=\mathcal{R}_{j}\cap(\{a\}\times\dots\times\{a\})\quad% \text{and}\quad\mathcal{R}^{\prime\prime}_{j}=\mathcal{R}_{j}\cap((H-\{a\})% \times\dots\times(H-\{a\})).

Since $\{a\}$ and $H-\{a\}$ are 2-subalgebras of ${\mathcal{H}}$ , the relations $\mathcal{R}^{\prime}_{j},\mathcal{R}^{\prime\prime}_{j}$ are $p$ -mpp-definable in ${\mathcal{H}}$ . The result follows from Proposition 6. $\hfill\blacktriangleleft$

Example 12.

Let ${\mathcal{H}}=(H;\mathcal{R},C_{H,a},a\in H)$ , where $H=\{0,\dots,p-1,p,p+1\}$ for some prime $p$ , $\mathcal{R}$ is the binary relation $H^{2}-\{(0,p),\dots,(p-1,p)\}$ , and $C_{H,a}$ is the constant relation $\{(a)\}$ . Since any automorphism of ${\mathcal{H}}$ must preserve $C_{H,a}$ for each $a\in H$ , the structure is rigid. However, it has a $p$ -automorphic polynomial $f$ given by

	$\displaystyle f(p,i)=f(p+1,i)=i+1\pmod{p},$	for $i\in\{0,\dots,p-1\}$ , and
	$\displaystyle f(x,y)=y$	$\displaystyle\text{otherwise}.$

If we now apply Proposition 10, the problem $\#_{p}{\rm CSP}({\mathcal{H}})$ can be reduced to $\#_{p}{\rm CSP}({\mathcal{H}}^{f})$ , where ${\mathcal{H}}^{f}$ is a multisorted structure with domains $\{p,p+1\}$ , $\{0,\dots,p-1\}$ , and the 1-element domains. The relations of ${\mathcal{H}}^{f}$ are all trivial, and so $\#_{p}{\rm CSP}({\mathcal{H}}^{f})$ is polynomial time solvable.

4 Tools for Reduction

This section introduces the main technical tools used in our reductions. First, we define indicator problems and explain how the existence of a Mal’tsev polymorphism relates to the presence of a specific predicate in the set of all (multi-sorted) pp-definable relations. Then, we apply all the constructions and tools that we developed in this section to two special classes of relational structures: $p$ -conservative and three-element structures.

4.1 Indicator Problem and Indicator Obstruction

In this section, we show that in many cases, if a relational structure ${\mathcal{H}}$ is not strongly $p$ -rectangular, then there is a rectangularity obstruction of a very specific kind. Recall that ([38]) for a (multi-sorted) relational structure ${\mathcal{H}}=(\{H_{i}\}_{i\in[k]};\mathcal{R}_{1},\ldots,\mathcal{R}_{\ell})$ , the ternary indicator problem ${\mathcal{I}}_{3}({\mathcal{H}})$ is an instance of ${\rm CSP}({\mathcal{H}})$ that characterizes the ternary polymorphisms of ${\mathcal{H}}$ .

$\blacksquare$

The set of variables $V$ is the set $H^{(3)}=H_{1}^{3}\cup\dots\cup H_{k}^{3}$ of all triples over the domains of ${\mathcal{H}}$ , i.e., for each triple ${\bf a}=({\bf a}[1],{\bf a}[2],{\bf a}[3])\in H_{i}^{3}$ , the set $V$ contains a variable $x_{\bf a}$ with domain $H_{i}$ .
$\blacksquare$

For every $s$ -ary relation $\mathcal{R}_{j}$ of type $(i_{1},\ldots,i_{s})$ from ${\mathcal{H}}$ and for any tuples ${\bf a}_{1},\dots,{\bf a}_{s}\in H^{(3)}$ , where each ${\bf a}_{q}=({\bf a}_{q}[1],{\bf a}_{q}[2],{\bf a}_{q}[3])\in H_{i_{q}}^{3}$ , we include the constraint $\left\langle(x_{{\bf a}_{1}},\dots,x_{{\bf a}_{s}}),\mathcal{R}_{j}\right\rangle$ in the instance ${\mathcal{I}}_{3}({\mathcal{H}})$ if for every $t\in[3]$ , the tuple $({\bf a}_{1}[t],\dots,{\bf a}_{s}[t])$ belongs to $\mathcal{R}_{j}$ . That is, the projection of the sequence $({\bf a}_{1},\dots,{\bf a}_{s})$ onto each coordinate $t\in[3]$ is a tuple in $\mathcal{R}_{j}$ .

As is easily seen, every solution of ${\mathcal{I}}_{3}({\mathcal{H}})$ defines a ternary multi-sorted operation $\{f_{i}\}_{i\in[k]}$ with $f_{i}:H_{i}^{3}\to H_{i}$ .

Example 13.

(a)

Let ${\mathcal{H}}_{1}$ be a relational structure with only one domain $H=\{0,1\}$ and one (binary) relation $\mathcal{R}=\{(0,1),(1,0)\}$ ,. Then ${\mathcal{I}}_{3}({\mathcal{H}}_{1})$ contains 8 variables $x_{000},x_{001},x_{010},x_{011},x_{100},$ $x_{101},x_{110},x_{111}$ , that is, all possible triples of elements of ${\mathcal{H}}$ , and the constraints are imposed on every pair $(x_{abc},x_{def})$ such that $(a,d),(b,e),(c,f)\in\mathcal{R}$ . In this case this means all pairs of “dual” variables of the form $(x_{abc},x_{\neg a\neg b\neg c})$ . Thus, the constraints are

$\langle(x_{000},x_{111}),\mathcal{R}\rangle,\langle(x_{001},x_{110}),\mathcal{% R}\rangle,\langle(x_{010},x_{101}),\mathcal{R}\rangle,\langle(x_{011},x_{100})% ,\mathcal{R}\rangle.$

(b)

For a structure ${\mathcal{H}}_{2}$ let the domain $H$ be the same set $\{0,1\}$ , but the only binary relation is given by $\mathcal{Q}=\{(0,0),(0,1),(1,0)\}$ . The set of variables of ${\mathcal{I}}_{3}({\mathcal{H}}_{2})$ is the same as before, but the constraints are very different. As is easily seen, the constraints in this case are

\hskip-40.00006pt\begin{array}[]{llllll}\langle(x_{000},x_{000}),\mathcal{Q}% \rangle&\langle(x_{000},x_{001}),\mathcal{Q}\rangle&\langle(x_{000},x_{010}),% \mathcal{Q}\rangle&\langle(x_{000},x_{011}),\mathcal{Q}\rangle&\langle(x_{000}% ,x_{100}),\mathcal{Q}\rangle&\langle(x_{000},x_{101}),\mathcal{Q}\rangle\\ \langle(x_{000},x_{110}),\mathcal{Q}\rangle&\langle(x_{000},x_{111}),\mathcal{% Q}\rangle&\langle(x_{001},x_{000}),\mathcal{Q}\rangle&\langle(x_{001},x_{010})% ,\mathcal{Q}\rangle&\langle(x_{001},x_{100}),\mathcal{Q}\rangle&\langle(x_{001% },x_{110}),\mathcal{Q}\rangle\\ \langle(x_{010},x_{000}),\mathcal{Q}\rangle&\langle(x_{010},x_{001}),\mathcal{% Q}\rangle&\langle(x_{010},x_{100}),\mathcal{Q}\rangle&\langle(x_{010},x_{101})% ,\mathcal{Q}\rangle&\langle(x_{100},x_{000}),\mathcal{Q}\rangle&\langle(x_{100% },x_{001}),\mathcal{Q}\rangle\\ \langle(x_{100},x_{010}),\mathcal{Q}\rangle&\langle(x_{100},x_{011}),\mathcal{% Q}\rangle&\langle(x_{011},x_{000}),\mathcal{Q}\rangle&\langle(x_{011},x_{100})% ,\mathcal{Q}\rangle&\langle(x_{101},x_{000}),\mathcal{Q}\rangle&\langle(x_{101% },x_{010}),\mathcal{Q}\rangle\\ \langle(x_{110},x_{000}),\mathcal{Q}\rangle&\langle(x_{110},x_{001}),\mathcal{% Q}\rangle&\langle(x_{111},x_{000}),\mathcal{Q}\rangle&&&\end{array}

$\lrcorner$

Lemma 14 ([38]).

For a (multi-sorted) relational structure ${\mathcal{H}}$ , a ternary (multi-sorted) operation on the domains of ${\mathcal{H}}$ is a solution of ${\mathcal{I}}_{3}({\mathcal{H}})$ if and only if it is a ternary polymorphism of ${\mathcal{H}}$ .

We will call the set of all solutions of ${\mathcal{I}}_{3}({\mathcal{H}})$ the indicator predicate $\Upsilon_{3}({\mathcal{H}})$ . It is not difficult to see that $\Upsilon_{3}({\mathcal{H}})$ is conjunctive-definable in ${\mathcal{H}}$ . Indeed, let ${\mathcal{C}}$ be the set of all constraints as defined above in ${\mathcal{I}}_{3}({\mathcal{H}})$ . Then we define the indicator predicate as the conjunction of all those constraints

\Upsilon_{3}({\mathcal{H}})({\bf x})=\bigwedge_{\langle{\bf s},\mathcal{R}_{j}% \rangle\in{\mathcal{C}}}\mathcal{R}_{j}({\bf s}),

where ${\bf x}$ is the tuple consisting of all variables $x_{(a,b,c)}$ indexed by triples $(a,b,c)\in H^{(3)}$ .

We now define certain coordinate sets used to analyze $\Upsilon_{3}({\mathcal{H}})$ . Let

I_{\mathcal{H}}=\{(a,b,b)\mid a,b\in H_{i},\ i\in[k]\},\quad J_{\mathcal{H}}=% \{(b,b,a)\mid a,b\in H_{i},\ i\in[k],\ a\neq b\}.

Note that the diagonal triples $(a,a,a)$ are included in $I_{\mathcal{H}}$ . Enumerate these sets as $I_{\mathcal{H}}=\{(a_{1},b_{1},b_{1}),\dots,(a_{N},b_{N},b_{N})\}$ , $J_{\mathcal{H}}=\{(c_{1},c_{1},d_{1}),\dots,(c_{M},c_{M},d_{M})\},$ and define tuples

{\bf a}_{\mathcal{H}}=(a_{1},\dots,a_{N}),\quad{\bf b}_{\mathcal{H}}=(b_{1},% \dots,b_{N}),\quad{\bf c}_{\mathcal{H}}=(c_{1},\dots,c_{M}),\quad{\bf d}_{% \mathcal{H}}=(d_{1},\dots,d_{M}).

Then ${\bf a}_{\mathcal{H}},{\bf b}_{\mathcal{H}}\in{\rm pr}_{I_{\mathcal{H}}}% \Upsilon_{3}({\mathcal{H}})$ , and ${\bf c}_{\mathcal{H}},{\bf d}_{\mathcal{H}}\in{\rm pr}_{J_{\mathcal{H}}}% \Upsilon_{3}({\mathcal{H}})$ . Also,

({\bf a}_{\mathcal{H}},{\bf c}_{\mathcal{H}}),({\bf b}_{\mathcal{H}},{\bf c}_{% \mathcal{H}}),({\bf b}_{\mathcal{H}},{\bf d}_{\mathcal{H}})\in{\rm pr}_{I_{% \mathcal{H}}\cup J_{\mathcal{H}}}\Upsilon_{3}({\mathcal{H}}).

Moreover, ${\mathcal{H}}$ admits a Mal’tsev polymorphism if and only if $({\bf a}_{\mathcal{H}},{\bf d}_{\mathcal{H}})\in{\rm pr}_{I_{\mathcal{H}}\cup J% _{\mathcal{H}}}\Upsilon_{3}({\mathcal{H}})$ .

Indeed, this condition tests whether the tuple $({\bf a}_{\mathcal{H}},{\bf d}_{\mathcal{H}})$ , which represents applying the Mal’tsev term coordinate-wise to the elements of each triple from $I_{\mathcal{H}}\cup J_{\mathcal{H}}$ , belongs to the projection of the relation $\Upsilon_{3}({\mathcal{H}})$ . That is, since $({\bf a}_{\mathcal{H}},{\bf c}_{\mathcal{H}}),\ ({\bf b}_{\mathcal{H}},{\bf c}% _{\mathcal{H}}),\ ({\bf b}_{\mathcal{H}},{\bf d}_{\mathcal{H}})\in{\rm pr}_{I_% {\mathcal{H}}\cup J_{\mathcal{H}}}\Upsilon_{3}({\mathcal{H}}),$ the closure under a Mal’tsev polymorphism would imply that the corresponding output tuple, $({\bf a}_{\mathcal{H}},{\bf d}_{\mathcal{H}})$ , must also be in the relation. So, its membership characterizes whether such a polymorphism exists.

Example 15.

Let us reconsider the structures ${\mathcal{H}}_{1},{\mathcal{H}}_{2}$ from Example 13 and their indicator problems. The following tables contain all the solutions of ${\mathcal{I}}_{3}({\mathcal{H}}_{1})$ and ${\mathcal{I}}_{3}({\mathcal{H}}_{2})$ , that is, the tuples of $\Upsilon_{3}({\mathcal{H}}_{1}),\Upsilon_{3}({\mathcal{H}}_{2})$ . The rows are labeled with the variables of ${\mathcal{I}}_{3}({\mathcal{H}}_{1}),{\mathcal{I}}_{3}({\mathcal{H}}_{2})$ .

	$\displaystyle\hskip-14.22636pt\Upsilon_{3}({\mathcal{H}}_{1}):\ \ \ \hskip 207% .70511pt\Upsilon_{3}({\mathcal{H}}_{2}):$
	$\displaystyle\hskip-11.38109pt\begin{array}[]{\|c\|\|c\|c\|c\|c\|c\|c\|c\|c\|c\|c\|c\|c\|c\|c\|% c\|c\|}x_{000}&0&0&0&0&0&0&0&0&1&1&1&1&1&1&1&1\\ x_{001}&0&0&1&1&0&0&1&1&0&0&1&1&0&0&1&1\\ x_{010}&0&1&0&1&0&1&0&1&0&1&0&1&0&1&0&1\\ x_{011}&0&1&1&0&1&0&0&1&0&0&0&1&1&1&1&0\\ x_{100}&1&0&0&1&0&1&1&0&1&1&1&0&0&0&0&1\\ x_{101}&1&0&1&0&1&0&1&0&1&0&1&0&1&0&1&0\\ x_{110}&1&1&0&0&1&1&0&0&1&1&0&0&1&1&0&0\\ x_{111}&1&1&1&1&1&1&1&1&0&0&0&0&0&0&0&0\\ \end{array}\quad\quad\begin{array}[]{\|c\|\|c\|c\|c\|c\|c\|c\|c\|c\|c\|}x_{000}&0&0&0&0&0&% 0&0&0&0\\ x_{001}&0&0&1&0&0&1&0&0&0\\ x_{010}&0&1&0&0&0&0&1&0&0\\ x_{011}&0&1&1&0&0&&&0&\\ x_{100}&1&0&0&0&0&0&0&1&0\\ x_{101}&1&0&1&0&0&&0&&\\ x_{110}&1&1&0&0&0&0&&&\\ x_{111}&1&1&1&0&1&&&&*\end{array}$

Every column in these tables represents a ternary polymorphism of ${\mathcal{H}}_{1},{\mathcal{H}}_{2}$ , respectively. Note that the first three polymorphisms in both cases are the projections, their values equal the first, second, and third component of the triple representing the label of variables of the indicator problem. Projections are polymorphisms of every structure, and therefore are always solutions of the indicator problem.

The relation $\Upsilon_{3}({\mathcal{H}}_{1})$ contains every polymorphism $f(x,y,z)$ satisfying the condition $f(\neg x,\neg y,\neg z)=\neg f(x,y,z)$ , also known as the condition of self-duality. The relation $\Upsilon_{3}({\mathcal{H}}_{2})$ cannot be described by such a simple condition. The stars in the table for $\Upsilon_{3}({\mathcal{H}}_{2})$ mean that no matter what values are in these positions, the tuple belongs to $\Upsilon_{3}({\mathcal{H}}_{2})$ .

The sets $I_{{\mathcal{H}}_{1}}=I_{{\mathcal{H}}_{2}}=\{000,011,100,111\}$ are equal in this case and so are $J_{{\mathcal{H}}_{1}}=J_{{\mathcal{H}}_{2}}=\{001,110\}$ . The special tuples ${\bf a}_{{\mathcal{H}}_{1}},{\bf b}_{{\mathcal{H}}_{1}},{\bf c}_{{\mathcal{H}}% _{1}},{\bf d}_{{\mathcal{H}}_{1}}$ and ${\bf a}_{{\mathcal{H}}_{2}},{\bf b}_{{\mathcal{H}}_{2}},{\bf c}_{{\mathcal{H}}% _{2}},{\bf d}_{{\mathcal{H}}_{2}}$ are also equal, as they are restrictions of the tuples corresponding to the same projections. Specifically,

{\bf a}_{{\mathcal{H}}_{1}}={\bf a}_{{\mathcal{H}}_{2}}=(0,0,1,1),\ {\bf b}_{{% \mathcal{H}}_{1}}={\bf b}_{{\mathcal{H}}_{2}}=(0,1,0,1),\ {\bf c}_{{\mathcal{H% }}_{1}}={\bf c}_{{\mathcal{H}}_{2}}=(0,1),\ {\bf d}_{{\mathcal{H}}_{1}}={\bf d% }_{{\mathcal{H}}_{2}}=(1,0).

As was observed, the presence of a Mal’tsev polymorphism is equivalent to the conditions

({\bf a}_{{\mathcal{H}}_{1}},{\bf d}_{{\mathcal{H}}_{1}})\in{\rm pr}_{I_{{% \mathcal{H}}_{1}}\cup J_{{\mathcal{H}}_{1}}}\Upsilon_{3}({\mathcal{H}}_{1}),% \quad({\bf a}_{{\mathcal{H}}_{2}},{\bf d}_{{\mathcal{H}}_{2}})\in{\rm pr}_{I_{% {\mathcal{H}}_{2}}\cup J_{{\mathcal{H}}_{2}}}\Upsilon_{3}({\mathcal{H}}_{2}),

that is $(0,0,1,1,1,0)\in{\rm pr}_{I_{{\mathcal{H}}_{1}}\cup J_{{\mathcal{H}}_{1}}}% \Upsilon_{3}({\mathcal{H}}_{1}),{\rm pr}_{I_{{\mathcal{H}}_{2}}\cup J_{{% \mathcal{H}}_{2}}}\Upsilon_{3}({\mathcal{H}}_{2}).$ It is not difficult to see that such a tuple exists in ${\rm pr}_{I_{{\mathcal{H}}_{1}}\cup J_{{\mathcal{H}}_{1}}}\Upsilon_{3}({% \mathcal{H}}_{1})$ , but not in ${\rm pr}_{I_{{\mathcal{H}}_{2}}\cup J_{{\mathcal{H}}_{2}}}\Upsilon_{3}({% \mathcal{H}}_{2})$ . $\lrcorner$

While $\Upsilon_{3}({\mathcal{H}})$ characterizes the ternary polymorphisms of ${\mathcal{H}}$ , we now define a construction that characterizes the ternary polymorphisms of $\langle{\mathcal{H}}\rangle_{p}$ .

Note that every polymorphism of $\langle{\mathcal{H}}\rangle_{p}$ is also a polymorphism of ${\mathcal{H}}$ . For any ternary polymorphism $f$ of ${\mathcal{H}}$ that is not a polymorphism of $\langle{\mathcal{H}}\rangle_{p}$ , there exists a relation $\mathcal{Q}_{f}\in\langle{\mathcal{H}}\rangle_{p}$ such that $f$ fails to preserve $\mathcal{Q}_{f}$ . Let ${\mathcal{H}}^{\dagger p}$ be the expansion of ${\mathcal{H}}$ by all such relations ${\mathcal{H}}^{\dagger p}={\mathcal{H}}+\{\mathcal{Q}_{f}\mid f\in{\sf Pol}_{3% }({\mathcal{H}})-{\sf Pol}_{3}(\langle{\mathcal{H}}\rangle_{p})\}.$ The following lemma is straightforward.

Lemma 16.

Let ${\mathcal{H}}$ be a (multi-sorted) relational structure. Then

1.

$\Upsilon_{3}({\mathcal{H}})$ is conjunctive-definable in ${\mathcal{H}}$ ,
2.

$\Upsilon_{3}({\mathcal{H}}^{\dagger p})$ is $p$ -mpp-definable in ${\mathcal{H}}$ .

If $\langle{\mathcal{H}}\rangle_{p}$ does not have a Mal’tsev polymorphism, then ${\mathcal{H}}^{\dagger p}$ also does not have a Mal’tsev polymorphism. Therefore, $({\bf a}_{\mathcal{H}},{\bf c}_{\mathcal{H}}),({\bf b}_{\mathcal{H}},{\bf c}_{% \mathcal{H}}),({\bf b}_{\mathcal{H}},{\bf d}_{\mathcal{H}})\in{\rm pr}_{I_{% \mathcal{H}}\cup J_{\mathcal{H}}}\Upsilon_{3}({\mathcal{H}}^{\dagger p})$ and $({\bf a}_{\mathcal{H}},{\bf d}_{\mathcal{H}})\not\in{\rm pr}_{I_{\mathcal{H}}% \cup J_{\mathcal{H}}}\Upsilon_{3}({\mathcal{H}}^{\dagger p})$ .

A relation $\mathcal{R}\subseteq{\rm pr}_{I_{\mathcal{H}}\cup J_{\mathcal{H}}}\Upsilon_{3}% ({\mathcal{H}}^{\dagger p})$ such that $({\bf a}_{\mathcal{H}},{\bf c}_{\mathcal{H}}),({\bf b}_{\mathcal{H}},{\bf c}_{% \mathcal{H}}),({\bf b}_{\mathcal{H}},{\bf d}_{\mathcal{H}})\in\mathcal{R}$ and $({\bf a}_{\mathcal{H}},{\bf d}_{\mathcal{H}})\not\in\mathcal{R}$ will be called a $p$ -indicator rectangularity obstruction. Clearly, if $\langle{\mathcal{H}}\rangle_{p}$ has no Mal’tsev polymorphism, ${\rm pr}_{I_{\mathcal{H}}\cup J_{\mathcal{H}}}\Upsilon_{3}({\mathcal{H}}^{% \dagger p})$ itself is a $p$ -indicator rectangularity obstruction. However, it may not be $p$ -mpp-definable in ${\mathcal{H}}$ . A relational structure ${\mathcal{H}}$ is said to admit a $p$ -indicator rectangularity obstruction if there exists a $p$ -indicator rectangularity obstruction $\mathcal{R}$ that is $p$ -mpp-definable in ${\mathcal{H}}$ .

Recall that for a multisorted structure ${\mathcal{H}}$ with domains $H_{1},\ldots,H_{k}$ we use $H^{(3)}$ to denote $H_{1}^{3}\cup\dots\cup H_{k}^{3}$ . An important ingredient in our construction is the study of automorphisms of ${\mathcal{H}}^{(3)}$ that fix certain structured tuples. Specifically, those of the form $(a,b,b)$ and $(b,b,a)$ . We refer to such automorphisms as M-automorphisms, with “M” standing for Mal’tsev.

The motivation for working with ${\mathcal{H}}^{(3)}$ comes from the need to apply our reduction tools in a higher-dimensional setting. While every automorphism of ${\mathcal{H}}^{(3)}$ induces a polymorphism of ${\mathcal{H}}$ via its coordinate projections, the converse does not hold: not every collection of polymorphisms arises as projections of a single automorphism of ${\mathcal{H}}^{(3)}$ . The notion of M-automorphisms captures precisely those symmetries of ${\mathcal{H}}^{(3)}$ that preserve the key tuples required for our connection to Mal’tsev polymorphisms. This connection will become essential later.

Let ${\bf x}=(x_{i})_{i\in{\mathcal{H}}^{(3)}}$ be the tuple of variables indexed by the elements of $H^{(3)}$ . For a subset $K\subseteq{\mathcal{H}}^{(3)}$ , we use the notation ${\bf x}_{\mid K}$ to denote the subtuple $(x_{i})_{i\in K}$ , that is, the variables whose indices belong to $K$ . The next lemma identifies conditions sufficient for ${\mathcal{H}}$ to admit a $p$ -indicator rectangularity obstruction. Define $E_{\mathcal{H}}=H^{(3)}-(I_{\mathcal{H}}\cup J_{\mathcal{H}})$ and $m=\hbox{ar}(\Upsilon_{3}({\mathcal{H}}))$ .

Lemma 17.

Let $\mathcal{R}({\bf x}_{|H^{(3)}-K})=\exists{\bf x}_{|K}\,\,\Upsilon_{3}({% \mathcal{H}}^{\dagger p})({\bf x})\wedge\Phi({\bf x}|_{K})$ , where $K\subseteq E_{\mathcal{H}}$ , and $\Phi$ is a conjunction of unary predicates on variables from $K$ such that $({\bf a}_{\mathcal{H}},{\bf c}_{\mathcal{H}}),({\bf b}_{\mathcal{H}},{\bf c}_{% \mathcal{H}}),({\bf b}_{\mathcal{H}},{\bf d}_{\mathcal{H}})\in{\rm pr}_{I_{% \mathcal{H}}\cup J_{\mathcal{H}}}\mathcal{R}.$ Let also $y\in E_{\mathcal{H}}-K$ and let

B_{1}={\rm pr}_{y}\mathsf{Ext}_{\mathcal{R}}({\bf a}_{\mathcal{H}},{\bf c}_{% \mathcal{H}}),\quad B_{2}={\rm pr}_{y}\mathsf{Ext}_{\mathcal{R}}({\bf b}_{% \mathcal{H}},{\bf c}_{\mathcal{H}}),\quad B_{3}={\rm pr}_{y}\mathsf{Ext}_{% \mathcal{R}}({\bf c}_{\mathcal{H}},{\bf d}_{\mathcal{H}}).

If $B_{1}\times B_{2}\times B_{3}$ contains a triple that is a fixed point of every M-automorphism of $({\mathcal{H}}^{\dagger p})^{3}$ then there is a $p$ -mpp-definable relation $\mathcal{Q}\subseteq{\rm pr}_{H^{(3)}-(K\cup\{y\})\mathcal{R}}$ in $\langle{\mathcal{H}}+\{\mathcal{R}\}\rangle_{p}$ such that $({\bf a}_{\mathcal{H}},{\bf c}_{\mathcal{H}}),({\bf b}_{\mathcal{H}},{\bf c}_{% \mathcal{H}}),({\bf b}_{\mathcal{H}},{\bf d}_{\mathcal{H}})\in{\rm pr}_{I_{% \mathcal{H}}\cup J_{\mathcal{H}}}\mathcal{Q}$ , and

|{\rm pr}_{y}(\mathsf{Ext}_{\mathcal{Q}}(({\bf a}_{\mathcal{H}},{\bf c}_{% \mathcal{H}})))|,|{\rm pr}_{y}(\mathsf{Ext}_{\mathcal{Q}}(({\bf b}_{\mathcal{H% }},{\bf c}_{\mathcal{H}})))|,|{\rm pr}_{y}(\mathsf{Ext}_{\mathcal{Q}}(({\bf b}% _{\mathcal{H}},{\bf d}_{\mathcal{H}})))|\not\equiv 0\pmod{p}.\\

Starting from $\Upsilon_{3}({\mathcal{H}}^{\dagger p})$ by repeated application of Lemma 17 we can obtain a relation $\mathcal{R}\subseteq{\rm pr}_{I_{\mathcal{H}}\cup J_{\mathcal{H}}}\Upsilon_{3}% ({\mathcal{H}}^{\dagger p})$ , which is a $p$ -indicator rectangularity obstruction.

4.2 Conservative and 3-Element Structures

In this section we use the results of Sections 3 and 4.1 to essentially show that in the case of a $p$ -conservative and 3-element structure ${\mathcal{H}}$ (single-sorted in the latter case) either there is a Mal’tsev polymorphism of $\langle{\mathcal{H}}\rangle_{p}$ or ${\mathcal{H}}$ admits a $p$ -indicator rectangularity obstruction. The latter will later be used to prove the hardness of the corresponding modular counting problem.

Recall that a multi-sorted relational structure ${\mathcal{H}}=(\{H_{i}\}_{i\in[k]};\mathcal{R}_{1},\dots,\mathcal{R}_{m})$ is said to be $p$ -conservative if for every $i\in[k]$ and every subset $A\subseteq H_{i}$ , the set $A$ is $p$ -mpp-definable in ${\mathcal{H}}$ (as a unary relation).

Theorem 18.

Let ${\mathcal{H}}$ be a $p$ -conservative structure. Then either $\langle{\mathcal{H}}\rangle_{p}$ has a Mal’tsev polymorphism, or ${\mathcal{H}}$ admits a $p$ -indicator rectangularity obstruction and therefore is not strongly $p$ -rectangular.

Proof (sketch).

We assume that $\langle{\mathcal{H}}\rangle_{p}$ has no Mal’tsev polymorphism. By Lemma 16, it suffices to show that $\Upsilon_{3}({\mathcal{H}}^{\dagger p})$ $p$ -mpp-defines a $p$ -indicator rectangularity obstruction.

Let $z_{1},\ldots,z_{L}$ be an ordering of the variables from the set $E_{\mathcal{H}}$ . We prove by induction that for any $q\in[L]$ , there exists a relation $\mathcal{Q}_{q}\subseteq{\rm pr}_{I_{\mathcal{H}}\cup J_{\mathcal{H}}\cup E_{q% }}\Upsilon_{3}({\mathcal{H}}^{\dagger p})$ , where $E_{q}=\{z_{q},\dots,z_{L}\}$ , such that $({\bf a}_{\mathcal{H}},{\bf c}_{\mathcal{H}}),({\bf b}_{\mathcal{H}},{\bf c}_{% \mathcal{H}}),({\bf b}_{\mathcal{H}},{\bf d}_{\mathcal{H}})\in{\rm pr}_{I_{% \mathcal{H}}\cup J_{\mathcal{H}}}\mathcal{Q}_{q}.$ Note that $\mathcal{Q}_{L+1}$ is the desired $p$ -indicator rectangularity obstruction. For the base case, let $\mathcal{Q}_{1}=\Upsilon_{3}({\mathcal{H}}^{\dagger p})$ , which satisfies the required condition, since $E_{1}=\{z_{1},\ldots,z_{L}\}$ .

Now suppose the statement holds for some $q$ and that $\mathcal{Q}_{q}$ is the corresponding relation. Consider the variable $z_{q}\in E_{q}$ , and let its domain be $H_{i}$ . Define the sets $B_{1},B_{2},B_{3}\subseteq H_{i}$ as the sets of values appearing at coordinate $z_{q}$ in the extensions of $({\bf a}_{\mathcal{H}},{\bf c}_{\mathcal{H}})$ , $({\bf b}_{\mathcal{H}},{\bf c}_{\mathcal{H}})$ , and $({\bf b}_{\mathcal{H}},{\bf d}_{\mathcal{H}})$ , respectively, within $\mathcal{Q}_{q}$ , i.e.,

B_{1}={\rm pr}_{z_{q}}\mathsf{Ext}_{\mathcal{Q}_{q}}({\bf a}_{\mathcal{H}},{% \bf c}_{\mathcal{H}}),\quad B_{2}={\rm pr}_{z_{q}}\mathsf{Ext}_{\mathcal{Q}_{q% }}({\bf b}_{\mathcal{H}},{\bf c}_{\mathcal{H}}),\quad B_{3}={\rm pr}_{z_{q}}% \mathsf{Ext}_{\mathcal{Q}_{q}}({\bf b}_{\mathcal{H}},{\bf d}_{\mathcal{H}}).

Let $D$ be a minimal set of representatives for $B_{1}$ , $B_{2}$ , and $B_{3}$ ; clearly, $|D|\leq 3$ . Let $\mathcal{Q}^{\prime}=\mathcal{Q}_{q}({\bf x}_{\mid I_{\mathcal{H}}\cup J_{% \mathcal{H}}\cup E_{q}})\wedge D(z_{q})$ . We then consider several cases depending on the cardinality of $D$ and use Lemma 17 to show that $z_{q}$ can be quantified away from $\mathcal{Q}^{\prime}$ via applying a $p$ -modular quantifier to it. $\hfill\blacktriangleleft$

Next, we assume ${\mathcal{H}}$ to be a 3-element (single-sorted) structure $(H,\mathcal{R}_{1},\ldots,\mathcal{R}_{\ell})$ , where $H=\{0,1,2\}$ . The main result of this section is the following theorem.

Theorem 19.

Let ${\mathcal{H}}$ be a 3-element structure. Then one of the following three options holds

(1)

$\langle{\mathcal{H}}\rangle_{p}$ has a Mal’tsev polymorphism and therefore ${\mathcal{H}}$ is strongly $p$ -rectangular;
(2)

${\mathcal{H}}$ admits a $p$ -indicator rectangularity obstruction;
(3)

$p=2$ and ${\mathcal{H}}$ has a $p$ -automorphic polynomial $f$ , there is $a\in H$ such that $f(a,x)$ is a permutation of order 2, and $H-\{a\}$ is a $p$ -subalgebra of ${\mathcal{H}}$ .

Proof (idea).

In this case we follow the same approach as in the proof of Theorem 18, except in some cases it is not possible to show that $z_{q}$ can be quantified away from $\mathcal{Q}^{\prime}$ . The reason for that is M-automorphisms of $({\mathcal{H}}^{\dagger p})^{3}$ that act nontrivially on $B_{1}\times B_{2}\times B_{3}$ . So, we prove that whenever such an M-automorphism is present, ${\mathcal{H}}$ has a $p$ -automorphic polynomial. This is done by a large case analysis using the Universal Algebra Calculator [29]. $\hfill\blacktriangleleft$

5 Complexity Classifications

We start this section with an (incomplete) complexity classification of $\#_{p}{\rm CSP}({\mathcal{H}})$ , where ${\mathcal{H}}$ is a $p$ -conservative structure. The missing case is $p>2$ and $\langle{\mathcal{H}}\rangle_{p}$ has a Mal’tsev polymorphism. The gap is due the lack of understanding of the complexity of partition functions over nontrivial finite fields. It is a highly nontrivial problem that requires a separate study, see [39] for some partial results.

We start with proving hardness for structures whose domains are 2-element. The proposition below generalizes the results of Faben [25] to multisorted CSPs.

Proposition 20.

Let ${\mathcal{H}}$ be a multi-sorted relational structure, all of whose domains contain at most 2 elements. The problem $\#_{p}{\rm CSP}({\mathcal{H}})$ is solvable in polynomial time if and only if $\langle{\mathcal{H}}\rangle_{p}$ has a Mal’tsev polymorphism. Otherwise it is $\#_{p}P$ -hard.

Proof (idea).

If $\langle{\mathcal{H}}\rangle_{p}$ does not have a Mal’tsev polymorphism, by Theorem 18 a $p$ -indicator rectangularity obstruction $\mathcal{R}$ is $p$ -mpp-definable in ${\mathcal{H}}$ . We start with the obstruction $\mathcal{R}$ and then recursively quantify away coordinates of $\mathcal{R}$ by applying $p$ -modular quantifiers (which requires significant care) until we obtain a binary non-rectangular relation, for which hardness is known by [25].

Now, suppose that $\langle{\mathcal{H}}\rangle_{p}$ has a Mal’tsev polymorphism. It is known that if a single-sorted 2-element relational structure has a Mal’tsev polymorphism then it also has the operation $x\oplus y\oplus z$ as a polymorphism [44], where $\oplus$ is addition modulo 2. This means that for every domain $H_{i}$ of ${\mathcal{H}}$ there is a polymorphism $m^{i}$ of $\langle{\mathcal{H}}\rangle_{p}$ that acts like $x\oplus y\oplus z$ if $H_{i}$ is equipped with addition $\oplus$ modulo 2. The main step of the proof is to show that all the $m^{i}$ can be chosen the same. Therefore ${\rm CSP}({\mathcal{H}})$ can be represented by a system of linear equations modulo 2, for which the exact number of solutions can be found. $\hfill\blacktriangleleft$

Theorem 21.

Let ${\mathcal{H}}$ be a conservative structure and $p$ a prime. If $\langle{\mathcal{H}}\rangle_{p}$ does not have a Mal’tsev polymorphism then $\#_{p}{\rm CSP}({\mathcal{H}})$ is $\#_{p}P$ -hard. If $\langle{\mathcal{H}}\rangle_{2}$ has a Mal’tsev polymorphism then $\#_{2}{\rm CSP}({\mathcal{H}})$ is solvable in polynomial time.

Proof.

The second statement of the theorem follows from Theorem 8. For the first statement, by Theorem 18 a $p$ -indicator rectangularity obstruction $\mathcal{R}$ is $p$ -mpp-definable in ${\mathcal{H}}$ . Recall that $({\bf a}_{\mathcal{H}},{\bf c}_{\mathcal{H}}),({\bf b}_{\mathcal{H}},{\bf c}_{% \mathcal{H}}),({\bf b}_{\mathcal{H}},{\bf d}_{\mathcal{H}})\in\mathcal{R},$ while $({\bf a}_{\mathcal{H}},{\bf d}_{\mathcal{H}})\not\in\mathcal{R}$ . As ${\mathcal{H}}$ is conservative, for every $v\in I_{\mathcal{H}}$ ( $v\in J_{\mathcal{H}}$ ), $H_{i_{v}}=\{{\bf a}[v],{\bf b}[v]\}$ ( $H_{i_{v}}=\{{\bf c}[v],{\bf d}[v]\}$ ) is a $p$ -subalgebra of ${\mathcal{H}}$ . Set

\mathcal{R}^{\prime}({\bf x}_{|I_{\mathcal{H}}\cup J_{\mathcal{H}}})=\mathcal{% R}({\bf x}_{|I_{\mathcal{H}}\cup J_{\mathcal{H}}})\wedge\bigwedge_{v\in I_{% \mathcal{H}}\cup J_{\mathcal{H}}}H_{i_{v}}({\bf x}_{v}).

The relation $\mathcal{R}^{\prime}$ still contains $({\bf a}_{\mathcal{H}},{\bf c}_{\mathcal{H}}),({\bf b}_{\mathcal{H}},{\bf c}_{% \mathcal{H}}),({\bf b}_{\mathcal{H}},{\bf d}_{\mathcal{H}})$ and does not contain $({\bf a}_{\mathcal{H}},{\bf d}_{\mathcal{H}})$ . By Proposition 20 $\#_{p}{\rm CSP}(\mathcal{R}^{\prime})$ is $\#_{p}P$ -hard. $\hfill\blacktriangleleft$

Next, we consider the case when ${\mathcal{H}}$ is a 3-element structure.

Theorem 22.

Let ${\mathcal{H}}$ be a 3-element structure and $p$ a prime. If one of the following conditions holds:

(a)

${\mathcal{H}}$ has a $p$ -automorphic polynomial $f$ and $\langle{\mathcal{H}}^{f}\rangle_{p}$ has a Mal’tsev polymorphism, or
(b)

${\mathcal{H}}$ does not have a $p$ -automorphic polynomial, $\langle{\mathcal{H}}\rangle_{p}$ has a Mal’tsev polymorphism, and $p=2$ ,

then $\#_{p}{\rm CSP}({\mathcal{H}})$ is solvable in polynomial time. Also, if

(1)

${\mathcal{H}}$ has a $p$ -automorphic polynomial $f$ and $\langle{\mathcal{H}}^{f}\rangle_{p}$ does not have a Mal’tsev polymorphism, or
(2)

${\mathcal{H}}$ does not have a $p$ -automorphic polynomial and $\langle{\mathcal{H}}\rangle_{p}$ does not have a Mal’tsev polymorphism,

then $\#_{p}{\rm CSP}({\mathcal{H}})$ is $\#_{p}P$ -complete.

Proof (idea).

If ${\mathcal{H}}$ has a $p$ -automorphic polynomial then $p=2$ , and the result follows from Corollary 11 and Proposition 20. If $\langle{\mathcal{H}}\rangle_{p}$ has a Mal’tsev polymorphism and $p=2$ , the result follows from Theorem 8. Therefore, we assume that $\langle{\mathcal{H}}\rangle_{p}$ has no Mal’tsev polymorphism and ${\mathcal{H}}$ does not have a $p$ -automorphic polynomial. By Theorem 19 a $p$ -indicator rectangularity obstruction $\mathcal{R}$ is $p$ -mpp-definable in ${\mathcal{H}}$ . We prove that it is possible to $p$ -mpp-define a binary non-rectangular relation showing that $\#_{p}{\rm CSP}({\mathcal{H}})$ is $\#_{p}P$ -complete. Unlike the case of $p$ -conservative structures, it is not possible to restrict $\mathcal{R}$ with arbitrary subsets of $H$ , because they may not be $p$ -subalgebras. We therefore use an approach similar to that in the proof of Theorem 21, except every possible combination of $p$ -subalgebras of ${\mathcal{H}}$ is considered separately. $\hfill\blacktriangleleft$

References

[1] Libor Barto. The dichotomy for conservative constraint satisfaction problems revisited. In LICS 2011, pages 301–310, 2011. doi:10.1109/LICS.2011.25.
[2] Libor Barto and Marcin Kozik. Constraint satisfaction problems solvable by local consistency methods. J. ACM, 61(1):3:1–3:19, 2014. doi:10.1145/2556646.
[3] Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and how to use them. In Dagstuhl Follow-Ups, volume 7. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/DFU.VOL7.15301.1.
[4] Alexander I. Barvinok. Combinatorics and Complexity of Partition Functions, volume 30 of Algorithms and Combinatorics. Springer, 2016. doi:10.1007/978-3-319-51829-9.
[5] Christoph Berkholz and Martin Grohe. Limitations of algebraic approaches to graph isomorphism testing. In ICALP 2015, volume 9134 of LNCS, pages 155–166. Springer, 2015. doi:10.1007/978-3-662-47672-7_13.
[6] Andrei A. Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM, 53(1):66–120, 2006. doi:10.1145/1120582.1120584.
[7] Andrei A. Bulatov. Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log., 12(4):24:1–24:66, 2011. doi:10.1145/1970398.1970400.
[8] Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. J. ACM, 60(5):34:1–34:41, 2013. doi:10.1145/2528400.
[9] Andrei A. Bulatov. Conservative constraint satisfaction re-revisited. J. Comput. Syst. Sci., 82(2):347–356, 2016. doi:10.1016/J.JCSS.2015.07.004.
[10] Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In FOCS, pages 319–330, 2017. doi:10.1109/FOCS.2017.37.
[11] Andrei A. Bulatov and Víctor Dalmau. A simple algorithm for Mal’tsev constraints. SIAM J. Comput., 36(1):16–27, 2006. doi:10.1137/050628957.
[12] Andrei A. Bulatov and Víctor Dalmau. Towards a dichotomy theorem for the counting constraint satisfaction problem. Information and Computation, 205(5):651–678, 2007. doi:10.1016/J.IC.2006.09.005.
[13] Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, and David Richerby. The complexity of weighted and unweighted #CSP. J. Comp. Syst. Sci., 78(2):681–688, 2012. doi:10.1016/J.JCSS.2011.12.002.
[14] Andrei A. Bulatov and Martin Grohe. The complexity of partition functions. Theor. Comput. Sci., 348(2-3):148–186, 2005. doi:10.1016/J.TCS.2005.09.011.
[15] Andrei A. Bulatov, Peter Jeavons, and Andrei A. Krokhin. Classifying the complexity of constraints using finite algebras. SIAM J. Comput., 34(3):720–742, 2005. doi:10.1137/S0097539700376676.
[16] Andrei A. Bulatov and Amirhossein Kazeminia. Complexity classification of counting graph homomorphisms modulo a prime number. In STOC, pages 1024–1037, 2022. doi:10.1145/3519935.3520075.
[17] Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights. J. ACM, 64(3), 2017. doi:10.1145/2822891.
[18] Jin-yi Cai, Xi Chen, and Pinyan Lu. Graph homomorphisms with complex values: A dichotomy theorem. In ICALP 2010, volume 6198 of LNCS, pages 275–286. Springer, 2010. doi:10.1007/978-3-642-14165-2_24.
[19] Jin-Yi Cai, Xi Chen, and Pinyan Lu. Nonnegative weighted #CSP: An effective complexity dichotomy. SIAM J. Comput., 45(6):2177–2198, 2016. doi:10.1137/15M1032314.
[20] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. The complexity of complex weighted Boolean #CSP. J. Comput. Syst. Sci., 80(1):217–236, 2014. doi:10.1016/J.JCSS.2013.07.003.
[21] Nadia Creignou and Miki Hermann. Complexity of generalized satisfiability counting problems. Inf. Comput., 125(1):1–12, 1996. doi:10.1006/INCO.1996.0016.
[22] Martin Dyer and Catherine Greenhill. The complexity of counting graph homomorphisms. Random Structures and Algorithms, 17:260–289, 2000. doi:10.1002/1098-2418(200010/12)17:3/4\%3C260::AID-RSA5\%3E3.0.CO;2-W.
[23] Martin Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM J on Comp, 42(3):1245–1274, 2013. doi:10.1137/100811258.
[24] Martin E. Dyer, Leslie Ann Goldberg, and Mark Jerrum. The complexity of weighted Boolean #CSP. SIAM J. Comput., 38(5):1970–1986, 2009. doi:10.1137/070690201.
[25] John Faben. The complexity of counting solutions to generalised satisfiability problems modulo $k$ , 2008. arXiv:0809.1836.
[26] John Faben and Mark Jerrum. The complexity of parity graph homomorphism: an initial investigation. arXiv preprint arXiv:1309.4033, 2013. arXiv:1309.4033.
[27] Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM J. Comput., 28(1):57–104, 1998. doi:10.1137/S0097539794266766.
[28] Jacob Focke, Leslie Ann Goldberg, Marc Roth, and Stanislav Zivny. Counting homomorphisms to $K_{4}$ -minor-free graphs, modulo 2. CoRR, abs/2006.16632, 2020. arXiv:2006.16632.
[29] Ralph Freese and Emil Kiss. Universal algebra calculator. Available at http://uacalc.org/.
[30] Andreas Göbel, Leslie Ann Goldberg, and David Richerby. Counting homomorphisms to square-free graphs, modulo 2. ACM Transactions on Computation Theory (TOCT), 8(3):1–29, 2016. doi:10.1145/2898441.
[31] Andreas Göbel, J. A. Gregor Lagodzinski, and Karen Seidel. Counting homomorphisms to trees modulo a prime. In MFCS, volume 117, pages 49:1–49:13, 2018. doi:10.4230/LIPIcs.MFCS.2018.49.
[32] Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley. A complexity dichotomy for partition functions with mixed signs. SIAM J. Comput., 39(7):3336–3402, 2010. doi:10.1137/090757496.
[33] Andreas Göbel, Leslie Ann Goldberg, and David Richerby. The complexity of counting homomorphisms to cactus graphs modulo 2. ACM Trans on Comp Th, 6(4):1–29, 2014. doi:10.1145/2635825.
[34] J. Hagemann and A. Mitschke. On $n$ -permutable congruences. Algebra Universalis, 3:8–12, 1973.
[35] Richard Hammack, Wilfried Imrich, and Sandi Klavzar. Handbook of Product Graphs, Second Edition. CRC Press, Inc., USA, 2nd edition, 2011.
[36] Pawel M. Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote, and Ross Willard. Tractability and learnability arising from algebras with few subpowers. SIAM J. Comput., 39(7):3023–3037, 2010. doi:10.1137/090775646.
[37] Peter Jeavons. On the algebraic structure of combinatorial problems. Theoretical Computer Science, 200(1-2):185–204, 1998. doi:10.1016/S0304-3975(97)00230-2.
[38] P.G. Jeavons, D.A. Cohen, and M. Gyssens. How to determine the expressive power of constraints. Constraints, 4:113–131, 1999. doi:10.1023/A:1009890709297.
[39] Amirhossein Kazeminia. Complexity of Modular Counting. PhD thesis, Simon Fraser University, 2025.
[40] Amirhossein Kazeminia and Andrei A Bulatov. Counting homomorphisms modulo a prime number. In MFCS, volume 138 of LIPIcs, pages 59:1–59:13, 2019. doi:10.4230/LIPIcs.MFCS.2019.59.
[41] Amirhossein Kazeminia and Andrei A. Bulatov. Modular counting CSP: reductions and algorithms. In STACS 2025, volume 327 of LIPIcs, pages 60:1–60:18, 2025. doi:10.4230/LIPIcs.STACS.2025.60.
[42] Amirhossein Kazeminia and Andrei A. Bulatov. Modular counting CSP: reductions and algorithms. CoRR, abs/2501.04224, 2025. doi:10.48550/arXiv.2501.04224.
[43] J. A. Gregor Lagodzinski, Andreas Göbel, Katrin Casel, and Tobias Friedrich. On counting (quantum-) graph homomorphisms in finite fields of prime order. CoRR, abs/2011.04827, 2021. arXiv:2011.04827.
[44] Emil L. Post. The two-valued iterative systems of mathematical logic, volume 5 of Annals Mathematical Studies. Princeton University Press, 1941.
[45] Leslie Valiant. The complexity of computing the permanent. Theor. Comput. Sci., 8:189–201, 1979. doi:10.1016/0304-3975(79)90044-6.
[46] Leslie Valiant. The complexity of enumeration and reliability problems. SIAM J. on Comput., 8(3):410–421, 1979. doi:10.1137/0208032.
[47] Dominic J.A. Welsh. The computational complexity of some classical problems from statistical physics. Oxford Univ. Press, 1990.
[48] Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67(5):30:1–30:78, 2020. doi:10.1145/3402029.

[bib.bib1] [1] Libor Barto. The dichotomy for conservative constraint satisfaction problems revisited. In LICS 2011, pages 301–310, 2011. doi:10.1109/LICS.2011.25.

[bib.bib2] [2] Libor Barto and Marcin Kozik. Constraint satisfaction problems solvable by local consistency methods. J. ACM, 61(1):3:1–3:19, 2014. doi:10.1145/2556646.

[bib.bib3] [3] Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and how to use them. In Dagstuhl Follow-Ups, volume 7. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/DFU.VOL7.15301.1.

[bib.bib4] [4] Alexander I. Barvinok. Combinatorics and Complexity of Partition Functions, volume 30 of Algorithms and Combinatorics. Springer, 2016. doi:10.1007/978-3-319-51829-9.

[bib.bib5] [5] Christoph Berkholz and Martin Grohe. Limitations of algebraic approaches to graph isomorphism testing. In ICALP 2015, volume 9134 of LNCS, pages 155–166. Springer, 2015. doi:10.1007/978-3-662-47672-7_13.

[bib.bib6] [6] Andrei A. Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM, 53(1):66–120, 2006. doi:10.1145/1120582.1120584.

[bib.bib7] [7] Andrei A. Bulatov. Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log., 12(4):24:1–24:66, 2011. doi:10.1145/1970398.1970400.

[bib.bib8] [8] Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. J. ACM, 60(5):34:1–34:41, 2013. doi:10.1145/2528400.

[bib.bib9] [9] Andrei A. Bulatov. Conservative constraint satisfaction re-revisited. J. Comput. Syst. Sci., 82(2):347–356, 2016. doi:10.1016/J.JCSS.2015.07.004.

[bib.bib10] [10] Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In FOCS, pages 319–330, 2017. doi:10.1109/FOCS.2017.37.

[bib.bib11] [11] Andrei A. Bulatov and Víctor Dalmau. A simple algorithm for Mal’tsev constraints. SIAM J. Comput., 36(1):16–27, 2006. doi:10.1137/050628957.

[bib.bib12] [12] Andrei A. Bulatov and Víctor Dalmau. Towards a dichotomy theorem for the counting constraint satisfaction problem. Information and Computation, 205(5):651–678, 2007. doi:10.1016/J.IC.2006.09.005.

[bib.bib13] [13] Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, and David Richerby. The complexity of weighted and unweighted #CSP. J. Comp. Syst. Sci., 78(2):681–688, 2012. doi:10.1016/J.JCSS.2011.12.002.

[bib.bib14] [14] Andrei A. Bulatov and Martin Grohe. The complexity of partition functions. Theor. Comput. Sci., 348(2-3):148–186, 2005. doi:10.1016/J.TCS.2005.09.011.

[bib.bib15] [15] Andrei A. Bulatov, Peter Jeavons, and Andrei A. Krokhin. Classifying the complexity of constraints using finite algebras. SIAM J. Comput., 34(3):720–742, 2005. doi:10.1137/S0097539700376676.

[bib.bib16] [16] Andrei A. Bulatov and Amirhossein Kazeminia. Complexity classification of counting graph homomorphisms modulo a prime number. In STOC, pages 1024–1037, 2022. doi:10.1145/3519935.3520075.

[bib.bib17] [17] Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights. J. ACM, 64(3), 2017. doi:10.1145/2822891.

[bib.bib18] [18] Jin-yi Cai, Xi Chen, and Pinyan Lu. Graph homomorphisms with complex values: A dichotomy theorem. In ICALP 2010, volume 6198 of LNCS, pages 275–286. Springer, 2010. doi:10.1007/978-3-642-14165-2_24.

[bib.bib19] [19] Jin-Yi Cai, Xi Chen, and Pinyan Lu. Nonnegative weighted #CSP: An effective complexity dichotomy. SIAM J. Comput., 45(6):2177–2198, 2016. doi:10.1137/15M1032314.

[bib.bib20] [20] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. The complexity of complex weighted Boolean #CSP. J. Comput. Syst. Sci., 80(1):217–236, 2014. doi:10.1016/J.JCSS.2013.07.003.

[bib.bib21] [21] Nadia Creignou and Miki Hermann. Complexity of generalized satisfiability counting problems. Inf. Comput., 125(1):1–12, 1996. doi:10.1006/INCO.1996.0016.

[bib.bib22] [22] Martin Dyer and Catherine Greenhill. The complexity of counting graph homomorphisms. Random Structures and Algorithms, 17:260–289, 2000. doi:10.1002/1098-2418(200010/12)17:3/4\%3C260::AID-RSA5\%3E3.0.CO;2-W.

[bib.bib23] [23] Martin Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM J on Comp, 42(3):1245–1274, 2013. doi:10.1137/100811258.

[bib.bib24] [24] Martin E. Dyer, Leslie Ann Goldberg, and Mark Jerrum. The complexity of weighted Boolean #CSP. SIAM J. Comput., 38(5):1970–1986, 2009. doi:10.1137/070690201.

[bib.bib25] [25] John Faben. The complexity of counting solutions to generalised satisfiability problems modulo $k$ , 2008. arXiv:0809.1836.

[bib.bib26] [26] John Faben and Mark Jerrum. The complexity of parity graph homomorphism: an initial investigation. arXiv preprint arXiv:1309.4033, 2013. arXiv:1309.4033.

[bib.bib27] [27] Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM J. Comput., 28(1):57–104, 1998. doi:10.1137/S0097539794266766.

[bib.bib28] [28] Jacob Focke, Leslie Ann Goldberg, Marc Roth, and Stanislav Zivny. Counting homomorphisms to $K_{4}$ -minor-free graphs, modulo 2. CoRR, abs/2006.16632, 2020. arXiv:2006.16632.

[bib.bib29] [29] Ralph Freese and Emil Kiss. Universal algebra calculator. Available at http://uacalc.org/.

[bib.bib30] [30] Andreas Göbel, Leslie Ann Goldberg, and David Richerby. Counting homomorphisms to square-free graphs, modulo 2. ACM Transactions on Computation Theory (TOCT), 8(3):1–29, 2016. doi:10.1145/2898441.

[bib.bib31] [31] Andreas Göbel, J. A. Gregor Lagodzinski, and Karen Seidel. Counting homomorphisms to trees modulo a prime. In MFCS, volume 117, pages 49:1–49:13, 2018. doi:10.4230/LIPIcs.MFCS.2018.49.

[bib.bib32] [32] Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley. A complexity dichotomy for partition functions with mixed signs. SIAM J. Comput., 39(7):3336–3402, 2010. doi:10.1137/090757496.

[bib.bib33] [33] Andreas Göbel, Leslie Ann Goldberg, and David Richerby. The complexity of counting homomorphisms to cactus graphs modulo 2. ACM Trans on Comp Th, 6(4):1–29, 2014. doi:10.1145/2635825.

[bib.bib34] [34] J. Hagemann and A. Mitschke. On $n$ -permutable congruences. Algebra Universalis, 3:8–12, 1973.

[bib.bib35] [35] Richard Hammack, Wilfried Imrich, and Sandi Klavzar. Handbook of Product Graphs, Second Edition. CRC Press, Inc., USA, 2nd edition, 2011.

[bib.bib36] [36] Pawel M. Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote, and Ross Willard. Tractability and learnability arising from algebras with few subpowers. SIAM J. Comput., 39(7):3023–3037, 2010. doi:10.1137/090775646.

[bib.bib37] [37] Peter Jeavons. On the algebraic structure of combinatorial problems. Theoretical Computer Science, 200(1-2):185–204, 1998. doi:10.1016/S0304-3975(97)00230-2.

[bib.bib38] [38] P.G. Jeavons, D.A. Cohen, and M. Gyssens. How to determine the expressive power of constraints. Constraints, 4:113–131, 1999. doi:10.1023/A:1009890709297.

[bib.bib39] [39] Amirhossein Kazeminia. Complexity of Modular Counting. PhD thesis, Simon Fraser University, 2025.

[bib.bib40] [40] Amirhossein Kazeminia and Andrei A Bulatov. Counting homomorphisms modulo a prime number. In MFCS, volume 138 of LIPIcs, pages 59:1–59:13, 2019. doi:10.4230/LIPIcs.MFCS.2019.59.

[bib.bib41] [41] Amirhossein Kazeminia and Andrei A. Bulatov. Modular counting CSP: reductions and algorithms. In STACS 2025, volume 327 of LIPIcs, pages 60:1–60:18, 2025. doi:10.4230/LIPIcs.STACS.2025.60.

[bib.bib42] [42] Amirhossein Kazeminia and Andrei A. Bulatov. Modular counting CSP: reductions and algorithms. CoRR, abs/2501.04224, 2025. doi:10.48550/arXiv.2501.04224.

[bib.bib43] [43] J. A. Gregor Lagodzinski, Andreas Göbel, Katrin Casel, and Tobias Friedrich. On counting (quantum-) graph homomorphisms in finite fields of prime order. CoRR, abs/2011.04827, 2021. arXiv:2011.04827.

[bib.bib44] [44] Emil L. Post. The two-valued iterative systems of mathematical logic, volume 5 of Annals Mathematical Studies. Princeton University Press, 1941.

[bib.bib45] [45] Leslie Valiant. The complexity of computing the permanent. Theor. Comput. Sci., 8:189–201, 1979. doi:10.1016/0304-3975(79)90044-6.

[bib.bib46] [46] Leslie Valiant. The complexity of enumeration and reliability problems. SIAM J. on Comput., 8(3):410–421, 1979. doi:10.1137/0208032.

[bib.bib47] [47] Dominic J.A. Welsh. The computational complexity of some classical problems from statistical physics. Oxford Univ. Press, 1990.

[bib.bib48] [48] Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67(5):30:1–30:78, 2020. doi:10.1145/3402029.

Modular Counting over 3-Element and Conservative Domains

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

The Constraint Satisfaction Problem.

Modular counting.

Existing results.

Our contribution.

Proposition 1.

Theorem 2.

Theorem 3.

2 Preliminaries

2.1 Relational structures

Proposition 4 ([41]).

2.2 The CSP and Modular Counting

2.3 Expansions of Relational Structures and the CSP

Proposition 5 ([41]).

Proposition 6 ([41]).

2.4 Polymorphisms and Automorphisms of Products

Lemma 7 ([34], see also [23]).

Theorem 8 ([41, 42]).

Lemma 9.

3 Automorphic Polynomials

Proposition 10.

Proof (sketch).

Corollary 11.

Proof.

Example 12.

4 Tools for Reduction

4.1 Indicator Problem and Indicator Obstruction

Example 13.

Lemma 14 ([38]).

Example 15.

Lemma 16.

Lemma 17.

4.2 Conservative and 3-Element Structures

Theorem 18.

Proof (sketch).

Theorem 19.

Proof (idea).

5 Complexity Classifications

Proposition 20.

Proof (idea).

Theorem 21.

Proof.

Theorem 22.

Proof (idea).

References