A character-sum bound for the Gold exponent 9
ProvedKonyaginUnitVectors.Alon.gold_charsum_sq_lealonextremal-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 .
For all ,
The exponent is a Gold exponent, so is a quadratic form over ; this is what makes a bound of order available without Weil-type estimates. The bound controls the eigenvalues of a Cayley graph on in Alon's construction of orthonormal labelings.
Formalization Note. psi F is defined in the definition module KonyaginUnitVectors_AlonConstruction; the bound holds for every finite field of characteristic and every .
Preamble
import Mathlib import Definitions.Def_KonyaginUnitVectors_AlonConstruction
Formal statement
namespace KonyaginUnitVectors.Alon
theorem gold_charsum_sq_le (F : Type*) [Field F] [Fintype F] [CharP F 2] [Algebra (ZMod 2) F]
(a b c : F) :
(∑ x : F, psi F (a * x + b * x ^ 3 + c * x ^ 5 + x ^ 9)) ^ 2 ≤ 64 * (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)