Lemma 12 — exponential steps in the game with numbers
ProvedPolyTimeMBLG.Monotone.lemma_12Consider the game with numbers: the board is a finite multiset of natural numbers that initially holds any number of zeros; in each step one occurrence of the minimum of the (nonempty) board is increased by , giving the intermediate board, after which a nonempty sub-multiset is erased and any number of zeros is added.
Let . In every play, if the number is on the intermediate board of step (right after the increment of step , before the erasure), then
In particular, the minimal number of steps for the number to appear on the board is at least .
In the proof of Theorem 11 the board holds the numbers of times each maximal unmarked word has been output at crucial moments, and there are at most crucial moments; the lemma therefore shows that no word is output at crucial moments more than times.
Formalization Note The source calls the board value ; here it is , to keep for the word length. Any on a board after step is also on (the zeros added are not ), so the statement covers appearance on the boards as well. The play has an arbitrary finite number of steps and .
Differences from the source:
- reading: "the minimal number of steps for a number n to appear on the board" → every occurrence of on the intermediate board of step (after the increment, before the erasure) forces ; reason: the source does not fix the moment within a step at which a number "appears"; the intermediate board is the stronger reading, because every on the board after step is also on , and it is the reading the proof's coin argument supports.
import Mathlib import Definitions.Def_PolyTimeMBLG_Monotone_NumberGame
namespace PolyTimeMBLG.Monotone
/-- Lemma 12 (p. 8): if a number `k ≥ 1` is on the board right after the increment of step `t`
of a legal play (before the erasure), then `t ≥ 2^(k-1)`. -/
theorem lemma_12 (T : ℕ) (board inter : ℕ → Multiset ℕ) (hplay : IsPlay T board inter)
(k t : ℕ) (hk : 1 ≤ k) (ht : 1 ≤ t) (htT : t ≤ T) (hkt : k ∈ inter t) :
2 ^ (k - 1) ≤ t := by sorry
end PolyTimeMBLG.Monotone
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.