Exact Distribution Laws and Complete Horizon Classification for Walsh Interaction-Order Energies via Krawtchouk Collision Exclusion

Abstract

Paper-2 v2.0 — Exact Distribution Laws and Complete Horizon Classification for Walsh Interaction-Order Energies via Krawtchouk Collision Exclusion Paper-2 develops an exact computational framework for Walsh interaction-order energies on the Boolean cube. It extends the study of permutation moments to exact distributional structure, computational complexity, structured exact algorithms, support geometry, multiplicity formulas, deterministic continuation horizons, and lower-order exact-counting complexity. The central computational message is that exact distributional calculation has sharply different regimes. For general inputs, exact atom counting can encounter #P-type counting barriers, while important structured classes admit exact finite formulas, recurrences, fixed-parameter algorithms, and algebraic representations. For sparse fixed-defect fields, the full Walsh interaction-order energy depends only on pairwise Hamming distances. This reduction leads to exact finite-state distribution laws, low-order closed forms, all-order recurrences, finite-alphabet extensions, fixed-parameter support algorithms, Gaussian determinant formulas, and a GKZ/A-hypergeometric representation of exact multiplicities. New in Version 2.0 Version 2.0 adds a scoped lower-order exact-counting complexity result and an independent finite-verification layer. For the exact atom-counting problem ORDER-1-WALSH-ATOM, the paper gives a polynomial-time metric reduction from #SUBSET-SUM on an infinite family of even Boolean-cube dimensions. The construction uses signed-radix separation, an anchored cube embedding, Gram-matrix rigidity, and an exact frame-multiplicity calculation. For the constructed instances, the exact indexed-permutation count takes the form C₁ = F · 2^(M−m) · α · c_T, where F = n(n−1)!M, c_T is the source #SUBSET-SUM count, and α is the explicitly determined target-symmetry factor. This establishes the scoped result that ORDER-1-WALSH-ATOM is #P-complete under polynomial metric reductions on the stated infinite even-n family, and therefore exact PMF/CDF evaluation inherits a corresponding #P-hardness boundary in this setting. An invertible Boolean linear map A = I + 11ᵀ for even n maps order 1 to order n−1, giving the corresponding exact-distribution hardness result for the near-top Walsh order. The result is deliberately scoped: it is an exact-counting result; it does not establish approximation hardness; intermediate Walsh orders are not claimed to be classified by this reduction; the rank-one Hamming/QAP connection is used as a structured corollary and not as a claim of generic QAP novelty. Independent finite verification The Version 2.0 proof layer is supported by independent exact finite checks. The verification suite includes: an exhaustive N=4 indexed-permutation theorem-family sweep with 315/315 exact matches; three auxiliary exhaustive N=8 fixtures, giving exact counts of 96, 192, and 96; three independent exact reduced N=16 evaluations, giving 12,288, 24,576, and 12,288; exact d=3 Gram-frame verification with 192/192 admissible frames. The N=16 calculation is an exact reduced evaluator and is not described as brute-force enumeration of all 16! permutations. The verification implementation is logically separated from the theorem-prediction path so that the finite computations provide an independent cross-check of the analytic formulas. Continuation-horizon classification A second principal result is the complete deterministic continuation-horizon classification. If H(k) denotes the number of additional coordinates required to distinguish exact pair states at Walsh order k, then H(2) = 1, H(3) = 2, H(k) = 3 for every even k ≥ 4, and H(k) = 4 for every odd k ≥ 5. The even-order result is obtained through a Krawtchouk collision-exclusion argument using recurrence relations, parity-channel factorization, real-rooted polynomial structure, degree complementation, and coordinate symmetry. The universal upper bound is H(k) ≤ min(k−1, 4), and the exact classification sharpens this bound for every k ≥ 2. Main mathematical framework For a function f : F₂ⁿ → R with N = 2ⁿ, the Walsh coefficient is f̂(A) = (1/N) Σₓ f(x)(−1)^(Σ_{i∈A} xᵢ), and the order-k interaction energy is E_k(f) = Σ_{|A|=k} f̂(A)². The scaled energy used throughout the paper is Q_k(f) = N²E_k(f). The binary Krawtchouk polynomial is K_k⁽ⁿ⁾(d) = Σ_{j=0}^k (−1)^j C(d,j)C(n−d,k−j), with generating function Σ_{k=0}^n K_k⁽ⁿ⁾(d)z^k = (1−z)^d(1+z)^(n−d), and recurrence (k+1)K_{k+1}(x;N) = (N−2x)K_k(x;N) − (N−k+1)K_{k−1}(x;N). For a fixed-defect field f(v) = b + Σ_{i=1}^s δᵢ 1_{v=vᵢ}, the exact pair-distance representation is Q_k = C(n,k)Σᵢδᵢ² + 2Σ_{i<j}δᵢδⱼK_k⁽ⁿ⁾(dᵢⱼ). If W_n(D) denotes the multiplicity of a reachable pair-distance state D, then the exact PMF has the form Pr(Q_k=q) = 1/(2ⁿ−1)^(s−1) · Σ_{D(D)=q} W_n(D). This separates the exact energy map from the finite multiplicity problem. Low-order formulas For order 1, Q₁⁽ʳ⁾ = (Σᵢ δᵢσᵢ,ᵣ)². For order 2, using the pair-Gram representation, Q₂(t) = ½[tr(ΔG_tΔG_t) − t(Σᵢδᵢ)²], equivalently, Q₂(t) = C(t,2)Σᵢδᵢ² + Σ_{i<j}δᵢδⱼ[mᵢⱼ(t)² − t]. For order 3, K₃⁽ᵗ⁾(dᵢⱼ) = [m³ − (3t−2)m]/6, and therefore Q₃(t) = C(t,3)Σᵢδᵢ² + (1/3)Σ_{i