Proof of Theorem 3.1, p. 11 — #{r ∈ GF(2^k) : r ≠ 0, 1 + d(r) = i} = 2^{i−1}
ProvedStableSKC.Galois.degree_countcombinatoricscountingfinite-fieldsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be presented with a root of an irreducible polynomial of degree over , and let be the degree of . Then for every round ,
This is the counting step of the proof of Theorem 3.1: the number of tournaments in which two given distinct players can meet in round equals the number of nonzero field elements of degree .
Formalization Note The proof of Theorem 3.1 on p. 11 prints the value as . That is a misprint: the elements of degree exactly are those with , for and arbitrary, which gives , in agreement with the stability count stated on p. 4. The formal statement uses .
Preamble
import Mathlib import Definitions.Def_StableSKC_Galois_Model
Formal statement
namespace StableSKC.Galois
theorem degree_count {F : Type*} [Field F] [Fintype F] [DecidableEq F] [Algebra (ZMod 2) F]
(pb : PowerBasis (ZMod 2) F) (i : ℕ) (hi1 : 1 ≤ i) (hik : i ≤ pb.dim) :
(Finset.univ.filter fun r : F => r ≠ 0 ∧ 1 + deg pb r = i).card = 2 ^ (i - 1) := by sorry
end StableSKC.Galois
Source
Lambers, Pendavingh & Spieksma, How to Design a Stable Serial Knockout Competition, arXiv:2211.02513v1, p. 11, proof of Theorem 3.1 (printed as 2^i; corrected to 2^{i−1}, cf. p. 4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.