What are some examples of proving that a thing exists by proving that the set of such things has positive measure?

Question

Suppose we want to prove that among some collection of things, at least one of them has some desirable property. Sometimes the easiest strategy is to equip the collection of all things with a measure, then show that the set of things with the desired property has positive measure. Examples of this strategy appear in many parts of mathematics.

What is your favourite example of a proof of this type?

Here are some examples:

• The probabilistic method in combinatorics As I understand it, a typical pattern of argument is as follows. We have a set $X$ and want to show that at least one element of $X$ has property $P$. We choose some function $f: X \to \{0, 1, \ldots\}$ such that $f(x) = 0$ iff $x$ satisfies $P$, and we choose a probability measure on $X$. Then we show that with respect to that measure, $\mathbb{E}(f) < 1$. It follows that $f^{-1}\{0\}$ has positive measure, and is therefore nonempty.

• Real analysis One example is Banach's proof that any measurable function $f: \mathbb{R} \to \mathbb{R}$ satisfying Cauchy's functional equation $f(x + y) = f(x) + f(y)$ is linear. Sketch: it's enough to show that $f$ is continuous at $0$, since then it follows from additivity that $f$ is continuous everywhere, which makes it easy. To show continuity at $0$, let $\varepsilon > 0$. An argument using Lusin's theorem shows that for all sufficiently small $x$, the set $\{y: |f(x + y) - f(y)| < \varepsilon\}$ has positive Lebesgue measure. In particular, it's nonempty, and additivity then gives $|f(x)| < \varepsilon$.

  Another example is the existence of real numbers that are normal (i.e. normal to every base). It was shown that almost all real numbers have this property well before any specific number was shown to be normal.

• Set theory Here I take ultrafilters to be the notion of measure, an ultrafilter on a set $X$ being a finitely additive $\{0, 1\}$-valued probability measure defined on the full $\sigma$-algebra $P(X)$. Some existence proofs work by proving that the subset of elements with the desired property has measure $1$ in the ultrafilter, and is therefore nonempty.

  One example is a proof that for every measurable cardinal $\kappa$, there exists some inaccessible cardinal strictly smaller than it. Sketch: take a $\kappa$-complete ultrafilter on $\kappa$. Make an inspired choice of function $\kappa \to \{\text{cardinals } < \kappa \}$. Push the ultrafilter forwards along this function to give an ultrafilter on $\{\text{cardinals } < \kappa\}$. Then prove that the set of inaccessible cardinals $< \kappa$ belongs to that ultrafilter ("has measure $1$") and conclude that, in particular, it's nonempty.

  (Although it has a similar flavour, I would not include in this list the cardinal arithmetic proof of the existence of transcendental real numbers, for two reasons. First, there's no measure in sight. Second -- contrary to popular belief -- this argument leads to an explicit construction of a transcendental number, whereas the other arguments on this list do not explicitly construct a thing with the desired properties.)

(Mathematicians being mathematicians, someone will probably observe that any existence proof can be presented as a proof in which the set of things with the required property has positive measure. Once you've got a thing with the property, just take the Dirac delta on it. But obviously I'm after less trivial examples.)

PS I'm aware of the earlier question On proving that a certain set is not empty by proving that it is actually large. That has some good answers, a couple of which could also be answers to my question. But my question is specifically focused on positive measure, and excludes things like the transcendental number argument or the Baire category theorem discussed there.

Answer 1

Szemerédi's theorem asserts that every set $A$ of integers of positive upper density (thus $\limsup_{N \to \infty} \frac{|A \cap [-N,N]|}{|[-N,N]|} > 0$) contains arbitrarily long arithmetic progressions. One of the shortest (but not the most elementary) proofs of this remarkably deep theorem deduces it from a result in ergodic theory:

Furstenberg recurrence theorem: Let $E$ be a subset of a probability space $(X,\mu)$ of positive measure, and let $T: X \to X$ be an invertible measure-preserving shift. Then for any $k \geq 1$ there exists a positive integer $n$ such that $E \cap T^n E \cap T^{2n} E \cap \dots \cap T^{(k-1) n} E$ has positive measure.

The case $k=1$ is trivial, and the case $k=2$ is the classical Poincare recurrence theorem. The general case was established in

Furstenberg, Harry, Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions, J. Anal. Math. 31, 204-256 (1977). ZBL0347.28016.

Roughly speaking the deduction of Szemerédi's theorem from Furstenberg's theorem is as follows. By hypothesis, there is a sequence $N_j \to \infty$ such that $\frac{|A \cap [-N_j,N_j]|}{|[-N_j,N_j]|}$ converges to a positive limit. One can define a generalised density of subsets $B \subset {\bf Z}$ by the formula $\mu(B) := \tilde \lim_{j \to \infty} \frac{|B \cap [-N_j,N_j]|}{|[-N_j,N_j]|}$ where $\tilde \lim$ is an extension of the limit functional $\lim$ to bounded sequences (this can be constructed using the Hahn-Banach theorem or using an ultrafilter). Morally speaking, this turns the integers ${\bf Z}$ into a probability space $({\bf Z},\mu)$ in which $A$ has positive measure and the shift $T: n \mapsto n-1$ is measure-preserving. Then by the Furstenberg recurrence theorem, for every $k$, there is a positive integer $n$ such that $A \cap T^n A \cap \dots \cap T^{(k-1) n} A$ has positive measure, hence non-empty, hence $A$ contains arbitrarily long arithmetic progressions.

(I cheated a little because $\mu$ is only a finitely additive measure rather than countably additive, but one can massage the finitely additive probability space $({\bf Z},\mu)$ constructed here into a countably additive model $(X, \tilde \mu)$ by a little bit of measure-theoretic trickery which I will not detail here.)

Answer 2

Sard's theorem implies that the measure of the set of critical points of a smooth function $f:M_1\to M_2$ between smooth manifolds has measure zero. Hence the preimage $f^{-1}(x)$ of almost every point in $M_2$ is a smooth submanifold. This can be used, for example, to prove the existence of Morse functions. Following Milnor's Morse Theory, Section 6, one can embed $M$ into $\mathbb{R}^n$. Then for almost all points in $\mathbb{R}^n$, the distance map is a Morse function. This may be seen by applying Sard's theorem to the normal bundle. The set of focal points has measure zero, and corresponds to the points at which the distance function is degenerate.

Answer 3

The Chevalley-Warning theorem asserts that if a system of polynomial equations in $r$ variables over a finite field of characteristic $p$ has total degree less than $r$, then the number of solutions to this system is a multiple of $p$.

An immediate corollary of this is Chevalley's theorem: if such a system of polynomials has a "trivial" solution (often this is the origin $(0,\dots,0)$), then it must necessarily have a non-trivial solution as well. This is often applied for instance as part of the "polynomial method" in combinatorics.

Answer 4

Kahn and Markovic showed the existence of immersed essential surfaces in closed hyperbolic 3-manifolds. The idea was to construct many immersed pants in the manifold using the frame flow. From the exponential mixing of the frame flow, they showed that the cuffs of the pants were equidistributed in a sufficiently uniform way so that they could use Hall's marriage theorem to pair the cuffs in a way that created a closed nearly geodesic (and hence essential) surface. They used similar ideas to resolve the Ehrenpreis conjecture, although the proof was more subtle since they couldn't use Hall's marriage theorem.

Answer 5

1. The proofs of existence of expanders by Barzdin - Kolmogorov and Pinsker,

and (somewhat related)

2. Gromov's proof of the existence of groups with no coarse embedding into a Hilbert space.

Answer 6

A very famous and important theorem in the theory of metric embeddings is known as "Assouad's Embedding Theorem". It concerns doubling metric spaces: metric spaces for which there is a constant $D$ such that every ball can be covered by $D$ balls of half the radius.

Theorem (Assouad, 1983): For every $\epsilon\in (0,1)$ and $D>0$, there are constants $L$ and $N$ such that if $(X,d)$ is doubling with constant $D$, then the metric space $(X,d^\epsilon)$ admits an $L$-bi-Lipschitz embedding into $\mathbb{R}^N$.

This theorem is widely used throughout metric geometry and analysis on metric spaces. (See, e.g., here or here.)

An $L$-bi-Lipschitz embedding is simply an embedding that preserves all distances up to factor $L$. It's easy to see that the doubling condition is necessary for this theorem to hold. Moreover, there are known doubling metric spaces (the Heisenberg group for one) that are doubling but do not admit a bi-Lipschitz embedding into any Euclidean space, so one cannot allow $\epsilon=1$ in Assouad's theorem.

This means, of course, that the constants $L$ and $N$ must blow up as $\epsilon\rightarrow 1$, and this is reflected Assouad's proof.

Except, that's not quite true. In a really surprising construction, Naor and Neiman showed in 2012 that the dimension $N$ in Assouad's theorem can be chosen independent of the ``snowflake'' parameter $\epsilon$ as $\epsilon\rightarrow 1$. (The distortion $L$ must necessarily blow up in general.) In other words, one need not use too many dimensions for the embedding, no matter how close $\epsilon$ gets to $1$. I believe this shocked many people.

The construction of Naor and Neiman is probabilistic: they construct a random Lipschitz map from $(X,d^\epsilon)$ into $\mathbb{R}^N$, and show that it is bi-Lipschitz with positive probability. The proof is also a nice application to geometry of the Lovasz Local Lemma.

Assouad's paper: http://www.numdam.org/article/BSMF_1983__111__429_0.pdf

Naor-Neiman's paper: https://www.cs.bgu.ac.il/~neimano/Naor-Neiman.pdf

Answer 7

In general, the probabilistic method of Erdos follows exactly this philosophy: prove that an object with a certain property of number theoretic interest exists by showing that the probability a random set satisfies the desired property with positive probability (usually the probability is one!)

Example: a subset $S \subset \mathbb{N}$ is an asymptotic additive basis of order $k$ if there exists $N_0 > 0$ such that for all $N > N_0$, there exists $x_1, \cdots, x_k \in S$ (not necessarily distinct) such that $N = x_1 + \cdots + x_k$. In other words, every sufficiently large positive integer is the sum of $k$ elements of $S$ (with possible repetition).

If we define $r_S^k(n) = \# \{(x_1, \cdots, x_k) \in S^k : n = x_1 + \cdots + x_k\}$ to be the representation function of order $k$ with respect to $S$, then the average size of $r_S^k(n)$ is a measure of how "optimal" the set $S$ as an additive basis. For instance it is known that the set $\mathcal{S}$ of square integer is an additive basis of order $4$ (Lagrange's theorem), but it is hardly optimal since $r_\mathcal{S}^4(n) \gg n$ for all $n$. How small can $r_S^k(n)$ be on average provided that it is positive for all sufficiently large $n$?

Erdos and Fuchs gave a "lower bound" for this average: $r_S^k(n)$ cannot be constant on average. Further, Erdos and Turan made the following conjecture: if $S$ is an asymptotic additive basis of order $k$, then $\liminf_{n \rightarrow \infty} r_S^k(n) = \infty$.

Erdos further refined this conjecture to assert that the lower bound ought to be of order $\log n$. To show that such optimal additive bases exist he used the probabilistic method. The case $k = 2$ is due to Erdos and the general case due to Erdos and Tetali.

Answer 8

Lubotzky, Maher, and Wu showed for any $n\in \mathbb{Z}, g\in \mathbb{N}$ the existence of homology 3-spheres of Heegaard genus $g$ and Casson invariant $n$ via a probabilistic argument. The idea is to take an appropriate subgroup of the Torelli subgroup of the mapping class group of a genus $g$ surface, and modify a Heegaard splitting of $S^3$ of genus $g$ by a random walk on this subgroup. On this subgroup, the Casson invariant is realized by a homomorphism to $\mathbb{Z}$. Since random walks are recurrent, each integer is realized as a Casson invariant infinitely often. And they show that with probability tending to 1, the Heegaard genus is $g$. Hence there exists manifolds with the desired invariants.

Answer 9

Universality of Riemann zeta function , Which related to the approximation of every Holomorphic function $f(z)$ by Riemann zeta function in the strip .

Corollary: Let $K_0$ be a compact set in the right half of the critical stripe $1/2< \Re z<1$. Let $f$ be a continuous function on $K_0$, which is holomorphic on an open set containing $K_0$ and does not have any zeros in $K_0$ . For every $\epsilon_0>0$, we have that the limit (lower density ) $$ \inf\lim\limits_{T \rightarrow \infty} \frac{1}{T} \lambda \Big (\{ t\in[0,T]: \max\limits_{z \in K_0} \left| {\zeta(z+it) -f(z) )}\right| < \epsilon_0\Big\}) $$ is positive for $\lambda$ being the Lebesgue measure.

Answer 10

An example from pre measure theory real analysis is in the proof of the Bounded Convergence Theorem for Riemann integrals in [1, §22.14, p288]. Here the author omits a portion of the proof, and in his other book [2, §7.2.5, p304] the proof is omitted entirely and described as 'quite delicate'. The proof required is of the following : if $\delta > 0$ and if $(E_n)$ is a sequence of sets in $[0, 1]$ with each $E_n$ containing a finite number of non-overlapping closed intervals with a total length $\geq \delta$, then there exists a point belonging to infinitely many of the $E_n$. In other words we need to show the set $E = \bigcap_{n=1}^{\infty} \bigcup_{m=n}^{\infty} E_m$ of all such points is non-empty and we can do this by showing it contains a set of positive measure : denote by $F_n$ the union of the above intervals within $E_n$ (so $F_n$ is a Borel set), and let $F = \bigcap_{n=1}^{\infty} \bigcup_{m=n}^{\infty} F_m \subseteq E$, then by [3, §2.60, p44], since this is a decreasing intersection, we have $|F| = \lim_{n \rightarrow \infty} |\bigcup_{m=n}^{\infty} F_m|$, where $\forall\ n\ |\bigcup_{m=n}^{\infty} F_m| \geq |F_n| \geq \delta$ (noting $F_n$ equals a finite union of disjoint intervals with a total length $\geq \delta$), so that $|F| \geq \delta > 0$ and hence $F \neq \emptyset$ and thus $E \neq \emptyset$, as required. The author then uses the above theorem to prove the Monotone Convergence Theorem and Dominated Convergence Theorem for Riemann integrals, [1, §22.15, p289], [1, §25.21, p359], [4, App A], and the latter of these facilitates the proof of Stirling's Formula in [5].

Another example is the problem stated in this answer to Theorems that are 'obvious' but hard to prove, as an example of a problem that may seem obvious but which requires a non-trivial proof : if intervals $I_n \subseteq [0, 1]\ \forall\ n$ and $\sum_{n=1}^{\infty} l(I_n) < 1$ then $\bigcup_{n=1}^{\infty} I_n \subsetneq [0, 1]$, so we seek a point in $[0, 1]$ which has the property of not being in any $I_n$. Noting all the sets below are Borel sets we have : \begin{eqnarray*} |[0, 1]| & = & |\bigcup_{n=1}^{\infty} I_n| + |[0, 1] \setminus \bigcup_{n=1}^{\infty} I_n|, \hspace{2em} \mbox{using countable additivity} \\ \Rightarrow |[0, 1] \setminus \bigcup_{n=1}^{\infty} I_n| & = & 1 - |\bigcup_{n=1}^{\infty} I_n| \\ \Rightarrow |[0, 1] \setminus \bigcup_{n=1}^{\infty} I_n| & > & 0 \end{eqnarray*} since by countable subadditivity $|\bigcup_{n=1}^{\infty} I_n| \leq \sum_{n=1}^{\infty} |I_n| = \sum_{n=1}^{\infty} l(I_n) < 1$. Thus the set of all the points of interest, ie $[0, 1] \setminus \bigcup_{n=1}^{\infty} I_n$, is non-empty as required. The proof is not 'hard' but does require the non-trivial concept of the outer measure on $\mathbb{R}$.

---

[1] Robert G. Bartle (1964), The Elements of Real Analysis, John Wiley & Sons.

[2] Robert G. Bartle & Donald R. Sherbert (1982), Introduction to Real Analysis, John Wiley & Sons.

[3] Sheldon Axler (2020), Measure, Integration & Real Analysis, Springer Graduate Texts in Mathematics, https://measure.axler.net/.

[4] Ross Ure Anderson (2023), Intervals and Outer Measure on R , https://ia601904.us.archive.org/19/items/intervals-and-outer-measure-on-r/IntervalsAndOuterMeasureOnR.pdf

[5] Keith Conrad, Stirling's Formula, https://kconrad.math.uconn.edu/blurbs/analysis/stirling.pdf (mirror : https://archive.org/details/stirlings-formula-keith-conrad)