real_hunger_coalescence_persists
For any positive natural number n, any n-by-n real matrix P, and any vectors h1, h2 : Fin n → ℝ, if the hunger trajectories from h1 and h2 coalesce at step t, then they remain equal at every step t + k for all k : ℕ.
Statement
theorem real_hunger_coalescence_persists {n : ℕ} [NeZero n] (P : Matrix (Fin n) (Fin n) ℝ) (h1 h2 : Fin n → ℝ) (t : ℕ) (h_coal : hunger_iter P t h1 = hunger_iter P t h2) : ∀ k : ℕ, hunger_iter P (t + k) h1 = hunger_iter P (t + k) h2- Source
- scout/2610-08949-primitive-periods-in-greedy-chip-firing-games.md:111
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- hunger_iterFor n : ℕ with [NeZero n], a linearly ordered additive group K with one, a matrix P : Matrix (Fin n) (Fin n) K, a natural number t, and an…
- hunger_stepFor n : ℕ with [NeZero n], a type K with a linear order, additive group structure, and one, a matrix P : Matrix (Fin n) (Fin n) K, and a…
Read back from the Lean
For any positive natural number $n$, any $n \times n$ real matrix $P$, any two functions $h_1, h_2 : \mathrm{Fin}\ n \to \mathbb{R}$, and any time step $t \in \mathbb{N}$: if the $t$-th iterates of $h_1$ and $h_2$ under hunger_step P are equal (that is, hunger_iter P t h1 = hunger_iter P t h2), then for all $k \in \mathbb{N}$, the $(t + k)$-th iterates of $h_1$ and $h_2$ under hunger_step P are also equal (hunger_iter P (t + k) h1 = hunger_iter P (t + k) h2).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Coalescence of hunger trajectories is absorbing: once two trajectories reach the exact same state at step t, they remain identical at all subsequent steps t + k. By the composition property of function iteration, the state at step t + k is simply the k-th iterate of the deterministic hunger transition applied to the state at step t. Since the two states at step t are equal by assumption, applying the same deterministic transition k times to both yields equal states at step t + k.
For an arbitrary offset k ∈ ℕ, showing equality at step t + k reduces to showing that applying the hunger transition k times to the states at step t yields the same result.
We fix an arbitrary step offset k ∈ ℕ. By the definition of hunger_iter, the hunger trajectory at step t + k is the (t + k)-th iterate of hunger_step P. Using the commutativity of addition (add_comm) to rewrite t + k as k + t, and the composition law for iterated functions (Function.iterate_add_apply), the (k + t)-th iterate decomposes into the k-th iterate of hunger_step P applied to the t-th iterate. Thus, both sides of the goal become the k-th iterate of hunger_step P applied to their respective states at step t.
uses
hunger_iter,add_comm,Function.iterate_add_applyintro k rw [hunger_iter, hunger_iter, add_comm t k, Function.iterate_add_apply, Function.iterate_add_apply]
The hunger trajectories are identical at step t + k.
The coalescence hypothesis h_coal asserts that the two trajectories have identical states at step t. Because the update rule is deterministic, applying the k-th iterate of hunger_step P to both sides of this equality yields identical states at step t + k by function congruence (congr_arg).
uses
congr_argexact congr_arg ((hunger_step P)^[k]) h_coal
hunger_iter- By definition, the hunger trajectory at step t starting from initial state h is the t-th iterate of the single-step operator hunger_step P applied to h: hunger_iter P t h = (hunger_step P)^[t] h.
add_comm- Addition is commutative: a + b = b + a for any two elements in an additive commutative magma (in particular, the natural numbers).
Function.iterate_add_apply- The (m + n)-th iterate of a function f applied to an element x equals the m-th iterate applied to the n-th iterate: f^[m + n] x = f^[m] (f^[n] x).
congr_arg- Equality is preserved under function application: if a₁ = a₂, then f a₁ = f a₂ for any function f.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- If two hunger trajectories coalesce at step t, they remain identical at all subsequent steps t + k. -/theorem real_hunger_coalescence_persists {n : ℕ} [NeZero n] (P : Matrix (Fin n) (Fin n) ℝ) (h1 h2 : Fin n → ℝ) (t : ℕ) (h_coal : hunger_iter P t h1 = hunger_iter P t h2) : ∀ k : ℕ, hunger_iter P (t + k) h1 = hunger_iter P (t + k) h2 := by intro k rw [hunger_iter, hunger_iter, add_comm t k, Function.iterate_add_apply, Function.iterate_add_apply] exact congr_arg ((hunger_step P)^[k]) h_coal