AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_threshold_highest_even_frequently

theoremverified

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

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.

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

    line 7

    uses prioritized_borel_highest_recurrent_index

      obtain ⟨I, hIpos, hIbound, hIrec, N0, hmax⟩ := prioritized_borel_highest_recurrent_index s f hf
  2. The 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.

    lines 8–9

    uses prioritized_borel_threshold_maximum_even_frequently

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

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