AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_threshold_maximum_even_frequently

theoremverified

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

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.

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

    lines 7–9

      intro K
      by_contra h
      push_neg at h
  2. 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.

    lines 10–12

    uses le_trans, le_max_left, le_max_right

      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
  3. 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.

    lines 13–15

      have hmn : I ≤ m n := by
        have := h n hnK hfn
        omega
  4. 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.

    lines 16–18

    uses if_neg

      have hreset : m (n+1) = 0 := by
        rw [hstep, if_neg]
        omega
  5. 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.

    lines 19–36

    uses Nat.add_assoc

      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
  6. 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.

    lines 37–43

      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

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