Introduction
In a constraint satisfaction problem (CSP), variables take values in a fixed domain, and constraints specify which combinations of values are allowed. The task is to find an assignment that satisfies every constraint. Even when such an assignment is promised to exist, finding one can be computationally hard. This motivates studying approximation of satisfiable CSPs, where we relax the requirement either quantitatively or qualitatively . In quantitative approximation, we seek an assignment satisfying as many of the original constraints as possible. In qualitative approximation, we weaken the constraints and seek an assignment satisfying every weakened constraint. We illustrate this distinction with two examples of well-known NP-hard CSPs.
Given a graph promised to be 3-colourable, a quantitative approximation seeks an assignment of three colours that gives different colours to the endpoints of as many edges as possible. A randomised polynomial-time algorithm by Goemans and Williamson [27 ] based on semidefinite programming finds a 3-colouring that properly colours at least a 0.836 fraction of the edges in expectation. A qualitative approximation instead allows more colours—say, 100—while still requiring the endpoints of every edge to receive different colours. This problem was recently shown to be NP-hard [DMR09, GS20, FMW26].
In (monotone) 1-in-3-SAT, each clause requires exactly one of its three literals to be true. Given a satisfiable instance, quantitative approximation seeks an assignment satisfying as many clauses as possible. A qualitative approximation can instead weaken the requirement to Not-All-Equal : every clause must contain both a true and a false literal. This relaxation is solvable in polynomial time, as shown by Brakensiek and Guruswami [7 ] . Many other qualitative approximations of 1-in-3-SAT have been studied, with tractability of some and NP-hardness of others [4 , 19 , 29 ] . These qualitative approximation tasks are examples of Promise Constraint Satisfaction Problems (PCSPs) [2 , 7 BBKO21] . The contrasting complexity of these relaxations motivates studying which relations are promise-useful [3 ] : which relations admit a nontrivial relaxation such that the associated PCSP is tractable? Once a relation is known to be promise-useful, one can study which of its nontrivial relaxations yield tractable PCSPs.
In their series of works, Bhangale, Khot, and Minzer [16 , 17 , 14 , 15 , 18 ] , and Bhangale, Khot, Liu, and Minzer [11 ] identified Abelian embeddings as an important structural feature for the quantitative approximation of satisfiable CSPs. Informally, such an embedding captures additive structure within a constraint relation. Bhangale et al. use this structure in a hybrid approximation algorithm combining the solution of equations over Abelian groups with semidefinite programming [18 ] .
Definition 1.1. Suppose R ⊆ A r R \subseteq A^r R ⊆ A r is an r r r -ary relation with A = dom ( R ) A = \operatorname{dom}(R) A = dom ( R ) and G G G is an Abelian group. We say that R R R admits an Abelian embedding to G G G if there exist functions f 1 , … , f r : A → G f_1,\ldots,f_r:A\to G f 1 , … , f r : A → G such that (i) at least one of f 1 , … , f r f_1,\ldots,f_r f 1 , … , f r is nonconstant, and (ii) for all ( x 1 , … , x r ) ∈ R (x_1,\ldots,x_r)\in R ( x 1 , … , x r ) ∈ R we have ∑ i f i ( x i ) = 0 \sum_i f_i(x_i)=0 ∑ i f i ( x i ) = 0 . We say simply that R R R admits an Abelian embedding if it admits one to some Abelian group.
In this paper, we develop an approach to qualitative approximation based on Abelian embeddings and establish a sharp complexity dichotomy for approximating detrivialised equations over prime-order groups, a family of PCSPs whose promise relations admit such embeddings. In particular, we show that suitable Abelian embeddings are a structural source of promise-usefulness.
This algorithmic role of Abelian embeddings is complemented by recent hardness results based on connectivity properties of the promise relation. Extending work of Braverman, Khot, Lifshitz, and Minzer [12 ] , Banakh, Barsukov, and Nakajima [6 ] show that, assuming the Rich 2-to-1 conjecture [13 ] , every (nontrivial) qualitative approximation of a symmetric reconfigurable relation is NP-hard. Here symmetry means closure under permutations of coordinates, while reconfigurability is defined as follows.
Definition 1.2. A relation R R R is reconfigurable if the graph whose vertices are tuples of R R R , and where edges are drawn between tuples which differ in exactly one coordinate, is connected.
For symmetric relations, Abelian embeddability imposes a separation between tuples that cannot be overcome by local changes, while reconfigurability requires local changes to connect all tuples. Indeed, the two regimes are disjoint: if adjacent tuples differ in coordinate i i i , then any Abelian embedding must assign the same value under f i f_i f i to the two entries in that coordinate. Connectivity and symmetry therefore force every f i f_i f i to be constant, so a reconfigurable relation admits no Abelian embedding. In fact, each detrivialised equations relation defined below has an edgeless reconfiguration graph. Our hardness results therefore concern promise relations at the opposite structural extreme from the reconfigurable relations covered by the framework of Banakh, Barsukov, and Nakajima [6 ] .
Concurrent work of Chan and Ng [20 ] also highlights the algorithmic role of Abelian embeddings, showing that an algorithm combining SDP and constraint singleton AIP subsumes the hybrid algorithm of Bhangale, Khot, and Minzer [18 ] . Our tractability results give a complementary perspective for qualitative approximation (PCSPs).
Contributions. Our first contribution is a general reduction that uses suitable Abelian embeddings and roundings to strengthen the promise relation of a PCSP. The reduction applies to both decision and search, yielding a new source of tractability for qualitative approximation.
Our second contribution is a sharp complexity dichotomy for approximating detrivialised equations over prime-order groups.
Definition 1.3. Let G G G be a finitely generated Abelian group. We define the ternary equations relation Eqn ( G ) = { ( x , y , z ) ∈ G 3 ∣ x + y + z = 0 } \operatorname{Eqn}(G) = \{(x,y,z) \in G^3 \mid x+y+z=0\} Eqn ( G ) = {( x , y , z ) ∈ G 3 ∣ x + y + z = 0 } . Its detrivialised equations relation is Eqn ∗ ( G ) = { ( x , y , z ) ∈ Eqn ( G ) ∣ x , y , z are not all equal } \operatorname{Eqn}^{*}(G) = \{(x,y,z) \in\operatorname{Eqn}(G) \mid x,y,z\text{ are not all equal}\} Eqn ∗ ( G ) = {( x , y , z ) ∈ Eqn ( G ) ∣ x , y , z are not all equal } .
If a ternary relation R R R contains a constant tuple ( a , a , a ) (a,a,a) ( a , a , a ) , then every instance of CSP ( R ) \operatorname{CSP}(R) CSP ( R ) is satisfied by assigning a a a to every variable. Detrivialisation removes precisely these tuples: Eqn ∗ ( G ) \operatorname{Eqn}^{*}(G) Eqn ∗ ( G ) is the largest subrelation of Eqn ( G ) \operatorname{Eqn}(G) Eqn ( G ) containing no constant tuple. When G G G has no 3 3 3 -torsion, as for Z p \mathbb{Z}_p Z p with p ≠ 3 p \ne3 p = 3 , this amounts to deleting only ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) . For nontrivial G G G , the identity map witnesses an Abelian embedding of Eqn ∗ ( G ) \operatorname{Eqn}^{*}(G) Eqn ∗ ( G ) into G G G .
Although systems of equations over Z p \mathbb{Z}_p Z p can be solved in polynomial time, CSP ( Eqn ∗ ( Z p ) ) \operatorname{CSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_p)) CSP ( Eqn ∗ ( Z p )) , i.e. finding a solution to a system of homogeneous linear equations mod p p p where no particular equation is assigned a constant tuple, is NP-hard.2
We therefore study a qualitative relaxation of this problem: given a system promised to have a solution over G G G that is nonconstant on every equation, find a c c c -colouring of its variables that makes every equation nonmonochromatic. This retains the nonconstancy requirement while discarding the equations themselves, leaving a colouring problem on the underlying hypergraph of constraints. We write NAE c \operatorname{NAE}_c NAE c for the ternary not-all-equal relation on c c c colours. For fixed c c c , this is the largest target relation containing no constant tuple, and hence gives the weakest relaxation excluding constant solutions.3 For detrivialised equations over prime-order groups, the resulting problem is defined as follows.
Definition 1.4. Let p p p be a prime and c ≥ 2 c \ge2 c ≥ 2 . An instance of PCSP ( Eqn ∗ ( Z p ) , NAE c ) \operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_c) PCSP ( Eqn ∗ ( Z p ) , NAE c ) is given by a system of linear equations of the form x + y + z ≡ 0 ( m o d p ) x+y+z \equiv0 \pmod p x + y + z ≡ 0 ( mod p ) . The goal is to output Yes if there exists a solution to this system over Z p \mathbb{Z}_p Z p which is nonconstant on every equation, and No if there is not even a solution over NAE c \operatorname{NAE}_c NAE c , i.e., a colouring of the variables with c c c colours which renders each equation nonconstant.
For p = 2 p=2 p = 2 and c = 2 c=2 c = 2 , PCSP ( Eqn ∗ ( Z p ) , NAE c ) \operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_c) PCSP ( Eqn ∗ ( Z p ) , NAE c ) is (isomorphic via Boolean complementation to) the 1-in-3 vs. NAE-3-SAT problem, shown tractable by Brakensiek and Guruswami [7 ] . For p = 3 p=3 p = 3 , PCSP ( Eqn ∗ ( Z p ) , NAE c ) \operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_c) PCSP ( Eqn ∗ ( Z p ) , NAE c ) corresponds to the 3-rainbow vs. c c c -normal hypergraph colouring problem, studied by McDiarmid [30 ] , who gave a randomised algorithm. A deterministic algorithm for p ∈ { 2 , 3 } p \in\{2,3\} p ∈ { 2 , 3 } and all c ≥ 2 c \ge2 c ≥ 2 follows from the tractability of the problem for p = c = 2 p=c=2 p = c = 2 via homomorphic relaxation [BBKO21, Definition 4.6].
For p ≥ 5 p \ge5 p ≥ 5 however, the story is more complicated, as the following theorem shows. Note that for p ≥ 5 p \ge5 p ≥ 5 the problem is well-defined for c ≥ 3 c \ge3 c ≥ 3 ; when c = 2 c=2 c = 2 , some instances satisfy both the Yes and No conditions.
Theorem 1.5. Fix a prime p ≥ 5 p \ge5 p ≥ 5 . PCSP ( Eqn ∗ ( Z p ) , NAE c ) \operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_c) PCSP ( Eqn ∗ ( Z p ) , NAE c ) is (i) solvable in polynomial time if c ≥ 4 c \ge4 c ≥ 4 , (ii) NP-hard if c = 3 c=3 c = 3 .
In fact we prove a stronger theorem.
Theorem 1.6. Fix a nontrivial finite Abelian group G G G without elements of order 2 or 3. Then PCSP ( Eqn ∗ ( G ) , NAE c ) \operatorname{PCSP}(\operatorname{Eqn}^{*}(G),\operatorname{NAE}_c) PCSP ( Eqn ∗ ( G ) , NAE c ) is (i) solvable in polynomial time if c ≥ 4 c \ge4 c ≥ 4 , (ii) NP-hard if c = 3 c=3 c = 3 (provided the problem is well-defined).
The algorithm that solves this problem is a singleton algorithm [35 ] , and its correctness relies on the fact that Eqn ∗ ( G ) \operatorname{Eqn}^{*}(G) Eqn ∗ ( G ) has an Abelian embedding to G G G . In fact, the algorithm generalises easily to one which works for all templates PCSP ( R , NAE c ) \operatorname{PCSP}(R,\operatorname{NAE}_{c}) PCSP ( R , NAE c ) , where R R R has an Abelian embedding to a group with a “c c c -rounding”. We present this more general algorithm along with the notion of c c c -rounding in § 3 , and show that the tractability part of the theorem above is a simple consequence. However, neither k k k -consistency (for any fixed k k k ) nor the combined Basic Linear Programming and Affine Integer Programming (BLP+AIP) relaxation [BGWZ20] solves this problem (Appendix § 7 .§ 1 ). Thus this is an example of a natural fragment of finite-domain PCSPs solvable by a singleton algorithm but not by either of the above methods.
Algorithmic results. We illustrate the algorithm by running it on a small instance of PCSP ( Eqn ∗ ( Z 5 ) , NAE 4 ) \operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_{5}),\operatorname{NAE}_{4}) PCSP ( Eqn ∗ ( Z 5 ) , NAE 4 ) . In fact, we will run it on the search version of the problem, denoted by Search-PCSP ( Eqn ∗ ( Z 5 ) , NAE 4 ) \operatorname{Search\text{-}PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_{5}),\operatorname{NAE}_{4}) Search - PCSP ( Eqn ∗ ( Z 5 ) , NAE 4 ) : Given an instance that is promised to admit a solution over Eqn ∗ ( Z 5 ) \operatorname{Eqn}^{*}(\mathbb{Z}_{5}) Eqn ∗ ( Z 5 ) , the goal is to find a solution over NAE 4 \operatorname{NAE}_{4} NAE 4 . Consider the instance with variable set { a , b , c , d , e , f , g , x , y , z , u } \{a,b,c,d,e,f,g,x,y,z,u\} { a , b , c , d , e , f , g , x , y , z , u } and the following eight equation constraints, where all equations are modulo 5:
C 1 : a + b + e = 0 , C 2 : a + c + d = 0 , C 3 : a + d + g = 0 , C 4 : a + e + f = 0 , C 5 : b + c + g = 0 , C 6 : b + d + f = 0 , C 7 : x + y + z = 0 , C 8 : a + x + u = 0. \begin{aligned}
C_{1}:&\ a+b+e=0, & C_{2}:&\ a+c+d=0, & C_{3}:&\ a+d+g=0, & C_{4}:&\ a+e+f=0,\\
C_{5}:&\ b+c+g=0, & C_{6}:&\ b+d+f=0, & C_{7}:&\ x+y+z=0, & C_{8}:&\ a+x+u=0.
\end{aligned} C 1 : C 5 : a + b + e = 0 , b + c + g = 0 , C 2 : C 6 : a + c + d = 0 , b + d + f = 0 , C 3 : C 7 : a + d + g = 0 , x + y + z = 0 , C 4 : C 8 : a + e + f = 0 , a + x + u = 0.
This is a valid instance: the assignment
a = 0 , b = 1 , c = 2 , d = 3 , e = 4 , f = 1 , g = 2 , x = 1 , y = 1 , z = 3 , u = 4 a=0,\quad b=1,\quad c=2,\quad d=3,\quad e=4,\quad f=1,\quad g=2,\quad x=1,\quad y=1,\quad z=3,\quad u=4 a = 0 , b = 1 , c = 2 , d = 3 , e = 4 , f = 1 , g = 2 , x = 1 , y = 1 , z = 3 , u = 4
satisfies every equation nontrivially. The algorithm is not given the displayed assignment; it only uses the promise that such an assignment exists. We will now explain how the algorithm works (illustrated in Figure 1 ).
Figure 1. An example run of the algorithm.
We start by picking some constraint, say C 1 C_{1} C 1 . We know there exists some solution to the system such that C 1 C_{1} C 1 does not get assigned the tuple ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) . We find such a solution as follows. We choose a variable in C 1 C_{1} C 1 , say a a a , and look (using Gaussian elimination) for a solution to the system with a a a fixed to 1 or some other nonzero value. In this case, no such solution exists, so we move on to another variable in C 1 C_{1} C 1 , say b b b , and look for a solution to the system with b b b fixed to 1. We find such a solution s 1 s_{1} s 1 , and fix the values of all variables that got a nonzero value. Next, we repeat the same process for the subinstance induced on the remaining variables. The final NAE 4 \operatorname{NAE}_{4} NAE 4 -solution γ \gamma γ assigns each variable the first nonzero value it receives in s 1 , s 2 , s 3 s_{1},s_{2},s_{3} s 1 , s 2 , s 3 . The end row of the lower table in Figure 1 lists the final tuple assigned to each constraint and shows that every constraint is nonmonochromatic. Informally, the reason this works is that, in the first step at which any variable in a constraint is coloured at all, it must be the case that 2 or 3 variables in that constraint are coloured, and indeed coloured with at least 2 different values. Hence, no matter what colour is assigned to the remaining variable (if it exists), the constraint is satisfied.
The algorithm as a reduction. Viewed more generally, the algorithm yields a polynomial-time reduction between the original PCSP and a PCSP obtained by restricting (and thus strengthening) its promise relation. The previous example is the special case in which the restricted promise relation is empty, and thus the target of the reduction is a trivial problem. The existence of this reduction contributes to the goal of the algebraic approach to PCSPs, which seeks to understand the complexity of all PCSPs through the algebraic characterisation of reductions between them [BBKQ21, BK22, DO24, BHZ27]. To this end, we show (Appendix § 7 .§ 2 ) that the reduction can be implemented using (Constraint) Singleton AIP (CSingl AIP). We then characterise CSingl AIP reductions algebraically, along the lines of Dalmau and Opršal [24 ] (Appendix § 7 .§ 3 ).
Additive combinatorics. Our (hardness) results use tools and ideas from additive combinatorics. Fix some prime p ≥ 5 p \ge5 p ≥ 5 . We call a partition of Z p \mathbb{Z}_{p} Z p into three sets A 1 , A 2 , A 3 A_{1},A_{2},A_{3} A 1 , A 2 , A 3 valid if the only solution to x + y + z ≡ 0 ( m o d p ) x+y+z\equiv0\pmod{p} x + y + z ≡ 0 ( mod p ) with x , y , z x,y,z x , y , z all in the same part is ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) . Validity is preserved by permuting the parts and by multiplying every element by the same nonzero scalar. A first step in the hardness proof is to classify these partitions: for every prime p ≥ 7 p \ge7 p ≥ 7 , there is exactly one up to these symmetries.
Theorem 1.7. For every prime p ≥ 7 p \ge7 p ≥ 7 , up to multiplication by a constant and permutation of parts, there exists exactly one valid partition of Z p \mathbb{Z}_p Z p , namely the partition that puts x x x into A 1 + ⌊ 3 x / p ⌋ A_{1+\lfloor3x/p\rfloor} A 1 + ⌊ 3 x / p ⌋ .
This fact follows from an application of the Cauchy–Davenport theorem, together with Vosper’s theorem. It does not hold for p = 5 p=5 p = 5 , as shown by the theorem below, which can be proved by a simple case analysis. The full proofs of both theorems are in Appendix § 8 .
Theorem 1.8. Up to multiplication by a constant and permutation of parts, there exist exactly two valid partitions of Z 5 \mathbb{Z}_5 Z 5 , namely { { 2 , 3 } , { 4 } , { 0 , 1 } } \{\{2,3\},\{4\},\{0,1\}\} {{ 2 , 3 } , { 4 } , { 0 , 1 }} and { { 2 , 3 } , { 1 , 4 } , { 0 } } \{\{2,3\},\{1,4\},\{0\}\} {{ 2 , 3 } , { 1 , 4 } , { 0 }} .
Preliminaries
We will only deal with PCSPs with a single relation. Therefore, we will specialise all of our notation and definitions for this case. Furthermore, we will leave the domains of relations implicit, for simplicity.4
For any relation R R R of arity r r r , let dom ( R ) \operatorname{dom}(R) dom ( R ) denote the set of values which appear in any tuple of R R R . For A ⊆ dom ( R ) A \subseteq\operatorname{dom}(R) A ⊆ dom ( R ) , write R ∣ A = R ∩ A r R|_A=R\cap A^r R ∣ A = R ∩ A r for the restriction of R R R to A A A , also called the subrelation induced by A A A . For two relations R , Q R,Q R , Q of arity r r r , define R × Q = { ( ( x 1 , y 1 ) , … , ( x r , y r ) ) ∣ ( x 1 , … , x r ) ∈ R , ( y 1 , … , y r ) ∈ Q } R\times Q=\{((x_1,y_1),\ldots,(x_r,y_r))\mid(x_1,\ldots,x_r)\in R,(y_1,\ldots,y_r)\in Q\} R × Q = {(( x 1 , y 1 ) , … , ( x r , y r )) ∣ ( x 1 , … , x r ) ∈ R , ( y 1 , … , y r ) ∈ Q } . Note that in general dom ( R × Q ) ⊆ dom ( R ) × dom ( Q ) \operatorname{dom}(R\times Q)\subseteq\operatorname{dom}(R)\times\operatorname{dom}(Q) dom ( R × Q ) ⊆ dom ( R ) × dom ( Q ) , but for symmetric R R R and Q Q Q this holds with equality. We define R n = R × ⋯ × R R^n=R\times\cdots\times R R n = R × ⋯ × R .
We write R → Q R\to Q R → Q if there exists h : dom ( R ) → dom ( Q ) h:\operatorname{dom}(R)\to\operatorname{dom}(Q) h : dom ( R ) → dom ( Q ) such that for any ( x 1 , … , x r ) ∈ R (x_1,\ldots,x_r)\in R ( x 1 , … , x r ) ∈ R we have ( h ( x 1 ) , … , h ( x r ) ) ∈ Q (h(x_1),\ldots,h(x_r))\in Q ( h ( x 1 ) , … , h ( x r )) ∈ Q . We call such a map a homomorphism . If R ⊆ Q R\subseteq Q R ⊆ Q then R → Q R\to Q R → Q . Let [ n ] = { 1 , … , n } [n]=\{1,\ldots,n\} [ n ] = { 1 , … , n } .
Let P P P and Q Q Q be two relations of the same arity such that P → Q P\to Q P → Q . An instance I = ( V ( I ) , C ( I ) ) I=(V(I),C(I)) I = ( V ( I ) , C ( I )) of PCSP ( P , Q ) \operatorname{PCSP}(P,Q) PCSP ( P , Q ) consists of a set of variables V ( I ) = { x 1 , … , x n } V(I)=\{x_1,\ldots,x_n\} V ( I ) = { x 1 , … , x n } and a set of constraints C ( I ) = { C 1 , … , C m } C(I)=\{C_1,\ldots,C_m\} C ( I ) = { C 1 , … , C m } , where each constraint C i C_i C i is a tuple of variables ( x i , 1 , … , x i , k ) (x_{i,1},\ldots,x_{i,k}) ( x i , 1 , … , x i , k ) . In this paper, we deal specifically with ternary relations (k = 3 k=3 k = 3 ), so every constraint is a triple. For a ternary relation R R R , an R R R -solution to I I I is a map h : V ( I ) → dom ( R ) h:V(I)\to\operatorname{dom}(R) h : V ( I ) → dom ( R ) such that ( h ( x ) , h ( y ) , h ( z ) ) ∈ R (h(x),h(y),h(z))\in R ( h ( x ) , h ( y ) , h ( z )) ∈ R for every ( x , y , z ) ∈ C ( I ) (x,y,z)\in C(I) ( x , y , z ) ∈ C ( I ) . For Z ⊆ V ( I ) Z\subseteq V(I) Z ⊆ V ( I ) , the induced subinstance is I [ Z ] = ( Z , C ( I ) ∩ Z 3 ) I[Z]=(Z,C(I)\cap Z^3) I [ Z ] = ( Z , C ( I ) ∩ Z 3 ) .
Definition 2.1. Fix P → Q P \to Q P → Q . Decision-PCSP( P , Q ) (P,Q) ( P , Q ) (or simply PCSP( P , Q ) (P,Q) ( P , Q ) ) asks us, given an instance promised to have either a P P P -solution (YES) or to have no Q Q Q -solution (NO), to distinguish these two cases. Search-PCSP( P , Q ) (P,Q) ( P , Q ) provides us with an instance which has a P P P -solution (that is not part of the input), and asks us to find a Q Q Q -solution of the instance.
Note that we require P → Q P \to Q P → Q for the problem to be well-defined, as otherwise the YES and NO cases overlap. It is well known that Decision-PCSP( P , Q ) (P,Q) ( P , Q ) reduces to Search-PCSP( P , Q ) (P,Q) ( P , Q ) [BBKO21]; the status of the converse is open.
We next state some simple lemmas that allow us to interpret Abelian embeddings as homomorphisms to certain “equation relations”. First, we note that when the relation is finite, one can assume without loss of generality that the target of an Abelian embedding is either the integers or a prime-order cyclic group. This is a direct consequence of the classification of finitely generated Abelian groups. The full proofs of this lemma and the next lemma are in Appendix § 5 .
Lemma 2.2. Let A A A be a finite set, r ≥ 1 r \ge1 r ≥ 1 , and ∅ ≠ R ⊆ A r \varnothing\ne R \subseteq A^r ∅ = R ⊆ A r . If R R R admits an Abelian embedding, then it admits one to some G ∈ { Z } ∪ { Z p ∣ p prime } G \in\{\mathbb{Z}\} \cup\{\mathbb{Z}_p \mid p\text{ prime}\} G ∈ { Z } ∪ { Z p ∣ p prime } .
For an Abelian group G G G , a set D D D , an element C ∈ G C \in G C ∈ G , and a positive integer c c c , we define
Eqn C ( G ) : = { ( x , y , z ) ∈ G 3 ∣ x + y + z = C } \operatorname{Eqn}_{C}(G) := \{(x,y,z) \in G^3 \mid x+y+z=C\} Eqn C ( G ) := {( x , y , z ) ∈ G 3 ∣ x + y + z = C }
Eqn ( G ) : = Eqn 0 ( G ) = { ( x , y , z ) ∈ G 3 ∣ x + y + z = 0 } \operatorname{Eqn}(G) := \operatorname{Eqn}_{0}(G) = \{(x,y,z) \in G^3 \mid x+y+z=0\} Eqn ( G ) := Eqn 0 ( G ) = {( x , y , z ) ∈ G 3 ∣ x + y + z = 0 }
Eqn ∗ ( G ) : = Eqn ( G ) ∩ NAE G \operatorname{Eqn}^{*}(G) := \operatorname{Eqn}(G) \cap\operatorname{NAE}_{G} Eqn ∗ ( G ) := Eqn ( G ) ∩ NAE G
NAE D : = D 3 ∖ { ( x , x , x ) ∣ x ∈ D } \operatorname{NAE}_{D} := D^3 \setminus\{(x,x,x) \mid x \in D\} NAE D := D 3 ∖ {( x , x , x ) ∣ x ∈ D }
NAE c : = NAE [ c ] \operatorname{NAE}_{c} := \operatorname{NAE}_{[c]} NAE c := NAE [ c ]
The primal (Gaifman) graph of a relation R R R has vertex set dom ( R ) \operatorname{dom}(R) dom ( R ) , with two values adjacent if they occur together in a tuple of R R R ; we call R R R connected if this graph is connected. For symmetric, connected, ternary relations, it is convenient to use the following homomorphism representation of an Abelian embedding.
Lemma 2.3. Let R R R be a ternary symmetric and connected relation, and let G G G be an Abelian group. Then R R R admits an Abelian embedding to G G G if and only if there exist C ∈ G C \in G C ∈ G and a nonconstant homomorphism q : R → Eqn C ( G ) q:R \to\operatorname{Eqn}_{C}(G) q : R → Eqn C ( G ) .
Except in Appendix § 5 (where we prove the two above lemmas), we henceforth use Abelian embedding exclusively in the homomorphism sense above.
Remark 2.4. Let R R R be a ternary relation, and q : R → Eqn C ( G ) q:R \to\operatorname{Eqn}_{C}(G) q : R → Eqn C ( G ) be a nonconstant homomorphism, where G ∈ { Z } ∪ { Z p ∣ p prime } G \in\{\mathbb{Z}\} \cup\{\mathbb{Z}_p \mid p\text{ prime}\} G ∈ { Z } ∪ { Z p ∣ p prime } . If G = Z G=\mathbb{Z} G = Z or G = Z p G=\mathbb{Z}_p G = Z p with p ≠ 3 p \ne3 p = 3 , then 3 q − C : R → Eqn ( G ) 3q-C:R \to\operatorname{Eqn}(G) 3 q − C : R → Eqn ( G ) is a nonconstant homomorphism. Thus we may assume without loss of generality that C = 0 C=0 C = 0 . If G = Z 3 G=\mathbb{Z}_3 G = Z 3 and C = 2 C=2 C = 2 , then − q : R → Eqn 1 ( Z 3 ) -q:R \to\operatorname{Eqn}_{1}(\mathbb{Z}_3) − q : R → Eqn 1 ( Z 3 ) is an Abelian embedding, so we may assume without loss of generality that C ∈ { 0 , 1 } C \in\{0,1\} C ∈ { 0 , 1 } .
Tractability Results
Our tractability results will be based on a generic reduction, which targets relational structures with homomorphisms to Eqn ( G ) \operatorname{Eqn}(G) Eqn ( G ) . It will also require some extra data which we call a c c c -rounding, which we now define.
Definition 3.1 (c c c -rounding). Let G G G be a finitely generated Abelian group. Write G ∗ G^* G ∗ for G ∖ { 0 } G \setminus\{0\} G ∖ { 0 } . A c c c -rounding for G G G is a map χ : G ∗ → [ c ] \chi:G^* \to[c] χ : G ∗ → [ c ] such that, for every g 1 , g 2 , g 3 ∈ G g_1,g_2,g_3 \in G g 1 , g 2 , g 3 ∈ G satisfying g 1 + g 2 + g 3 = 0 g_1+g_2+g_3=0 g 1 + g 2 + g 3 = 0 and ( g 1 , g 2 , g 3 ) ≠ ( 0 , 0 , 0 ) (g_1,g_2,g_3) \ne(0,0,0) ( g 1 , g 2 , g 3 ) = ( 0 , 0 , 0 ) , the nonzero values among g 1 , g 2 , g 3 g_1,g_2,g_3 g 1 , g 2 , g 3 do not all receive the same colour under χ \chi χ .
Definition 3.2. A c c c -rounding χ \chi χ is efficient if, for some fixed representation of G G G as a direct sum Z n ⊕ t G \mathbb{Z}^n \oplus tG Z n ⊕ tG where t G tG tG is the torsion subgroup of G G G , the value of χ ( x 1 , … , x n , g ) \chi(x_1,\ldots,x_n,g) χ ( x 1 , … , x n , g ) for x 1 , … , x n ∈ Z x_1,\ldots,x_n \in\mathbb{Z} x 1 , … , x n ∈ Z and g ∈ t G g \in tG g ∈ tG can be computed in polynomial time with respect to ∑ i log 2 ( 1 + ∣ x i ∣ ) \sum_i \log_2(1+|x_i|) ∑ i log 2 ( 1 + ∣ x i ∣ ) , the number of bits needed to represent x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n .
Every c c c -rounding we will give below will be efficient. Note that an (efficient) c c c -rounding for G G G is also an (efficient) c ′ c' c ′ -rounding for G G G for every c ′ ≥ c c' \ge c c ′ ≥ c .
Let us now state our goal for this section.
Theorem 3.3. Let R R R be a finite relation, and c ≥ 2 c \ge2 c ≥ 2 . Suppose there exist a finitely generated Abelian group G G G as well as a homomorphism q q q from R R R to Eqn ( G ) \operatorname{Eqn}(G) Eqn ( G ) , and a c c c -rounding χ \chi χ for G G G . Then, Decision-PCSP( R , NAE c ) (R,\operatorname{NAE}_{c}) ( R , NAE c ) reduces to Decision-PCSP( R ∣ q − 1 ( 0 ) , NAE c ) (R|_{q^{-1}(0)},\operatorname{NAE}_{c}) ( R ∣ q − 1 ( 0 ) , NAE c ) in polynomial time. Furthermore, if χ \chi χ is efficient, then Search-PCSP( R , NAE c ) (R,\operatorname{NAE}_{c}) ( R , NAE c ) reduces to Search-PCSP( R ∣ q − 1 ( 0 ) , NAE c ) (R|_{q^{-1}(0)},\operatorname{NAE}_{c}) ( R ∣ q − 1 ( 0 ) , NAE c ) in polynomial time.
Informal description. Given an instance I I I of Search-PCSP( R , NAE c ) (R,\operatorname{NAE}_{c}) ( R , NAE c ) , let h h h be a promised R R R -solution of I I I (although it is not given to us). Then q ∘ h q \circ h q ∘ h is an Eqn ( G ) \operatorname{Eqn}(G) Eqn ( G ) -solution of I I I which takes values in q ( dom ( R ) ) q(\operatorname{dom}(R)) q ( dom ( R )) . Starting from the given instance, we repeatedly perform the following four steps.
Solve 5 the induced system of equations over G G G , seeking a solution s s s that assigns some variable a nonzero value from q ( dom ( R ) ) q(\operatorname{dom}(R)) q ( dom ( R )) . If none exists, then we know that the image of h h h maps to 0 0 0 through q q q . Hence, we can restrict the domains of the variables to q − 1 ( 0 ) q^{-1}(0) q − 1 ( 0 ) , reducing the problem to Search-PCSP( R ∣ q − 1 ( 0 ) , NAE c ) (R|_{q^{-1}(0)},\operatorname{NAE}_{c}) ( R ∣ q − 1 ( 0 ) , NAE c ) as claimed. So assume we find such a solution s s s .
Round each nonzero value s ( x ) s(x) s ( x ) to χ ( s ( x ) ) ∈ [ c ] \chi(s(x)) \in[c] χ ( s ( x )) ∈ [ c ] ; i.e., set variable x x x to χ ( s ( x ) ) \chi(s(x)) χ ( s ( x )) once and for all.6
Peel off the nonzero support P = { x ∈ V ( I ) ∣ s ( x ) ≠ 0 } P = \{x \in V(I) \mid s(x) \ne0\} P = { x ∈ V ( I ) ∣ s ( x ) = 0 } . By the definition of c c c -rounding, every constraint which intersects P P P is already satisfied, no matter what values are assigned to the variables outside of P P P . Thus it is safe to remove all constraints intersecting P P P , as well as all variables in P P P .
Recurse on the subinstance induced by the remaining zero set s − 1 ( 0 ) = V ( I ) ∖ P s^{-1}(0) = V(I) \setminus P s − 1 ( 0 ) = V ( I ) ∖ P . Since P ≠ ∅ P \ne\varnothing P = ∅ , each round removes at least one variable.
Remark 3.4. Since every R ∣ q − 1 ( 0 ) R|_{q^{-1}(0)} R ∣ q − 1 ( 0 ) -solution is an R R R -solution, Decision-PCSP( R ∣ q − 1 ( 0 ) , NAE c ) (R|_{q^{-1}(0)},\operatorname{NAE}_{c}) ( R ∣ q − 1 ( 0 ) , NAE c ) reduces to Decision-PCSP( R , NAE c ) (R,\operatorname{NAE}_{c}) ( R , NAE c ) in polynomial time. Thus, Theorem 3.3 implies a polynomial-time equivalence between Decision-PCSP( R ∣ q − 1 ( 0 ) , NAE c ) (R|_{q^{-1}(0)},\operatorname{NAE}_{c}) ( R ∣ q − 1 ( 0 ) , NAE c ) and Decision-PCSP( R , NAE c ) (R,\operatorname{NAE}_{c}) ( R , NAE c ) . The same holds for Search-PCSP.
Remark 3.5. For a finite Abelian group G G G , define the subequation relation
SubEqn ( G ) = { ( x , y , z ) ∈ ( G ∗ ) 3 : x + y + z = 0 or x + y = 0 or x + z = 0 or y + z = 0 } . \operatorname{SubEqn}(G) = \left\{(x,y,z) \in(G^{*})^{3} : x+y+z=0\ \text{or}\ x+y=0\ \text{or}\ x+z=0\ \text{or}\ y+z=0\right\}. SubEqn ( G ) = { ( x , y , z ) ∈ ( G ∗ ) 3 : x + y + z = 0 or x + y = 0 or x + z = 0 or y + z = 0 } .
Let q : R → Eqn ( G ) q : R \to\operatorname{Eqn}(G) q : R → Eqn ( G ) , and put R 0 = R ∣ q − 1 ( 0 ) R_{0} = R|_{q^{-1}(0)} R 0 = R ∣ q − 1 ( 0 ) . Provided R → SubEqn ( G ) R \to\operatorname{SubEqn}(G) R → SubEqn ( G ) , the proof of Theorem 3.3, with each nonzero value s ( x ) s(x) s ( x ) retained instead of mapped through a rounding, gives Decision-PCSP( R , SubEqn ( G ) ) ≤ p (R,\operatorname{SubEqn}(G)) \le_p ( R , SubEqn ( G )) ≤ p Decision-PCSP( R 0 , SubEqn ( G ) ) (R_{0},\operatorname{SubEqn}(G)) ( R 0 , SubEqn ( G )) and Search-PCSP( R , SubEqn ( G ) ) ≤ p (R,\operatorname{SubEqn}(G)) \le_p ( R , SubEqn ( G )) ≤ p Search-PCSP( R 0 , SubEqn ( G ) ) (R_{0},\operatorname{SubEqn}(G)) ( R 0 , SubEqn ( G )) . Indeed, when a constraint is first removed, either its three nonzero values sum to zero, or exactly two values are nonzero and sum to zero. Hence it is satisfied in SubEqn ( G ) \operatorname{SubEqn}(G) SubEqn ( G ) , independently of values assigned later to the remaining variables. Moreover, a c c c -rounding χ : G ∗ → [ c ] \chi: G^{*} \to[c] χ : G ∗ → [ c ] is exactly the same as a homomorphism SubEqn ( G ) → NAE c \operatorname{SubEqn}(G) \to\operatorname{NAE}_{c} SubEqn ( G ) → NAE c .
Example 3.6. We give a few examples of roundings (and two nonexamples):
χ ∞ : Z ∗ → { 1 , 2 } , χ ∞ ( x ) = { 1 , x > 0 2 , x < 0 \chi_{\infty} : \mathbb{Z}^{*} \to\{1,2\}, \qquad
\chi_{\infty}(x) =
\begin{cases}
1, & x > 0 \\
2, & x < 0
\end{cases} χ ∞ : Z ∗ → { 1 , 2 } , χ ∞ ( x ) = { 1 , 2 , x > 0 x < 0
χ p : Z p ∗ → { 1 , 2 , 3 , 4 } , χ p ( x ) = { 1 , 0 < x < p 3 , 2 , p 3 < x < p 2 , 3 , p 2 < x < 2 p 3 , 4 , 2 p 3 < x < p . \chi_p : \mathbb{Z}_p^* \to\{1,2,3,4\}, \qquad\chi_p(x)=
\begin{cases}
1, & 0 < x < \frac{p}{3},\\
2, & \frac{p}{3} < x < \frac{p}{2},\\
3, & \frac{p}{2} < x < \frac{2p}{3},\\
4, & \frac{2p}{3} < x < p.
\end{cases} χ p : Z p ∗ → { 1 , 2 , 3 , 4 } , χ p ( x ) = ⎩ ⎨ ⎧ 1 , 2 , 3 , 4 , 0 < x < 3 p , 3 p < x < 2 p , 2 p < x < 3 2 p , 3 2 p < x < p .
More generally, for every prime p ≥ 5 p \ge5 p ≥ 5 and every k ≥ 1 k \ge1 k ≥ 1 , the following is a 4-rounding for Z p k \mathbb{Z}_{p^k} Z p k . Given x ∈ Z p k ∗ x \in\mathbb{Z}_{p^k}^* x ∈ Z p k ∗ , write x = p j a x=p^j a x = p j a , where 0 ≤ j < k 0 \le j < k 0 ≤ j < k and p ∤ a p \nmid a p ∤ a , and define χ p k ( x ) = χ p ( a m o d p ) \chi_{p^k}(x)=\chi_p(a \bmod p) χ p k ( x ) = χ p ( a mod p ) . To see that this works, write x x x in base p p p , and for x + y + z = 0 x+y+z=0 x + y + z = 0 consider the least significant nonzero digits in x , y , z x,y,z x , y , z . At least two must appear at the same position, and must sum up to 0 0 0 — hence correctness follows from the correctness of χ p \chi_p χ p .
χ ( n ) : ( G n ) ∗ → [ c ] , χ ( n ) ( x 1 , … , x n ) = χ ( x j ) , j = min { i ∣ x i ≠ 0 } . \chi^{(n)}:(G^n)^* \to[c], \qquad\chi^{(n)}(x_1,\ldots,x_n)=\chi(x_j), \qquad j=\min\{i\mid x_i\ne0\}. χ ( n ) : ( G n ) ∗ → [ c ] , χ ( n ) ( x 1 , … , x n ) = χ ( x j ) , j = min { i ∣ x i = 0 } .
This follows by essentially the same reasoning as the previous example.
χ Π : ( ∏ i = 1 n G i ) ∗ → [ c ] , χ Π ( x 1 , … , x n ) = χ j ( x j ) , j = min { i ∣ x i ≠ 0 } . \chi_{\Pi}:\left(\prod_{i=1}^{n}G_i\right)^* \to[c], \qquad\chi_{\Pi}(x_1,\ldots,x_n)=\chi_j(x_j), \qquad j=\min\{i\mid x_i\ne0\}. χ Π : ( i = 1 ∏ n G i ) ∗ → [ c ] , χ Π ( x 1 , … , x n ) = χ j ( x j ) , j = min { i ∣ x i = 0 } .
Nonexamples involve Z 2 \mathbb{Z}_2 Z 2 and Z 3 \mathbb{Z}_3 Z 3 as there are no c c c -roundings for Z 2 \mathbb{Z}_2 Z 2 and Z 3 \mathbb{Z}_3 Z 3 , for any c c c . In Z 2 \mathbb{Z}_2 Z 2 , the equation 1 + 1 + 0 = 0 1+1+0=0 1 + 1 + 0 = 0 has two nonzero entries, both equal to 1 1 1 , so they necessarily receive the same colour. In Z 3 \mathbb{Z}_3 Z 3 , the same obstruction is given by 1 + 1 + 1 = 0 1+1+1=0 1 + 1 + 1 = 0 . Both equations violate the defining property of a rounding.
We defer a formal proof of Theorem 3.3 to Appendix B; the filling in of the informal description is, however, straightforward.
Remark 3.7 (Generalising to higher arities). For r ≥ 3 r\ge3 r ≥ 3 , define
Eqn ( r ) ( G ) = { ( x 1 , … , x r ) ∈ G r : ∑ i = 1 r x i = 0 } , NAE D ( r ) = D r ∖ { ( a , … , a ) : a ∈ D } , c r = ∑ k = 1 r φ ( k ) , \operatorname{Eqn}^{(r)}(G)=\left\{(x_1,\ldots,x_r)\in G^r:\sum_{i=1}^{r}x_i=0\right\}, \qquad\operatorname{NAE}^{(r)}_D=D^r\setminus\{(a,\ldots,a):a\in D\}, \qquad c_r=\sum_{k=1}^{r}\varphi(k), Eqn ( r ) ( G ) = { ( x 1 , … , x r ) ∈ G r : i = 1 ∑ r x i = 0 } , NAE D ( r ) = D r ∖ {( a , … , a ) : a ∈ D } , c r = k = 1 ∑ r φ ( k ) ,
where φ \varphi φ is the Euler totient function. An r r r -ary c c c -rounding of G G G is a map χ : G ∖ { 0 } → [ c ] \chi:G\setminus\{0\}\to[c] χ : G ∖ { 0 } → [ c ] such that, for every nonzero tuple ( x 1 , … , x r ) ∈ Eqn ( r ) ( G ) (x_1,\ldots,x_r)\in\operatorname{Eqn}^{(r)}(G) ( x 1 , … , x r ) ∈ Eqn ( r ) ( G ) , the nonzero entries receive at least two different colours. With these replacements, the proof of Theorem 3.3 applies verbatim in arity r r r .
The existence of a rounding depends on the arity. An r r r -ary rounding is an s s s -ary rounding for every s ≤ r s\le r s ≤ r , by padding zero-sum s s s -tuples with zeros, but the converse need not hold. If p ≤ r p\le r p ≤ r , then Z p \mathbb{Z}_p Z p has no r r r -ary c c c -rounding for any c c c . If p > r p>r p > r on the other hand, we can generalise the construction of the ternary 4-rounding to get an r r r -ary c r c_r c r -rounding for Z p \mathbb{Z}_p Z p as follows: construct the set Q p , r = { p a b : 1 ≤ a ≤ b ≤ r } ⊂ Q Q_{p,r}=\left\{p^{\frac{a}{b}}:1\le a\le b\le r\right\}\subset\mathbb{Q} Q p , r = { p b a : 1 ≤ a ≤ b ≤ r } ⊂ Q . Note that ∣ Q p , r ∣ = c r \lvert Q_{p,r}\rvert=c_r ∣ Q p , r ∣ = c r for all p p p . Then, identifying Z p ∗ \mathbb{Z}_p^* Z p ∗ with { 1 , … , p − 1 } \{1,\ldots,p-1\} { 1 , … , p − 1 } , assign to each x ∈ Z p ∗ x\in\mathbb{Z}_p^* x ∈ Z p ∗ the colour indexed by the least element of Q p , r Q_{p,r} Q p , r greater than x x x . This is an r r r -ary c r c_r c r -rounding of Z p \mathbb{Z}_p Z p . There are however for many pairs ( p , r ) (p,r) ( p , r ) roundings which use even fewer colours.
Finally, although Lemma 2.2 generalises immediately, the normalisation of an Abelian embedding described in Remark 2.4 also depends on the arity: if q : R → Eqn C ( r ) ( Z p ) q:R\to\operatorname{Eqn}^{(r)}_C(\mathbb{Z}_p) q : R → Eqn C ( r ) ( Z p ) , then x ↦ r q ( x ) − C x\mapsto rq(x)-C x ↦ r q ( x ) − C is a nonconstant homomorphism to Eqn ( r ) ( Z p ) \operatorname{Eqn}^{(r)}(\mathbb{Z}_p) Eqn ( r ) ( Z p ) provided p ∤ r p\nmid r p ∤ r . Primes dividing r r r must be treated separately.
Consequences of Theorem
Corollary 3.8. Under the assumptions of Theorem 3.3 for the Search-PCSP reduction, if R ∣ q − 1 ( 0 ) = ∅ R|_{q^{-1}(0)}=\varnothing R ∣ q − 1 ( 0 ) = ∅ , then Search-PCSP ( R , N A E c ) (R,\mathrm{NAE}_{c}) ( R , NAE c ) is solvable in polynomial time.
Proof. By Theorem 3.3, it suffices to solve Search-PCSP( ∅ , N A E c ) (\varnothing,\mathrm{NAE}_{c}) ( ∅ , NAE c ) . Any promised instance of this problem has no constraints, so assigning an arbitrary colour to each remaining variable gives an N A E c \mathrm{NAE}_{c} NAE c -solution. □ \square □
Together with the existence of an Abelian embedding to Z \mathbb{Z} Z for 1-in-3, this is enough to prove that Search-PCSP(1-in-3, N A E 2 \mathrm{NAE}_{2} NAE 2 ) can be solved in polynomial time, a classical theorem in the literature [7 ] . This corollary is also sufficient to prove our tractability claim about detrivialised equations.
Corollary 3.9. For any finite Abelian group G G G without elements of order 2 2 2 or 3 3 3 , Search-PCSP ( E q n ∗ ( G ) , N A E 4 ) (\mathrm{Eqn}^{*}(G),\mathrm{NAE}_{4}) ( Eqn ∗ ( G ) , NAE 4 ) is solvable in polynomial time.
Proof. By the classification theorem for finite Abelian groups, G = Z p 1 k 1 × ⋯ × Z p n k n G=\mathbb{Z}_{p_{1}^{k_{1}}}\times\cdots\times\mathbb{Z}_{p_{n}^{k_{n}}} G = Z p 1 k 1 × ⋯ × Z p n k n with p i ≠ 2 , 3 p_i\ne2,3 p i = 2 , 3 . By Example 3.6, Z p i k i \mathbb{Z}_{p_i^{k_i}} Z p i k i has a 4-rounding for i = 1 , … , n i=1,\ldots,n i = 1 , … , n , and the product of groups which admit 4-roundings also admits a 4-rounding. Hence G G G admits a 4-rounding. Moreover, letting q = id G q=\operatorname{id}_{G} q = id G , q q q is a homomorphism E q n ∗ ( G ) → E q n ( G ) \mathrm{Eqn}^{*}(G)\to\mathrm{Eqn}(G) Eqn ∗ ( G ) → Eqn ( G ) with q − 1 ( 0 ) = { 0 } q^{-1}(0)=\{0\} q − 1 ( 0 ) = { 0 } , and E q n ∗ ( G ) ∣ { 0 } = ∅ \mathrm{Eqn}^{*}(G)|_{\{0\}}=\varnothing Eqn ∗ ( G ) ∣ { 0 } = ∅ since ( 0 , 0 , 0 ) ∉ E q n ∗ ( G ) (0,0,0)\notin\mathrm{Eqn}^{*}(G) ( 0 , 0 , 0 ) ∈ / Eqn ∗ ( G ) . The result now follows from Corollary 3.8. □ \square □
Corollary 3.10. Let R R R be a finite ternary relation. Suppose that every nonempty induced subrelation S = R ∣ A S=R|_{A} S = R ∣ A satisfies at least one of the following:
there is a nonconstant homomorphism q q q from S S S to E q n ( Z ) \mathrm{Eqn}(\mathbb{Z}) Eqn ( Z ) or E q n ( Z p ) \mathrm{Eqn}(\mathbb{Z}_{p}) Eqn ( Z p ) for some prime p > 3 p>3 p > 3 ;
there is a homomorphism q : S → E q n 1 ( Z 3 ) q:S\to\mathrm{Eqn}_{1}(\mathbb{Z}_{3}) q : S → Eqn 1 ( Z 3 ) .
Then Search-PCSP ( R , N A E 4 ) (R,\mathrm{NAE}_{4}) ( R , NAE 4 ) is solvable in polynomial time.
Proof. Set S 0 = R S_{0}=R S 0 = R , and consider the current nonempty induced subrelation S i S_i S i . If there is a homomorphism q i : S i → E q n 1 ( Z 3 ) q_i:S_i\to\mathrm{Eqn}_{1}(\mathbb{Z}_{3}) q i : S i → Eqn 1 ( Z 3 ) , solve (by Gaussian elimination) the induced system of equations of the form x + y + z ≡ 1 ( m o d 3 ) x+y+z\equiv1\pmod3 x + y + z ≡ 1 ( mod 3 ) . It has a solution because the instance has an S i S_i S i -solution. Moreover, since E q n 1 ( Z 3 ) \mathrm{Eqn}_{1}(\mathbb{Z}_{3}) Eqn 1 ( Z 3 ) contains no constant tuple, any solution is an N A E 3 \mathrm{NAE}_{3} NAE 3 -colouring, and hence an N A E 4 \mathrm{NAE}_{4} NAE 4 -colouring.
Otherwise, there is a nonconstant homomorphism q i : S i → E q n ( G i ) q_i:S_i\to\mathrm{Eqn}(G_i) q i : S i → Eqn ( G i ) , where G i = Z G_i=\mathbb{Z} G i = Z or G i = Z p G_i=\mathbb{Z}_{p} G i = Z p for some prime p ≥ 5 p\ge5 p ≥ 5 . In either case G i G_i G i has an efficient 4-rounding (see Example 3.6), so Theorem 3.3 reduces the problem to the induced subrelation S i + 1 = S i ∣ q i − 1 ( 0 ) S_{i+1}=S_i|_{q_i^{-1}(0)} S i + 1 = S i ∣ q i − 1 ( 0 ) . Since q i q_i q i is nonconstant, q i − 1 ( 0 ) q_i^{-1}(0) q i − 1 ( 0 ) is a proper subset of dom ( S i ) \operatorname{dom}(S_i) dom ( S i ) .
We may repeat this argument because every S i S_i S i is an induced subrelation of R R R . After at most ∣ dom ( R ) ∣ |\operatorname{dom}(R)| ∣ dom ( R ) ∣ steps we therefore encounter the Z 3 \mathbb{Z}_{3} Z 3 case or reach the empty relation. Both have a polynomial-time search algorithm, and the reductions lift the resulting solution to an N A E 4 \mathrm{NAE}_{4} NAE 4 -solution of the original instance. □ \square □
S → E q n 1 ( r ) ( Z p ) for some prime p ∣ r . S\to\mathrm{Eqn}^{(r)}_{1}(\mathbb{Z}_{p})\qquad\text{for some prime }p\mid r. S → Eqn 1 ( r ) ( Z p ) for some prime p ∣ r .
Example 3.12. Let R R R be a nonempty symmetric ternary relation, and take two new elements + + + , − - − ∉ dom ( R ) \notin\operatorname{dom}(R) ∈ / dom ( R ) . Define the suspension of R R R as
S ( R ) = R ∪ { ( a , + , − ) and all permutations of this tuple ∣ a ∈ dom ( R ) } . S(R)=R\cup\{(a,+,-)\text{ and all permutations of this tuple}\mid a\in\operatorname{dom}(R)\}. S ( R ) = R ∪ {( a , + , − ) and all permutations of this tuple ∣ a ∈ dom ( R )} . The relation S ( R ) S(R) S ( R ) has an Abelian embedding to every nontrivial Abelian group, given by + ↦ g +\mapsto g + ↦ g , − ↦ − g -\mapsto-g − ↦ − g , a ↦ 0 ∀ a ∈ dom ( R ) a\mapsto0\ \forall a\in\operatorname{dom}(R) a ↦ 0 ∀ a ∈ dom ( R ) for some nonzero g ∈ G g\in G g ∈ G . Moreover, if G G G admits a rounding, every nonconstant
q : S ( R ) → Eqn ( G ) q : S(R) \to\operatorname{Eqn}(G) q : S ( R ) → Eqn ( G ) satisfies q − 1 ( 0 ) = dom ( R ) q^{-1}(0) = \operatorname{dom}(R) q − 1 ( 0 ) = dom ( R ) , and hence S ( R ) ∣ q − 1 ( 0 ) = R S(R)|_{q^{-1}(0)} = R S ( R ) ∣ q − 1 ( 0 ) = R . Thus no choice of embedding can remove more than one suspension layer, and iterating the construction makes arbitrarily many applications of Theorem 3.3 necessary before the original relation R R R is reached.
For a prime p ≥ 3 p \ge3 p ≥ 3 , with dom ( R ) ∩ Z p = ∅ \operatorname{dom}(R) \cap\mathbb{Z}_p = \varnothing dom ( R ) ∩ Z p = ∅ , define the p p p -suspension of R R R as
S p ( R ) = R ∪ Eqn ∗ ( Z p ) ∪ { ( a , x , − x ) and all its permutations ∣ a ∈ dom ( R ) , x ∈ Z p ∗ } . S_p(R) = R \cup\operatorname{Eqn}^*(\mathbb{Z}_p) \cup\{(a,x,-x)\text{ and all its permutations} \mid a \in\operatorname{dom}(R),\ x \in\mathbb{Z}_p^*\}. S p ( R ) = R ∪ Eqn ∗ ( Z p ) ∪ {( a , x , − x ) and all its permutations ∣ a ∈ dom ( R ) , x ∈ Z p ∗ } .
Note that S p ( R ) S_p(R) S p ( R ) has an Abelian embedding to Z p \mathbb{Z}_p Z p , given by π p ( a ) = 0 \pi_p(a) = 0 π p ( a ) = 0 for a ∈ dom ( R ) a \in\operatorname{dom}(R) a ∈ dom ( R ) and π p ( x ) = x \pi_p(x) = x π p ( x ) = x for x ∈ Z p x \in\mathbb{Z}_p x ∈ Z p . Then S p ( R ) ∣ π p − 1 ( 0 ) = R S_p(R)|_{\pi_p^{-1}(0)} = R S p ( R ) ∣ π p − 1 ( 0 ) = R . Moreover, every Abelian embedding q : S p ( R ) → Eqn C ( G ) q : S_p(R) \to\operatorname{Eqn}_C(G) q : S p ( R ) → Eqn C ( G ) has the form q = g + φ ∘ π p q = g + \varphi\circ\pi_p q = g + φ ∘ π p , where g ∈ G g \in G g ∈ G satisfies 3 g = C 3g = C 3 g = C , and φ : Z p → G \varphi: \mathbb{Z}_p \to G φ : Z p → G is a group homomorphism. Hence S p ( R ) S_p(R) S p ( R ) embeds into none of Z \mathbb{Z} Z , Z p ′ \mathbb{Z}_{p'} Z p ′ for primes p ′ ≠ p p' \ne p p ′ = p , so nested p p p -suspensions can force different prime-order targets at successive steps.
Remark 3.13. One interesting open question is the complexity of PCSP ( Eqn ∗ ( Z n ) , NAE c ) \operatorname{PCSP}(\operatorname{Eqn}^*(\mathbb{Z}_n),\operatorname{NAE}_c) PCSP ( Eqn ∗ ( Z n ) , NAE c ) for n ≥ 2 n \ge2 n ≥ 2 and c c c sufficiently large.7 Eqn ∗ ( Z n ) \operatorname{Eqn}^*(\mathbb{Z}_n) Eqn ∗ ( Z n ) has an Abelian embedding (to Z 2 \mathbb{Z}_2 Z 2 for instance), but not the kind that gives tractability in Corollary 3.10 .
Hardness of approximating detrivialised equations with 3 colours
For the hardness results, we will need the following notions from the algebraic approach to PCSPs [BBKO21], which we specialise to the case of relational structures with one symmetric relation.8 An n n n -ary polymorphism is a homomorphism f : R n → Q f : R^n \to Q f : R n → Q . We let Pol ( n ) ( R , Q ) \operatorname{Pol}^{(n)}(R,Q) Pol ( n ) ( R , Q ) denote the set of all polymorphisms R n → Q R^n \to Q R n → Q , and Pol ( R , Q ) = ⋃ n ≥ 1 Pol ( n ) ( R , Q ) \operatorname{Pol}(R,Q) = \bigcup_{n \ge1}\operatorname{Pol}^{(n)}(R,Q) Pol ( R , Q ) = ⋃ n ≥ 1 Pol ( n ) ( R , Q ) . For this, we need to define the notion of a minor of an operation. Suppose f : A n → B f : A^n \to B f : A n → B and π : [ n ] → [ m ] \pi: [n] \to[m] π : [ n ] → [ m ] are functions. We then define f π : A m → B f^\pi: A^m \to B f π : A m → B by
f π ( x 1 , … , x m ) = f ( x π ( 1 ) , … , x π ( n ) ) . f^\pi(x_1,\ldots,x_m) = f(x_{\pi(1)},\ldots,x_{\pi(n)}). f π ( x 1 , … , x m ) = f ( x π ( 1 ) , … , x π ( n ) ) .
Definition 4.1. A (function) minion M \mathcal{M} M on a pair of finite sets ( A , B ) (A,B) ( A , B ) is a nonempty subset of { f : A n → B ∣ n ≥ 1 } \{f : A^n \to B \mid n \ge1\} { f : A n → B ∣ n ≥ 1 } that is closed under taking minors, meaning that for each minor map π : [ n ] → [ m ] \pi: [n] \to[m] π : [ n ] → [ m ] and n n n -ary f ∈ M f \in\mathcal{M} f ∈ M , we have f π ∈ M f^\pi\in\mathcal{M} f π ∈ M . For fixed n ≥ 1 n \ge1 n ≥ 1 , let M ( n ) \mathcal{M}^{(n)} M ( n ) denote the set of n n n -ary functions in M \mathcal{M} M .
Note that for relations R R R and Q Q Q , Pol ( R , Q ) \operatorname{Pol}(R,Q) Pol ( R , Q ) is closed under taking minors. If there is also a homomorphism from R R R to Q Q Q , then Pol ( R , Q ) \operatorname{Pol}(R,Q) Pol ( R , Q ) is nonempty and hence forms a minion.
Definition 4.2. Let M \mathcal{M} M and N \mathcal{N} N be minions. A collection of maps μ = ( μ n ) n = 1 ∞ \mu= (\mu_n)_{n=1}^{\infty} μ = ( μ n ) n = 1 ∞ with μ n : M ( n ) → N ( n ) \mu_n : \mathcal{M}^{(n)} \to\mathcal{N}^{(n)} μ n : M ( n ) → N ( n ) is a minion homomorphism from M \mathcal{M} M to N \mathcal{N} N if it preserves taking minors, meaning that for each minor map π : [ n ] → [ m ] \pi: [n] \to[m] π : [ n ] → [ m ] and f ∈ M ( n ) f \in\mathcal{M}^{(n)} f ∈ M ( n ) , we have ( μ n ( f ) ) π = μ m ( f π ) (\mu_n(f))^\pi= \mu_m(f^\pi) ( μ n ( f ) ) π = μ m ( f π ) .
Theorem 4.3. [BBKO21, Theorem 3.1] Let R 1 , R 2 , Q 1 , Q 2 R_1,R_2,Q_1,Q_2 R 1 , R 2 , Q 1 , Q 2 be relations such that R 1 → Q 1 R_1 \to Q_1 R 1 → Q 1 and R 2 → Q 2 R_2 \to Q_2 R 2 → Q 2 . If there exists a minion homomorphism from Pol ( R 1 , Q 1 ) \operatorname{Pol}(R_1,Q_1) Pol ( R 1 , Q 1 ) to Pol ( R 2 , Q 2 ) \operatorname{Pol}(R_2,Q_2) Pol ( R 2 , Q 2 ) , then PCSP ( R 2 , Q 2 ) \operatorname{PCSP}(R_2,Q_2) PCSP ( R 2 , Q 2 ) reduces to PCSP ( R 1 , Q 1 ) \operatorname{PCSP}(R_1,Q_1) PCSP ( R 1 , Q 1 ) in logarithmic space.
Our goal is to prove that PCSP ( Eqn ∗ ( G ) , NAE 3 ) \operatorname{PCSP}(\operatorname{Eqn}^*(G),\operatorname{NAE}_3) PCSP ( Eqn ∗ ( G ) , NAE 3 ) is NP-hard whenever G G G has no elements of order 2 or 3, and the problem is well-defined, i.e. Eqn ∗ ( G ) → NAE 3 \operatorname{Eqn}^*(G) \to\operatorname{NAE}_3 Eqn ∗ ( G ) → NAE 3 . We show that for this it suffices to consider the case G = Z p G = \mathbb{Z}_p G = Z p for p ≥ 5 p \ge5 p ≥ 5 – in the subsequent sections we prove hardness for these cases.
Lemma 4.4. If an Abelian group G G G admits an element g g g of order k k k , and Eqn ∗ ( G ) → NAE 3 \operatorname{Eqn}^*(G) \to\operatorname{NAE}_3 Eqn ∗ ( G ) → NAE 3 , then PCSP ( Eqn ∗ ( Z k ) , NAE 3 ) \operatorname{PCSP}(\operatorname{Eqn}^*(\mathbb{Z}_k),\operatorname{NAE}_3) PCSP ( Eqn ∗ ( Z k ) , NAE 3 ) reduces to PCSP ( Eqn ∗ ( G ) , NAE 3 ) \operatorname{PCSP}(\operatorname{Eqn}^*(G),\operatorname{NAE}_3) PCSP ( Eqn ∗ ( G ) , NAE 3 ) . In particular, if G G G is a nontrivial finite Abelian group with no elements of order 2 or 3 such that Eqn ∗ ( G ) → NAE 3 \operatorname{Eqn}^*(G) \to\operatorname{NAE}_3 Eqn ∗ ( G ) → NAE 3 , then PCSP ( Eqn ∗ ( Z p ) , NAE 3 ) \operatorname{PCSP}(\operatorname{Eqn}^*(\mathbb{Z}_p),\operatorname{NAE}_3) PCSP ( Eqn ∗ ( Z p ) , NAE 3 ) reduces to PCSP ( Eqn ∗ ( G ) , NAE 3 ) \operatorname{PCSP}(\operatorname{Eqn}^*(G),\operatorname{NAE}_3) PCSP ( Eqn ∗ ( G ) , NAE 3 ) for some prime p ≥ 5 p \ge5 p ≥ 5 .
Proof. Note that n ↦ n g n \mapsto ng n ↦ n g determines an injective homomorphism Z k → G \mathbb{Z}_k \to G Z k → G , which induces a homomorphism Eqn ∗ ( Z k ) → Eqn ∗ ( G ) \operatorname{Eqn}^{*}(\mathbb{Z}_k) \to\operatorname{Eqn}^{*}(G) Eqn ∗ ( Z k ) → Eqn ∗ ( G ) (since injectivity preserves the nonconstancy of tuples). Thus, as every Eqn ∗ ( Z k ) \operatorname{Eqn}^{*}(\mathbb{Z}_k) Eqn ∗ ( Z k ) -solution induces an Eqn ∗ ( G ) \operatorname{Eqn}^{*}(G) Eqn ∗ ( G ) -solution by composition with this homomorphism, the identity map gives the required reduction. For the second part, a nontrivial finite Abelian group must have some element of prime order, and by assumption it cannot have order 2 or 3. □
The proof of hardness in Theorem 1.6 then follows by Lemma 4.4 with Theorem 4.13 and Theorem 4.19 .
Hardness for p = 5 p = 5 p = 5
Definition 4.5. Following [28 ] , a digraph G G G is balanced if each of its oriented cycles has zero net length. Following [4 , 19 ] , associate with a directed graph G G G , viewed as a binary relation, the ternary symmetric relation G ^ ≔ { ( x , x , y ) , ( x , y , x ) , ( y , x , x ) ∣ ( x , y ) ∈ G } \widehat{G} \coloneqq\{(x,x,y),(x,y,x),(y,x,x) \mid(x,y) \in G\} G : = {( x , x , y ) , ( x , y , x ) , ( y , x , x ) ∣ ( x , y ) ∈ G } .
Theorem 4.6. [19 Theorem 2] Let G G G be a bipartite directed graph. Then PCSP ( G ^ , NAE 2 ) \operatorname{PCSP}(\widehat{G},\operatorname{NAE}_2) PCSP ( G , NAE 2 ) is tractable if G G G is balanced, and it is NP-hard otherwise.
Let D 4 ≔ { ( x , − 2 x ) ∣ x ∈ Z 5 ∗ } D_4 \coloneqq\{(x,-2x) \mid x \in\mathbb{Z}_5^{*}\} D 4 : = {( x , − 2 x ) ∣ x ∈ Z 5 ∗ } . This is a directed cycle of net length 4, so it is bipartite and not balanced.
Corollary 4.7. PCSP ( D ^ 4 , NAE 2 ) \operatorname{PCSP}(\widehat{D}_4,\operatorname{NAE}_2) PCSP ( D 4 , NAE 2 ) is NP-hard.
Moreover, D ^ 4 \widehat{D}_4 D 4 is the restriction of Eqn ∗ ( Z 5 ) \operatorname{Eqn}^{*}(\mathbb{Z}_5) Eqn ∗ ( Z 5 ) to Z 5 ∗ \mathbb{Z}_5^{*} Z 5 ∗ .
We will construct a minion homomorphism from Pol ( Eqn ∗ ( Z 5 ) , NAE 3 ) \operatorname{Pol}(\operatorname{Eqn}^{*}(\mathbb{Z}_5),\operatorname{NAE}_3) Pol ( Eqn ∗ ( Z 5 ) , NAE 3 ) to Pol ( D ^ 4 , NAE 2 ) \operatorname{Pol}(\widehat{D}_4,\operatorname{NAE}_2) Pol ( D 4 , NAE 2 ) . Let g ∈ Pol ( Eqn ∗ ( Z 5 ) , NAE 3 ) g \in\operatorname{Pol}(\operatorname{Eqn}^{*}(\mathbb{Z}_5),\operatorname{NAE}_3) g ∈ Pol ( Eqn ∗ ( Z 5 ) , NAE 3 ) with g ( 0 , … , 0 ) = 3 g(0,\ldots,0) = 3 g ( 0 , … , 0 ) = 3 .
Lemma 4.8. For every u ∈ Z 5 ∗ n u \in\mathbb{Z}_5^{*n} u ∈ Z 5 ∗ n , we have ∣ { g ( u ) , g ( − u ) } ∩ { 1 , 2 } ∣ = 1 |\{g(u),g(-u)\} \cap\{1,2\}| = 1 ∣ { g ( u ) , g ( − u )} ∩ { 1 , 2 } ∣ = 1 .
Proof. Note that for every n n n -ary polymorphism g g g and every u ∈ Z 5 ∗ n u \in\mathbb{Z}_5^{*n} u ∈ Z 5 ∗ n , h ( t ) ≔ g ( t u ) h(t) \coloneqq g(tu) h ( t ) : = g ( t u ) is a homomorphism from Eqn ∗ ( Z 5 ) \operatorname{Eqn}^{*}(\mathbb{Z}_5) Eqn ∗ ( Z 5 ) to NAE 3 \operatorname{NAE}_3 NAE 3 . Thus this follows from the classification of homomorphisms in Theorem 1.8, and the assumption g ( 0 , … , 0 ) = 3 g(0,\ldots,0) = 3 g ( 0 , … , 0 ) = 3 . □
Definition 4.9. For g ∈ Pol ( Eqn ∗ ( Z 5 ) , NAE 3 ) g \in\operatorname{Pol}(\operatorname{Eqn}^{*}(\mathbb{Z}_5),\operatorname{NAE}_3) g ∈ Pol ( Eqn ∗ ( Z 5 ) , NAE 3 ) with g ( 0 , … , 0 ) = 3 g(0,\ldots,0) = 3 g ( 0 , … , 0 ) = 3 , define τ g \tau_g τ g by letting τ g ( u ) ∈ { 1 , 2 } \tau_g(u) \in\{1,2\} τ g ( u ) ∈ { 1 , 2 } denote, for each u ∈ Z 5 ∗ n u \in\mathbb{Z}_5^{*n} u ∈ Z 5 ∗ n , the unique element in { g ( u ) , g ( − u ) } ∩ { 1 , 2 } \{g(u),g(-u)\} \cap\{1,2\} { g ( u ) , g ( − u )} ∩ { 1 , 2 } .
Proposition 4.10. τ g ∈ Pol ( D ^ 4 , NAE 2 ) \tau_g \in\operatorname{Pol}(\widehat{D}_4,\operatorname{NAE}_2) τ g ∈ Pol ( D 4 , NAE 2 ) .
Proof. Suppose for a contradiction that u , v , w ∈ Z 5 ∗ n u,v,w \in\mathbb{Z}_5^{*n} u , v , w ∈ Z 5 ∗ n satisfy u + v + w = 0 u+v+w=0 u + v + w = 0 but τ g ( u ) = τ g ( v ) = τ g ( w ) ≔ c \tau_g(u)=\tau_g(v)=\tau_g(w) \coloneqq c τ g ( u ) = τ g ( v ) = τ g ( w ) : = c . Then for each λ ∈ Z 5 ∗ \lambda\in\mathbb{Z}_5^{*} λ ∈ Z 5 ∗ , the triple ( λ u , λ v , λ w ) (\lambda u,\lambda v,\lambda w) ( λ u , λ v , λ w ) is a constraint triple. Note that for all u ∈ Z 5 ∗ n u \in\mathbb{Z}_5^{*n} u ∈ Z 5 ∗ n , τ g ( − u ) = τ g ( u ) \tau_g(-u)=\tau_g(u) τ g ( − u ) = τ g ( u ) , and τ g ( 2 u ) ≠ τ g ( u ) \tau_g(2u)\ne\tau_g(u) τ g ( 2 u ) = τ g ( u ) . Hence every value in the first and fourth rows of the matrix below is in { 3 , c } \{3,c\} { 3 , c } , and every value in the second and third rows is in { 3 , 3 − c } \{3,3-c\} { 3 , 3 − c } . Consequently, 3 must appear at least once in each row (otherwise the row would be monochromatic, contradicting that g g g is a polymorphism).
g ( u ) g ( v ) g ( w ) g ( 2 u ) g ( 2 v ) g ( 2 w ) g ( 3 u ) g ( 3 v ) g ( 3 w ) g ( 4 u ) g ( 4 v ) g ( 4 w ) \begin{aligned}
g(u) &\quad g(v) \quad g(w) \\
g(2u) &\quad g(2v) \quad g(2w) \\
g(3u) &\quad g(3v) \quad g(3w) \\
g(4u) &\quad g(4v) \quad g(4w)
\end{aligned} g ( u ) g ( 2 u ) g ( 3 u ) g ( 4 u ) g ( v ) g ( w ) g ( 2 v ) g ( 2 w ) g ( 3 v ) g ( 3 w ) g ( 4 v ) g ( 4 w )
By the pigeonhole principle, some column has at least two occurrences of the value 3, but since also g ( 0 , … , 0 ) = 3 g(0,\ldots,0)=3 g ( 0 , … , 0 ) = 3 , this contradicts Theorem 1.8, applied to the homomorphism induced by that column. □
Proposition 4.11. g ↦ τ g g \mapsto\tau_g g ↦ τ g preserves minors.
Proof. Since { g π ( u ) , g π ( − u ) } = { g ( u π ) , g ( − u π ) } \{g^{\pi}(u),g^{\pi}(-u)\}=\{g(u^{\pi}),g(-u^{\pi})\} { g π ( u ) , g π ( − u )} = { g ( u π ) , g ( − u π )} , we have that τ g π ( u ) = τ g ( u π ) = ( τ g ) π ( u ) \tau_{g^{\pi}}(u)=\tau_g(u^{\pi})=(\tau_g)^{\pi}(u) τ g π ( u ) = τ g ( u π ) = ( τ g ) π ( u ) . □
Theorem 4.12. There exists a minion homomorphism from Pol ( Eqn ∗ ( Z 5 ) , NAE 3 ) \operatorname{Pol}(\operatorname{Eqn}^{*}(\mathbb{Z}_5),\operatorname{NAE}_3) Pol ( Eqn ∗ ( Z 5 ) , NAE 3 ) to Pol ( D ^ 4 , NAE 2 ) \operatorname{Pol}(\widehat{D}_4,\operatorname{NAE}_2) Pol ( D 4 , NAE 2 ) .
Proof. Let σ ∈ S 3 \sigma\in S_3 σ ∈ S 3 be the permutation sending 3 ↦ 2 ↦ 1 ↦ 3 3\mapsto2\mapsto1\mapsto3 3 ↦ 2 ↦ 1 ↦ 3 . For g ∈ Pol ( Eqn ∗ ( Z 5 ) , NAE 3 ) g\in\operatorname{Pol}(\operatorname{Eqn}^{*}(\mathbb{Z}_5),\operatorname{NAE}_3) g ∈ Pol ( Eqn ∗ ( Z 5 ) , NAE 3 ) , let g ~ = σ g ( 0 , … , 0 ) ∘ g \widetilde{g}=\sigma^{g(0,\ldots,0)}\circ g g = σ g ( 0 , … , 0 ) ∘ g . Note that (since σ \sigma σ is an automorphism of NAE 3 \operatorname{NAE}_3 NAE 3 ) g ~ ∈ Pol ( Eqn ∗ ( Z 5 ) , NAE 3 ) \widetilde{g}\in\operatorname{Pol}(\operatorname{Eqn}^{*}(\mathbb{Z}_5),\operatorname{NAE}_3) g ∈ Pol ( Eqn ∗ ( Z 5 ) , NAE 3 ) . Also, since σ 1 ( 1 ) = σ 2 ( 2 ) = σ 3 ( 3 ) = 3 \sigma^1(1)=\sigma^2(2)=\sigma^3(3)=3 σ 1 ( 1 ) = σ 2 ( 2 ) = σ 3 ( 3 ) = 3 , we have g ~ ( 0 , … , 0 ) = 3 \widetilde{g}(0,\ldots,0)=3 g ( 0 , … , 0 ) = 3 . Now let μ \mu μ be the map on Pol ( Eqn ∗ ( Z 5 ) , NAE 3 ) \operatorname{Pol}(\operatorname{Eqn}^{*}(\mathbb{Z}_5),\operatorname{NAE}_3) Pol ( Eqn ∗ ( Z 5 ) , NAE 3 ) given by μ ( g ) ≔ τ g ~ \mu(g)\coloneqq\tau_{\widetilde{g}} μ ( g ) : = τ g . By Proposition 4.10 , μ : Pol ( Eqn ∗ ( Z 5 ) , NAE 3 ) → Pol ( D ^ 4 , NAE 2 ) \mu:\operatorname{Pol}(\operatorname{Eqn}^{*}(\mathbb{Z}_5),\operatorname{NAE}_3)\to\operatorname{Pol}(\widehat{D}_4,\operatorname{NAE}_2) μ : Pol ( Eqn ∗ ( Z 5 ) , NAE 3 ) → Pol ( D 4 , NAE 2 ) . It remains to show that μ \mu μ preserves minors. Using Proposition 4.11 , it is enough to show g ↦ g ~ g\mapsto\widetilde{g} g ↦ g preserves minors.
g ~ π = σ g π ( 0 , … , 0 ) ∘ g π = σ g ( 0 , … , 0 ) ∘ g π = ( σ g ( 0 , … , 0 ) ∘ g ) π = g ~ π . \widetilde{g}^{\pi}=\sigma^{g^{\pi}(0,\ldots,0)}\circ g^{\pi}=\sigma^{g(0,\ldots,0)}\circ g^{\pi}=(\sigma^{g(0,\ldots,0)}\circ g)^{\pi}=\widetilde{g}^{\pi}. g π = σ g π ( 0 , … , 0 ) ∘ g π = σ g ( 0 , … , 0 ) ∘ g π = ( σ g ( 0 , … , 0 ) ∘ g ) π = g π .
Here the second equality is because g π ( 0 , … , 0 ) = g ( 0 , … , 0 ) g^{\pi}(0,\ldots,0)=g(0,\ldots,0) g π ( 0 , … , 0 ) = g ( 0 , … , 0 ) and the third equality is because automorphisms commute with minors. □
Theorem 4.13. PCSP ( Eqn ∗ ( Z 5 ) , NAE 3 ) \operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_5),\operatorname{NAE}_3) PCSP ( Eqn ∗ ( Z 5 ) , NAE 3 ) is NP-hard.
Proof. Theorem 4.12 provides a minion homomorphism which, by Theorem 4.3, gives a log-space reduction from PCSP ( D ^ 4 , NAE 2 ) \operatorname{PCSP}(\widehat{D}_4,\operatorname{NAE}_2) PCSP ( D 4 , NAE 2 ) to PCSP ( Eqn ∗ ( Z 5 ) , NAE 3 ) \operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_5),\operatorname{NAE}_3) PCSP ( Eqn ∗ ( Z 5 ) , NAE 3 ) . By Corollary 4.7 , PCSP ( D ^ 4 , NAE 2 ) \operatorname{PCSP}(\widehat{D}_4,\operatorname{NAE}_2) PCSP ( D 4 , NAE 2 ) is NP-hard, hence so is PCSP ( Eqn ∗ ( Z 5 ) , NAE 3 ) \operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_5),\operatorname{NAE}_3) PCSP ( Eqn ∗ ( Z 5 ) , NAE 3 ) . □
Hardness for p ≥ 7 p \ge7 p ≥ 7
Now, we will show NP-hardness of PCSP ( Eqn ∗ ( Z p ) , NAE 3 ) \operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_3) PCSP ( Eqn ∗ ( Z p ) , NAE 3 ) for all primes p ≥ 7 p\ge7 p ≥ 7 . First we must recall a few more standard notions from the algebraic approach to PCSPs [BBKO21].
Definition 4.14. Let M M M be a minion. The free structure of M M M generated by 1-in-3 is the relation F M ( 1 -in- 3 ) F_M(1\text{-in-}3) F M ( 1 -in- 3 ) defined as the set of all triples ( f 1 , f 2 , f 3 ) (f_1,f_2,f_3) ( f 1 , f 2 , f 3 ) of functions in M ( 2 ) M^{(2)} M ( 2 ) for which there exists some g ∈ M ( 3 ) g\in M^{(3)} g ∈ M ( 3 ) such that the following identities hold for all x , y x,y x , y in the domain of the f i f_i f i ’s:
f 1 ( x , y ) = g ( x , y , y ) , f 2 ( x , y ) = g ( y , x , y ) , f 3 ( x , y ) = g ( y , y , x ) . f_1(x,y)=g(x,y,y),\qquad f_2(x,y)=g(y,x,y),\qquad f_3(x,y)=g(y,y,x). f 1 ( x , y ) = g ( x , y , y ) , f 2 ( x , y ) = g ( y , x , y ) , f 3 ( x , y ) = g ( y , y , x ) .
Theorem 4.15 (Special case of Lemma 4.4 in [BBKO21]). Let M M M be a minion. If F M ( 1 -in- 3 ) → 1 -in- 3 F_M(1\text{-in-}3)\to1\text{-in-}3 F M ( 1 -in- 3 ) → 1 -in- 3 , then there exists a minion homomorphism from M M M to Pol ( 1 -in- 3 , 1 -in- 3 ) \operatorname{Pol}(1\text{-in-}3,1\text{-in-}3) Pol ( 1 -in- 3 , 1 -in- 3 ) .
Definition 4.16. For relations R R R , Q Q Q and S ⊆ dom ( R ) S\subseteq\operatorname{dom}(R) S ⊆ dom ( R ) , define Pol ( R , Q ) ∣ S \operatorname{Pol}(R,Q)|_S Pol ( R , Q ) ∣ S by
Pol ( R , Q ) ∣ S = ⋃ n { f ∣ S n ∣ f ∈ Pol ( n ) ( R , Q ) } . \operatorname{Pol}(R,Q)|_S=\bigcup_n\{f|_S^n\mid f\in\operatorname{Pol}^{(n)}(R,Q)\}. Pol ( R , Q ) ∣ S = n ⋃ { f ∣ S n ∣ f ∈ Pol ( n ) ( R , Q )} .
Observation 4.17. For any S ⊆ dom ( R ) S\subseteq\operatorname{dom}(R) S ⊆ dom ( R ) , restriction defines a minion homomorphism Pol ( R , Q ) → Pol ( R , Q ) ∣ S \operatorname{Pol}(R,Q)\to\operatorname{Pol}(R,Q)|_S Pol ( R , Q ) → Pol ( R , Q ) ∣ S .
Theorem 4.18. For p ≥ 7 p\ge7 p ≥ 7 prime, every function in Pol ( 2 ) ( Eqn ∗ ( Z p ) , NAE 3 ) ∣ Z p ∗ \operatorname{Pol}^{(2)}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_3)|_{\mathbb{Z}_p^{*}} Pol ( 2 ) ( Eqn ∗ ( Z p ) , NAE 3 ) ∣ Z p ∗ is nonconstant and essentially unary.
We prove Theorem 4.18 in Appendix § 9 , using a proof obtained with GPT-5.6 Sol (cf. AI methodology).
Theorem 4.19. For p ≥ 7 p\ge7 p ≥ 7 prime, PCSP ( Eqn ∗ ( Z p ) , NAE 3 ) \operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_3) PCSP ( Eqn ∗ ( Z p ) , NAE 3 ) is NP-hard.
Proof. Let M = Pol ( Eqn ∗ ( Z p ) , NAE 3 ) ∣ Z p ∗ M=\operatorname{Pol}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_3)|_{\mathbb{Z}_p^{*}} M = Pol ( Eqn ∗ ( Z p ) , NAE 3 ) ∣ Z p ∗ . We show F M ( 1 -in- 3 ) → 1 -in- 3 F_M(1\text{-in-}3)\to1\text{-in-}3 F M ( 1 -in- 3 ) → 1 -in- 3 . Define the map α : M ( 2 ) → { 0 , 1 } \alpha:M^{(2)}\to\{0,1\} α : M ( 2 ) → { 0 , 1 } as follows:
α ( f ) = { 1 , if the first coordinate is essential in f , 0 , if the second coordinate is essential in f . \alpha(f)=
\begin{cases}
1, & \text{if the first coordinate is essential in }f,\\
0, & \text{if the second coordinate is essential in }f.
\end{cases} α ( f ) = { 1 , 0 , if the first coordinate is essential in f , if the second coordinate is essential in f .
This map is well defined by Theorem 4.18 . Now, we must show that α \alpha α is a homomorphism from F M ( 1 -in- 3 ) F_M(1\text{-in-}3) F M ( 1 -in- 3 ) to 1 -in- 3 1\text{-in-}3 1 -in- 3 . ( f 1 , f 2 , f 3 ) ∈ F M ( 1 -in- 3 ) (f_1,f_2,f_3) \in F_M(1\text{-in-}3) ( f 1 , f 2 , f 3 ) ∈ F M ( 1 -in- 3 ) means ∃ g ∈ M ( 3 ) \exists g \in\mathcal{M}^{(3)} ∃ g ∈ M ( 3 ) such that
f 1 ( x , y ) = g ( x , y , y ) , f 2 ( x , y ) = g ( y , x , y ) , f 3 ( x , y ) = g ( y , y , x ) . f_1(x,y)=g(x,y,y), \qquad f_2(x,y)=g(y,x,y), \qquad f_3(x,y)=g(y,y,x). f 1 ( x , y ) = g ( x , y , y ) , f 2 ( x , y ) = g ( y , x , y ) , f 3 ( x , y ) = g ( y , y , x ) .
Write h ( x ) = g ( x , x , x ) h(x)=g(x,x,x) h ( x ) = g ( x , x , x ) . Each of these f i f_i f i 's is essentially unary by assumption, so for each i i i either f i ( x , y ) = h ( x ) f_i(x,y)=h(x) f i ( x , y ) = h ( x ) (and α ( f i ) = 1 \alpha(f_i)=1 α ( f i ) = 1 ) or f i ( x , y ) = h ( y ) f_i(x,y)=h(y) f i ( x , y ) = h ( y ) (and α ( f i ) = 0 \alpha(f_i)=0 α ( f i ) = 0 ). We prove that exactly one of the f i f_i f i 's has α ( f i ) = 1 \alpha(f_i)=1 α ( f i ) = 1 . If α ( f 1 ) = α ( f 2 ) = α ( f 3 ) \alpha(f_1)=\alpha(f_2)=\alpha(f_3) α ( f 1 ) = α ( f 2 ) = α ( f 3 ) , we derive a contradiction by considering where g g g maps the (rows of the) following tableau:
( − 2 1 1 1 − 2 1 1 1 − 2 ) \begin{pmatrix}
-2 & 1 & 1 \\
1 & -2 & 1 \\
1 & 1 & -2
\end{pmatrix} − 2 1 1 1 − 2 1 1 1 − 2
If exactly two of α ( f 1 ) , α ( f 2 ) , α ( f 3 ) \alpha(f_1),\alpha(f_2),\alpha(f_3) α ( f 1 ) , α ( f 2 ) , α ( f 3 ) equal 1 1 1 , then by symmetry we may assume that α ( f 1 ) = α ( f 2 ) = 1 \alpha(f_1)=\alpha(f_2)=1 α ( f 1 ) = α ( f 2 ) = 1 , α ( f 3 ) = 0 \alpha(f_3)=0 α ( f 3 ) = 0 . We derive a contradiction by considering where g g g maps the following tableau:
( 1 − 2 − 2 − 2 1 − 2 1 1 4 ) \begin{pmatrix}
1 & -2 & -2 \\
-2 & 1 & -2 \\
1 & 1 & 4
\end{pmatrix} 1 − 2 1 − 2 1 1 − 2 − 2 4
Thus, exactly one binary polymorphism in each tuple of F M ( 1 -in- 3 ) F_M(1\text{-in-}3) F M ( 1 -in- 3 ) gets assigned the value 1 1 1 by α \alpha α , which means that α \alpha α is a homomorphism from F M ( 1 -in- 3 ) F_M(1\text{-in-}3) F M ( 1 -in- 3 ) to 1 -in- 3 1\text{-in-}3 1 -in- 3 .
Thus, combining Theorem 4.15 , Observation 4.17, and Theorem 4.3 gives a reduction from CSP ( 1 -in- 3 ) \operatorname{CSP}(1\text{-in-}3) CSP ( 1 -in- 3 ) to PCSP ( Eqn ∗ ( Z p ) , NAE 3 ) \operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_3) PCSP ( Eqn ∗ ( Z p ) , NAE 3 ) , proving NP-hardness. □
Abelian embeddings
We prove the two lemmas about Abelian embeddings from the preliminaries.
Lemma 2.3. Let R R R be a ternary symmetric and connected relation, and let G G G be an Abelian group. Then R R R admits an Abelian embedding to G G G if and only if there exist C ∈ G C \in G C ∈ G and a nonconstant homomorphism q : R → Eqn C ( G ) q:R \to\operatorname{Eqn}_C(G) q : R → Eqn C ( G ) .
Proof. Let A = dom ( R ) A=\operatorname{dom}(R) A = dom ( R ) . Suppose first that f 1 , f 2 , f 3 f_1,f_2,f_3 f 1 , f 2 , f 3 witness an Abelian embedding. If x x x and y y y are adjacent in the primal graph, symmetry lets us choose z z z so that both ( x , y , z ) (x,y,z) ( x , y , z ) and ( y , x , z ) (y,x,z) ( y , x , z ) belong to R R R . Subtracting the two corresponding equations gives
f 1 ( x ) − f 2 ( x ) = f 1 ( y ) − f 2 ( y ) . f_1(x)-f_2(x)=f_1(y)-f_2(y). f 1 ( x ) − f 2 ( x ) = f 1 ( y ) − f 2 ( y ) .
Thus f 1 − f 2 f_1-f_2 f 1 − f 2 is constant on every connected component of the primal graph, and hence on all of A = dom ( R ) A=\operatorname{dom}(R) A = dom ( R ) . The same argument, after permuting coordinates, shows that f 1 − f 3 f_1-f_3 f 1 − f 3 is constant. Consequently there are constants a 1 , a 2 , a 3 ∈ G a_1,a_2,a_3 \in G a 1 , a 2 , a 3 ∈ G and a map q : A → G q:A \to G q : A → G such that
f i = q + a i ( i ∈ [ 3 ] ) . f_i=q+a_i \qquad(i \in[3]). f i = q + a i ( i ∈ [ 3 ]) .
At least one f i f_i f i is nonconstant, so q q q is nonconstant. For every ( x , y , z ) ∈ R (x,y,z) \in R ( x , y , z ) ∈ R we now have
q ( x ) + q ( y ) + q ( z ) = − ( a 1 + a 2 + a 3 ) . q(x)+q(y)+q(z)=-(a_1+a_2+a_3). q ( x ) + q ( y ) + q ( z ) = − ( a 1 + a 2 + a 3 ) .
Taking C = − ( a 1 + a 2 + a 3 ) C=-(a_1+a_2+a_3) C = − ( a 1 + a 2 + a 3 ) proves the second condition.
Conversely, suppose that q ( x ) + q ( y ) + q ( z ) = C q(x)+q(y)+q(z)=C q ( x ) + q ( y ) + q ( z ) = C on R R R . Set
f 1 = q − C , f 2 = q , f 3 = q . f_1=q-C, \qquad f_2=q, \qquad f_3=q. f 1 = q − C , f 2 = q , f 3 = q .
These maps are nonconstant and their coordinate-wise sum is zero on every tuple of R R R . □
Lemma 2.2. Let A A A be a finite set, r ≥ 1 r \ge1 r ≥ 1 , and ∅ ≠ R ⊆ A r \varnothing\ne R \subseteq A^r ∅ = R ⊆ A r . If R R R admits an Abelian embedding, then it admits one to some G ∈ { Z } ∪ { Z p ∣ p prime } G \in\{\mathbb{Z}\} \cup\{\mathbb{Z}_p \mid p\ \text{prime}\} G ∈ { Z } ∪ { Z p ∣ p prime } .
Proof of Lemma 2.2. Let f 1 , … , f r : A → Γ f_1,\ldots,f_r:A\to\Gamma f 1 , … , f r : A → Γ witness an Abelian embedding to an Abelian group Γ \Gamma Γ .
Fix a 0 ∈ A a_0 \in A a 0 ∈ A , put
g i ( a ) = f i ( a ) − f i ( a 0 ) , g_i(a)=f_i(a)-f_i(a_0), g i ( a ) = f i ( a ) − f i ( a 0 ) ,
and let H ≤ Γ H \le\Gamma H ≤ Γ be the subgroup generated by all g i ( a ) g_i(a) g i ( a ) , for i ∈ [ r ] i \in[r] i ∈ [ r ] and a ∈ A a \in A a ∈ A . The group H H H is finitely generated and nontrivial: the former follows from finiteness of A A A , and the latter from nonconstancy of at least one f i f_i f i . Moreover, if
C = − ∑ i = 1 r f i ( a 0 ) , C=-\sum_{i=1}^{r}f_i(a_0), C = − i = 1 ∑ r f i ( a 0 ) ,
then every ( x 1 , … , x r ) ∈ R (x_1,\ldots,x_r)\in R ( x 1 , … , x r ) ∈ R satisfies
∑ i = 1 r g i ( x i ) = C . \sum_{i=1}^{r}g_i(x_i)=C. i = 1 ∑ r g i ( x i ) = C .
In particular, C ∈ H C\in H C ∈ H .
By the structure theorem for finitely generated Abelian groups, there is a nonconstant homomorphism φ : H → G \varphi:H\to G φ : H → G , where G = Z G=\mathbb{Z} G = Z if H H H is infinite, and G = Z p G=\mathbb{Z}_p G = Z p for some prime p p p if H H H is finite. Since the elements g i ( a ) g_i(a) g i ( a ) generate H H H and g i ( a 0 ) = 0 g_i(a_0)=0 g i ( a 0 ) = 0 , at least one map φ ∘ g i \varphi\circ g_i φ ∘ g i is nonconstant. Define
f 1 ′ ( a ) = φ ( g 1 ( a ) ) − φ ( C ) , f i ′ ( a ) = φ ( g i ( a ) ) ( 2 ≤ i ≤ r ) . f'_1(a)=\varphi(g_1(a))-\varphi(C),\qquad f'_i(a)=\varphi(g_i(a))\quad(2\le i\le r). f 1 ′ ( a ) = φ ( g 1 ( a )) − φ ( C ) , f i ′ ( a ) = φ ( g i ( a )) ( 2 ≤ i ≤ r ) .
Again, at least one map f i ′ f'_i f i ′ is nonconstant. For every tuple ( x 1 , … , x r ) ∈ R (x_1,\ldots,x_r)\in R ( x 1 , … , x r ) ∈ R ,
∑ i = 1 r f i ′ ( x i ) = φ ( ∑ i = 1 r g i ( x i ) − C ) = 0. \sum_{i=1}^{r}f'_i(x_i)=\varphi\left(\sum_{i=1}^{r}g_i(x_i)-C\right)=0. i = 1 ∑ r f i ′ ( x i ) = φ ( i = 1 ∑ r g i ( x i ) − C ) = 0.
Hence these maps give an Abelian embedding to G G G . □
Proof of main reduction
Theorem 3.3. Let R R R be a finite relation, and c ≥ 2 c\ge2 c ≥ 2 . Suppose there exist a finitely generated Abelian group G G G as well as a homomorphism q q q from R R R to Eqn ( G ) \operatorname{Eqn}(G) Eqn ( G ) , and a c c c -rounding χ \chi χ for G G G . Then, Decision-PCSP( R , NAE c ) (R,\operatorname{NAE}_c) ( R , NAE c ) reduces to Decision-PCSP( R ∣ q − 1 ( 0 ) , NAE c ) (R|_{q^{-1}(0)},\operatorname{NAE}_c) ( R ∣ q − 1 ( 0 ) , NAE c ) in polynomial time. Furthermore, if χ \chi χ is efficient, then Search-PCSP( R , NAE c ) (R,\operatorname{NAE}_c) ( R , NAE c ) reduces to Search-PCSP( R ∣ q − 1 ( 0 ) , NAE c ) (R|_{q^{-1}(0)},\operatorname{NAE}_c) ( R ∣ q − 1 ( 0 ) , NAE c ) in polynomial time.
Proof. Let us start with the reduction for Search-PCSP. Fix an efficient c c c -rounding χ \chi χ for G G G , and write D = q ( dom ( R ) ) D=q(\operatorname{dom}(R)) D = q ( dom ( R )) and R 0 = R ∣ q − 1 ( 0 ) R_0=R|_{q^{-1}(0)} R 0 = R ∣ q − 1 ( 0 ) .
Let I I I be an instance of Search-PCSP( R , NAE c ) (R,\operatorname{NAE}_c) ( R , NAE c ) , and fix an R R R -solution h h h of I I I for the analysis (the algorithm does not need access to h h h ). We construct a decreasing sequence V 0 ⊇ V 1 ⊇ ⋯ V_0\supseteq V_1\supseteq\cdots V 0 ⊇ V 1 ⊇ ⋯ of sets of active variables, starting with V 0 = V ( I ) V_0=V(I) V 0 = V ( I ) , together with a partial colouring γ : V ( I ) ∖ V i → [ c ] \gamma:V(I)\setminus V_i\to[c] γ : V ( I ) ∖ V i → [ c ] . At stage i i i , the active instance is the induced instance I i = I [ V i ] I_i=I[V_i] I i = I [ V i ] . Notice that h ∣ V i h|_{V_i} h ∣ V i is an R R R -solution of I i I_i I i .
For every x ∈ V i x\in V_i x ∈ V i and every a ∈ D ∖ { 0 } a\in D\setminus\{0\} a ∈ D ∖ { 0 } , we test whether I i I_i I i has an Eqn ( G ) \operatorname{Eqn}(G) Eqn ( G ) -solution s i s_i s i satisfying s i ( x ) = a s_i(x)=a s i ( x ) = a . If such a solution is found, let P i = { x ∈ V i ∣ s i ( x ) ≠ 0 } P_i=\{x\in V_i\mid s_i(x)\ne0\} P i = { x ∈ V i ∣ s i ( x ) = 0 } be its nonzero support, and set V i + 1 = V i ∖ P i = s i − 1 ( 0 ) V_{i+1}=V_i\setminus P_i=s_i^{-1}(0) V i + 1 = V i ∖ P i = s i − 1 ( 0 ) . For each x ∈ P i x\in P_i x ∈ P i , extend the partial colouring by setting γ ( x ) = χ ( s i ( x ) ) \gamma(x)=\chi(s_i(x)) γ ( x ) = χ ( s i ( x )) .
We claim that every constraint removed at this stage is already satisfied by γ \gamma γ . Indeed, let ( x , y , z ) (x,y,z) ( x , y , z ) be a constraint of I i I_i I i which is not a constraint of I i + 1 I_{i+1} I i + 1 . Since s i s_i s i is an Eqn ( G ) \operatorname{Eqn}(G) Eqn ( G ) -solution, s i ( x ) + s i ( y ) + s i ( z ) = 0 s_i(x)+s_i(y)+s_i(z)=0 s i ( x ) + s i ( y ) + s i ( z ) = 0 . Moreover, at least one of x , y , z x,y,z x , y , z belongs to P i P_i P i , so these three values are not all zero. The defining property of χ \chi χ therefore implies that the nonzero values among them receive at least two different colours. All variables carrying these nonzero values belong to P i P_i P i , and hence their colours have just been fixed by γ \gamma γ . Thus ( x , y , z ) (x,y,z) ( x , y , z ) is nonmonochromatic, independently of how the remaining variables are coloured later. Since P i P_i P i is nonempty, every successful stage strictly decreases the number of active variables. The process therefore reaches, after at most ∣ V ( I ) ∣ |V(I)| ∣ V ( I ) ∣ stages, an active set V t V_t V t for which none of the tests above succeeds. We output the residual instance I ′ = I [ V t ] I' = I[V_t] I ′ = I [ V t ] . This is a valid instance of Search-PCSP( R 0 , NAE c ) (R_0,\operatorname{NAE}_c) ( R 0 , NAE c ) . To see this, consider the R R R -solution h ∣ V t h|_{V_t} h ∣ V t of I ′ I' I ′ . The composition q ∘ h ∣ V t q \circ h|_{V_t} q ∘ h ∣ V t is an Eqn( G ) (G) ( G ) -solution of I ′ I' I ′ taking values in D D D . If q ( h ( x ) ) ≠ 0 q(h(x)) \ne0 q ( h ( x )) = 0 for some x ∈ V t x \in V_t x ∈ V t , then the test for the pair ( x , q ( h ( x ) ) ) (x,q(h(x))) ( x , q ( h ( x ))) would have succeeded. Consequently q ( h ( x ) ) = 0 q(h(x)) = 0 q ( h ( x )) = 0 for every x ∈ V t x \in V_t x ∈ V t , and hence h ∣ V t h|_{V_t} h ∣ V t is an R 0 R_0 R 0 -solution of I ′ I' I ′ .
Given any NAE c \operatorname{NAE}_c NAE c -solution γ ′ \gamma' γ ′ of I ′ I' I ′ , extend the partial colouring γ \gamma γ by setting γ ∣ V t = γ ′ \gamma|_{V_t} = \gamma' γ ∣ V t = γ ′ . Every constraint of I ′ I' I ′ is satisfied by γ ′ \gamma' γ ′ , while every other constraint was already made nonmonochromatic at the stage when it was removed. Therefore γ \gamma γ is an NAE c \operatorname{NAE}_c NAE c -solution of I I I .
Finally, all steps run in polynomial time. Since G G G is a fixed finitely generated Abelian group, systems of linear equations over G G G can be solved in polynomial time. At each of at most ∣ V ( I ) ∣ |V(I)| ∣ V ( I ) ∣ stages, we solve one such system for every pair ( x , a ) ∈ V i × ( D ∖ { 0 } ) (x,a) \in V_i \times(D \setminus\{0\}) ( x , a ) ∈ V i × ( D ∖ { 0 }) . The set D D D is fixed and finite, and χ \chi χ is polynomial-time computable by assumption. The construction of I ′ I' I ′ and the lifting of γ ′ \gamma' γ ′ are therefore both polynomial-time.
For the decision reduction, the residual instance I ′ I' I ′ is computed using only the solutions to the group equations and their zero supports; the algorithm does not evaluate χ \chi χ . If I I I has an R R R -solution, the argument above shows that I ′ I' I ′ has an R 0 R_0 R 0 -solution. Conversely, if I ′ I' I ′ has an NAE c \operatorname{NAE}_c NAE c -solution, then this solution extends existentially, using the fixed rounding χ \chi χ , to an NAE c \operatorname{NAE}_c NAE c -solution of I I I . Thus No instances are preserved, even when χ \chi χ is not efficiently computable. □
Comparison with known algorithms
Failure of k-consistency and BLP+AIP for approximating detrivialised equations
An m m m -ary polymorphism f f f is a weak near-unanimity (WNU) polymorphism if
f ( y , x , … , x ) = f ( x , y , x , … , x ) = ⋯ = f ( x , … , x , y ) f(y,x,\ldots,x) = f(x,y,x,\ldots,x) = \cdots= f(x,\ldots,x,y) f ( y , x , … , x ) = f ( x , y , x , … , x ) = ⋯ = f ( x , … , x , y )
for all x , y x,y x , y in the left-hand domain. Atserias and Dalmau proved that the following condition is necessary even for sublinear width.
Theorem C.1 ([AD22, Corollary 2]). Let ( R , Q ) (R,Q) ( R , Q ) be a PCSP template. If PCSP( R , Q ) (R,Q) ( R , Q ) is solvable by a consistency algorithm of bounded or sublinear width, then Pol ( R , Q ) \operatorname{Pol}(R,Q) Pol ( R , Q ) contains an m m m -ary WNU polymorphism for every m ≥ 3 m \ge3 m ≥ 3 .
Proposition C.2. For every prime p ≠ 3 p \ne3 p = 3 and every c c c for which the template is defined, PCSP( Eqn ∗ ( Z p ) , NAE c ) (\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_c) ( Eqn ∗ ( Z p ) , NAE c ) is not solvable by k k k -consistency for any fixed k k k .
Proof. It suffices to rule out a ternary WNU polymorphism. Suppose that f ∈ Pol ( 3 ) ( Eqn ∗ ( Z p ) , NAE c ) f \in\operatorname{Pol}^{(3)}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_c) f ∈ Pol ( 3 ) ( Eqn ∗ ( Z p ) , NAE c ) were WNU. Since p ≠ 3 p \ne3 p = 3 , we have 1 ≠ − 2 1 \ne-2 1 = − 2 , and each column of
( − 2 1 1 1 − 2 1 1 1 − 2 ) \begin{pmatrix}
-2 & 1 & 1 \\
1 & -2 & 1 \\
1 & 1 & -2
\end{pmatrix} − 2 1 1 1 − 2 1 1 1 − 2
is a permutation of the nonconstant zero-sum tuple ( − 2 , 1 , 1 ) (-2,1,1) ( − 2 , 1 , 1 ) and hence belongs to Eqn ∗ ( Z p ) \operatorname{Eqn}^{*}(\mathbb{Z}_p) Eqn ∗ ( Z p ) . The polymorphism property says that the tuple obtained by applying f f f to the rows belongs to NAE c \operatorname{NAE}_c NAE c . But the WNU identities make its three entries f ( − 2 , 1 , 1 ) f(-2,1,1) f ( − 2 , 1 , 1 ) , f ( 1 , − 2 , 1 ) f(1,-2,1) f ( 1 , − 2 , 1 ) , f ( 1 , 1 , − 2 ) f(1,1,-2) f ( 1 , 1 , − 2 ) equal, a contradiction. Thus no ternary WNU polymorphism exists, so Theorem C.1 rules out bounded-width, equivalently fixed k k k -consistency, algorithms. □
We say that a polymorphism of arity 2 k + 1 2k+1 2 k + 1 is block symmetric if its outputs are invariant under permutations of its first k k k inputs and of its last k + 1 k+1 k + 1 inputs. We recall the following classical result.
Theorem C.3 ([BGWZ20]). PCSP ( R , Q ) \operatorname{PCSP}(R,Q) PCSP ( R , Q ) is solved by BLP+AIP \operatorname{BLP+AIP} BLP+AIP if and only if Pol ( R , Q ) \operatorname{Pol}(R,Q) Pol ( R , Q ) contains a block-symmetric polymorphism of arity 2 k + 1 2k+1 2 k + 1 for every k ≥ 1 k \ge1 k ≥ 1 .
Proposition C.4. For every prime p ≥ 5 p \ge5 p ≥ 5 , PCSP ( Eqn ∗ ( Z p ) , NAE c ) \operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_{p}),\operatorname{NAE}_{c}) PCSP ( Eqn ∗ ( Z p ) , NAE c ) is not solved by BLP+AIP \operatorname{BLP+AIP} BLP+AIP , for every c c c for which the template is defined.
Proof. Suppose that f f f is a block-symmetric polymorphism for k = 5 k=5 k = 5 , so that its two blocks have sizes 5 and 6. Consider the following three inputs to f f f , where the vertical line separates the two blocks:
( 1 2 − 1 0 − 1 2 1 ∣ 1 1 − 2 1 1 − 2 1 2 0 − 1 2 1 − 1 ∣ 1 − 2 1 1 − 2 1 − 1 1 1 2 − 1 2 0 ∣ − 2 1 1 − 2 1 1 ) \begin{pmatrix}
\frac{1}{2} & -1 & 0 & -\frac{1}{2} & 1 & \mid& 1 & 1 & -2 & 1 & 1 & -2 \\
\frac{1}{2} & 0 & -\frac{1}{2} & 1 & -1 & \mid& 1 & -2 & 1 & 1 & -2 & 1 \\
-1 & 1 & \frac{1}{2} & -\frac{1}{2} & 0 & \mid& -2 & 1 & 1 & -2 & 1 & 1
\end{pmatrix} 2 1 2 1 − 1 − 1 0 1 0 − 2 1 2 1 − 2 1 1 − 2 1 1 − 1 0 ∣ ∣ ∣ 1 1 − 2 1 − 2 1 − 2 1 1 1 1 − 2 1 − 2 1 − 2 1 1
Every column is a nonconstant zero-sum tuple, hence belongs to Eqn ∗ ( Z p ) \operatorname{Eqn}^{*}(\mathbb{Z}_{p}) Eqn ∗ ( Z p ) . Within each block, the three rows are permutations of one another. Thus block symmetry makes their three images under f f f equal, contradicting preservation of NAE c \operatorname{NAE}_{c} NAE c .
Consequently there is no block-symmetric polymorphism for k = 5 k=5 k = 5 , and the result follows from Theorem C.3 .
Implementing the reduction with SinglAIP or CSinglAIP
We begin by recalling AIP and the two singleton variants of AIP studied recently by Zhuk [35 ] . View a finite-domain CSP instance I I I as having a current domain D x D_x D x for every variable x x x and a current relation R C R_C R C for every constraint C ∈ C ( I ) C \in\mathcal{C}(I) C ∈ C ( I ) . For a ∈ D x a \in D_x a ∈ D x , let I [ x = a ] I[x=a] I [ x = a ] denote the instance obtained by replacing D x D_x D x with { a } \{a\} { a } and deleting all incompatible tuples from every constraint containing x x x . For a constraint C = R C ( x 1 , … , x r ) C=R_C(x_1,\ldots,x_r) C = R C ( x 1 , … , x r ) and a tuple a ˉ ∈ R C \bar{a} \in R_C a ˉ ∈ R C , let I [ C = a ˉ ] I[C=\bar{a}] I [ C = a ˉ ] denote the instance obtained by replacing the relation of this particular constraint with { a ˉ } \{\bar{a}\} { a ˉ } .
Definition C.5 (Affine Integer Programming). The AIP relaxation of I I I has integer variables λ x ( a ) \lambda_x(a) λ x ( a ) for x ∈ V ( I ) x \in V(I) x ∈ V ( I ) and a ∈ D x a \in D_x a ∈ D x , and λ C ( a ˉ ) \lambda_C(\bar{a}) λ C ( a ˉ ) for every constraint C C C and a ˉ ∈ R C \bar{a} \in R_C a ˉ ∈ R C . They satisfy
∑ a ∈ D x λ x ( a ) = 1 , ∑ a ˉ ∈ R C λ C ( a ˉ ) = 1 , \sum_{a \in D_x} \lambda_x(a)=1,\qquad\sum_{\bar{a} \in R_C} \lambda_C(\bar{a})=1, a ∈ D x ∑ λ x ( a ) = 1 , a ˉ ∈ R C ∑ λ C ( a ˉ ) = 1 , together with the marginal equations
λ x i ( a ) = ∑ b ˉ ∈ R C b i = a λ C ( b ˉ ) \lambda_{x_i}(a)=\sum_{\substack{\bar{b} \in R_C\\b_i=a}}\lambda_C(\bar{b}) λ x i ( a ) = b ˉ ∈ R C b i = a ∑ λ C ( b ˉ ) for every C = R C ( x 1 , … , x r ) C=R_C(x_1,\ldots,x_r) C = R C ( x 1 , … , x r ) , i ∈ [ r ] i \in[r] i ∈ [ r ] , and a ∈ D x i a \in D_{x_i} a ∈ D x i . There are no nonnegativity constraints. AIP accepts I I I if this system has an integer solution, and rejects it otherwise.
Definition C.6 (SinglAIP and CSinglAIP). Both algorithms repeatedly prune the instance until reaching a fixed point.
If no further deletion is possible, the corresponding algorithm accepts and returns the resulting reduced instance.
Both algorithms are sound: a value, respectively a constraint tuple, used by a genuine solution can never be deleted.
The reduction in Theorem 3.3 repeatedly solves systems of equations and rounds one solution at a time. We next show that the same reduction can be expressed as one run of either Singleton AIP (SinglAIP) or Constraint Singleton AIP (CSinglAIP).
Proof of Theorem 3.3 using CSinglAIP. Fix an efficient c c c -rounding χ \chi χ for G G G , and write R 0 = R ∣ q − 1 ( 0 ) R_0=R|_{q^{-1}(0)} R 0 = R ∣ q − 1 ( 0 ) . Let I I I be an instance of Search-PCSP( R , NAE c ) (R,\operatorname{NAE}_c) ( R , NAE c ) , and fix an R R R -solution h h h of I I I for the analysis (the algorithm does not need access to h h h ). Colour variables that occur in no constraint arbitrarily, so we may assume that every variable occurs in a constraint. Run CSinglAIP on I I I to a fixed point, obtaining an instance I ⋆ I^\star I ⋆ with nonempty surviving constraint relations R C ⋆ R_C^\star R C ⋆ .
Define the set of surviving constraint-tuple pairs
Ω = { ( C , a ˉ ) ∣ C ∈ C ( I ) , a ˉ ∈ R C ⋆ } . \Omega=\{(C,\bar{a})\mid C\in C(I),\ \bar{a}\in R_C^\star\}. Ω = {( C , a ˉ ) ∣ C ∈ C ( I ) , a ˉ ∈ R C ⋆ } .
For each ( C , a ˉ ) ∈ Ω (C,\bar{a})\in\Omega ( C , a ˉ ) ∈ Ω , choose an AIP solution λ [ C = a ˉ ] \lambda^{[C=\bar{a}]} λ [ C = a ˉ ] of I ⋆ [ C = a ˉ ] I^\star[C=\bar{a}] I ⋆ [ C = a ˉ ] , and define the induced Eqn( G ) (G) ( G ) -solution
s [ C = a ˉ ] ( y ) = ∑ b ∈ D y λ y [ C = a ˉ ] ( b ) q ( b ) . s^{[C=\bar{a}]}(y)=\sum_{b\in D_y}\lambda_y^{[C=\bar{a}]}(b)q(b). s [ C = a ˉ ] ( y ) = b ∈ D y ∑ λ y [ C = a ˉ ] ( b ) q ( b ) .
If C = ( x 1 , x 2 , x 3 ) C=(x_1,x_2,x_3) C = ( x 1 , x 2 , x 3 ) and a ˉ = ( a 1 , a 2 , a 3 ) \bar{a}=(a_1,a_2,a_3) a ˉ = ( a 1 , a 2 , a 3 ) , then for i ∈ [ 3 ] i\in[3] i ∈ [ 3 ] ,
s [ C = a ˉ ] ( x i ) = q ( a i ) . s^{[C=\bar{a}]}(x_i)=q(a_i). s [ C = a ˉ ] ( x i ) = q ( a i ) .
Moreover, for every constraint B = ( y 1 , y 2 , y 3 ) B=(y_1,y_2,y_3) B = ( y 1 , y 2 , y 3 ) , the AIP marginal equations give
∑ i = 1 3 s [ C = a ˉ ] ( y i ) = ∑ b ˉ ∈ R B ⋆ λ B [ C = a ˉ ] ( b ˉ ) ∑ i = 1 3 q ( b i ) = 0. \sum_{i=1}^{3}s^{[C=\bar{a}]}(y_i)=\sum_{\bar{b}\in R_B^\star}\lambda_B^{[C=\bar{a}]}(\bar{b})\sum_{i=1}^{3}q(b_i)=0. i = 1 ∑ 3 s [ C = a ˉ ] ( y i ) = b ˉ ∈ R B ⋆ ∑ λ B [ C = a ˉ ] ( b ˉ ) i = 1 ∑ 3 q ( b i ) = 0.
Thus each s [ C = a ˉ ] s^{[C=\bar{a}]} s [ C = a ˉ ] is indeed an Eqn( G ) (G) ( G ) -solution of I I I .
Fix an ordering of Ω \Omega Ω and combine these solutions into the solution vector
s ( y ) = ( s [ C = a ˉ ] ( y ) ) ( C , a ˉ ) ∈ Ω ∈ G ∣ Ω ∣ . s(y)=\left(s^{[C=\bar{a}]}(y)\right)_{(C,\bar{a})\in\Omega}\in G^{|\Omega|}. s ( y ) = ( s [ C = a ˉ ] ( y ) ) ( C , a ˉ ) ∈ Ω ∈ G ∣Ω∣ .
This is an Eqn( G ∣ Ω ∣ ) (G^{|\Omega|}) ( G ∣Ω∣ ) -solution of I I I . Let
P = { y ∈ V ( I ) ∣ s ( y ) ≠ 0 } , Z = V ( I ) ∖ P = s − 1 ( 0 ) , P=\{y\in V(I)\mid s(y)\ne0\},\qquad Z=V(I)\setminus P=s^{-1}(0), P = { y ∈ V ( I ) ∣ s ( y ) = 0 } , Z = V ( I ) ∖ P = s − 1 ( 0 ) ,
and let I ′ = I [ Z ] I'=I[Z] I ′ = I [ Z ] . For each y ∈ P y\in P y ∈ P , define a partial colouring by
γ ( y ) = χ ( ∣ Ω ∣ ) ( s ( y ) ) . \gamma(y)=\chi^{(|\Omega|)}(s(y)). γ ( y ) = χ ( ∣Ω∣ ) ( s ( y )) .
Since s s s is an Eqn( G ∣ Ω ∣ ) (G^{|\Omega|}) ( G ∣Ω∣ ) -solution and χ ( ∣ Ω ∣ ) \chi^{(|\Omega|)} χ ( ∣Ω∣ ) is a c c c -rounding for G ∣ Ω ∣ G^{|\Omega|} G ∣Ω∣ , every constraint not contained in I ′ I' I ′ contains two variables in P P P that receive different colours under γ \gamma γ .
It remains to check that I ′ I' I ′ is a valid instance of Search-PCSP( R 0 , NAE c ) (R_0,\operatorname{NAE}_c) ( R 0 , NAE c ) . Let y ∈ Z y\in Z y ∈ Z , choose a constraint C = ( x 1 , x 2 , x 3 ) C=(x_1,x_2,x_3) C = ( x 1 , x 2 , x 3 ) containing y y y , and write y = x i y=x_i y = x i . Since CSinglAIP never deletes the tuple
h ˉ C = ( h ( x 1 ) , h ( x 2 ) , h ( x 3 ) ) , \bar{h}_C=(h(x_1),h(x_2),h(x_3)), h ˉ C = ( h ( x 1 ) , h ( x 2 ) , h ( x 3 )) ,
the pair ( C , h ˉ C ) (C,\bar{h}_C) ( C , h ˉ C ) belongs to Ω \Omega Ω . The corresponding coordinate of s ( y ) s(y) s ( y ) is
s [ C = h ˉ C ] ( y ) = q ( h ( y ) ) . s^{[C=\bar{h}_C]}(y)=q(h(y)). s [ C = h ˉ C ] ( y ) = q ( h ( y )) .
Since s ( y ) = 0 s(y)=0 s ( y ) = 0 , it follows that q ( h ( y ) ) = 0 q(h(y))=0 q ( h ( y )) = 0 . Therefore h ∣ Z h|_Z h ∣ Z is an R 0 R_0 R 0 -solution of I ′ I' I ′ . Given any N A E c \mathrm{NAE}_{c} NAE c -solution γ ′ \gamma' γ ′ of I ′ I' I ′ , extend the partial colouring γ \gamma γ by setting γ ∣ Z = γ ′ \gamma|_{Z}=\gamma' γ ∣ Z = γ ′ . Every constraint of I ′ I' I ′ is satisfied by γ ′ \gamma' γ ′ , while every other constraint was already made nonmonochromatic. Therefore γ \gamma γ is an N A E c \mathrm{NAE}_{c} NAE c -solution of I I I ; assigning arbitrary colours to the isolated variables set aside at the beginning completes the solution of the original instance.
Finally, the construction runs in polynomial time. Indeed,
∣ Ω ∣ ≤ ∣ C ( I ) ∣ ∣ R ∣ . |\Omega| \leq|C(I)|\,|R|. ∣Ω∣ ≤ ∣ C ( I ) ∣ ∣ R ∣.
CSinglAIP and the extraction of the AIP solutions λ [ C = a ˉ ] \lambda^{[C=\bar{a}]} λ [ C = a ˉ ] take polynomial time, and the product rounding χ ( ∣ Ω ∣ ) \chi^{(|\Omega|)} χ ( ∣Ω∣ ) is polynomial-time computable.
For the decision reduction, if CSinglAIP rejects, we output a fixed instance with no N A E c \mathrm{NAE}_{c} NAE c -solution; this is safe because CSinglAIP cannot reject an R R R -solvable instance. Otherwise, the residual instance I ′ = I [ Z ] I'=I[Z] I ′ = I [ Z ] is computed using only the induced group-valued solutions and their common zero set, without evaluating χ ( ∣ Ω ∣ ) \chi^{(|\Omega|)} χ ( ∣Ω∣ ) . If I I I has an R R R -solution, the argument above shows that I ′ I' I ′ has an R 0 R_{0} R 0 -solution. Conversely, any N A E c \mathrm{NAE}_{c} NAE c -solution of I ′ I' I ′ extends existentially, using the fixed product rounding χ ( ∣ Ω ∣ ) \chi^{(|\Omega|)} χ ( ∣Ω∣ ) , to an N A E c \mathrm{NAE}_{c} NAE c -solution of I I I . Thus No instances are preserved even when χ \chi χ is not efficiently computable. □
Remark C.7. The same reduction can also be implemented using SinglAIP. Indeed, after running SinglAIP to a fixed point, index the pinned AIP solutions by the surviving variable-value pairs ( x , a ) (x,a) ( x , a ) . The corresponding coordinate solution satisfies s [ x = a ] ( x ) = q ( a ) s^{[x=a]}(x)=q(a) s [ x = a ] ( x ) = q ( a ) . Hence, if the combined solution vector vanishes at x x x , then every surviving value a ∈ D x a\in D_{x} a ∈ D x belongs to q − 1 ( 0 ) q^{-1}(0) q − 1 ( 0 ) . The rounding and lifting arguments are otherwise identical. This is also consistent with the fact that every finite PCSP template solved by CSinglAIP is solved by SinglAIP.
Remark C.8. Both SinglAIP and CSinglAIP are idempotent: their outputs are fixed points, so rerunning the same algorithm makes no further deletions. Consequently, a single run of either singleton algorithm can provide several successive applications of Theorem 3.3.
A minion characterisation of CSinglAIP reductions
We now show that the reduction of Theorem 3.3 can also be performed by the broader class of CSinglAIP reductions. Following Dalmau and Opršal, we characterise when there exists a CSinglAIP reduction between PCSPs by a minion condition. The characterisation combines Zhuk’s [35 ] skeletal-matrix description of CSinglAIP, building on [21 ] , with the minion formulation of arc-consistency reductions from [24 ] .
We pass from function minions to the more general notion of an abstract minion. We also allow arities to be indexed by arbitrary nonempty finite sets, rather than only by sets of the form [ n ] [n] [ n ] .
Definition C.9 (Abstract minion). An (abstract) minion N \mathcal{N} N consists of a set N ( X ) \mathcal{N}^{(X)} N ( X ) for every nonempty finite set X X X and, for every map π : X → Y \pi:X\to Y π : X → Y , an operation
N ( X ) → N ( Y ) , f ↦ f π , \mathcal{N}^{(X)}\to\mathcal{N}^{(Y)},\qquad f\mapsto f^{\pi}, N ( X ) → N ( Y ) , f ↦ f π , such that
f i d x = f and ( f π ) ρ = f ρ ∘ π f^{\mathrm{idx}}=f\qquad\text{and}\qquad(f^{\pi})^{\rho}=f^{\rho\circ\pi} f idx = f and ( f π ) ρ = f ρ ∘ π for all maps π : X → Y \pi:X\to Y π : X → Y and ρ : Y → Z \rho:Y\to Z ρ : Y → Z . The elements of N ( X ) \mathcal{N}^{(X)} N ( X ) are said to have arity X X X , and the operations f ↦ f π f\mapsto f^{\pi} f ↦ f π are called minors .
A minion homomorphism ξ : N → M \xi:\mathcal{N}\to\mathcal{M} ξ : N → M is a collection of maps ξ X : N ( X ) → M ( X ) \xi_{X}:\mathcal{N}^{(X)}\to\mathcal{M}^{(X)} ξ X : N ( X ) → M ( X ) that preserve minors: for every f ∈ N ( X ) f\in\mathcal{N}^{(X)} f ∈ N ( X ) and π : X → Y \pi:X\to Y π : X → Y ,
ξ Y ( f π ) = ξ X ( f ) π . \xi_{Y}(f^{\pi})=\xi_{X}(f)^{\pi}. ξ Y ( f π ) = ξ X ( f ) π .
A function minion is viewed in this form by taking N ( X ) \mathcal{N}^{(X)} N ( X ) to consist of functions whose coordinates are indexed by X X X ; the minor corresponding to π : X → Y \pi:X\to Y π : X → Y identifies, permutes, or introduces dummy coordinates according to π \pi π .
We first define the minion of affine certificates arising from CSinglAIP. This is a special case of the skeletal-matrix descriptions of singleton algorithms from [35 ] .
Definition C.10 (Skeletal affine minion). For a nonempty finite set X X X , let M C S i n g l A I P ( X ) \mathcal{M}_{\mathrm{CSinglAIP}}^{(X)} M CSinglAIP ( X ) consist of the integer matrices
M : X × J → Z , M : X \times J \to\mathbb{Z}, M : X × J → Z , where J J J is an arbitrary nonempty finite set of columns, subject to the following two conditions:
every column has sum one, so
∑ x ∈ X M ( x , j ) = 1 ( j ∈ J ) ; \sum_{x \in X} M(x,j) = 1 \qquad(j \in J); x ∈ X ∑ M ( x , j ) = 1 ( j ∈ J ) ; every row occurring nontrivially in M M M has a unit column. More precisely, if
supp M = { x ∈ X : M ( x , j ) ≠ 0 for some j ∈ J } , \operatorname{supp} M = \{x \in X : M(x,j) \ne0 \text{ for some } j \in J\}, supp M = { x ∈ X : M ( x , j ) = 0 for some j ∈ J } , then, for every x ∈ supp M x \in\operatorname{supp} M x ∈ supp M , some column of M M M is the unit vector e x e_x e x .
For a map π : X → Y \pi: X \to Y π : X → Y , define
M π ( y , j ) = ∑ x ∈ π − 1 ( y ) M ( x , j ) . M^\pi(y,j) = \sum_{x \in\pi^{-1}(y)} M(x,j). M π ( y , j ) = x ∈ π − 1 ( y ) ∑ M ( x , j ) .
The second condition ensures that support cannot disappear through cancellation when rows are identified: a unit column e x e_x e x becomes e π ( x ) e_{\pi(x)} e π ( x ) . Consequently,
supp ( M π ) = π ( supp M ) . \operatorname{supp}(M^\pi) = \pi(\operatorname{supp} M). supp ( M π ) = π ( supp M ) .
The column-sum condition is also preserved by minors, and the unit columns remain unit columns after rows are identified. Hence M C S i n g l A I P \mathcal{M}_{\mathrm{CSinglAIP}} M CSinglAIP is indeed an abstract minion, and the support map describes a minion homomorphism from M C S i n g l A I P \mathcal{M}_{\mathrm{CSinglAIP}} M CSinglAIP to the nonempty-powerset minion
P + ( X ) = { S ⊆ X : S ≠ ∅ } , S π = π ( S ) . \mathcal{P}_{+}^{(X)} = \{S \subseteq X : S \ne\varnothing\}, \qquad S^\pi= \pi(S). P + ( X ) = { S ⊆ X : S = ∅ } , S π = π ( S ) .
Dalmau and Opršal’s construction is
ω ( N ) ( X ) = { ( S , f ) : S ∈ P + ( X ) , f ∈ N ( S ) } , ( S , f ) π = ( π ( S ) , f π ∣ S ) . \omega(\mathcal{N})^{(X)} = \{(S,f) : S \in\mathcal{P}_{+}^{(X)},\ f \in\mathcal{N}^{(S)}\}, \qquad(S,f)^\pi= (\pi(S), f^{\pi|_S}). ω ( N ) ( X ) = {( S , f ) : S ∈ P + ( X ) , f ∈ N ( S ) } , ( S , f ) π = ( π ( S ) , f π ∣ S ) .
Definition C.11. For an abstract minion N \mathcal{N} N , define
ω C S i n g l A I P ( N ) ( X ) = { ( M , f ) : M ∈ M C S i n g l A I P ( X ) , f ∈ N ( supp M ) } , ( M , f ) π = ( M π , f π ∣ supp M ) . \omega_{\mathrm{CSinglAIP}}(\mathcal{N})^{(X)} = \{(M,f) : M \in\mathcal{M}_{\mathrm{CSinglAIP}}^{(X)},\ f \in\mathcal{N}^{(\operatorname{supp} M)}\}, \qquad(M,f)^\pi= (M^\pi, f^{\pi|_{\operatorname{supp} M}}). ω CSinglAIP ( N ) ( X ) = {( M , f ) : M ∈ M CSinglAIP ( X ) , f ∈ N ( supp M ) } , ( M , f ) π = ( M π , f π ∣ supp M ) .
Mirroring Dalmau and Opršal’s treatment of arc consistency, we describe the construction in the language of Label Cover and minions. A finite Label Cover instance L \mathcal{L} L consists of a finite directed multigraph, a nonempty finite domain X v X_v X v for every vertex v v v , and, for every directed edge e = ( v → π e w ) e = (v \mathrel{\xrightarrow{\pi_e}} w) e = ( v π e w ) , a projection map π e : X v → X w \pi_e : X_v \to X_w π e : X v → X w . We call v v v the source and w w w the target of e e e and view the edge as the binary constraint with source coordinate first and relation
R e = { ( a , π e ( a ) ) : a ∈ X v } ⊆ X v × X w . R_e = \{(a,\pi_e(a)) : a \in X_v\} \subseteq X_v \times X_w. R e = {( a , π e ( a )) : a ∈ X v } ⊆ X v × X w .
Let N \mathcal{N} N be an abstract minion. An N \mathcal{N} N -solution of L \mathcal{L} L assigns an element f v ∈ N ( X v ) f_v \in\mathcal{N}^{(X_v)} f v ∈ N ( X v ) to every vertex v v v such that
f w = f v π e f_w = f_v^{\pi_e} f w = f v π e
for every edge e = ( v → π e w ) e = (v \mathrel{\xrightarrow{\pi_e}} w) e = ( v π e w ) . We write L → N \mathcal{L} \to\mathcal{N} L → N if such an N \mathcal{N} N -solution exists.
For a CSP instance I \mathcal{I} I , its associated LC instance, denoted LC ( I ) \operatorname{LC}(\mathcal{I}) LC ( I ) , has a variable of domain D x D_x D x for every variable x x x of I \mathcal{I} I , a variable of domain R C R_C R C for every constraint C C C , and the directed projection constraint C → π i x C \xrightarrow{\pi_i} x C π i x , where π i : R C → D x \pi_i : R_C \to D_x π i : R C → D x is the i i i th coordinate projection, whenever x x x occurs in position i i i of C C C .
For any finite CSP instance J J J , let κ C S i n g l A I P ( J ) \kappa_{\mathrm{CSinglAIP}}(J) κ CSinglAIP ( J ) denote the instance obtained by running CSinglAIP to a fixed point and then restricting each domain to the values occurring in the surviving constraint tuples; the domain of an isolated variable is left unchanged. If some constraint relation becomes empty, regard this instance as unsatisfiable. The following lemma is the analogue of [24 Lemma C.1] .
Lemma C.12. For every finite Label Cover instance L \mathcal{L} L and every abstract minion N \mathcal{N} N ,
κ C S i n g l A I P ( L ) ⟶ N ⟺ L ⟶ ω C S i n g l A I P ( N ) . \kappa_{\mathrm{CSinglAIP}}(\mathcal{L}) \longrightarrow\mathcal{N}
\quad\Longleftrightarrow\quad
\mathcal{L} \longrightarrow\omega_{\mathrm{CSinglAIP}}(\mathcal{N}). κ CSinglAIP ( L ) ⟶ N ⟺ L ⟶ ω CSinglAIP ( N ) .
Proof. Write F v ⊆ X v F_v \subseteq X_v F v ⊆ X v for the domain of v v v in κ C S i n g l A I P ( L ) \kappa_{\mathrm{CSinglAIP}}(\mathcal{L}) κ CSinglAIP ( L ) , provided CSinglAIP does not reject. Note that for every a ∈ F v a \in F_v a ∈ F v , the AIP relaxation of κ C S i n g l A I P ( L ) [ v = a ] \kappa_{\mathrm{CSinglAIP}}(\mathcal{L})[v=a] κ CSinglAIP ( L ) [ v = a ] is feasible. This also implies that for every edge e = ( v → π e w ) e=(v \xrightarrow{\pi_e} w) e = ( v π e w ) , π e ( F v ) = F w \pi_e(F_v)=F_w π e ( F v ) = F w .
Suppose first that h : κ C S i n g l A I P ( L ) → N h:\kappa_{\mathrm{CSinglAIP}}(\mathcal{L}) \to\mathcal{N} h : κ CSinglAIP ( L ) → N is an N \mathcal{N} N -solution sending v v v to h v h_v h v . We define a map g : L ⟶ ω C S i n g l A I P ( N ) g:\mathcal{L}\longrightarrow\omega_{\mathrm{CSinglAIP}}(\mathcal{N}) g : L ⟶ ω CSinglAIP ( N ) by
g ( v ) = ( M v , h v ) , g(v)=(M_v,h_v), g ( v ) = ( M v , h v ) ,
where M v ∈ M C S i n g l A I P ( X v ) M_v\in\mathcal{M}_{\mathrm{CSinglAIP}}^{(X_v)} M v ∈ M CSinglAIP ( X v ) is constructed as follows. Let Γ = { ( u , a ) ∣ u ∈ V ( L ) , a ∈ F u } \Gamma=\{(u,a)\mid u\in V(\mathcal{L}),\ a\in F_u\} Γ = {( u , a ) ∣ u ∈ V ( L ) , a ∈ F u } . By assumption, we can choose for each ( u , a ) ∈ Γ (u,a)\in\Gamma ( u , a ) ∈ Γ an AIP solution to the LC instance κ C S i n g l A I P ( L ) [ u = a ] \kappa_{\mathrm{CSinglAIP}}(\mathcal{L})[u=a] κ CSinglAIP ( L ) [ u = a ] , say λ u , a \lambda^{u,a} λ u , a . We write λ v u , a \lambda_v^{u,a} λ v u , a for its marginal distribution on v v v , a Z \mathbb{Z} Z -valued vector indexed by F v F_v F v . We construct M v ∈ M C S i n g l A I P ( X v ) M_v\in\mathcal{M}_{\mathrm{CSinglAIP}}^{(X_v)} M v ∈ M CSinglAIP ( X v ) as the X v × Γ X_v\times\Gamma X v × Γ matrix whose column indexed by ( u , a ) (u,a) ( u , a ) is λ v u , a \lambda_v^{u,a} λ v u , a padded with zeros in the entries corresponding to X v ∖ F v X_v\setminus F_v X v ∖ F v .
It is easy to check that M v ∈ M C S i n g l A I P ( X v ) M_v\in\mathcal{M}_{\mathrm{CSinglAIP}}^{(X_v)} M v ∈ M CSinglAIP ( X v ) , supp M v = F v \operatorname{supp}M_v=F_v supp M v = F v and h v ∈ N ( F v ) h_v\in\mathcal{N}^{(F_v)} h v ∈ N ( F v ) , and that g g g respects LC constraints/minors.
For the reverse implication, let g : L → ω C S i n g l A I P ( N ) g:\mathcal{L}\to\omega_{\mathrm{CSinglAIP}}(\mathcal{N}) g : L → ω CSinglAIP ( N ) , and write
g ( v ) = ( M v , g v ) , S v = supp M v . g(v)=(M_v,g_v),\qquad S_v=\operatorname{supp}M_v. g ( v ) = ( M v , g v ) , S v = supp M v .
Because g g g is an ω C S i n g l A I P ( N ) \omega_{\mathrm{CSinglAIP}}(\mathcal{N}) ω CSinglAIP ( N ) -solution,
M w = M v π e , S w = π e ( S v ) , g w = g v π e ∣ S v M_w=M_v^{\pi_e},\qquad S_w=\pi_e(S_v),\qquad g_w=g_v^{\pi_e|_{S_v}} M w = M v π e , S w = π e ( S v ) , g w = g v π e ∣ S v
for every edge e = ( v → π e w ) e=(v\xrightarrow{\pi_e}w) e = ( v π e w ) . Note that since taking the minor of a matrix does not change the column index set, all matrices in a connected component have the same column index set.
We claim that, for every edge e = ( v → π e w ) e=(v\xrightarrow{\pi_e}w) e = ( v π e w ) and every a ∈ S v a\in S_v a ∈ S v , the ordered tuple ( a , π e ( a ) ) (a,\pi_e(a)) ( a , π e ( a )) is never removed by CSinglAIP.
Suppose such a tuple is deleted at some point, say the tuple ( a , π e ( a ) ) (a,\pi_e(a)) ( a , π e ( a )) on e = ( v → π e w ) e=(v\xrightarrow{\pi_e}w) e = ( v π e w ) is the first such to be deleted. Fix a column j j j of M v M_v M v equal to the unit vector e a e_a e a . If x x x is in the same component as v v v , set j x = j j_x=j j x = j . For every other component K K K , choose some j K j_K j K in its column index set arbitrarily, and set j x = j K j_x=j_K j x = j K for all x x x in K K K . Now define
λ x ( b ) : = M x ( b , j x ) , λ d ( b , π d ( b ) ) : = M x ( b , j x ) ( d = ( x → π d y ) ) . \lambda_x(b):=M_x(b,j_x),\qquad
\lambda_d(b,\pi_d(b)):=M_x(b,j_x)\quad(d=(x\xrightarrow{\pi_d}y)). λ x ( b ) := M x ( b , j x ) , λ d ( b , π d ( b )) := M x ( b , j x ) ( d = ( x π d y )) .
λ \lambda λ is a valid solution to the AIP relaxation of the remaining LC instance: a nonzero coefficient requires b ∈ S x b\in S_x b ∈ S x , and by the choice of the first deletion the tuple ( b , π d ( b ) ) (b,\pi_d(b)) ( b , π d ( b )) is still present. Every column has sum one, while M y = M x π d M_y=M_x^{\pi_d} M y = M x π d gives the marginal equation at the target of $d; the marginal equation at its source is immediate. Moreover, on the distinguished edge e e e , the choice of the unit column gives
λ e ( a , π e ( a ) ) = 1 and λ e ( b , π e ( b ) ) = 0 ( b ≠ a ) . \lambda_e(a,\pi_e(a))=1
\qquad\text{and}\qquad
\lambda_e(b,\pi_e(b))=0\quad(b\ne a). λ e ( a , π e ( a )) = 1 and λ e ( b , π e ( b )) = 0 ( b = a ) .
Thus the AIP relaxation with ( a , π e ( a ) ) (a,\pi_e(a)) ( a , π e ( a )) forced on e e e is feasible, contradicting the deletion. This proves the claim.
Since every S v S_v S v is nonempty, the claim shows that every edge retains at least one tuple; hence CSinglAIP does not reject. Therefore the sets F v F_v F v are defined. Moreover, S v ⊆ F v S_v \subseteq F_v S v ⊆ F v for every v v v : this follows directly from the claim when v v v is the source of an edge, from S v = π e ( S u ) ⊆ π e ( F u ) = F v S_v = \pi_e(S_u) \subseteq\pi_e(F_u) = F_v S v = π e ( S u ) ⊆ π e ( F u ) = F v when v v v is only a target, and from F v = X v F_v = X_v F v = X v when v v v is isolated.
Define h v ∈ N ( F v ) h_v \in\mathcal{N}(F_v) h v ∈ N ( F v ) to be the minor of g v ∈ N ( S v ) g_v \in\mathcal{N}(S_v) g v ∈ N ( S v ) obtained by adding dummy coordinates indexed by F v ∖ S v F_v \setminus S_v F v ∖ S v . Using S w = π e ( S v ) S_w = \pi_e(S_v) S w = π e ( S v ) and g w = g v π e ∣ S v g_w = g_v^{\pi_e|_{S_v}} g w = g v π e ∣ S v , it follows that h : κ CSinglAIP ( L ) → N h : \kappa_{\operatorname{CSinglAIP}}(\mathcal{L}) \to\mathcal{N} h : κ CSinglAIP ( L ) → N is an N \mathcal{N} N -solution, as required. □
For a finite Label Cover instance L \mathcal{L} L and a relation S S S , let π S ( L ) \pi_S(\mathcal{L}) π S ( L ) denote the universal S S S -gadget ([24 Definition A.13] , presented as the indicator instance in [BBKO21]): take a copy of S X v S^{X_v} S X v for every vertex v v v , and for every edge e = ( v → π e w ) e=(v \xrightarrow{\pi_e} w) e = ( v π e w ) identify each b ∈ S X w b \in S^{X_w} b ∈ S X w with b ∘ π e ∈ S X v b \circ\pi_e \in S^{X_v} b ∘ π e ∈ S X v . By [BBKO21, Lemma 3.16],
π S ( L ) → T ⟺ L → Pol ( S , T ) . \pi_S(\mathcal{L}) \to T \quad\Longleftrightarrow\quad\mathcal{L} \to\operatorname{Pol}(S,T). π S ( L ) → T ⟺ L → Pol ( S , T ) .
Definition C.13. Let J ∘ J_\circ J ∘ be the instance with one variable x x x and the single constraint ( x , x , x ) (x,x,x) ( x , x , x ) . Define
Φ S ( I ) = { J ∘ , if CSinglAIP rejects on LC ( I ) , π S ( κ CSinglAIP ( LC ( I ) ) ) , otherwise. \Phi_S(I)=
\begin{cases}
J_\circ, & \text{if CSinglAIP rejects on } \operatorname{LC}(I),\\
\pi_S\bigl(\kappa_{\operatorname{CSinglAIP}}(\operatorname{LC}(I))\bigr), & \text{otherwise.}
\end{cases} Φ S ( I ) = { J ∘ , π S ( κ CSinglAIP ( LC ( I )) ) , if CSinglAIP rejects on LC ( I ) , otherwise. We write
PCSP ( R , Q ) ≤ CSinglAIP PCSP ( S , T ) \operatorname{PCSP}(R,Q) \le_{\operatorname{CSinglAIP}} \operatorname{PCSP}(S,T) PCSP ( R , Q ) ≤ CSinglAIP PCSP ( S , T ) if Φ S \Phi_S Φ S is a reduction from PCSP ( R , Q ) \operatorname{PCSP}(R,Q) PCSP ( R , Q ) to PCSP ( S , T ) \operatorname{PCSP}(S,T) PCSP ( S , T ) .
Definition C.14 (Free structure [BBKO21]). Let R ⊆ A k R \subseteq A^k R ⊆ A k be a nonempty relation on a finite set A A A , and let M \mathcal{M} M be an abstract minion. The free structure of M \mathcal{M} M generated by R R R , denoted F M ( R ) F_{\mathcal{M}}(R) F M ( R ) , is the k k k -ary relation on M ( A ) \mathcal{M}(A) M ( A ) consisting of all tuples ( f 1 , … , f k ) (f_1,\ldots,f_k) ( f 1 , … , f k ) for which there exists g ∈ M ( R ) g \in\mathcal{M}(R) g ∈ M ( R ) such that
f i = g π i ( i ∈ [ k ] ) , π i : R → A , π i ( a 1 , … , a k ) = a i . f_i=g^{\pi_i}\qquad(i \in[k]),\qquad\pi_i:R\to A,\qquad\pi_i(a_1,\ldots,a_k)=a_i. f i = g π i ( i ∈ [ k ]) , π i : R → A , π i ( a 1 , … , a k ) = a i .
Theorem C.15 (Characterisation of the CSinglAIP reduction). For finite promise templates ( R , Q ) (R,Q) ( R , Q ) and ( S , T ) (S,T) ( S , T ) such that T T T contains no constant tuple,
PCSP ( R , Q ) ≤ CSinglAIP PCSP ( S , T ) ⟺ ω CSinglAIP Pol ( S , T ) → Pol ( R , Q ) . \operatorname{PCSP}(R,Q) \le_{\operatorname{CSinglAIP}} \operatorname{PCSP}(S,T)
\quad\Longleftrightarrow\quad
\omega_{\operatorname{CSinglAIP}}\operatorname{Pol}(S,T) \to\operatorname{Pol}(R,Q). PCSP ( R , Q ) ≤ CSinglAIP PCSP ( S , T ) ⟺ ω CSinglAIP Pol ( S , T ) → Pol ( R , Q ) .
Proof. Note that the completeness of the reduction on the left is easy to show in general, so we show that the soundness of the reduction is equivalent to the property on the right.
Fix a finite instance I I I of PCSP ( R , Q ) \operatorname{PCSP}(R,Q) PCSP ( R , Q ) . The defining property of the universal gadget and Lemma C.12 give
Φ S ( I ) → T ⟺ κ CSinglAIP ( LC ( I ) ) → Pol ( S , T ) ⟺ LC ( I ) → ω CSinglAIP Pol ( S , T ) . \Phi_S(I) \to T
\quad\Longleftrightarrow\quad
\kappa_{\operatorname{CSinglAIP}}(\operatorname{LC}(I)) \to\operatorname{Pol}(S,T)
\quad\Longleftrightarrow\quad
\operatorname{LC}(I) \to\omega_{\operatorname{CSinglAIP}}\operatorname{Pol}(S,T). Φ S ( I ) → T ⟺ κ CSinglAIP ( LC ( I )) → Pol ( S , T ) ⟺ LC ( I ) → ω CSinglAIP Pol ( S , T ) .
The property we need is [24 Lemma C.4]
LC ( I ) → M ⟺ I → F M ( R ) . \operatorname{LC}(I) \to\mathcal{M}
\quad\Longleftrightarrow\quad
I \to F_{\mathcal{M}}(R). LC ( I ) → M ⟺ I → F M ( R ) .
Moreover, by [BBKO21, Lemma 4.4],
M → Pol ( R , Q ) ⟺ F M ( R ) → Q . \mathcal{M} \to\operatorname{Pol}(R,Q)
\quad\Longleftrightarrow\quad
F_{\mathcal{M}}(R) \to Q. M → Pol ( R , Q ) ⟺ F M ( R ) → Q .
Since Q Q Q is finite, compactness shows that
F M ( R ) → Q ⟺ ( ∀ I a finite R -instance , I → F M ( R ) ⟹ I → Q ) . F_{\mathcal{M}}(R) \to Q
\quad\Longleftrightarrow\quad
\left(\forall I\text{ a finite }R\text{-instance},\ I \to F_{\mathcal{M}}(R) \Longrightarrow I \to Q\right). F M ( R ) → Q ⟺ ( ∀ I a finite R -instance , I → F M ( R ) ⟹ I → Q ) .
Setting M = ω CSinglAIP Pol ( S , T ) \mathcal{M}=\omega_{\operatorname{CSinglAIP}}\operatorname{Pol}(S,T) M = ω CSinglAIP Pol ( S , T ) completes the proof. □
We next show that the reduction from Theorem 3.3 can indeed be placed in this broader reduction framework.
Corollary C.16. Under the hypotheses of Theorem 3.3, with R 0 = R ∣ q − 1 ( 0 ) R_0 = R|_{q^{-1}(0)} R 0 = R ∣ q − 1 ( 0 ) ,
PCSP ( R , NAE c ) ≤ CSinglAIP PCSP ( R 0 , NAE c ) . \operatorname{PCSP}(R,\operatorname{NAE}_c) \leq_{\operatorname{CSinglAIP}} \operatorname{PCSP}(R_0,\operatorname{NAE}_c). PCSP ( R , NAE c ) ≤ CSinglAIP PCSP ( R 0 , NAE c ) .
Proof. We construct the minion homomorphism required by Theorem C.15.
Let ( M , f ) ∈ ω CSinglAIP ( Pol ( R 0 , NAE c ) ) ( X ) (M,f) \in\omega_{\operatorname{CSinglAIP}}(\operatorname{Pol}(R_0,\operatorname{NAE}_c))(X) ( M , f ) ∈ ω CSinglAIP ( Pol ( R 0 , NAE c )) ( X ) , let J J J be the column index set of M M M , put S = supp M S = \operatorname{supp} M S = supp M , and put
s M ( a ) = ( ∑ x ∈ X M ( x , j ) q ( a x ) ) j ∈ J s_M(a) = \left(\sum_{x \in X} M(x,j)q(a_x)\right)_{j \in J} s M ( a ) = ( x ∈ X ∑ M ( x , j ) q ( a x ) ) j ∈ J
for a ∈ dom ( R ) X a \in\operatorname{dom}(R)^X a ∈ dom ( R ) X .
Extend f f f to f ^ : dom ( R ) S → [ c ] \widehat{f} : \operatorname{dom}(R)^S \to[c] f : dom ( R ) S → [ c ] by setting f ^ ( b ) = f ( b ) \widehat{f}(b) = f(b) f ( b ) = f ( b ) for b ∈ dom ( R 0 ) S b \in\operatorname{dom}(R_0)^S b ∈ dom ( R 0 ) S and f ^ ( b ) = 1 \widehat{f}(b) = 1 f ( b ) = 1 otherwise. After fixing an order on each column index set, define
ξ X ( M , f ) ( a ) = { χ ( ∣ J ∣ ) ( s M ( a ) ) , s M ( a ) ≠ 0 , f ^ ( a ∣ S ) , s M ( a ) = 0. \xi_X(M,f)(a) =
\begin{cases}
\chi^{(|J|)}(s_M(a)), & s_M(a) \ne0, \\
\widehat{f}(a|_S), & s_M(a) = 0.
\end{cases} ξ X ( M , f ) ( a ) = { χ ( ∣ J ∣ ) ( s M ( a )) , f ( a ∣ S ) , s M ( a ) = 0 , s M ( a ) = 0.
We must show that ξ X ( M , f ) \xi_X(M,f) ξ X ( M , f ) is indeed a polymorphism. Suppose ( a ˉ , b ˉ , c ˉ ) ∈ R X (\bar{a},\bar{b},\bar{c}) \in R^X ( a ˉ , b ˉ , c ˉ ) ∈ R X . Then it is easy to see that s M ( a ˉ ) + s M ( b ˉ ) + s M ( c ˉ ) = 0 ˉ s_M(\bar{a}) + s_M(\bar{b}) + s_M(\bar{c}) = \bar{0} s M ( a ˉ ) + s M ( b ˉ ) + s M ( c ˉ ) = 0 ˉ . If some s M s_M s M -vector is nonzero, the c c c -rounding makes the three outputs nonconstant. Suppose instead that s M ( a ˉ ) = s M ( b ˉ ) = s M ( c ˉ ) = 0 ˉ s_M(\bar{a}) = s_M(\bar{b}) = s_M(\bar{c}) = \bar{0} s M ( a ˉ ) = s M ( b ˉ ) = s M ( c ˉ ) = 0 ˉ . For every x ∈ S x \in S x ∈ S , the unit column e x e_x e x shows that q ( a x ) = q ( b x ) = q ( c x ) = 0 q(a_x) = q(b_x) = q(c_x) = 0 q ( a x ) = q ( b x ) = q ( c x ) = 0 . Hence ( a ˉ ∣ S , b ˉ ∣ S , c ˉ ∣ S ) ∈ R 0 S (\bar{a}|_S,\bar{b}|_S,\bar{c}|_S) \in R_0^S ( a ˉ ∣ S , b ˉ ∣ S , c ˉ ∣ S ) ∈ R 0 S , so the three outputs are nonconstant since f ∈ Pol ( R 0 , NAE c ) f \in\operatorname{Pol}(R_0,\operatorname{NAE}_c) f ∈ Pol ( R 0 , NAE c ) .
Finally, let π : X → Y \pi: X \to Y π : X → Y , put S ′ = π ( S ) = supp ( M π ) S' = \pi(S) = \operatorname{supp}(M^\pi) S ′ = π ( S ) = supp ( M π ) , and write ρ = π ∣ S : S → S ′ \rho= \pi|_S : S \to S' ρ = π ∣ S : S → S ′ . Since ρ \rho ρ is surjective, for every u ∈ dom ( R ) S ′ u \in\operatorname{dom}(R)^{S'} u ∈ dom ( R ) S ′ we have
u ∈ dom ( R 0 ) S ′ ⟺ u ∘ ρ ∈ dom ( R 0 ) S . u \in\operatorname{dom}(R_0)^{S'} \Longleftrightarrow u \circ\rho\in\operatorname{dom}(R_0)^S. u ∈ dom ( R 0 ) S ′ ⟺ u ∘ ρ ∈ dom ( R 0 ) S .
Thus ( f ^ ) ρ = f ρ ^ (\widehat{f})^\rho= \widehat{f^\rho} ( f ) ρ = f ρ , where the right-hand side denotes the same constant-1 extension to dom ( R ) S ′ \operatorname{dom}(R)^{S'} dom ( R ) S ′ . Together with
s M π ( a ) = s M ( a ∘ π ) and ( a ∘ π ) ∣ S = ( a ∣ S ′ ) ∘ ρ , s_{M^\pi}(a) = s_M(a \circ\pi) \qquad\text{and}\qquad(a \circ\pi)|_S = (a|_{S'}) \circ\rho, s M π ( a ) = s M ( a ∘ π ) and ( a ∘ π ) ∣ S = ( a ∣ S ′ ) ∘ ρ ,
this proves that ξ \xi ξ preserves minors. □
Classification of valid partitions of Z p \mathbb{Z}_p Z p
Recall that we say a partition of Z p \mathbb{Z}_p Z p into 3 sets A 1 , A 2 , A 3 A_1,A_2,A_3 A 1 , A 2 , A 3 is valid if the only solution to x + y + z ≡ 0 ( m o d p ) x+y+z \equiv0 \pmod p x + y + z ≡ 0 ( mod p ) with x , y , z ∈ A i x,y,z \in A_i x , y , z ∈ A i for some i ∈ [ 3 ] i \in[3] i ∈ [ 3 ] is x = y = z = 0 x=y=z=0 x = y = z = 0 . Furthermore, we only consider such partitions up to (i) multiplication by a constant and (ii) permutation of parts.
Subsets T T T of an Abelian group for which t 1 + t 2 + t 3 ≠ 0 t_1+t_2+t_3 \ne0 t 1 + t 2 + t 3 = 0 for all t 1 , t 2 , t 3 ∈ T t_1,t_2,t_3 \in T t 1 , t 2 , t 3 ∈ T are known as 3-independent sets. Voloch constructed maximal 3-independent subsets of Z p \mathbb{Z}_p Z p [33 Section 2] , and Szőnyi studied their possible sizes and structure; in particular, he proved uniqueness up to automorphism for a 3-independent subset of Z p \mathbb{Z}_p Z p of size ( p + 1 ) / 3 (p+1)/3 ( p + 1 ) /3 when p ≡ 2 ( m o d 3 ) p \equiv2 \pmod3 p ≡ 2 ( mod 3 ) [32 Proposition 4.2] . Theorem 1.7 instead concerns the simultaneous classification of partitions into three valid parts, with the trivial triple ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) allowed in the part containing 0.
The proof of Theorem 1.7 relies on the following standard results from additive combinatorics.
Theorem D.1 (Cauchy–Davenport [22 ] ). Let p p p be prime and let X , Y ⊆ Z p X,Y \subseteq\mathbb{Z}_p X , Y ⊆ Z p be nonempty. Then
∣ X + Y ∣ ≥ min { p , ∣ X ∣ + ∣ Y ∣ − 1 } . |X+Y| \ge\min\{p,|X|+|Y|-1\}. ∣ X + Y ∣ ≥ min { p , ∣ X ∣ + ∣ Y ∣ − 1 } .
Theorem D.2 (Vosper [34 ] ). Let p p p be prime and let X , Y ⊆ Z p X,Y \subseteq\mathbb{Z}_p X , Y ⊆ Z p satisfy ∣ X ∣ , ∣ Y ∣ ≥ 2 |X|,|Y| \ge2 ∣ X ∣ , ∣ Y ∣ ≥ 2 . If
∣ X + Y ∣ = ∣ X ∣ + ∣ Y ∣ − 1 ≤ p − 2 , |X+Y|=|X|+|Y|-1\le p-2, ∣ X + Y ∣ = ∣ X ∣ + ∣ Y ∣ − 1 ≤ p − 2 , then X X X and Y Y Y are arithmetic progressions with the same nonzero common difference.
Theorem 1.7. For every prime p ≥ 7 p \ge7 p ≥ 7 , up to multiplication by a constant and permutation of parts, there exists exactly one valid partition of Z p \mathbb{Z}_p Z p , namely the partition that puts x x x into A 1 + ⌊ 3 x p ⌋ A_{1+\left\lfloor\frac{3x}{p}\right\rfloor} A 1 + ⌊ p 3 x ⌋ .
Proof. It is easy to check that this is a valid partition of Z p \mathbb{Z}_p Z p : indeed if x , y , z ∈ A 1 + i x,y,z \in A_{1+i} x , y , z ∈ A 1 + i and at least one of x , y , z x,y,z x , y , z is not 0, then the rounding operation in the following expression is applied to a nonintegral value at least once, and hence
3 i = ⌊ 3 x p ⌋ + ⌊ 3 y p ⌋ + ⌊ 3 z p ⌋ < 3 x p + 3 y p + 3 z p . 3i=\left\lfloor\frac{3x}{p}\right\rfloor+\left\lfloor\frac{3y}{p}\right\rfloor+\left\lfloor\frac{3z}{p}\right\rfloor<\frac{3x}{p}+\frac{3y}{p}+\frac{3z}{p}. 3 i = ⌊ p 3 x ⌋ + ⌊ p 3 y ⌋ + ⌊ p 3 z ⌋ < p 3 x + p 3 y + p 3 z .
Hence i p < x + y + z ip<x+y+z i p < x + y + z . More easily,
3 ( i + 1 ) = ( 1 + ⌊ 3 x p ⌋ ) + ( 1 + ⌊ 3 y p ⌋ ) + ( 1 + ⌊ 3 z p ⌋ ) > 3 x p + 3 y p + 3 z p . 3(i+1)=\left(1+\left\lfloor\frac{3x}{p}\right\rfloor\right)+\left(1+\left\lfloor\frac{3y}{p}\right\rfloor\right)+\left(1+\left\lfloor\frac{3z}{p}\right\rfloor\right)>\frac{3x}{p}+\frac{3y}{p}+\frac{3z}{p}. 3 ( i + 1 ) = ( 1 + ⌊ p 3 x ⌋ ) + ( 1 + ⌊ p 3 y ⌋ ) + ( 1 + ⌊ p 3 z ⌋ ) > p 3 x + p 3 y + p 3 z .
Hence x + y + z < ( i + 1 ) p x+y+z<(i+1)p x + y + z < ( i + 1 ) p . So x + y + z ≢ 0 ( m o d p ) x+y+z\not\equiv0\pmod p x + y + z ≡ 0 ( mod p ) , and this is indeed a valid partition.
We now need to prove uniqueness up to multiplication by a constant and permutation of parts. Suppose without loss of generality that ∣ A 1 ∣ ≤ ∣ A 2 ∣ ≤ ∣ A 3 ∣ |A_1|\le|A_2|\le|A_3| ∣ A 1 ∣ ≤ ∣ A 2 ∣ ≤ ∣ A 3 ∣ . We first prove a simple fact.
Claim D.3. ∣ A i ∣ ≤ ⌈ p 3 ⌉ |A_i|\le\left\lceil\frac{p}{3}\right\rceil ∣ A i ∣ ≤ ⌈ 3 p ⌉ .
Proof. Let A = A i A=A_i A = A i . Note that by definition any solution to x + y + z ≡ 0 ( m o d p ) x+y+z\equiv0\pmod p x + y + z ≡ 0 ( mod p ) in A A A is x = y = z = 0 x=y=z=0 x = y = z = 0 . Hence, ( A + A ) ∩ ( − A ) ⊆ { 0 } (A+A)\cap(-A)\subseteq\{0\} ( A + A ) ∩ ( − A ) ⊆ { 0 } . Thus ∣ A + A ∣ + ∣ − A ∣ ≤ p + 1 |A+A|+|-A|\le p+1 ∣ A + A ∣ + ∣ − A ∣ ≤ p + 1 . Note that ∣ − A ∣ = ∣ A ∣ |-A|=|A| ∣ − A ∣ = ∣ A ∣ , and furthermore by the Cauchy–Davenport theorem ∣ A + A ∣ ≥ min ( p , 2 ∣ A ∣ − 1 ) |A+A|\ge\min(p,2|A|-1) ∣ A + A ∣ ≥ min ( p , 2∣ A ∣ − 1 ) . Thus min ( p , 2 ∣ A ∣ − 1 ) + ∣ A ∣ ≤ p + 1 \min(p,2|A|-1)+|A|\le p+1 min ( p , 2∣ A ∣ − 1 ) + ∣ A ∣ ≤ p + 1 . If the minimum on the left-hand side is p p p , then ∣ A ∣ ≤ 1 |A|\le1 ∣ A ∣ ≤ 1 , which implies the desired bound. Otherwise we have 3 ∣ A ∣ − 1 ≤ p + 1 3|A|-1\le p+1 3∣ A ∣ − 1 ≤ p + 1 , or, rearranging, ∣ A ∣ ≤ ⌊ p + 2 3 ⌋ = ⌈ p 3 ⌉ |A|\le\left\lfloor\frac{p+2}{3}\right\rfloor=\left\lceil\frac{p}{3}\right\rceil ∣ A ∣ ≤ ⌊ 3 p + 2 ⌋ = ⌈ 3 p ⌉ .
Returning to the proof of uniqueness, we split into two cases: p = 3 k + 1 p=3k+1 p = 3 k + 1 and p = 3 k + 2 p=3k+2 p = 3 k + 2 .
Claim D.4. Uniqueness holds for p = 3 k + 1 p=3k+1 p = 3 k + 1 .
Proof. In this case we have, by Claim D.3, that without loss of generality ( ∣ A 1 ∣ , ∣ A 2 ∣ , ∣ A 3 ∣ ) = ( k , k , k + 1 ) (|A_1|,|A_2|,|A_3|)=(k,k,k+1) ( ∣ A 1 ∣ , ∣ A 2 ∣ , ∣ A 3 ∣ ) = ( k , k , k + 1 ) or ( k − 1 , k + 1 , k + 1 ) (k-1,k+1,k+1) ( k − 1 , k + 1 , k + 1 ) . Note that if ∣ A i ∣ = k + 1 |A_i|=k+1 ∣ A i ∣ = k + 1 , the inequality of Claim D.3 is tight, hence (i) the inequality ∣ A i + A i ∣ + ∣ − A i ∣ ≤ p + 1 |A_i+A_i|+|-A_i|\le p+1 ∣ A i + A i ∣ + ∣ − A i ∣ ≤ p + 1 is tight—and hence 0 ∈ A i 0\in A_i 0 ∈ A i —and (ii) our application of Cauchy–Davenport is tight. Since 0 can only be in one of the sets, we must be in the case ∣ A 1 ∣ = ∣ A 2 ∣ = k |A_1|=|A_2|=k ∣ A 1 ∣ = ∣ A 2 ∣ = k and ∣ A 3 ∣ = k + 1 |A_3|=k+1 ∣ A 3 ∣ = k + 1 . Also, by Vosper’s theorem, A 3 A_3 A 3 is an arithmetic progression. Multiplying by the inverse of the common difference of this arithmetic progression, we may assume that A 3 A_3 A 3 is an arithmetic progression with common difference 1, which contains 0. It cannot contain − 1 -1 − 1 and 1 (or else the nontrivial solution ( − 1 ) + 0 + 1 ≡ 0 ( m o d p ) (-1)+0+1\equiv0\pmod p ( − 1 ) + 0 + 1 ≡ 0 ( mod p ) would be monochromatic). Hence it contains only one of these, and by multiplying perhaps with − 1 -1 − 1 we may assume without loss of generality that it contains − 1 ≡ p − 1 ( m o d p ) -1\equiv p-1\pmod p − 1 ≡ p − 1 ( mod p ) . Hence A 3 = { 2 k + 1 , … , 3 k , 0 } A_3=\{2k+1,\ldots,3k,0\} A 3 = { 2 k + 1 , … , 3 k , 0 } .
At this point, we note A 1 ∪ A 2 = { 1 , … , 2 k } A_1\cup A_2=\{1,\ldots,2k\} A 1 ∪ A 2 = { 1 , … , 2 k } . Note that since k + k + ( k + 1 ) ≡ 0 ( m o d p ) k+k+(k+1)\equiv0\pmod p k + k + ( k + 1 ) ≡ 0 ( mod p ) , we have that k k k and k + 1 k+1 k + 1 are not both within the same part. Assume without loss of generality k ∈ A 1 k\in A_1 k ∈ A 1 , k + 1 ∈ A 2 k+1\in A_2 k + 1 ∈ A 2 . We prove inductively that { k − r + 1 , … , k } ⊆ A 1 \{k-r+1,\ldots,k\}\subseteq A_1 { k − r + 1 , … , k } ⊆ A 1 and { k + 1 , … , k + r } ⊆ A 2 \{k+1,\ldots,k+r\}\subseteq A_2 { k + 1 , … , k + r } ⊆ A 2 for r = 1 , … , k r=1,\ldots,k r = 1 , … , k . The base case is already shown. Now suppose we have established this for some r < k r<k r < k . Consider that
k + 1 , k + r ∈ A 2 k+1,k+r\in A_2 k + 1 , k + r ∈ A 2 and ( k − r ) + ( k + 1 ) + ( k + r ) ≡ 0 ( m o d p ) (k-r)+(k+1)+(k+r)\equiv0\pmod{p} ( k − r ) + ( k + 1 ) + ( k + r ) ≡ 0 ( mod p ) implies k − r ∈ A 1 k-r\in A_1 k − r ∈ A 1 ; and k − r , k ∈ A 1 k-r,k\in A_1 k − r , k ∈ A 1 and ( k − r ) + k + ( k + r + 1 ) ≡ 0 ( m o d p ) (k-r)+k+(k+r+1)\equiv0\pmod{p} ( k − r ) + k + ( k + r + 1 ) ≡ 0 ( mod p ) implies k + r + 1 ∈ A 2 k+r+1\in A_2 k + r + 1 ∈ A 2 , which completes the inductive step. At r = k r=k r = k , both containments are equalities by the known cardinalities of A 1 A_1 A 1 and A 2 A_2 A 2 . Hence A 1 = { 1 , … , k } A_1=\{1,\ldots,k\} A 1 = { 1 , … , k } , A 2 = { k + 1 , … , 2 k } A_2=\{k+1,\ldots,2k\} A 2 = { k + 1 , … , 2 k } , A 3 = { 2 k + 1 , … , 3 k , 0 } A_3=\{2k+1,\ldots,3k,0\} A 3 = { 2 k + 1 , … , 3 k , 0 } , and thus ( − A 3 , − A 2 , − A 1 ) = ( { 0 , … , k } , { k + 1 , … , 2 k } , { 2 k + 1 , … , 3 k } ) (-A_3,-A_2,-A_1)=(\{0,\ldots,k\},\{k+1,\ldots,2k\},\{2k+1,\ldots,3k\}) ( − A 3 , − A 2 , − A 1 ) = ({ 0 , … , k } , { k + 1 , … , 2 k } , { 2 k + 1 , … , 3 k }) . This concludes the proof of uniqueness. □
Claim D.5. Uniqueness holds for p = 3 k + 2 p=3k+2 p = 3 k + 2 .
Proof. Similarly to before, we see that ∣ A 1 ∣ = k |A_1|=k ∣ A 1 ∣ = k and ∣ A 2 ∣ = ∣ A 3 ∣ = k + 1 |A_2|=|A_3|=k+1 ∣ A 2 ∣ = ∣ A 3 ∣ = k + 1 . Without loss of generality, suppose 0 ∉ A 3 0\notin A_3 0 ∈ / A 3 . Hence ( A 3 + A 3 ) ∩ ( − A 3 ) = ∅ (A_3+A_3)\cap(-A_3)=\varnothing ( A 3 + A 3 ) ∩ ( − A 3 ) = ∅ , ∣ A 3 + A 3 ∣ + ∣ − A 3 ∣ ≤ p |A_3+A_3|+|-A_3|\le p ∣ A 3 + A 3 ∣ + ∣ − A 3 ∣ ≤ p , and Cauchy-Davenport holds with equality, since by disjointness ∣ A 3 + A 3 ∣ ≤ p − ∣ A 3 ∣ = 2 k + 1 = ∣ A 3 ∣ + ∣ A 3 ∣ − 1 |A_3+A_3|\le p-|A_3|=2k+1=|A_3|+|A_3|-1 ∣ A 3 + A 3 ∣ ≤ p − ∣ A 3 ∣ = 2 k + 1 = ∣ A 3 ∣ + ∣ A 3 ∣ − 1 . Hence, by Vosper’s theorem, we see that A 3 A_3 A 3 is an arithmetic progression.
Suppose that A 3 A_3 A 3 is the arithmetic progression { a + d i ∣ i = 0 , … , k } \{a+di\mid i=0,\ldots,k\} { a + d i ∣ i = 0 , … , k } . Therefore A 3 + A 3 + A 3 = { 3 a + d i ∣ i = 0 , … , 3 k } A_3+A_3+A_3=\{3a+di\mid i=0,\ldots,3k\} A 3 + A 3 + A 3 = { 3 a + d i ∣ i = 0 , … , 3 k } . Note that 0 ∉ A 3 + A 3 + A 3 0\notin A_3+A_3+A_3 0 ∈ / A 3 + A 3 + A 3 , hence 3 a + d i 3a+di 3 a + d i enumerates all values 1 , … , 3 k + 1 1,\ldots,3k+1 1 , … , 3 k + 1 as i i i ranges from 0 0 0 to 3 k 3k 3 k . Note furthermore that i ↦ 3 a + d i i\mapsto3a+di i ↦ 3 a + d i is a bijection on Z p \mathbb{Z}_p Z p , so applying it to the value not mentioned before (i.e. 3 k + 1 3k+1 3 k + 1 ) yields the output not mentioned before (i.e. 0 0 0 ). In other words 3 a + d ( 3 k + 1 ) ≡ 0 ( m o d p ) 3a+d(3k+1)\equiv0\pmod p 3 a + d ( 3 k + 1 ) ≡ 0 ( mod p ) . Hence 3 a ≡ d ( m o d p ) 3a\equiv d\pmod p 3 a ≡ d ( mod p ) , and multiplying by k + 1 k+1 k + 1 we have a ≡ d ( k + 1 ) a\equiv d(k+1) a ≡ d ( k + 1 ) . Hence A 3 = { d ( k + 1 ) , … , d ( 2 k + 1 ) } A_3=\{d(k+1),\ldots,d(2k+1)\} A 3 = { d ( k + 1 ) , … , d ( 2 k + 1 )} .
Observe that A 3 = − A 3 A_3=-A_3 A 3 = − A 3 . Suppose first, for contradiction, that 0 ∉ A 2 0\notin A_2 0 ∈ / A 2 . By the preceding argument, we see also that A 2 = − A 2 A_2=-A_2 A 2 = − A 2 , and hence A 1 = − A 1 A_1=-A_1 A 1 = − A 1 and by the process of elimination 0 ∈ A 1 0\in A_1 0 ∈ A 1 . But this is impossible, since then (as k > 1 k>1 k > 1 ) there exists some nonzero x ∈ A 1 x\in A_1 x ∈ A 1 , and then x + 0 + ( − x ) ≡ 0 ( m o d p ) x+0+(-x)\equiv0\pmod p x + 0 + ( − x ) ≡ 0 ( mod p ) is a monochromatic nontrivial solution. Hence we find that 0 ∈ A 2 0\in A_2 0 ∈ A 2 . Now, scale all sets by the inverse of d d d to get to the following situation: 0 ∈ A 2 0\in A_2 0 ∈ A 2 , A 1 ∪ A 2 = { − k , … , k } A_1\cup A_2=\{-k,\ldots,k\} A 1 ∪ A 2 = { − k , … , k } and A 3 = { k + 1 , … , 2 k + 1 } A_3=\{k+1,\ldots,2k+1\} A 3 = { k + 1 , … , 2 k + 1 } .
Note that if A 1 A_1 A 1 contains x x x and − x -x − x for any x ∈ [ k ] x\in[k] x ∈ [ k ] , by the pigeonhole principle there exists some y ∈ [ k ] y\in[k] y ∈ [ k ] such that y , − y ∈ A 2 y,-y\in A_2 y , − y ∈ A 2 , which is impossible as 0 ∈ A 2 0\in A_2 0 ∈ A 2 . Hence for every such pair, one element belongs to A 1 A_1 A 1 and one to A 2 A_2 A 2 . Assume (by negating) that { 0 , 1 } ⊆ A 2 \{0,1\}\subseteq A_2 { 0 , 1 } ⊆ A 2 and − 1 ∈ A 1 -1\in A_1 − 1 ∈ A 1 . We shall prove inductively that A 1 ⊇ { − r , … , − 1 } A_1\supseteq\{-r,\ldots,-1\} A 1 ⊇ { − r , … , − 1 } and A 2 ⊇ { 0 , … , r } A_2\supseteq\{0,\ldots,r\} A 2 ⊇ { 0 , … , r } , for r = 1 , … , k r=1,\ldots,k r = 1 , … , k . The base case is already proved. Now assume we have this for some r < k r<k r < k . Note that as 1 , r ∈ A 2 1,r\in A_2 1 , r ∈ A 2 we have that − r − 1 ∈ A 1 -r-1\in A_1 − r − 1 ∈ A 1 ; and as − r , − 1 ∈ A 1 -r,-1\in A_1 − r , − 1 ∈ A 1 we have that r + 1 ∈ A 2 r+1\in A_2 r + 1 ∈ A 2 . This completes the induction.
Hence A 1 = { − k , … , − 1 } A_1=\{-k,\ldots,-1\} A 1 = { − k , … , − 1 } , A 2 = { 0 , … , k } A_2=\{0,\ldots,k\} A 2 = { 0 , … , k } , A 3 = { k + 1 , … , 2 k + 1 } A_3=\{k+1,\ldots,2k+1\} A 3 = { k + 1 , … , 2 k + 1 } . This concludes the proof of uniqueness.
This concludes the proof of uniqueness in all cases.
Theorem 1.8. Up to multiplication by a constant and permutation of parts, there exist exactly two valid partitions of Z 5 \mathbb{Z}_5 Z 5 , namely ( { 2 , 3 } , { 4 } , { 0 , 1 } ) (\{2,3\},\{4\},\{0,1\}) ({ 2 , 3 } , { 4 } , { 0 , 1 }) and ( { 2 , 3 } , { 1 , 4 } , { 0 } ) (\{2,3\},\{1,4\},\{0\}) ({ 2 , 3 } , { 1 , 4 } , { 0 }) .
Proof. Regard a partition as a colouring
χ : Z 5 → { 1 , 2 , 3 } . \chi:\mathbb{Z}_5\to\{1,2,3\}. χ : Z 5 → { 1 , 2 , 3 } .
Since ( 1 , 2 , 2 ) (1,2,2) ( 1 , 2 , 2 ) , ( 2 , 4 , 4 ) (2,4,4) ( 2 , 4 , 4 ) , ( 4 , 3 , 3 ) (4,3,3) ( 4 , 3 , 3 ) , and ( 3 , 1 , 1 ) (3,1,1) ( 3 , 1 , 1 ) are nontrivial zero-sum triples,
χ ( 1 ) ≠ χ ( 2 ) , χ ( 2 ) ≠ χ ( 4 ) , χ ( 4 ) ≠ χ ( 3 ) , χ ( 3 ) ≠ χ ( 1 ) . \chi(1)\ne\chi(2),\qquad\chi(2)\ne\chi(4),\qquad\chi(4)\ne\chi(3),\qquad\chi(3)\ne\chi(1). χ ( 1 ) = χ ( 2 ) , χ ( 2 ) = χ ( 4 ) , χ ( 4 ) = χ ( 3 ) , χ ( 3 ) = χ ( 1 ) .
Thus each element in { ± 1 } \{\pm1\} { ± 1 } cannot share a colour with each element in { ± 2 } \{\pm2\} { ± 2 } . Since only 3 colours are available, one of these sets must be monochromatic. By multiplying by 2 and permuting the parts if necessary,
χ ( 2 ) = χ ( 3 ) = 1. \chi(2)=\chi(3)=1. χ ( 2 ) = χ ( 3 ) = 1.
Since ( 0 , 2 , 3 ) (0,2,3) ( 0 , 2 , 3 ) is a nontrivial zero-sum triple, we also have that χ ( 0 ) ≠ 1 \chi(0)\ne1 χ ( 0 ) = 1 , so χ ( 0 ) = 3 \chi(0)=3 χ ( 0 ) = 3 without loss of generality. Since ( 0 , 1 , 4 ) (0,1,4) ( 0 , 1 , 4 ) is also a nontrivial zero-sum triple, χ ( 1 ) \chi(1) χ ( 1 ) and χ ( 4 ) \chi(4) χ ( 4 ) cannot both be 3. Thus, by multiplying by − 1 -1 − 1 if necessary, the given partitions are the only possible options. It is easy to check that both of these are indeed valid. □
Proof of essential arity theorem
Theorem 4.18. For p ≥ 7 p \ge7 p ≥ 7 prime, every function in Pol ( 2 ) ( Eqn ∗ ( Z p ) , NAE 3 ) ∣ Z p ∗ \operatorname{Pol}^{(2)}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_3)|_{\mathbb{Z}_p^*} Pol ( 2 ) ( Eqn ∗ ( Z p ) , NAE 3 ) ∣ Z p ∗ is nonconstant and essentially unary.
This section will contain three parts. First, a set of technical preliminaries. Next, a general proof of our theorem for the case p ≥ 11 p \ge11 p ≥ 11 . Unfortunately this proof fails for the case p = 7 p = 7 p = 7 , which we treat separately in the last part.
Technical Preliminaries
For every prime p ≥ 7 p \ge7 p ≥ 7 , let
h p : Z p → [ 3 ] , h p ( x ) = 1 + ⌊ 3 x p ⌋ h_p:\mathbb{Z}_p \to[3], \qquad h_p(x)=1+\left\lfloor\frac{3x}{p}\right\rfloor h p : Z p → [ 3 ] , h p ( x ) = 1 + ⌊ p 3 x ⌋
where x x x is represented by an integer in { 0 , … , p − 1 } \{0,\ldots,p-1\} { 0 , … , p − 1 } . By Theorem 1.7, h p h_p h p is, up to scaling its input and permuting the colours, the unique homomorphism from Eqn ∗ ( Z p ) \operatorname{Eqn}^{*}(\mathbb{Z}_p) Eqn ∗ ( Z p ) to NAE 3 \operatorname{NAE}_3 NAE 3 .
Lemma E.1. Let p p p be an odd prime. Pick disjoint sets C , E ⊆ Z p C,E \subseteq\mathbb{Z}_p C , E ⊆ Z p such that
C + C 2 ⊆ C ∪ E . \frac{C+C}{2} \subseteq C \cup E. 2 C + C ⊆ C ∪ E . Then either ∣ C ∣ ≤ ∣ E ∣ + 1 |C| \le|E|+1 ∣ C ∣ ≤ ∣ E ∣ + 1 or C = Z p ∖ E C=\mathbb{Z}_p\setminus E C = Z p ∖ E .
Proof. The hypothesis gives ∣ C + C ∣ ≤ ∣ C ∣ + ∣ E ∣ |C+C| \le|C|+|E| ∣ C + C ∣ ≤ ∣ C ∣ + ∣ E ∣ . By the Cauchy–Davenport theorem (the conclusion is immediate if C = ∅ C=\varnothing C = ∅ ), ∣ C + C ∣ ≥ min ( p , 2 ∣ C ∣ − 1 ) |C+C| \ge\min(p,2|C|-1) ∣ C + C ∣ ≥ min ( p , 2∣ C ∣ − 1 ) . If the minimum is 2 ∣ C ∣ − 1 2|C|-1 2∣ C ∣ − 1 , then ∣ C ∣ ≤ ∣ E ∣ + 1 |C| \le|E|+1 ∣ C ∣ ≤ ∣ E ∣ + 1 . If it is p p p , then p ≤ ∣ C ∣ + ∣ E ∣ ≤ p p \le|C|+|E| \le p p ≤ ∣ C ∣ + ∣ E ∣ ≤ p ; hence equality holds and the disjoint sets C , E C,E C , E partition Z p \mathbb{Z}_p Z p . □ \square □
Definition E.2. For an odd prime p p p , we say that a set C ⊆ Z p ∗ C \subseteq\mathbb{Z}_p^* C ⊆ Z p ∗ is midpoint-closed if, for any r , s ∈ C r,s \in C r , s ∈ C with r + s ≠ 0 r+s \ne0 r + s = 0 , we have r + s 2 ∈ C \frac{r+s}{2} \in C 2 r + s ∈ C .
Corollary E.3. Let p p p be an odd prime. If C ⊆ Z p ∗ C \subseteq\mathbb{Z}_p^* C ⊆ Z p ∗ is midpoint closed and admits elements a , b ∈ Z p ∗ a,b \in\mathbb{Z}_p^* a , b ∈ Z p ∗ with a ≠ ± b a \ne\pm b a = ± b , then C = Z p ∗ C=\mathbb{Z}_p^* C = Z p ∗ .
Proof. Pick such a , b ∈ C a,b \in C a , b ∈ C . By assumption, a , b , a + b 2 a,b,\frac{a+b}{2} a , b , 2 a + b are distinct and are all in C C C , hence ∣ C ∣ ≥ 3 |C| \ge3 ∣ C ∣ ≥ 3 . The conclusion follows by Lemma E.1 with E = { 0 } E=\{0\} E = { 0 } .
Lemma E.4. Let p ≥ 7 p \ge7 p ≥ 7 prime and let k = ⌊ p 3 ⌋ k=\left\lfloor\frac{p}{3}\right\rfloor k = ⌊ 3 p ⌋ , S = { 1 , … , k } S=\{1,\ldots,k\} S = { 1 , … , k } , M = Z p ∗ ∖ ( S ∪ − S ) M=\mathbb{Z}_p^*\setminus(S\cup-S) M = Z p ∗ ∖ ( S ∪ − S ) . Equivalently, S = h p − 1 ( 1 ) ∖ { 0 } S=h_p^{-1}(1)\setminus\{0\} S = h p − 1 ( 1 ) ∖ { 0 } , M = h p − 1 ( 2 ) M=h_p^{-1}(2) M = h p − 1 ( 2 ) , − S = h p − 1 ( 3 ) -S=h_p^{-1}(3) − S = h p − 1 ( 3 ) . Then for d , c ∈ Z p ∗ d,c\in\mathbb{Z}_p^* d , c ∈ Z p ∗ :
(i) If d S ∩ ( − S ) = ∅ dS\cap(-S)=\varnothing d S ∩ ( − S ) = ∅ , then d ∈ { 1 , 2 , p + 1 2 } d\in\left\{1,2,\frac{p+1}{2}\right\} d ∈ { 1 , 2 , 2 p + 1 } .
(ii) If c M ∩ M = ∅ cM\cap M=\varnothing c M ∩ M = ∅ , then (i) c ∈ { ± 2 , ± 1 2 } c\in\left\{\pm2,\pm\frac{1}{2}\right\} c ∈ { ± 2 , ± 2 1 } if p ≠ 13 p\ne13 p = 13 , or (ii) c ∈ { ± 2 , ± 1 2 , ± 5 } c\in\left\{\pm2,\pm\frac{1}{2},\pm5\right\} c ∈ { ± 2 , ± 2 1 , ± 5 } if p = 13 p=13 p = 13 .
(iii) If c M = M cM=M c M = M , then c ∈ { ± 1 } c\in\{\pm1\} c ∈ { ± 1 } .
We prove each point separately.
Proof of Lemma E.4 (i). Suppose d ∉ { 1 , 2 , p + 1 2 } d\notin\left\{1,2,\frac{p+1}{2}\right\} d ∈ / { 1 , 2 , 2 p + 1 } . In the following, d d d is taken to be its representative within 1 , … , p − 1 1,\ldots,p-1 1 , … , p − 1 .
Case 3 ≤ d < p / 3 3\le d<p/3 3 ≤ d < p /3 . Then ⌊ p / d ⌋ ∈ S \lfloor p/d\rfloor\in S ⌊ p / d ⌋ ∈ S , and − d ⌊ p / d ⌋ ∈ S -d\lfloor p/d\rfloor\in S − d ⌊ p / d ⌋ ∈ S , contradicting the assumption d S ∩ ( − S ) = ∅ dS\cap(-S)=\varnothing d S ∩ ( − S ) = ∅ .
Case p / 3 < d ≤ ( p − 1 ) / 2 p/3<d\le(p-1)/2 p /3 < d ≤ ( p − 1 ) /2 . Then 2 , − 2 d ∈ S 2,-2d\in S 2 , − 2 d ∈ S , likewise leading to a contradiction. Case ( p + 3 ) / 2 ≤ d < 2 p / 3 (p+3)/2 \le d < 2p/3 ( p + 3 ) /2 ≤ d < 2 p /3 . This interval is empty for p = 7 p=7 p = 7 , so we may assume p ≥ 11 p \ge11 p ≥ 11 . Let a = 2 d − p a=2d-p a = 2 d − p and n = 2 ⌊ k / a ⌋ + 1 n=2\lfloor k/a\rfloor+1 n = 2 ⌊ k / a ⌋ + 1 . By a simple computation we have n ∈ S n \in S n ∈ S and p − 2 k ≤ n a < p p-2k \le na < p p − 2 k ≤ na < p . Since n n n is odd and d = ( p + a ) / 2 d=(p+a)/2 d = ( p + a ) /2 ,
− n d = − n p − n a 2 = − n + 1 2 p + p − n a 2 ≡ p − n a 2 ( m o d p ) -nd=\frac{-np-na}{2}=-\frac{n+1}{2}p+\frac{p-na}{2}\equiv\frac{p-na}{2}\pmod p − n d = 2 − n p − na = − 2 n + 1 p + 2 p − na ≡ 2 p − na ( mod p )
Using the inequality for n a na na , we finally have 0 < − n d ≤ k 0<-nd\le k 0 < − n d ≤ k and hence − n d ∈ S -nd\in S − n d ∈ S .
Case 2 p / 3 < d < p 2p/3<d<p 2 p /3 < d < p . Then 1 , − d ∈ S 1,-d\in S 1 , − d ∈ S .
Proof of Lemma E.4 (iii). If c M = M cM=M c M = M , then squaring and taking the difference we have
( c 2 − 1 ) ∑ x ∈ M x 2 = 0. (c^2-1)\sum_{x\in M}x^2=0. ( c 2 − 1 ) x ∈ M ∑ x 2 = 0.
The total sum of squares in Z p \mathbb{Z}_p Z p is ( p − 1 ) p ( 2 p − 1 ) 6 ≡ 0 \frac{(p-1)p(2p-1)}{6}\equiv0 6 ( p − 1 ) p ( 2 p − 1 ) ≡ 0 , hence as Z p ∗ ∖ M = { ± 1 , … , ± k } \mathbb{Z}_p^*\setminus M=\{\pm1,\ldots,\pm k\} Z p ∗ ∖ M = { ± 1 , … , ± k } we have
∑ x ∈ M x 2 = − 2 ∑ j = 1 k j 2 = − k ( k + 1 ) ( 2 k + 1 ) 3 ≠ 0 ( m o d p ) . \sum_{x\in M}x^2=-2\sum_{j=1}^{k}j^2=-\frac{k(k+1)(2k+1)}{3}\ne0\pmod p. x ∈ M ∑ x 2 = − 2 j = 1 ∑ k j 2 = − 3 k ( k + 1 ) ( 2 k + 1 ) = 0 ( mod p ) .
Thus c 2 = 1 c^2=1 c 2 = 1 , proving item (3).
Proof of Lemma E.4 (ii). Since M = − M M=-M M = − M , we have ( − c ) M = c M (-c)M=cM ( − c ) M = c M . Thus, after replacing c c c by − c -c − c if necessary, we may assume 1 ≤ c ≤ p − 1 2 1\le c\le\frac{p-1}{2} 1 ≤ c ≤ 2 p − 1 . We first deal directly with p = 7 , 11 , 13 p=7,11,13 p = 7 , 11 , 13 . Multiplying M M M by each possible value of c c c in the specified interval yields:
Table 1.
Noting that 3 ≡ − 1 2 ( m o d 7 ) 3\equiv-\frac{1}{2}\pmod7 3 ≡ − 2 1 ( mod 7 ) , 5 ≡ − 1 2 ( m o d 11 ) 5\equiv-\frac{1}{2}\pmod{11} 5 ≡ − 2 1 ( mod 11 ) and 6 ≡ − 1 2 ( m o d 13 ) 6\equiv-\frac{1}{2}\pmod{13} 6 ≡ − 2 1 ( mod 13 ) completes the proof for this case.
Now, let p ≥ 17 p\ge17 p ≥ 17 and c M ∩ M = ∅ cM\cap M=\varnothing c M ∩ M = ∅ , so c M ⊆ S ∪ ( − S ) cM\subseteq S\cup(-S) c M ⊆ S ∪ ( − S ) . Write m = ∣ M ∣ m=|M| m = ∣ M ∣ . For i = 1 , … , m i=1,\ldots,m i = 1 , … , m , let x i x_i x i be the representative of c ( k + i ) c(k+i) c ( k + i ) in the interval [ − k , k ] [-k,k] [ − k , k ] . Since x i + 1 − x i ∈ [ − 2 k , 2 k ] x_{i+1}-x_i\in[-2k,2k] x i + 1 − x i ∈ [ − 2 k , 2 k ] for i = 1 , … , m − 1 i=1,\ldots,m-1 i = 1 , … , m − 1 , we have x i + 1 − x i ∈ { c , c − p } x_{i+1}-x_i\in\{c,c-p\} x i + 1 − x i ∈ { c , c − p } . We now split in cases depending on whether c ≤ m c\le m c ≤ m or c ≥ m + 1 c\ge m+1 c ≥ m + 1 .
Case c ≤ m c\le m c ≤ m . Since p − m = 2 k + 1 p-m=2k+1 p − m = 2 k + 1 , the value c − p c-p c − p is strictly smaller than − 2 k -2k − 2 k , so we must have x i + 1 − x i = c x_{i+1}-x_i=c x i + 1 − x i = c for all i = 1 , … , m − 1 i=1,\ldots,m-1 i = 1 , … , m − 1 . Hence by a telescoping sum, ( m − 1 ) c = x m − x 1 ≤ 2 k (m-1)c=x_m-x_1\le2k ( m − 1 ) c = x m − x 1 ≤ 2 k ; since m ∈ { k , k + 1 } m\in\{k,k+1\} m ∈ { k , k + 1 } , this implies c ≤ 2 c\le2 c ≤ 2 . Since of course M = 1 M M=1M M = 1 M , we must have c = 2 c=2 c = 2 .
Case c ≥ m + 1 c\ge m+1 c ≥ m + 1 . As m ≥ k m\ge k m ≥ k , we have c > k c>k c > k , and since c ≤ p − 1 2 c\le\frac{p-1}{2} c ≤ 2 p − 1 , we also have c − p < − k c-p<-k c − p < − k . Thus, for the x i x_i x i 's to stay in [ − k , k ] [-k,k] [ − k , k ] , the increments x i + 1 − x i x_{i+1}-x_i x i + 1 − x i must alternate between c c c and c − p c-p c − p .
Put q = p − 2 c q=p-2c q = p − 2 c , so q q q is a positive odd integer. Since m = p − 1 − 2 k m=p-1-2k m = p − 1 − 2 k is even, put L = m 2 − 1 L=\frac{m}{2}-1 L = 2 m − 1 . The two parity subsequences have common difference − q -q − q , and hence x m − 1 = x 1 − L q x_{m-1}=x_1-Lq x m − 1 = x 1 − L q and x m = x 2 − L q x_m=x_2-Lq x m = x 2 − L q . As all the x i x_i x i lie in [ − k , k ] [-k,k] [ − k , k ] , we obtain
2 k ≥ max { x 1 , x 2 } − min { x m − 1 , x m } = ∣ x 2 − x 1 ∣ + L q ≥ c + L q , \begin{aligned}
2k&\ge\max\{x_1,x_2\}-\min\{x_{m-1},x_m\}\\
&=|x_2-x_1|+Lq\\
&\ge c+Lq,
\end{aligned} 2 k ≥ max { x 1 , x 2 } − min { x m − 1 , x m } = ∣ x 2 − x 1 ∣ + L q ≥ c + L q ,
where the final inequality uses x 2 − x 1 ∈ { c , c − p } x_2-x_1\in\{c,c-p\} x 2 − x 1 ∈ { c , c − p } and c ≤ p − c c\le p-c c ≤ p − c . Now c = ( p − q ) / 2 c=(p-q)/2 c = ( p − q ) /2 , so p + ( m − 3 ) q ≤ 4 k p+(m-3)q\le4k p + ( m − 3 ) q ≤ 4 k . Since p = 3 m ± 1 p=3m\pm1 p = 3 m ± 1 and 2 k + m = p − 1 2k+m=p-1 2 k + m = p − 1 , we have 2 k = 2 m − 1 ± 1 2k=2m-1\pm1 2 k = 2 m − 1 ± 1 . Substituting into p + ( m − 3 ) q ≤ 4 k p+(m-3)q\le4k p + ( m − 3 ) q ≤ 4 k , we get
3 m ± 1 + ( m − 3 ) q ≤ 4 m − 2 ± 2 , 3m\pm1+(m-3)q\le4m-2\pm2, 3 m ± 1 + ( m − 3 ) q ≤ 4 m − 2 ± 2 ,
where the ± \pm ± signs are the same on both sides. This implies ( m − 3 ) q ≤ m − 2 ± 1 (m-3)q \le m-2 \pm1 ( m − 3 ) q ≤ m − 2 ± 1 .
As p ≥ 17 p \ge17 p ≥ 17 , we have m ≥ 6 m \ge6 m ≥ 6 . Since q q q is a positive odd integer, the inequality forces q = 1 q=1 q = 1 . Therefore
c = p − q 2 = p − 1 2 . c=\frac{p-q}{2}=\frac{p-1}{2}. c = 2 p − q = 2 p − 1 .
Restricted binary polymorphisms for p ≥ 11 p \ge11 p ≥ 11
Throughout this subsection, let p ≥ 11 p \ge11 p ≥ 11 be an odd prime, and let k = ⌊ p / 3 ⌋ k=\lfloor p/3\rfloor k = ⌊ p /3 ⌋ . Let τ \tau τ be the permutation swapping 2 and 3. Below we let x ⊕ y x\oplus y x ⊕ y denote addition modulo 2; of course τ x ⊕ y = τ x ∘ τ y \tau^{x\oplus y}=\tau^x\circ\tau^y τ x ⊕ y = τ x ∘ τ y . Let f ∈ Pol ( 2 ) ( Eqn ∗ ( Z p ) , NAE 3 ) ∣ Z p ∗ f\in\operatorname{Pol}^{(2)}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_3)|_{\mathbb{Z}_p^{*}} f ∈ Pol ( 2 ) ( Eqn ∗ ( Z p ) , NAE 3 ) ∣ Z p ∗ . Choose f ~ ∈ Pol ( 2 ) ( Eqn ∗ ( Z p ) , NAE 3 ) \tilde{f}\in\operatorname{Pol}^{(2)}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_3) f ~ ∈ Pol ( 2 ) ( Eqn ∗ ( Z p ) , NAE 3 ) whose restriction to Z p ∗ \mathbb{Z}_p^{*} Z p ∗ is f f f . After simultaneously scaling both inputs and permuting the colours, we may assume by the classification of valid partitions that f ~ ( t , t ) = h p ( t ) \tilde{f}(t,t)=h_p(t) f ~ ( t , t ) = h p ( t ) for every t ∈ Z p t\in\mathbb{Z}_p t ∈ Z p .
For each r ∈ Z p ∗ r\in\mathbb{Z}_p^{*} r ∈ Z p ∗ , the map t ↦ f ~ ( t , r t ) t\mapsto\tilde{f}(t,rt) t ↦ f ~ ( t , r t ) is a homomorphism Eqn ∗ ( Z p ) → NAE 3 \operatorname{Eqn}^{*}(\mathbb{Z}_p)\to\operatorname{NAE}_3 Eqn ∗ ( Z p ) → NAE 3 sending 0 to 1. Hence, by the classification of valid partitions, for every r ∈ Z p ∗ r\in\mathbb{Z}_p^{*} r ∈ Z p ∗ , there exist
P r ∈ ( Z p ∗ ) 2 , ε ( r ) ∈ { 0 , 1 } , P_r\in(\mathbb{Z}_p^{*})^2,\qquad\varepsilon(r)\in\{0,1\}, P r ∈ ( Z p ∗ ) 2 , ε ( r ) ∈ { 0 , 1 } ,
where P r P_r P r has slope r r r (meaning P r = ( x , r x ) P_r=(x,rx) P r = ( x , r x ) for some x ∈ Z p ∗ x\in\mathbb{Z}_p^{*} x ∈ Z p ∗ ), such that
f ( t P r ) = τ ε ( r ) h p ( t ) ( t ∈ Z p ∗ ) . f(tP_r)=\tau^{\varepsilon(r)}h_p(t)\qquad(t\in\mathbb{Z}_p^{*}). f ( t P r ) = τ ε ( r ) h p ( t ) ( t ∈ Z p ∗ ) .
Note that since f ( x , x ) = h p ( x ) f(x,x)=h_p(x) f ( x , x ) = h p ( x ) for every x ∈ Z p ∗ x\in\mathbb{Z}_p^{*} x ∈ Z p ∗ , we have P 1 = ( 1 , 1 ) P_1=(1,1) P 1 = ( 1 , 1 ) and ε ( 1 ) = 0 \varepsilon(1)=0 ε ( 1 ) = 0 .
We want to show that f f f is essentially unary. Equivalently:
ε ( r ) = 0 \varepsilon(r)=0 ε ( r ) = 0 for all r r r and
either P r = ( 1 , r ) P_r=(1,r) P r = ( 1 , r ) for all r r r or P r = ( r − 1 , 1 ) P_r=(r^{-1},1) P r = ( r − 1 , 1 ) for all r r r .
First we need to prove some more lemmas. Since p = 13 p=13 p = 13 is in some sense special, it will be useful to define
D : = { { 1 , 2 , 1 2 } , if p ≠ 13 , { 1 , 2 , 1 2 , 5 } , if p = 13. D:=\begin{cases}
\{1,2,\frac{1}{2}\}, & \text{if }p\ne13,\\
\{1,2,\frac{1}{2},5\}, & \text{if }p=13.
\end{cases} D := { { 1 , 2 , 2 1 } , { 1 , 2 , 2 1 , 5 } , if p = 13 , if p = 13.
Lemma E.5. Let p ≥ 11 p\ge11 p ≥ 11 prime and r , s ∈ Z p ∗ r,s\in\mathbb{Z}_p^{*} r , s ∈ Z p ∗ . Define α : ± D → { 0 , 1 } \alpha:\pm D\to\{0,1\} α : ± D → { 0 , 1 } , α ( ± 1 ) = 1 \alpha(\pm1)=1 α ( ± 1 ) = 1 , α ( x ) = 0 \alpha(x)=0 α ( x ) = 0 otherwise.
(i) Suppose P r + P s ∈ ( Z p ∗ ) 2 P_r+P_s\in(\mathbb{Z}_p^{*})^2 P r + P s ∈ ( Z p ∗ ) 2 , and let q , d ∈ Z p ∗ q,d\in\mathbb{Z}_p^{*} q , d ∈ Z p ∗ be such that P r + P s = d P q P_r+P_s=dP_q P r + P s = d P q . Then d ∈ { 1 , 2 , 1 2 } d\in\{1,2,\frac{1}{2}\} d ∈ { 1 , 2 , 2 1 } and
ε ( r ) = ε ( s ) = : e ⟹ ε ( q ) = e ⊕ α ( d ) . \varepsilon(r)=\varepsilon(s)=:e\mathrel{\Longrightarrow}\varepsilon(q)=e\oplus\alpha(d). ε ( r ) = ε ( s ) =: e ⟹ ε ( q ) = e ⊕ α ( d ) . (ii) Suppose P r − P s ∈ ( Z p ∗ ) 2 P_r-P_s\in(\mathbb{Z}_p^{*})^2 P r − P s ∈ ( Z p ∗ ) 2 , and let q , c ∈ Z p ∗ q,c\in\mathbb{Z}_p^{*} q , c ∈ Z p ∗ be such that P r − P s = c P q P_r-P_s=cP_q P r − P s = c P q . Then
ε ( r ) = ε ( s ) = : e ⟹ c ∈ ± D and ε ( q ) = e ⊕ α ( c ) . \varepsilon(r)=\varepsilon(s)=:e\mathrel{\Longrightarrow}c\in\pm D\text{ and }\varepsilon(q)=e\oplus\alpha(c). ε ( r ) = ε ( s ) =: e ⟹ c ∈ ± D and ε ( q ) = e ⊕ α ( c ) .
Proof of Lemma E.5 (i). Since P r + P s − d P q = ( 0 , 0 ) P_r+P_s-dP_q=(0,0) P r + P s − d P q = ( 0 , 0 ) , we have:
( f ( t P r ) , f ( t P s ) , f ( − d t P q ) ) = ( τ ε ( r ) h p ( t ) , τ ε ( s ) h p ( t ) , τ ε ( q ) h p ( − d t ) ) ∈ NAE 3 \bigl(f(tP_r),f(tP_s),f(-dtP_q)\bigr)
=\bigl(\tau^{\varepsilon(r)}h_p(t),\tau^{\varepsilon(s)}h_p(t),\tau^{\varepsilon(q)}h_p(-dt)\bigr)\in\operatorname{NAE}_3 ( f ( t P r ) , f ( t P s ) , f ( − d t P q ) ) = ( τ ε ( r ) h p ( t ) , τ ε ( s ) h p ( t ) , τ ε ( q ) h p ( − d t ) ) ∈ NAE 3
for all t ∈ Z p ∗ t\in\mathbb{Z}_p^{*} t ∈ Z p ∗ . In particular, taking t ∈ S t\in S t ∈ S , we get by Lemma E.4 (i) that d ∈ { 1 , 2 , p + 1 2 } d\in\{1,2,\frac{p+1}{2}\} d ∈ { 1 , 2 , 2 p + 1 } .
If ε ( r ) = ε ( s ) = : e \varepsilon(r)=\varepsilon(s)=:e ε ( r ) = ε ( s ) =: e , we get τ e ⊕ ε ( q ) h p ( − d t ) ≠ h p ( t ) \tau^{e\oplus\varepsilon(q)}h_p(-dt)\ne h_p(t) τ e ⊕ ε ( q ) h p ( − d t ) = h p ( t ) for all t ∈ Z p ∗ t\in\mathbb{Z}_p^{*} t ∈ Z p ∗ . Now, consider possible values of ( d , ε ( q ) ) (d,\varepsilon(q)) ( d , ε ( q )) . ( 2 , e ) (2,e) ( 2 , e ) is valid from the zero-sum triple ( t , t , − 2 t ) (t,t,-2t) ( t , t , − 2 t ) , and ( 1 / 2 , e ) (1/2,e) ( 1/2 , e ) from ( − t / 2 , − t / 2 , t ) (-t/2,-t/2,t) ( − t /2 , − t /2 , t ) . Also τ h p ( − t ) ≠ h p ( t ) \tau h_p(-t)\ne h_p(t) τ h p ( − t ) = h p ( t ) for every t ≠ 0 t\ne0 t = 0 , as is immediate from the three intervals defining h p h_p h p . The remaining tuples ( 1 , e ) (1,e) ( 1 , e ) , ( 2 , 1 ⊕ e ) (2,1\oplus e) ( 2 , 1 ⊕ e ) , and ( 1 2 , 1 ⊕ e ) (\frac{1}{2},1\oplus e) ( 2 1 , 1 ⊕ e ) fail respectively by taking t t t in h p − 1 ( 2 ) h_p^{-1}(2) h p − 1 ( 2 ) , t = 1 2 t=\frac{1}{2} t = 2 1 , and t = − 1 t=-1 t = − 1 . □ \square □
Proof of Lemma E.5 (ii). Assume ε ( r ) = ε ( s ) ≔ e \varepsilon(r)=\varepsilon(s)\coloneqq e ε ( r ) = ε ( s ) : = e . Since P r − P s − c P q = ( 0 , 0 ) P_r-P_s-cP_q=(0,0) P r − P s − c P q = ( 0 , 0 ) , we have:
( f ( t P r ) , f ( − t P s ) , f ( − c t P q ) ) = ( τ e h p ( t ) , τ e h p ( − t ) , τ ε ( q ) h p ( − c t ) ) ∈ N A E 3 \left(f(tP_r),f(-tP_s),f(-ctP_q)\right)=\left(\tau^e h_p(t),\tau^e h_p(-t),\tau^{\varepsilon(q)}h_p(-ct)\right)\in\mathrm{NAE}_3 ( f ( t P r ) , f ( − t P s ) , f ( − c t P q ) ) = ( τ e h p ( t ) , τ e h p ( − t ) , τ ε ( q ) h p ( − c t ) ) ∈ NAE 3
for all t t t . Taking t ∈ M t\in M t ∈ M , we get that h p ( t ) = h p ( − t ) h_p(t)=h_p(-t) h p ( t ) = h p ( − t ) , hence (replacing t t t by − t -t − t ) τ e ⊕ ε ( q ) h p ( c t ) ≠ h p ( t ) \tau^{e\oplus\varepsilon(q)}h_p(ct)\ne h_p(t) τ e ⊕ ε ( q ) h p ( c t ) = h p ( t ) .
If e ⊕ ε ( q ) = 0 e\oplus\varepsilon(q)=0 e ⊕ ε ( q ) = 0 , the tuple implies c M ∩ M = ∅ cM\cap M=\varnothing c M ∩ M = ∅ , so Lemma E.4 (ii) gives c ∈ { ± 2 , ± 1 / 2 } c\in\{\pm2,\pm1/2\} c ∈ { ± 2 , ± 1/2 } for p ≠ 13 p\ne13 p = 13 and c ∈ { ± 2 , ± 1 / 2 , ± 5 } c\in\{\pm2,\pm1/2,\pm5\} c ∈ { ± 2 , ± 1/2 , ± 5 } for p = 13 p=13 p = 13 , i.e. c ∈ ± D c\in\pm D c ∈ ± D .
If e ⊕ ε ( q ) = 1 e\oplus\varepsilon(q)=1 e ⊕ ε ( q ) = 1 , it implies that the symmetric set c M = − c M cM=-cM c M = − c M avoids h p − 1 ( 3 ) = − S h_p^{-1}(3)=-S h p − 1 ( 3 ) = − S . If c M cM c M met S S S , symmetry would make it meet − S -S − S as well. Thus, c M cM c M contains neither 0 0 0 nor any point of S ∪ ( − S ) S\cup(-S) S ∪ ( − S ) , and therefore c M ⊆ M cM\subseteq M c M ⊆ M . Equal cardinalities give c M = M cM=M c M = M , and Lemma E.4 (iii) gives c = ± 1 ∈ ± D c=\pm1\in\pm D c = ± 1 ∈ ± D .
Lemma E.6. Let p ≥ 11 p\ge11 p ≥ 11 and define for a ∈ D a\in D a ∈ D
ϕ a ( t ) ≔ τ α ( a ) h p ( a t ) . \phi_a(t)\coloneqq\tau^{\alpha(a)}h_p(at). ϕ a ( t ) : = τ α ( a ) h p ( a t ) . For every a , b ∈ D a,b\in D a , b ∈ D , there is t ∈ Z p ∗ t\in\mathbb{Z}_p^* t ∈ Z p ∗ such that
ϕ a ( t ) = ϕ b ( t ) = h p ( − 2 t ) . \phi_a(t)=\phi_b(t)=h_p(-2t). ϕ a ( t ) = ϕ b ( t ) = h p ( − 2 t ) .
Proof. This follows by case exhaustion. Write p = 6 n ± 1 p=6n\pm1 p = 6 n ± 1 . We calculate:
It remains to consider p = 13 p=13 p = 13 and the pairs involving 5 5 5 . Since 1 2 = 7 \frac{1}{2}=7 2 1 = 7 in Z 13 \mathbb{Z}_{13} Z 13 , we can calculate:
Lemma E.7. Assume p ≥ 11 p\ge11 p ≥ 11 . If ε ( r ) = ε ( s ) ≔ e \varepsilon(r)=\varepsilon(s)\coloneqq e ε ( r ) = ε ( s ) : = e , then for P = P r = ( P x , P y ) P=P_r=(P_x,P_y) P = P r = ( P x , P y ) and Q = P s = ( Q x , Q y ) Q=P_s=(Q_x,Q_y) Q = P s = ( Q x , Q y ) we have
P x = ± Q x or P y = ± Q y . P_x=\pm Q_x\quad\text{or}\quad P_y=\pm Q_y. P x = ± Q x or P y = ± Q y .
Proof. Suppose that neither coordinate of P = P r P=P_r P = P r agrees up to sign with the corresponding coordinate of Q = P s Q=P_s Q = P s . This means that the sums P + Q P+Q P + Q and P − Q P-Q P − Q have no zero coefficients. Hence we may apply Lemma E.5 to deduce that P + Q = d R P+Q=dR P + Q = d R and P − Q = ± c T P-Q=\pm cT P − Q = ± c T for some R = P v R=P_v R = P v , T = P u T=P_u T = P u , d ∈ { 1 , 2 , 1 2 } d\in\{1,2,\frac{1}{2}\} d ∈ { 1 , 2 , 2 1 } , c ∈ D c\in D c ∈ D . Furthermore, ε ( v ) ⊕ e = α ( d ) \varepsilon(v)\oplus e=\alpha(d) ε ( v ) ⊕ e = α ( d ) , ε ( u ) ⊕ e = α ( c ) \varepsilon(u)\oplus e=\alpha(c) ε ( u ) ⊕ e = α ( c ) .
Let d R + c T = 2 X dR+cT=2X d R + c T = 2 X ; note X ∈ { P , Q } X\in\{P,Q\} X ∈ { P , Q } . Apply Lemma E.6 to c c c and d d d to yield t t t . After applying τ e \tau^e τ e to all three colours, the zero-sum triple t d R + t c T − 2 t X = 0 tdR+tcT-2tX=0 t d R + t c T − 2 tX = 0 is mapped to ( ϕ d ( t ) , ϕ c ( t ) , h p ( − 2 t ) ) (\phi_d(t),\phi_c(t),h_p(-2t)) ( ϕ d ( t ) , ϕ c ( t ) , h p ( − 2 t )) by f f f , which is monochromatic. This is a contradiction.
Theorem E.8. Let p ≥ 11 p\ge11 p ≥ 11 prime and f f f , ε ( r ) \varepsilon(r) ε ( r ) , P r P_r P r be as described at the start of this subsection. Then
ε ( r ) = 0 \varepsilon(r)=0 ε ( r ) = 0 for every r ∈ Z p ∗ r\in\mathbb{Z}_p^* r ∈ Z p ∗ , and
either P r = ( 1 , r ) P_r=(1,r) P r = ( 1 , r ) for every r ∈ Z p ∗ r\in\mathbb{Z}_p^* r ∈ Z p ∗ , or P r = ( r − 1 , 1 ) P_r=(r^{-1},1) P r = ( r − 1 , 1 ) for every r ∈ Z p ∗ r\in\mathbb{Z}_p^* r ∈ Z p ∗ .
Equivalently, f f f is essentially unary.
We will devote the remainder of the section to proving this theorem. Let us first give a schematic overview of the proof. We begin by creating a family of (two) graphs derived from the polymorphisms we are studying, with edges induced by the P r P_r P r ’s. We deduce that each such graph is bipartite and its edges intersect pairwise; hence it is a star, which enforces consistency (in some sense) between the edges within each graph. We then prove in stages that in fact only one graph within our family has any edges at all. The final step is to decode one such star into a coordinate unambiguously.
Stage 1: Graph representation. Let Z p ∗ / { ± 1 } \mathbb{Z}_p^*/\{\pm1\} Z p ∗ / { ± 1 } be Z p ∗ \mathbb{Z}_p^* Z p ∗ quotiented by sign, writing [ x ] [x] [ x ] for the equivalence class { x , − x } \{x,-x\} { x , − x } . For each e ∈ { 0 , 1 } e \in\{0,1\} e ∈ { 0 , 1 } , define the bipartite graph G e G_e G e with vertex set two copies of Z p ∗ / { ± 1 } \mathbb{Z}_p^*/\{\pm1\} Z p ∗ / { ± 1 } and edge set
{ ( [ x ] , [ y ] ) ∣ ∃ r ∈ ε − 1 ( e ) : P r = ( x , y ) } . \{([x],[y]) \mid\exists r \in\varepsilon^{-1}(e): P_r=(x,y)\}. {([ x ] , [ y ]) ∣ ∃ r ∈ ε − 1 ( e ) : P r = ( x , y )} .
Note that every P r P_r P r induces an edge in precisely one graph G e G_e G e , namely in G ε ( r ) G_{\varepsilon(r)} G ε ( r ) . By Lemma E.7 , any two edges of G e G_e G e are incident. A pairwise-intersecting family of edges in a bipartite graph has a common vertex — any intersecting family of edges is either a star or a triangle, and the triangle is not bipartite. Thus G e G_e G e is a star, together with possibly some isolated vertices.
Choose e ∈ { 0 , 1 } e \in\{0,1\} e ∈ { 0 , 1 } such that, if we take A = ε − 1 ( e ) A=\varepsilon^{-1}(e) A = ε − 1 ( e ) , B = ε − 1 ( e ⊕ 1 ) B=\varepsilon^{-1}(e\oplus1) B = ε − 1 ( e ⊕ 1 ) , then we have ∣ A ∣ ≥ ∣ B ∣ |A| \ge|B| ∣ A ∣ ≥ ∣ B ∣ . In particular, we then have ∣ A ∣ ≥ p − 1 2 > 0 |A| \ge\frac{p-1}{2} > 0 ∣ A ∣ ≥ 2 p − 1 > 0 . Consider the graph G e G_e G e , and assume without loss of generality that the star has its central vertex on the left side of G e G_e G e . (If it is on the right side, this can be fixed by swapping coordinates of f f f , which swaps coordinates of every P r P_r P r and thus also swaps the sides of G e G_e G e .) Letting [ γ ] [\gamma] [ γ ] be this central vertex, we see that every P r P_r P r with r ∈ A r \in A r ∈ A is of the form ± γ ( 1 , r ) \pm\gamma(1,r) ± γ ( 1 , r ) . For each r ∈ A r \in A r ∈ A , choose δ r ∈ { ± 1 } \delta_r \in\{\pm1\} δ r ∈ { ± 1 } such that P r = δ r γ ( 1 , r ) P_r=\delta_r\gamma(1,r) P r = δ r γ ( 1 , r ) .
Stage 2: Characterising B B B . Set T = { r ∈ B ∣ P r = ± 2 γ ( 1 , r ) } T=\{r \in B \mid P_r=\pm2\gamma(1,r)\} T = { r ∈ B ∣ P r = ± 2 γ ( 1 , r )} . Our proof will first show that this set must be small, then it will show that in fact T = B T=B T = B . For r ∈ T r \in T r ∈ T define δ r ∈ { ± 1 } \delta_r \in\{\pm1\} δ r ∈ { ± 1 } so that P r = 2 δ r γ ( 1 , r ) P_r=2\delta_r\gamma(1,r) P r = 2 δ r γ ( 1 , r ) . We shall use the following simple consequence of Lemma E.5 .
Corollary E.9. Suppose ε ( q ) = ε ( s ) \varepsilon(q)=\varepsilon(s) ε ( q ) = ε ( s ) and P q ± P s = c P m ∈ ( Z p ∗ ) 2 P_q\pm P_s=cP_m\in(\mathbb{Z}_p^*)^2 P q ± P s = c P m ∈ ( Z p ∗ ) 2 . Furthermore, suppose ε ( q ) ≠ ε ( m ) \varepsilon(q)\ne\varepsilon(m) ε ( q ) = ε ( m ) . Then c = ± 1 c=\pm1 c = ± 1 .
Claim E.10. T T T intersects at most one set of the form { ± x } \{\pm x\} { ± x } , and hence ∣ T ∣ ≤ 2 |T|\le2 ∣ T ∣ ≤ 2 .
Proof. Suppose for contradiction that there exist r , r ′ ∈ T r,r'\in T r , r ′ ∈ T with r ≠ ± r ′ r\ne\pm r' r = ± r ′ . These induce lines P r P_r P r and P r ′ P_{r'} P r ′ , which in turn induce the edges ( [ 2 γ ] , [ 2 γ r ] ) ([2\gamma],[2\gamma r]) ([ 2 γ ] , [ 2 γ r ]) and ( [ 2 γ ] , [ 2 γ r ′ ] ) ([2\gamma],[2\gamma r']) ([ 2 γ ] , [ 2 γ r ′ ]) within G e ⊕ 1 G_{e\oplus1} G e ⊕ 1 . These edges share a left endpoint (but not a right endpoint) — hence G e ⊕ 1 G_{e\oplus1} G e ⊕ 1 is a star with its central vertex at the shared vertex [ 2 γ ] [2\gamma] [ 2 γ ] . But then every r ∈ B r\in B r ∈ B satisfies P r = ± 2 γ ( 1 , r ) P_r=\pm2\gamma(1,r) P r = ± 2 γ ( 1 , r ) , and thus B = T B=T B = T .
We now show T T T is midpoint-closed: consider q , s ∈ T q,s\in T q , s ∈ T with q + s ≠ 0 q+s\ne0 q + s = 0 , and take m = q + s 2 ∈ Z p ∗ m=\frac{q+s}{2}\in\mathbb{Z}_p^* m = 2 q + s ∈ Z p ∗ . Observe
P q + δ q δ s P s = 4 δ q γ ( 1 , m ) = c P m , P_q+\delta_q\delta_sP_s=4\delta_q\gamma(1,m)=cP_m, P q + δ q δ s P s = 4 δ q γ ( 1 , m ) = c P m ,
for some constant c c c (since at this point we already know that P m P_m P m is either ± γ ( 1 , m ) \pm\gamma(1,m) ± γ ( 1 , m ) or ± 2 γ ( 1 , m ) \pm2\gamma(1,m) ± 2 γ ( 1 , m ) ). Assume for contradiction that m ∈ A m\in A m ∈ A , hence ε ( m ) = e \varepsilon(m)=e ε ( m ) = e and P m = ± γ ( 1 , m ) P_m=\pm\gamma(1,m) P m = ± γ ( 1 , m ) . Then we are exactly in the situation from Corollary E.9 and we deduce c = ± 1 c=\pm1 c = ± 1 . This implies ± γ ( 1 , m ) = P m = ± 4 γ ( 1 , m ) \pm\gamma(1,m)=P_m=\pm4\gamma(1,m) ± γ ( 1 , m ) = P m = ± 4 γ ( 1 , m ) , hence ± 1 = ± 4 \pm1=\pm4 ± 1 = ± 4 , impossible in Z p ∗ \mathbb{Z}_p^* Z p ∗ for p ≥ 11 p\ge11 p ≥ 11 .
Thus T T T is midpoint-closed. Since it contains r , r ′ r,r' r , r ′ with r ≠ ± r ′ r\ne\pm r' r = ± r ′ , Corollary E.3 gives T = Z p ∗ T=\mathbb{Z}_p^* T = Z p ∗ , contradicting A ≠ ∅ A\ne\varnothing A = ∅ . Hence T T T intersects at most 1 set of the form { ± x } \{\pm x\} { ± x } .
Claim E.11. A + A 2 ⊆ A ∪ T ∪ { 0 } \frac{A+A}{2}\subseteq A\cup T\cup\{0\} 2 A + A ⊆ A ∪ T ∪ { 0 } .
Proof. Let r , s ∈ A r,s\in A r , s ∈ A with r + s ≠ 0 r+s\ne0 r + s = 0 , and put m = r + s 2 ∈ Z p ∗ m=\frac{r+s}{2}\in\mathbb{Z}_p^* m = 2 r + s ∈ Z p ∗ . Then
P r + δ r δ s P s = 2 δ r γ ( 1 , m ) = c P m P_r+\delta_r\delta_sP_s=2\delta_r\gamma(1,m)=cP_m P r + δ r δ s P s = 2 δ r γ ( 1 , m ) = c P m
for some constant c c c . If ε ( m ) = e \varepsilon(m)=e ε ( m ) = e , then m ∈ A m\in A m ∈ A . Otherwise, Corollary E.9 gives c = ± 1 c=\pm1 c = ± 1 , hence P m = ± 2 γ ( 1 , m ) P_m=\pm2\gamma(1,m) P m = ± 2 γ ( 1 , m ) and m ∈ T m\in T m ∈ T . Allowing also the case r + s = 0 r+s=0 r + s = 0 , we deduce A + A 2 ⊆ A ∪ T ∪ { 0 } \frac{A+A}{2}\subseteq A\cup T\cup\{0\} 2 A + A ⊆ A ∪ T ∪ { 0 } .
Proof. Apply Lemma E.1 with C = A C=A C = A and E = T ∪ { 0 } E=T\cup\{0\} E = T ∪ { 0 } . We deduce that either ∣ A ∣ ≤ ∣ T ∣ + 2 |A|\leq|T|+2 ∣ A ∣ ≤ ∣ T ∣ + 2 or A ∪ T = Z p ∗ A\cup T=\mathbb{Z}_p^* A ∪ T = Z p ∗ . But the first alternative is impossible: ∣ T ∣ ≤ 2 |T|\leq2 ∣ T ∣ ≤ 2 and thus ∣ T ∣ + 2 ≤ 4 |T|+2\leq4 ∣ T ∣ + 2 ≤ 4 , yet ∣ A ∣ ≥ p − 1 2 ≥ 5 |A|\geq\frac{p-1}{2}\geq5 ∣ A ∣ ≥ 2 p − 1 ≥ 5 . Thus A A A and T T T partition Z p ∗ \mathbb{Z}_p^* Z p ∗ . Since also A A A and B B B partition Z p ∗ \mathbb{Z}_p^* Z p ∗ , it follows B = T B=T B = T .
Stage 3: Eliminating B B B . We next show that B = ∅ B=\varnothing B = ∅ . First, partition A A A in terms of the signs of the first coordinate, i.e. for δ ∈ { ± 1 } \delta\in\{\pm1\} δ ∈ { ± 1 } , define
A δ = { r ∈ A ∣ P r = δ γ ( 1 , r ) } = { r ∈ A ∣ δ r = δ } . A_\delta=\{r\in A\mid P_r=\delta\gamma(1,r)\}=\{r\in A\mid\delta r=\delta\}. A δ = { r ∈ A ∣ P r = δ γ ( 1 , r )} = { r ∈ A ∣ δ r = δ } .
Claim E.13. B = ∅ B=\varnothing B = ∅ . Hence Z p ∗ = A = A + ∪ A − \mathbb{Z}_p^*=A=A_+\cup A_- Z p ∗ = A = A + ∪ A − .
Proof. Suppose otherwise, and choose q ∈ T = B q\in T=B q ∈ T = B . Write δ = δ q \delta=\delta_q δ = δ q , so that P q = 2 δ γ ( 1 , q ) P_q=2\delta\gamma(1,q) P q = 2 δ γ ( 1 , q ) . We first claim that ∣ A δ ∣ ≥ 2 |A_\delta|\geq2 ∣ A δ ∣ ≥ 2 . Otherwise, ∣ A − δ ∣ ≥ ∣ A ∣ − 1 = p − 2 − ∣ T ∣ ≥ p − 4 > p 2 |A_{-\delta}|\geq|A|-1=p-2-|T|\geq p-4>\frac p2 ∣ A − δ ∣ ≥ ∣ A ∣ − 1 = p − 2 − ∣ T ∣ ≥ p − 4 > 2 p . Hence, by Cauchy–Davenport, A − δ + A − δ = Z p A_{-\delta}+A_{-\delta}=\mathbb{Z}_p A − δ + A − δ = Z p , so there exist r , s ∈ A − δ r,s\in A_{-\delta} r , s ∈ A − δ such that r + s = 2 q r+s=2q r + s = 2 q . But then
P r + P s = − 2 δ γ ( 1 , q ) = − P q . P_r+P_s=-2\delta\gamma(1,q)=-P_q. P r + P s = − 2 δ γ ( 1 , q ) = − P q .
contradicting Lemma E.5 (i). We may therefore choose r ∈ A δ r\in A_\delta r ∈ A δ with r ≠ − 2 q r\neq-2q r = − 2 q . Put u = 2 q + r 3 ∈ Z p ∗ u=\frac{2q+r}{3}\in\mathbb{Z}_p^* u = 3 2 q + r ∈ Z p ∗ . Then
P q + P r = 3 δ γ ( 1 , u ) = d P u . P_q+P_r=3\delta\gamma(1,u)=dP_u. P q + P r = 3 δ γ ( 1 , u ) = d P u .
If u ∈ A u\in A u ∈ A , comparison of first coordinates gives d = ± 3 d=\pm3 d = ± 3 , whereas if u ∈ B = T u\in B=T u ∈ B = T , it gives d = ± 3 2 d=\pm\frac32 d = ± 2 3 . This contradicts Lemma E.5 (i): ± 3 \pm3 ± 3 and ± 3 2 \pm\frac32 ± 2 3 are not equivalent modulo p ≥ 11 p\geq11 p ≥ 11 to 1 1 1 , 2 2 2 , 1 2 \frac12 2 1 . Therefore B = ∅ B=\varnothing B = ∅ .
:::
Stage 4: Eliminating one of A + A_+ A + and A − A_- A − and decoding. We start by showing that A + A_+ A + and A − A_- A − are midpoint closed.
Claim E.14. For δ = ± 1 \delta=\pm1 δ = ± 1 , A δ A_\delta A δ is midpoint-closed.
Proof. Take r , s ∈ A δ r,s\in A_\delta r , s ∈ A δ with r + s ≠ 0 r+s\neq0 r + s = 0 . Setting m = r + s 2 m=\frac{r+s}{2} m = 2 r + s , we have
P r + P s = 2 δ γ ( 1 , m ) = d P m . P_r+P_s=2\delta\gamma(1,m)=dP_m. P r + P s = 2 δ γ ( 1 , m ) = d P m .
Since B = ∅ B=\varnothing B = ∅ , we have m ∈ A m\in A m ∈ A , and P m = ± γ ( 1 , m ) P_m=\pm\gamma(1,m) P m = ± γ ( 1 , m ) . Thus 2 δ γ ( 1 , m ) = ± d γ ( 1 , m ) 2\delta\gamma(1,m)=\pm d\gamma(1,m) 2 δ γ ( 1 , m ) = ± d γ ( 1 , m ) and d = ± 2 d=\pm2 d = ± 2 . Conversely, by Lemma E.5 (i) we have d ∈ { 1 , 2 , 1 2 } d\in\{1,2,\frac12\} d ∈ { 1 , 2 , 2 1 } , and as p ≥ 11 p\geq11 p ≥ 11 this implies d = 2 d=2 d = 2 . Thus P m = δ γ ( 1 , m ) P_m=\delta\gamma(1,m) P m = δ γ ( 1 , m ) , and m ∈ A δ m\in A_\delta m ∈ A δ .
At least one of A + A_+ A + and A − A_- A − contains two elements which are not equal up to sign. Indeed, otherwise each A δ A_\delta A δ would have size at most 2, giving ∣ Z p ∗ ∣ ≤ 2 + 2 = 4 |\mathbb{Z}_p^*|\leq2+2=4 ∣ Z p ∗ ∣ ≤ 2 + 2 = 4 , a contradiction. By Corollary E.3 , this A δ A_\delta A δ equals Z p ∗ \mathbb{Z}_p^* Z p ∗ . Thus we deduce the following fact.
Fact E.15. For some δ ∈ { ± 1 } \delta\in\{\pm1\} δ ∈ { ± 1 } , we have P r = δ γ ( 1 , r ) P_r=\delta\gamma(1,r) P r = δ γ ( 1 , r ) for all r ∈ Z p ∗ r\in\mathbb{Z}_p^* r ∈ Z p ∗ , or P r = δ γ ( r − 1 , 1 ) P_r=\delta\gamma(r^{-1},1) P r = δ γ ( r − 1 , 1 ) for all r ∈ Z p ∗ r\in\mathbb{Z}_p^* r ∈ Z p ∗ . Furthermore, ε ( r ) = 0 \varepsilon(r)=0 ε ( r ) = 0 for all r ∈ Z p ∗ r\in\mathbb{Z}_p^* r ∈ Z p ∗ .
Proof. Since P 1 = ( 1 , 1 ) P_1=(1,1) P 1 = ( 1 , 1 ) and ε ( 1 ) = 0 \varepsilon(1)=0 ε ( 1 ) = 0 , we obtain δ γ = 1 \delta\gamma=1 δ γ = 1 and e = 0 e=0 e = 0 . Thus, if we did not interchange coordinates earlier, we have P r = ( 1 , r ) P_r=(1,r) P r = ( 1 , r ) and ε ( r ) = 0 \varepsilon(r)=0 ε ( r ) = 0 for all r ∈ Z p ∗ r\in\mathbb{Z}_p^* r ∈ Z p ∗ . Conversely, if we did interchange coordinates we have P r = ( r − 1 , 1 ) P_r=(r^{-1},1) P r = ( r − 1 , 1 ) and again ε ( r ) = 0 \varepsilon(r)=0 ε ( r ) = 0 for all r ∈ Z p ∗ r\in\mathbb{Z}_p^* r ∈ Z p ∗ .
Let us now briefly argue this implies that the operations are essentially unary. If P r = δ γ ( 1 , r ) P_r=\delta\gamma(1,r) P r = δ γ ( 1 , r ) , for ( x , y ) ∈ ( Z p ∗ ) 2 (x,y)\in(\mathbb{Z}_p^*)^2 ( x , y ) ∈ ( Z p ∗ ) 2 , taking r = y / x r=y/x r = y / x gives ( x , y ) = x P r (x,y)=xP_r ( x , y ) = x P r and hence f ( x , y ) = h p ( x ) f(x,y)=h_p(x) f ( x , y ) = h p ( x ) . If P r = δ γ ( r − 1 , 1 ) P_r=\delta\gamma(r^{-1},1) P r = δ γ ( r − 1 , 1 ) again with r = y / x r=y/x r = y / x we have ( x , y ) = y P r (x,y)=yP_r ( x , y ) = y P r and hence f ( x , y ) = h p ( y ) f(x,y)=h_p(y) f ( x , y ) = h p ( y ) . Thus f f f is essentially unary.
Restricted binary polymorphisms for p = 7 p = 7 p = 7
Much of the setup of this section will be similar to the previous one — we redo it to refresh the reader’s memory. Let τ \tau τ be as in the preceding subsection, and let f ∈ Pol ( 2 ) ( Eqn ∗ ( Z 7 ) , NAE 3 ) ∣ ( Z 7 ∗ ) 2 f \in\operatorname{Pol}^{(2)}(\operatorname{Eqn}^{*}(\mathbb{Z}_7),\operatorname{NAE}_3)|_{(\mathbb{Z}_7^{*})^2} f ∈ Pol ( 2 ) ( Eqn ∗ ( Z 7 ) , NAE 3 ) ∣ ( Z 7 ∗ ) 2 . Choose f ~ ∈ Pol ( 2 ) ( Eqn ∗ ( Z 7 ) , NAE 3 ) \tilde{f} \in\operatorname{Pol}^{(2)}(\operatorname{Eqn}^{*}(\mathbb{Z}_7),\operatorname{NAE}_3) f ~ ∈ Pol ( 2 ) ( Eqn ∗ ( Z 7 ) , NAE 3 ) whose restriction to ( Z 7 ∗ ) 2 (\mathbb{Z}_7^{*})^2 ( Z 7 ∗ ) 2 is f f f . As in the preceding subsection, after simultaneously scaling both inputs and permuting the colours, we may assume that
f ~ ( t , t ) = h 7 ( t ) ( t ∈ Z 7 ) . \tilde{f}(t,t) = h_7(t) \qquad(t \in\mathbb{Z}_7). f ~ ( t , t ) = h 7 ( t ) ( t ∈ Z 7 ) .
For every r ∈ Z 7 ∗ r \in\mathbb{Z}_7^{*} r ∈ Z 7 ∗ , the map t ↦ f ~ ( t , r t ) t \mapsto\tilde{f}(t,rt) t ↦ f ~ ( t , r t ) is a homomorphism from Eqn ∗ ( Z 7 ) \operatorname{Eqn}^{*}(\mathbb{Z}_7) Eqn ∗ ( Z 7 ) to NAE 3 \operatorname{NAE}_3 NAE 3 which sends 0 0 0 to 1 1 1 . Hence, by the classification of valid partitions, there exist
P r ∈ ( Z 7 ∗ ) 2 , ε ( r ) ∈ { 0 , 1 } , P_r \in(\mathbb{Z}_7^{*})^2,\qquad\varepsilon(r) \in\{0,1\}, P r ∈ ( Z 7 ∗ ) 2 , ε ( r ) ∈ { 0 , 1 } ,
where P r P_r P r has slope r r r , such that
f ( t P r ) = τ ε ( r ) h 7 ( t ) ( t ∈ Z 7 ∗ ) . f(tP_r) = \tau^{\varepsilon(r)}h_7(t) \qquad(t \in\mathbb{Z}_7^{*}). f ( t P r ) = τ ε ( r ) h 7 ( t ) ( t ∈ Z 7 ∗ ) .
Write P r = a r − 1 ( 1 , r ) P_r = a_r^{-1}(1,r) P r = a r − 1 ( 1 , r ) for some a r ∈ Z 7 ∗ a_r \in\mathbb{Z}_7^{*} a r ∈ Z 7 ∗ . Equivalently,
f ( t , r t ) = τ ε ( r ) h 7 ( a r t ) ( t ∈ Z 7 ∗ ) . f(t,rt) = \tau^{\varepsilon(r)}h_7(a_rt) \qquad(t \in\mathbb{Z}_7^{*}). f ( t , r t ) = τ ε ( r ) h 7 ( a r t ) ( t ∈ Z 7 ∗ ) .
The diagonal normalisation allows us to take
a 1 = 1 , ε ( 1 ) = 0. a_1 = 1,\qquad\varepsilon(1) = 0. a 1 = 1 , ε ( 1 ) = 0.
Thus, on each of the other five lines through the origin, the restriction of f f f is one of the twelve distinct maps
t ⟼ τ e h 7 ( a t ) , ( a , e ) ∈ Z 7 ∗ × { 0 , 1 } . t \longmapsto\tau^e h_7(at),\qquad(a,e) \in\mathbb{Z}_7^{*} \times\{0,1\}. t ⟼ τ e h 7 ( a t ) , ( a , e ) ∈ Z 7 ∗ × { 0 , 1 } .
Claim E.16. Suppose that, for every r ∈ Z 7 ∗ r \in\mathbb{Z}_7^{*} r ∈ Z 7 ∗ , we choose ( a r , e r ) ∈ Z 7 ∗ × { 0 , 1 } (a_r,e_r) \in\mathbb{Z}_7^{*} \times\{0,1\} ( a r , e r ) ∈ Z 7 ∗ × { 0 , 1 } , with ( a 1 , e 1 ) = ( 1 , 0 ) (a_1,e_1) = (1,0) ( a 1 , e 1 ) = ( 1 , 0 ) , and define
g ( t , r t ) = τ e r h 7 ( a r t ) ( r , t ∈ Z 7 ∗ ) . g(t,rt) = \tau^{e_r}h_7(a_rt) \qquad(r,t \in\mathbb{Z}_7^{*}). g ( t , r t ) = τ e r h 7 ( a r t ) ( r , t ∈ Z 7 ∗ ) . If g : Eqn ∗ ( Z 7 ) 2 ∣ ( Z 7 ∗ ) 2 → NAE 3 g \colon\operatorname{Eqn}^{*}(\mathbb{Z}_7)^2|_{(\mathbb{Z}_7^{*})^2} \to\operatorname{NAE}_3 g : Eqn ∗ ( Z 7 ) 2 ∣ ( Z 7 ∗ ) 2 → NAE 3 , then exactly one of the following holds:
( a r , e r ) = ( 1 , 0 ) (a_r,e_r) = (1,0) ( a r , e r ) = ( 1 , 0 ) for every r ∈ Z 7 ∗ r \in\mathbb{Z}_7^{*} r ∈ Z 7 ∗ ;
( a r , e r ) = ( r , 0 ) (a_r,e_r) = (r,0) ( a r , e r ) = ( r , 0 ) for every r ∈ Z 7 ∗ r \in\mathbb{Z}_7^{*} r ∈ Z 7 ∗ .
Proof. We prove the claim by exhaustion using the Python script in Listing 1, which was implemented with GPT-5.6 Sol (cf. AI methodology). Lines 3–13 of Listing 1 construct the set
T Y P E S = Z 7 ∗ × { 0 , 1 } \mathsf{TYPES} = \mathbb{Z}_7^{*} \times\{0,1\} TYPES = Z 7 ∗ × { 0 , 1 }
and, for each ( a , e ) ∈ T Y P E S (a,e) \in\mathsf{TYPES} ( a , e ) ∈ TYPES , store the values of the map
t ⟼ τ e h 7 ( a t ) t \longmapsto\tau^e h_7(at) t ⟼ τ e h 7 ( a t )
in RAY_VALUES[(a,e)]. Line 13 verifies that these twelve maps are distinct. Lines 14–26 identify a point u = ( x , y ) ∈ ( Z 7 ∗ ) 2 u=(x,y) \in(\mathbb{Z}_7^{*})^2 u = ( x , y ) ∈ ( Z 7 ∗ ) 2 with its ray coordinates ( r , t ) = ( y / x , x ) (r,t)=(y/x,x) ( r , t ) = ( y / x , x ) and construct the set
{ ( u 1 , u 2 , u 3 ) ∈ ( ( Z 7 ∗ ) 2 ) 3 | u 1 + u 2 + u 3 = ( 0 , 0 ) } \left\{(u_1,u_2,u_3) \in((\mathbb{Z}_7^{*})^2)^3 \mathrel{\middle|} u_1+u_2+u_3=(0,0)\right\} { ( u 1 , u 2 , u 3 ) ∈ (( Z 7 ∗ ) 2 ) 3 u 1 + u 2 + u 3 = ( 0 , 0 ) }
up to permutation. There are 168 such three-element multisets, where repetitions of points are allowed; this count is printed on line 42. For a tuple
c h o i c e = ( ( a 1 , e 1 ) , … , ( a 6 , e 6 ) ) , \mathit{choice}=((a_1,e_1),\ldots,(a_6,e_6)), choice = (( a 1 , e 1 ) , … , ( a 6 , e 6 )) ,
::: lines 28–33 evaluate g ( t , r t ) g(t,rt) g ( t , r t ) using RAY_VALUES[(a_r,e_r)] and test that all 168 triples are mapped nonmonochromatically. There are 12 5 = 248 832 12^5 = 248\,832 1 2 5 = 248 832 choices after fixing ( a 1 , e 1 ) = ( 1 , 0 ) (a_1,e_1)=(1,0) ( a 1 , e 1 ) = ( 1 , 0 ) . Lines 35–39 exhaustively test all of them. The assertion on line 41 checks that the only two which pass all 168 constraints are
( ( a r , e r ) ) r = 1 6 = ( ( 1 , 0 ) , ( 1 , 0 ) , ( 1 , 0 ) , ( 1 , 0 ) , ( 1 , 0 ) , ( 1 , 0 ) ) , ((a_r,e_r))_{r=1}^{6}=((1,0),(1,0),(1,0),(1,0),(1,0),(1,0)), (( a r , e r ) ) r = 1 6 = (( 1 , 0 ) , ( 1 , 0 ) , ( 1 , 0 ) , ( 1 , 0 ) , ( 1 , 0 ) , ( 1 , 0 )) ,
( ( a r , e r ) ) r = 1 6 = ( ( 1 , 0 ) , ( 2 , 0 ) , ( 3 , 0 ) , ( 4 , 0 ) , ( 5 , 0 ) , ( 6 , 0 ) ) , ((a_r,e_r))_{r=1}^{6}=((1,0),(2,0),(3,0),(4,0),(5,0),(6,0)), (( a r , e r ) ) r = 1 6 = (( 1 , 0 ) , ( 2 , 0 ) , ( 3 , 0 ) , ( 4 , 0 ) , ( 5 , 0 ) , ( 6 , 0 )) ,
which are precisely the two choices in the statement.
Theorem E.17. Every function in Pol ( 2 ) ( Eqn ∗ ( Z 7 ) , NAE 3 ) ∣ Z 7 \operatorname{Pol}^{(2)}(\operatorname{Eqn}^{*}(\mathbb{Z}_7),\operatorname{NAE}_3)|_{\mathbb{Z}_7} Pol ( 2 ) ( Eqn ∗ ( Z 7 ) , NAE 3 ) ∣ Z 7 is essentially unary.
Proof. Apply Claim E.16 to the parameters above. In the first case, for ( x , y ) ∈ ( Z 7 ∗ ) 2 (x,y)\in(\mathbb{Z}_7^*)^2 ( x , y ) ∈ ( Z 7 ∗ ) 2 , put r = y / x r=y/x r = y / x and t = x t=x t = x . Then
f ( x , y ) = f ( t , r t ) = h 7 ( t ) = h 7 ( x ) . f(x,y)=f(t,rt)=h_7(t)=h_7(x). f ( x , y ) = f ( t , r t ) = h 7 ( t ) = h 7 ( x ) . In the second case, the same substitution gives
f ( x , y ) = f ( t , r t ) = h 7 ( r t ) = h 7 ( y ) . f(x,y)=f(t,rt)=h_7(rt)=h_7(y). f ( x , y ) = f ( t , r t ) = h 7 ( r t ) = h 7 ( y ) . Thus the normalised function f f f depends on only one coordinate. Undoing the simultaneous scaling of the inputs and the permutation of the colours preserves this property, so the original function is essentially unary as well. □ \square □
Listing 1: Complete dependency-free Python verification of Claim E.16 .
from itertools import product
P = 7; U = range(1, P)
# The twelve possible maps t -> tau^e(h_7(a*t)).
def h_P(x):
return 1 + (3 * (x % P)) // P
TAU = (0, 1, 3, 2)
TYPES = list(product(U, (0, 1)))
RAY_VALUES = {
(a, e): tuple((TAU[h_P(a * t)] if e else h_P(a * t)) for t in U)
for a, e in TYPES
}
assert len(set(RAY_VALUES.values())) == (P-1)*2
# The unordered triples in (Z_7^*)^2 which sum to (0,0).
def ray_coordinates(u):
x, y = u
return y * pow(x, -1, P) % P, x
POINTS = set(product(U, repeat=2))
TRIPLES = set()
for u in POINTS:
for v in POINTS:
w = ((-u[0] - v[0]) % P, (-u[1] - v[1]) % P)
if w in POINTS:
TRIPLES.add(tuple(sorted((u, v, w))))
CONSTRAINTS = [tuple(ray_coordinates(u) for u in c) for c in TRIPLES]
# Test whether all triples are mapped nonmonochromatically.
def colour(choice, point):
r, t = point
return RAY_VALUES[choice[r - 1]][t - 1]
def is_valid(choice):
return all(len({colour(choice, u) for u in c}) > 1 for c in CONSTRAINTS)
# Fix (a_1,e_1)=(1,0) and exhaust the remaining 12^5 choices.
SOLUTIONS = []
for tail in product(TYPES, repeat=P-2):
choice = ((1, 0),) + tail
if is_valid(choice):
SOLUTIONS.append(choice)
EXPECTED = [((1, 0),) * 6, tuple((r, 0) for r in U)]
assert SOLUTIONS == EXPECTED
print("constraints:", len(CONSTRAINTS), "search space:", len(TYPES)**5)
print(*SOLUTIONS, sep="\n")
Acknowledgements. Nakajima thanks Amey Bhangale for pointing out the connection between Abelian embeddings and reconfigurability, and Demian Banakh for useful discussions.
AI methodology. LLMs were used for proving the hardness side of our results. Nakajima used Opus 4.8, Opus 5, Sonnet 5, and DeepSeek interactively to help understand the combinatorics of our problems. (e.g. writing SAT code, searching for useful properties). Verwimp also used GPT-5.6 Sol to assist in proving Theorem 4.18 . Following an iterative exchange and prompts by Verwimp to use Theorem 1.7, the model found the proof for primes p ≥ 11 p \ge11 p ≥ 11 presented in Appendix § 9 . ChatGPT was also used to reimplement the self-contained p = 7 p = 7 p = 7 verification in Listing 1. The models above also helped with a literature search. ChatGPT was also used to improve the presentation of the paper, including the generation of the figure; and to look for typos and minor errors. The authors take full responsibility for the final text.
References