Cardinality of a support-intersection fiber
ProvedQuantumLTF.Majority.intersectionIndex_fiber_cardboolean-cubecombinatoricssection-4
If has size , then for every , the number of Boolean strings satisfying is
Choose the selected coordinates inside and assign the remaining coordinates arbitrarily.
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority open QAlgorithms theorem intersectionIndex_fiber_card : ∀ n r : ℕ, r ≤ n → ∀ A : ExactSupports n r, ∀ a : Fin (r+1), (Finset.univ.filter fun S : Qubits n => intersectionIndex A S = a).card = 2^(n-r) * r.choose a := by sorry end QuantumLTF.Majority
Source
Elementary Boolean-cube intersection counting used in the Section 4.2 adversary objective calculation of Krivcenko, Nguyen, de Wolf, arXiv:2609.40331v3.