AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_threshold_reset_frequently

theoremverified

For positive inputs bounded by s and a memory value initially zero that updates to the input when it exceeds memory and resets to zero otherwise, reset steps occur arbitrarily late.

Statement

theorem prioritized_borel_threshold_reset_frequently
    (s : ℕ) (f m : ℕ → ℕ) (hf : ∀ n, 1 ≤ f n ∧ f n ≤ s)
    (hinit : m 0 = 0)
    (hstep : ∀ n, m (n+1) = if m n < f n then f n else 0) :
    ∀ N, ∃ n ≥ N, f n ≤ m n
Source
arXiv:2611.10136, Section 5.3.2, Proposition 41; s+1-state threshold controller for the paper’s lower-bound game.
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof proceeds by contradiction. Memory is shown to always be bounded by s because each update either sets it to an input bounded by s or resets it to 0. If no reset step f n ≤ m n ever occurred past N, the memory would strictly increase at every subsequent step, forcing m (N + s + 1) ≥ s + 1 by induction and contradicting the bound m (N + s + 1) ≤ s.

  1. For all n, the memory value is bounded by s: m n ≤ s.

    We proceed by case analysis on n. At n = 0, m 0 = 0 ≤ s by the initialization hypothesis hinit. For a successor step n + 1, m (n + 1) is defined by hstep to be f n when m n < f n and 0 otherwise. Since f n ≤ s by hypothesis hf, both branches evaluate to at most s.

    lines 6–10

      have hm : ∀ n, m n ≤ s := by
        intro n
        cases n with
        | zero => rw [hinit]; omega
        | succ n => rw [hstep]; split_ifs <;> have := (hf n).2 <;> omega
  2. Assume for contradiction that from index N onward, memory is always strictly less than the input: m n < f n for all n ≥ N.

    Fixing N, we assume the negation of the goal. Pushing the negation through the existential quantifier converts ¬(∃ n ≥ N, f n ≤ m n) into ∀ n ≥ N, m n < f n.

    lines 11–13

      intro N
      by_contra h
      push_neg at h
  3. For every n ≥ N, the memory strictly increases at the next step: m n < m (n + 1).

    For any n ≥ N, the contradiction hypothesis guarantees m n < f n. By the recurrence hstep, the condition of the if-expression holds, so if_pos reduces m (n + 1) to f n. Since m n < f n, it follows that m n < m (n + 1).

    lines 14–18

    uses if_pos

      have hincr : ∀ n, N ≤ n → m n < m (n+1) := by
        intro n hn
        have hn' := h n hn
        rw [hstep, if_pos (by omega)]
        omega
  4. For all j, the memory value after j steps past N is at least j: j ≤ m (N + j).

    We induct on j. The base case j = 0 requires 0 ≤ m N, which holds trivially in ℕ. In the induction step, assuming j ≤ m (N + j), the strict increase property gives m (N + j) < m (N + j + 1). Because these are natural numbers, j + 1 ≤ m (N + j) + 1 ≤ m (N + j + 1) = m (N + (j + 1)).

    lines 19–27

      have hind : ∀ j, j ≤ m (N+j) := by
        intro j
        induction j with
        | zero => omega
        | succ j ih =>
          have hi := hincr (N+j) (by omega)
          have heq : N + (j+1) = (N+j)+1 := by omega
          rw [heq]
          omega
  5. Contradiction: the memory would exceed its upper bound.

    Evaluating the lower bound at j = s + 1 yields s + 1 ≤ m (N + (s + 1)). But the global bound hm evaluated at N + (s + 1) requires m (N + (s + 1)) ≤ s. These two inequalities contradict each other because s + 1 ≤ s is impossible.

    lines 28–30

      have := hind (s+1)
      have := hm (N+(s+1))
      omega
if_pos
If a proposition c is true, the conditional expression (if c then t else e) simplifies to t.

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

theorem prioritized_borel_threshold_reset_frequently    (s : ℕ) (f m : ℕ → ℕ) (hf : ∀ n, 1 ≤ f n ∧ f n ≤ s)    (hinit : m 0 = 0)    (hstep : ∀ n, m (n+1) = if m n < f n then f n else 0) :    ∀ N, ∃ n ≥ N, f n ≤ m n := by  have hm : ∀ n, m n ≤ s := by    intro n    cases n with    | zero => rw [hinit]; omega    | succ n => rw [hstep]; split_ifs <;> have := (hf n).2 <;> omega  intro N  by_contra h  push_neg at h  have hincr : ∀ n, N ≤ n → m n < m (n+1) := by    intro n hn    have hn' := h n hn    rw [hstep, if_pos (by omega)]    omega  have hind : ∀ j, j ≤ m (N+j) := by    intro j    induction j with    | zero => omega    | succ j ih =>      have hi := hincr (N+j) (by omega)      have heq : N + (j+1) = (N+j)+1 := by omega      rw [heq]      omega  have := hind (s+1)  have := hm (N+(s+1))  omega
See it in the graphDiscuss this resultChallenge it