AFTD Auto-Formalizing Theoretical Domains

hunger_transient_polynomial_bound_of_mem_basin

theoremverified

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.

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

    lines 7–8

    uses hunger_transient_time_eq_zero_of_mem_basin, Nat.cast_zero, one_mul, pow_one

      rw [hunger_transient_time_eq_zero_of_mem_basin P T h h_mem]
      simp only [Nat.cast_zero, one_mul, pow_one]
  2. 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`.

    lines 9–13

    uses Finset.le_fold_max, le_rfl

      have h_norm : 0 ≤ hunger_max_norm h := by
        dsimp [hunger_max_norm]
        rw [Finset.le_fold_max]
        left
        exact le_rfl
  3. 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.

    lines 14–17

    uses Nat.cast_nonneg

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

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