User:Barto/Asymptotic Notation

Every reference I know is a bit fuzzy about asymptotic notations. (And it's a good thing they are - look how tedious it is to define them properly and in full generality!) However, if there is one place where they should be defined properly, it surely is ProofWiki.

There's nothing really difficult about it. It's just a lot of work.

Contributing:

Everyone is welcome to change the draft definitions I gave here. Also, feel free to discuss them on the talk page of this project.

WARNING

The definitions on this project pages' subpages may not be up-to-date. In fact, most likely they're not. If you want to edit them, replace them by the definition on proofwiki (depending on which phase we're in; see below) before editing. Beware: differences may be almost unnoticeable, so it's safest to copy them anyway.

Difficulties:

• Asymptotic notations are used in different spaces: $\N\to\R$, $\N\to\C$, $\R\to\R$, $\R\to\C$, $\C\to\C$, Banach $\to$ Banach or more generally topological $\to$ normed. Evidently, all of these are special cases of the last. Does this mean we only need one definition? Surely not. ProofWiki has to be understandable, and we do not expect from someone doing their first asymptotic estimates in e.g. Definition:Analytic Number Theory to read the definition of a normed vector space to proceed.

• Asymptotic notations are used in different contexts: there are point estimates (e.g. occurring in series expansions) as well as estimates at infinity. Here, $\infty$ (seemingly) has a different meaning depending on the space: in the real case, it is usually interpreted as $+\infty$, whereas in other spaces it is commonly interpreted as in Alexandroff Extension, where neighborhoods of $\infty$ are the complements of closed compact sets.

• There are definitions using $\lim$ or $\limsup$, which apply to cases where we're in a field and if things are nonzero. They can be mentioned in the definition page, but I'd rather treat them as corollaries instead of definitions.

• Domains of validity. Sometimes we say an estimate is valid in a certain domain only. (In complex analysis: typically half planes, infinite rectangles, angular regions.)

• Parameter-dependent estimates. Sometimes, the functions or domains of validity involved depend on a parameter, in which case the implied constants and implied neighborhoods may depend on that parameter. You may say we should not use them because they're difficult to define properly. I say we should provide the formal framework to allow them to be used.

• When it comes to proving properties of $O$ and $o$, such as transitivity of $O$ estimates (or less innocent basic properties such as substitution or going from non-uniform to uniform $O$-estimates), all these different factors (source space, target space, estimate at point or infinity, parameter-dependence and domains of validity) make it cumbersome to prove them and organize the proof pages. This is the main motivation to try to find a general framework, in order to avoid essentially proving things twice.

• $O$ estimates frequently occur at both sides of an equation. Example: $x + \map \OO {\log x} = \log x + \map \OO x$. Some resolve this by defining $\map \OO f$ as a set of functions and treating equations with $O$-estimates as inclusions of sets. An other framework consists of treating such equations as sentences with quantifiers. Example: for any $f = \map \OO {\log x}$, there exists $g = \map \OO x$ such that $x + f = \log x + \map \OO g$. In any case, the $=$-sign becomes non-symmetric. That is, equations have to be read left-to-right. $\OO$-estimates (or other ones) may appear inside formulas in a more nested way. Example: $\map f z = \map \OO {e^{\map {\OO_\epsilon} {z^{1 + \epsilon} } } }$ ($f$ is an entire function of order $1$). However this issue seems to be of a less severe nature.

Plan

• [Completed] Phase 1: Big O in its simplest form. Of all asymptotic notations, Big-O is undoubtedly the simplest to define, so it is natural to start with this. To do list:
  • Big-O for sequences. This is the easiest of all. For $\R$, $\C$ and general. (no parameter)
  • Big-O for point estimates in the general case. (no parameter)
  • Neighborhoods of infinity in the general case.
  • Big-O at $\infty$ in the general case. (no parameter)
  • Big-O for real (two-sided only) and complex point estimates.
  • neighborhoods of infinity for $\C$.
  • Big-O at $\infty$ for $\C$.
  • Discuss neighborhoods of $+\infty$, $-\infty$ and $\pm\infty$ in $\R$.
  • Big-O at $+\infty$ and $-\infty$ for $\R$.

• Phase 2: Little O in its simplest form. Once the basic framework for Big-O has been created, it should not be hard to adapt this for little-o., by simply quantifying over the implied constant.

• Phase 3: Basic properties. Transitivity, substitution, sum and product. Perhaps integration. Define Asymptotic equivalence.

Structuring the Definitions

I think it may be better to create separate pages (subpages) collecting the notations for real numbers, complex numbers, and the general case. Reasons include:

• There are terribly many definitions (see the list of difficulties above), so transcluding all of them will make for a very cluttered definition page.
• A computer scientist, or someone who is just studying Taylor-expansions of real functions, won't be interested in the notation for complex numbers, let alone the general case. Similarly, someone who is new to analytic number theory does not need to know about the definitions in complex analysis. They will serve them later, but not now.
• Some remarks and alternative definitions only apply to real functions or complex functions

The following main question remains: should all notations be subpages of one "Asymptotic Notation" page? If not, do we separate them based in the notation ($o, \OO, \sim, \asymp$) or context (real, complex, general)?

Links to definitions at ProofWiki

Big-$\OO$

Little-$\oo$

Asymptotic Equivalence: $\sim$

Big Omega: $\Omega$

Little Omega: $\omega$

Theta: $\Theta$

List of definitions by notation

Little-$\oo$

Sketchy definition: $\forall\epsilon>0 : |f|\leq\epsilon|g|$ in a certain punctured neighborhood $U_\epsilon$.

In case of field and if $g\neq0$ in a certain domain: equivalent to $\lim f/g=0$ ($\iff \lim|f/g|=0$)

Asymptotic Equivalence: $\sim$

Sketchy definition: $f\sim g\iff f-g=o(g)$. (Provably equivalent to $f-g=o(f)$.)

In case of field and if $g\neq0$ in a certain domain: equivalent to $f/g\to0$ (With appropriate definition of the limit in case of $\infty$.)

Order of Magnitude: $\asymp$

Definition: $f = \map \OO g$ and $g = \map \OO f$

Other notations: $\ll$ $\gg$ $\Omega$ $\omega$ $\Theta$ $\theta$

Vinogradov's $\ll$ and $\gg$, $\asymp$, $\Omega$, $\omega$, $\Theta$, $\theta$

List of definitions by context

General Cases

Functions from a topological space to a normed vector space.

Sources

A.J. Hildebrand: Introduction to Analytic Number Theory Lecture Notes, Math 531 (pp. 42 – 44) $\S$ $2.1$