prioritized_borel_threshold_maximum_even_frequently
If a positive index I occurs arbitrarily late and all sufficiently late inputs are at most I, then under the threshold update there are arbitrarily late occurrences of I at which the memory is below I.
Statement
theorem prioritized_borel_threshold_maximum_even_frequently (f m : ℕ → ℕ) (I N0 : ℕ) (hI : 0 < I) (hmax : ∀ n, N0 ≤ n → f n ≤ I) (hinf : ∀ N, ∃ n ≥ N, f n = I) (hstep : ∀ n, m (n+1) = if m n < f n then f n else 0) : ∀ K, ∃ n ≥ K, f n = I ∧ m n < I
- 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- Used by 1
- prioritized_borel_threshold_highest_even_frequentlyFor any positive bounded input sequence and threshold-memory update, the largest recurrent input occurs arbitrarily late when memory is…
The proof, explained
We proceed by contradiction: assuming no such occurrence exists past K, every occurrence of f(n) = I with n ≥ K must have memory m(n) ≥ I. Picking an occurrence n ≥ max(K, N0), the condition m(n) < f(n) fails, forcing the memory to reset to m(n + 1) = 0. By induction, the memory then remains strictly below I at all subsequent steps, because inputs after N0 cannot exceed I and any input equal to I would violate the contradiction assumption. Finally, choosing another occurrence of I at some n2 ≥ n + 1 reveals that m(n2) < I, which contradicts the assumption that m(n2) ≥ I.
Assume for contradiction that for every n ≥ K with f(n) = I, the memory satisfies m(n) ≥ I.
We fix an arbitrary index K and assume the negation of the conclusion. Pushing the negation inward gives the hypothesis that for every n ≥ K, whenever f(n) = I, the memory cannot be strictly less than I, and so m(n) ≥ I.
intro K by_contra h push_neg at h
There exists an index n such that n ≥ K, n ≥ N0, and f(n) = I.
Since f attains the value I arbitrarily late, we choose an index n ≥ max(K, N0) with f(n) = I. Applying transitivity with the basic inequalities for the maximum yields n ≥ K and n ≥ N0.
uses
le_trans,le_max_left,le_max_rightobtain ⟨n, hn, hfn⟩ := hinf (max K N0) have hnK : K ≤ n := le_trans (le_max_left ..) hn have hnN : N0 ≤ n := le_trans (le_max_right ..) hn
At this index n, the memory satisfies m(n) ≥ I.
Specializing the contradiction assumption to n, which is valid because n ≥ K and f(n) = I, immediately forces m(n) ≥ I.
have hmn : I ≤ m n := by have := h n hnK hfn omega
The memory resets at the next step: m(n + 1) = 0.
According to the update rule, m(n + 1) equals f(n) if m(n) < f(n), and 0 otherwise. Since m(n) ≥ I = f(n), the strict inequality m(n) < f(n) does not hold, so the conditional evaluates to 0.
uses
if_neghave hreset : m (n+1) = 0 := by rw [hstep, if_neg] omega
For all j ≥ 0, the memory remains strictly below I: m(n + 1 + j) < I.
We prove this by induction on j. For the base case j = 0, m(n + 1) = 0 < I because the memory just reset to 0 and I > 0. For the inductive step, assume m(n + 1 + j) < I. Because n + 1 + j ≥ K and the memory is below I, the contradiction hypothesis implies that f(n + 1 + j) cannot equal I. Since n + 1 + j ≥ N0, the input is at most I, so it must be strictly less than I: f(n + 1 + j) < I. By the update rule, m(n + 1 + j + 1) either takes the value f(n + 1 + j) (if m(n + 1 + j) < f(n + 1 + j)) or resets to 0; both outcomes are strictly less than I, which completes the induction.
uses
Nat.add_assochave hind : ∀ j, m (n+1+j) < I := by intro j induction j with | zero => simpa using (show m (n+1) < I by rw [hreset]; exact hI) | succ j ih => have hk : K ≤ n+1+j := by omega have hn0 : N0 ≤ n+1+j := by omega have hsmall : f (n+1+j) < I := by have hle := hmax (n+1+j) hn0 have hne : f (n+1+j) ≠ I := by intro heq have := h (n+1+j) hk heq omega omega have hnext : m ((n+1+j)+1) < I := by rw [hstep] split_ifs <;> omega simpa [Nat.add_assoc] using hnext
A contradiction is reached, completing the proof.
Since f takes value I infinitely often, there is an occurrence n2 ≥ n + 1 with f(n2) = I. Applying the inductive invariant at j = n2 - (n + 1) shows m(n2) < I. But since n2 ≥ n + 1 > n ≥ K, the contradiction assumption also demands m(n2) ≥ I, which is impossible.
obtain ⟨n2, hn2, hfn2⟩ := hinf (n+1) have hn2K : K ≤ n2 := by omega have hm2 := hind (n2-(n+1)) have heq : n+1+(n2-(n+1)) = n2 := by omega rw [heq] at hm2 have := h n2 hn2K hfn2 omega
le_trans- If a ≤ b and b ≤ c, then a ≤ c (transitivity of order).
le_max_left- For any a and b, a ≤ max(a, b).
le_max_right- For any a and b, b ≤ max(a, b).
if_neg- If a condition c is false, then if c then t else e evaluates to e.
Nat.add_assoc- Addition of natural numbers is associative: (n + m) + k = n + (m + k).
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_maximum_even_frequently (f m : ℕ → ℕ) (I N0 : ℕ) (hI : 0 < I) (hmax : ∀ n, N0 ≤ n → f n ≤ I) (hinf : ∀ N, ∃ n ≥ N, f n = I) (hstep : ∀ n, m (n+1) = if m n < f n then f n else 0) : ∀ K, ∃ n ≥ K, f n = I ∧ m n < I := by intro K by_contra h push_neg at h obtain ⟨n, hn, hfn⟩ := hinf (max K N0) have hnK : K ≤ n := le_trans (le_max_left ..) hn have hnN : N0 ≤ n := le_trans (le_max_right ..) hn have hmn : I ≤ m n := by have := h n hnK hfn omega have hreset : m (n+1) = 0 := by rw [hstep, if_neg] omega have hind : ∀ j, m (n+1+j) < I := by intro j induction j with | zero => simpa using (show m (n+1) < I by rw [hreset]; exact hI) | succ j ih => have hk : K ≤ n+1+j := by omega have hn0 : N0 ≤ n+1+j := by omega have hsmall : f (n+1+j) < I := by have hle := hmax (n+1+j) hn0 have hne : f (n+1+j) ≠ I := by intro heq have := h (n+1+j) hk heq omega omega have hnext : m ((n+1+j)+1) < I := by rw [hstep] split_ifs <;> omega simpa [Nat.add_assoc] using hnext obtain ⟨n2, hn2, hfn2⟩ := hinf (n+1) have hn2K : K ≤ n2 := by omega have hm2 := hind (n2-(n+1)) have heq : n+1+(n2-(n+1)) = n2 := by omega rw [heq] at hm2 have := h n2 hn2K hfn2 omega