Self-dual basis of over
DefinitionSpencerEight_Supplement_IsSelfDualBasisdiscrepancymatrix-spencerp2o-gran-per-chapterp2o-plan-bookp2o-v1random-matrices
Let , , be the absolute trace. A basis of over is self-dual if it is orthonormal for the trace form:
Through a self-dual basis, the coordinates of are and the dot product of coordinate vectors is .
Formalization Note is GaloisField 2 k and the absolute trace is Algebra.trace (ZMod 2) (GaloisField 2 k), which for a finite field equals the sum of the Galois conjugates. This is the field trace, not the matrix trace.
Definition code
import Mathlib
namespace SpencerEight.Supplement
/-- A self-dual basis of `GF(2^k)` over `F₂` (Section 15.3, Song, Zhang, *Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input*, arXiv:2609.15025 (held version, sha256 9ccbcdb8…), p.291 (PDF p.291)):
a basis `b₁, …, b_k` with `Tr[bᵢ bⱼ] = 1{i = j}`, where `Tr` is the absolute trace
`GF(2^k) → F₂`, `x ↦ x + x² + ⋯ + x^{2^{k−1}}`.
**Formalization Note** `GF(2^k)` is Mathlib's `GaloisField 2 k` and `F₂` is `ZMod 2`. The absolute trace is
`Algebra.trace (ZMod 2) (GaloisField 2 k)`, the trace of multiplication; for a finite field it equals the sum
of the Galois conjugates `x + x² + ⋯ + x^{2^{k−1}}`. It is the field trace, not the matrix trace. -/
def IsSelfDualBasis {k : ℕ} (b : Module.Basis (Fin k) (ZMod 2) (GaloisField 2 k)) : Prop :=
∀ i j, Algebra.trace (ZMod 2) (GaloisField 2 k) (b i * b j) = if i = j then 1 else 0
end SpencerEight.Supplement
Source
Song, Zhang, Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input, arXiv:2609.15025 (held version, sha256 9ccbcdb8…), Section 15.3, p.291 (PDF p.291)