Sum over the Boolean cube grouped by intersection size
ProvedQuantumLTF.Majority.sum_by_intersectionIndexadversary-methodboolean-cubecombinatoricssection-4
For a fixed support of size , any sum over Boolean strings of a function depending only on can be grouped by intersection size:
This is the weighted-sum form of the intersection-fiber cardinality formula.
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority open QAlgorithms theorem sum_by_intersectionIndex : ∀ n r : ℕ, r ≤ n → ∀ A : ExactSupports n r, ∀ f : Fin (r+1) → ℝ, ∑ S : Qubits n, f (intersectionIndex A S) = (2^(n-r) : ℝ) * ∑ a : Fin (r+1), (r.choose a : ℝ) * f a := by sorry end QuantumLTF.Majority
Source
Immediate fiberwise summation consequence of Boolean-cube intersection counting; used in Krivcenko, Nguyen, de Wolf, arXiv:2609.40331v3, Section 4.2.