Pointwise odd-support polynomial witness
ProvedQuantumLTF.Majority.odd_polynomial_pointwise_witnessadversary-methodkrawtchouk-polynomialssection-4
For every odd , the Section 4.2 polynomial construction provides normalized coefficient families with complementary interior supports and zero weighted signed cross term. Moreover, for a universal constant , every degree satisfies
This is the pointwise estimate obtained from the interlacing polynomial construction before summing over degrees.
Preamble
import Mathlib
Formal statement
namespace QuantumLTF.Majority theorem odd_polynomial_pointwise_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 * (r : ℝ) / (((t : ℕ) + 1 : ℕ) * (r - (t : ℕ) + 1 : ℕ)) := by sorry end QuantumLTF.Majority
Source
Krivcenko, Nguyen, de Wolf, arXiv:2609.40331v3, Section 4.2 and Lemma 4.3: complementary polynomial construction and pointwise coefficient-energy estimate, with the endpoint and cross-term conditions used by the adversary proof made explicit.