Any six columns of the BCH check matrix of designed distance 7 are independent
ProvedKonyaginUnitVectors.Alon.bch6_independentalonextremal-combinatoricsfinite-fieldsorthonormal-labelings
Let be a field of characteristic and let be a finite set with at most elements such that
Then . Equivalently, any at most six distinct columns , , of the parity-check matrix of the binary BCH code of designed distance are linearly independent over .
Formalization Note. Only the characteristic is assumed; need not be finite.
Preamble
import Mathlib
Formal statement
namespace KonyaginUnitVectors.Alon
theorem bch6_independent {F : Type*} [Field F] [CharP F 2] (T : Finset F) (h0 : (0 : F) ∉ T)
(hT : T.card ≤ 6) (h1 : ∑ x ∈ T, x = 0) (h3 : ∑ x ∈ T, x ^ 3 = 0) (h5 : ∑ x ∈ T, x ^ 5 = 0) :
T = ∅ := 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)