Möbius cancellation on a strict partition interval
ProvedQuantumBipartiteTesting.Bipartiteness.partition_mobius_cancellationmobius-inversionpartition-latticequantum-query-complexity
Let and be partitions of a finite set, with a proper refinement of . Write for the signed refinement-chain coefficient of their partition lattice. Then
The coefficient includes the empty chain on a diagonal interval and the signed count of chains on each strict interval. This cancellation is the partition inclusion-exclusion identity used to eliminate low-order terms in the matching-moment factorization.
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction open scoped BigOperators Classical
Formal statement
theorem QuantumBipartiteTesting.Bipartiteness.partition_mobius_cancellation {k : ℕ}
(p r : QuantumBipartiteTesting.Bipartiteness.Partition k)
(hpr : QuantumBipartiteTesting.Bipartiteness.Refines p r) (hne : p ≠ r) :
(∑ t : QuantumBipartiteTesting.Bipartiteness.Partition k,
if QuantumBipartiteTesting.Bipartiteness.Refines p t ∧
QuantumBipartiteTesting.Bipartiteness.Refines t r then
QuantumBipartiteTesting.Bipartiteness.Mobius t r else 0) = 0 := by sorrySource
Ambainis–Childs–Liu, Quantum Property Testing for Bounded-Degree Graphs, https://arxiv.org/pdf/1012.3174, Proposition 5 and §C.4 equation (11), printed pp.7 and20. Used by Kayal–Sen–Szabó, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf, Appendix A.2 equations (A.3), (A.7), pp.30–31.