Theorem 3.1, p. 11 — {T(z) : z ∈ GF(2^k) ∖ {0}} is a stable SKC: each pair of players can meet in round i in exactly 2^{i−1} tournaments
ProvedStableSKC.Galois.theorem_3_1Let be presented as for an irreducible of degree with root , let be the degree function with respect to the basis , and let be a knockout tournament whose players are the elements of and which satisfies Lemma 3.1:
For nonzero let be the tournament obtained from by replacing each player with . Then
is a stable serial knockout competition:
- consists of knockout tournaments on the players;
- for every pair of distinct players and every round ,
This is the paper's main result: stable serial knockout competitions exist for every number of players , and they are obtained explicitly from the multiplicative group of . The count is the only possible stable value, since a player can meet opponents in round of any single tournament.
Formalization Note The family is indexed by the units z : Fˣ of a field F with a power basis pb over ZMod 2 of dimension = pb.dim. IsStableSKC includes that the index set has elements; the explicit count is stated as a second conclusion (the proof on p. 11 prints , a misprint; p. 4 gives ). The hypothesis on is required for distinct players only, since is undefined on the page; Lemma 3.1 shows it is satisfiable. No assumption is made, as Theorem 3.1 does not need it.
import Mathlib import Definitions.Def_StableSKC_Galois_Model
namespace StableSKC.Galois
theorem theorem_3_1 {F : Type*} [Field F] [Fintype F] [DecidableEq F] [Algebra (ZMod 2) F]
(pb : PowerBasis (ZMod 2) F) (T : Seeding pb.dim F)
(hT : ∀ x y : F, x ≠ y → CanMeetIn T x y (1 + deg pb (x - y))) :
IsStableSKC (fun z : Fˣ => scale T z) ∧
∀ x x' : F, x ≠ x' → ∀ i : ℕ, 1 ≤ i → i ≤ pb.dim →
meetCount (fun z : Fˣ => scale T z) x x' i = 2 ^ (i - 1) := by sorry
end StableSKC.Galois
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.