prioritized_borel_threshold_highest_even_frequently
For any positive bounded input sequence and threshold-memory update, the largest recurrent input occurs arbitrarily late when memory is smaller, and no larger input occurs after some point.
Statement
theorem prioritized_borel_threshold_highest_even_frequently (s : ℕ) (f m : ℕ → ℕ) (hf : ∀ n, 1 ≤ f n ∧ f n ≤ s) (hstep : ∀ n, m (n+1) = if m n < f n then f n else 0) : ∃ I, 0 < I ∧ I ≤ s ∧ (∀ N, ∃ n ≥ N, f n = I) ∧ (∃ N0, ∀ n, N0 ≤ n → f n ≤ I) ∧ (∀ K, ∃ n ≥ K, f n = I ∧ m n < I)
- Source
- arXiv:2611.10136, Section 5.3.2, Proposition 41; threshold controller for the lower-bound example
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- prioritized_borel_highest_recurrent_indexEvery infinite sequence of positive natural numbers bounded by s has a positive largest recurrent value I, and all sufficiently late…
- prioritized_borel_threshold_maximum_even_frequentlyIf a positive index I occurs arbitrarily late and all sufficiently late inputs are at most I, then under the threshold update there are…
The proof, explained
The proof combines two existing results. First, `prioritized_borel_highest_recurrent_index` yields a maximal recurrent value I ≤ s that f attains infinitely often and above which f never rises after some cutoff N₀. Second, `prioritized_borel_threshold_maximum_even_frequently` guarantees that this maximal recurrent value I also occurs infinitely often at moments when the memory state m(n) is strictly smaller than I.
There exists a maximal recurrent value I ∈ {1, ..., s} and a cutoff N₀ past which f never exceeds I.
Applying `prioritized_borel_highest_recurrent_index` to the bounded sequence f yields a value I satisfying 0 < I ≤ s, which f visits infinitely often, along with a threshold index N₀ such that f(n) ≤ I for all n ≥ N₀.
uses
prioritized_borel_highest_recurrent_indexobtain ⟨I, hIpos, hIbound, hIrec, N0, hmax⟩ := prioritized_borel_highest_recurrent_index s f hfThe value I satisfies all conditions of the theorem, including occurring infinitely often with memory strictly below I.
We instantiate the existential goal with I. The first four properties (0 < I, I ≤ s, recurrence of I, and eventual upper bound at N₀) were obtained directly in the previous step. The final property—that f(n) = I and m(n) < I occurs for arbitrarily large n—is established by applying `prioritized_borel_threshold_maximum_even_frequently` using the recurrence and eventual bound on I.
uses
prioritized_borel_threshold_maximum_even_frequentlyexact ⟨I, hIpos, hIbound, hIrec, ⟨N0, hmax⟩, prioritized_borel_threshold_maximum_even_frequently f m I N0 hIpos hmax hIrec hstep⟩
prioritized_borel_highest_recurrent_index- For any sequence with values in {1, ..., s}, there exists a positive value I ≤ s that appears infinitely often, and a threshold N₀ after which the sequence never exceeds I.
prioritized_borel_threshold_maximum_even_frequently- For a threshold-memory update m(n+1) = if m(n) < f(n) then f(n) else 0, if I > 0 is an eventual upper bound on f and occurs infinitely often, then f(n) = I with m(n) < I occurs infinitely often.
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_highest_even_frequently (s : ℕ) (f m : ℕ → ℕ) (hf : ∀ n, 1 ≤ f n ∧ f n ≤ s) (hstep : ∀ n, m (n+1) = if m n < f n then f n else 0) : ∃ I, 0 < I ∧ I ≤ s ∧ (∀ N, ∃ n ≥ N, f n = I) ∧ (∃ N0, ∀ n, N0 ≤ n → f n ≤ I) ∧ (∀ K, ∃ n ≥ K, f n = I ∧ m n < I) := by obtain ⟨I, hIpos, hIbound, hIrec, N0, hmax⟩ := prioritized_borel_highest_recurrent_index s f hf exact ⟨I, hIpos, hIbound, hIrec, ⟨N0, hmax⟩, prioritized_borel_threshold_maximum_even_frequently f m I N0 hIpos hmax hIrec hstep⟩