Krawtchouk polynomials as fixed-weight character sums
ProvedQuantumLTF.Majority.krawtchouk_as_character_sumfourier-analysiskrawtchouk-polynomialsquantum-algorithmssection-4
Fix a canonical subset . The binary Krawtchouk polynomial is the sum of Walsh characters over all subsets of weight :
Grouping the subsets by recovers the defining binomial sum. This representation connects the polynomial definition used in Section 4 to Fourier analysis on the Boolean cube.
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority theorem krawtchouk_as_character_sum : ∀ k : ℕ, ∀ t a : Fin (k+1), (krawtchouk k t a : ℤ) = ∑ T ∈ (Finset.univ : Finset (Fin k)).powersetCard (t : ℕ), (-1 : ℤ) ^ ((T ∩ (Finset.univ.filter fun i : Fin k => (i : ℕ) < (a : ℕ))).card) := by sorry end QuantumLTF.Majority
Source
Standard character-sum representation of binary Krawtchouk polynomials; Krivcenko, Nguyen, de Wolf, STOC 2027 submission #347, Sections 4.2–4.3, Krawtchouk transform used in the adversary construction.