Spectral lower bound for the connection set S
ProvedKonyaginUnitVectors.Alon.S_spectrumalonextremal-combinatoricsfinite-fieldsorthonormal-labelings
Throughout, is a finite field of characteristic with elements, regarded as an algebra over (for example ), is the absolute trace, and is the associated additive character of .
Let and be as in the definition module, and assume that is injective on . Put . Then for every character of
and moreover
These bounds on the smallest eigenvalue of the Cayley graph on with connection set , and on the sizes of the two classes, are what make the Fourier-type system of unit vectors of Alon's construction well defined and give the norm estimate.
Formalization Note. Injectivity is a hypothesis (it is proved separately); chi F w s is the character of the definition module.
Preamble
import Mathlib import Definitions.Def_KonyaginUnitVectors_AlonConstruction
Formal statement
namespace KonyaginUnitVectors.Alon
theorem S_spectrum (F : Type*) [Field F] [Fintype F] [CharP F 2] [Algebra (ZMod 2) F]
(hinj : Set.InjOn (fun p : F × F => gamma F p.1 + gamma F p.2) ↑(W0 F ×ˢ W1 F)) :
(∀ w : F × F × F, -((8 * Real.sqrt (Fintype.card F) + 1) ^ 2 / 4) ≤ ∑ s ∈ Sset F, chi F w s) ∧
|((W0 F).card : ℝ) - ((W1 F).card : ℝ)| ≤ 8 * Real.sqrt (Fintype.card F) + 1 := by sorry
end KonyaginUnitVectors.Alon
Source
N. Alon, Explicit Ramsey graphs and orthonormal labelings, Electron. J. Combin. 1 (1994), R12, doi:10.37236/1192 (Sections 3 and 4; the construction here partitions by Tr(x^9) instead of the leading bit of x^7)