Structure of the connection set S
ProvedKonyaginUnitVectors.Alon.S_structurealonextremal-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 be the two classes , , let and . Then:
- the map is injective on ;
- for , (in particular );
- no three elements satisfy ;
- ;
- .
Property 3 says that the Cayley graph on with connection set is triangle-free, and properties 1 and 4 give the size of ; both are needed in Alon's construction of orthonormal labelings.
Formalization Note. W0 F, W1 F, Sset F and gamma F are the platform definitions of the definition module KonyaginUnitVectors_AlonConstruction.
Preamble
import Mathlib import Definitions.Def_KonyaginUnitVectors_AlonConstruction
Formal statement
namespace KonyaginUnitVectors.Alon
theorem S_structure (F : Type*) [Field F] [Fintype F] [CharP F 2] [Algebra (ZMod 2) F] :
Set.InjOn (fun p : F × F => gamma F p.1 + gamma F p.2) ↑(W0 F ×ˢ W1 F) ∧
(∀ p ∈ W0 F ×ˢ W1 F, gamma F p.1 + gamma F p.2 ≠ 0) ∧
(∀ s₁ ∈ Sset F, ∀ s₂ ∈ Sset F, ∀ s₃ ∈ Sset F, s₁ + s₂ + s₃ ≠ 0) ∧
(Sset F).card = (W0 F).card * (W1 F).card ∧
(W0 F).card + (W1 F).card + 1 = Fintype.card F := 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)