Readers need some familiarity with sentences like “for every there exists a large such that…” or its symbolic equivalent, ““.
A rough idea of big O notation would also be helpful but is not necessary. A brief introduction: we say that (as ) to mean that the “growth” of is “bounded above” by ; more formally, there exist positive real numbers and such that for all .
(note that denotes the absolute value of , not its cardinality as indicated in Part 4.)
Analysis (something like an advanced calculus) is often differentiated into “hard analysis” (“quantitative”, “finitary”) and “soft analysis” (“qualitative”, “infinitary”). Discrete math, computer science, and analytic number theory normally uses hard analysis while operator algebra, abstract harmonic analysis, and ergodic theory tend to rely on soft analysis. The field of partial differential equations uses techniques from both.
Convenient notation (e.g. ) from qualitative analysis can conceal gritty details from quantitative and argue efficiently from the big picture, at the cost of a precise description. Conversely, quantitative analysis can be seen as a more precise and detailed refinement of qualitative analysis. The intuitions, methods and results in hard analysis often have analogues in soft analysis and vice versa, despite their contrasting language. Tao argues this technique transfer can benefit both disciplines. Table 5 features a rough “dictionary” between the notational languages of soft and hard analysis. Kudos to Tao for such an illuminating comparison!
Table 5: “Translating” soft analysis to hard analysis [1.3]
|Soft analysis||Hard analysis|
|is finite||is bounded (e.g. )|
|vanishes||is small (e.g. )|
|is infinite||is large (e.g. )|
|Quantitative decay bound (e.g. )|
|is convergent||is metastable*|
*A sequence is “metastable” when a large number of consecutive terms are very close to each other; see “Further discussion” for more details.
Here I must reproduce two concise and important observations of Tao (almost directly lifted):
- Soft analysis statements can often be formulated both succinctly and rigorously, by using precisely defined and useful concepts (e.g. compactness, measurability, etc.). In hard analysis, one usually has to sacrifice one or the other: either one is rigorous but verbose (using lots of parameters such as , , etc.), or succinct but “fuzzy” (using intuitive but vaguely defined concepts such as “size”, “complexity”, “nearby”, etc.)
- A single concept in soft analysis can have multiple hard analysis counterparts. In particular, a “naive” translation of a statement in soft analysis into hard analysis may be incorrect. (In particular, one should not use Table 5 blindly to convert from one to the other.)
Tao’s original blog post walks through one such “translation”, from soft analysis to hard analysis, of the fundamental infinite convergence principle, more commonly known as:
Monotone convergence theorem. Every bounded monotone (i.e. either nonincreasing or nondecreasing) sequence of real numbers converges.
Intuition: If a sequences increases but does not slow down enough at some limit, no upper bound can contain its growth.
As the first step to a hard analysis version, we try to understand this theorem quantitatively—using precise quantities like and . For simplicity, we restrict the bounded sequence to the interval .
Infinite convergence principle. If and , then there exists an such that for all .
Intuition: After the first terms in the sequence, the terms get very close to each other. The sequence is “permanently stable” (varies very little) after terms.
We seek to capture in the finitary (hard analysis) version the idea that the bounds on a finite monotone sequence “squeeze” the terms together to some precise extent. Indeed, a natural candidate would be:
Pigeonhole principle (PP). If and is such that , then there exists an integer with such that .
Intuition: Given many points on the line segment , pushing points apart will result in some points being squeezed closer together.
This is easily proved by contradiction. If the distance between consecutive terms and is always greater than , then the sum of all the distances is greater than , which is absurd because all of the terms must fit inside the interval .
Let’s say that a sequence is stable on the (integer) interval if for all . Thus we say that the infinite convergence principle guarantees stability on . It turns out that the PP does not obviously imply the infinite convergence principle, so the former is not a satisfactory finitary version of the latter (we would like them to be equivalent). This is because the PP only guarantees stability on the tiny range . After different generalizations of the PP that extend that range, Tao presents the correct translation:
Finite convergence principle. If and is a function from the positive integers to the positive integers, and is such that is sufficiently large depending on and , then there exists an integer with such that for all .
(This can be proved by applying the PP to the subsequence , where and . This gives an explicit bound on how large needs to be; any will suffice.)
The finite convergence principle guarantees stability on , which can be very large, depending how is chosen. Tao proved its equivalence to the infinite convergence principle, thus establishing it as the true finitary version. It looks considerably uglier than its infinitary counterpart, with its epsilons and quantifiers and tangled logic; this demonstrates the ability of soft analysis to abstract away those wordy, quantitative descriptions into cleaner statements.
However, not every infinitary statement has a finitary analogue; consider the obvious statement
Infinite pigeonhole principle. If the integers are divided among a finite number of groups, one of those groups must have infinite size.
I suspect that there was much of the informal intuition that I couldn’t capture in my adaptation above – simply because I don’t fully understand the subject matter. The dangers of oversimplification also make it useful for readers to check out the original blog post too.
1 Translation table
I left out many rows of the original Table 5 because they needed much prior knowledge; but the following row might bring insight to the student of topology:
|Soft analysis||Hard analysis|
|is uniformly continuous||has a Lipschitz or Hölder bound (e.g. )|
From one of Tao’s papers (Tao, 2008), I’m guessing metastability (a word he coined recently) to mean the stability of a sequence over a large interval.
2 Alternatives to the limit
Tao could well have formulated the infinite convergence principle as the equivalent
Infinite convergence principle (limit version). If , then there exists a real number such that for every , there exists a n such that for all .
which is the familiar -definition of convergence from calculus. But the idea of a “limit” has no obvious finitary counterpart, so Tao favoured the formulation using Cauchy sequences as presented earlier.
3 Extending the stability range
The initial attempts to extend the PP’s interval of stability are actually quite instructive. A “constant extension” gives a stability range of :
Constant-extended pigeonhole principle. If and is a positive integer and is such that , then there exists an integer with such that for all .
(Prove it! Hint: apply the PP to the subsequence )
A “linear extension” gives a stability range of :
Linearly-extended pigeonhole principle. If and is such that , then there exists an integer with such that for all .
(Prove it! Hint: apply the PP to the subsequence )
Greater extensions progressively strengthen the PP but still do not yield any generalization that can imply the infinite convergence principle. The finite convergence principle is somewhat the “ultimate generalization” which takes into account every single extension possible (including the extensions and as shown above). Only then does the PP gain enough strength to imply the infinite convergence principle.
Challenge: can you generalize the PP to extend its stability range “polynomially” (range ) or “exponentially” (range )?
[1.3] Tao, Terence. Soft analysis, hard analysis, and the finite convergence principle. In Structure and Randomness: Pages from Year One of a Mathematical Blog. American Mathematical Society (2008).
(Tao, 2008) Tao, Terence. Norm convergence of multiple ergodic averages for commuting transformations. Ergodic Theory and Dynamical Systems 28, 657-688 (2008).