A Full Complexity Dichotomy for Complex-Valued Boolean Holant Problems

Code Availability

• The verification code for Appendix A’s finite calculations is in the repository’s certificates/ directory.The repository is identified as Full-Holant-Dichotomy.Source: Code Availability · p. 1
• Run the complete certificate suite from the repository root with python3 certificates/run_all_exact.py.The README.md in certificates/ gives requirements and reproduction commands.Source: Code Availability · p. 1
• The theorem-to-script map identifies checked statements and distinguishes supplementary checks from calculations used in the proof.It is located in certificates/theorem-to-script-map.md.Source: Code Availability · p. 1

1 Introduction

• The result covers finite algebraic complex-valued Boolean signature sets on general graphs, including unrestricted all-even sets without a prescribed auxiliary binary signature.Holant evaluates a graph tensor-network partition function by summing products of local signatures over Boolean edge assignments.Source: §1 · p. 3

1.1 From counting CSP to the full Holant dichotomy

• Earlier counting classifications expanded across domain size, signature symmetry, and weight types; Table 1 records the graph-homomorphism and counting-CSP development.For Boolean Holant, prior classifications progressed through assumptions on symmetry and available unary signatures, as summarized in Table 2.Source: §1.1 · pp. 3–4, Table 1 · p. 3, Table 2 · p. 4
• The all-even analysis combines known binary-equality and quaternary dichotomies with a Hamming-imbalance height decomposition, completing the unrestricted complex classification together with the odd-arity dichotomy.The criterion is equivalent to the seven conditions from the odd-arity dichotomy and is applied without an odd-arity assumption; a single basis must work for the edge and every signature in each holographic alternative.Source: §1.1 · pp. 4–5, §1.2 · p. 5

1.2 Our result: the full dichotomy

• The theorem makes Tract(F) decidable for finite algebraic complex-valued Boolean signature sets and classifies tractable cases under polynomial-time Turing reductions.It allows mixed arities, zero and tensor-decomposable signatures, and singular binary factors; recognition uses the fixed exact algebraic encoding, while evaluation and oracle reductions are polynomial in instance size.Source: §1.2 · p. 5

1.3 Proof organization

• The proof transforms the remaining two-sided, multilayer all-even cases into a mountain signature, then divides the analysis by its height.Height one and two reduce through binary-equality or quaternary classifications; height three uses loop and two-copy contractions, while heights at least four use port normalization and phase recovery, with height four handled separately.Source: §1.3 · pp. 5–6

1.4 Related work

• Related work also studies planar tractability, restricted graph classes, stronger lower bounds under #ETH, and equality of Holant values under holographic transformations.The cited planar results include matchgate reductions for cases hard on general graphs but tractable on planar graphs; other work treats excluded-minor settings and bipartite orbit closures.Source: §1.4 · pp. 6–7
• For planar Holant, classifications include symmetric complex-valued signatures beyond FKT reductions and an eight-vertex classification distinguishing general-graph tractability, planar-only tractability, and hardness even on planar graphs.These are separate from the unrestricted general-graph dichotomy presented here.Source: §1.4 · p. 6

2.1 Algebraic notation

• Algebraic notation treats rings as commutative with identity, distinguishes the fields Q, R, and C, and uses F2 and F3 for the two- and three-element fields.Matrix transposes do not include complex conjugation.Source: §2.1 · p. 7

2.2 Complexity and exact-input conventions

• Complexity is exact: tractable means FP, hard means #P-hard under polynomial-time Turing reductions, and exact algebraic operations and postprocessing are allowed.Signature lists are fixed during evaluation; any shared basis, sign, or class in a tractable alternative must work for the entire set.Source: §2.2 · p. 7

2.4 Graphs, matchings, and Walsh coordinates

• Matching-code support alone does not imply matching-product factorization; even- and odd-parity Walsh support respectively imply complement symmetry and antisymmetry.The matching-product definition allows an arbitrary coefficient function on the independent binary choices of matching edges.Source: §2.4 · p. 9

2.5 Gadgets and allowed operations

• A slice, linear combination, or Walsh calculation is not by itself a gadget; pinning needs an available point-mass unary, while interpolation yields an oracle reduction.Direct constructions use fixed finite gadgets, and tensor-factor extraction or global basis changes require stated hypotheses.Source: §2.5 · p. 9

2.3 Tensor and group conventions

• Tensor factorization is defined up to port permutation and nonzero scalar redistribution, and tensor-prime signatures have unique prime factorization under those operations.Projective classes identify nonzero scalar multiples; rank one means a product of one vector on each specified factor.Source: §2.3 · p. 8, §2.6 · p. 10

2.6 Signatures, tensors, and Holant instances

• Holant sums products of vertex-signature values over edge assignments, and subdividing each edge by EQ2 identifies Holant(F) with Holant(EQ2 | F).The #CSPq variant restricts each variable degree to a multiple of q.Source: §2.6 · p. 11

2.7 Holographic transformations and the K-basis

• A global basis change preserves the partition function up to a known edge-count scalar, but group conjugacy alone does not make it a legal K-Holant normalization or a gadget.The finite projective subgroups considered are cyclic, dihedral, A4, S4, and A5.Source: §2.7 · pp. 12–13

2.9 Zero and nullary preprocessing

• Deleting zero and nullary signatures preserves the structural problem: zero-vertex instances evaluate to zero, and removed nullary factors can be restored exactly.After preprocessing, structural arguments assume nonzero positive-arity signatures.Source: §2.9 · p. 15

2.10 Charge and Hamming layers

• A set is common one-sided when all support lies in one charge direction; a mountain has arity 2d, nonzero endpoints at half-charges ±d, and possible central support at 0.No restriction is placed on the central EO layer, and X-contraction preserves external total charge.Source: §2.10 · pp. 15–16

2.11 Bell signatures and the Reed–Muller core

• Bell products pair ports according to a perfect matching, with reversing a pair carrying B1,1 changing the scalar sign; the RM(1, 3) code supplies the eight-port Reed–Muller core RM8, identified with f8.The supplied passage also notes that Bell contraction identities and the reduction adjoining equality are established in cited prior work.Source: §2.11 · p. 16

2.12 Exact finite verification

• Finite verification uses exact arithmetic and explicit rational-rank bounds; the six-port calculation also uses real polynomial satisfiability checks after splitting complex variables.The appendix records which conclusions depend on the solver.Source: §2.12 · p. 17

2.13.1 The standard signature classes

• The standard classes include affine signatures with quadratic Z4 phases and products of unary, equality, or disequality constraints; common transformability requires one basis for the entire set.The common-basis quantifier is over the set, not chosen separately for each signature.Source: §2.13.1 · pp. 17–18

2.13.2 The Eulerian-orientation predicate

• EOTract requires one shared sign and class for the set, a support condition on triplewise XORs, and membership in that class after every oriented perfect pairing.Single-layer signatures can be completed to even-arity central-support EO signatures by adding unaries; EOTract applies to finite EO signature sets.Source: §2.13.2 · p. 18

2.13.3 The tractability predicate

• The tractability predicate is a disjunction of seven alternatives; its first uses common one-sided support and EOTract, while the next begins with single-layer support.The second alternative also imposes a condition on support across the signature set, but the supplied passage does not include its full statement.Source: §2.13.3 · p. 19
• The tractability predicate includes A-, P-, and L-transformability conditions, and effective witnesses for these transformations can be found over Q and decided from exact algebraic input.The witness lemma states that if a complex invertible matrix witnesses the transformation, then a rational-matrix witness exists.Source: §2.13.3 · p. 19

2.13.4 Dichotomies and tensor decomposition

• Weighted Eulerian Holant is in FP exactly when EOTract holds, while one-layer signatures are #P-hard unless one of two EOTract exceptions applies; odd-arity Holant is in FP exactly when Tract holds.For the one-layer case, the exceptions are common one-sided signatures with EOTract(G|EO), or both charge signs with EOTract(G→EO); the exceptions are in FP.Source: §2.13.4 · pp. 19–20
• Tensor-factor extraction has a common-one-sided exception governed by EOTract, while quaternary eight-vertex Holant is #P-hard unless an A-, P-, or L-transformability condition holds.Every exception in the eight-vertex boundary is in FP, and its transform can be taken over Q using Lemma 2.10.Source: §2.13.4 · p. 20
• Even-degree CSP is #P-hard unless all signatures share one of four tractable classes, and degree-multiple CSP has one of two polynomial-time alternatives for some r in {1, ..., q}.Each stated exceptional case is computable in polynomial time.Source: §2.13.4 · p. 20

2.13.5 Decidability and polynomial-time evaluation

• For finite algebraic signature sets, Tract(F) is decidable after preprocessing, and when it holds, Holant(F) is in FP.Transformability witnesses for A, P, or L can be taken over Q and decided from exact algebraic input, with an algebraic witness produced.Source: §2.13.3 · p. 19, §2.13.5 · p. 20

2.14.1 Factor closure

• A finite signature set is factor-closed when it contains all tensor-prime factors of its signatures; if it is not common one-sided, factor closure follows under the equivalence convention.Repeated factorization terminates because each proper positive-arity factor has smaller arity than its parent.Source: §2.14.1 · p. 21

2.14.2 Downward inheritance and coordinate transport

• Tractability is inherited by subsets, invariant under GO(X), and preserved through the stated equivalent augmentations and coordinate transport.The transport result also preserves common presentations in A, P, and L.Source: §2.14.2 · pp. 21–22

2.15 Binary-equality and quaternary dichotomies

• With binary equality, K-Holant is in FP when Tract(KΛ) holds and #P-hard otherwise; the same dichotomy holds with an eight-vertex signature having nonzero endpoint values.Both applicable sides are decidable from exact algebraic input; the eight-vertex result covers tensor-prime signatures and, by its corollary, arbitrary such signatures.Source: §2.15 · pp. 22–23

3.1 Binary Interpolation

• A nonsingular binary with infinite projective order yields a nonzero rank-one binary in Γ.This is the stated nonsingular case of binary interpolation.Source: §3.1 · p. 23

3.2 Single-occurrence Reductions and Nonzero Unaries

• Single-occurrence replication uses a fixed gadget chain and a nonzero one-g witness to obtain arbitrarily many h occurrences while retaining exactly one g-vertex.The construction connects successive gadget copies along designated port blocks and divides by a known nonzero scalar to recover the desired value.Source: §3.2 · pp. 24–25
• A nonzero unary makes ordinary Holant or K-Holant #P-hard unless the corresponding tractability criterion holds; EQd for d ≥4 supplies both point-mass unaries.The higher-equality result therefore makes the nonzero-unary dichotomy applicable.Source: §3.2 · p. 25

3.3 Hardness from an Eulerian-orientation Signature

• Fixed direct X-gadget derivations over a subset Λ transfer to Γ, but a source’s problem-level Turing reduction alone does not establish such a derivation.When the derivation reaches a #P-hard subproblem, K-Holant(Γ) is #P-hard; tensor-factor extraction must be supplied separately.Source: §3.3 · pp. 25–26
• Under (REO1)–(REO2), an EO signature outside BARS makes K-Holant(Γ) #P-hard.The theorem assumes a nonzero positive-arity signature that cannot be expressed, up to a nonzero scalar, as a product of binary EO–ARS signatures over a perfect matching of its ports.Source: §3.3 · p. 26
• Under (REO1)–(REO2), a complementary weight-two quaternary with nonzero coefficients yields a nonzero unary in Γ.Lemma 3.4 then makes its nonzero-unary hardness criterion available.Source: §3.2 · p. 25, §3.3 · p. 26
• Under (REO1)–(REO2), an EO signature either has projective ARS or is hard; if it has projective ARS but lacks the specified BARS factorization, it is still #P-hard.The latter condition rules out a decomposition into binary EO–ARS factors on an oriented perfect matching, up to a nonzero scalar.Source: §3.3 · pp. 27–28
• The Eulerian-orientation argument yields #P-hardness: either K-Holant(Γ) is already hard, or h is projectively ARS but outside BARS, giving hardness by Lemma 3.10.The proof’s pinnings are coordinate slices for tensor-divisibility identities, not signatures produced by pinning gadgets; induction instead starts from h ∈ Γ or a factor adjoined by Theorem 2.14.Source: §3.3 · p. 29

3.4 Equalities and Generalized Equalities

• When one matrix transforms both the native edge to a nonzero multiple of EQ2 and a quaternary signature to a nonzero multiple of EQ4, K-Holant(G) is #P-hard or Tract(KG) holds.Transforming the quaternary signature alone does not ensure equality edges in the transformed problem.Source: §3.4 · p. 30
• For a generalized equality Gq = c0δ0q + c1δ1q with c0,c1 ∈ Q× and q ≥ 4, K-Holant(G) is #P-hard or Tract(KG) holds.Source: §3.4 · p. 30
• Under the two-point Walsh-factor conditions, K-Holant(Γ) is #P-hard or Tract(KΓ) holds; if c1/c0 is a root of unity, a finite equivalent enlargement yields a quaternary signature meeting Lemma 3.13’s conditions with U = K.The construction uses two copies of h; for finite-order ρ it chains binary gadgets to obtain the quaternary equality, while the infinite-order case uses a rank-one binary and a nonzero unary.Source: §3.4 · pp. 30–31

4 Obtaining a Mountain

• There is an arity-2d signature M with nonzero values at the all-zero and all-one inputs, and M(x) = 0 whenever wt(x) is not in {0, d, 2d}.Source: §4 · p. 31
• Alternatively, both point masses are accessible, and if ¬Tract(KG) holds, this outcome yields #P-hardness for K-Holant(G).The lemma’s two alternatives are adjoining the gcd-height mountain or obtaining both point masses.Source: §4 · p. 31
• Nonnegative multiplicities of supported half-charges can form tensor products with supported words of half-charges d and −d.The construction combines Bézout coefficients with positive multiplicities, then uses an endpoint-preserving self-loop lemma to obtain signatures P and N.Source: §4 · p. 32
• If P and N lack the required endpoints, joining their central parts or using two copies of one signature produces an arity-2d candidate with the needed endpoint values.The resulting support is restricted to half-charges −d, 0, and d.Source: §4 · p. 32
• For {EXACT4_1}, integer-half-charge conservation prevents a gadget from producing a mountain, so factor extraction instead gives both point masses.This example motivates retaining the factor alternative in the lemma.Source: §4 · p. 32

5 Mountain Height One

• For every finite algebraic signature set containing a height-one mountain, Tract(KΓ) holds or K-Holant(Γ) is #P-hard.Source: §5 · p. 33
• Under the nonsingular finite-projective-order hypothesis, the transfer group is finite and yields a nonsingular weighted equality or an odd cyclic or dihedral group.Source: §5 · pp. 33–34

5.1 Odd cyclic and dihedral transfer groups

• No infinite sequence of strict updates can persist: each update decreases the finite-group measure or the minimum arity of a tensor-prime signature of arity at least three.The construction uses the pulled-back transfer group and that minimum arity as its quantities of progress; if no such nonbinary tensor-prime signature remains, the arity-at-most-two case is tractable.Source: §5.1 · pp. 37–38
• For odd-dihedral transfer groups, the theorem gives #P-hardness or tractability, or a later stage with a strictly smaller transfer group or minimum tensor-prime arity.Source: §5.1 · p. 38
• The odd-dihedral theorem also permits equivalent saturation to a set for which the fixed Walsh matrix gives a common K-presentation, making KΓ P-transformable.Source: §5.1 · p. 38
• The recursive procedure either reaches a hardness or tractability case, makes a strict update, or exhaustively processes contractions; it terminates because each new nonbinary factor drops at least two in arity.The exhaustive-closure outcome need not strictly change either tracked quantity.Source: §5.1 · pp. 39–40

5.2 Contractions for the odd cyclic and dihedral groups

• Contractions are native K-gadgets: P is used only for analysis, and displayed pencil combinations are not asserted to be realizable.Source: §5.2 · p. 40

5.2.1 Contraction kernels and the four-coefficient relation

• For odd N, plus kernels occur in both groups and minus kernels only in the dihedral group; for every N ≥3, RN is equivalent to each phase contraction being zero or projectively Dη.Port reversal fixes Ds and sends Fs projectively to Fs−1.Source: §5.2.1 · pp. 40–41

5.2.2 Support parity

• If every specified contraction prime factor of an even-arity signature has one Walsh parity, the signature has one parity too, even in the cyclic case; Walsh duality yields the complement relation, with only the plus sign cyclically.Source: §5.2.2 · p. 41

5.3.1 Support and coefficients on even blocks

• The class PN consists of tensors supported on cosets determined by partitions into even blocks, with constrained block coefficient ratios, and is closed under the specified contractions.The closure also holds under scalar multiplication, port permutation, and tensor products; contractions may yield zero.Source: §5.3.1 · p. 42

5.3.2 Four-port support and coefficients

• For odd N ≥3, every nonzero quaternary satisfying the dihedral condition has one Walsh parity and exactly one or two nonzero complementary coefficient pairs, and these forms satisfy the stated contractions.The classification places the Walsh tensor in PN([4]).Source: §5.3.2 · p. 44

5.3.3 Products of binaries and the six-port case

• For odd N ≥3, if every nonzero oriented phase or reflection contraction of an arity-six signature has Walsh tensor in BN([4]), then the signature is zero or a product of three nonsingular binaries.Source: §5.3.3 · p. 45

5.3.4 Matching pencils

• Three nonproportional matching products in a linear relation either share support and lie in one Segre ruling or differ only on four ports; for arity at least eight, each contraction pencil has a phase-independent matching.The pencil factors as a fixed product of nonsingular binaries on disjoint pairs times a binary tensor on one fixed remaining pair.Source: §5.3.4 · p. 46

5.3.5 A common binary factor suffices

• Under the hypotheses of Proposition 5.16, every nonzero signature is tensor-decomposable.The proof obtains a common external binary factor across the two xor restrictions, which yields a factor of the original signature.Source: §5.3.5 · pp. 47–48
• For a minimum-arity nonbinary prime, every positive-arity prime factor of a two-port contraction is binary, so its transfer lies in D2N and nonzero two-port contractions lie in BN.Closure of BN extends this property to further contractions involving at least one port pair.Source: §5.3.5 · p. 48
• After excluding prime arities 4, 6, and at least 8, the proof yields hardness or tractability, or shows every tensor-prime is binary in one Walsh basis, giving the stated common K-presentation.In the binary case, P TXP = 2Z ∈ P.Source: §5.3.5 · p. 48

5.4 The odd-cyclic case

• Under the stated odd-cyclic assumptions, K-Holant(G) is #P-hard or Tract(KG) holds, or the analysis yields a later stage satisfying the update conditions or an equivalent set showing KG is P-transformable.The later-stage alternative has ν(G+) < ν(G) when both values are defined; the saturation alternative uses the fixed Walsh matrix P.Source: §5.4 · pp. 48–49

5.4.1 Phase-independent matching

• For each port pair, either every phase contraction vanishes or at most one does and all nonzero contractions share a fixed perfect-matching support, including when N = 3.The associated Walsh signature has even parity.Source: §5.4.1 · p. 49

5.4.2 Pairs with every phase contraction zero

• When every phase contraction for a pair vanishes, the zero-edge components are complete bipartite; for arity at least six, every port pair has a nonzero phase contraction.The arity-six-or-higher result rules out an all-phase-zero pair in that range.Source: §5.4.2 · p. 50

5.4.3 Weight-two coefficients and the arity bound

• The minimum-arity nonbinary tensor-prime signature in the cyclic case has arity exactly four.The theorem bounds its arity by four under the stated contraction and cyclic-transfer assumptions; it is even-arity and nonbinary, so the bound is attained. The proof uses rank-one diagonal restrictions to force factorization of the associated coefficient function when there are at least four paired variables, with a separate three-variable case.Source: §5.4.3 · pp. 51–52

5.4.4 The quaternary cyclic case

• The quaternary cyclic case uses a four-port attachment gadget for cyclic binary representatives and establishes a case split for quaternary signatures under the stated contraction assumptions.The theorem’s alternatives include a condition involving nonzero positive-arity signatures of arity below four.Source: §5.4.4 · p. 52, Consider the map · p. 53

Consider the map

• For odd N, the map from cyclic phase parameters to quaternary attachment targets is bijective.This bijection permits the proof to prescribe parameters for the four-port gadget.Source: Consider the map · p. 53
• An invertible-binary attachment of the mountain to q is endpoint-nondegenerate, so Corollary 2.25 gives tractability or #P-hardness that transfers to Γ as outcome 1.The attachment is adjoined using Equation (5); downward inheritance or the gadget reduction transfers the conclusion.Source: Consider the map · p. 54
• A phase contraction of Gi yields either a singular binary, a nonsingular binary outside CN, or a contradiction to the definition of G(Γ).A singular binary supplies unary factors; an infinite-order transfer is handled by Lemma 3.1, while finite order contradicts G(Γ). In factor cases, invertible attachments pull the factorization back to q and the transported mountain enables outcome 2.Source: Consider the map · p. 55
• For a minimum-arity nonbinary tensor-prime signature, condition (C) and the arity-four bound yield hardness, tractability, or a factorization, with the factorization excluded by tensor-primality.The remaining alternatives give outcome 1.Source: Consider the map · p. 55
• When every tensor-prime signature is binary, each has transfer class in G(Γ) and Walsh tensor proportional to DrZ, establishing Equation (16).This proves the third conclusion of Theorem 5.18.Source: Consider the map · p. 55
• Factor closure terminates by strict arity descent, and a strict group inclusion or decrease of ν gives outcome 2; recursive contractions and factor extraction also terminate.Only finitely many such updates are possible, so repeated application reaches hardness or tractability and transports that conclusion to the initial signature set.Source: Consider the map · p. 56
• For the two residual forms, Theorems 5.7 and 5.18 give outcome 1, updates satisfying outcome 2 by Definition 5.5, or Equation (16), which Lemma 2.22 transports back to Tract(KΓ).Source: Consider the map · p. 56

6 Mountain Height Two

• If the mountain is tensor-prime, Theorem 2.24 applies; otherwise its parity and endpoints force a 2 + 2 product of nonsingular weighted equalities.Factor reduction and a legal diagonal GO(X)-normalization send such an equality to I, allowing Theorem 2.23 to apply.Source: §6 · p. 56
• A finite algebraic signature set containing a height-two mountain has Tract(KΓ) or K-Holant(Γ) is #P-hard.A height-two mountain is quaternary, has nonzero values at 0000 and 1111, and vanishes on odd Hamming weight.Source: §6 · pp. 56–57
• The proof applies Corollary 2.25 to the mountain, then transfers tractability or hardness back to Γ.Hardness already reduces to K-Holant(Γ), while the tractable case supplies the required predicate.Source: §6 · p. 57

7 Mountain Height Three

• If every supported input has charge divisible by three and Γ contains the specified height-three mountain, then Tract(KΓ) holds or K-Holant(Γ) is #P-hard.The mountain has form M = aδ06 + bδ16 + Q, with ab ≠ 0 and Q EO.Source: §7 · p. 57

7.1 Matching Products and Two-Copy Constructions

• When the central layer is a matching product, a fixed two-copy gadget yields an EO quaternary with six weight-two entries and a hard K-Holant problem.The gadget uses native X-edges; its supported patterns have unique extensions.Source: §7.1 · pp. 57–58

7.2 Six-Port Loop and Two-Copy Contractions

• For a six-port mountain, the proof examines 15 one-copy loops and 5400 labelled two-copy contractions to force support conditions.The support conclusion holds for arbitrary complex q_S values when ab ≠ 0.Source: §7.2 · p. 59
• Theorem 7.5 selects a non-matching quaternary output from a loop, a labelled two-copy contraction, or the explicit matching-product gadget.The selection depends on whether Q lies in the matching-product class; the Q = 0 case uses a contraction with two endpoint–endpoint coefficients.Source: §7.2 · pp. 59–60
• The selected nonzero quaternary EO signature lies outside B×; Theorem 3.7 then proves hardness, which transfers to the original Γ.Its zero charge preserves the charge hypothesis, while the enlargement remains nontractable.Source: §7.2 · p. 60

8 Mountain Height at Least Four

• For every d ≥4, a finite algebraic even-arity signature set with a mountain having nonzero endpoints and nonzero EO layer satisfies Tract(KΓ) or K-Holant(Γ) is #P-hard.Source: §8 · p. 60

8.1 Common Normalization and Phase Recovery

• Under nontractability and a nonzero EO layer, finite equivalent enlargement yields an actual mountain with X-matching-product contractions; a common scalar makes its central layer real, complement-invariant, and exact ARS.Source: §8.1 · pp. 62–63

8.2 Height at Least Five

• For d ≥5, matching-product reconstruction makes the central layer an X-matching product, so Lemma 7.2 yields hardness for the original signature set outside the tractable case.Source: §8.2 · p. 64

8.3 Height Four

• At height four, the eight-port Reed–Muller central tensor has fourteen supported words and is not a matching product, although each contraction is an X-product.Source: §8.3 · p. 64

8.3.1 Translation Form of the Matching Family

• The matching family forces a relabelling over F3^2, after which the central layer has equal coefficients on fourteen affine planes and yields the full sixteen-word Reed–Muller signature.Source: §8.3.1 · pp. 65–66

8.3.2 Normalizing the Endpoint Coefficients

• After the central coefficients are equal, one information-set contraction detects the remaining endpoint invariant.Source: §8.3.2 · p. 66
• When AB ≠ c^2, the construction gives the first nonzero EO outcome; otherwise D(s) ∈ GO(X) normalizes M° to cRM8.The scaling fixes the central layer and sends both endpoint coefficients A and B to c.Source: §8.3.2 · p. 67, §8.3.3 · p. 68

8.3.3 Obtaining Equality from the Reed–Muller Signature

• The Bell reduction establishes that ¬Tract(KΓ) makes K-Holant(Γ) #P-hard, adjoining Y and I to obtain equality without assuming global ARS.The equality dichotomy for the enlarged language transfers hardness back to K-Holant(Γ).Source: §8.3.3 · pp. 67–68
• For d = 4, the remaining cases yield hardness either from a nonzero EO signature outside B× or, after D(s)-equivalence produces cRM8, from Lemma 8.12.Applying D(s) to the whole signature set preserves nontractability, and Lemma 8.12 completes the proof in the cRM8 case.Source: §8.3.3 · p. 68

9.1 Combining the Height Cases

• For a mountain of height d≥3, with every supported charge in dZ, either TractK(G) holds or K-Holant(G) is #P-hard.Source: §9.1 · p. 69
• The mountain theorem combines the cases d=1, 2, 3, and d≥4, which exhaust all heights.Source: §9.1 · p. 69

9.2 Proof of the Main Theorem

• For every finite algebraic signature set G, TractK(G) gives FP; otherwise K-Holant(G) is #P-hard, and the applicable side is decidable from exact algebraic input.Source: §9.2 · p. 69
• The main-theorem proof checks odd arity, one-sided support, and single-layer cases before factor extraction and the two-sided multilayer mountain case.The two supported charge signs may come from different signatures; factor closure can then produce either a pin outcome or a mountain of the charge gcd.Source: §9.2 · p. 69
• The K-coordinate dichotomy transfers to the original Holant problem by a polynomial-time Turing reduction.Source: §9.2 · p. 70

• The result is an FP-versus-#P-hard dichotomy for Boolean Holant on general graphs with finite algebraic complex-valued signatures, under polynomial-time Turing reductions.Source: §10 · p. 70
• The classification uses the same seven conditions as the odd-arity dichotomy, and the criterion is decidable from exact algebraic input.Source: §10 · p. 70
• For all-even cases, charge conservation and tensor-factor extraction lead either to a known classification or to a mountain signature analyzed by height.The full result also combines existing odd-arity, Eulerian-orientation, binary-equality, and quaternary dichotomies; each holographic tractable case uses one basis for the edge and every signature.Source: §10 · p. 70

• The appendix supplies exact finite calculations for the odd-dihedral order-three and high-charge six- and eight-port arguments.It follows detailed propositions with the consequences used in the main proof and preserves exhaustive counts, equations, and verification details.Source: A Exact Finite Certificates · p. 70
• The accompanying programs reconstruct and check the finite objects, while algebraic reductions and direct-gadget arguments remain in the text.Source: A Exact Finite Certificates · p. 70
• Ranks and linear systems are computed exactly over characteristic-zero fields, without numerical tolerance or random sampling.Projective vectors are normalized by their first nonzero coordinate, with a specified integer representative when requested.Source: A Exact Finite Certificates · p. 70
• For the high-charge q8 check, a kernel vector and a rank-97 modular minor bound the matrix rank, while integer minors and modular rank establish Smith-invariant information.The passage describes exact rank and divisibility arguments over the integers, not heuristic finite-field specializations.Source: A Exact Finite Certificates · p. 71

A.1.1 The order-three odd-dihedral six-port certificate

• The projective classification finds 202 lines and 1,212 labelled pencils satisfying the stated conditions in each parity.The lines comprise one-block, two-block, and three-block geometries.Source: §A.1.1 · p. 72
• Exact intersection of the local support lists leaves 873 distinct supports, exactly the classified coset families, the 480-element orbit of S⋆, and the empty support.The enumeration starts from 10,452 candidates.Source: §A.1.1 · p. 74
• The certificate is a normalized finite statement and does not prove the broader support bounds, arbitrary-arity argument, or reduction for the entire signature set.Those arguments remain in the main proof.Source: §A.1.1 · p. 74
• For each fixed pair and xor, the local support union is empty or contains at most two complementary pairs in its residual parity.The condition applies when every contraction belongs to the specified B3 class or is zero.Source: §A.1.1 · p. 74
• Every six-port tensor meeting the local contraction condition has empty support, a partition coset of type (6), (4 + 2), or (2 + 2 + 2), or a bit-flip/port-permutation image of S⋆.Every nonempty support has one parity.Source: §A.1.1 · p. 74
• The support classification alone does not establish coefficient factorization; that argument and exclusions of contractions supported on two points are proved separately.Those steps are established in Theorem 5.14.Source: §A.1.1 · p. 75

A.1.2 High-charge six-port loop and two-copy arrays

• The calculation reduces 315 signed-equation branches to 1,868 linear subspaces, then evaluates 61 exact real-polynomial queries—51 for sparse-orbit projective charts and 10 for dense-orbit implications—all of which are UNSAT.Source: §A.1.2 · pp. 75–76
• The UNSAT conclusions rely on Z3 because the runs neither request nor check solver proof objects.Exporting or rerunning the inputs does not remove this dependence.Source: §A.1.2 · p. 76
• These arrays are not themselves established as direct gadgets, and the certificate does not establish a reduction for the entire signature set.Those arguments remain in Section 7.2 and Theorem 7.5.Source: §A.1.2 · p. 76
• If all 15 loop arrays and 5,400 labelled two-copy arrays satisfy the stated conditions, the nonzero triple coefficients occupy at most one complementary pair {S, U\S}.The conclusion allows arbitrary complex coefficients and nonzero t.Source: §A.1.2 · p. 76
• The 15 loop conditions alone do not imply the coefficient conclusion: a full-support vector satisfies all loop-array conditions but fails a labelled two-copy array condition.The two-copy array has six nonzero entries and lies outside the required class.Source: §A.1.2 · p. 77

A.1.3 Eight-port matching families

• Exactly nine labelled families satisfy the matching constraints: seven come from a global perfect matching and violate the intersection condition, while two remain up to relabelling.An exhaustive backtracking search finds 236 nodes and nine leaves.Source: §A.1.3 · p. 77
• The intersection condition on the surviving family yields a relabelling as a translation family indexed by F3^2.The two surviving labelled families differ only by relabelling.Source: §A.1.3 · p. 78
• Under the coefficient constraints, the nonzero four-set coefficients are exactly those on the fourteen affine planes, and all supported coefficients are equal.The proof forces nonplane coefficients to vanish and connects the plane coefficients and pair weights to one common nonzero value.Source: §A.1.3 · pp. 78–79