https://terrytao.wordpress.com/2025/05/04/orders-of-infinity/

[cropped-co]
What's new

Updates on my research and expository papers, discussion of open
problems, and other maths-related topics. By Terence Tao

  * Home
  * About
  * Career advice
  * On writing
  * Books
  * Applets
  * Mastodon+

  * Subscribe to feed

Orders of infinity

4 May, 2025 in expository, math.AC, math.RA | Tags: nonstandard
analysis, order theory | by Terence Tao

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 {X} 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 (Frechet) 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:

  * (i) We write {X = O(Y)}, {X \lesssim Y}, or {Y \gtrsim X} (and
    sometimes {Y = \Omega(X)}) if there exists a constant {C>0} such
    that {X(N) \leq CY(N)} for all sufficiently large {N}.
  * (ii) We write {X = o(Y)}, {X \ll Y}, or {Y \gg X} (and sometimes
    {Y = \omega(X)}) if, for every {\varepsilon>0}, one has {X(N) \
    leq \varepsilon Y(N)} for all sufficiently large {N}.
  * (iii) We write {X \asymp Y} (and sometimes {X \sim Y} or {Y = \
    Theta(X)}) if {X \lesssim Y \lesssim X}, or equivalently if there
    exist constants {C, c > 0} such that {c Y(N) \leq X(N) \leq C Y
    (N)} for all sufficiently large {N}.

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:

  * If {X \lesssim Y} and {Y \lesssim Z}, then {X \lesssim Z}.
  * {X \lesssim Y} if and only if {XZ \lesssim YZ}.
  * If {N} is restricted to a sequence, then (after passing to a
    subsequence if necessary), exactly one of {X \ll Y}, {X \asymp Y}
    , and {X \gg Y} is true.

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:

  * Given any predicate {P(N)}, exactly one of the two statements "{P
    (N)} holds for sufficiently large {N}" and "{P(N)} does not hold
    for sufficiently large {N}" is true.

This can be compared with the situation with, say, the Frechet 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}}:

  * Addition. We define {\Theta(X)+\Theta(Y) :=\Theta(X+Y)}. It is
    easy to see that this is well-defined, by verifying that if {X \
    asymp X'} and {Y \asymp Y'}, then {X+Y \asymp X'+Y'}. However,
    because of our positivity requirement, we do not define
    subtraction on {{\mathcal O}}.
  * Multiplication and division We define {\Theta(X) \times \Theta(Y)
    := \Theta(XY)} and {\Theta(X)/\Theta(Y) = \Theta(X/Y)}; we do not
    need to worry about division by zero, thanks to the positivity
    requirement. Again it is easy to verify this is well-defined.
  * Scalar exponentiation If {\lambda} is a real number, we define {\
    Theta(X)^\lambda := \Theta(X^\lambda)}. Again, this is easily
    checked to be well-defined.
  * Order We define {\Theta(X) \leq \Theta(Y)} if {X \lesssim Y}, and
    {\Theta(X) < \Theta(Y)} if {X \ll Y}. Again, this is easily
    checked to be well-defined. (And the ultrafilter axiom ensures
    that {\Theta(X) \leq \Theta(Y)} holds iff exactly one of {\Theta
    (X)=\Theta(Y)} and {\Theta(X) < \Theta(Y)} holds.)

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.

Share this:

  * Click to print (Opens in new window) Print
  * Click to email a link to a friend (Opens in new window) Email
  * More
  * 

  * Click to share on X (Opens in new window) X
  * Click to share on Facebook (Opens in new window) Facebook
  * Click to share on Reddit (Opens in new window) Reddit
  * Click to share on Pinterest (Opens in new window) Pinterest
  * 

Like Loading...

Recent Comments

[]    Anonymous on Orders of infinity
[]    Anonymous on Orders of infinity
[5d6] Dave Doty on A proof of concept tool to ver...
[eb9] Toby Bartels on Orders of infinity
[d7f] Terence Tao on Orders of infinity
[474] hideoutleftca8790a9b... on Orders of infinity
[46c] Justin Bian on Orders of infinity
[bd4] Orders of infinity |... on A proof of concept tool to ver...
[d7f] Terence Tao on A proof of concept tool to ver...
[80e] nunosempere2 on A proof of concept tool to ver...
[5d6] Dave Doty on A proof of concept tool to ver...
[8e5] Andrew Krause on A proof of concept tool to ver...
[d7f] Terence Tao on The equational theories projec...
[d7f] Terence Tao on A proof of concept tool to ver...
[d7f] Terence Tao on A proof of concept tool to ver...
[                    ] [Search]
Top Posts

  * Orders of infinity
  * A proof of concept tool to verify estimates
  * Career advice
  * Cosmic Distance Ladder videos with Grant Sanderson (3blue1brown):
    commentary and corrections
  * Does one have to be a genius to do maths?
  * Books
  * There's more to mathematics than rigour and proofs
  * The equational theories project: a brief tour
  * About
  * On writing

Archives

  * May 2025 (2)
  * April 2025 (2)
  * March 2025 (1)
  * February 2025 (3)
  * January 2025 (1)
  * December 2024 (3)
  * November 2024 (4)
  * October 2024 (1)
  * September 2024 (4)
  * August 2024 (3)
  * July 2024 (3)
  * June 2024 (1)
  * May 2024 (1)
  * April 2024 (5)
  * March 2024 (1)
  * December 2023 (2)
  * November 2023 (2)
  * October 2023 (1)
  * September 2023 (3)
  * August 2023 (3)
  * June 2023 (8)
  * May 2023 (1)
  * April 2023 (1)
  * March 2023 (2)
  * February 2023 (1)
  * January 2023 (2)
  * December 2022 (3)
  * November 2022 (3)
  * October 2022 (3)
  * September 2022 (1)
  * July 2022 (3)
  * June 2022 (1)
  * May 2022 (2)
  * April 2022 (2)
  * March 2022 (5)
  * February 2022 (3)
  * January 2022 (1)
  * December 2021 (2)
  * November 2021 (2)
  * October 2021 (1)
  * September 2021 (2)
  * August 2021 (1)
  * July 2021 (3)
  * June 2021 (1)
  * May 2021 (2)
  * February 2021 (6)
  * January 2021 (2)
  * December 2020 (4)
  * November 2020 (2)
  * October 2020 (4)
  * September 2020 (5)
  * August 2020 (2)
  * July 2020 (2)
  * June 2020 (1)
  * May 2020 (2)
  * April 2020 (3)
  * March 2020 (9)
  * February 2020 (1)
  * January 2020 (3)
  * December 2019 (4)
  * November 2019 (2)
  * September 2019 (2)
  * August 2019 (3)
  * July 2019 (2)
  * June 2019 (4)
  * May 2019 (6)
  * April 2019 (4)
  * March 2019 (2)
  * February 2019 (5)
  * January 2019 (1)
  * December 2018 (6)
  * November 2018 (2)
  * October 2018 (2)
  * September 2018 (5)
  * August 2018 (3)
  * July 2018 (3)
  * June 2018 (1)
  * May 2018 (4)
  * April 2018 (4)
  * March 2018 (5)
  * February 2018 (4)
  * January 2018 (5)
  * December 2017 (5)
  * November 2017 (3)
  * October 2017 (4)
  * September 2017 (4)
  * August 2017 (5)
  * July 2017 (5)
  * June 2017 (1)
  * May 2017 (3)
  * April 2017 (2)
  * March 2017 (3)
  * February 2017 (1)
  * January 2017 (2)
  * December 2016 (2)
  * November 2016 (2)
  * October 2016 (5)
  * September 2016 (4)
  * August 2016 (4)
  * July 2016 (1)
  * June 2016 (3)
  * May 2016 (5)
  * April 2016 (2)
  * March 2016 (6)
  * February 2016 (2)
  * January 2016 (1)
  * December 2015 (4)
  * November 2015 (6)
  * October 2015 (5)
  * September 2015 (5)
  * August 2015 (4)
  * July 2015 (7)
  * June 2015 (1)
  * May 2015 (5)
  * April 2015 (4)
  * March 2015 (3)
  * February 2015 (4)
  * January 2015 (4)
  * December 2014 (6)
  * November 2014 (5)
  * October 2014 (4)
  * September 2014 (3)
  * August 2014 (4)
  * July 2014 (5)
  * June 2014 (5)
  * May 2014 (5)
  * April 2014 (2)
  * March 2014 (4)
  * February 2014 (5)
  * January 2014 (4)
  * December 2013 (4)
  * November 2013 (5)
  * October 2013 (4)
  * September 2013 (5)
  * August 2013 (1)
  * July 2013 (7)
  * June 2013 (12)
  * May 2013 (4)
  * April 2013 (2)
  * March 2013 (2)
  * February 2013 (6)
  * January 2013 (1)
  * December 2012 (4)
  * November 2012 (7)
  * October 2012 (6)
  * September 2012 (4)
  * August 2012 (3)
  * July 2012 (4)
  * June 2012 (3)
  * May 2012 (3)
  * April 2012 (4)
  * March 2012 (5)
  * February 2012 (5)
  * January 2012 (4)
  * December 2011 (8)
  * November 2011 (8)
  * October 2011 (7)
  * September 2011 (6)
  * August 2011 (8)
  * July 2011 (9)
  * June 2011 (8)
  * May 2011 (11)
  * April 2011 (3)
  * March 2011 (10)
  * February 2011 (3)
  * January 2011 (5)
  * December 2010 (5)
  * November 2010 (6)
  * October 2010 (9)
  * September 2010 (9)
  * August 2010 (3)
  * July 2010 (4)
  * June 2010 (8)
  * May 2010 (8)
  * April 2010 (8)
  * March 2010 (8)
  * February 2010 (10)
  * January 2010 (12)
  * December 2009 (11)
  * November 2009 (8)
  * October 2009 (15)
  * September 2009 (6)
  * August 2009 (13)
  * July 2009 (10)
  * June 2009 (11)
  * May 2009 (9)
  * April 2009 (11)
  * March 2009 (14)
  * February 2009 (13)
  * January 2009 (18)
  * December 2008 (8)
  * November 2008 (9)
  * October 2008 (10)
  * September 2008 (5)
  * August 2008 (6)
  * July 2008 (7)
  * June 2008 (8)
  * May 2008 (11)
  * April 2008 (12)
  * March 2008 (12)
  * February 2008 (13)
  * January 2008 (17)
  * December 2007 (10)
  * November 2007 (9)
  * October 2007 (9)
  * September 2007 (7)
  * August 2007 (9)
  * July 2007 (9)
  * June 2007 (6)
  * May 2007 (10)
  * April 2007 (11)
  * March 2007 (9)
  * February 2007 (4)

Categories

  * expository (317)
      + tricks (13)
  * guest blog (10)
  * Mathematics (888)
      + math.AC (9)
      + math.AG (42)
      + math.AP (115)
      + math.AT (17)
      + math.CA (190)
      + math.CO (197)
      + math.CT (9)
      + math.CV (37)
      + math.DG (37)
      + math.DS (89)
      + math.FA (24)
      + math.GM (14)
      + math.GN (21)
      + math.GR (88)
      + math.GT (17)
      + math.HO (13)
      + math.IT (13)
      + math.LO (53)
      + math.MG (47)
      + math.MP (31)
      + math.NA (24)
      + math.NT (199)
      + math.OA (22)
      + math.PR (109)
      + math.QA (6)
      + math.RA (48)
      + math.RT (21)
      + math.SG (4)
      + math.SP (48)
      + math.ST (11)
  * non-technical (195)
      + admin (46)
      + advertising (66)
      + diversions (7)
      + media (14)
          o journals (3)
      + obituary (15)
  * opinion (36)
  * paper (253)
      + book (20)
      + Companion (13)
      + update (23)
  * question (127)
      + polymath (86)
  * talk (69)
      + DLS (20)
  * teaching (189)
      + 245A - Real analysis (11)
      + 245B - Real analysis (22)
      + 245C - Real analysis (6)
      + 246A - complex analysis (11)
      + 246B - complex analysis (5)
      + 246C - complex analysis (5)
      + 247B - Classical Fourier Analysis (5)
      + 254A - analytic prime number theory (19)
      + 254A - ergodic theory (18)
      + 254A - Hilbert's fifth problem (12)
      + 254A - Incompressible fluid equations (5)
      + 254A - random matrices (14)
      + 254B - expansion in groups (8)
      + 254B - Higher order Fourier analysis (9)
      + 255B - incompressible Euler equations (2)
      + 275A - probability theory (6)
      + 285G - poincare conjecture (20)
      + Logic reading seminar (8)
  * The sciences (1)
  * travel (26)

additive combinatorics approximate groups arithmetic progressions Ben
Green Cauchy-Schwarz Cayley graphs central limit theorem Chowla
conjecture compressed sensing correspondence principle distributions
divisor function eigenvalues Elias Stein Emmanuel Breuillard entropy
equidistribution ergodic theory Euler equations exponential sums
finite fields Fourier transform Freiman's theorem Gowers uniformity
norm Gowers uniformity norms graph theory Gromov's theorem GUE
Hilbert's fifth problem incompressible Euler equations inverse
conjecture Joni Teravainen Kaisa Matomaki Kakeya conjecture Lie
algebras Lie groups Liouville function Littlewood-Offord problem
Maksym Radziwill Mobius function multiplicative functions
Navier-Stokes equations nilpotent groups nilsequences nonstandard
analysis parity problem Paul Erdos politics polymath1 polymath8
Polymath15 polynomial method polynomials prime gaps prime numbers
prime number theorem random matrices randomness Ratner's theorem
regularity lemma Ricci flow Riemann zeta function Schrodinger
equation Shannon entropy sieve theory structure Szemeredi's theorem
Tamar Ziegler tiling UCLA ultrafilters universality Van Vu wave maps
Yitang Zhang

RSS The Polymath Blog

  * Polymath projects 2021
  * A sort of Polymath on a famous MathOverflow problem
  * Ten Years of Polymath
  * Updates and Pictures
  * Polymath proposal: finding simpler unit distance graphs of
    chromatic number 5
  * A new polymath proposal (related to the Riemann Hypothesis) over
    Tao's blog
  * Spontaneous Polymath 14 - A success!
  * Polymath 13 - a success!
  * Non-transitive Dice over Gowers's Blog
  * Rota's Basis Conjecture: Polymath 12, post 3

6 comments

Comments feed for this article

4 May, 2025 at 7:31 am

Justin Bian

[46c]

Nothing too much, just to say thank you for your interesting posts
and productive works [?]

Reply

4 May, 2025 at 7:45 am

hideoutleftca8790a9b5

[474]

Dear Professor Tao,

Your exposition on orders of infinity and their algebraic structure
in nonstandard analysis is illuminating, particularly the
completeness property of \mathcal{O} and its log-vector space
structure.

I wonder if the tropical semiring perspective could be further
leveraged to connect with optimization problems, such as those in
combinatorial geometry or network theory, where tropical algebra
often simplifies asymptotic bounds.

For instance, could the idempotent addition \Theta(X) + \Theta(Y) = \
max(\Theta(X), \Theta(Y)) inform algorithms for scaling limits in
graph problems?

Additionally, the non-metrizability of \mathcal{O} seems to limit
explicit constant extraction, but might there be a way to define a
"coarse" metric or topology on a quotient of \mathcal{O} (e.g., by
grouping orders within bounded logarithmic ratios) to regain some
computational tractability?

This could bridge the algebraic elegance of nonstandard analysis with
practical applications in symbolic computation, as you hinted.

Finally, your mention of symbolic computations suggests potential for
automated theorem proving or computer algebra systems. Have you
considered formalizing parts of \mathcal{O}'s structure in a system
like Lean or Coq to test conjectures about asymptotic relations?

Such tools might uncover new algebraic identities or streamline the
verification of your exercises.

Thank you for this thought-provoking post! I look forward to seeing
how these ideas evolve. Best regards,

Reply

   
    4 May, 2025 at 7:59 am

    Terence Tao

    [d7f]

    In fact, I have thought about doing exactly this, and started a
    bare-bones repository at https://github.com/teorth/estimate_tools
    to set this up. Right now it contains almost no content - just a
    proof of concept of a single Lean derivation done in the setting
    of totally ordered vector fields (which are already set up in
    Lean's Mathlib) - but if there is interest, I could expand this
    into a collaborative formalization project.

    It is indeed true that while the full space {\mathcal O} is
    non-metrizable, there are many useful metrizable subquotients of
    this log-vector space, for instance the canonical linear
    surjection from N^{O(1)} to {\mathbb R} discussed in the blog
    post gives one such example.

    Reply

4 May, 2025 at 8:39 am

Toby Bartels

[eb9]

Another way to extend completeness to arbitrary intervals is to look
at the interiors of the intervals. If these interiors have non-empty
intersection, then certainly the original intervals do.

(There's a slight technicality: a non-empty closed interval could
have empty interior, by being a single point. But if that ever
happens, then every further interval in the sequence must also be
that point, so the intersection is that point.)

Reply

4 May, 2025 at 2:02 pm

Anonymous

[]

few elementary questions.. when we say 1/0 or for that matter talk
about blowups in navier stokes do we know it is enough to use the
smallest infinity? When you talk about using halting problem for
navier stokes for blowup is it still the countable infinity even
though reals are uncountable and pdes are over reals.

Reply

4 May, 2025 at 2:26 pm

Anonymous

[]

yay for non-standard non-standard analysis

Reply


Leave a comment Cancel reply

 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
D[                                             ] 

For commenters

To enter in LaTeX in comments, use $latex <Your LaTeX code>$ (without
the < and > signs, of course; in fact, these signs should be avoided
as they can cause formatting errors). Also, backslashes \ need to be
doubled as \\.  See the about page for details and for other
commenting policy.

<< A proof of concept tool to verify estimates

Blog at WordPress.com.Ben Eastaugh and Chris Sternal-Johnson.

Subscribe to feed.

  * Comment
  * Reblog
  * Subscribe Subscribed
      + [bd4bda] What's new
        Join 11,771 other subscribers
        [                    ]
        Sign me up
      + Already have a WordPress.com account? Log in now.
  * 
      + [bd4bda] What's new
      + Subscribe Subscribed
      + Sign up
      + Log in
      + Copy shortlink
      + Report this content
      + View post in Reader
      + Manage subscriptions
      + Collapse this bar

%d

[b]