Orthogonality of Boolean subset characters
ProvedQuantumLTF.Majority.boolean_character_orthogonalityboolean-functionsfourier-analysisquantum-algorithmssection-4
For a subset , define its Boolean character by . These characters are orthogonal under the unnormalized counting measure on the Boolean cube:
This is the elementary Fourier-analytic cancellation underlying weighted Krawtchouk orthogonality after characters are grouped by Hamming weight.
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Basic
Formal statement
namespace QuantumLTF.Majority open QAlgorithms theorem boolean_character_orthogonality : ∀ k : ℕ, ∀ T U : Finset (Fin k), ∑ S : Qubits k, (-1 : ℤ) ^ ((T.filter fun i => S i).card) * (-1 : ℤ) ^ ((U.filter fun i => S i).card) = if T = U then (2 : ℤ)^k else 0 := by sorry end QuantumLTF.Majority
Source
Standard Walsh–Fourier character orthogonality on the Boolean cube; used implicitly in Krivcenko, Nguyen, de Wolf, STOC 2027 submission #347, Section 4.2 Krawtchouk orthogonality calculation.