43
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ You got the argument for the probabilistic method in combinatorics the wrong way around: $\mathbb{E}(f)<1$ does not imply $f^{-1}(0) \neq \emptyset$. The argument works the other way: One shows $\mathbb{E}(f)>0$ and infers that there must be at least one point $x\in X$ with $f(x)>0$. $\endgroup$ – Johannes Hahn Jul 14 at 19:18
  • 7
    $\begingroup$ Not sure what you mean, Johannes. If $\mathbb{E}(f) < 1$ then there's some $x$ such that $f(x) < 1$. Since $f$ is valued in $\mathbb{N}$, that's equivalent to $f(x) = 0$. Of course, one can make similar arguments with $\mathbb{E}(f) < a$ or $\mathbb{E}(f) > a$ for any constant $a$, as you've done with $a = 0$. $\endgroup$ – Tom Leinster Jul 14 at 20:04
  • 3
    $\begingroup$ I feel like basically all Brownian motion sample path properties are of this form. Given any one of them, it's usually not so obvious how you would construct even one continuous function with that property (nowhere differentiable, uncountable level sets, nowhere increasing, etc, etc); yet "almost every" continuous function enjoys all of them simultaneously. $\endgroup$ – Nate Eldredge Jul 14 at 20:16
  • 3
    $\begingroup$ This question should be community wiki since there's no "correct" answer. $\endgroup$ – Ian Agol Jul 14 at 20:32
  • 1
    $\begingroup$ One of the most spectacular examples (at least in functional analysis) is Gluskin’s results that the Banach Mazur compactum, i.e., the family of $n$ dimensional Banach spaces, which is a compact space under a natural metric, is as bad as can be. He did this by showing that there is a suitable measure so that pairs of randomly chosen polytopes generate spaces with large Banach Mazur distances on a set of positive measure. A more precise statement can be found in the (in this case reliable) wikipedia article “Banch Mazur compactum”. $\endgroup$ – user131781 Jul 16 at 8:38
28
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ a curiosity: is it really necessary for this argument to work to have at disposal the (weak version of - but still stronger than Countable Dependent) Axiom of Choice? I ask because I don't think anything more than DC is needed to prove both Furstenberg's theorem and Szemerédi's one (but I might be wrong here), thus I find curious that some `serious choice' is needed to bridge them $\endgroup$ – Nicola Gigli Jul 14 at 21:36
  • $\begingroup$ There is another way to proceed with the derivation by constructively building some finite probability measures on a Cantor space that approximately model the set $A$ and then extracting a weakly convergent subsequence. I think this has a chance of being done completely in a choice-free manner (countable iterations of Bolzano-Weierstrass plus a diagonalization argument). Not an expert on these questions though. [And now one can go further and ask if one can make this argument intuitionistic, my guess is no...] $\endgroup$ – Terry Tao Jul 14 at 23:46
  • $\begingroup$ Actually I now remember that I looked into this question back in 2005 and found a version of the Furstenberg correspondence principle that does not require the axiom of choice: math.ucla.edu/~tao/preprints/Expository/limiting.pdf $\endgroup$ – Terry Tao Jul 15 at 0:04
  • 2
    $\begingroup$ @NicolaGigli: Doesn't non-dependence on AC follow from $Π^1_1$-absoluteness? $\endgroup$ – user21820 Jul 15 at 6:20
  • 1
    $\begingroup$ @NicolaGigli: I am not a set theory expert, but from what I know AC can be eliminated from any ZFC proof of any theorem that is $Σ^1_2$ or $Π^1_2$, by simply applying Shoenfield's absoluteness theorem. In particular, the statement $Q$ here is equivalent to a $Π^1_1$ sentence that says "$∀A{⊆}N\ $ $( \ ∃p,q{∈}N\ ∀k{∈}N\ ∃m,c{∈}N\ ∃t{∈}(A⋂[-m,m])^c ( \ p,q>0 ∧ c·q > (2·m+1)·p \ )$ $⇒ ∀c{∈}N\ ∃t{∈}A^c\ ( \ \text{$t$ is an AP} \ ) \ )$" where $N$ is the naturals. $\endgroup$ – user21820 Jul 15 at 7:41
20
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
14
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, but in the spirit of the game: where's the measure here? Did you just mean counting measure? $\endgroup$ – Tom Leinster Jul 14 at 21:08
  • 4
    $\begingroup$ Yeah, counting measure, applied to the non-trivial solutions. (Arguably one should be measuring here using the p-adic valuation rather than the Archimedean valuation, though.) There are some proofs of at least one of the Sylow theorems in a similar spirit, though I don't remember the details offhand. $\endgroup$ – Terry Tao Jul 14 at 21:13
  • 2
    $\begingroup$ For the Sylow theorem. Let $G$ act on the set $X$ all subsets of size $p^k$ (where $|G|=p^k.a$) by right multiplication (or left if you prefer). Since $|X|$ is not divisible by $p$, there is an orbit of this action of size not divisible by $p$. Thus its stabilizer contains a multiple of $p^k$ elements in it. Either induction or an easy argument shows that the stabilizer has order exactly $p^k$. $\endgroup$ – David A. Craven Jul 16 at 14:22
  • 1
    $\begingroup$ In the same spirit, a p group acting on a finite vector space over F_p always has a fixed point. The orbits are all sizes power of p. There is an orbit of size 1 corresponding to 0 so there must be at least p-1 other orbits of size 1. $\endgroup$ – Asvin Jul 16 at 20:39
  • $\begingroup$ @TerryTao could u give me your opinion about my example here as an answer to the titled question, Thanks for any comment $\endgroup$ – zeraoulia rafik Jul 17 at 9:57
9
$\begingroup$

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.

$\endgroup$
7
$\begingroup$
  1. The proofs of existence of expanders by Barzdin - Kolmogorov and Pinsker,

and (somewhat related)

  1. Gromov's proof of the existence of groups with no coarse embedding into a Hilbert space.
$\endgroup$
7
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ That's a great example! But I was wondering what L was and checked the linked wiki page and learned that the statement on universality there is purely in terms of $ \zeta$ (and without a log). So is there a reason why you quoted this more complicated statement? $\endgroup$ – Dirk Jul 16 at 17:09
  • $\begingroup$ @Dirk,yes am going to edit it, this is a particular case of Universality of Riemann zeta function, Thanks for your attention $\endgroup$ – zeraoulia rafik Jul 16 at 17:42
  • 1
    $\begingroup$ @PierrePC, yes thanks for your attention it fixed now $\endgroup$ – zeraoulia rafik Jul 17 at 9:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.