AFTD Auto-Formalizing Theoretical Domains

real_hunger_coalescence_persists

theoremverified

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.

  1. 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.

    lines 3–4

    uses hunger_iter, add_comm, Function.iterate_add_apply

      intro k
      rw [hunger_iter, hunger_iter, add_comm t k, Function.iterate_add_apply, Function.iterate_add_apply]
  2. 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).

    line 5

    uses congr_arg

      exact 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

/-- 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
See it in the graphDiscuss this resultChallenge it