A Fourier system of vectors with a prescribed Gram matrix
ProvedKonyaginUnitVectors.Alon.fourier_systemThroughout, 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 be any subset (the additive group has elements), let , and let be the characters of . Suppose
Then there are vectors , , with
and
In other words, is the Gram matrix of a vector system whenever it is positive semidefinite, where is the adjacency matrix of the Cayley graph on with connection set . This is the Fourier (spectral) realisation of orthonormal labelings from Cayley graphs used in Alon's construction.
Formalization Note. chi F w s is the character of the definition module KonyaginUnitVectors_AlonConstruction; the vectors live in EuclideanSpace ℝ (F × F × F) and inner ℝ is its inner product. No assumption such as is needed.
import Mathlib import Definitions.Def_KonyaginUnitVectors_AlonConstruction
namespace KonyaginUnitVectors.Alon
open Classical in
theorem fourier_system (F : Type*) [Field F] [Fintype F] [CharP F 2] [Algebra (ZMod 2) F]
(S : Finset (F × F × F)) (κ : ℝ)
(hκ : ∀ w : F × F × F, 0 ≤ 1 + κ * ∑ s ∈ S, chi F w s) :
∃ u : F × F × F → EuclideanSpace ℝ (F × F × F),
(∀ g h : F × F × F, inner ℝ (u g) (u h) = (if g = h then (1 : ℝ) else 0) + κ * (if g + h ∈ S then 1 else 0)) ∧
‖∑ g, u g‖ ^ 2 = (Fintype.card F : ℝ) ^ 3 * (1 + κ * (S.card : ℝ)) := by sorry
end KonyaginUnitVectors.Alon