AFTD Auto-Formalizing Theoretical Domains

asymptotics_isLittleO_of_pos_neg

theoremverified

If both the positive and negative deviations max(0, f(n)) and max(0, -f(n)) are little-o of g(n) along Filter.atTop, then f(n) = o(g(n)).

Statement

theorem asymptotics_isLittleO_of_pos_neg (f g : ℕ → ℝ)
    (hpos : (fun n => max 0 (f n)) =o[Filter.atTop] g)
    (hneg : (fun n => max 0 (-f n)) =o[Filter.atTop] g) :
    f =o[Filter.atTop] g
Source
step towards mms_threshold_monotone_asymptotic
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof decomposes $f(n)$ into the difference of its non-negative parts, $f(n) = \max(0, f(n)) - \max(0, -f(n))$. Because little-o is closed under subtraction, the hypotheses imply that this difference is $o(g(n))$ along Filter.atTop. The argument then reduces to verifying the algebraic identity $f(n) = \max(0, f(n)) - \max(0, -f(n))$ pointwise, which is established by splitting into the cases $0 \le f(n)$ and $f(n) \le 0$.

  1. To prove $f = o(g)$, it suffices to show that $\max(0, f(n)) - \max(0, -f(n)) = f(n)$ for every $n \in \mathbb{N}$.

    Since both positive and negative parts satisfy $\max(0, f) = o(g)$ and $\max(0, -f) = o(g)$ along Filter.atTop, their difference is also $o(g)$ by subtracting the asymptotic bounds. Asymptotic congruence on the left (`congr_left`) reduces the goal $f = o(g)$ to proving that this difference equals $f$ pointwise, and we fix an arbitrary index $n$.

    lines 6–7

    uses congr_left

      refine (hpos.sub hneg).congr_left ?_
      intro n
  2. The identity $\max(0, f(n)) - \max(0, -f(n)) = f(n)$ holds when $0 \le f(n)$.

    By totality of the ordering on $\mathbb{R}$ (`le_total`), either $0 \le f(n)$ or $f(n) \le 0$. In the first branch where $0 \le f(n)$, the term $\max(0, f(n))$ simplifies to $f(n)$ (`max_eq_right`). Since $0 \le f(n)$ implies $-f(n) \le 0$ (`neg_nonpos.mpr`), the second term $\max(0, -f(n))$ simplifies to $0$ (`max_eq_left`). The expression reduces to $f(n) - 0 = f(n)$, which is closed by ring arithmetic.

    lines 8–10

    uses le_total, max_eq_right, max_eq_left, neg_nonpos.mpr

      rcases le_total 0 (f n) with h | h
      · rw [max_eq_right h, max_eq_left (neg_nonpos.mpr h)]
        ring
  3. The identity $\max(0, f(n)) - \max(0, -f(n)) = f(n)$ holds when $f(n) \le 0$.

    In the remaining branch where $f(n) \le 0$, the first term $\max(0, f(n))$ simplifies to $0$ (`max_eq_left`). Since $f(n) \le 0$ implies $0 \le -f(n)$ (`neg_nonneg.mpr`), the second term $\max(0, -f(n))$ simplifies to $-f(n)$ (`max_eq_right`). The expression reduces to $0 - (-f(n)) = f(n)$, which is closed by ring arithmetic.

    lines 11–12

    uses max_eq_left, max_eq_right, neg_nonneg.mpr

      · rw [max_eq_left h, max_eq_right (neg_nonneg.mpr h)]
        ring
congr_left
If $f_1 = o(g)$ along a filter and $f_1(x) = f_2(x)$ for all $x$, then $f_2 = o(g)$ along that filter.
le_total
For any two elements $a$ and $b$ in a linear order, either $a \le b$ or $b \le a$.
max_eq_right
If $a \le b$, then $\max(a, b) = b$.
max_eq_left
If $b \le a$, then $\max(a, b) = a$.
neg_nonpos.mpr
If $0 \le a$, then $-a \le 0$.
neg_nonneg.mpr
If $a \le 0$, then $0 \le -a$.

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

/-- Real functions f with max 0 f =o[atTop] g and max 0 (-f) =o[atTop] g satisfy f =o[atTop] g. -/theorem asymptotics_isLittleO_of_pos_neg (f g : ℕ → ℝ)    (hpos : (fun n => max 0 (f n)) =o[Filter.atTop] g)    (hneg : (fun n => max 0 (-f n)) =o[Filter.atTop] g) :    f =o[Filter.atTop] g := by  refine (hpos.sub hneg).congr_left ?_  intro n  rcases le_total 0 (f n) with h | h  · rw [max_eq_right h, max_eq_left (neg_nonpos.mpr h)]    ring  · rw [max_eq_left h, max_eq_right (neg_nonneg.mpr h)]    ring
See it in the graphDiscuss this resultChallenge it