hunger_transient_polynomial_bound_of_mem_basin
For a natural number n with [NeZero n], a rational matrix P : Matrix (Fin n) (Fin n) ℚ, a natural number T, and a rational vector h : Fin n → ℚ, if h belongs to hunger_recurrent_basin P T, then (hunger_transient_time P T h : ℚ) ≤ (1 : ℚ) * ((n : ℚ) + (T : ℚ) + hunger_max_norm h + (rational_matrix_max_denominator P : ℚ)) ^ 1.
Statement
theorem hunger_transient_polynomial_bound_of_mem_basin {n : ℕ} [NeZero n]
(P : Matrix (Fin n) (Fin n) ℚ) (T : ℕ) (h : Fin n → ℚ)
(h_mem : h ∈ hunger_recurrent_basin P T) :
(hunger_transient_time P T h : ℚ) ≤
(1 : ℚ) * ((n : ℚ) + (T : ℚ) + hunger_max_norm h + (rational_matrix_max_denominator P : ℚ)) ^ 1- Source
- arXiv:2610.08949 after Thm 3.8
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- hunger_transient_timeFor a natural number n with [NeZero n], a rational matrix P : Matrix (Fin n) (Fin n) ℚ, a natural number T, and a rational vector h : Fin…
- hunger_transient_time_eq_zero_of_mem_basinFor a natural number n with [NeZero n], a rational matrix P : Matrix (Fin n) (Fin n) ℚ, a natural number T, and a rational vector h : Fin…
- rational_matrix_max_denominatorFor a natural number n and a rational matrix P : Matrix (Fin n) (Fin n) ℚ, rational_matrix_max_denominator P is the maximum of 1 and all…
- hunger_recurrent_basinFor n : ℕ with [NeZero n], a linearly ordered additive group K with one, a matrix P : Matrix (Fin n) (Fin n) K, and a natural number T,…
- hunger_max_normThe maximum absolute value of coordinates of a rational hunger vector h.
Read back from the Lean
For any natural number $n$ with $n \ne 0$ ([NeZero n]), any $n \times n$ rational matrix $P$, any natural number $T$, and any rational vector $h : \text{Fin } n \to \mathbb{Q}$:
If $h$ belongs to the recurrent basin of period $T$ under $P$ (i.e., h ∈ hunger_recurrent_basin P T),
then the transient time hunger_transient_time P T h (cast to $\mathbb{Q}$) is less than or equal to:
$$1 \cdot (n + T + \text{hunger\_max\_norm}(h) + \text{rational\_matrix\_max\_denominator}(P))^1$$
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
When a hunger vector $h$ already belongs to the recurrent basin, its transient time is zero by definition. The polynomial bound then reduces to showing that zero is at most $(n + T + \|h\|_\infty + \operatorname{denom}(P))$, which holds immediately because each of the four summands is non-negative.
The inequality reduces to showing that $0 \\le n + T + \\|h\\|_\\infty + \\operatorname{denom}(P)$.
Since the vector $h$ is assumed to belong to the recurrent basin, its transient time is zero by `hunger_transient_time_eq_zero_of_mem_basin`. Simplifying the left-hand side ($0$ cast to $\\mathbb{Q}$) and the right-hand side ($1 \\cdot X^1 = X$) leaves the goal of showing that the sum $n + T + \\|h\\|_\\infty + \\operatorname{denom}(P)$ is non-negative.
uses
hunger_transient_time_eq_zero_of_mem_basin,Nat.cast_zero,one_mul,pow_onerw [hunger_transient_time_eq_zero_of_mem_basin P T h h_mem] simp only [Nat.cast_zero, one_mul, pow_one]
The max-norm of $h$ is non-negative: $0 \\le \\operatorname{hunger\\_max\\_norm}(h)$.
Unfolding the definition, the max-norm is the maximum over all coordinates of $|h(i)|$, folded with an initial value of $0$. By `Finset.le_fold_max`, $0$ is bounded below by this fold if $0 \\le 0$, which holds reflexively by `le_rfl`.
uses
Finset.le_fold_max,le_rflhave h_norm : 0 ≤ hunger_max_norm h := by dsimp [hunger_max_norm] rw [Finset.le_fold_max] left exact le_rfl
The overall sum is non-negative, completing the inequality.
The dimensions and parameters $n$, $T$, and the maximum denominator of $P$ are all natural numbers, so their coercions to $\\mathbb{Q}$ are non-negative by `Nat.cast_nonneg`. Since every term in the sum is non-negative, linear arithmetic (`linarith`) closes the goal.
uses
Nat.cast_nonneghave : 0 ≤ (n : ℚ) := Nat.cast_nonneg n have : 0 ≤ (T : ℚ) := Nat.cast_nonneg T have : 0 ≤ (rational_matrix_max_denominator P : ℚ) := Nat.cast_nonneg _ linarith
hunger_transient_time_eq_zero_of_mem_basin- A hunger vector already in the recurrent basin has transient time 0.
Nat.cast_zero- The coercion of the natural number 0 into a ring is 0.
one_mul- Multiplying an element by 1 on the left leaves it unchanged ($1 \\cdot a = a$).
pow_one- Raising an element to the first power leaves it unchanged ($a^1 = a$).
Finset.le_fold_max- A value $c$ is less than or equal to the fold of $\\max$ starting at $b$ over a finite set $s$ if and only if $c \\le b$ or $c \\le f(x)$ for some $x \\in s$.
le_rfl- The preorder relation $\\le$ is reflexive ($a \\le a$).
Nat.cast_nonneg- The coercion of any natural number into an ordered semiring is non-negative ($0 \\le n$).
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.
/-- The polynomial bound holds with C=1, d=1 for hunger vectors already in the recurrent basin. -/theorem hunger_transient_polynomial_bound_of_mem_basin {n : ℕ} [NeZero n] (P : Matrix (Fin n) (Fin n) ℚ) (T : ℕ) (h : Fin n → ℚ) (h_mem : h ∈ hunger_recurrent_basin P T) : (hunger_transient_time P T h : ℚ) ≤ (1 : ℚ) * ((n : ℚ) + (T : ℚ) + hunger_max_norm h + (rational_matrix_max_denominator P : ℚ)) ^ 1 := by rw [hunger_transient_time_eq_zero_of_mem_basin P T h h_mem] simp only [Nat.cast_zero, one_mul, pow_one] have h_norm : 0 ≤ hunger_max_norm h := by dsimp [hunger_max_norm] rw [Finset.le_fold_max] left exact le_rfl have : 0 ≤ (n : ℚ) := Nat.cast_nonneg n have : 0 ≤ (T : ℚ) := Nat.cast_nonneg T have : 0 ≤ (rational_matrix_max_denominator P : ℚ) := Nat.cast_nonneg _ linarith