asymptotics_isLittleO_of_pos_neg
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$.
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$.
uses
congr_leftrefine (hpos.sub hneg).congr_left ?_ intro n
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.
uses
le_total,max_eq_right,max_eq_left,neg_nonpos.mprrcases le_total 0 (f n) with h | h · rw [max_eq_right h, max_eq_left (neg_nonpos.mpr h)] ring
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.
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
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.
/-- 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