# mathlibdocumentation

analysis.asymptotics.superpolynomial_decay

# Super-Polynomial Function Decay #

This file defines a predicate asymptotics.superpolynomial_decay f for a function satisfying one of following equivalent definitions (The definition is in terms of the first condition):

• x ^ n * f tends to 𝓝 0 for all (or sufficiently large) naturals n
• |x ^ n * f| tends to 𝓝 0 for all naturals n (superpolynomial_decay_iff_abs_tendsto_zero)
• |x ^ n * f| is bounded for all naturals n (superpolynomial_decay_iff_abs_is_bounded_under)
• f is o(x ^ c) for all integers c (superpolynomial_decay_iff_is_o)
• f is O(x ^ c) for all integers c (superpolynomial_decay_iff_is_O)

These conditions are all equivalent to conditions in terms of polynomials, replacing x ^ c with p(x) or p(x)⁻¹ as appropriate, since asymptotically p(x) behaves like X ^ p.nat_degree. These further equivalences are not proven in mathlib but would be good future projects.

The definition of superpolynomial decay for f : α → β is relative to a parameter k : α → β. Super-polynomial decay then means f x decays faster than (k x) ^ c for all integers c. Equivalently f x decays faster than p.eval (k x) for all polynomials p : polynomial β. The definition is also relative to a filter l : filter α where the decay rate is compared.

When the map k is given by n ↦ ↑n : ℕ → ℝ this defines negligible functions: https://en.wikipedia.org/wiki/Negligible_function

When the map k is given by (r₁,...,rₙ) ↦ r₁*...*rₙ : ℝⁿ → ℝ this is equivalent to the definition of rapidly decreasing functions given here: https://ncatlab.org/nlab/show/rapidly+decreasing+function

# Main Theorems #

• superpolynomial_decay.polynomial_mul says that if f(x) is negligible, then so is p(x) * f(x) for any polynomial p.
• superpolynomial_decay_iff_zpow_tendsto_zero gives an equivalence between definitions in terms of decaying faster than k(x) ^ n for all naturals n or k(x) ^ c for all integer c.
def asymptotics.superpolynomial_decay {α : Type u_1} {β : Type u_2} (l : filter α) (k f : α → β) :
Prop

f has superpolynomial decay in parameter k along filter l if k ^ n * f tends to zero at l for all naturals n

Equations
theorem asymptotics.superpolynomial_decay.congr' {α : Type u_1} {β : Type u_2} {l : filter α} {k f g : α → β} (hf : f) (hfg : f =ᶠ[l] g) :
theorem asymptotics.superpolynomial_decay.congr {α : Type u_1} {β : Type u_2} {l : filter α} {k f g : α → β} (hf : f) (hfg : ∀ (x : α), f x = g x) :
@[simp]
theorem asymptotics.superpolynomial_decay_zero {α : Type u_1} {β : Type u_2} (l : filter α) (k : α → β) :
theorem asymptotics.superpolynomial_decay.add {α : Type u_1} {β : Type u_2} {l : filter α} {k f g : α → β} (hf : f) (hg : g) :
(f + g)
theorem asymptotics.superpolynomial_decay.mul {α : Type u_1} {β : Type u_2} {l : filter α} {k f g : α → β} (hf : f) (hg : g) :
(f * g)
theorem asymptotics.superpolynomial_decay.mul_const {α : Type u_1} {β : Type u_2} {l : filter α} {k f : α → β} (hf : f) (c : β) :
(λ (n : α), f n * c)
theorem asymptotics.superpolynomial_decay.const_mul {α : Type u_1} {β : Type u_2} {l : filter α} {k f : α → β} (hf : f) (c : β) :
(λ (n : α), c * f n)
theorem asymptotics.superpolynomial_decay.param_mul {α : Type u_1} {β : Type u_2} {l : filter α} {k f : α → β} (hf : f) :
(k * f)
theorem asymptotics.superpolynomial_decay.mul_param {α : Type u_1} {β : Type u_2} {l : filter α} {k f : α → β} (hf : f) :
(f * k)
theorem asymptotics.superpolynomial_decay.param_pow_mul {α : Type u_1} {β : Type u_2} {l : filter α} {k f : α → β} (hf : f) (n : ) :
(k ^ n * f)
theorem asymptotics.superpolynomial_decay.mul_param_pow {α : Type u_1} {β : Type u_2} {l : filter α} {k f : α → β} (hf : f) (n : ) :
(f * k ^ n)
theorem asymptotics.superpolynomial_decay.polynomial_mul {α : Type u_1} {β : Type u_2} {l : filter α} {k f : α → β} (hf : f) (p : polynomial β) :
(λ (x : α), polynomial.eval (k x) p * f x)
theorem asymptotics.superpolynomial_decay.mul_polynomial {α : Type u_1} {β : Type u_2} {l : filter α} {k f : α → β} (hf : f) (p : polynomial β) :
(λ (x : α), f x * polynomial.eval (k x) p)
theorem asymptotics.superpolynomial_decay.trans_eventually_le {α : Type u_1} {β : Type u_2} {l : filter α} {k f g g' : α → β} (hk : 0 ≤ᶠ[l] k) (hg : g) (hg' : g') (hfg : g ≤ᶠ[l] f) (hfg' : f ≤ᶠ[l] g') :
theorem asymptotics.superpolynomial_decay_iff_abs_tendsto_zero {α : Type u_1} {β : Type u_2} (l : filter α) (k f : α → β)  :
∀ (n : ), filter.tendsto (λ (a : α), |k a ^ n * f a|) l (nhds 0)
theorem asymptotics.superpolynomial_decay_iff_superpolynomial_decay_abs {α : Type u_1} {β : Type u_2} (l : filter α) (k f : α → β)  :
(λ (a : α), |k a|) (λ (a : α), |f a|)
theorem asymptotics.superpolynomial_decay.trans_eventually_abs_le {α : Type u_1} {β : Type u_2} {l : filter α} {k f g : α → β} (hf : f) (hfg : ≤ᶠ[l] ) :
theorem asymptotics.superpolynomial_decay.trans_abs_le {α : Type u_1} {β : Type u_2} {l : filter α} {k f g : α → β} (hf : f) (hfg : ∀ (x : α), |g x| |f x|) :
theorem asymptotics.superpolynomial_decay_mul_const_iff {α : Type u_1} {β : Type u_2} (l : filter α) (k f : α → β) [field β] {c : β} (hc0 : c 0) :
(λ (n : α), f n * c)
theorem asymptotics.superpolynomial_decay_const_mul_iff {α : Type u_1} {β : Type u_2} (l : filter α) (k f : α → β) [field β] {c : β} (hc0 : c 0) :
(λ (n : α), c * f n)
theorem asymptotics.superpolynomial_decay_iff_abs_is_bounded_under {α : Type u_1} {β : Type u_2} {l : filter α} {k : α → β} (f : α → β) (hk : filter.at_top) :
∀ (z : ), (λ (a : α), |k a ^ z * f a|)
theorem asymptotics.superpolynomial_decay_iff_zpow_tendsto_zero {α : Type u_1} {β : Type u_2} {l : filter α} {k : α → β} (f : α → β) (hk : filter.at_top) :
∀ (z : ), filter.tendsto (λ (a : α), k a ^ z * f a) l (nhds 0)
theorem asymptotics.superpolynomial_decay.param_zpow_mul {α : Type u_1} {β : Type u_2} {l : filter α} {k f : α → β} (hk : filter.at_top) (hf : f) (z : ) :
(λ (a : α), k a ^ z * f a)
theorem asymptotics.superpolynomial_decay.mul_param_zpow {α : Type u_1} {β : Type u_2} {l : filter α} {k f : α → β} (hk : filter.at_top) (hf : f) (z : ) :
(λ (a : α), f a * k a ^ z)
theorem asymptotics.superpolynomial_decay.inv_param_mul {α : Type u_1} {β : Type u_2} {l : filter α} {k f : α → β} (hk : filter.at_top) (hf : f) :
(k⁻¹ * f)
theorem asymptotics.superpolynomial_decay.param_inv_mul {α : Type u_1} {β : Type u_2} {l : filter α} {k f : α → β} (hk : filter.at_top) (hf : f) :
(f * k⁻¹)
theorem asymptotics.superpolynomial_decay_param_mul_iff {α : Type u_1} {β : Type u_2} {l : filter α} {k : α → β} (f : α → β) (hk : filter.at_top) :
(k * f)
theorem asymptotics.superpolynomial_decay_mul_param_iff {α : Type u_1} {β : Type u_2} {l : filter α} {k : α → β} (f : α → β) (hk : filter.at_top) :
(f * k)
theorem asymptotics.superpolynomial_decay_param_pow_mul_iff {α : Type u_1} {β : Type u_2} {l : filter α} {k : α → β} (f : α → β) (hk : filter.at_top) (n : ) :
(k ^ n * f)
theorem asymptotics.superpolynomial_decay_mul_param_pow_iff {α : Type u_1} {β : Type u_2} {l : filter α} {k : α → β} (f : α → β) (hk : filter.at_top) (n : ) :
(f * k ^ n)
theorem asymptotics.superpolynomial_decay_iff_norm_tendsto_zero {α : Type u_1} {β : Type u_2} (l : filter α) (k f : α → β)  :
∀ (n : ), filter.tendsto (λ (a : α), k a ^ n * f a) l (nhds 0)
theorem asymptotics.superpolynomial_decay_iff_superpolynomial_decay_norm {α : Type u_1} {β : Type u_2} (l : filter α) (k f : α → β)  :
(λ (a : α), k a) (λ (a : α), f a)
theorem asymptotics.superpolynomial_decay_iff_is_O {α : Type u_1} {β : Type u_2} {l : filter α} {k : α → β} (f : α → β) (hk : filter.at_top) :
∀ (z : ), f =O[l] λ (a : α), k a ^ z
theorem asymptotics.superpolynomial_decay_iff_is_o {α : Type u_1} {β : Type u_2} {l : filter α} {k : α → β} (f : α → β) (hk : filter.at_top) :
∀ (z : ), f =o[l] λ (a : α), k a ^ z