prioritized_borel_threshold_reset_frequently
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.
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.
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
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.
intro N by_contra h push_neg at h
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).
uses
if_poshave 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
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)).
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
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.
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
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.
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