Octal Periodicity Theorem
ProvedOctalGames.periodicity_theoremLet be an octal game whose digits vanish beyond index (so has finite length at most ), and let be the nim-value of a -heap of tokens (see the definition OctalGames_Code). Let and . If
then for all . That is, is periodic with period and preperiod .
This is the Octal Periodicity Theorem. It reduces periodicity of a finite octal game to a finite computation: one computes and checks the hypothesis. For example, Kayles () has period and preperiod , which follows from the first values. It is the standard tool behind every known solution of a periodic octal game, and a companion to the open question OctalGames.guy_question (is every finite octal game eventually periodic?).
Formalization Note Siegel states the theorem for the exact length (the largest index with ). Here is any index beyond which all digits vanish; the two forms are equivalent, since a larger only enlarges the range that the hypothesis checks.
import Mathlib import Definitions.Def_OctalGames_Code open OctalGames
theorem OctalGames.periodicity_theorem (c : Code) (k n₀ p : ℕ) (hk : ∀ i, k < i → c.digit i = 0) (hn₀ : 1 ≤ n₀) (hp : 1 ≤ p) (h : ∀ n, n₀ ≤ n → n < 2 * n₀ + p + k → grundy c (n + p) = grundy c n) : ∀ n, n₀ ≤ n → grundy c (n + p) = grundy c n := by sorry