Modular Counting CSP: Reductions and Algorithms

We begin with introducing multi-sorted or typed sets. Let $H=\{H_{i}\}_{{i\in[k]}}=\{H_{1},\dots,H_{k}\}$ be a collection of sets. We will assume that the sets $H_{1},\dots,H_{k}$ are disjoint. The cardinality of a multi-sorted set $H$ equals $|H|=\sum_{i\in[k]}|H_{i}|$. 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 $\{1,\dots,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, and a tuple $(i_{1},\dots,i_{\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}}}}$ and $(i_{1},\dots,i_{\ell_{\mathcal{R}}})$ is called the type of $\mathcal{R}$. The multi-sorted structure $\mathcal{H}$ is finite if $H$ and $\sigma$ are 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 type are called similar.

Let $\mathcal{G},\mathcal{H}$ be similar multi-sorted structures with signature $\sigma$. A homomorphism $\varphi$ from $\mathcal{G}$ to $\mathcal{H}$ is a collection of mappings $\varphi_{i}:G_{i}\to H_{i}$, $i\in[k]$, from $G$ to $H$ such that for any $\mathcal{R}\in\sigma$ with type $(i_{1},\dots,i_{\ell_{\mathcal{R}}})$, if $\mathcal{R}^{\mathcal{G}}(a_{1},\dots,a_{\ell_{\mathcal{R}}})$ is true for $(a_{1},\dots,a_{r})\in G_{i_{1}}\times...\times G_{i_{\ell_{\mathcal{R}}}}$, then $\mathcal{R}^{\mathcal{H}}(\varphi_{i_{1}}(a_{1}),\dots,\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})$. For a multi-sorted structure $\mathcal{H}$, the corresponding counting CSP, $\#_{p}\mathsf{CSP}(\mathcal{H})$, is the problem of computing $\mathsf{hom}(\mathcal{G},\mathcal{H})$ for a given structure $\mathcal{G}$. 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})$.

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}),\dots,(a_{k},b_{k}))=1$ if and only if $\mathcal{R}^{\mathcal{H}}(a_{1},\dots,a_{k})=1$ and $\mathcal{R}^{\mathcal{G}}(b_{1},\dots,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}$.

Let $\mathcal{H}=(\{H_{i}\}_{{i\in[k]}};\mathcal{R}_{1},\dots,\mathcal{R}_{m})$ be a multi-sorted relational structure and $\pi$ an automorphism of $\mathcal{H}$. For $\mathcal{Q}\subseteq H_{i_{1}}\times\dots\times H_{i_{\ell}}$, we use $\pi(\mathcal{Q})$ to denote the set $\{\pi(\mathbf{a})\mid\mathbf{a}\in\mathcal{Q}\}$, where $\pi(\mathbf{a})=(\pi_{i_{1}}(\mathbf{a}[1]),\dots,\pi_{i_{\ell}}(\mathbf{a}[\ell])$. For a prime number $p$ we say that $\pi$ has order $p$ if $\pi$ is not the identity in $\mathsf{Aut}(\mathcal{H})$ and has order $p$ in $\mathsf{Aut}(\mathcal{H})$. In other words, each of the $\pi_{j}$’s is either the identity mapping or has order $p$, and at least one of the $\pi_{j}$’s is not the identity mapping. Structure $\mathcal{H}$ is said to be $p$-rigid if it has no automorphism of order $p$. Similar to regular relational structures we can introduce reductions of multi-sorted structures by their automorphisms of order $p$.

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},\dots,\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},\dots,i_{\ell})$ is the type of $\mathcal{R}_{j}$. By $\mathsf{Fix}(\pi)$ we denote the collection $\{\mathsf{Fix}(\pi_{i})\}_{j\in[k]}$ of sets of fixed points of the $\pi_{i}$’s. Let $\mathcal{H}^{\pi}$ denote the substructure of $\mathcal{H}$ induced by $\mathsf{Fix}(\pi)$. We write $\mathcal{H}\rightarrow_{p}\mathcal{H}^{\prime}$ if there is $\pi\in\mathsf{Aut}(\mathcal{H})$ of order $p$ such that $\mathcal{H}^{\prime}$ is isomorphic to $\mathcal{H}^{\pi}$. We also write $\mathcal{H}\rightarrow^{*}_{p}\mathcal{H}^{\prime}$ if there are structures $\mathcal{H}_{1},\dots,\mathcal{H}_{t}$ such that $\mathcal{H}$ is isomorphic to $\mathcal{H}_{1}$, $\mathcal{H}^{\prime}$ is isomorphic to $\mathcal{H}_{t}$, and $\mathcal{H}_{1}\rightarrow_{p}\mathcal{H}_{2}\rightarrow_{p}\dots\rightarrow_{p}\mathcal{H}_{t}$. Let also $\mathcal{H}^{*p}$ be a $p$-rigid structure such that $\mathcal{H}\rightarrow^{*}_{p}\mathcal{H}^{*p}$.

The proof of Proposition 2.1 follows the same lines as the analogous statement in the single-sorted case, and is moved to Appendix A.

The following statements are well-known for single-sorted structures, see [20, 12].

The following statement is a straightforward implication of Lemma 2.2.

We complete this section with a definition of polymorphisms. Let $\mathcal{R}\subseteq H^{n}$ be a relation over a set $H$. A $k$-ary polymorphism of $\mathcal{R}$ is a mapping $f:H^{k}\to H$ such that for any choice of $\mathbf{a}_{1},\dots,\mathbf{a}_{k}\in\mathcal{R}$, it holds that $f(\mathbf{a}_{1},\dots,\mathbf{a}_{k})\in\mathcal{R}$ (computed component-wise). The mapping $f$ is a polymorphism of a (single-sorted) relational structure $\mathcal{H}=(H,\mathcal{R}_{1},\dots,\mathcal{R}_{m})$ if it is a polymorphism of each relation $\mathcal{R}_{1},\dots,\mathcal{R}_{m}$. In the multi-sorted case the definitions are a bit more complicated. Let $\mathcal{R}\subseteq H_{1}\times\dots\times H_{n}$ be a multi-sorted relation. Instead of a single mapping we consider a family of mappings $f=\{f_{i}\}_{i\in[n]}$, $f_{i}:H^{k}_{i}\to H_{i}$. The family $f$ is said to be a polymorphism of $\mathcal{R}$ if it satisfies the same condition: for any choice of $\mathbf{a}_{1},\dots,\mathbf{a}_{k}\in\mathcal{R}$, it holds that $f(\mathbf{a}_{1},\dots,\mathbf{a}_{k})\in\mathcal{R}$, only in this case the mapping $f_{i}$ is applied in the $i$th coordinate position, $i\in[n]$. A polymorphism of a multi-sorted structure $\mathcal{H}=(\{H_{i}\}_{i\in[q]};\mathcal{Q}_{1},\dots,\mathcal{Q}_{m})$ is again a family $f=\{f_{i}\}_{i\in q}:H^{k}_{i}\to H_{i}$ such that for each $j\in[m]$, $f$ (or rather its appropriate subfamily) is a polymorphism of $\mathcal{Q}_{j}$. For a complete introduction into polymorphisms the reader is referred to [2].

The following special type of polymorphisms often occurs in the study of counting CSPs. For a set $H$ a mapping $\varphi:H^{3}\rightarrow H$ is said to be a Mal’tsev operation if for any $a,b\in H$ it satisfies the conditions $f(a,a,b)=f(b,a,a)=b$. In the multi-sorted case a family $f=\{f_{i}\}_{i\in[n]}$ is Mal’tsev, if every $f_{i}$ is Mal’tsev. A Mal’tsev operation (or a family of operations) that is a polymorphism of a relation $\mathcal{R}$ or a relational structure $\mathcal{H}$ is said to be a Mal’tsev polymorphism of $\mathcal{R}$ or $\mathcal{H}$. One of the useful properties of Mal’tsev polymorphisms is that it enforces the rectangularity of relations. A binary relation $\mathcal{R}\subseteq H^{2}$ is rectangular if whenever $((a,c),(a,d),(b,c)\in\mathcal{R}$ it also holds that $(b,d)\in\mathcal{R}$. If $\mathcal{R}$ has a Mal’tsev polymorphism $f$, it is rectangular. Indeed,

See Section 6 for further details.

In the Introduction, we defined the CSP as the problem of deciding the existence of a homomorphism between two relational structures. From a technical perspective, however, a more traditional approach is often more useful.

Let $H$ be a (finite) set and $\Gamma$ a set of relations on $H$. Such a set of relations is called a constraint language, and the set $H$ is often referred to as the domain.

The Constraint Satisfaction Problem $\mathsf{CSP}(\Gamma)$ is the combinatorial problem with:
Instance: a pair $\mathcal{P}=(V,\mathcal{C})$ where $V$ is a finite set of variables and $\mathcal{C}$ is a finite set of constraints. Each constraint $C\in\mathcal{C}$ is a pair $\langle\mathbf{s},\mathcal{R}\rangle$ where

• •

  $\mathbf{s}=(v_{1},v_{2},...,v_{m})$ is a tuple of variables from $V$ of length $m$, called the constraint scope;

• •

  $\mathcal{R}\in\Gamma$ is an $m$-ary relation, called the constraint relation.

Objective: Decide whether there is a solution of $\mathcal{P}$, that is, a mapping $\varphi:V\to H$ such that for each constraint $\langle\mathbf{s},\mathcal{R}\rangle\in\mathcal{C}$ with $\mathbf{s}=(v_{1},\dots,v_{m})$ the tuple $(\varphi(v_{1}),\dots,\varphi(v_{m}))$ belongs to $\mathcal{R}$.

In the (modular) counting version of $\mathsf{CSP}(\Gamma)$ denoted $\mathsf{\#CSP}(\Gamma)$ ($\#_{p}\mathsf{CSP}(\Gamma)$) the objective is to find the number of solutions of instance $\mathcal{P}$ (modulo $p$). We will refer to this definition as the standard definition of the CSP.

To relate this definition to the homomorphism definition of the CSP, note that for a $\sigma$-structure $\mathcal{H}$ the collection of interpretations $\mathcal{R}^{\mathcal{H}}$, $\mathcal{R}\in\sigma$, is just a set of relations, that is a constraint language over $H$. Thus, for every relational structure $\mathcal{H}$ there is an associated constraint language $\Gamma_{\mathcal{H}}$. Conversely, every (finite) constraint language $\Gamma$ can be converted into a relational structure $\mathcal{H}_{\Gamma}$ such that $\Gamma_{\mathcal{H}_{\Gamma}}=\Gamma$ in a straightforward way, although in this case there is much room for the choice of a signature.

It is well known, see e.g. [21] and [2] that the problems $\mathsf{CSP}(\mathcal{H})$ and $\mathsf{CSP}(\Gamma_{\mathcal{H}})$ can be easily translated into each other. The same is true for $\mathsf{\#CSP}(\mathcal{H})$ and $\mathsf{\#CSP}(\Gamma_{\mathcal{H}})$. The conversion procedure goes as follows. Let $\mathcal{G}$ be an instance of $\mathsf{CSP}(\mathcal{H})$ and $\sigma$ is the signature of $\mathcal{H}$. Create an instance $\mathcal{P}=(V,\mathcal{C})$ of $\mathsf{CSP}(\Gamma_{\mathcal{H}})$ by setting $V=G$, the base set of $\mathcal{G}$, and for every $\mathcal{R}\in\sigma$ and every $\mathbf{s}\in\mathcal{R}^{\mathcal{G}}$, include the constraint $\langle\mathbf{s},\mathcal{R}^{\mathcal{H}}\rangle$ into $\mathcal{C}$. The transformation of instances of $\mathsf{CSP}(\Gamma)$ to an instance of $\mathsf{CSP}(\mathcal{H}_{\Gamma})$ is the reverse of the procedure above. This transformation is clearly extended to counting CSPs, as well. In this paper we often use the standard definition of the CSP inside proofs assuming that an instance of $\#_{p}\mathsf{CSP}(\mathcal{H})$ or $\oplus\mathsf{CSP}(\mathcal{H})$ is given by variables and constraints.

The definition above can easily be extended to multi-sorted relational structures and languages. If $\mathcal{H}$ is a multi-sorted relational structure, $\mathsf{CSP}(\mathcal{H})$ ($\#\mathsf{CSP}(\mathcal{H})$) asks, given a similar structure $\mathcal{G}$, whether there exists a homomorphism of multi-sorted structure $\mathcal{G}$ to $\mathcal{H}$ (asks to find the number of such homomorphisms). If $\Gamma$ is a set of multi-sorted relations, every variable $v\in V$ for an instance $(V,\mathcal{C})$ of $\mathsf{CSP}(\Gamma)$ is assigned a type $\tau(v)$ and for every constraint $\langle(v_{1},\dots,v_{k}),\mathcal{R}\rangle$, the sequence $(\tau(v_{1}),\dots,\tau(v_{k}))$ must match the type of $\mathcal{R}$.

One of the standard techniques when studying constraint problems is to identify ways to expand the target relational structure or constraint language with additional relations without changing the complexity of the problem.

Let $\mathcal{H}$ be a relational structure with signature $\sigma$ and $\mathcal{H}^{=}$ its expansion by adding a binary relational symbol $=$ interpreted as $=_{H}$, the equality relation on $H$. The following reduction is straightforward.

A constant relation over a set $H$ is a unary relation $C_{a}=\{a\}$, $a\in H$. For a relational structure $\mathcal{H}$ by $\mathcal{H}^{\mathsf{c}}$ we denote the expansion of $\mathcal{H}$ by all the constant relations $C_{a}$, $a\in H$. Theorem 2.5 was proved for exact counting in [8], for modular counting of graph homomorphisms in [20, 24, 25], and for general modular counting CSP in [12].

Lemma 2.4 and Theorem 2.5 can be generalized to the multi-sorted case. Let $\mathcal{H}=\{\mathcal{H}_{i}\}_{i\in[k]}$ 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_{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_{a}$, $a\in H_{i},i\in[k]$.

Yet another way to expand a relational structure is by primitive positive definable (pp-definable for short) relations. Primitive-positive definitions have played a major role in the study of the CSP. It has been proved in multiple circumstances that expanding a structure with pp-definable relations does not change the complexity of the corresponding CSP. This has been proved for the decision CSP in [31, 11] and the exact Counting CSP [8]. The reader is referred to [2] for details about pp-definitions and their use in the study of the CSP.

Conjunctive definitions are a special case of primitive positive definitions that do not use quantifiers. Let $\mathcal{H}$ be a structure with signature $\sigma$. A conjunctive formula $\Phi$ over variables $\{x_{1},\dots,x_{k}\}$ is a conjunction of atomic formulas of the form $\mathcal{R}(y_{1},\dots,y_{\ell})$, where $\mathcal{R}\in\sigma$ is an ($\ell$-ary) symbol and $y_{1},\dots,y_{\ell}\in\{x_{1},\dots,x_{k}\}$. A $k$-ary predicate $\mathcal{Q}$ is conjunctive definable in $\mathcal{H}$ if $(a_{1},\dots,a_{k})\in\mathcal{Q}$ if and only if $\Phi(a_{1},\dots,a_{k})$ is true.

We now extend the concept of primitive-positive definability to the multi-sorted case. Let $\mathcal{H}$ be a multi-sorted relational structure with the base set $H$. As before primitive positive (pp-) formula in $\mathcal{H}$ is a first-order formula $\exists y_{1},\dots,y_{s}\Phi(x_{1},\dots,x_{k},y_{1},\dots,y_{s}),$ where $\Phi$ is a conjunction of atomic formulas of the form $z_{1}=_{H}z_{2}$ or $\mathcal{R}(z_{1},\dots,z_{\ell})$, $z_{1},\dots,z_{\ell}\in\{x_{1},\dots,x_{k},y_{1},\dots,y_{s}\}$, and $\mathcal{R}$ is a predicate of $\mathcal{H}$. However, every variable in $\Phi$ is now 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},\dots,z_{\ell})$ the sequence $(\tau(z_{1}),\dots,\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

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

While when $\mathcal{H}$ is a graph it is possible to prove a statement similar to Lemma 2.7 for pp-definable relations [12], we will later see that it is unlikely to be true for general relational structures.

Finally, for a relational structure $\mathcal{H}$ (single- or multi-sorted) $\langle\mathcal{H}\rangle$ denotes the relational clone of $\mathcal{H}$, that is, the set of all relations pp-definable in $\mathcal{H}$

$p$-rigidity. The classification result in Theorem 1.2 asserts that $\#_{p}\mathsf{Hom}(H)$ for a $p$-rigid graph $H$ is hard whenever the exact counting problem is hard. In Example 5.1 we show that this is no longer the case for general relational structures. Let $p$ be a prime number and $T_{p}=\{0,\dots,p-1,p,p+1\}$. A relational structure $\mathcal{T}_{p}$ has the base set $T_{p}$ and predicates $\mathcal{R},C_{0},\dots,C_{p+1}$, where $C_{a}$ is the constant relation $\{(a)\}$ and $\mathcal{R}=T^{2}_{p}-\{(0,p),\dots,(p-1,p)\}$. The structure $\mathcal{T}_{p}$ is $p$-rigid as it contains all the constant relations and every automorphism must preserve them, implying that every element of $T_{p}$ is a fixed point. By [6, 40] the decision $\mathsf{CSP}(\mathcal{T}_{p})$ is solvable in polynomial time, while the exact counting problem $\#\mathsf{CSP}(\mathcal{T}_{p})$ is $\#$P-complete by [8], as it does not have a Mal’tsev polymorphism and $\mathcal{R}$ is not rectangular (see below). However, if $\mathcal{G}$ is a structure similar to $\mathcal{T}_{p}$ and there is a homomorphism $\varphi:\mathcal{G}\to\mathcal{T}_{p}$ such that some vertex $v$ of $\mathcal{G}$ is mapped to $a\in\{0,\dots,p-1\}$ then, unless $v$ is bound by $C_{a}$, the mapping that differs from $\varphi$ only at $v$ by sending it to any $b\in\{0,\dots,p-1\}$ is also a homomorphism. Since $|\{0,\dots,p-1\}|=p$, this means that the elements $0,\dots,p-1$ can be effectively eliminated from $\mathcal{T}_{p}$, and the resulting structure is somewhat trivial. Therefore $\#_{p}\mathsf{CSP}(\mathcal{T}_{p})$ can be solved in polynomial time.

Automorphisms of direct products. Another crucial component of Theorem 1.2 is the structure of automorphisms of direct products of graphs [29]. It essentially asserts that every automorphism of a direct product $H_{1}\times\dots\times H_{n}$ can be thought of as a composition of a permutation of factors in the product and automorphisms of those factors. In Example 8.2 we show that this breaks down already for digraphs. Indeed, let $\mathcal{H}=(V,E)$ be a directed graph where $V=\{a,b,c,d\}$ with (directed) edge set $E=\{(b,a),(b,c),(c,d)\}$. This digraph is rigid. However, the automorphism group of $\mathcal{H}^{2}$, see Figure 1, has a complicated structure. As is easily seen $\mathcal{H}^{2}$ has a large number of automorphisms of order 2 and 3, not all of which have a simple representation mentioned above.

In [12] one of the important applications of the structural theorem for automorphisms of graph products is that it allows one to prove that $\#_{p}\mathsf{Hom}(\mathcal{H}+\mathcal{R}))$, where $\mathcal{H}+\mathcal{R}$ denotes the expansion of $\mathcal{H}$ by a relation $\mathcal{R}$ pp-definable in $\mathcal{H}$, is polynomial time reducible to $\#_{p}\mathsf{Hom}(\mathcal{H})$ (see below). The example above indicates that this result may no longer be true for general relational structures.

Rectangularity, permutability, and Mal’tsev polymorphisms. The key properties of relational structures heavily exploited in [5, 17, 13] to obtain characterizations of the complexity of exact counting are rectangularity, balancedness, and the presence of a Mal’tsev polymorphism.

Recall that a binary relation $\mathcal{R}\subseteq H_{1}\times H_{2}$ is said to be rectangular if $(a,c),(a,d),(b,c)\in\mathcal{R}$ implies $(b,d)\in\mathcal{R}$ for any $a,b\in A_{1},c,d\in A_{2}$. A relation $\mathcal{R}\subseteq H^{n}$ for $n\geq 2$ is rectangular if for every $I\subsetneq[n]$, the relation $R$ is rectangular when viewed as a binary relation, a subset of $\mathsf{pr}_{I}\mathcal{R}\times\mathsf{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.

An $n$-by-$m$ matrix $M$ is said to be a rank-1 block matrix if by permuting rows and columns it can be transformed to a block-diagonal matrix (not necessarily square), where every nonzero diagonal block with has rank at most 1.

Finally, let $\mathcal{R}(x,y,z)$ be a ternary relation,a subset of $H_{1}\times H_{2}\times H_{3}$. We call $\mathcal{R}$ balanced if the matrix $\mathsf{M}_{\mathcal{R}}\in\mathbb{Z}^{|H_{1}|\times|H_{2}|}$, where $\mathsf{M}_{\mathcal{R}}[x,y]=|\{z\in H_{3}:(x,y,z)\in\mathcal{R}\}|$ such that $x\in H_{1}$ and $y\in H_{2}$ is a rank-1 block matrix. A relation $\mathcal{R}$ of arity $n>3$ is balanced if every representation of $\mathcal{R}$ as a ternary relation, a subset of $H^{k}\times H^{\ell}\times H^{n-k-\ell}$, is balanced. A relational structure $\mathcal{H}$ is called strongly balanced if every relation $\mathcal{R}\in\langle\mathcal{H}\rangle$ is balanced.

These three concepts are closely related and proved to be very useful for exact counting. It is well known [28] that strong rectangularity of a relation structure is equivalent to it having a Mal’tsev polymorphism. It is also straightforward that every balanced relation is rectangular. According to [17] $\#\mathsf{CSP}(\mathcal{H})$ is polynomial time solvable if and only if $\mathcal{H}$ is strongly balanced. However, in order for the solution algorithm to work, it requires a Mal’tsev polymorphism to be applied over and over again to construct a frame, that is, a compact representation of the set of solutions, [5, 17]. As was observed above, pp-definitions do not quite work in the case of modular counting, and we introduce their modular counterparts by introducing modular quantifier (see below). Using modular pp-definitions, we can change the definitions of rectangularity and balancedness accordingly to obtain the properties of strong $p$-rectangularity and $p$-balancedness. These new properties require that every modular-pp-definable relation is rectangular and balanced. Modular-pp-definitions preserve the complexity of modular problems, however, they destroy the connections between the concepts above. In Section 6 we present a series of counterexamples showing that almost all the properties of $p$-rectangularity, $p$-permutability, $p$-balancedness, and having a Mal’tsev polymorphism are independent of each other. While as we prove the first three properties are necessary for the tractability of the problem, the latter one does not follow from them, and therefore neither of $p$-rectangularity, $p$-permutability, $p$-balancedness help to construct a solution algorithm in the same fashion it is done for exact counting.

In the category of positive results we propose several ways to overcome the difficulties outlined in Section 3.1. We hope that these new approaches will lead to a complexity classification of modular counting.

Multi-sorted structures and $p$-rigidity. We start with applying a well-known framework of multi-sorted relational structures to modular counting. While multi-sorted structures is a standard tool in the study of decision CSPs, it usually only used to simplify arguments and streamline algorithms. Here we use this framework in a more fundamental way, to strengthen the main (hypothetical) tractability condition.

Let us consider again the structure $\mathcal{T}_{p}$ introduced in the beginning of Section 3.1 and discover that when considered as a multi-sorted structure $\mathcal{T}_{p}$ is not $p$-rigid, and therefore can be transformed so that the corresponding modular CSP is solvable in polynomial time. The idea is, given an instance $\mathcal{G}$ of $\#_{p}\mathsf{Hom}(\mathcal{T}_{p})$, to use some preprocessing algorithm (such as local propagation or a solution algorithm for the decision CSP) to reduce possible range of vertices from $\mathcal{G}$ under homomorphisms. We then refine the instance by replacing $\mathcal{T}_{p}$ with a multi-sorted structure in such a way that every possible range of a vertex from $\mathcal{G}$ becomes a set of a distinct type. Now, since automorphisms of a multi-sorted structure may act differently on different types, the refined structure may have a richer automorphism group. For instance, for the refinement of $\mathcal{T}_{p}$ the sets $T_{p}$ and $\{0\}$ have different types, and an automorphism of such a structure may act differently on these sets and no longer has to have $0$ as a fixed point when acting on $T_{p}$.

We identify several ways how a refinement of a structure or an instance can be constructed and prove that these constructions are parsimonious reductions between modular CSPs. We are not aware of any example of a refined $p$-rigid structure whose complexity differs from that for exact counting.

Modular existential quantifiers. We follow the approach of [12] by expanding the relational structure $\mathcal{H}$ by adding pp-definable relations, but doing in a manner friendly to modular counting.

We introduce a new form of expansion which is using $p$-modular quantifiers instead of regular existential quantifiers. The semantics of a $p$-modular quantifier is ”there are non-zero modulo $p$ values of a variable” rather than ”there exists at least one value of a variable” as the regular existential quantifier asserts. The new concept gives rise to new definitions of pp-formulas. If regular existential quantifiers in pp-formulas are replaced with $p$-modular quantifiers, we obtain $p$-modular primitive positive formulas ($p$-mpp-formulas, for short). The $p$-modular quantifier is denoted $\exists^{\equiv p}$, and so $p$-mpp-formulas have the form

Note the more complicated form of the quantifier prefix: modular quantification is not as robust as the regular one and quantifying variables away in groups or one-by-one may change the result. For example, let $\mathcal{R}=\{(1,0,0),(1,1,0),(1,1,1),(2,2,2)\}$ be a relation on $\{0,1,2\}$. Then formulas $\exists^{\equiv 3}y\exists^{\equiv 3}z\ \ \mathcal{R}(x,y,z)$ and $\exists^{\equiv 3}y,z\ \ \mathcal{R}(x,y,z)$ define sets $\{1,2\}$ and $\{2\}$, respectively.

Every relational structure is associated with a relational clone $\langle\mathcal{H}\rangle$ that consists of all relations pp-definable in $\mathcal{H}$. Then, similar to pp-definitions, a relation $\mathcal{R}$ is said to be $p$-mpp-definable in a structure $\mathcal{H}$ if there is a $p$-mpp-formula in $\mathcal{H}$ expressing $\mathcal{R}$. The $p$-modular clone $\langle\mathcal{H}\rangle_{p}$ associated with $\mathcal{H}$ is the set of all relations $p$-mpp-definable in $\mathcal{H}$. Similar to the result of Bulatov and Dalmau [8], expanding a structure by a $p$-mpp-definable relation does not change the complexity of the problem $\#_{p}\mathsf{CSP}(\mathcal{H})$.