Odd-support Krawtchouk polynomial witnesses of logarithmic energy
ProvedQuantumLTF.Majority.odd_krawtchouk_polynomial_witnessadversary-methodkrawtchouk-polynomialssection-4
There is a universal constant such that every odd admits two real coefficient families with the endpoint normalization and complementary interior support required by the Section 4.2 adversary construction, whose weighted signed cross term vanishes, and whose total binomial energy satisfies
These are the polynomial witnesses constructed from the interlacing zero sets in the paper. The explicit cross-term condition is included because it is required by the corrected scalar Parseval identity.
Preamble
import Mathlib
Formal statement
namespace QuantumLTF.Majority theorem odd_krawtchouk_polynomial_witness : ∃ C : ℝ, 0 < C ∧ ∀ r : ℕ, 3 ≤ r → Odd r → ∃ p q : Fin (r+1) → ℝ, p 0 * q 0 = 1/2 ∧ (∀ t : Fin (r+1), 1 ≤ (t : ℕ) → (t : ℕ) < r → (p t = 0 ↔ q t ≠ 0)) ∧ (∑ t : Fin (r+1), (r.choose t : ℝ) * ((-1 : ℝ) ^ (t : ℕ) * p t * q t)) = 0 ∧ (∑ t : Fin (r+1), (r.choose t : ℝ) * (p t^2 + q t^2)) ≤ C * Real.log r := by sorry end QuantumLTF.Majority
Source
Krivcenko, Nguyen, de Wolf, arXiv:2609.40331v3, Section 4.2, especially the polynomial construction and estimates summarized in Lemma 4.3 and used in Lemma 4.5.