↩︎

0.0.1 Background↩︎

Arity reduction is perhaps the most common component in proof templates for dichotomy theorems. Suppose we aim to prove a complexity dichotomy theorem for a problem class \(\{ \#' \mathcal{F} \mid \mathcal{F} \text{ is some set of some kind of functions}\}\), and two maximal tractable classes are known to be \(\mathcal{A}\) and \(\mathcal{B}\). In addition to the two algorithms for \(\mathcal{A}\) and \(\mathcal{B}\), one must also show that for any set \(\mathcal{F}\), if \(\mathcal{F} \not \subseteq \mathcal{A}\) and \(\mathcal{F} \not \subseteq \mathcal{B}\), then \(\#' \mathcal{F}\) is \(\#\mathrm{P}\)-hard. Arity reduction serves as the inductive step in this inductive proof template. Since \(\mathcal{F} \not \subseteq \mathcal{A}\), there exists \(S \in \mathcal{F}\) such that \(S \not \in \mathcal{A}\), where \(S\) is a \(d\)-ary function for some arbitrary natural number \(d\). Induction is performed on the arity \(d\) of \(S\), constructing functions of smaller arity within the problem \(\#' \mathcal{F}\) while preserving the property of not belonging to \(\mathcal{A}\) (referred to as non-\(\mathcal{A}\)), until the arity is reduced to a quaternary function \(S'\) (or some other fixed small arity). We apply the same procedure to a non-\(\mathcal{B}\) function \(T\) to obtain \(T'\). This constitutes the inductive process.

As for the hardness of \(\#'\{ S', T'\}\), this belongs to the base case of the induction, which must be proved separately. Nowadays, thanks to the foundations laid by established dichotomy theorems, this base case is often handled similarly: we show that either \(\#'\{ S'\}\) is hard, or \(\#'\{ S'\}\) can realize equality functions of arbitrary arity (or other auxiliary functions), thereby allowing us to invoke the dichotomy theorem for the \(\#\mathrm{CSP}\) class (or other corresponding classes).

The problem class \({\# \mathcal{F}}\) possesses an obvious tractable class \(\langle T \rangle\) (consisting of all functions that can be decomposed via tensor product into binary functions). In the study of the dichotomy theorem for the real-valued subclass [1], a highly significant phenomenon was encountered and resolved: the non-\(\langle T \rangle\) property is not guaranteed to survive arity reduction. Specifically, there exist two exceptional functions, \(f_6\) and \(f_8\), for which no reduction method preserves the non-\(\langle T \rangle\) property.

This potential failure of the arity reduction process has gradually led to a new research paradigm. Based on the conditions for successful and failed reduction, the discussion is divided into two cases, termed the lower-set condition and the upper-set condition. Recall that we are currently proving the hardness side of the dichotomy theorem—namely, showing that any problem without a tractable algorithm is hard. Such a problem must contain a non-\(\langle T \rangle\) function \(F\). One case corresponds to when \(F\) can be successfully reduced, yielding a non-\(\langle T \rangle\) quaternary function. The other case corresponds to when \(F\) cannot be successfully reduced: all non-\(\langle T \rangle\) functions fail to reduce to quaternary ones, meaning that any quaternary function belongs to \(\langle T \rangle\) and is the tensor product of two binary functions. The former also corresponds to the base case of the induction and is classified under the lower set, characterized by the existence of an indecomposable true quaternary function (referred to as a "true quaternary"). The latter corresponds to the infinite family of cases of arbitrary arity that the inductive step was supposed to handle. This is classified under the upper set, characterized by the condition that any quaternary function is a tensor product of two binary functions (referred to as a "fake quaternary").

Since the inductive process of arity reduction fails here, why not try directly utilizing the fake quaternary condition (temporarily putting aside the non-\(\langle T \rangle\) function at hand)? This is precisely the precondition for the realnumberizing method. The realnumberizing method disconnects two edges, say \((x,y)\) and \((z,w)\), of a closed tensor network (one with no external edges) to form a quaternary gadget. Since this gadget must be a decomposable fake quaternary, reconnecting them in a different way, such as \((x,z)\) and \((y,w)\), yields a new closed tensor network whose value is related to the previous one. Remarkably, this relation turns out to be a difference by a real factor. The reason is that normalized binary functions form a second-order complex matrix group, in which the trace of every element is real. Since each such operation merely scales the value by a real factor, the original complex number behaves as an invariant constant. The entire problem is then essentially no different from a problem over a real domain, hence the term realnumberizing method.

If realnumberizing can be achieved, it significantly narrows the scope of the study and allows us to invoke the dichotomy theorem for the real-valued subclass [1]. This serves as an indirect approach: rather than directly confronting the difficulties in the complex domain—such as investigating whether more functions like \(f_6\) and \(f_8\) resist arity reduction—we bypass them by showing that all such difficulties have already been resolved and overcome in the real-valued case.

The group phenomenon and realnumberizing are the two most critical engines driving this entire plan. The former provides real traces, while the latter provides the transformation method. Together, they highlight the foundational importance of the dichotomy theorem for the real-valued subclass, a fact that actually came as a surprise to the author.

However, this elegant plan is not quite so straightforward. In this second version, the study under \(C_1\) represents a case that does not easily fall into the nine classes, and we have failed to achieve a complete realnumberizing.

The author first encountered the edge-recombination step of the realnumberizing method on August 25, 2023, during a joint discussion between faculty and students of the University of Chinese Academy of Sciences (UCAS) and the University of Science and Technology of China (USTC). To maintain the independence of their respective research on the \(\#\mathrm{EO}\) counting problem, the two teams discussed this recombination process in the context of the decision version of the problem. Because the decision problem always takes values in \(\{0, 1\}\), there was no notion of function-value realnumberizing. Later, this recombination step was applied to the \(\#\mathrm{EO}\) counting problem [2], yielding the realnumberizing results.

The autonomous nature of the \(C_1\) group condition yields a specific condition: the domain is symmetric under \(0\)-\(1\) bit-flip, i.e., \(F(X) = F(\bar{X})\). Because of the extremely limited auxiliary capability of the \(C_1\) group, which possesses only a single binary function \(=_2\), the realnumberizing method requires taking the \(2^{2d}\)-dimensional value vector of the function \(=_2^{\otimes d}\) as the coefficient vector of a system of equations. This yields linear equations concerning \(\{F(X) \mid X \in \{0,1\}^{2d} \text{ and } X \text{ contains an even number of 1s} \}\), where different variable orderings yield different equations. We hope for this system of equations to be of full rank. However, due to the extremely low auxiliary capability of \(C_1\), the system remains underdetermined (not of full rank) even when combined with the equations arising from the \(0\)-\(1\) symmetry.

Applying a basis change to the \(K\)-basis transforms all tensor networks from the default "edges represent binary equality" to "edges represent binary inequality", i.e., converting the problem from \(\# =_2 \mid \mathcal{F}\) to \(\# \neq_2 \mid \hat{\mathcal{F}}\). Theoretically, this does not alter the essence of the aforementioned difficulties, but it yields a form that is much more conducive to analysis. Under this transformation, the \(C_1\) group condition translates to having only a single binary function \(\neq_2\). In the realnumberizing method, taking the \(2^{2d}\)-dimensional value vector of the function \(\neq_2^{\otimes d}\) as the coefficient vector gives linear equations concerning \(\{F(X) \mid X \in \text{EO}^{2d} \}\). Different orderings of the variables yield different equations, and when combined with the equations derived from the \(0\)-\(1\) symmetry, the system becomes of full rank.

In the descriptions of the two preceding paragraphs, the function set \(\mathcal{F}\) was implicitly substituted by a single function \(F\). In Section 2, we will demonstrate that under the \(C_1\) condition, using realnumberizing to prove this transformation does not alter the computational complexity.

In Section 3, we analyze this full-rank property and successfully achieve realnumberizing for the part \(\{F(X) \mid X \in \text{EO}^{2d} \}\), which is \(F|_{\text{EO}}\).

Although the \(K\)-basis transformation is highly useful—helping us recombine variables, cleanly channel information, capture the tractable parts onto \(\mathrm{EO}\), and leave the intractable, unobservable "black hole" part in \(F - F|_{\text{EO}}\)—it is essentially identical to the form before the transformation. It does not provide any additional information about this "black hole", but merely concentrates its scattered "dark matter" pattern into a centralized "black hole" pattern. (This physical analogy is used somewhat loosely here, please do not take it literally.)

In Section 4, we observe the \(\mathrm{EO}\) part of \(F^{\otimes k}\) to obtain information about the non-\(\mathrm{EO}\) part of \(F\). Then, through a diagonal matrix basis transformation, we transform these non-\(\mathrm{EO}\) parts into either real numbers or pure imaginary numbers that satisfy the domain \(0\)-\(1\) symmetry. Unfortunately, we remain just one step away from invoking the dichotomy theorem for \(\#\mathrm{ARS}\text{-}\mathrm{EO}\). When \(\alpha \notin \text{EO}\) and \(F(\alpha)\) is a non-zero pure imaginary number, this function satisfies \(F(\alpha) = F(\bar{\alpha})\), whereas the ARS condition requires them to be conjugate, i.e., \(F(\alpha) = -F(\bar{\alpha})\). While we had hoped to invoke the Real-Holant dichotomy theorem as in some other cases of the nine classes, or black-box invoke the \(\#\mathrm{ARS}\text{-}\mathrm{EO}\) dichotomy theorem here, we were unable to do so. Therefore, in the first version of this paper, we conjectured that the dichotomy theorem holds for the required problem.

Section 5 records the reflections during this teaching semester. After some analysis, we formulate a more concrete conjecture. We suspect that this conjecture is highly likely to be correct, but proving it requires unfolding the proof details of the \(\#\mathrm{ARS}\text{-}\mathrm{EO}\) dichotomy theorem, particularly several lemmas related to arity reduction.

The proof of a dichotomy theorem is not as simple and straightforward as the inductive arity reduction described at the beginning of this section. It does not merely involve maximal tractable classes; often, inductive reductions on other related function structures are nested within it. For example, in the dichotomy theorem of [4], one must perform reduction on the property that the support set is not an affine subspace. This reduction is encapsulated into a lemma stating that if the support set is not affine, the defined \(\#\mathrm{CSP}\) problem is \(\#\mathrm{P}\)-hard. This encapsulation allows the lemma to use the most common definitions and to be stated simply, but it also hides the reduction conclusions concerning properties other than this structure. The actual, complete long conclusion typically takes the form: either the arity reduction succeeds, or its failure still allows proving \(\#\mathrm{P}\)-hardness. Almost all dichotomy theorems adopt this presentation style, placing the exquisite case analyses in the proof details while leaving only a cleanly encapsulated, concise form in the theorem statement. Even so, this can be daunting to readers, and the dichotomy theorem for \(\#\mathrm{ARS}\text{-}\mathrm{EO}\) is no exception. Faced with this encapsulation, my strategy is to leave professional matters to the professionals and leave this conjecture open.

0.0.1.1 Notation

We use the symbol \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}\mathcal{F}\) as a shorthand for the \(\# \neq_2 \mid \mathcal{F}\) problem. The problem \(\# \mathcal{F}\) is exactly \(\# =_2 \mid \mathcal{F}\). Visually, the symbol "#" resembles a double negation of "=", which remains "="; visually, "\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}\)" looks like a triple negation of "=", so we select "\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}\)" to denote the \(\# \neq_2 \mid \mathcal{F}\) problem. "\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}\)" is pronounced as *sa*, sounding like the Chinese character "卅" (sà).

The \(\#\mathrm{EO}\) problem originally refers to the problem of counting Eulerian Orientations of a graph. It is a special class of \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}\mathcal{F}\) problems where the functions in \(\mathcal{F}\) can take non-zero values only on strings with an equal number of 0s and 1s. (This implicitly requires the functions to be of even arity, which is also true for the edge function \(\neq_2\)). The term "\(\mathrm{EO}\)" has been extended in usage: we sometimes call such functions "\(\mathrm{EO}\) functions", and sometimes refer to the set of such strings as "\(\mathrm{EO}\)" (which can be mnemonically remembered as "equal (or even) opportunity"). The set of such strings of length \(2d\) is denoted by \(\text{EO}^{2d}\). Thus, an \(\mathrm{EO}\) function is a function whose support is contained within \(\mathrm{EO}\). Since \(\mathrm{EO}\) is a subset of the domain, we can define the restriction of a function to it: \(F|_{\text{EO}}\) denotes the function obtained by setting the values of \(F\) outside \(\text{EO}\) to 0.

The first-order group condition, also called the \(C_1\) condition, states that all realizable binary functions in \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}\mathcal{F}\) have the form \(\epsilon \neq_2\) (where \(\epsilon\) is a constant from the codomain, which can be zero).

The upper-set (condition) states that all quaternary functions can be decomposed into the product of two binary functions. Combining the decomposition lemma with the first-order group condition, all realizable quaternary functions are of the form \(\epsilon \neq_2 \otimes \neq_2\).

In this version, the objects of study throughout the paper satisfy the first-order group upper-set condition.

0.0.2 Zero-Value Sharing↩︎

0.0.2.1 Single-Step Recombination of Tensor Networks

Let \(n\) be a fixed positive integer, and consider all \(\neq_2 \mid \mathcal{F}\) tensor networks with \(n\) vertices.

Let \(G\) be an arbitrary network among them, containing two edges \(\neq_2(x,y)\) and \(\neq_2(z,w)\). Let \(G'\) be another network that is identical to \(G\), except that these two edges are removed and replaced by two different edges: \(\neq_2(x,z)\) and \(\neq_2(y,w)\).

We define this transition from \(G\) to \(G'\) as a single step in the realnumberizing process.

Disconnecting the two edges \(\neq_2(x,y)\) and \(\neq_2(z,w)\) of \(G\) yields a quaternary gadget \(H(x,y,z,w)\). The gadget \(H\) must be of the form \(\lambda \neq_2 \otimes \neq_2\). The value of \(G\) obtained by connecting \(H\) with two edges is easily calculated to be either \(2\lambda\) or \(4\lambda\). Similarly, the value of \(G'\) must also be either \(2\lambda\) or \(4\lambda\). Therefore, the values of \(G\) and \(G'\) either both vanish, or both are non-zero with their ratio being \(1\), \(2\), or \(1/2\).

0.0.2.1.1 Zero-Value Sharing

Single-step recombination can be viewed as an "edge" connecting \(G\) and \(G'\). Considering all tensor networks with \(n\) vertices, these edges can connect all such tensor networks. Therefore, the values of these networks either all vanish, or are all non-zero. This conclusion holds for all \(n\), including when \(n=1\). From this, we obtain the following lemma.

0.0.3 Substituting a Function Set with a Single Function↩︎

0.0.4 Domain 0-1 Symmetry and Full Rank↩︎

We say that \(F\) is \(0\)-\(1\) symmetric if \(F(\alpha)=F(\overline{\alpha})\) for any \(\alpha\).

For any \(2d\)-ary Boolean function, \(\mathrm{EO}\) denotes a subset of its domain consisting of all \(0\)-\(1\) strings with exactly \(d\) ones and \(d\) zeros. \(F | _{EO}\) is obtained from \(F\) by setting the values on all strings outside \(\mathrm{EO}\) to \(0\).

Referring to the introduction of full-rank properties in the realnumberizing process in Section 1, it can be seen from the proof of realnumberizing in a later section that the lemma above is formulated precisely to show that the system of linear equations is of full rank with respect to the variables in \(F|_{EO}\).

As early as in the study of the six-vertex model, there was the following obvious calculation process. This process computes the full-rank property for the 4-ary case. There are three pairing patterns for \(\neq_2 \otimes \neq_2\), yielding the functions \([x_1 \neq x_2][ x_3 \neq x_4]\), \([x_1 \neq x_3][ x_2 \neq x_4]\), and \([x_1 \neq x_4][ x_2 \neq x_3]\), respectively. Their function value tables are \(e_\alpha+e_{\bar{\alpha}}+e_\beta+e_{\bar{\beta}}\), \(e_\beta+e_{\bar{\beta}}+e_\gamma+e_{\bar{\gamma}}\), and \(e_\alpha+e_ {\bar{\alpha}}+e_\gamma+e_{\bar{\gamma}}\), respectively, where \(\alpha=0101, \beta=0110, \gamma=0011\), and \(e_\alpha\) denotes a 16-dimensional standard basis vector with a value of \(1\) only at component \(\alpha\). Connecting self-loops to \(F\) in the manner of \([x_1 \neq x_2][ x_3 \neq x_4]\) yields the value \(F(\alpha)+F(\bar{\alpha})+ F(\beta)+ F(\bar{\beta})\). The other two equations are analogous. Combined with the equations for \(0\)-\(1\) symmetry, namely \(F(\theta)=F(\bar{\theta})\) for any \(\theta\), it is straightforward to see that these six equations are exactly sufficient to solve for \(F|_\text{EO}\) with full rank.

During the research of [2], when applying the realnumberizing method via the full-rank approach, it was initially assumed that the proof of full rank for the \(4d\)-ary or \(4^d\) case was essentially the \(d\)-th tensor product of the coefficient matrix of the aforementioned 4-ary case, and thus full rank. Later, Zhuxiao Tang read the draft and discovered that this was incorrect. My co-authors subsequently fixed this error using the approach of Lemma 4.

In the research of this paper, I again followed the incorrect method and wrote the first draft. Later, while explaining the \(C_1\) case to my graduate teaching assistant after an undergraduate class at Yanqi Lake, I realized the logic failed and found the error. I only corrected it after re-reading [2]. Recently, as the semester’s courses have basically ended, I returned to the study of the \(C_1\) case. While trying out some ideas, I seemingly discovered a correction to the previous error, which is recorded below. However, this correction appears to be essentially identical to Lemma 4, and its proof is actually less concise than that of Lemma 4.

Consider the following subsets of the linear space \(\text{EO}^{2d}\) and the subspaces they span.

Define \(A=\{ F \mid F = F|_\text{EO}, F \text{ has a } 0\text{-}1 \text{ symmetric domain, and any binary function obtained after adding } d-1 \\ \text{ binary inequality self-loops to } F \text{ is of the form } \epsilon \neq_2 \}\), and \(B=\{e_\alpha+e_{\bar{\alpha}} \mid \alpha \in \text{EO}\}\).

Clearly, \(B \subseteq A\). Moreover, any function element in \(A\) can be linearly expressed by \(B\). Therefore, the subspaces they span are equal, i.e., \(\langle A \rangle = \langle B \rangle\).

Define \(C=\{ [x_{\pi(1)} \neq x_{\pi(2)}] \cdots [ x_{\pi(2d-1)} \neq x_{\pi(2d)}] \mid \pi \in S_{2d}\}\). Clearly, \(C \subseteq A\). Thus, it suffices to prove \(B \subseteq \langle C \rangle\) to show that the subspaces generated by all three are identical.

We prove \(B \subseteq \langle C \rangle\) by induction on \(d\). For \(d=1,2\), this has already been established.

Now we want to prove \(B_{2d+4} \subseteq \langle C_{2d+4} \rangle\). Choose an arbitrary string in \(B_{2d+4}\). Since the string contains an equal number of 0s and 1s, after a permutation of the variables, we may assume without loss of generality that this string is \(0101 \xi\), where \(\xi \in \text{EO}^{2d}\). Applying the induction hypothesis to the last \(2d+2\) bits, we have \(e_{01\xi}+ e_{10\bar{\xi}} \in B_{2d+2}\subseteq \langle C_{2d+2} \rangle\), meaning that \(e_{01\xi}+ e_{10\bar{\xi}}\) can be linearly expressed by \(C_{2d+2}\). For the first two bits, applying \([x_1 \neq x_2]\), we obtain that \(\langle C_{2d+4} \rangle\) can linearly express \(e_{(01+10) \circ (01\xi+10\bar{\xi})}=e_{0101\xi}+e_{1010\bar{\xi}}+e_{1001\xi}+e_{0110\bar{\xi}}\) (here, we have borrowed regular expression notation without a formal definition).

Similarly, applying the induction hypothesis to the last \(2d\) bits and the 2nd and 3rd bits, we have \(e_{\sqcup 10 \sqcup \xi}+ e_{\sqcup01\sqcup\bar{\xi}} \in B_{2d+2}\subseteq \langle C_{2d+2} \rangle\). Applying \([x_1 \neq x_4]\) yields that \(\langle C_{2d+4} \rangle\) can linearly express \(e_{(0\sqcup\sqcup1+1\sqcup\sqcup0) \circ (\sqcup 10 \sqcup \xi+\sqcup01\sqcup\bar{\xi})}=e_{0101\xi}+e_{1010\bar{\xi}}+e_{1100\xi}+e_{0011\bar{\xi}}\).

Similarly, applying the induction hypothesis to the last \(2d\) bits and the 1st and 3rd bits, we have \(e_{1 \sqcup 0 \sqcup \xi}+ e_{0 \sqcup 1\sqcup \bar{\xi}} \in B_{2d+2}\subseteq \langle C_{2d+2} \rangle\). Applying \([x_2 \neq x_4]\) yields that \(\langle C_{2d+4} \rangle\) can linearly express \(e_{(\sqcup 1 \sqcup 0+\sqcup 0 \sqcup 1) \circ (1 \sqcup 0 \sqcup \xi+0 \sqcup 1\sqcup \bar{\xi} )}=e_{1100\xi}+e_{0011\bar{\xi}}+e_{1001\xi}+e_{0110\bar{\xi}}\).

Summing the first two and subtracting the third, we obtain \(2(e_{0101\xi}+ e_{1010\bar{\xi}}) \in \langle C_{2d+4} \rangle\).

0.0.5 Realnumberizing the EO Part↩︎

This part of the proof remains identical to that in [2].

Because this proof embeds the small step of deriving full rank from Lemma 4, it is slightly cluttered. Briefly speaking, combining each \(\neq_2 ^{\otimes d}\) with \(H\) yields a linear equation regarding \(H|_\text{EO}\). Combined with the equations given by the domain \(0\)-\(1\) symmetry, this system of equations is of full rank (as shown in the proof following Lemma 4 in the previous section). Single-step recombination guarantees that adjacent equations—and, by connectivity, any two equations—have constant terms that differ only by a real factor. Thus, there exists a complex number \(\theta\) such that \(\frac{1}{\theta} H|_\text{EO}\) is the unique solution to a full-rank real system of linear equations.

0.0.6 Observing the Non-EO Part of a Small Function Through the EO Part of a Large Function↩︎

For a string \(\alpha\) of length \(2d\), we define its bias \(r(\alpha)\) as the number of 1s minus the number of 0s. Let \(\mathrm{EO}^{\geq}\) denote the set of all strings with non-negative bias, and let \(\mathrm{EO}^{\leq}\) denote the set of all strings with non-positive bias.

0.0.7 Arity Reduction and Shaping of the Non-EO Part↩︎

According to Lemma 5, it suffices to study the complexity of \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\) defined by such \(H\). Here, \(H\) is at least a 6-ary function, \(H\) satisfies the non-vanishing property, and there exist a domain \(0\)-\(1\) symmetric rational function \(Q\) (\(\mathrm{supp}(Q) \subseteq \mathrm{EO}\)) and a complex number \(\theta\) such that \(H|_{EO}= \theta Q\). Redefining \(H/\theta\) as \(H\), the condition simplifies to: \(H\) takes rational values on \(\mathrm{EO}\) and is \(0\)-\(1\) symmetric.

Let \(Q=H|_\text{EO}\) and \(Q'=H-Q\). We perform a case analysis to study and process the complexity of \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\).

• If \(Q\) is identically zero, we directly invoke Theorem 1 to obtain the complexity classification of \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\).

• Suppose there exists some \(\alpha={0^a1^b}\) with \(a\neq b\) such that \(Q(\alpha)\neq 0\). Among such strings, choose one with the minimum \(|a-b|\), denoted as \(\alpha={0^a1^b}\), where \(a+b \geq 6\). We aim to perform arity reduction while preserving this property until \(a=0\) or \(b=0\), or until the arity is reduced to four, which would contradict the upper-set condition. Without loss of generality, assume \(b>a>0\). That is, there are three variable positions \(x,y,z\) such that \(\alpha|_{xyz}=011\). Rearranging these three positions to the first three coordinates, we write \(\alpha=011\beta\). Consider: \[((x \neq y) H) (1 \beta)=H(011\beta)+H(101 \beta)\] \[((x \neq z) H) (1 \beta)=H(011\beta)+H(110 \beta)\] \[((z \neq y) H) (1 \beta)=H(101\beta)+H(110 \beta)\] Since \(H(011\beta) \neq 0\), at least one of these three functions successfully reduces the arity by two, taking a non-zero value on \(1\beta\). The difference between the numbers of 0s and 1s in \(1\beta\) remains \(|a-b|\).

  Continuing this arity reduction process, we will eventually obtain a function that is non-zero on either the all-1 string or the all-0 string. If the support contains other strings outside \(\mathrm{EO}\) with an even smaller difference between the number of 0s and 1s, we continue the arity reduction on those strings. Eventually, we obtain a new function \(H'\) such that \(H' - H'|_\text{EO}\) is not the zero function, and it takes non-zero values at most on the all-0 and all-1 strings.

The above process shapes \(H\) into \(H'\). Throughout this process, we clearly have \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H' \leq_P \mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\).

In the subsequent analysis, we can prove that either \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H'\) is \(\#\mathrm{P}\)-hard, or \(H'\) can realize certain functions such that \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\) has a known dichotomy theorem with the help of these functions. Since the aforementioned reduction only holds in one direction, providing a polynomial-time algorithm for \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H'\) would have no effect on the complexity classification of the original problem \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\).

We rename \(H'\) as \(F\) and restate the conditions:

\(F = Q + a e_{0^{2d}} + b e_{1^{2d}} = Q + a |0^{2d}\rangle + b |1^{2d}\rangle\), where \(Q\) is a \(0\)-\(1\) symmetric rational \(\mathrm{EO}\) function, and we also have \(a \neq 0\) or \(b \neq 0\).

0.0.8 Invoking the ARS-EO Dichotomy Theorem↩︎

The premise of this section is:

\(F = Q + \lambda e_{0^{2d}} + \lambda e_{1^{2d}} = Q + \lambda |0^{2d}\rangle + \lambda |1^{2d}\rangle\), where \(Q\) is a \(0\)-\(1\) symmetric rational \(\mathrm{EO}\) function, and we also have \(a \neq 0\).

Although \(F\) is not an \(\mathrm{EO}\) function, it is essentially a function reduced to the verge of no longer preserving the non-\(\mathrm{EO}\) property. Clearly, we have \((x_i \neq x_j) F=(x_i \neq x_j) Q\). Any of its binary inequality reductions \((x_i \neq x_j) F\) is a \(0\)-\(1\) symmetric rational \(\mathrm{EO}\) function, and hence is also an \(\mathrm{ARS}\text{-}\mathrm{EO}\) function.

According to the \(\mathrm{ARS}\text{-}\mathrm{EO}\) dichotomy theorem (Theorem 1), we can divide the discussion into the following two major cases:

1. There exist \(i,j\) such that \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}(x_i \neq x_j) F\) is \(\#\mathrm{P}\)-hard, and thus the original problem is \(\#\mathrm{P}\)-hard.

2. For any \(i,j\), \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}(x_i \neq x_j) F\) is polynomial-time computable, i.e., it is in \(\mathcal{P}\) or \(\mathcal{A}\).

   1. For any \(i,j\), \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}(x_i \neq x_j) F\) is the zero function. According to the inductive step of single-step arity reduction proved in Lemma 4, we can show that \(Q \equiv 0\). Consequently, \(F=\lambda |0^{2d}\rangle + \lambda |1^{2d}\rangle\). Since we can realize \(|0^k1^k\rangle + |1^k 0^k\rangle\) for any \(k\), invoking Lemma 7 below yields the complexity dichotomy.

   2. There exist \(i,j\) such that \((x_i \neq x_j) F\) is a non-zero function. For this specific pair \(i,j\), let \(H=(x_i \neq x_j) F \in \mathcal{P}\). According to Lemma 8 below, either the original problem has a complexity dichotomy, or \(H\) is of the form \(\neq_2^{\otimes}\).

   3. There exist \(i,j\) such that \((x_i \neq x_j) F\) is a non-zero function. For this specific pair \(i,j\), let \(H=(x_i \neq x_j) F \in \mathcal{A}\). According to Lemma 9 below, either the original problem has a complexity dichotomy, or \(H\) is of the form \(\neq_2^{\otimes}\).

In fact, due to the sharing of the non-vanishing property, as long as there exist \(i,j\) such that \((x_i \neq x_j) F\) is a non-zero function, then for any \(i,j\), \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}(x_i \neq x_j) F\) is a non-zero function.

Returning to the case analysis at the beginning of this section, we obtain that for any \(i,j\), the function \((x_i \neq x_j) F\) is of the form \(\epsilon \neq_2^{\otimes}\), where \(\epsilon\) is a constant that can be zero.

0.0.9 Conjecture on Arity Reduction for Rational 0-1 Symmetric EO Functions↩︎

The proof of Conjecture [3] implies the following result.

We are still dealing with \(F = Q + a e_{0^{2d}} + b e_{1^{2d}} = Q + a |0^{2d}\rangle + b |1^{2d}\rangle\), where \(Q\) is a \(0\)-\(1\) symmetric rational \(\mathrm{EO}\) function, and \(a \neq 0\) or \(b \neq 0\). \(F\) has arity at least six, because the \(C_1\) upper-set condition restricts the forms of binary and quaternary functions, preventing them from being non-zero on the all-0 or all-1 strings.

• If \(Q\) is of the form \(\epsilon \neq_2^{\otimes}\), we may assume without loss of generality that \(Q\) has the factor \([x_1 \neq x_2]\).

  We adopt the classical "one-produces-many" strategy. In an instance, we can use the quaternary function \([x_1 \neq x_2][x_3 \neq x_4]+[x_1 \neq x_3][x_2 \neq x_4]-[x_1 \neq x_4][x_2 \neq x_3]\), which is \(|0011 \rangle + |1100\rangle\), or \([x_1=x_2 \neq x_3=x_4]\). This is the "one".

  We take two copies of \(F\), say \(F\) and \(F'\), and apply the aforementioned quaternary function (via binary inequality edges) to their first two variables. That is, we consider \((x_1=x_2 \neq x'_1=x'_2) F(x_1,\dots,x_{2d}) F'(x'_1,\dots,x'_{2d}) = |0^{2d-2}1^{2d-2}\rangle + |1^{2d-2}0^{2d-2}\rangle\). Since \(F\) has arity at least six, it consumes two variables and produces at least four variables. Continuing this process recursively, it can realize \(|0^k1^k\rangle + |1^k 0^k\rangle\) for any integer \(k\). According to Lemma 7, this yields a complexity dichotomy.

• If \(Q\) is of the form \(F'_8= I^{\otimes 4}+X^{\otimes 4}+Y^{\otimes 4}+Z^{\otimes 4}-|0^{8}\rangle - |1^{1}\rangle\).

  \(F'_8\) possesses the "one-produces-three" property: when connected to one \(Y=\begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}\), it yields \(Y^{\otimes 3}\). Each step consumes one and produces three, resulting in a net gain of two \(Y\)s, which can be repeated arbitrarily many times. For \(F = Q + a |0^{8}\rangle + a |1^{8}\rangle\), connecting it with self-loops of \(Y\) has exactly the same effect as on \(Q\).

  We next prove that the original problem \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\) is equivalent to \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}\{H, Y\}\). Suppose \(G\) is any instance of the latter that uses an odd number of \(Y\)s. Utilizing the "one-produces-three" property of \(F\), we can transform it into a value-preserving instance \(G'\) that uses only one \(Y\). Removing this single \(Y\) from \(G'\) yields a binary gadget of \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\), whose function is only \(\epsilon I\). Reconnecting \(Y\) back shows that the value of \(G'\) must be zero, meaning we can compute the value of \(G\).¹ Suppose \(G\) is any instance of the latter that uses an even number of \(Y\)s. Utilizing the "one-produces-three" property of \(F\), we can transform it into a value-preserving instance \(G'\) that uses only two \(Y\)s. This quaternary function of two \(Y\)s can be realized by \([x_1 \neq x_3][x_2 \neq x_4]-[x_1 \neq x_4][x_2 \neq x_3]\).

0.0.10 A Trying Proof of the Conjecture, together with Unfinished Computational Verifiability↩︎

For any fixed arity \(2d\), whether the conjecture is correct can be verified or disproved by brute-force enumeration. For any \(i, j\), we can assume and enumerate the form of \((x_i \neq x_j) Q\), using relative coefficients. According to the two preceding lemmas, these coefficients only have two choices: 1 and 2. Once an enumeration scheme is fixed, for any way of adding \(d\) self-loops to \(Q\), we can obtain its value starting from the related forms of \((x_i \neq x_j) Q\). If no contradiction arises, this scheme is valid and satisfies the conditions of the conjecture. Since the system of equations obtained from all ways of adding self-loops is of full rank, we can solve for \(Q\) and check whether it satisfies the conclusion of the conjecture. After enumerating all schemes, we can determine whether the conjecture holds for arity \(2d\).

In the subsequent proof, we assume without loss of generality that a sufficiently large integer \(N\) is chosen, and the functions under consideration have arity at least \(N\). In fact, choosing \(N = 10\) seems to suffice for the proofs that follow.

Finally, only one step remains to extract the factor \([x_9 \neq x_{10}]\) from \(Q\), which is to prove that for any string with \(x_9 = 0, x_{10} = 1\), the value remains unchanged when these two bits are flipped. Since \((x_9 \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix} x_{10}) \equiv 0\), this is indeed correct.

0.0.11 Retrospective and Acknowledgments↩︎

In the second version, the AI contributed only to the Chinese-to-English translation. This paper is based on the Chinese version. The English translation was automatically generated by AI.

任意取定一个由布尔变量的复数值域的函数构成的集合F，就得到一个计数问题#F。只取F中的函数形式构成张量网络，作为问题的输入，计数问题#F问张量网络的值。如果证明了一个计数问题类中，每个问题的计算复杂性，要么是#P难解的，要么是易解的，即在（\(\text{FP}^{\text{NP}}\)）FP中，就称为（准）二分定理。已有很多特定子类的二分定理，例如任意实数值域的函数构成的集合定义的#F 问题组成的子类。这些二分或准二分定理，按照其刻画的问题子类的包含关系，形成偏序。随着已知二分定理的增加，其偏序集极大元数量，先增多，然后当有新的二分定理统一之前若干个极大二分定理时，就收缩，目前大约五、六个。仍然可以有很多未发掘为研究的子类定义模式，可以去研究新特定情形的有趣的数学结构，证明更多的极大二分定理，然而，历史可能到了直接研究此偏序列中最大元，即整个类的时刻。

本文提出了一个研究整个类的规划。可以证明，未被解决的#F问题，它能实现的二元函数构成群，并对应 二阶酉矩阵有限群，亦即对应三维行列式为1的实正交群SO(3)的有限子群。这种有限群分为五大类：循环群、二面体群、四面体群、八面体群、二十面体群。循环群继续分为一阶、二阶、高阶；二面体群分为奇二面体群、克莱因四元群、大偶二面体群。这样，用九个子类，不相交地覆盖整个类中所有未解决情形。其中一些研究与探讨见第一版。本第二版仅截取第一版的一阶循环群上，补充此情形的一些新证明，其中用到的基础知识需参考文献与第一版。

关键词：张量网络；计数问题；#P困难性；多项式时间；全息归约；二分定理；转动群；#ARS-EO。

0.0.12 背景介绍↩︎

降元大概是最常见的二分定理的证明的套路组成部分。 假设要证明问题类\(\{ \#' \mathcal{F} | \mathcal{F} \text{ is some set of some kind of functions}\}\) 的复杂性二分定理，且已知两个极大易解类是\(\mathcal{A}\)与\(\mathcal{B}\)。 除了\(\mathcal{A}\)与\(\mathcal{B}\)的两个算法，还要证明：任意集合\(\mathcal{F}\)，如果\(\mathcal{F} \not \subseteq \mathcal{A}\)且\(\mathcal{F} \not \subseteq \mathcal{B}\)，那么\(\#' \mathcal{F}\)是\(\#P\)难的。 降元是这个结论的归纳法证明套路中的归纳过程。因为\(\mathcal{F} \not \subseteq \mathcal{A}\)，存在\(S \in \mathcal{F}\)，\(S \not \in \mathcal{A}\)，\(S\)是d元函数，d可以是任意自然数，要对\(S\)的元数d做归纳，在问题\(\#' \mathcal{F}\)中构造元数更小的函数，保持不在\(\mathcal{A}\)中（简称为非\(\mathcal{A}\)）这样一个性质，直至降元到一个4元函数\(S'\)，或者其他某个固定的小元数。 对非\(\mathcal{B}\)的函数\(T\)，做同样的事情，得到\(T'\)。 这就是归纳过程。

至于\(\#'\{ S', T'\}\)的难解性，就属于需要另外证明的归纳法的起始结论了。 时至今日，由于一些的已知二分定理打下的根基，这个起始结论也常常这样处理， 证明要么\(\#'\{ S'\}\)难解，要么\(\#'\{ S'\}\)能实现任意元的相等函数（或其他辅助函数），从而可以调用\(\#CSP\)问题类（或其他相应类）的二分定理。

问题类\({\# \mathcal{F}}\)，有一个显然的易解类\(<T>\)（由所有能张量积分解为二元函数的函数构成）。 实数值域子类的二分定理[1]的研究中，遇到并解决了一个非常重要的现象，非\(<T>\)性质，不一定能成功降元， 有两个特例函数\(f_6\)与\(f_8\)，任何降元手段都不保持非\(<T>\)性质。

降元过程可失败现象，逐渐引发了新的研究范式。 按照降元成功与失败形成的条件，分成两种情形，分别叫做下集条件、上集条件，分别讨论。回忆我们现在正在证明二分定理的难解侧，即证明任意无易解算法的问题 都难解，这种问题中必然有非\(<T>\)的函数F。 一种情形对应F能降元成功的情况，存在一个非\(<T>\)的四元函数。 另一种情形，对应F没能成功降元，所有非\(<T>\)的函数，都没能降元到四元，任意四元函数都在\(<T>\)中，都是两个二元函数的张量积。 前者也对应归纳法的起始根基结论，归为下集，其条件为存在不可分解的真四元函数，简称真四元。 后者对应，手头的非\(<T>\)的函数可以是任意元的，本应该是归纳步骤应该应对解决的无限多的情况，归为上集，其条件为，任意四元函数都是两个二元函数的张量积，简称假四元。

既然降元归纳过程失效，何不直接使用假四元条件（暂时忘却手头有个非\(<T>\)函数）试试？这便是实数化方法的前提条件。 实数化方法，打断一个无外部边即封闭的张量网络的两条边\((x,y)\)与\((z,w)\)，变成一个四元构件，由于其必为可分解的假四元，换一种方式连成\((x,z)\)与\((y,w)\)，得到的新的封闭张量网络与前一个封闭张量网络的值有联系。 这个联系，非常巧妙地落在相差一个实数倍数。 原因在于归一化的二元函数构成二阶复数矩阵群，这种群的元素的迹都是实数。 既然每次都是变实数倍，最初的复数就是个永远不变的常数，整个问题与一个实数值域的问题无异，因而称为实数化（realnumberizing）方法。

若能实数化，就极其缩小了研究对象的范围，并且可以调用 实数值域子类的二分定理[1]。相当于曲线救国，不去研究复数值域时，会不会出现更多的类似\(f_6\)与\(f_8\)那样抗拒降元的函数，直接克服困难；而是绕道说明了，所有的困难，都在实数值域情形解决好了，克服掉了。

群现象与实数化，是整个这套的规划启航时的最重要的两个引擎。 前者提供实数迹，后者提供转化方法，这两盏聚光灯照亮了实数值域子类的二分定理的重要基础地位，这点其实出乎作者的意料。

然后以上美好计划没那么简单与一帆风顺，本第二版研究C1上就是一个不容易上九类，没能完整实数化。

作者最早接触实数化方法的重组边过程的方法，是在2023年8月25日，国科大师生访问中科大师生的讨论中，两个队伍为了保持在#EO计数问题上研究的独立性，是在判定问题上讨论了这个重组过程，判定问题一直取值0、1也没有函数值实数化一说；后来重组步骤，用于了#EO计数问题[2]，带来了实数化结论。

C1群条件的自律性特点，能带来一个条件，定义域01对称，即\(F(X)=F(\bar{X})\)。C1群的极低的辅助性能力特点，只有一个二元函数\(=_2\)， 实数化方法中，要取\(=_2^{\otimes d}\)这个函数的\(2^{2d}\)维函数值向量，作为方程的系数向量，得到关于\(\{F(X)| X \in \{0,1\}^{2d} \text{且含有偶数个1} \}\)的线性方程，不同的变量次序得到不同的方程，我们期望这个方程组满秩，然而C1的极低的辅助性能力，导致即便联合了01对称带来的方程，也仍然不满秩。

使用K基做变化，把所有张量网络，从默认”边是二元相等”，转化为，默认”边是二元不等”，即从\(\# =_2|\mathcal{F}\)转化为\(\# \neq_2| \hat{\mathcal{F}}\)问题。理论上，不改变上述难点的本质，却带来利于分析的形式。此时， C1群条件，变为只有一个二元函数\(\neq_2\)， 实数化方法中，取\(\neq_2^{\otimes d}\)这个函数的\(2^{2d}\)维函数值向量，作为方程的系数向量，得到关于\(\{F(X)| X \in \text{EO}^{2d} \}\)的线性方程，不同的变量次序得到不同的方程，联合了01对称带来的方程，满秩。

在上两段的介绍中，函数集合被\(\mathcal{F}\)被偷换成了单个函数\(F\)。在第二节，讲解C1条件下，使用实数化证明这个转化，不改变复杂性。

第三节中，我们分析这个满秩，并对\(\{F(X)| X \in \text{EO}^{2d} \}\)，即\(F|_ {\text{EO}}\)部分实现了实数化。

虽然K基变换很有用，帮我们重新组合了变量，使信息清晰地分流，把能搞定的部分抓到了EO上，不能搞定的无法直接观测的黑洞部分，留在了\(F-F|_{\text{EO}}\)，但它本质与变换前应是一样的，没有多给出有关黑洞的信息，只是把黑洞的分散的暗物质模式，变成了集中的黑洞模式。（这里滥用物理名词比方，别当真。）

第四节中，我们通过观测\(F^{\otimes k}\)的EO部分，来拿到\(F\)的非EO部分的信息，接着通过一个对角矩阵基变换，把这些非EO的部分，变成实数或者纯虚数，且满足定义域01对称。很不幸，我们距离调用#ARS-EO的二分定理，仅仅一步之遥，当\(\alpha \not \in \text{EO}\)且\(F(\alpha)\)是非零纯虚数时，这个函数满足\(F(\alpha)=F(\bar{\alpha})\)，但ARS条件要求它们共轭，即\(F(\alpha)=-F(\bar{\alpha})\)。非常希望能类似其它上九类的一些情形，调用Real-Holant的二分定理，在这里黑盒调用#ARS-EO的二分定理，但未能如愿，因此在本文的第一版中，把需要调用的问题，猜想了其二分定理成立。

第五节，记载了这个上课学期中的思考，经过一些分析，做了一个更具体猜想。猜测这个猜想大概率是对的，但需要把#ARS-EO的二分定理的证明细节展开，主要是其中的降元相关的几个引理。

二分定理的证明，不像本节开头讲的归纳法降元那么简单易行，不只是对极大易解类，往往在其中嵌套着对其它一些相关函数结构做归纳降元。例如，在[4]的二分定理中，需要对支撑集不是仿射子空间这一特性做降元，而这个降元被封装成了，如果支撑集不是仿子，定义的#CSP问题是#P难的。这种封装使得引理使用最常见的定义，陈述简单，也隐藏了相关非此结构属性的降元结论，具体而真实的长结论，通常是：要么成功降元，要么不成功降元的形式能证明#P难。几乎所有二分定理，都采用了这样的展现模式，把精美的分情况讨论放在证明细节里，结论陈述中至留下封装完毕的简练模式，即便这样，都会吓跑读者，#ARS-EO的二分定理也不例外。面对这个封装，我的策略是把专业的事情留给专业的人，留下这个猜想空白。

0.0.12.1 记号

使用符号\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}\mathcal{F}\)，简记\(\# \neq_2|\mathcal{F}\)问题。 \(\# \mathcal{F}\)即\(\# =_2|\mathcal{F}\)，形象上”\(\#\)“像”\(=\)“的双重否定，还是”\(=\)“； 形象上”\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}\)“像”\(=\)“的三重否定，故选取”\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}\)“，来标记\(\# \neq_2|\mathcal{F}\)问题。”\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}\)“读做sa，音同汉字”卅”。

#EO问题本指图的欧拉定向（Eulerian Orientation）数目问题，它是特殊的\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}\mathcal{F}\)问题，要求\(\mathcal{F}\)的函数，只在0、1个数相同的哪些串上可以取非零值。（这隐含了必须是偶数元函数。边函数\(\neq_2\)本身也是这样的。）EO这个词被延展使用了，有时称这种函数为EO函数，有时称这种串构成的集合为EO（为方便记忆”equal （or even） opportunity”），长度2d的这种串集合记为\(EO^{2d}\)，那么EO函数就是支撑集包含在EO里的函数。EO作为定义域的子集，可定义限制到它的函数，\(F|_\text{EO}\)表示把F在\(\text{EO}\)之外的函数值修改为0得到的函数。

一阶群条件，也叫C1条件，指，\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}\mathcal{F}\)中所有能实现的二元函数都有形式\(\epsilon \neq_2\)。（\(\epsilon\)表示是来自值域的常数，可以是零。）

上集（条件）指，所有的四元函数都能分解成两个二元的乘积，结合分解引理与一阶群条件，所有能实现的二元函数都有形式\(\epsilon \neq_2 \otimes \neq_2\)。

这一版里，全文的研究对象都有一阶群上集条件。

0.0.13 零性共享↩︎

0.0.13.1 张量网络单步重组

取定n，考虑所有n个点的\(\neq_2|\mathcal{F}\)-张量网络。

任取其中一个网络G，设其中两条边\(\neq_2(x,y)\)与\(\neq_2(z,w)\)。 另一个网络G’，与G完全相同，除了没有这两条边，取而代之的是另外两条边：\(\neq_2(x,z)\)与\(\neq_2(y,w)\)。

定义实数化过程的从G到G’一步。

把G的\(\neq_2(x,y)\)与\(\neq_2(z,w)\)两条边断开，得到一个四元构件H(x,y,z,w)。 H必有形式\(\lambda \neq_2 \otimes \neq_2\)。 H接两条边的值很容易计算，可得G的值为\(2 \lambda\)或者\(4 \lambda\)。 同理，G’的值必为\(2 \lambda\)或者\(4 \lambda\)。 因此，G与G’的值，或者同时为0，或者同时不为0且比例为1或者2。

0.0.13.1.1 零性共享

单步重组，是连通G与G’的”边”，考虑所有n个点的张量网络，这种边，可以连通所有这些张量网络。 因此，这些网络的值，要么全为0，要么全非零。 这个结论对所有的n，包括n=1时，都成立。由此，我们得到如下引理。

0.0.14 单个函数顶替函数集合↩︎

0.0.15 定义域01对称、满秩↩︎

如果任意\(\alpha\)，\(F(\alpha)=F(\overline{\alpha})\)，就说\(F\)是01对称的。

对任意2d元布尔函数，EO指它定义域的一个子集，由所有d个1、d个0的01串构成。 \(F | _{EO}\)，是从F出发，把EO之外的串上值都定义为0。

参考第一节对实数化过程满秩的介绍，从后面一节的实数化的证明过程中，可以看出上述引理，就是为了说明线性方程组对\(F | _{EO}\)这些变量满秩。

早在六点模型的研究中，就有如下显然的计算过程。这个过程计算4元时候的满秩。 \(\neq_2 \otimes \neq_2\)有三种配对模式，分别得到函数\([x_1 \neq x_2][ x_3 \neq x_4]\)，\([x_1 \neq x_3][ x_2 \neq x_4]\)，\([x_1 \neq x_4][ x_2 \neq x_3]\)，其函数值表分别是\(e_\alpha+e_{\bar{\alpha}}+e_\beta+e_{\bar{\beta}}\)，\(e_\beta+e_{\bar{\beta}}+e_\gamma+e_{\bar{\gamma}}\)，\(e_\alpha+e_ {\bar{\alpha}}+e_\gamma+e_{\bar{\gamma}}\)，其中\(\alpha=0101, \beta=0110, \gamma=0011\)，\(e_\alpha\)表示一个16维的标准基向量，仅在\(\alpha\)处分量值为1。 F以\([x_1 \neq x_2][ x_3 \neq x_4]\)方式接自环，得到\(F(\alpha)+F(\bar{\alpha})+ F(\beta)+ F(\bar{\beta})\)的值，其余两个方程类似， 再结合01对称性的方程，任意\(\theta\)，\(F(\theta)=F(\bar{\theta})\)，不难看出这六个方程恰好能满秩地解出\(F|_\text{EO}\)。

在[2]的研究过程中，以满秩方式使用实数化方法，以为4d元或者\(4^d\)情形的满秩证明，基本就是上述4元情形的系数矩阵的d次张量积，因此满秩，后来唐竹笑阅读初稿发现这样是错的，我的合作者用引理4的方式修复了此错误。

在本文的研究中，我又按照错误的方法，写了第一版的初稿，后在雁栖湖与我的研究生助教上完本科生课后讲解C1情形，逻辑通不过发现了错误，重读[2]之后，才修正了过来。近期课程基本结束，重拾C1情形的研究，在尝试有些想法时，貌似发现了之前的错误的修正方法，记录如下。但这个修正似乎本质与引理4一样，证明方式反而不如引理4简练。

考虑如下\(\text{EO}^{2d}\)线性空间的子集与其张成的子空间。

定义\(A=\{ F | F = F|_\text{EO}\text{，且 F 定义域01对称，} \text{且 F任意加d-1二元不等自环后，} \\ \text{得到的二元函数都是} \epsilon \neq_2 \}\)， \(B=\{e_\alpha+e_{\bar{\alpha}} | \alpha \in \text{EO}\}\)。

显然\(B \subseteq A\)，还有B可以线性表出A中任意函数元素，因此有他们张成的子空间相等，即\(<A>=<B>\)。

定义\(C=\{ [x_{\pi(1)} \neq x_{\pi(2)}] \cdots [ x_{\pi(2d-1)} \neq x_{\pi(2d)}] | \pi \in S_{2d}\}\)。 显然\(C \subseteq A\)，再只需证明\(B \subseteq <C>\)，就能证明三者生成的子空间相同。

对d使用归纳法证明\(B \subseteq <C>\)。 \(d=1,2\)时，已经成立了。

现在想证明\(B_{2d+4}\subseteq <C_{2d+4}>\)。任意选取\(B_{2d+4}\)中的一个串，由于串里一半0一半1，对变量重排次序之后， 不妨假设这个串是\(0101 \xi\)，其中\(\xi \in \text{EO}^{2d}\)。把归纳假设，应用到后\(2d+2\)个位上，\(e_{01\xi}+ e_{10\bar{\xi}} \in B_{2d+2}\subseteq <C_{2d+2}>\)，因此\(e_{01\xi}+ e_{10\bar{\xi}}\)能被\(C_{2d+2}\)线性表出。 对前两位，使用\([x_1 \neq x_2]\)，我们得到\(<C_{2d+4}>\)能够线性表出\(e_{(01+10) \circ (01\xi+10\bar{\xi})}=e_{0101\xi}+e_{1010\bar{\xi}}+e_{1001\xi}+e_{0110\bar{\xi}}\) （这里，我们未定义而直接借用了一下正则表达式）。

类似地，把归纳假设，应用到后\(2d\)位以及第2、3位上，\(e_{\sqcup 10 \sqcup \xi}+ e_{\sqcup01\sqcup\bar{\xi}} \in B_{2d+2}\subseteq <C_{2d+2}>\)，使用\([x_1 \neq x_4]\)，得到\(<C_{2d+4}>\)能够线性表出\(e_{(0\sqcup\sqcup1+1\sqcup\sqcup0) \circ (\sqcup 10 \sqcup \xi+\sqcup01\sqcup\bar{\xi})}=e_{0101\xi}+e_{1010\bar{\xi}}+e_{1100\xi}+e_{0011\bar{\xi}}\)。

类似地，把归纳假设，应用到后\(2d\)位以及第1、3位上，\(e_{1 \sqcup 0 \sqcup \xi}+ e_{0 \sqcup 1\sqcup \bar{\xi}} \in B_{2d+2}\subseteq <C_{2d+2}>\)，使用\([x_2 \neq x_4]\)，得到\(<C_{2d+4}>\)能够线性表出\(e_{(\sqcup 1 \sqcup 0+\sqcup 0 \sqcup 1) \circ (1 \sqcup 0 \sqcup \xi+0 \sqcup 1\sqcup \bar{\xi} )}=e_{1100\xi}+e_{0011\bar{\xi}}+e_{1001\xi}+e_{0110\bar{\xi}}\)。

前两个相加，减掉第三个，就得到\(2(e_{0101\xi}+ e_{1010\bar{\xi}}) \in <C_{2d+4}>\)。

0.0.16 EO部分的实数化↩︎

这部分证明仍然与[2]一样。

由于这个证明内嵌了引理4导出满秩的小步骤而略显杂乱。 简略说来，以每个\(\neq_2 ^{\otimes d}\)与H结合，得到一个有关\(H|_\text{EO}\)的线性方程。定义域01对称给出的方程，联合这些方程，满秩（见上节末引理4后的证明）。 单步重组保证了，相邻的方程，连通从而任意两个方程，其常数项相差实数倍。 因此，存在复数\(\theta\)，\(\frac{1}{\theta} H|_\text{EO}\)是一个满秩的实数线性方程组的解。

0.0.17 透过大函数的EO部分观测小函数的非EO部分↩︎

长2d的串\(\alpha\)，定义其偏离度\(r(\alpha)\)为1的个数减去0的个数。\(EO ^\geq\)表示所有偏离度非负的串， \(EO ^\leq\)表示所有偏离度非正的串。

0.0.18 对非EO的部分降元整形↩︎

根据引理5，只需研究这种H定义的\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\)的复杂性，H至少是六元函数，H具备非零性，且 存在定义域01对称的有理函数\(Q\)（ supp(Q)\(\subseteq EO\)），复数\(\theta\)，满足\(H|_{EO}= \theta Q\)。 把\(H/\theta\)重定义为\(H\)，条件变为H在EO内是有理值且01对称。

设\(Q=H|_\text{EO}\)，\(Q'=H-Q\)。分情况讨论\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\)的复杂性研究处理。

• 如果Q恒等于0，直接调用定理1得到\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\)的复杂性刻画。

• 存在\(\alpha={0^a1^b}\)，\(a\neq b\)，使得\(Q(\alpha)\neq 0\)。 取这种串中\(|a-b|\)最小的，设为\(\alpha={0^a1^b}\)，\(a+b \geq 6\)。 我们要保持这样的性质降元，直至\(a=0\)或者\(b=0\)，或者降到了四元，与上集条件矛盾。 不妨假设\(b>a>0\)，即有三个自变量位\(x,y,z\)，\(\alpha|_{xyz}=011\)，把这三位重排到前三位， 设\(\alpha=011\beta\)。 考察\(((x \neq y) H) (1 \beta)=H(011\beta)+H(101 \beta)\)，\(((x \neq z) H) (1 \beta)=H(011\beta)+H(110 \beta)\)，\(((z \neq y) H) (1 \beta)=H(101\beta)+H(110 \beta)\)。 因为\(H(011\beta) \neq 0\)，这三个函数，至少有一个成功降了两元，在\(1\beta\)上值非零， \(1\beta\)的0与1的数目差还是\(|a-b|\)。

  一路降元下去，会得到一个函数，它在纯1串或者纯0串上非零。 如果支撑集里还有其他EO之外，0、1数量差更小的串，就对那个串继续降元。 最终会得到一个新函数H’，\(H' - H'|_\text{EO}\)不是零函数，且之多只在纯0与纯1串上非零。

以上就是对H整形到了H’，在此过程中，显然\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H' \leq_P \mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\)。

在之后的分析中，我们可以证明要么\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H'\)是#P难的，要么H’能实现一些函数，从而\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\)，在这些函数的帮助下，有已知的二分定理。由于刚才的归约只保证单向成立，给出\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H'\)的多项式时间算法，对原始问题\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\)的复杂性无效果。

我们把H’重新记为F，重述一下条件：

\(F = Q + a e_{0^{2d}} + b e_{1^{2d}} = Q + a |0^{2d}\rangle + a |1^{2d}\rangle\)，其中Q是01对称的有理EO函数，且还有\(a \neq 0\)或者\(b \neq 0\)。

0.0.19 调用ARS-EO的二分定理↩︎

本节的前提条件是： \(F = Q + \lambda e_{0^{2d}} + \lambda e_{1^{2d}} = Q + \lambda |0^{2d}\rangle + \lambda |1^{2d}\rangle\)，其中Q是01对称的有理EO函数，且还有\(a \neq 0\)。 虽然F不是EO函数，但它本质是降元降到了即将不能保持非EO属性的前夕的函数，显然有\((x_i \neq x_j) F=(x_i \neq x_j) Q\)，它的任意二元不等降元\((x_i \neq x_j) F\)都是01对称的有理EO函数，因而也是ARS-EO函数。

根据ARS-EO的二分定理1，可分为以下两种大情况讨论：

1. 存在\(i,j\)，\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}(x_i \neq x_j) F\)是#P难的，从而原问题#P难。

2. 任意\(i,j\)，\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}(x_i \neq x_j) F\)是多项式时间可计算的，即它在\(\mathcal{P}\)或者\(\mathcal{A}\)里。

   1. 任意\(i,j\)，\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}(x_i \neq x_j) F\)是零函数。根据引理4证明的一步降元归纳步骤，即可证明\(Q \equiv 0\)。从而\(F=\lambda |0^{2d}\rangle + \lambda |1^{2d}\rangle\)。可对任意k实现\(|0^k1^k\rangle + |1^k 0^k\rangle\)，使用下面的引理7，即可复杂性二分。

   2. 存在\(i,j\)，\((x_i \neq x_j) F\)是个非零函数。当前的这个\(i,j\)，\(H=(x_i \neq x_j) F \in \mathcal{P}\)，根据后面的引理8，要么原始问题有复杂性二分，要么\(H\)有\(\neq_2^{\otimes}\)形式。

   3. 存在\(i,j\)，\((x_i \neq x_j) F\)是个非零函数。当前的这个\(i,j\)，\(H=(x_i \neq x_j) F \in \mathcal{A}\)，根据后面的引理9，要么原始问题有复杂性二分，要么\(H\)有\(\neq_2^{\otimes}\)形式。

实际上，由于非零性共享，只要存在\(i,j\)，\((x_i \neq x_j) F\)是个非零函数，那么任意\(i,j\)，\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}(x_i \neq x_j) F\)是非零函数。

回到本节开头的分类讨论，我们得到了， 任意\(i,j\)得到的\((x_i \neq x_j) F\)有形式\(\epsilon \neq_2^{\otimes}\)，其中\(\epsilon\)是可为零的常数。

0.0.20 对有理01对称EO函数降元的猜想↩︎

猜想[3]的证明中，蕴含了如下结论。

我们手中仍然是，\(F = Q + a e_{0^{2d}} + b e_{1^{2d}} = Q + a |0^{2d}\rangle + b |1^{2d}\rangle\)，其中Q是01对称的有理EO函数，且还有\(a \neq 0\)或者\(b \neq 0\)。\(F\)至少是六元函数，因为C1上集条件，限制住了二元与四元函数的形式，不可能在全0或者全1串上非零。

• Q具有形式\(\epsilon \neq_2^{\otimes}\)，不妨设Q有因子\([x_1 \neq x_2]\)。

  采用经典的一生多策略。我们可以在实例中，使用一次四元函数\([x_1 \neq x_2][x_3 \neq x_4]+[x_1 \neq x_3][x_2 \neq x_4]-[x_1 \neq x_4][x_2 \neq x_3]\)，即\(|0011 \rangle + |1100\rangle\)，即\([x_1=x_2 \neq x_3=x_4]\)。此为一。

  取两个F函数，F与F’，把刚才的四元函数（经过二元不等边）用到它们的前两个变量上，即考虑\((x_1=x_2 \neq x'_1=x'_2) F(x_1,\ldots,x_{2d}) F'(x'_1,\ldots,x'_{2d}) = |0^{2d-2}1^{2d-2}\rangle + |1^{2d-2}0^{2d-2}\rangle\)。 由于F至少是六元函数，它消耗两元，生出至少四元。 这样继续生生不息下去，对任意整数k，它可以实现\(|0^k1^k\rangle + |1^k 0^k\rangle\)。 根据引理7，从而有复杂性二分。

• Q具有形式\(F'_8= I ^ {\otimes 4}+X^ {\otimes 4}+Y^{\otimes 4}+Z^{\otimes 4}-|0^{8}\rangle - |1^{1}\rangle\)。

  \(F'_8\)具有一生三的特点，当它接上一个\(Y=\begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}\)，会得到\(Y^{\otimes 3}\)。每次消耗一个，得到三个，每次多出两个\(Y\)，可以使用任意多次。 \(F = Q + a |0^{8}\rangle + a |1^{8}\rangle\)，它接\(Y\)的自环，与Q的效果完全一样。

  记下来证明原问题\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\)与\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}\{H, Y\}\)等价。设后者的任意一个用了奇数个Y的一个实例G，利用F的一生三能力，可以保持值转化为一个只用一个Y的实例G’，从G’中删除这一个Y，是\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\)的一个二元构件，其函数只有\(\epsilon I\)，再把Y接回去，就可知G’的值必为零，因此可计算G的值。² 设后者的任意一个用了偶数个Y的一个实例G，利用F的一生三能力，可以保持值转化为一个只用两个Y的实例G’，这两个Y这个四元函数，可以用\([x_1 \neq x_3][x_2 \neq x_4]-[x_1 \neq x_4][x_2 \neq x_3]\)实现。

0.0.21 猜想可计算验证真伪↩︎

对于任意去顶的元数\(2d\)，猜想是否正确，可以暴力枚举计算证真或者证伪。 对任意\(i,j\)，不妨枚举设出来\((x_i \neq x_j) Q\)的形式，其系数使用相对的系数即可，根据前两个引理， 这些系数只有\(1、2\)两种选择。取定一种枚举方案， 任意一种\(Q\)加d个自环的方式，我们可以从相关的不同的\((x_i \neq x_j) Q\)的形式出发，得到其答案， 如果无矛盾，这个方案就是合理的满足猜想条件的方案， 所有加自环的方式得到的方程组是满秩的，可以解出Q来，看看是否满足猜想的结论。 枚举完所有方案，就知道猜想对\(2d\)元是否正确。

接下来的证明中，我们不妨假设取定了一个充分大的整数\(N\)，考虑的函数至少是N元的。 其实貌似取N=10，就能通过之后的证明。

最后，要对Q提取出来\([x_9 \neq x_{10}]\)这个因子，只差一步，证明任意的\(x_9=0,x_{10}=1\)的串，如果把它的这两位翻转之后，值不变。 因为\((x_9 \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix} x_{10}) \equiv 0\)，这是对的。

0.0.22 研究过程回顾与致谢↩︎

第二版中ai仅贡献了汉译英。 英文版只翻译这里，本句话结束之处：“本文以中文版为根基。英文版由ai自动翻译。”。

对一阶群上集的研究中，调用几个二分定理，其中包括有理数值域定义域01对称的#EO问题的二分定理， 作为[3]中#ARS-EO的二分定理的特殊情况调用的。 或者这个特殊情况，可以另有相对简单的证明，或者与#ARS-EO的二分定理的证明一样复杂。 总之，是动用了一个较后期的结论，经过加工，得到了较强的猜想的条件， 按理来说，这个猜想，如果蕴含[3]的证明中，现在的证明条件，因动用了可能后期的结论，比当时有利多了，应该容易证明一些。

但是，尝试证明这个猜想的过程一点也不简单，耗时十天，勉强得出上节的证明过程，甚至不确定这个过程正确，还包括着有限计算能搞定的部分，没去计算验证。由此可知，[3]的证明过程中，筛选出f6与f8是多么艰难，当年没听懂过，至今以40多岁的精力旺盛程度，也不敢下手去通读。 第二版只能先到这了，就剩一天，去做全新报告的幻灯片了，用于ITCS十周年workshop。

References↩︎

---

1. Some details are omitted here, and the reduction chain of the entire proof is very long. The decomposition lemma might have been used in the process of realizing \(F\) from \(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\). A more rigorous argumentation should strictly follow the reduction path, potentially using several copies of \(G'\) to compute the value of \(G\). How to carefully combine the decomposition lemma, as a special reduction step, with other reductions remains to be thoroughly checked.↩︎

2. 这里隐藏了一些细节，整个证明的归约链条太长了，从\(\mathrel{\tikz[baseline=0ex, line width=0.05em, x=1.2ex, y=1.2ex]{ \draw (0.15,-0.3) -- (0.5,1.3); \draw (0.5,-0.3) -- (0.85,1.3); \draw (0.85,-0.3) -- (1.2,1.3); \draw (-0.1,0.75) -- (1.35,0.75); \draw (-0.1,0.35) -- (1.35,0.35); }}H\)中实现F的过程中可能用了分解引理。较为严格论证方式应按照归约路线来，可能用了若干个G’，能计算G的值。分解引理这个特殊的归约步骤，如何与其他归约仔细结合，有待仔细检查。↩︎