32
$\begingroup$

The probabilitic method is a genius idea in combinatorics, graph theory etc, where instead of constructing something by hand, you construct the thing randomly and show that there is a positive probability of whatever property you wanted to hold holding.

Q: Are there examples of this method being used to prove results in other areas of mathematics, e.g. geometry, topology, algebraic number theory,... ?


For the purposes of this question, I want to avoid results which are "discrete mathematics in disguise", e.g. concerning structures which live on a triangulation of a topological space (but using discrete approximations of topological spaces to prove an original property of that space is OK). I would also like to avoid (non algebraic) number theory, because applications there are well known.

Edit: Finally, while there is a similar class of methods in algebraic geometry, e.g. where you show that the set of counterexamples has positive codimension, or restrict to generic points, I would like to avoid these examples because they are also fairly well known and have a slightly different flavour to the combinatorics probabilistic method

$\endgroup$
16
  • 10
    $\begingroup$ Are you willing to replace positive probability by things like set of measure nonzero or proving the set of examples is dense without an explicit construction? $\endgroup$ Feb 25, 2023 at 16:51
  • 5
    $\begingroup$ I know of several applications in which a point of interest is only known to exist because it resides in the complement of a (semi) algebraic set of low dimension. Does this count? $\endgroup$ Feb 25, 2023 at 16:53
  • 3
    $\begingroup$ Some of the examples I had in mind are of a similar type to Dustin's. For instance where the bad instances are a finite union of proper closed subsets of an irreducible variety and hence not all instances are bad $\endgroup$ Feb 25, 2023 at 17:56
  • 3
    $\begingroup$ What about things like the existence of transcendental numbers? A simple counting argument shows that most numbers are transcendental but it requires more work to find one. $\endgroup$ Feb 26, 2023 at 4:11
  • 3
    $\begingroup$ One way to formulate the probabilistic method is that every random variable $X\colon\Omega\to\mathbb{R}$ satisfies $\sup_{\omega\in\Omega}X(\omega)\geq\mathbb{E}X$. The fact that the supremum is at least the average generalizes the pigeonhole principle and is under the hood of a lot of analysis, e.g., the proof of $\|x\|_2\leq\sqrt{n}\|x\|_\infty$ for $x\in\mathbb{R}^n$, the proof that the spectral norm of a positive semidefinite matrix is its top eigenvalue, and the proof of the mean value theorem (for definite integrals). $\endgroup$ Feb 26, 2023 at 23:57

3 Answers 3

25
+50
$\begingroup$

One application of the probabilistic method in topology was found by Melanie Matchett Wood and myself:

Let $H$ be the finite group $(\mathbb Z/15) \rtimes Q_8$, where generators $i$ and $j$ of $Q_8$ act on $\mathbb Z/15$ by multiplication by -1 and 4 respectively.

Let $S$ be a finite set of primes including $2,3,$ and $5$. Then there exists a 3-manifold $M$ such that $H$ is the maximal quotient of $\pi_1(M)$ of order divisible only by primes in $S$.

However, $H$ is not itself the fundamental group of any 3-manifold.

In fact, $H$ is the smallest group with this property.

The existential part of this statement is proven using the probabilistic method, i.e. we prove that a random 3-manifold has a fundamental group of this form with positive probability. The notion of random 3-manifold we use was defined by Dunfield and Thurston, who also suggested using the probabilistic method to prove the existence of 3-manifolds with particular properties.

The relevant probability distribution is on a space of profinite groups, those most of the calculations reduce to sets of finite groups, which are discrete, so one could argue that this is discrete in disguise, but the set of isomorphism classes of finite groups certainly has a different flavor from what's usually considered in the probabilistic method in discrete mathematics. One could make the statement less discrete, though also less concrete, by saying we find a characterization of the closure of the set of fundamental groups of oriented 3-manifolds inside the space of isomorphism classes of profinite groups (with a natural topology) by the probabilistic method.

A reference is Proposition 8.17 of our paper Finite quotients of 3-manifold groups.

$\endgroup$
8
$\begingroup$

The Wiener measure gives positive weight to those continuous functions $f:[0,1]\to\Bbb R$ that are nowhere differentiable. In particular, there do exist such functions.

$\endgroup$
1
  • 4
    $\begingroup$ Along the same lines, the Wiener measure gives positive measure to any open ball in $C[0, 1]$ (see here), and is fully supported on the set of continuous nowhere differentiable functions. This proves the density of nowhere differentiable functions in $C[0, 1]$. $\endgroup$
    – Nate River
    May 26, 2023 at 5:26
3
$\begingroup$

The book Introduction to Banach spaces II by Daniel Li and Hervé Queffélec has a chapter on "the method of selectors" which seems to be a subgenre of the probabilistic method. Here is a sample of the applications given in the chapter:

  • A theorem of Bourgain allowing on the extraction of "big" quasi-independent sets, with applications to theorems of Pisier and Drury about Sidon sets.

  • A theorem of Bourgain on sums of sines: for any integer $N \geq 1$, there exists a subset $\Lambda \subseteq \mathbb N^*$, of cardinality $\lvert \Lambda \rvert = N$, such that $\left\| \sum_{k\in\Lambda} \sin(kx)\right\|_\infty \leq C_0\,N^{2/3}$, where $C_0$ is a numerical constant. This has an application to vectorial Hilbert tranforms.

  • A theorem of Bourgain on the geometry of Banach spaces (a lower bound on the "K-convexity constant").

I don't know these subjects too well, but I feel that each of these examples live in a rich ecosystem of results, some of which also answer your question. For example, here are two other results on trigonometric polynomials which can also be obtained by probabilistic methods:

  • Salem and Zygmund proved in 1954 that given amplitudes $\rho_1, \ldots, \rho_N$ and phases $\phi_1, \ldots, \phi_N$, one can find (random) signs such that $\left\| \sum_{k=1}^N \pm \rho_k \,\cos(kt+\phi_k) \right\|_\infty \leq C\,\sqrt{\sum_{k=1}^n \rho_k^2} \sqrt{\ln N}$, where $C$ is an absolute constant.

  • Uchiyama proved in 1965 that there are subsets $\Lambda \subseteq [\![ 1, N ]\!]$ such that $\left\| \sum_{k \in \Lambda} e^{ikx} \right\|_1 \geq c\,\sqrt N$, where $c$ is an absolute constant.

I know I would love to see a user-friendly survey on this kind of constructions. Kahane's book is probably very enlightening, but it remains a bit formidable-looking to me.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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