Alon's system of unit vectors over GF(2^k)
ProvedKonyaginUnitVectors.Alon.alon_systemalonextremal-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 .
If , then there are unit vectors , , in a Euclidean space such that among any three distinct vectors of the system some two are orthogonal, and
With vectors the sum thus has norm at least . This is the construction behind Alon's lower bound for orthonormal systems without three pairwise non-orthogonal vectors, which matches Konyagin's upper bound up to the constant.
Formalization Note. The orthogonality condition is stated through the inner product of EuclideanSpace ℝ (F × F × F); the system is indexed by the group itself.
Preamble
import Mathlib
Formal statement
namespace KonyaginUnitVectors.Alon
theorem alon_system (F : Type*) [Field F] [Fintype F] [CharP F 2] [Algebra (ZMod 2) F]
(hq : 256 ≤ Fintype.card F) :
∃ u : F × F × F → EuclideanSpace ℝ (F × F × F),
(∀ g, ‖u g‖ = 1) ∧
(∀ g h k : F × F × F, g ≠ h → h ≠ k → g ≠ k →
inner ℝ (u g) (u h) = 0 ∨ inner ℝ (u h) (u k) = 0 ∨ inner ℝ (u g) (u k) = 0) ∧
(1 / 13 : ℝ) * ((Fintype.card F : ℝ) ^ 3) ^ ((2 : ℝ) / 3) ≤ ‖∑ g, u g‖ := 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)