Fourier Fact Vector
ProvedLIDT.MIPStarRE.LDT.Preliminaries.fourier_fact_vectorA finite-field vector character averages to zero away from the zero vector.
For a vector v : Fin m -> F, average the vector Fourier character at v applied to a uniformly sampled vector u. The average detects exactly whether v is the zero vector:
This is the coordinatewise finite-field Fourier orthogonality identity. It supplies the vector-valued companion to the scalar fact for higher-dimensional polynomial calculations.
Formalization credit: Sirui Lu, Ruixuan Deng, Yanqiao Zhu, and Zhengfeng Ji (arXiv:2609.19814). Mathematical source: Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen (arXiv:2009.12982).
Formalization Note. The source declaration is MIPStarRE.LDT.Preliminaries.fourier_fact_vector; its Lean statement gives the exact quantifier order and all boundary hypotheses.
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_ParametersBase
import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_FiniteFields
import Mathlib
import Mathlib.Analysis.Fourier.FiniteAbelian.Orthogonality
import Mathlib.Analysis.SpecialFunctions.Complex.CircleAddChar
import Mathlib.NumberTheory.LegendreSymbol.AddCharacter
open LIDT
/-!
# Finite fields and Fourier orthogonality
This file formalizes the finite-field trace and the two Fourier orthogonality facts
from `references/ldt-paper/preliminaries.tex` (lines 15–83).
## Main results
* `fourier_fact_scalar` (`prop:fourier-fact-scalar`):
`𝔼_{x ∈ 𝔽_q} ω^{tr[x·a]} = 1 if a = 0, 0 otherwise`
* `fourier_fact_vector` (`prop:fourier-fact-vector`):
Vector version over `𝔽_q^m`.
## References
* `references/ldt-paper/preliminaries.tex`, lines 15–83
-/
@[expose] public section
open scoped BigOperators
open LIDT.MIPStarRE.LDT.Preliminaries
open MIPStarRE.LDT
-- The Fourier section uses `[Fintype F]` (rather than `[Finite F]` as in the Trace section)
-- because `AddChar.expect_eq_ite` requires a `Fintype` instance. Downstream users with
-- only `[Finite F]` can obtain `Fintype` via `Fintype.ofFinite`.
variable {p : ℕ} [Fact p.Prime]
variable {F : Type*} [Field F] [Fintype F] [DecidableEq F] [Algebra (ZMod p) F]
variable {m : ℕ}
-- We define `ffDotProduct` directly rather than reusing `Matrix.dotProduct` to avoid
-- pulling in the full `Mathlib.Data.Matrix.Basic` import. The definitions are identical.theorem LIDT.MIPStarRE.LDT.Preliminaries.fourier_fact_vector (v : Fin m → F) :
𝔼 u : (Fin m → F), _root_.LIDT.MIPStarRE.LDT.Preliminaries.ffVecChar (p := p) (F := F) v u =
if v = 0 then (1 : ℂ) else 0 := by sorry