Orders of infinity | What's new

Many problems in analysis (as well as adjacent fields such as combinatorics, theoretical computer science, and PDE) are interested in the order of growth (or decay) of some quantity that depends on one or more asymptotic parameters (such as ${N}$ ) – for instance, whether the quantity ${X}$ grows or decays linearly, quadratically, polynomially, exponentially, etc. in ${N}$ . In the case where these quantities grow to infinity, these growth rates had once been termed “orders of infinity” – for instance, in the 1910 book of this name by Hardy – although this term has fallen out of use in recent years. (Hardy fields are still a thing, though.)

In modern analysis, asymptotic notation is the preferred device to organize orders of infinity. There are a couple of flavors of this notation, but here is one such (a blend of Hardy’s notation and Landau’s notation). Formally, we need a parameter space ${\Omega}$ equipped with a non-principal filter ${{\mathcal F}}$ that describes the subsets of parameter space that are “sufficiently large” (e.g., the cofinite (Fréchet) filter on ${{\bf N}}$ , or the cocompact filter on ${{\bf R}}$ ). We will use ${N}$ to denote elements of this filter; thus, an assertion holds for sufficiently large ${N}$ if and only if it holds for all ${N}$ in some element ${U}$ of the filter ${{\mathcal F}}$ . Given two positive quantities ${X = X(N), Y = Y(N)}$ that are defined for sufficiently large ${N \in \Omega}$ , one can then define the following notions:

We caution that in analytic number theory and adjacent fields, the slightly different notation of Vinogradov is favored, in which ${X \ll Y}$ would denote the concept (i) instead of (ii), and ${X \sim Y}$ would denote a fourth concept ${X = (1+o(1)) Y}$ instead of (iii). However, we will use the Hardy-Landau notation exclusively in this blog post.

Anyone who works with asymptotic notation for a while will quickly recognize that it enjoys various algebraic properties akin to the familiar algebraic properties of order ${<}$ on the real line. For instance, the symbols ${\lesssim, \ll, \gg, \gtrsim}$ behave very much like ${\leq}$ , ${<}$ , ${>}$ , ${\gtrsim}$ , with properties such as the following:

One also has the “tropical” property ${X+Y \asymp \max(X,Y)}$ , making asymptotic notation a kind of “tropical algebra“.

However, in contrast with other standard algebraic structures (such as ordered fields) that blend order and arithmetic operations, the precise laws of orders of infinity are usually not written down as a short list of axioms. Part of this is due to cultural differences between analysis and algebra – as discussed in this essay by Gowers, analysis is often not well suited to the axiomatic approach to mathematics that algebra benefits so much from. But another reason is due to our orthodox implementation of analysis via “epsilon-delta” type concepts, such as the notion of “sufficiently large” used above, which notoriously introduces a large number of both universal and existential quantifiers into the subject (for every epsilon, there exists a delta…) which tends to interfere with the smooth application of algebraic laws (which are optimized for the universal quantifier rather than the existential quantifier).

But there is an alternate approach to analysis, namely nonstandard analysis, which rearranges the foundations so that many of quantifiers (particularly the existential ones) are concealed from view (usually via the device of ultrafilters). This makes the subject of analysis considerably more “algebraic” in nature, as the “epsilon management” that is so prevalent in orthodox analysis is now performed much more invisibly. For instance, as we shall see, in the nonstandard framework, orders of infinity acquire the algebraic structure of a totally ordered vector space that also enjoys a completeness property reminiscent, though not identical to, the completeness of the real numbers. There is also a transfer principle that allows one to convert assertions in orthodox asymptotic notation into logically equivalent assertions about nonstandard orders of infinity, allowing one to then prove asymptotic statements in a purely algebraic fashion. There is a price to pay for this “algebrization” of analysis; the spaces one works with become quite large (in particular, they tend to be “inseparable” and not “countably generated” in any reasonable fashion), and it becomes difficult to extract explicit constants ${C}$ (or explicit decay rates) from the asymptotic notation. However, there are some cases in which the tradeoff is worthwhile. For instance, symbolic computations tend to be easier to perform in algebraic settings than in orthodox analytic settings, so formal computations of orders of infinity (such as the ones discussed in the previous blog post) could benefit from the nonstandard approach. (See also my previous posts on nonstandard analysis for more discussion about these tradeoffs.)

Let us now describe the nonstandard approach to asymptotic notation. With the above formalism, the switch from standard to nonstandard analysis is actually quite simple: one assumes that the asymptotic filter ${{\mathcal F}}$ is in fact an ultrafilter. In terms of the concept of “sufficiently large”, this means adding the following useful axiom:

This can be compared with the situation with, say, the Fréchet filter on the natural numbers ${{\bf N}}$ , in which one has to insert some qualifier such as “after passing to a subsequence if necessary” in order to make the above axiom true.

The existence of an ultrafilter requires some weak version of the axiom of choice (specifically, the ultrafilter lemma), but for this post we shall just take the existence of ultrafilters for granted.

We can now define the nonstandard orders of infinity ${{\mathcal O}}$ to be the space of all non-negative functions ${X(N)}$ defined for sufficiently large ${N \in \Omega}$ , modulo the equivalence relation ${\asymp}$ defined previously. That is to say, a nonstandard order of infinity is an equivalence class

$\displaystyle \Theta(X) := \{ Y : U \rightarrow {\bf R}^+: X \asymp Y \}$

of functions ${Y: U \rightarrow {\bf R}^+}$ defined on elements ${U}$ of the ultrafliter. For instance, if ${\Omega}$ is the natural numbers, then ${\Theta(N)}$ itself is an order of infinity, as is ${\Theta(N^2)}$ , ${\Theta(e^N)}$ , ${\Theta(1/N)}$ , ${\Theta(N \log N)}$ , and so forth. But we exclude ${0}$ ; it will be important for us that the order of infinity is strictly positive for all sufficiently large ${N}$ .

We can place various familiar algebraic operations on ${{\mathcal O}}$ :

With these operations, combined with the ultrafilter axiom, we see that ${{\mathcal O}}$ obeys the laws of many standard algebraic structures, the proofs of which we leave as exercises for the reader:

${({\mathcal O}, \leq)}$ is a totally ordered set.
In fact, ${({\mathcal O}, \leq, \Theta(1), \times, (\cdot)^{\cdot})}$ is a totally ordered vector space, with ${\Theta(1)}$ playing the role of the zero vector, multiplication ${(\Theta(X), \Theta(Y)) \mapsto \Theta(X) \times \Theta(Y)}$ playing the role of vector addition, and scalar exponentiation ${(\lambda, \Theta(X)) \mapsto \Theta(X)^\lambda}$ playing the role of scalar multiplication. (Of course, division would then play the role of vector subtraction.) To avoid confusion, one might refer to ${{\mathcal O}}$ as a log-vector space rather than a vector space to emphasize the fact that the vector structure is coming from multiplication (and exponentiation) rather than addition (and multiplication). Ordered log-vector spaces may seem like a strange and exotic concept, but they are actually already studied implicitly in analysis, albeit under the guise of other names such as log-convexity.
${({\mathcal O}, +, \times, 1)}$ is a semiring (albeit one without an additive identity element), which is idempotent: ${\Theta(X) + \Theta(X) = \Theta(X)}$ for all ${\Theta(X) \in {\mathcal O}}$ .
More generally, addition can be described in purely order-theoretic terms: ${\Theta(X) + \Theta(Y) = \max(\Theta(X), \Theta(Y))}$ for all ${\Theta(X), \Theta(Y) \in {\mathcal O}}$ . (It would therefore be natural to call ${{\mathcal O}}$ a tropical semiring, although the precise axiomatization of this term does not appear to be fully standardized currently.)

The ordered (log-)vector space structure of ${{\mathcal O}}$ in particular opens up the ability to prove asymptotic implications by (log-)linear programming; this was implicitly used in my previous post. One can also use the language of (log-)linear algebra to describe further properties of various orders of infinity. For instance, if ${\Omega}$ is the natural numbers, we can form the subspace

$\displaystyle N^{O(1)} := \bigcup_{k \geq 0} [\Theta(N)^{-k}, \Theta(N)^k]$

of ${{\mathcal O}}$ consisting of those orders of infinity ${\Theta(X)}$ which are of polynomial type in the sense that ${N^{-C} \lesssim X \lesssim N^C}$ for some ${C>0}$ ; this is then a (log)-vector subspace of ${{\mathcal O}}$ , and has a canonical (log-)linear surjection ${\mathrm{ord}: N^{O(1)} \rightarrow {\bf R}}$ that assigns to each order of infinity ${\Theta(X)}$ of polynomial type the unique real number ${\alpha}$ such that ${X(N) = N^{\alpha+o(1)}}$ , that is to say for all ${\varepsilon>0}$ one has ${N^{\alpha-\varepsilon} \lesssim X(N) \lesssim N^{\alpha+\varepsilon}}$ for all sufficiently large ${N}$ . (The existence of such an ${\alpha}$ follows from the ultrafilter axiom and by a variant of the proof of the Bolzano–Weierstrass theorem; the uniqueness is also easy to establish.) The kernel ${N^{o(1)}}$ of this surjection is then the log-subspace of quasilogarithmic orders of infinity – ${\Theta(X)}$ for which ${N^{-\varepsilon} \lesssim X \lesssim N^\varepsilon}$ for all ${\varepsilon>0}$ .

In addition to the above algebraic properties, the nonstandard orders of infinity ${{\mathcal O}}$ also enjoy a completeness property that is reminiscent of the completeness of the real numbers. In the reals, it is true that any nested sequence ${K_1 \supset K_2 \supset \dots}$ of non-empty closed intervals has a non-empty intersection, which is a property closely tied to the more familiar definition of completeness as the assertion that Cauchy sequences are always convergent. This claim of course fails for open intervals: for instance, ${(0,1/n)}$ for ${n=1,2,\dots}$ is a nested sequence of non-empty open intervals whose intersection is empty. However, in the nonstandard orders of infinity ${{\mathcal O}}$ , we have the same property for both open and closed intervals!

Lemma 1 (Completeness for arbitrary intervals) Let ${I_1 \supset I_2 \supset \dots}$ be a nested sequence of non-empty intervals in ${{\mathcal O}}$ (which can be open, closed, or half-open). Then the intersection ${\bigcap_{n=1}^\infty I_n}$ is non-empty.

Proof: For sake of notation we shall assume the intervals are open intervals ${I_n = (\Theta(X_n), \Theta(Y_n))}$ , although much the same argument would also work for closed or half-open intervals (and then by the pigeonhole principle one can then handle nested sequences of arbitrary intervals); we leave this extension to the interested reader.

Pick an element ${\Theta(Z_n)}$ of each ${I_n}$ , then we have ${X_m \ll Z_n \ll Y_m}$ whenever ${m \leq n}$ . In particular, one can find a set ${U_n}$ in the ultrafilter such that

$\displaystyle n X_m(N) \leq Z_n(N) \leq \frac{1}{n} Y_m(N)$

whenever ${N \in U_n}$ and ${m \leq n}$ , and by taking suitable intersections that these sets are nested: ${U_1 \supset U_2 \supset \dots}$ . If we now define ${Z(N)}$ to equal ${Z_n(N)}$ for ${N \in U_n \backslash U_{n+1}}$ (and leave ${Z}$ undefined outside of ${U_1}$ ), one can check that ${X_m \ll Z \ll Y_m}$ for all ${m}$ , thus ${\Theta(Z)}$ lies in the intersection of all the ${I_n}$ , giving the claim. $\Box$

This property is closely related to the countable saturation and overspill properties in nonstandard analysis. From this property one might expect that ${{\mathcal O}}$ has better topological structure than say the reals. This is not exactly true, because unfortunately ${{\mathcal O}}$ is not metrizable (or separable, or first or second countable). It is perhaps better to view ${{\mathcal O}}$ as obeying a parallel type of completeness that is neither strictly stronger nor strictly weaker than the more familiar notion of metric completeness, but is otherwise rather analogous.

Source link

What's Hot

Why Are Remittance Costs Still High?

OpenAI launches a data residency program in Asia

How to Quit Should’ing on Yourself About Spending – TFFH

Pages

Orders of infinity | What’s new

Comparison of Decimal Fractions | Comparing Decimals Numbers

Worksheet on Comparing and Ordering Decimals |Arranging Decimals

Worksheets on Missing Numbers from 1 to 20

Subtraction without Regrouping |4-Digit, 5-Digit & 6-Digit Subtraction

Top Insights