On proving that a certain set is not empty by proving that it is actually large

Question

It happens occasionally that one can prove that a given set is not empty by proving that it is actually large. The word "large" here may refer to different properties.

For example, one can prove that a certain set is not empty by proving that its cardinality is big, as in the proof that there exist transcendental numbers : The set of algebraic numbers is countable, but the set of real numbers is uncountable, so there is uncountably many transcendental numbers.

One could also prove that a certain set is not empty by proving, for example, that it has positive measure, that it is dense, etc.

What are some good examples of such proofs?

Answer 1

Many existence proofs which exploit the idea of Baire category.

For instance, existence of a metrically transitive automorphism of the closed unit square was first obtained by the category method (see "Measure-preserving homeomorphisms and metrical transitivity" by Oxtoby and Ulam) . Another classical example is due to Banach who proved that every function from a residual subset of $C[0,1]$ is nowhere differentiable.

A nice and elementary book by Oxtoby discusses these and many other applications of the category method.

Answer 2

Virtually any existence proof in analytic number theory goes by giving a quantitative lower bound (or asymptotic formula) for the number of objects of interest. For example, there are infinitely many primes of the form $x^2 + y^4$ was shown by Friedlander and Iwaniec by finding an asymptotic formula for the counting function of such primes.

Answer 3

Sard's lemma is an example - the set of regular values is non-empty since it has positive measure.

The following example also answers your question: Recently I proved the following lemma.

Let $f\colon M\to N$ be a smooth map, $M$ is a non-empty paracompact manifold. Let $k$ be a maximal rank of a differential $df(x)$ over $x\in M$. Then there exists a point $y$ in $f(M)$ such that the rank of the differential $df$ is maximal for all points of $f^{-1}(y)$.

Answer 4

Frequently in arguments in algebraic number theory, one has to choose a prime that satisfies some list of conditions, and is bigger than some given bound. (A simple example of the kind of condition that I am thinking of would be that the prime should lie in a given congruence class modulo some number $n$.) One then interprets the conditions in such a way as to be able to apply the Cebotarev density theorem to conclude that there are infinitely many primes satisfying the given conditions, and so in particular a suitable prime can be found that lies above the desired bound. (In the simple example, one would use Dirichlet's theorem on the existence of infinitely many primes in arithmetic progression, which from this point of view is a special case of Cebotarev density.)

Answer 5

This page of the Tricki describes exactly the technique you are looking for.

Answer 6

There are non-Borel sets that are Lebesgue measurable. This is proved in the following way. First show that the Borel sigma algebra for the real line is uncountable with cardinality of the real line. On the other hand, you have the Cantor set which is uncountable(cardinality = $\mathbb R$) and is of Lebesgue measure zero. Since Lebesgue measure is complete, every subset of the Cantor set belongs to the Lebesgue sigma algebra and therefore the Lebesgue sigma algebra has cardinality of the power set of the reals.

Construction of explicit examples would require axiom of choice.

Answer 7

C.Cornut and V.Vatsal's proof (as in e.g Inventiones mathematicae 148) of the non-triviality of CM points on zero and one-dimensional quaternionic Shimura varieties as one goes up an anticylcotomic $\mathbb Z_{p}$-extension $K_{\infty}$ is by showing that reduction modulo $\ell$ of CM points is actually onto points modulo $\ell$ for infinitely many $\ell$. In particular, their proof actually implies the much stronger statement that the $\mathbb Z_{p}[[\Gamma]]$-module generated by the image of the norm-coherent CM points under the Kummer map has trivial $\mu$-invariant (here $\Gamma$ is the Galois group of $K_{\infty}/K$).

Answer 8

Not quite an answer to the question but related (large modulo $2$):

Zagier's beautiful proof (Amer. Math. Monthly 97 (1990), no. 2, 144) that every prime congruent to $1$ modulo $4$ is a sum of two squares is based on the fact that the cardinality of a certain finite set is odd and the set is thus non-empty.

Answer 9

As Tsuyoshi Ito commented, the probabilistic method in combinatorics is an example. You use a probability measure on the space of possibilities, and show that the set with the desired probabilities has positive measure, hence is nonempty.

The classic example of this is the result by Erdős (1947) that the Ramsey number $R(t,t)$ grows at least exponentially with $t$. If you consider a random coloring of the edges of the complete graph on $n$ vertices, then the probability that a particular complete subgraph on $t$ vertices is monochromatic is $2^{1-{t \choose 2}}$. If ${n\choose t} 2^{1-{t \choose 2}} \lt 1$, then a random coloring has no monochromatic subgraph with positive probability. This is the case for $n = \sqrt 2^t$, $t\gt 2$, so $R(t,t) \ge \sqrt2^t$ for $t \gt 2$.

For slightly smaller $n$, most random colorings of the complete graph on $n$ vertices have no monochromatic subgraph of size $t$, but finding a construction has been an open problem.

Answer 10

The theme is prevalent in combinatorial number theory and ergodic theory. Consider the ergodic Szemerédi theorem, for instance. It says that if $(X,\mathcal{B},\mu,T)$ is a measure-preserving system and $A \in \mathcal{B}$ has $\mu (A) >0$, then $\forall k \in \mathbb{N}$ $\exists n \in \mathbb{N}$ so that $\mu (A \cap T^{-n}A \cap T^{-2n}A \cap \cdots \cap T^{-kn}A)>0$. It turns out that it's easier to prove that measure of the intersection is positive for infinitely many $n$. In fact, Furstenberg's original proof showed that $\liminf_{N \to \infty} \frac{1}{N} \sum_{n=1}^{N} \mu (A \cap T^{-n}A \cap T^{-2n}A \cap \cdots \cap T^{-kn}A) > 0$.

Answer 11

A kind of analogue of Sard's Lemma in Algebraic Geometry is Bertini's Theorem:

"Given a linear sistem $|L|$ on a smooth projective variety X, its general element is smooth outside the base points".

In particular, if $|L|$ is base-point free then the set of smooth elements in $|L|$ is dense, in particular non-empty.

Answer 12

I just heard this in a talk by Jan Krajicek: It is known that there are Boolean functions that require a "large" circuit to compute them, but the proof is probabilistic. (I.e., the measure of the set of such Boolean function (say of arity n) is known to be nonzero.) No explicit construction of such functions is known.