Alon's construction over GF(2^k): character, BCH columns and the connection set
DefinitionKonyaginUnitVectors_AlonConstructionalonextremal-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 .
The module defines the ingredients of Alon's construction of an orthonormal labeling:
psi y;chi w g, the character of the additive group indexed by ;gamma x, the columns of the parity-check matrix of the binary BCH code of designed distance ;W0andW1, a partition of ;Sset, the connection set of a Cayley graph on .
Formalization Note. All definitions are for a finite field F with [Algebra (ZMod 2) F]; the trace is Algebra.trace (ZMod 2) F.
Definition code
import Mathlib
/-!
# Alon-type construction over `GF(2^k)` (definitions)
Everything is stated for an arbitrary finite field `F` of characteristic 2 that is an algebra over
`ZMod 2` (e.g. `GaloisField 2 k`).
-/
set_option autoImplicit false
namespace KonyaginUnitVectors.Alon
variable (F : Type*) [Field F] [Algebra (ZMod 2) F]
/-- The `±1`-valued additive character `ψ y = (-1)^{Tr y}` of `F`, `Tr : F → ZMod 2` the absolute trace. -/
noncomputable def psi (y : F) : ℝ := if Algebra.trace (ZMod 2) F y = 0 then 1 else -1
/-- The character `ψ_w(g) = ψ (w₁ g₁ + w₂ g₂ + w₃ g₃)` of the additive group `F × F × F`. -/
noncomputable def chi (w g : F × F × F) : ℝ := psi F (w.1 * g.1 + w.2.1 * g.2.1 + w.2.2 * g.2.2)
/-- `γ x = (x, x³, x⁵)`: the columns of the parity check matrix of the binary BCH code of designed distance 7. -/
def gamma (x : F) : F × F × F := (x, x ^ 3, x ^ 5)
variable [Fintype F]
open Classical in
/-- Nonzero `x` with `Tr (x⁹) = 0`. -/
noncomputable def W0 : Finset F :=
Finset.univ.filter fun x => x ≠ 0 ∧ Algebra.trace (ZMod 2) F (x ^ 9) = 0
open Classical in
/-- Nonzero `x` with `Tr (x⁹) = 1`. -/
noncomputable def W1 : Finset F :=
Finset.univ.filter fun x => x ≠ 0 ∧ Algebra.trace (ZMod 2) F (x ^ 9) ≠ 0
open Classical in
/-- The connection set `S = {γ x + γ y : x ∈ W0, y ∈ W1}` of the Cayley graph on `F × F × F`. -/
noncomputable def Sset : Finset (F × F × F) :=
(W0 F ×ˢ W1 F).image fun p => gamma F p.1 + gamma F p.2
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)