Low-weight partition power sums have vanishing Möbius average
ProvedQuantumBipartiteTesting.Bipartiteness.partition_power_sum_cancellationmobius-inversionpartition-latticepolynomial-method
Let be a partition of a set of elements, and let be arbitrary real numbers indexed by an element and one of finitely many colors . For a positive integer and a partition , define
Let be positive integers satisfying
Then the signed refinement-chain coefficients satisfy
This is the polynomial cancellation identity underlying the extra power of the block parameter in the matching-moment numerator. It applies in particular to the component-color edge counts used in the source factorization.
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction open scoped BigOperators Classical
Formal statement
theorem QuantumBipartiteTesting.Bipartiteness.partition_power_sum_cancellation {k colors m : ℕ}
(p : QuantumBipartiteTesting.Bipartiteness.Partition k) (a : Fin m → ℕ)
(ha : ∀ t, 0 < a t) (d : Fin k → Fin colors → ℝ)
(hbudget : (∑ t, (a t-1))+(QuantumBipartiteTesting.Bipartiteness.Blocks p).card < k) :
(∑ r : QuantumBipartiteTesting.Bipartiteness.Partition k,
if QuantumBipartiteTesting.Bipartiteness.Refines r p then
(QuantumBipartiteTesting.Bipartiteness.Mobius r p:ℝ) *
(∏ t : Fin m, ∑ S ∈ QuantumBipartiteTesting.Bipartiteness.Blocks r,
∑ j : Fin colors, (∑ i ∈ S, d i j)^(a t)) else 0) = 0 := by sorrySource
Ambainis–Childs–Liu, Quantum Property Testing for Bounded-Degree Graphs, https://arxiv.org/pdf/1012.3174, Proposition 19, §C.5 equation (13), printed pp.20–21; used in Proposition 6, pp.8–9. The polynomial identity is proved for arbitrary real entries, extending the nonnegative component-count entries used there. Kayal–Sen–Szabó, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf, Appendix A.2 equation (A.7), pp.30–31.