Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 12 — exponential steps in the game with numbers

Proved
PolyTimeMBLG.Monotone.lemma_12

by mikedeng1 · Nov 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatorial-gamesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-argument

Consider 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 111, giving the intermediate board, after which a nonempty sub-multiset is erased and any number of zeros is added.

Let k≥1k\ge1k≥1. In every play, if the number kkk is on the intermediate board ItI_tIt​ of step ttt (right after the increment of step ttt, before the erasure), then

t ≥ 2k−1.t\ \ge\ 2^{k-1}.t ≥ 2k−1.

In particular, the minimal number of steps for the number kkk to appear on the board is at least 2k−12^{k-1}2k−1.

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 2n2^n2n crucial moments; the lemma therefore shows that no word is output at crucial moments more than n+1n+1n+1 times.

Formalization Note The source calls the board value nnn; here it is kkk, to keep nnn for the word length. Any k≥1k\ge1k≥1 on a board BtB_tBt​ after step ttt is also on ItI_tIt​ (the zeros added are not kkk), so the statement covers appearance on the boards as well. The play has an arbitrary finite number TTT of steps and 1≤t≤T1\le t\le T1≤t≤T.

Differences from the source:

  • reading: "the minimal number of steps for a number n to appear on the board" → every occurrence of k≥1k\ge1k≥1 on the intermediate board ItI_tIt​ of step ttt (after the increment, before the erasure) forces t≥2k−1t\ge2^{k-1}t≥2k−1; 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 k≥1k\ge1k≥1 on the board after step ttt is also on ItI_tIt​, and it is the reading the proof's coin argument supports.
Preamble
import Mathlib
import Definitions.Def_PolyTimeMBLG_Monotone_NumberGame
Formal statement
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
Source
Héctor Jimenez, Alexander Kozachinskiy, Vicente Opazo, STOC 2027 submission #402 (October 2026), Lemma 12, p. 8 (the game with numbers is defined just before it on p. 8). PDF SHA-256 2e6ec485290626cb762f55f7c45588eeb0047572a27748b20af18d34ebad7511
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me