Definition 2.1

Given a set of signatures \(\mathcal {F}\), we define the counting problem \(\operatorname {Holant}(\mathcal {F})\) as:

Theorem 2.2 (Valiant’s Holant Theorem 45)

If \(T \in \mathbb {C}^{2 \times 2}\) is an invertible matrix, then we have \(\operatorname {Holant}({\Omega }; \mathcal {F} \mid \mathcal {G}) = \operatorname {Holant}({\Omega }^{\prime }; \mathcal {F} T \mid T^{-1} \mathcal {G})\).

Theorem 2.3 (Theorem 2.6 in 17)

If \(T \in \mathbf {O}_{2}(\mathbb {C})\) is an orthogonal matrix (i.e. TT^T = I₂), then \(\operatorname {Holant}({\Omega }; \mathcal {F}) = \operatorname {Holant}({\Omega }^{\prime }; T \mathcal {F})\).

Definition 2.4

We say a signature set \(\mathcal {F}\) is \({\mathscr{C}}\)-transformable if there exists a \(T \in \mathbf {GL}_{2}(\mathbb {C})\) such that \([1,0,1] T^{\otimes 2} \in {\mathscr{C}}\) and \(\mathcal {F} \subseteq T {\mathscr{C}}\).

Definition 2.5 (Definition 3.1 in 18)

Definition 2.6 (Definition 3.3 in 18)

A function is of product type if it can be expressed as a product of unary functions, binary equality functions ([1,0,1]), and binary disequality functions ([0,1,0]). We use \({\mathscr{P}}\) to denote the set of product-type functions.

Matchgate Signatures

Matchgates were introduced by Valiant [42, 43] to give polynomial-time algorithms for a collection of counting problems over planar graphs. As the name suggests, problems expressible by matchgates can be reduced to computing a weighted sum of perfect matchings. The latter problem is tractable over planar graphs by Kasteleyn’s algorithm [30], a.k.a. the FKT algorithm [29, 41]. These counting problems are naturally expressed in the Holant framework using matchgate signatures. We use \({\mathscr{M}}\) to denote the set of all matchgate signatures; thus \(\operatorname {Pl-Holant}({\mathscr{M}})\) is tractable. The function \([0,1,0,\dots ,0]\) of arity k belongs to \({\mathscr{M}}\), and is called the ExactOne_k function. More generally, we can define \({\text {\sc ExactOne}_{k: {a_{1}, \ldots , a_{k}}}}\) as a weighted version of ExactOne_k, which takes value a_i if the input has Hamming weight 1 and x_i = 1; the function outputs 0 on all other inputs. This function also belongs to \({\mathscr{M}}\).

Holographic transformations extend the reach of the FKT algorithm even further, as stated below.

Theorem 2.7

Let \(\mathcal {F}\) be any set of complex-valued signatures in Boolean variables. If \(\mathcal {F}\) is \({\mathscr{M}}\)-transformable, then \(\operatorname {Pl-Holant}(\mathcal {F})\) is computable in polynomial time.

Proposition 2.8

Definition 2.9

Proposition 2.10

Vanishing Signatures

Vanishing signatures were first introduced in [25] in the parity setting to denote signatures for which the Holant value is always 0 modulo 2.

Definition 2.11

A set of signatures \(\mathcal {F}\) is called vanishing if the value \(\operatorname {Holant}_{\Omega }(\mathcal {F})\) is 0 for every signature grid Ω. A signature f is called vanishing if the singleton set {f} is vanishing.

Definition 2.12 (Definition 17, p. 1683 in 11)

If f cannot be expressed as such a symmetrization form, we define vd⁺(f) = 0. If f is the all zero signature, define vd⁺(f) = n + 1.

We define negative vanishing degree vd⁻ similarly, using − i instead of i.

Definition 2.13 (Definition 18, p. 1684 in 11)

For σ ∈{+,−}, we define \({\mathscr{V}}^{\sigma } = \{f | 2 \operatorname {vd}^{\sigma }(f) > \operatorname {arity}(f)\}\).

Lemma 2.14 (Lemma 29, p.1690 in 11)

For a symmetric signature f of arity n, σ ∈{+,−}, and an orthogonal matrix \(T \in \mathbb {C}^{2 \times 2}\), vd^σ(f) is either vd^σ(T^⊗nf) or vd^−σ(T^⊗nf).

Theorem 2.15 (Theorem 26, p. 1689 in 11)

Let \(\mathcal {F}\) be a set of symmetric signatures. Then \(\mathcal {F}\) is vanishing if and only if \(\mathcal {F} \subseteq {\mathscr{V}}^{+}\) or \(\mathcal {F} \subseteq {\mathscr{V}}^{-}\).

Definition 2.16 (Definition 20, p. 1684 in 11)

Definition 2.17 (Definition 21, p. 1684 in 11)

For a nonzero symmetric signature f of arity n, it is of positive (resp. negative) recurrence degreet ≤ n, denoted by rd⁺(f) = t (resp. rd⁻(f) = t), if and only if \(f \in {\mathscr{R}}^{+}_{t+1} - {\mathscr{R}}^{+}_{t}\) (resp. \(f \in {\mathscr{R}}^{-}_{t+1} - {\mathscr{R}}^{-}_{t}\)). If f is the all zero signature, we define rd⁺(f) = rd⁻(f) = − 1.

Corollary 2.18 (Corollary 23, p. 1686 in [11])

If f is a symmetric signature and σ ∈{+,−}, then vd^σ(f) + rd^σ(f) = arity(f).

Lemma 2.19 (Lemma 30, p. 1690 of 11)

Suppose f is a symmetric signature of arity n. Let \(\hat {f} = (Z^{-1})^{\otimes n} f\). If rd⁺(f) = d, then \(\hat {f} = [\hat {f}_{0}, \hat {f}_{1}, \dotsc , \hat {f}_{d}, 0, \dotsc , 0]\) and \(\hat {f}_{d} \ne 0\). Also \(f \in {\mathscr{R}}_{d}^{+}\) iff all nonzero entries of \(\hat {f}\) are among the first d entries in its symmetric signature notation.

Similarly, if rd⁻(f) = d, then \(\hat {f} = [0, \dotsc , 0, \hat {f}_{n-d}, \dotsc , \hat {f}_{n}]\) and \(\hat {f}_{n-d} \ne 0\). Also \(f\in {\mathscr{R}}_{d}^{-}\) iff all nonzero entries of \(\hat {f}\) are among the last d entries in its symmetric signature notation.

Lemma 2.20 (Lemma 65, p. 1724 in 11)

for any \(v \in \mathbb {C}\).

Theorem 2.21 (Theorem 31, p. 1691 in 11)

Theorem 2.22

Corollary 2.23 (Lemma 5.5 in [26])

Let \(v \in \mathbb {C}\). If v≠ 0, then Pl-Holant ([v,1,0,0,0]) is #P-hard.

Theorem 2.24

Theorem 1

Theorem 2.25 (Theorem 9.3 in 26)

Let \(\mathcal {F}\) be any set of symmetric, complex-valued signatures in Boolean variables. Then \(\operatorname {Pl-\#CSP}(\mathcal {F})\) is #P-hard unless \(\mathcal {F} \subseteq {\mathscr{A}}\), \(\mathcal {F} \subseteq {\mathscr{P}}\), or \(\mathcal {F} \subseteq \widehat {{\mathscr{M}}}\), in which case the problem is computable in polynomial time.

Definition 2.26 (Definition 32, p. 1692 in 11)

A 4-by-4 matrix is redundant if its middle two rows and middle two columns are the same.

Definition 2.27 (Definition 33, p. 1693 in 11)

where g^wxyz is the output of g on input wxyz. When we present g as an \(\mathcal {F}\)-gate, we order the four external edges ABCD counterclockwise. In M_g, the row index bits are ordered AB and the column index bits are ordered DC, in the reverse order. We order them in this way so that when we link two arity 4 \(\mathcal {F}\)-gates with signature matrices A and B, the resulting signature matrix is the matrix product AB.

Lemma 2.28 (Corollary 3.8 in [26])

Let f be an arity 4 signature with complex weights. If M_f is redundant and \(\widetilde {M_{f}}\) is nonsingular, then Pl-Holant(f) is #P-hard.

Corollary 2.29

Let f be an arity 4 signature with complex weights. If there exists a nonsingular matrix \(T \in \mathbb {C}^{2 \times 2}\) such that \(\hat {f} = T^{\otimes 4} f\), where \(M_{\hat {f}}\) is redundant and \(\widetilde {M_{\hat {f}}}\) is nonsingular, then Pl-Holant(f) is #P-hard.

Definition 3.1

A signature f of arity n is in, respectively, \({\mathscr{A}}_{1}\), or \({\mathscr{A}}_{2}\), or \({\mathscr{A}}_{3}\) if it is symmetric and there exist an \(H \in \mathbf {O}_{2}(\mathbb {C})\) and a nonzero constant \(c \in \mathbb {C}\) such that f has the form, respectively, \(c H^{\otimes n} \left ({\left [\begin {array}{ll} 1 \\ 1 \end {array}\right ]}^{\otimes n} + \beta {\left [\begin {array}{ll} 1 \\ -1 \end {array}\right ]}^{\otimes n}\right )\), or cH^⊗n \(\left ({\left [\begin {array}{ll} 1 \\ i \end {array}\right ]}^{\otimes n} + {\left [\begin {array}{ll} 1 \\ -i \end {array}\right ]}^{\otimes n}\right )\), or \(c H^{\otimes n} \left ({\left [\begin {array}{ll} 1 \\ \alpha \end {array}\right ]}^{\otimes n} + i^{r} {\left [\begin {array}{ll} 1 \\ -\alpha \end {array}\right ]}^{\otimes n}\right )\), where β = α^tn+ 2r, r ∈{0,1,2,3}, and t ∈{0,1}.

Lemma 3.2 (Lemma 54, p. 1714 in 11)

Let f be a symmetric signature of arity n. Then \(f \in {\mathscr{A}}_{2}\) if and only if \(f = c \left (\left [\begin {array}{ll} 1 \\ i \end {array}\right ]^{\otimes n} + \beta \left [\begin {array}{ll} 1 \\ -i \end {array}\right ]^{\otimes n}\right )\) for some nonzero constants \(c, \beta \in \mathbb {C}\). Thus signatures in \({\mathscr{A}}_{2}\) are those with the form [x, y,−x,−y,…] with y≠ ± ix.

Lemma 3.3 (Lemma 56, p. 1715 in 11)

Let f be a non-degenerate symmetric signature. Then f is \({\mathscr{A}}\)-transformable if and only if \(f \in {\mathscr{A}}_{1} \cup {\mathscr{A}}_{2} \cup {\mathscr{A}}_{3}\).

Definition 3.4

A signature f of arity n is in \({\mathscr{P}}_{1}\) if it is symmetric and there exist an \(H \in \mathbf {O}_{2}(\mathbb {C})\) and a nonzero \(c \in \mathbb {C}\) such that \(f = c H^{\otimes n} \left ({\left [\begin {array}{ll} 1 \\ 1 \end {array}\right ]}^{\otimes n} + \beta {\left [\begin {array}{ll} 1 \\ -1 \end {array}\right ]}^{\otimes n}\right )\), where β≠ 0.

Lemma 3.5 (Lemma 59, p. 1717 in 11)

Let f be a non-degenerate symmetric signature. Then f is \({\mathscr{P}}\)-transformable if and only if \(f \in {\mathscr{P}}_{1} \cup {\mathscr{P}}_{2}\).

Proposition 3.6

\(\operatorname {Stab}({\mathscr{M}})\) is generated by nonzero scalar multiples of \(\left [\begin {array}{ll} 1 & 0 \\ 0 & \nu \end {array}\right ]\) for any nonzero \(\nu \in \mathbb {C}\) and \(X = \left [\begin {array}{ll} 0 & 1 \\ 1 & 0 \end {array}\right ]\).

Proposition 3.7 (Proposition 47, p. 1711 in 11)

Lemma 3.8

Let \(\mathcal {F}\) be a set of signatures. Then \(\mathcal {F}\) is \({\mathscr{M}}\)-transformable if and only if \(\mathcal {F} \subseteq \left [\begin {array}{ll} 1 & 1 \\ i & -i \end {array}\right ] {\mathscr{M}}\) or there exists an \(H \in \mathbf {SO}_{2}(\mathbb {C})\) such that \(\mathcal {F} \subseteq H {\mathscr{M}}\).

Proof

Sufficiency is easily verified by checking that =₂ is transformed into \({\mathscr{M}}\) in both cases. In particular, H leaves =₂ unchanged.

Definition 3.9

Lemma 3.10

Let f be a symmetric signature of arity n. Then \(f \in {\mathscr{M}}_{4}\) if and only if \(f = c \operatorname {Sym}_{n}^{n-1}(\left [\begin {array}{ll} 1 \\ i \end {array}\right ]; \left [\begin {array}{ll} 1 \\ -i \end {array}\right ])\) or \(f = c \operatorname {Sym}_{n}^{n-1}(\left [\begin {array}{ll} 1 \\ -i \end {array}\right ]; \left [\begin {array}{ll} 1 \\ i \end {array}\right ])\) for some nonzero constant \(c \in \mathbb {C}\).

Proof

Suppose \(f \in {\mathscr{M}}_{4}\), so that \(f = c H^{\otimes n} \operatorname {Sym}_{n}^{n-1}(\left [\begin {array}{ll} 1 \\ i \end {array}\right ]; \left [\begin {array}{ll} 1 \\ -i \end {array}\right ])\). If \(H \in \mathbf {SO}_{2}(\mathbb {C})\), then \(H = \left [\begin {array}{ll} a & b \\ -b & a\end {array}\right ]\) for some \(a,b \in \mathbb {C}\) such that a² + b² = 1. Since \(H \left [\begin {array}{ll} 1 \\ i \end {array}\right ] = (a + b i) \left [\begin {array}{ll} 1 \\ i \end {array}\right ]\) and \(H \left [\begin {array}{ll} 1 \\ -i \end {array}\right ] = (a - b i) \left [\begin {array}{ll} 1 \\ -i \end {array}\right ]\), it follows that \(f = c (a + b i)^{n-1} (a - b i) \operatorname {Sym}_{n}^{n-1}(\left [\begin {array}{ll} 1 \\ i \end {array}\right ]; \left [\begin {array}{ll} 1 \\ -i \end {array}\right ])\). Otherwise, \(H \in \mathbf {O}_{2}(\mathbb {C}) - \mathbf {SO}_{2}(\mathbb {C})\), so \(H = \left [\begin {array}{ll} a & b \\ b & -a\end {array}\right ]\) for some \(a,b \in \mathbb {C}\) such that a² + b² = 1. Then \(f = c (a + b i) (a - b i)^{n-1} \operatorname {Sym}_{n}^{n-1}(\left [\begin {array}{ll} 1 \\ -i \end {array}\right ]; \left [\begin {array}{ll} 1 \\ i \end {array}\right ])\).

Now suppose \(f = c \operatorname {Sym}_{n}^{n-1}(\left [\begin {array}{ll} 1 \\ i \end {array}\right ]; \left [\begin {array}{ll} 1 \\ -i \end {array}\right ])\) or \(f = c \operatorname {Sym}_{n}^{n-1}(\left [\begin {array}{ll} 1 \\ -i \end {array}\right ]; \left [\begin {array}{ll} 1 \\ i \end {array}\right ])\). The first case is already in the standard form of \({\mathscr{M}}_{4}\). In the second case, we pick \(H = \left [\begin {array}{ll} 1 & 0 \\ 0 & -1 \end {array}\right ] \in \mathbf {O}_{2}(\mathbb {C})\). Then H^⊗nf is in the standard form of \({\mathscr{M}}_{4}\). □

Lemma 3.11

Let f be a non-degenerate symmetric signature. Then f is \({\mathscr{M}}\)-transformable if and only if \(f \in {\mathscr{M}}_{1} \cup {\mathscr{M}}_{2} \cup {\mathscr{M}}_{3} \cup {\mathscr{M}}_{4}\).

Proof

Conversely, if there exists a matrix \(H \in \mathbf {O}_{2}(\mathbb {C})\) such that H^⊗nf is in one of the canonical forms of \({\mathscr{M}}_{1}\), \({\mathscr{M}}_{2}\), \({\mathscr{M}}_{3}\), or \({\mathscr{M}}_{4}\), then one can directly check that f is \({\mathscr{M}}\)-transformable by Definition 2.4. In fact, the transformations that we applied above are all invertible. □

Lemma 3.12

Let \(f\in {\mathscr{M}}_{3}\) be a non-degenerate signature of arity n ≥ 3 with \(H\in \mathbf {O}_{2}(\mathbb {C})\). Then f is not \({\mathscr{A}}\)- or \({\mathscr{P}}\)-transformable. Moreover, f is \({\mathscr{M}}\)-transformable with only HD or \(H{\left [\begin {array}{ll} 0 & 1 \\ 1 & 0 \end {array}\right ]}D\) for some diagonal matrix D.

Proof

Suppose \(f=[f_{0},f_{1},\dots ,f_{n}]\). It can be directly verified that symmetric signatures in \({\mathscr{A}}\) and \({\mathscr{P}}\) satisfy second order recurrence relations (see Lemma 48, p. 1712 [11]) with distinct eigenvalues, and this property still holds under a holographic transformation. Indeed if f is \({\mathscr{A}}\)- or \({\mathscr{P}}\)-transformable, then f satisfies a second order recurrence relation af_i + bf_i+ 1 + cf_i+ 2 = 0, for \(a,b,c\in \mathbb {C}\) such that not all a, b, c are 0 and b² − 4ac≠ 0. In other words, the second order recurrence relation has to have distinct eigenvalues. Moreover, this property is preserved by holographic transformations [12]. However, f is in \({\mathscr{M}}_{3}\). Hence \(f=H^{\otimes n}{\text {\sc ExactOne}_{n}}\) for some \(H\in \mathbf {O}_{2}(\mathbb {C})\) up to a nonzero factor. On the other hand, ExactOne_n does not satisfy a second order recurrence with distinct eigenvalues if n ≥ 3, a contradiction.

Moreover, notice that the only signatures in \({\mathscr{M}}\) that do not satisfy such second order recurrence relations are ExactOne_k and AllButOne_k functions. If f is \({\mathscr{M}}\)-transformable, then there exists a transformation T such that f = T^⊗ng for some \(g\in {\mathscr{M}}\) and \([1,0,1]T^{\otimes 2}\in {\mathscr{M}}\). Hence g = ExactOne_n or AllButOne_n. On the other hand \(f=H^{\otimes n}{\text {\sc ExactOne}_{n}}\) up to a nonzero factor. Therefore \((T^{-1}H)^{\otimes n}{\text {\sc ExactOne}_{n}}={\text {\sc ExactOne}_{n}}\) or AllButOne_n up to a nonzero factor.

Let \(J = T^{-1} H = {\left [\begin {array}{ll} x & y \\ z & w \end {array}\right ]}\) and let \(h = J^{\otimes n} {\text {\sc ExactOne}_{n}}\). As \({\text {\sc ExactOne}_{n}}=\operatorname {Sym}_{n}^{n-1}({\left [\begin {array}{ll} 1 \\ 0 \end {array}\right ]}; {\left [\begin {array}{ll} 0 \\ 1 \end {array}\right ]})\), \(h=({\left [\begin {array}{ll} x & y \\ z & w \end {array}\right ]})^{\otimes n}{\text {\sc ExactOne}_{n}}=\operatorname {Sym}_{n}^{n-1}({\left [\begin {array}{ll} x \\ z \end {array}\right ]}; {\left [\begin {array}{ll} y \\ w \end {array}\right ]})\). The first and last entries of h are x^n− 1y and z^n− 1w. As h = ExactOne_n or AllButOne_n, we have that x^n− 1y = z^n− 1w = 0. It is easy to see that x and z, or y and w cannot be both 0. Then x = w = 0 or y = z = 0. This implies that J = D or \(J=D{\left [\begin {array}{ll} 0 & 1 \\ 1 & 0 \end {array}\right ]}\) for some diagonal matrix D. Thus T = HJ^− 1 = HD^− 1 or \(H{\left [\begin {array}{ll} 0 & 1 \\ 1 & 0 \end {array}\right ]} D^{-1}\). □

Lemma 3.13

Let n ≥ 3, \(g = [x,y,0, \dotsc , 0,z]\) have arity n and xyz≠ 0. Then the signature Z^⊗ng is neither \({\mathscr{A}}\)-, \({\mathscr{P}}\)-, \({\mathscr{M}}\)-transformable, nor vanishing.

Remark 1

By Theorem 2.22, for arity n = 3 or 4, Lemma 3.13 says that Pl-Holant(Z^⊗ng) is #P-hard. After we have proved Theorem 6.1, this lemma will imply that Pl-Holant(Z^⊗ng) is #P-hard for all n ≥ 3.

Proof

That Z^⊗ng is not vanishing follows from Lemma 2.19 combined with Corollary 2.18 and Theorem 2.15. To show that Z^⊗ng is not \({\mathscr{A}}\)-, \({\mathscr{P}}\)-, \({\mathscr{M}}\)-transformable, we only need to show that \(Z^{\otimes n}g \not \in {\mathscr{P}}_{1} \cup {\mathscr{M}}_{2} \cup {\mathscr{A}}_{3} \cup {\mathscr{M}}_{3} \cup {\mathscr{M}}_{4}\) by Lemma 3.3, 3.5 and 3.11, and the fact that \({\mathscr{M}}_{1} \subset {\mathscr{A}}_{1} \subset {\mathscr{P}}_{1}\) and \({\mathscr{A}}_{2} = {\mathscr{P}}_{2} \subset {\mathscr{M}}_{2}\). See Fig. 3.

We first show that \(Z^{\otimes n}g \not \in {\mathscr{P}}_{1} \cup {\mathscr{M}}_{2} \cup {\mathscr{A}}_{3}\). We say a signature \(f=[f_{0}, f_{1}, \dotsc ,f_{n}]\) satisfies a second order recurrence of type 〈a, b, c〉 if af_k − bf_k+ 1 + cf_k+ 2 = 0 for 1 ≤ k ≤ n − 2, for some a, b and c not all zero. Symmetric signatures in \({\mathscr{A}}, {\mathscr{P}}, {\mathscr{M}}\) all satisfy second order recurrences, and this property is invariant under a holographic transformation. So signatures in \({\mathscr{P}}_{1} \cup {\mathscr{M}}_{2} \cup {\mathscr{A}}_{3}\) also satisfy second order recurrences. The recurrence af_k − bf_k+ 1 + cf_k+ 2 = 0 has characteristic equation a − bX + cX² = 0. Suppose \(Z^{\otimes n} g \in {\mathscr{P}}_{1} \cup {\mathscr{M}}_{2} \cup {\mathscr{A}}_{3}\), then for some \(H \in \mathbf {O}_{2}(\mathbb {C})\), f = H^⊗nZ^⊗ng = (HZ)^⊗ng has the canonical form given in Definitions 3.4, 3.9 or 3.1. As such, f satisfies a second order recurrence, and so does (Z^− 1)^⊗nf. We have HZ = ZD or \(Z D {\left [\begin {array}{ll} 0 & 1 \\ 1 & 0 \end {array}\right ]}\) for some non-singular diagonal D. Then \(f = Z^{\otimes n} g^{\prime }\), where \(g^{\prime } = D^{\otimes n} g\) or \((D {\left [\begin {array}{ll} 0 & 1 \\ 1 & 0 \end {array}\right ]})^{\otimes n} g\). So \(g^{\prime }\) has the form \([x^{\prime },y^{\prime },0, \dotsc , 0,z^{\prime }]\) or \([x^{\prime },0, \dotsc , 0,y^{\prime },z^{\prime }]\), with \(x^{\prime }y^{\prime }z^{\prime } \not =0\). We assume the former; the proof is similar for the latter.

It follows that \(g^{\prime } = (Z^{-1})^{\otimes n}f\) satisfies a second order recurrence. However, for n ≥ 4, \(g^{\prime }\) does not satisfy any second order recurrence. For a contradiction suppose \(g^{\prime }\) does. By \(x^{\prime }y^{\prime }z^{\prime } \not =0\), \(ay^{\prime } - b 0 + c 0 =0\) gives a = 0, \(a x^{\prime } - b y^{\prime } + c 0 =0\) gives b = 0, and \(a 0 - b 0 + c z^{\prime } =0\) gives c = 0; but a, b, c cannot be all zero.

Next suppose n = 3, and we show that \(g^{\prime } = (Z^{-1})^{\otimes n} f\) is still impossible. For \({\mathscr{P}}_{1}\), \(f = {\left [\begin {array}{ll} 1 \\ 1 \end {array}\right ]}^{\otimes 3} + \beta {\left [\begin {array}{ll} 1 \\ -1 \end {array}\right ]}^{\otimes 3}\) up to a nonzero constant. It is easy to check that (Z^− 1)^⊗nf satisfies a second order recurrence whose two eigenvalues sum to zero. However \(g^{\prime } = [x^{\prime }, y^{\prime }, 0, z^{\prime }]\) has type \(\langle y^{\prime }z^{\prime }, x^{\prime }z^{\prime }, -y^{\prime 2} \rangle \), so the sum of its two eigenvalues is \(-x^{\prime }z^{\prime }/y^{\prime 2} \not =0\).

For \({\mathscr{M}}_{2}\), \(f = \left [\begin {array}{ll} 1 \\ \gamma \end {array}\right ]^{\otimes 3} \pm \left [\begin {array}{ll} 1 \\ -\gamma \end {array}\right ]^{\otimes 3}\). In (Z^− 1)^⊗nf, \(Z^{-1} {\left [\begin {array}{ll} 1 & 1 \\ \gamma & -\gamma \end {array}\right ]}\) has the form \({\left [\begin {array}{ll} u & v \\ v & u \end {array}\right ]}\), and \((Z^{-1})^{\otimes n} f = \left [\begin {array}{ll} u \\ v \end {array}\right ]^{\otimes 3} \pm \left [\begin {array}{ll} v \\ u \end {array}\right ]^{\otimes 3}\). Thus the weight 1 and weight 2 entries of (Z^− 1)^⊗nf are either equal or sum to zero. If \(g^{\prime } = (Z^{-1})^{\otimes n} f\) this would imply \(y^{\prime } =0\), a contradiction.

For \({\mathscr{A}}_{3}\), \(f = {\left [\begin {array}{ll} 1 \\ \alpha \end {array}\right ]}^{\otimes n} + i^{r} {\left [\begin {array}{ll} 1 \\ -\alpha \end {array}\right ]}^{\otimes n}\). (Recall, as defined at the beginning of Section 3, \(\alpha = \sqrt {i}\).) \(Z^{-1} {\left [\begin {array}{ll} 1 & 1 \\ \alpha & -\alpha \end {array}\right ]} = {\left [\begin {array}{ll} u & v \\ v & u \end {array}\right ]}\), with u = 1 − αi and v = 1 + αi. The weight 2 entry of (Z^− 1)^⊗nf is uv² + i^rvu² = (uv)(v + i^ru). This is nonzero for all r. However for \(g^{\prime } = [x^{\prime }, y^{\prime }, 0, z^{\prime }]\), the weight 2 entry is 0.

It remains to show that \(Z^{\otimes n}g \not \in {\mathscr{M}}_{3} \cup {\mathscr{M}}_{4}\). If \(Z^{\otimes n}g \in {\mathscr{M}}_{3}\), then Z^⊗ng = cH^⊗nf for some \(H \in \mathbf {O}_{2}(\mathbb {C})\) and \(f = \operatorname {Sym}_{n}^{n-1}(\left [\begin {array}{ll} 1 \\ 0 \end {array}\right ]; \left [\begin {array}{ll} 0 \\ 1 \end {array}\right ])\). Again \(f = ((cH)^{-1} Z)^{\otimes n} g = Z^{\otimes n} g^{\prime }\) for some \(g^{\prime }\) having the same form as g or its reversal. Then \(g^{\prime } = (Z^{-1})^{\otimes n} f\) is the signature \([n, n-2, \dotsc , -(n-2), -n]\), up to a nonzero constant. The weight 1 entry and weight n − 1 entry have the same absolute value. By the form of \(g^{\prime }\) this is a contradiction.

Finally if \(Z^{\otimes n}g \in {\mathscr{M}}_{4}\), then by Lemma 3.10, Z^⊗ng = cZ^⊗nf, for some nonzero constant \(c \in \mathbb {C}\), and \(f = \operatorname {Sym}_{n}^{n-1}(\left [\begin {array}{ll} 1 \\ 0 \end {array}\right ]; \left [\begin {array}{ll} 0 \\ 1 \end {array}\right ])\) or its reversal \(\operatorname {Sym}_{n}^{n-1}(\left [\begin {array}{ll} 0 \\ 1 \end {array}\right ]; \left [\begin {array}{ll} 1 \\ 0 \end {array}\right ])\). In either case, after canceling out Z, the weight 0 entry is 0 in the expression but not so in g; a contradiction. □

Lemma 5.2 (cf. Lemma 61, p. 1717 in 11)

Let \(f\in {\mathscr{P}}_{1}\) be a non-degenerate signature of arity n ≥ 3 with an orthogonal transformation H^− 1 and \(\mathcal {F}\) be a set of signatures containing f. Let H₂ be the 2-by-2 matrix \(\tfrac {1}{\sqrt {2}}{\left [\begin {array}{ll} 1 & 1 \\ 1 & -1 \end {array}\right ]}\). Then \(\operatorname {Pl-\#CSP}^{2}(H_{2}H\mathcal {F})\le _{T}\operatorname {Pl-Holant}(\mathcal {F})\).

Lemma 5.3 (cf. Lemma 63, p. 1719 in 11)

Let \(f\in {\mathscr{A}}_{3}\) be a non-degenerate signature of arity n ≥ 3 with an orthogonal transformation H^− 1 and \(\mathcal {F}\) be a set of signatures containing f. Let α = e^πi/4 and Y be the 2-by-2 matrix \(\left [\begin {array}{ll} \alpha & 1 \\ -\alpha & 1 \end {array}\right ]\). Then \(\operatorname {Pl-\#CSP}^{2}(YH\mathcal {F}\cup \{[1,-i,1]\})\le _{T}\operatorname {Pl-Holant}(\mathcal {F})\).

Corollary 5.4

Let \(\mathcal {F}\) be a set of symmetric signatures. Suppose there exists \(f\in \mathcal {F}\) that is a non-degenerate signature of arity n ≥ 3 in \({\mathscr{P}}_{1}\). Then \(\operatorname {Pl-Holant}(\mathcal {F})\) is #P-hard unless \(\mathcal {F}\) is \({\mathscr{A}}\)-, \({\mathscr{P}}\)-, or \({\mathscr{M}}\)-transformable, in which case \(\operatorname {Pl-Holant}(\mathcal {F})\) is tractable.

Proof

Suppose \(f \in {\mathscr{P}}_{1}\). Then there is some \(H \in \mathbf {O}_{2}(\mathbb {C})\) such that (H₂H)^⊗nf has the form [a,0,…,0, b], where ab≠ 0, and \(H_{2} = \frac {1}{\sqrt {2}}{\left [\begin {array}{ll} 1 & 1 \\ 1 & -1 \end {array}\right ]}\). Let \(H^{\prime } = (H_{2} H)^{-1} \in \mathbf {O}_{2}(\mathbb {C})\). By Lemma 5.2 and Theorem 5.1, \(\operatorname {Pl-Holant}(\mathcal {F})\) is #P-hard unless either (1) \(\mathcal {F} \subseteq H^{\prime } {\mathscr{P}}\), or (2) \(\mathcal {F} \subseteq H^{\prime } T {\mathscr{A}}\), or (3) \(\mathcal {F} \subseteq H^{\prime } T^{\prime } {\left [\begin {array}{ll} 1 & 1 \\ 1 & -1 \end {array}\right ]} {\mathscr{M}}\), where \(T \in \mathcal {T}_{8}\) and \(T^{\prime } \in \mathcal {T}_{4}\). In case (1), \(\mathcal {F}\) is \({\mathscr{P}}\)-transformable since \((=_{2}) H^{{\prime }\otimes 2} = (=_{2}) \in {\mathscr{P}}\). In case (2), \(\mathcal {F}\) is \({\mathscr{A}}\)-transformable since \((=_{2}) (H^{\prime }T)^{\otimes 2} = (=_{2})T^{\otimes 2} \in {\mathscr{A}}\). In case (3), \(\mathcal {F}\) is \({\mathscr{M}}\)-transformable. If \(T^{\prime } = {\left [\begin {array}{ll} 1 & 0 \\ 0 & \pm 1 \end {array}\right ]}\), then \(T^{\prime } \in \mathbf {O}_{2}(\mathbb {C})\). So \((=_{2}) (H^{\prime }T^{\prime } {\left [\begin {array}{ll} 1 & 1 \\ 1 & -1 \end {array}\right ]})^{\otimes 2}\) is unchanged \((=_{2}) \in {\mathscr{M}}\). If \(T^{\prime } = {\left [\begin {array}{ll} 1 & 0 \\ 0 & \pm i \end {array}\right ]}\), then \(T^{\prime } {\left [\begin {array}{ll} 1 & 1 \\ 1 & -1 \end {array}\right ]} = {\left [\begin {array}{ll} 1 & 1 \\ i & -i \end {array}\right ]}\) or \({\left [\begin {array}{ll} 1 & 1 \\ -i & i \end {array}\right ]}\), and \((=_{2}) (H^{\prime }T^{\prime } {\left [\begin {array}{ll} 1 & 1 \\ 1 & -1 \end {array}\right ]})^{\otimes 2} = 2[0,1,0] \in {\mathscr{M}}\). □

Corollary 5.5

Suppose f is a non-degenerate signature of arity n ≥ 5. Let \(f^{\prime }\) be obtained from f with a self loop, and assume that \(f^{\prime } \in {\mathscr{P}}_{1}\) is non-degenerate. Then Pl-Holant(f) is #P-hard unless f is \({\mathscr{A}}\)-, \({\mathscr{P}}\)-, or \({\mathscr{M}}\)-transformable, in which case Pl-Holant(f) is tractable.

Corollary 5.6

Let \(\mathcal {F}\) be a set of signatures. Suppose there exists \(f\in \mathcal {F}\) that is a non-degenerate signature of arity n ≥ 3 in \({\mathscr{A}}_{3}\). Then \(\operatorname {Pl-Holant}(\mathcal {F})\) is #P-hard unless \(\mathcal {F}\) is \({\mathscr{A}}\)- or \({\mathscr{M}}\)-transformable, in which case \(\operatorname {Pl-Holant}(\mathcal {F})\) is tractable.

Proof

Assume that \(f\in {\mathscr{A}}_{3}\) with an orthogonal transformation H^− 1. By Lemma 5.3, we have \(\operatorname {Pl-\#CSP}^{2}(Y H \mathcal {F} \cup \{[1,-i,1]\}) \le _{T} \operatorname {Pl-Holant}(\mathcal {F})\), where \(Y = {\left [\begin {array}{ll} \alpha & 1 \\ -\alpha & 1 \end {array}\right ]}\) and α = e^πi/4. Let g = [1,−i,1] and \(\mathcal {F}^{\prime } = Y H \mathcal {F} \cup \{g\}\).

We apply Theorem 5.1 to \(\operatorname {Pl-\#CSP}^{2}(\mathcal {F}^{\prime })\). The consequence is that \(\operatorname {Pl-\#CSP}^{2}(\mathcal {F}^{\prime })\) (and hence \(\operatorname {Pl-Holant}\mathcal ({F})\)) is #P-hard unless \(\mathcal {F}^{\prime }\subseteq {\mathscr{P}}\), or \(\mathcal {F}^{\prime }\subseteq {\left [\begin {array}{ll} 1 & 0 \\ 0 & i^{r} \end {array}\right ]}\widehat {{\mathscr{M}}}\) for some integer 0 ≤ r ≤ 3, or \(\mathcal {F}^{\prime }\subseteq {\left [\begin {array}{ll} 1 & 0 \\ 0 & \alpha ^{r} \end {array}\right ]}{\mathscr{A}}\) for some integer 0 ≤ r ≤ 7 where α = e^iπ/4. Notice that \(g\not \in {\mathscr{P}}\) and hence the first case is impossible.

Corollary 5.7

Let f be a non-degenerate signature of arity n ≥ 5. Let \(f^{\prime }\) be obtained from f with a self loop. If \(f^{\prime }\) is non-degenerate and \(f^{\prime }\in {\mathscr{A}}_{3}\), then Pl-Holant(f) is #P-hard unless f is \({\mathscr{A}}\)- or \({\mathscr{M}}\)-transformable, in which case Pl-Holant(f) is tractable.

Lemma 5.8

Let \(\mathcal {F}\) be a set of signatures. Suppose there exists \(f\in \mathcal {F}\) which is a non-degenerate signature of arity n ≥ 3 in \({\mathscr{M}}_{2}\setminus {\mathscr{P}}_{2}\). Then \(\operatorname {Pl-Holant}\left (\mathcal {F} \right )\) is #P-hard unless \(\mathcal {F}\) is \({\mathscr{A}}\)-, \({\mathscr{P}}\)-, or \({\mathscr{M}}\)-transformable, in which case \(\operatorname {Pl-Holant}\left (\mathcal {F} \right )\) is tractable.

Proof

As \(f\in {\mathscr{M}}_{2}\setminus {\mathscr{P}}_{2}\), we may assume \(f= H^{\otimes n} \left ({\left [\begin {array}{ll} 1 \\ \gamma \end {array}\right ]}^{\otimes n} \pm {\left [\begin {array}{ll} 1 \\ -\gamma \end {array}\right ]}^{\otimes n}\right )\) up to a nonzero constant, where H is an orthogonal 2-by-2 matrix and γ≠ 0,±i.

Otherwise such k and c do not exist. The two eigenvalues of N are λ₁ = 2 and λ₂ = 2γ². If λ₁ = λ₂, then γ² = 1 and \(N={\left [\begin {array}{ll} 2 & 0 \\ 0 & 2 \end {array}\right ]}\). Contradiction. Hence λ₁≠λ₂, and N is diagonalizable. Let \(N=P{\left [\begin {array}{ll} \lambda _{1} & 0 \\ 0 & \lambda _{2} \end {array}\right ]}P^{-1}\), for some non-singular matrix P. By connecting l many copies of N on the left via =₂ on the right, where l is a positive integer, we can implement \(N^{l}=P{\left [\begin {array}{ll} {\lambda _{1}^{l}} & 0 \\ 0 & {\lambda ^{l}_{2}} \end {array}\right ]}P^{-1}\). Since N does not have finite order up to a scalar, for any positive integer l, \(\left (\lambda _{1}/\lambda _{2}\right )^{l}\neq 1\).

Consider an instance Ω of \({\text {Pl-Holant}\left (=_{2},g\mid =_{2},=_{n},T^{-1}\mathcal {F}\right )}\). Suppose that the left =₂ appears t times. Let l be a positive integer. We obtain Ω_l from Ω by replacing each occurrence of =₂ on the left with N^l.

Since \(N^{l}=P{\left [\begin {array}{ll} {\lambda _{1}^{l}} & 0 \\ 0 & {\lambda _{2}^{l}} \end {array}\right ]}P^{-1}\), we can view our construction of Ω_l as replacing N^l by 3 signatures, with matrix P, \({\left [\begin {array}{ll} {\lambda _{1}^{l}} & 0 \\ 0 & {\lambda _{2}^{l}} \end {array}\right ]}\), and P^− 1, respectively. This does not change the Holant value.

Corollary 5.9

Let f be a non-degenerate signature of arity n ≥ 5. Let \(f^{\prime }\) be f with a self loop, and \(f^{\prime }\) is non-degenerate and \(f^{\prime }\in {\mathscr{M}}_{2}\setminus {\mathscr{P}}_{2}\). Then Pl-Holant(f) is #P-hard unless f is \({\mathscr{A}}\)-, \({\mathscr{P}}\)-, or \({\mathscr{M}}\)-transformable, in which case Pl-Holant(f) is tractable.

Lemma 5.10

Let \(\mathcal {F}\) be a set of signatures. Suppose there exists \(f\in \mathcal {F}\) that is a non-degenerate signature of arity n ≥ 3 in \({\mathscr{M}}_{3}\). Then \(\operatorname {Pl-Holant}(\mathcal {F})\) is #P-hard unless \(\mathcal {F}\subseteq H {\mathscr{M}}\) for some \(H \in \mathbf {O}_{2}(\mathbb {C})\), in which case \(\mathcal {F}\) is \({\mathscr{M}}\)-transformable and \(\operatorname {Pl-Holant}(\mathcal {F})\) is tractable.

Proof

We first claim that \(\operatorname {Pl-Holant}(\mathcal {F})\) is #P-hard unless \(\mathcal {F}\) is \({\mathscr{A}}\)-, \({\mathscr{P}}\)-, or \({\mathscr{M}}\)-transformable.

By the definition of \({\mathscr{M}}_{3}\), we may assume, up to a nonzero constant, that \(\hat {f} = (H^{-1})^{\otimes n}f = {\text {\sc ExactOne}_{n}}\) for some orthogonal matrix \(H \in \mathbf {O}_{2}(\mathbb {C})\). After zero or more self loops, we can further assume that either \(\hat {f} = {\text {\sc ExactOne}_{3}}\) or \(\hat {f} = {\text {\sc ExactOne}_{4}}\) depending on the parity of n.

Suppose \(\hat {f} = {\text {\sc ExactOne}_{3}}\). Consider the gadget in Fig. 6a. We assign \(\hat {f}\) to all vertices. The signature of the resulting gadget is g = [0,1,0,1], which is in \({\mathscr{M}}_{2}\) and not in \({\mathscr{P}}_{2}={\mathscr{A}}_{2}\) by Lemma 3.2. Thus, the claim follows from Lemma 5.8.

Otherwise, \(\hat {f} = {\text {\sc ExactOne}_{4}}\). Consider the gadget in Figure 6b. We assign \(\hat {f}\) to all vertices. Note that this is a matchgate. The signature of the resulting gadget is [0,2,0,1,0], which is in \({\mathscr{M}}_{2}\) and not in \({\mathscr{P}}_{2} = {\mathscr{A}}_{2}\) by Lemma 3.2. Thus, the claim follows from Lemma 5.8. This completes the proof of the claim.

However, as \(f\in \mathcal {F}\) and \(f\in {\mathscr{M}}_{3}\), \(\mathcal {F}\) cannot be \({\mathscr{A}}\)- or \({\mathscr{P}}\)-transformable by Lemma 3.12. Also by Lemma 3.12, if \(\mathcal {F}\) is \({\mathscr{M}}\)-transformable, then \(\mathcal {F}\subseteq HD{\mathscr{M}}\) or \(H{\left [\begin {array}{ll} 0 & 1 \\ 1 & 0 \end {array}\right ]}D{\mathscr{M}}\) for some diagonal matrix D. Notice that \(D\in \operatorname {Stab}({\mathscr{M}})\) and \({\left [\begin {array}{ll} 0 & 1 \\ 1 & 0 \end {array}\right ]}D\in \operatorname {Stab}({\mathscr{M}})\). This implies that \(\mathcal {F}\subseteq H{\mathscr{M}}\). □

Corollary 5.11

Let f be a non-degenerate signature of arity n ≥ 5. Let \(f^{\prime }\) be f with a self loop, and \(f^{\prime }\) is non-degenerate and \(f^{\prime }\in {\mathscr{M}}_{3}\). Then Pl-Holant(f) is #P-hard unless f is \({\mathscr{M}}\)-transformable, in which case Pl-Holant(f) is tractable.

Lemma 6.2

Suppose f is a non-degenerate signature of arity n ≥ 5. Let \(f^{\prime }\) be f with a self loop. If \(f^{\prime }\in {\mathscr{P}}_{1} \cup {\mathscr{M}}_{2} \cup {\mathscr{A}}_{3} \cup {\mathscr{M}}_{3} \cup {\mathscr{V}}\) is non-degenerate, then Pl-Holant(f) is #P-hard unless \(f \in {\mathscr{P}}_{1} \cup {\mathscr{M}}_{2} \cup {\mathscr{A}}_{3} \cup {\mathscr{M}}_{3} \cup {\mathscr{V}}\).

Lemma 6.3

Let f be a non-degenerate signature of arity n ≥ 5. If \(f = Z^{\otimes n} [a,1,0,\dots ,0,1,b]\) for some \(a,b \in \mathbb {C}\), where the number of 0’s is n − 3. Then Pl-Holant(f) is #P-hard.

Proof

First we use the gadget in Fig. 7b, where we put f on both vertices. Let the resulting signature be \(h=Z^{\otimes 4}\hat {h}\). It is easier to calculate \(\hat {h}\), that is, h in the Z basis. Indeed, \(\hat {h}\) is not symmetric, but \(\hat {h}\) has the following matrix representation as n ≥ 5:

$$ \begin{array}{@{}rcl@{}} M_{\hat{h}}= \begin{bmatrix} 0 & a & a & ab+(n-2) \\ a & 2 & 2 & b \\ a & 2 & 2 & b \\ ab+(n-2) & b & b & 0 \end{bmatrix}. \end{array} $$

Notice that this matrix is redundant, and \(\det (\widetilde {M_{\hat {h}}})=-4 (n-2) (a b + n-2)\). If ab≠ 2 − n, then by Corollary 2.29 Pl-Holant(h) is #P-hard, and so is Pl-Holant(f). Hence in the following we assume ab = 2 − n.

where \(\widehat {f^{\prime }}=[1,0,\dots ,0,1]\) and \(\hat {f}=[a,1,0,\dots ,0,1,b]\) for some \(a,b\in \mathbb {C}\). We get this expression of \(\widehat {f^{\prime }}\) because doing a self loop commutes with the operation of holographic transformations.

We connect \(\widehat {f^{\prime }}\) to \(\hat {f}\) via [0,1,0], getting [a,2, b]. Then we connect [a,2, b] to \(\hat {f}\) via [0,1,0] again, getting \(\hat {g}=[ab+4,b,0,\dots ,0,a,ab+4]\) of arity n − 2.

It is easy to compute that \(\det (\widetilde {M_{\widehat {h^{\prime }}}})=-8(3n-14)(ab(n-6)^{2}-6n^{2}+40n-56) =8(n-4)(n-2)^{2}(3n-14)\). Since n ≥ 7, \(\det (\widetilde {M_{\widehat {h^{\prime }}}})>0\). Then by Corollary 2.29 \(\operatorname {Pl-Holant}(h^{\prime })\) is #P-hard, and so is Pl-Holant(f).

The remaining cases are n = 6 and n = 5. When n = 6, ab = 2 − n = − 4. Moreover, \(\hat {g}\) is of arity 4 and \(\hat {g}=[ab+4,b,0,a,ab+4]=[0,b,0,a,0]\). We do one more self loop on g via [0,1,0] in the Z basis, resulting in \(\widehat {g^{\prime }}=[b,0,a]\). Connecting \(\widehat {g^{\prime }}\) to \(\hat {f}\) via [0,1,0], we get \(\widehat {g_{1}}=[a^{2},a,0,b,b^{2}]\). Hence \(\det (\widetilde {M_{\widehat {g_{1}}}})=-4a^{2}b^{2}=-64\neq 0\). Then by Corollary 2.29 Pl-Holant(g₁) is #P-hard, and so is Pl-Holant(f).

At last, n = 5 and ab = 2 − n = − 3. We also have \(\hat {g}=[ab+4,b,a,ab+4]=[1,b,a,1]\). One more self loop on g via [0,1,0] in the Z basis results in \(\widehat {g^{\prime \prime }}=[b,a]\). Connecting \(\widehat {g^{\prime \prime }}\) to \(\hat {f}\) via [0,1,0], we get \(\widehat {g_{2}}=[a^{2}+b,a,0,b,b^{2}+a]\). Hence \(\det (\widetilde {M_{\widehat {g_{2}}}})=-2 (a^{3} + 2 a^{2} b^{2} + b^{3})=-2 (a^{3} + b^{3} + 18)\). If a³ + b³ + 18 ≠ 0, then we are done by Corollary 2.29. Otherwise a³ + b³ = − 18, and we construct a binary signature [a,0, b] by doing a self-loop on \(\widehat {g_{2}}\) in the Z basis. Then we construct another unary signature by connecting \(\widehat {g^{\prime \prime }}=[b,a]\) to [a,0, b] via [0,1,0], which gives [a², b²]. Connecting [a², b²] to \(\hat {f}\) via [0,1,0], we have another arity-4 signature \(\widehat {g_{3}}=[ab^{2}+a^{2},b^{2},0,a^{2},a^{2} b +b^{2}]\). We compute \(\det (\widetilde {M_{\widehat {g_{3}}}})=-2 (a^{6} + a^{5} b^{2} + a^{2} b^{5} + b^{6})=-2(a^{6}+b^{6}-162)\). If a⁶ + b⁶ − 162 ≠ 0, again we are done by Corollary 2.29. Otherwise a⁶ + b⁶ = 162. Together with a³ + b³ = − 18 and ab = − 3, there is no solution of a and b. This finishes the proof. □

Corollary 6.4

Suppose f is a non-degenerate signature of arity n ≥ 5. Let \(f^{\prime }\) be obtained from f with a self loop. If \(f^{\prime } \in {\mathscr{P}}_{2}\) is non-degenerate, then Pl-Holant(f) is #P-hard.

Proof

Since \(f^{\prime }\in {\mathscr{P}}_{2} = {\mathscr{A}}_{2}\), we can assume by Lemma 3.2 that we have the form \(c^{-1} f^{\prime } = Z^{\otimes (n-2)} \left (\left [\begin {array}{ll} 1 \\ 0 \end {array}\right ]^{\otimes (n-2)} + \beta \left [\begin {array}{ll} 0 \\ 1 \end {array}\right ]^{\otimes (n-2)}\right )\), for some c, β≠ 0. Let \(\gamma = \beta ^{\frac {1}{n-2}}\), \(a = \frac {\gamma +1}{2 \sqrt {\gamma }}\) and \(b = \frac {\gamma -1}{2 i \sqrt {\gamma }}\), then \(a+bi = \sqrt {\gamma }\) and \(a-bi = \frac {1}{\sqrt {\gamma }}\), both nonzero with a² + b² = 1 and \(\frac {a+bi}{a-bi} = \gamma \). Thus \(H = \left [ \begin {array}{ll} a & b\\ -b & a \end {array} \right ] \in \mathbf {O}_{2}(\mathbb {C})\), and \(HZ = Z \left [\begin {array}{cc} a+bi & 0 \\ 0 & a-bi \end {array} \right ]\). Then \(c^{-1} H^{\otimes (n-2)} f^{\prime } = (HZ)^{\otimes (n-2)} \left (\left [\begin {array}{ll} 1 \\ 0 \end {array}\right ]^{\otimes (n-2)} + \gamma ^{n-2} \left [\begin {array}{ll} 0 \\ 1 \end {array}\right ]^{\otimes (n-2)}\right )= (a+bi)^{n-2} Z^{\otimes (n-2)} [1,0,\dots ,0,1]\) of arity n − 2. Since H does not change the complexity, we may assume we are under this transformation. Then up to a nonzero constant f is of the form \(Z^{\otimes n}[a,1,0,\dots ,0,1,b]\) of arity n. The claim follows by Lemma 6.3. □

Lemma 6.5

Suppose f is a non-degenerate signature of arity n ≥ 5. Let \(f^{\prime }\) be obtained from f with a self loop. If \(f^{\prime }\) is non-degenerate and vanishing, then Pl-Holant(f) is #P-hard unless \(\{f,f^{\prime }\}\) is vanishing, in which case Pl-Holant(f) is tractable.

Proof

Since \(f^{\prime }\) is vanishing, \(f^{\prime } \in {\mathscr{V}}^{\sigma }\) for some σ ∈{+,−} by Theorem 2.15. For simplicity, assume that \(f^{\prime } \in {\mathscr{V}}^{+}\). The other case is similar.

where \(\hat {f^{\prime }} = (Z^{-1})^{\otimes n} f^{\prime } = [\hat {f}_{1}, \dotsc , \hat {f}_{d}, 0, \dotsc , 0]\) with \(\hat {f}_{d} \neq 0\) by Lemma 2.19. Note that adding a self-loop in the standard basis is the same as connecting to [0,1,0] in the Z basis. Hence we may assume that \(\hat {f} = [\hat {f}_{0}, \hat {f}_{1}, \dotsc , \hat {f}_{d}, 0, \dotsc , 0, c]\), for some \(\hat {f}_{0}\) and c. If c = 0, then \(\{f,f^{\prime }\}\subset {\mathscr{V}}^{+}\) is vanishing. Hence we may assume that c≠ 0. We will show that Pl-Holant(f) is #P-hard.

Doing d − 2 self-loops by [0,1,0] on \(\hat {f}\), we get a signature \(\hat {h} = [\hat {f}_{d-2}, \hat {f}_{d-1}, \hat {f}_{d}, 0, \dotsc , 0, 0 ~\text {(or)}~ c]\) of arity n − 2(d − 2) = n − 2d + 4 ≥ 5. The last entry of \(\hat {h}\) is c when d = 2 and is 0 when d > 2. As n > 2d, we may do two more self loops and get \([\hat {f}_{d}, 0, \dotsc , 0]\) of arity k = n − 2d ≥ 1. This signature is equivalent to [1,0]^⊗k. Now connect this signature back to \(\hat {f}\) via [0,1,0]. It is the same as getting the last n − k + 1 = 2d + 1 signature entries of \(\hat {f}\) up to a nonzero scalar. We may repeat this operation zero or more times until the arity \(k^{\prime }\) of the resulting signature is less than or equal to k. We claim that this signature has the form \(\hat {g} = [0, \dotsc , 0, c]\). In other words, the \(k^{\prime }+1\) entries of \(\hat {g}\) consist of the last c and \(k^{\prime }\) many 0’s from the signature \(\hat {f}\), all appearing after \(\hat {f}_{d}\). This is because there are n − d − 1 many 0 entries in the signature \(\hat {f}\) after \(\hat {f}_{d}\), and \(n - d - 1 \ge k \ge k^{\prime }\). Note that \(\hat {g}=[0,1]^{\otimes k^{\prime }}\).

Having both [1,0]^⊗k and \(\hat {g} = [0,1]^{\otimes k^{\prime }}\) in the Z basis, we realize [0,1]^⊗t using the subtractive Euclidean argument as in Lemma 4.1, where \(t=\gcd (k,k^{\prime })\). Then we put \(\tfrac {k}{t}\) many copies of [0,1]^⊗t together to get [0,1]^⊗k. Connect \(\hat {h}\) with [0,1]^⊗k by [0,1,0]. Note that due to [0,1,0] flipping the bits, this gets the prefix of \(\hat {h}\) of arity arity(h) − k. Recall that arity(h) = n − 2d + 4, and hence arity(h) − k = n − 2d + 4 − (n − 2d) = 4. The resulting signature has arity 4. Moreover, the signature is \([\hat {f}_{d-2}, \hat {f}_{d-1}, \hat {f}_{d}, 0, 0]\). The last entry is 0 (and not c), because k ≥ 1 and \(\operatorname {arity}(\hat {h})\ge 5\).

However, as explained in the proof of Lemma 4.7, the problem \(\operatorname {Pl-Holant}([0,1,0] | [\hat {f}_{d-2}, \hat {f}_{d-1}, \hat {f}_{d}, 0, 0])\) is equivalent to Pl-Holant([0,1,0]| [0,0,1,0,0]) when \(\hat {f}_{d} \neq 0\), the problem of counting Eulerian Orientations in planar 4-regular graphs. This problem is #P-hard [26]. □

Lemma 6.6

Let \(a, b \in \mathbb {C}\). Suppose f is a signature of the form \(Z^{\otimes n}[a,1,0,\dotsc ,0,b]\), where \(Z={\left [\begin {array}{ll} 1 & 1 \\ i & -i \end {array}\right ]}\), with arity n ≥ 3. If ab≠ 0, then Pl-Holant(f) is #P-hard.

Proof

We prove by induction on n. For n = 3 or 4, it follows from Lemma 3.13 and Theorem 2.22 that Pl-Holant(f) is #P-hard.

Doing a self loop on f yields \(f^{\prime }=Z^{\otimes (n-2)}[1,0,\dots ,0]\). Connecting \(f^{\prime }\) back to f, we get a binary signature g₂ = Z^⊗2[0,0, b]. Once again we connect g₂ to f, the resulting signature is \(h=Z^{\otimes (n-2)}[a,1,0,\dots ,0]\) of arity n − 2 ≥ 3 up to the constant factor of b≠ 0.

Notice that h is non-degenerate and \(h\in {\mathscr{V}}^{+}\). Since a≠ 0, \(h \not \in {\mathscr{M}}_{4}^{+}\). By Lemma 4.3, Pl-Holant(h, g₁) is #P-hard, hence Pl-Holant(f) is also #P-hard. □

Lemma 6.7

Proof

Consider the gadget in Fig. 8a. We assign [0,0,0,1,0] to the triangle vertices, [0,1,0,0,0] to the circle vertices, \(\hat {g}\) to the pentagon vertex, and [0,1,0] to the square vertices. Let \(\hat {h}\) be the signature of this gadget. By adding two more disequality signatures and then grouping appropriately, it is clear that the gadget in Fig. 8b has the same signature of the gadget in Fig. 8a, where the circle vertices are still assigned [0,1,0,0,0], the square vertices are still assigned [0,1,0], and the diamond vertex is assigned the quaternary equality signature. To compute the signature \(\hat {h}\), first compute the signature \(\hat {h}^{\prime }\) of the inner gadget enclosed by the dashed line, which has signature matrix

$$ M_{\hat{h}^{\prime}} \! =\! \begin{bmatrix} 3 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{bmatrix}. $$

Then by Fig. 9, the signature matrix of \(\hat {h}\) is

$$ \hat{h} \text{ is } M_{\hat{h}} \! =\! \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 1 & 3 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}\!. $$

We use one more gadget before we finish the proof using interpolation. Consider the gadget in Fig. 10b. We assign \(\hat {h}\) to the circle vertices and [0,1,0] to the square vertices. The signature of the resulting gadget is \(\hat {r}\) with signature matrix \(M_{\hat {r}}\) (see Fig. 2 for the signature of a rotated copy of \(\hat {h}\) that appears as the second circle vertex in Fig. 10b), where

$$ M_{\hat{r}} = \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 1 & 3 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \left( \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \otimes \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \right) \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 3 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 6 & 4 & 0 \\ 0 & 4 & 2 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}. $$

So we can construct \(\hat {r}\) in the RHS of \(\text {Pl-Holant}\left ({\neq }_2\mid [0,1,0,0,0],[0,0,0,1,0],\hat {g}\right )\).

Consider an instance Ω of \({\text {Pl-Holant}\left ({\neq }_{2}\mid \mathcal {F} \cup \{\hat {r}^{\prime }\}\right )}\), where \(\mathcal {F}\) is a set of symmetric signatures containing \(\hat {r}\), and the signature matrix of \(\hat {r}^{\prime }\) is

$$ M_{\hat{r}^{\prime}} = \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 3 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}. $$

Suppose that \(\hat {r}^{\prime }\) appears n times in Ω. We construct from Ω a sequence of instances Ω_s of \({\text {Pl-Holant}\left ({\neq }_{2}\mid \mathcal {F}\right )}\) indexed by s ≥ 1. We obtain Ω_s from Ω by replacing each occurrence of \(\hat {r}^{\prime }\) with the gadget N_s in Fig. 11 with \(\hat {r}\) assigned to the circle vertices and [0,1,0] assigned to the square vertices. In Ω_s, the edge corresponding to the i th significant index bit of N_s connects to the same location as the edge corresponding to the i th significant index bit of \(\hat {r}^{\prime }\) in Ω.

Lemma 6.8

Let \(b \in \mathbb {C}\). Suppose f is a signature of the form \(Z^{\otimes n}[0,1,0,\dotsc ,0,b]\), where \(Z={\left [\begin {array}{ll} 1 & 1 \\ i & -i \end {array}\right ]}\), with arity n ≥ 4. If b≠ 0, then Pl-Holant(f) is #P-hard.

Remark 3

For n = 3, Z^⊗3[0,1,0, b] is tractable, as it is \({\mathscr{M}}\)-transformable.

Proof

If n = 4, then we are done by Corollary 2.29. Thus, assume that n ≥ 5.

where \(\hat {f} = [0, 1, 0, \dotsc , 0, b]\). We show how to construct the following three signatures: [0,0,0,1,0], [0,1,0,0,0], and \(\hat {g}\), where \(\hat {g}\) is defined by (6.7). Then we are done by Lemma 6.7.

Consider the gadget in Fig. 7. We assign \(\hat {f}\) to the circle vertices and [0,1,0] to the square vertices. The signature of the resulting gadget is [0,0,0,1,0] up to a nonzero factor of b.

Taking a [0,1,0] self loop on [0,0,0,1,0] gives [0,0,1] = [0,1]^⊗2. We connect this back to \(\hat {f}\) through [0,1,0] until the arity of the resulting signature is either 4 or 5, depending on the parity of n. If n is even, then we have [0,1,0,0,0] as desired. Otherwise, n is odd and we have [0,1,0,0,0, b or 0], where the last entry is b if n = 5 and 0 if n > 5. Connecting [0,1]^⊗2 through [0,1,0] to \(\hat {f}\) twice more gives [0,1]. We connect this through [0,1,0] to [0,1,0,0,0, b or 0] to get [0,1,0,0,0] as desired.

Taking a [0,1,0] self loop on [0,1,0,0,0] gives [1,0,0] = [1,0]^⊗2. Now consider the gadget in Fig. 7b. We assign \(\hat {f}\) to the circle vertices, [1,0]^⊗2 to the triangle vertices, and [0,1,0] to the square vertices. Up to a factor of b², the signature of the resulting gadget is \(\hat {g}\) with signature matrix \(M_{\hat {g}}\) given in (6.7). To see this, first replace the two copies of the signatures [1,0]^⊗2 assigned to the triangle vertices with two copies of [1,0] each. Then notice that \(\hat {f}\) simplifies to a weighted equality signature when connected to [1,0] through [0,1,0]. □

Proof Proof of Theorem 6.1

The proof is by induction on n. The base cases of n = 3 and n = 4 are proved in Theorem 2.22. Now assume n ≥ 5.

Lemma 7.1

\({\text {Pl-Holant}\left ({\neq }_{2}\mid {=}_{3},[0,1,0,0]\right )}\) is #P-hard.

Proof

By connecting two copies of [0,1,0,0] together via ≠₂, we have [0,1,0,0,0] on the right. Consider the gadget in Fig. 12a. We assign =₃ to the triangle vertices, [0,1,0,0] to the circle vertices, ≠₂ to the square vertices, and [0,1,0,0,0] on the diamond vertex in the middle. Let f be the signature of this gadget.

We claim that the support of f is {0011,0110,1100,1001}. To see this, notice that [0,1,0,0,0] in the middle must match exactly one of the half edges, which forces the corresponding equality signature to take the value 0 and all other equality signatures to take value 1. The two [0,1,0,0]’s adjacent to the equality assigned 0 must have 0 going out, and the other two [0,1,0,0]’s have 1 going out.

Now we consider the gadget in Fig. 12a again. This time we place [0,1,0,0] on each triangle, =₃ on each circle, f on the middle diamond, and again ≠₂ on each square. Now notice that each support of f makes two [0,1,0,0]’s that are cyclically adjacent on the outer cycle to become [0,1,0] and the other two [1,0,0]. It is easy to see that the support of the resulting signature is {0111,1011,1101,1110}. Therefore it is the reversed ExactOne₄ signature [0,0,0,1,0] (namely AllButOne₄). The whole gadget is illustrated in Fig. 13, where each circle is assigned [0,1,0,0], triangle =₃, and square ≠₂.

Finally, we build the gadget in Fig. 12b. We place =₃ on each circle and ≠₂ on each square. It is easy to see that there are only two support vectors of the resulting signature, which are 0101 and 1010. Recall the definition (6.7) of the partial crossover \(\hat {g}\). This gadget realizes exactly \(\hat {g}\).

By Lemma 6.7, \({\text {Pl-Holant}\left ({\neq }_{2}\mid [0,1,0,0,0],[0,0,0,1,0],\hat {g}\right )}\) is #P-hard. We have constructed [0,1,0,0,0], [0,0,0,1,0], and \(\hat {g}\) on the right side. Therefore \({\text {Pl-Holant}\left ({\neq }_{2}\mid {=}_{3},[0,1,0,0]\right )}\) is #P-hard. □

Lemma 7.2

Then Pl-Holant(g) is #P-hard.

Proof

Let h = [2,1,1]. We show that Pl-#CSP(h) ≤_T Pl-Holant(g) in two steps. In each step, we begin with a signature grid and end with a new signature grid such that the Holant values of both signature grids are the same. This follows from Theorem 2.24, since \(\operatorname {Pl-\#CSP}(h) \equiv {\text {Pl-Holant}\left (\mathcal {E}\mathcal {Q}\mid h\right )}\) by (2.2).

For step one, let G = (U, V, E) be an instance of \({\text {Pl-Holant}\left (\mathcal {E}\mathcal {Q}\mid h\right )}\). Fix an embedding of G in the plane. This defines a cyclic ordering of the edges incident to each vertex. Consider a vertex u ∈ U of degree k. It is assigned the signature =_k. We decompose u into k vertices. Then we connect the k edges originally incident to u to these k new vertices so that each vertex is incident to exactly one edge. We also connect these k new vertices in a cycle according to the cyclic ordering induced on them by their incident edges. Each of these vertices has degree 3, and we assign them =₃. Clearly the Holant value is unchanged. This completes step one. An example of this step applied to a vertex of degree 4 is given in Fig. 14a. The resulting graph has the following properties: (1) it is planar; (2) every vertex is either degree 2 (in V and assigned h) or degree 3 (newly created and assigned =₃); (3) each degree 2 vertex is connected to two degree 3 vertices; and (4) each degree 3 vertex is connected to one degree 2 vertex and two other degree 3 vertices.

Now step two. For every v ∈ V, v has degree 2. We contract the two edges incident to v, or equivalently, we replace the two circle vertices and one triangle vertex boxed in Fig. 14b with a single (square) vertex of degree 4. The resulting graph \(G^{\prime } = (V^{\prime },E^{\prime })\) is planar and 4-regular.

Next we determine what is the signature on \(v^{\prime }\in V^{\prime }\) after this contraction. Clearly the two inputs to each original circle have to be the same (as illustrated in the first figure in Fig. 14b). Therefore its support is 0000,0110,1001,1111, listed starting from the diamond and going counterclockwise. Moreover, due to the triangle assigned h in the middle, the weight on 0000 is 2, and every other weight is 1. Hence it is exactly the signature g, with the diamond in Fig. 14b marking the first input bit. This finishes the proof. □

Remark 4

From the planar embedding of the graph G, treating h vertices as edges, the resulting graph \(G^{\prime }\) is known as the medial graph of G. The (constructive) definition is usually phrased in the following way. The medial graph G_m of plane graph G has a vertex on each edge of G and two vertices in G_m are joined by an edge for each face of G in which their corresponding edges occur consecutively. See Fig. 15 for an example. However, our construction described in the proof clearly extends to nonplanar graphs as well.

Lemma 7.3

\({\text {Pl-Holant}\left ({\neq }_{2}\mid {=}_{4},[0,1,0,0]\right )}\) is #P-hard.

Proof

Consider the gadget in Fig. 16. We assign binary disequality ≠₂ to the square vertices, =₄ to the circle vertices, and [0,1,0,0] to the triangle vertices. We show that the support of the resulting signature is the set {00110011,11001100,11111111}, where each vector is the assignment ordered counterclockwise starting from the diamond point.

We call the equality signature =₄ in the middle the origin. There are two possible assignments at the origin. If it is assigned 0, then every adjacent perfect matching signature [0,1,0,0] is matched to the half edge towards the origin, and every equality =₄ is forced to be 1. This gives the support vector 11111111.

The other possibility is that the origin is 1. In this case, we can remove the origin leaving the outer cycle, with every [0,1,0,0] becoming [0,1,0]. This is effectively a cycle of four equalities connected by ≠₂. It is easy to see that there are only two support vectors, which are exactly 00110011 and 11001100.

Every pair of half edges at each corner always take the same value. We further connect each pair of these edges to different copy of =₄ via two copies of ≠₂. This results in a gadget with signature f whose support is the complement of the original support, that is, {11001100,00110011,00000000}.

Now consider the gadget in Fig. 17a. We assign ≠₂ to the square vertices, =₄ to the circle vertices, [0,1,0,0] to the triangle vertices, and f to the pentagon vertex. Notice that each pair of edges coming out of the pentagon vertex are from the same corner of the gadget in Fig. 16 used to realize f. We now study the signature of this gadget.

Notice that if an =₄ on the outer cycle is assigned 0, then the two adjacent perfect matchings must match half edges toward that =₄, and their outgoing edges must be 0. Furthermore, the two =₄ one more step away must be 1. A further observation is that any pair of consecutive =₄’s cannot be both 0, and if a pair of consecutive =₄’s are both 1, then the [0,1,0,0] between them must have a 1 going out. In Fig. 17a, we call the pentagon connecting to four equalities =₄ on the upper right f₁ and the other one f₂. Let g be the signature of resulting gadget. We further order the external wires of f₁, f₂, and g counterclockwise, each starting from edge marked with a diamond. With this notation and these observations, we get Table 17b listing the support of g. The support of g is {11111111,01111000,11110000,10000111,00000000,00001111,00000000}, and 00000000 has multiplicity 2.

By Lemma 7.2 \(\operatorname {Pl-Holant}(g^{\prime })\) is #P-hard. Hence \({\text {Pl-Holant}\left ({\neq }_{2}\mid {=}_{4},[0,1,0,0]\right )}\) is #P-hard. □

Lemma 7.4

Proof

We can construct =_ℓk on the right, for any integer ℓ ≥ 1, by ≠₂ on the left and =_k on the right, as follows. If we connect two copies of =_k via ≠₂ we get a signature of arity 2k − 2 with k − 1 consecutive external wires labeled + and the others labeled −. As k ≥ 3, we can take 2 wires of the k − 1 wires labeled − and attach to two copies of =_k via two ≠₂. This creates a signature of arity 3(k − 1) + (k − 3) with 3(k − 1) consecutive wires labeled + and the other k − 3 wires labeled −. Finally connect k − 3 pairs of adjacent + / − labeled wires by ≠₂ recursively. This creates a planar gadget with an equality signature of arity 3(k − 1) − (k − 3) = 2k, up to a nonzero constant factor. This can be extended to any =_ℓk by applying the same process on any consecutive k wires.

We construct ExactOne_{2+ℓ(d− 2)} on the right, for any integer ℓ ≥ 1, by connecting ℓ many copies of ExactOne_d sequentially via ≠₂.

Next we construct [0,1]^⊗r for some integer r ≥ 1 on the right hand side. We get [1,0]^{⊗(d− 2)} by a self-loop of ExactOne_d via ≠₂, ignoring the factor 2. We pick an integer ℓ large enough so that d − 2 < ℓk. Then we connect [1,0]^{⊗(d− 2)} to =_ℓk via ≠₂ to get [0,1]^{⊗(ℓk−d+ 2)}. Thus r = ℓk − d + 2 suffices.

Given an instance Ω of \({\text {Pl-Holant}\left ({\neq }_{2}\mid {=}_{k},{\text {\sc ExactOne}_{d}},[0,1],\mathcal {F}\right )}\) with an underlying plane graph G, consider the dual graph G^∗ of G. Take a spanning tree T of G^∗, with the external face as the root. In each face F, let c_F be the number of [0,1]’s in the face F. We start from the leaves to recursively move all the pinnings of [0,1] to the external face. Suppose we are working on the face F as a leaf of T, and it is not the root (the external face). If c_F = 0 then we just remove the leaf from T and recurse on another leaf. Otherwise we remove all [0,1]’s in F, creating c_F dangling edges in the face F. Let s be the smallest integer such that sr ≥ c_F. We replace the ≠₂ edge bordering between F and its parent \(F^{\prime }\) by a chain of three signatures: ≠₂, ExactOne_{2+ℓ(d− 2)} and ≠₂, where ℓ is an integer such that ℓ(d − 2) ≥ sr − c_F. (Notice that if ℓ(d − 2) many dangling edges of ExactOne_{2+ℓ(d− 2)} are all pinned to 0, then this chain becomes a chain of three (≠₃)’s, and thus functionally equivalent to the original single ≠₂ between F and \(F^{\prime }\).) From ExactOne_{2+ℓ(d− 2)} there are two edges connected to the two adjacent copies of ≠₂. Of the other ℓ(d − 2) edges we will put sr − c_F many dangling edges in F, and the remaining ℓ(d − 2) − (sr − c_F) dangling edges in \(F^{\prime }\). Hence there are sr dangling edges in F, including those c_F many that were connected to [0,1]’s via ≠₂ before we removed the [0,1]’s. We put s copies of [0,1]^⊗r inside the face F to pin all of them in a planar way. We add ℓ(d − 2) − (sr − c_F) to \(c_{F^{\prime }}\), and they are all pinned to 0 (by connecting to [0,1] via ≠₂). Remove the leaf F from T, and recurse.

After the process, all [0,1]’s are in the external face of G. Suppose the number is p. We put r disjoint copies of G together to form a planar signature grid. Apply a total of pr many [0,1]’s by p copies of [0,1]^⊗r in a planar way. This is now an instance of \({\text {Pl-Holant}\left ({\neq }_{2}\mid {=}_{k},{\text {\sc ExactOne}_{d}},\mathcal {F}\right )}\) and the Holant value is the r th power of that of Ω. Since the Holant value of Ω is a nonnegative integer, we can take the r th root and finish the reduction. □

Corollary 7.5

If d ≥ 3 and k ∈{3,4}, then \({\text {Pl-Holant}\left ({\neq }_{2}\mid {=}_{k},{\text {\sc ExactOne}_{d}}\right )}\) is #P-hard.

Lemma 7.6

Let G = (L ∪ R, E) be a nonempty planar bipartite (multi)-graph with parts L and R. If every vertex in L has degree at least 6 and every vertex in R has degree at least 3, then G is not simple.

Proof

a contradiction. Here we used the trivial fact that 1/2 = 1/6 + 1/3. □

Lemma 7.7

For any integer k ≥ 6, \({\text {Pl-Holant}\left ({\neq }_2\mid {=}_k,\mathcal {E}\mathcal {O},\neq _2,[1,0],[0,1]\right )}\) is tractable.

Proof

Let Ω be an instance of \({\text {Pl-Holant}\left ({\neq }_2\mid {=}_k,\mathcal {E}\mathcal {O},\neq _2,[1,0],[0,1]\right )}\). Without loss of generality, we assume that Ω is connected. Any occurrence of ≠₂ of the right hand side can be removed as follows: It is connected to two adjacent copies of ≠₂ of the left hand side. We replace this chain of three copies of ≠₂ by a single ≠₂ from the left hand side.

The given signatures have no weight, however the proof below can be adapted to the weighted case. For the unweighted case, we only need to count the number of satisfying assignments. We call an edge in the bipartite instance graph of Ω pinned if it has the same value in all satisfying assignments, if there is any. Clearly any edge incident to a vertex assigned [1,0] or [0,1] is pinned.

When an edge is pinned to a known value, we can get a smaller instance of the problem \(\operatorname {Pl-Holant}({\neq }_{2}\mid =_{k},\mathcal {E}\mathcal {O},\neq _{2},[1,0],[0,1])\) without changing the number of satisfying assignments. In our algorithm we may also find a contradiction and simply return 0. If e is a pinned edge, then it is adjacent to another edge \(e^{\prime }\) via ≠₂ on the left hand side, and both e and \(e^{\prime }\) are pinned. We remove e, \(e^{\prime }\), and ≠₂, and perform the following on e (and on \(e^{\prime }\) as well). If the other endpoint of e is u = [1,0] or [0,1] we either remove that u if the pinned value on e is consistent with u, or return 0 otherwise. If the other endpoint of e is =_k, then all edges of this =_k are pinned to the same value which we can recursively apply. If the other endpoint of e is \({\text {\sc ExactOne}_{d}} \in \mathcal {E}\mathcal {O}\), then we replace this signature by ExactOne_d− 1 when the pinned value is 0; or if the pinned value is 1 then the remaining d − 1 edges of this ExactOne_d are pinned to 0 which we recursively apply. Notice that we may create an ExactOne₂ (i.e. ≠₂) on the right hand side when we pin 0 on ExactOne₃. Such ≠₂’s are replaced as described at the beginning. It is easy to see that all these steps do not change the number of satisfying assignments, and work in polynomial time.

If Ω does not contain any \(\mathcal {E}\mathcal {O}\) signatures, i.e., any ExactOne_d function (for some d ≥ 3), then Ω is an instance of \({\mathscr{P}}\) and therefore tractable. If Ω does not contain any =_k, then it is an instance of \({\mathscr{M}}\) and therefore also tractable. So we may assume Ω contains at least one =_k and at least one \(\mathcal {E}\mathcal {O}\) signature. Then, we claim that there always exists an edge in Ω that is pinned, or there is a contradiction. Furthermore, in polynomial time we can find a pinned edge with a known value, or return that there is a contradiction. (If there is a contradiction in Ω, we may still return a purported pinned edge with a known value, which we can apply and simplify Ω. The contradiction will eventually be found.) The lemma follows from the claim, for we either recurse on a smaller instance or have a tractable instance.

Now we assume Ω is an instance where at least one =_k and at least one \({\text {\sc ExactOne}_{d}} \in \mathcal {E}\mathcal {O}\) appear. We assume no ≠₂ appears on the right hand side. If any [1,0] or [1,0] appear, then we have found a pinned edge with a known value. Hence we may assume neither [1,0] nor [1,0] appears in Ω. So we may assume Ω is an instance for \({\text {Pl-Holant}\left ({\neq }_2\mid {=}_k,\mathcal {E}\mathcal {O}\right )}\).

If a signature \({\text {\sc ExactOne}_{d}} \in \mathcal {E}\mathcal {O}\) is connected to itself by a self-loop through a ≠₂, then there are two choices for the assignment on this pair of edges through the ≠₂, but the remaining d − 2 ≥ 1 edges are pinned to 0. We can keep track of the factor 2 and have found a pinned edge with a known value. Thus we may assume there are no self-loops via ≠₂ on \(\mathcal {E}\mathcal {O}\) signatures.

We can now use our definition of an E_k-block (before Lemma 7.6) as a connected component composed of =_k and ≠₂. All external connecting edges of each E_k-block are marked with + or − and this can be found by testing bipartiteness of an E_k-block where we treat ≠₂’s as edges and =_k’s as vertices. If any E_k-block is not bipartite, we return 0. Such an E_k-block is called trivial. In the following we may assume no trivial E_k-block exists. We contract all E_k-blocks and maintain planarity, as described earlier: For each E_k-block we contract two vertices that are connected by an edge, one edge at a time, and remove self loops in this contraction process. Any nontrivial E_k-block of arity 2 has signature ≠₂, by (7.9). If there is a nontrivial E_k-block of arity 2, we replace it with an edge labeled by ≠₂ to form an instance \({\Omega }^{\prime }\), maintaining planarity, such that any pinned edge in \({\Omega }^{\prime }\) corresponds to a pinned edge in Ω. This new edge is between \(\mathcal {E}\mathcal {O}\) signatures and can be dealt with as described earlier. So we may assume the arity of any E_k-block is at least 4. Since k ≥ 6, the only possible E_k-blocks of arity 4 are those in Fig. 19a up to a rotation. Since there is at least one ExactOne_d signature with d ≥ 3, forming E_k-blocks does not consume all of Ω.

After these steps we may consider Ω a bipartite graph, with one side consisting of E_k-blocks and the other side \(\mathcal {E}\mathcal {O}\) signatures. And they are now connected by edges labeled by =₂.

Suppose there are parallel edges between an E_k-block and an ExactOne_d signature. We show that this always leads to some pinned edges. If two parallel edges are marked by the same sign in the E_k-block, then they must be pinned to 0. If they are marked by different signs, then the remaining d − 2 ≥ 1 edges of the ExactOne_d signature must be pinned to 0. Therefore, we may assume there are no parallel edges between any E_k-block and any \(\mathcal {E}\mathcal {O}\) signature.

The next thing we do is to consider E_k-blocks of arity 4 with \(\mathcal {E}\mathcal {O}\) signatures together. Call a connected component consisting of E_k-blocks of arity 4 and \(\mathcal {E}\mathcal {O}\) signatures an EO-Eq-4-block. Figure 20a illustrates an example. Notice that the two possibilities of E_k-blocks of arity 4 can be viewed as two parallel ≠₂’s but with some correlation between them. This is illustrated in Fig. 19b. Note that the two dotted lines in Fig. 19b represent different correlations.

At this point we would like to replace every E_k-block of arity 4 by two parallel ≠₂’s. However this replacement destroys the equivalence of the Holant values, before and after.

The surprising move of this proof is that we shall do so anyway!

Suppose we ignore the correlation for the time being and replace every E_k-block of arity 4 by two parallel ≠₂’s (each parallel copy of ≠₂ is technically a path of length 2, with the middle vertex labeled by ≠₂) as in Fig. 19b. This replacement produces a planar signature grid Ω₁. Every edge in Ω₁ corresponds to a unique edge in Ω. The set of satisfying assignments of Ω₁ is a superset of that of Ω. Moreover, if there is an edge pinned in Ω₁ to a known value, the corresponding edge is also pinned in Ω to the same value. Once we find that in Ω₁ we revert back to work in Ω and apply the pinned value to the pinned edge.

All that remains to be shown is that pinning always happens in Ω₁. Each EO-Eq-4-block splits into some number of connected components in Ω₁. Suppose some component contains a cycle. Such a cycle must alternate between ≠₂ (these are the newly created ones from splitting the E_k-blocks of arity 4) and ExactOne_d signatures for d ≥ 3 (the cycle may involve only one ExactOne_d and one ≠₂, in which case the cycle has length 2). Each cycle has even length (as each copy of ≠₂ takes length 2), and there are exactly two potential satisfying assignments, which assign exactly one 0 and one 1 to the two cycle edges incident to each ExactOne_d signature. Then any edge not on the cycle but incident to some vertex in the cycle is pinned to 0. Such edges must exist, for ExactOne_d signatures in the cycle are of arity at least 3. Thus we have found pinned edges.

Hence we may assume there are no cycles in these components, and every such component forms a tree. We can view this tree as a tree on vertices labeled by \(\mathcal {E}\mathcal {O}\) functions and edges by ≠₂’s. Since we have at least one copy of ≠₂ in each component, and it does not form a loop on an \(\mathcal {E}\mathcal {O}\) signature, the tree has n ≥ 2 vertices, and n − 1 edges. Similar to the discussion in item 1 above for connecting two \(\mathcal {E}\mathcal {O}\) functions ExactOne_d and ExactOne_ℓ by a single ≠₂, the whole tree is an ExactOne_t function for some arity t. Since each vertex in the tree has degree at least 3, the arity t ≥ 3n − 2(n − 1) = n + 2 ≥ 4. We replace these components by ExactOne_t’s.

Thus, each connected component in the graph underlying Ω₁ is a planar bipartite graph with E_k-blocks of arity at least 6 on the one side and \(\mathcal {E}\mathcal {O}\) signatures on the other. By Lemma 7.6, no component is simple, which means that there are parallel edges between some E_k-block and some \(\mathcal {E}\mathcal {O}\) signature. As discussed earlier, there must exist some pinned edge, and we can find a pinned edge with a known value in polynomial time. This finishes the proof. □

Lemma 7.8

Lemma 7.7 holds when each indicated signature is replaced by any set of weighted versions of the signature of the same type.

Lemma 7.9

Let G = (L ∪ R, E) be a planar bipartite graph with parts L and R. Every vertex in L has degree at least 5 and every vertex in R has degree at least 3. If G is simple, then there exists one of the two wheel structures in Fig. 21 as an induced subgraph in G (where the five occurrences of the circle vertices on the outer circuit of length 10 may not be all distinct).

Proof

Note that since G is bipartite, every k-gon face has k even. And since G has no parallel edges, we have k > 2. Hence k ≥ 4. Also, the number of occurrences v appears when we traverse all faces is the degree of v. Thus the total score for v coming from all faces is at most \(\frac {\deg (v)}{4}\). Now we have the following claim.

The claim is proved.

Since the total score is positive, there must exist v ∈ L, \(\deg (v) = 5\), and s_v > 0. Because G is bipartite and simple, v and its five neighboring vertices v₁,…, v₅ are six distinct vertices.

contrary to the assumption that s_v > 0. Hence v is adjacent to exactly one occurrence of k-gon with k ≥ 6—we will call it F_v—and all other occurrences are 4-gons. Clearly F_v is distinct from the 4-gons. Moreover these four occurrences of 4-gons are all distinct 4-gons. This is because, by cyclically renaming v₁,…, v₅, we may name {v, v_i, v_i+ 1, u_i} for 1 ≤ i ≤ 4 the vertices of the four occurrences of 4-gons. If there are any multiple occurrences of these 4-gons, by G being bipartite we would have {v_i, v_i+ 1} = {v_j, v_j+ 1} for some 1 ≤ i < j ≤ 4. This is a contradiction since {v₁,…, v₅} are five distinct vertices.

Hence in any case, we have \(s_{u}\le -\frac {\ell }{12}\). This implies that the total score of u and all positively scored vertices associated to u is at most 0. However each positively scored vertex is associated to a vertex in R. Hence the total score cannot be positive. This is a contradiction.

If all neighbors of v have degree 3, that is a wheel of type 1 as in Fig. 21a. If one neighbor of v has degree ≥ 4, that is a wheel of type 2 as in Fig. 21b. □

Lemma 7.10

\({\text {Pl-Holant}\left ({\neq }_2\mid {=}_5,\mathcal {E}\mathcal {O},\neq _2,[1,0],[0,1]\right )}\) is tractable.

Proof

We proceed as in Lemma 7.7 up until the point of getting Ω₁. Note that due to (7.9) the only nontrivial E₅-blocks of arity ≤ 4 are ≠₂ and those in Fig. 19a. Moreover, each connected component of Ω₁ is planar and bipartite with vertices on one side having degree at least 5 and those on the other at least 3. We only need to show that there are edges pinned in Ω₁.

Unlike in Lemma 7.7, the underlying graph of Ω₁ does not satisfy the condition of Lemma 7.6 but that of Lemma 7.9. If the graph is not simple, then there are pinned edges similar to Lemma 7.7. Otherwise by Lemma 7.9, the wheel structure in Fig. 21 appears. Note that by (7.9), n₊ ≡ n₋ mod 5 and the arity n₊ + n₋ = 5 imply that the center vertex, which is an E₅-block, has signature =₅. All we need to show is that wheel structures of either type contain pinned edges.

First we claim that if a wheel of either type has a E₅-block, call it E₁, on the outer circuit that has different sign labels (+/−) on the two edges incident to it along the circuit, then the center vertex denoted by E_o and has signature =₅, is pinned. This is pictured in Fig. 22a. It does not matter whether the wheel is type 1 or 2, or the position of E₁ relative to the special triangle P₁ in type 2. Because E_o is an equality, both e₁ and e₂, the two edges incident to E_o that are connected to the two \(\mathcal {E}\mathcal {O}\) signatures flanking E₁, must take the same value. If both e₁ and e₂ are assigned 1, then the two incoming wires of E₁ along the circuit have to be both assigned 0, whereas they are marked by different signs. This is a contradiction. Hence both e₁ and e₂ are pinned to 0 as well as all edges incident to E_o.

We may therefore assume that each E₅-block has equal signs along the outer circuit, either + + or −− (some may have + + while others may have −−). Then as far as the two edges along the outer circuit incident to each E₅-block are concerned, each E₅-block serves as a binary equality; this is true regardless whether the five triangle vertices for E₅-block’s along the outer circuit in Fig. 21 are distinct or not.

Suppose the wheel has type 1. If the edges incident to E_o are assigned 0, then the five ExactOne₃ signatures along the outer circuit have all effectively become ≠₂ along the circuit. If we now consider the E₅-block signatures along the outer circuit as equalities (since they have signs + + or −−) and treat them as edges, we get a cycle on the five ExactOne₃ signatures along the outer circuit as a cycle of five ≠₂’s. This has no satisfying assignment. Hence E_o and all its incident edges are pinned to 1.

Otherwise the wheel is of type 2, and each E₅-block has signs + + or −− along the outer circuit. We denote by P₁ the special ExactOne_d function that has arity d > 3. We claim that the two edges e and \(e^{\prime }\) incident to P₁ along the circuit are both pinned to 0. This is illustrated in Fig. 22b. As P₁ is ExactOne_d, at most one of e and \(e^{\prime }\) is 1. If one of e and \(e^{\prime }\) is 1, the other is 0, and as P₁ is an ExactOne_d function its edge to E_o is also 0, and thus all edges incident to E_o are 0. As all five neighbors of E_o are \(\mathcal {E}\mathcal {O}\) functions, the four ExactOne₃ functions effectively become (≠₂) functions along the wheel, and we can remove E_o and its incident edges. This becomes the same situation as in the previous case of type 1, where effectively a circuit of five binary equalities are linked by five binary disequalities, which has no valid assignment. This implies that both e and \(e^{\prime }\) are pinned to 0. This finishes the proof. □

Lemma 7.11

Lemma 7.10 holds when each indicated signature is replaced by any set of weighted versions of the signature of the same type.

Lemma 7.12

If integers d₁, d₂, k ≥ 3, then \(\text {Pl-Holant}({\neq }_{2}\mid {=}_{k},{\text {\sc ExactOne}_{d_{1}}},\) \({\text {\sc AllButOne}_{d_{2}}})\) is #P-hard.

Proof

We first get the pinning signatures [1,0] and [0,1]. We apply Lemma 7.4 to create [0,1]. Then note that AllButOne_d is just flipping the roles of 0 and 1 in ExactOne_d, we can get [1,0] too. So we get both [1,0] and [0,1] by applying Lemma 7.4 twice. With both [1,0] and [0,1] in hand, we may reduce d₁ (respectively d₂) to 4 if d₁ > 4 (respectively d₂ > 4), and obtain ExactOne₄ and AllButOne₄. If either of the two arities d₁ or d₂ is 3, then we connect two copies together via ≠₂ to realize an arity 4 copy.

Moreover, we use the gadget illustrated in Fig. 23 to create the function \(\hat {g}\) in Lemma 6.7 as an E_k-block. Then by Lemma 6.7, Pl-Holant(≠₂∣=_k, \({\text {\sc ExactOne}_{d_1}},{\text {\sc AllButOne}_{d_2}})\) is #P-hard. □

Lemma 7.13

Let \(f\in {\mathscr{P}}_{2}\), \(g_{1}\in {\mathscr{M}}_{4}^{+}\), \(g_{2}\in {\mathscr{M}}_{4}^{-}\) be non-degenerate signatures with arity ≥ 3. Then Pl-Holant(f, g₁, g₂) is #P-hard.

Proof

where in the last line we ignored several nonzero factors. The lemma follows from Lemma 7.12. □

Lemma 7.14

Let \(\mathcal {F}\) be a set of symmetric signatures. Suppose \(\mathcal {F}\) contains a non-degenerate signature \(f\in {\mathscr{P}}_{2}\) of arity n ≥ 3 and a binary signature h. Then \(\operatorname {Pl-Holant}(\mathcal {F})\) is #P-hard unless \(h\in Z{\mathscr{P}}\), or \(\operatorname {Pl-\#CSP}^{2}(DZ^{-1}\mathcal {F})\le _{T}\operatorname {Pl-Holant}(\mathcal {F})\) for some diagonal transformation D.

Proof

where in the second line we ignore a nonzero factor on ≠₂. Hence by Theorem 2.24, \(\operatorname {Pl-Holant}(\mathcal {F})\) is #P-hard unless \(\left ((ZD_{1})^{-1}\right )^{\otimes 2}h\in {\mathscr{P}}\) (cases 1, 2 or 3 in Theorem 2.24) or \(\left ((ZD_{1})^{-1}\right )^{\otimes 2}h=[a,b,c]\) for some \(a,b,c\in \mathbb {C}\) such that ac≠ 0 and (a/c)²ⁿ = 1 (cases 4 or 5 in Theorem 2.24).

as r²ⁿ = 1.

The last problem is \(\operatorname {Pl-\#CSP}^{2}(DZ^{-1}\mathcal {F})\). Thus \(\operatorname {Pl-\#CSP}^{2}(DZ^{-1}\mathcal {F})\le _{T}\operatorname {Pl-Holant}(\mathcal {F})\). □

Lemma 7.15

Let \(\mathcal {F}\) be a set of symmetric signatures. Let \({\mathcal {F}_{nd}^{\ge 3}}\) be the set of non-degenerate signatures in \(\mathcal {F}\) of arity at least 3. Suppose \({\mathcal {F}_{nd}^{\ge 3}}\) contains some \(f\in {\mathscr{M}}_{4}\) of arity d ≥ 3. Moreover, suppose \({\mathcal {F}_{nd}^{\ge 3}}\cap {\mathscr{P}}_{2}\) is nonempty, and let k be the greatest common divisor of the arities of signatures in \(\mathcal {F}^{*}\cap {\mathscr{P}}_{2}\). If k ≤ 4, then \(\operatorname {Pl-Holant}(\mathcal {F})\) is #P-hard.

Proof

where we ignore nonzero factors on ≠₂ and ExactOne_d.