Probabilistic proofs of non-probabilistic theorems
Encyclopedia
Probability theory
routinely uses results from other fields of mathematics (mostly, analysis). The opposite cases, collected below, are relatively rare; however, probability theory is used systematically in combinatorics via the probabilistic method
. They are particularly used for non-constructive proofs.
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
routinely uses results from other fields of mathematics (mostly, analysis). The opposite cases, collected below, are relatively rare; however, probability theory is used systematically in combinatorics via the probabilistic method
Probabilistic method
The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the probability that the...
. They are particularly used for non-constructive proofs.
Analysis
- Normal numberNormal numberIn mathematics, a normal number is a real number whose infinite sequence of digits in every base b is distributed uniformly in the sense that each of the b digit values has the same natural density 1/b, also all possible b2 pairs of digits are equally likely with density b−2,...
s exist. Moreover, computableComputable numberIn mathematics, particularly theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers or the computable reals, are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm...
normal numbers exist. These non-probabilistic existence theorems follow from probabilistic results: (a) a number chosen at random (uniformly on (0,1)) is normal almost surely (which follows easily from the strong law of large numbers); (b) some probabilistic inequalities behind the strong law. The existence of a normal number follows from (a) immediately. The proof of the existence of computable normal numbers, based on (b), involves additional arguments. All known proofs use probabilistic arguments.
- Dvoretzky's theoremDvoretzky's theoremIn mathematics, in the theory of Banach spaces, Dvoretzky's theorem is an important structural theorem proved by Aryeh Dvoretzky in the early 1960s. It answered a question of Alexander Grothendieck...
which states that high-dimensional convex bodies have ball-like slices is proved probabilistically. No deterministic construction is known, even for many specific bodies.
- The diameter of the Banach–Mazur compactumBanach–Mazur compactumIn the mathematical study of functional analysis, the Banach–Mazur distance is a way to define a distance on the set Q of n-dimensional normed spaces. If X and Y are two finite-dimensional normed spaces with the same dimension, let GL denote the collection of all linear isomorphisms...
was calculated using a probabilistic construction. No deterministic construction is known.
- The original proof that the Hausdorff–Young inequalityHausdorff–Young inequalityIn mathematics, the Hausdorff−Young inequality bounds the Lq-norm of the Fourier coefficients of a periodic function for q ≥ 2. proved the inequality for some special values of q, and proved it in general...
cannot be extended to
is probabilistic. The proof of the de Leeuw–Kahane–Katznelson theorem (which is a stronger claim) is partially probabilistic.
- The first construction of a Salem set was probabilstic. Only in 1981 did Kaufman give a deterministic construction.
- Every continuous function on an interval can be uniformly approximated by polynomials, which is the Weierstrass approximation theorem. A probabilistic proof uses the weak law of large numbers. Non-probabilistic proofs were available earlier.
- Existence of a nowhere differentiable continuous function follows easily from properties of Wiener processWiener processIn mathematics, the Wiener process is a continuous-time stochastic process named in honor of Norbert Wiener. It is often called standard Brownian motion, after Robert Brown...
. A non-probabilistic proofWeierstrass functionIn mathematics, the Weierstrass function is a pathological example of a real-valued function on the real line. The function has the property that it is continuous everywhere but differentiable nowhere...
was available earlier.
- Stirling's formula was first discovered by Abraham de MoivreAbraham de MoivreAbraham de Moivre was a French mathematician famous for de Moivre's formula, which links complex numbers and trigonometry, and for his work on the normal distribution and probability theory. He was a friend of Isaac Newton, Edmund Halley, and James Stirling...
in his `The Doctrine of ChancesThe Doctrine of ChancesThe Doctrine of Chances was the first textbook on probability theory, written by 18th-century French mathematician Abraham de Moivre and first published in 1718. De Moivre wrote in English because he resided in England at the time, having fled France to escape the persecution of Huguenots...
' (with a constant identified later by Stirling) in order to be used in probability theory. Several probabilistic proofs of Stirling's formula (and related results) are found in 20 century.
- The only bounded harmonic functions defined on the whole plane are constant functions by Liouville's theorem. A probabilistic proof via two-dimensional Brownian motion is well-known. Non-probabilistic proofs were available earlier.
- Non-tangential boundary values of an analyticHolomorphic functionIn mathematics, holomorphic functions are the central objects of study in complex analysis. A holomorphic function is a complex-valued function of one or more complex variables that is complex differentiable in a neighborhood of every point in its domain...
or harmonicHarmonic functionIn mathematics, mathematical physics and the theory of stochastic processes, a harmonic function is a twice continuously differentiable function f : U → R which satisfies Laplace's equation, i.e....
function exist at almost all boundary points of non-tangential boundedness. This result (PrivalovIvan PrivalovIvan Ivanovich Privalov was a Russian mathematician best known for his work on analytic functions.- Biography :...
's theorem), and several results of this kind, are deduced from martingale convergenceDoob's martingale convergence theoremsIn mathematics — specifically, in stochastic analysis — Doob's martingale convergence theorems are a collection of results on the long-time limits of supermartingales, named after the American mathematician Joseph Leo Doob....
. Non-probabilistic proofs were available earlier.
- The boundary Harnack principle is proved using Brownian motion (see also ). Non-probabilistic proofs were available earlier.
Combinatorics
- A number of theorems stating existence of graphs (and other discrete structures) with desired properties are proved by the probabilistic methodProbabilistic methodThe probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the probability that the...
. Non-probabilistic proofs are available for some of them.
- The Maximum-minimums identity admits a probabilistic proof.
Algebra
- The fundamental theorem of algebraFundamental theorem of algebraThe fundamental theorem of algebra states that every non-constant single-variable polynomial with complex coefficients has at least one complex root...
can be proved using two-dimensional Brownian motion. Non-probabilistic proofs were available earlier.
- The index theorem for elliptic complexes is proved using probabilistic methods (rather than heat equation methods). A non-probabilistic proof was available earlier.
Topology and geometry
- A smooth boundaryBoundary (topology)In topology and mathematics in general, the boundary of a subset S of a topological space X is the set of points which can be approached both from S and from the outside of S. More precisely, it is the set of points in the closure of S, not belonging to the interior of S. An element of the boundary...
is evidently two-sided, but a non-smooth (especially, fractal) boundary can be quite complicated. It was conjectured to be two-sided in the sense that the natural projection of the Martin boundary to the topological boundary is at most 2 to 1 almost everywhere. This conjecture is proved using Brownian motionWiener processIn mathematics, the Wiener process is a continuous-time stochastic process named in honor of Norbert Wiener. It is often called standard Brownian motion, after Robert Brown...
, local timeLocal time (mathematics)In the mathematical theory of stochastic processes, local time is a stochastic process associated with diffusion processes such as Brownian motion, that characterizes the amount of time a particle has spent at a given level...
, stochastic integrationStochastic calculusStochastic calculus is a branch of mathematics that operates on stochastic processes. It allows a consistent theory of integration to be defined for integrals of stochastic processes with respect to stochastic processes...
, couplingCoupling (probability)In probability theory, coupling is a proof technique that allows one to compare two unrelated variables by "forcing" them to be related in some way.-Definition:...
, hypercontractivity etc. (see also). Known non-probabilistic approaches give weaker results: at most 10 sides in four (and more) dimensions; at most 4 sides in three dimensions; and 2 sides on the plane.
- The Loewner's torus inequality relates the area of a compact surface (topologically, a torus) to its systole. It can be proved most easily by using the probabilistic notion of varianceVarianceIn probability theory and statistics, the variance is a measure of how far a set of numbers is spread out. It is one of several descriptors of a probability distribution, describing how far the numbers lie from the mean . In particular, the variance is one of the moments of a distribution...
. A non-probabilistic proof was available earlier.
- The weak halfspace theorem for minimal surfaceMinimal surfaceIn mathematics, a minimal surface is a surface with a mean curvature of zero.These include, but are not limited to, surfaces of minimum area subject to various constraints....
s states that any complete minimal surface of bounded curvature which is not a plane is not contained in any halfspace. This theorem is proved using a couplingCouplingA coupling is a device used to connect two shafts together at their ends for the purpose of transmitting power. Couplings do not normally allow disconnection of shafts during operation, however there are torque limiting couplings which can slip or disconnect when some torque limit is exceeded.The...
between Brownian motions on minimal surfaces. A non-probabilistic proof was available earlier.
Number theory
- The normal numberNormal numberIn mathematics, a normal number is a real number whose infinite sequence of digits in every base b is distributed uniformly in the sense that each of the b digit values has the same natural density 1/b, also all possible b2 pairs of digits are equally likely with density b−2,...
theorem (1909), due to Émile BorelÉmile BorelFélix Édouard Justin Émile Borel was a French mathematician and politician.Borel was born in Saint-Affrique, Aveyron. Along with René-Louis Baire and Henri Lebesgue, he was among the pioneers of measure theory and its application to probability theory. The concept of a Borel set is named in his...
, could be one of the first examples of the probabilistic methodProbabilistic methodThe probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the probability that the...
, providing the first proof of existence of normal numbers, with the help of the first version of the strong law of large numbers (see also the first item of the section Analysis). - The Rogers–Ramanujan identities are proved using Markov chainMarkov chainA Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
s. A non-probabilistic proof was available earlier.
Quantum theory
- Non-commutative dynamics (called also quantum dynamics) is formulated in terms of Von Neumann algebraVon Neumann algebraIn mathematics, a von Neumann algebra or W*-algebra is a *-algebra of bounded operators on a Hilbert space that is closed in the weak operator topology and contains the identity operator. They were originally introduced by John von Neumann, motivated by his study of single operators, group...
s and continuous tensor products of Hilbert spacesTensor product of Hilbert spacesIn mathematics, and in particular functional analysis, the tensor product of Hilbert spaces is a way to extend the tensor product construction so that the result of taking a tensor product of two Hilbert space is another Hilbert space. Roughly speaking, the tensor product is the completion of the...
. Several results (for example, a continuum of mutually non-isomorphic models) are obtained by probabilistic means (random compact setRandom compact setIn mathematics, a random compact set is essentially a compact set-valued random variable. Random compact sets are useful in the study of attractors for random dynamical systems.-Definition:...
s and Brownian motionWiener processIn mathematics, the Wiener process is a continuous-time stochastic process named in honor of Norbert Wiener. It is often called standard Brownian motion, after Robert Brown...
). One part of this theory (so-called type III systems) is translated into the analytic language and is developing analytically; the other part (so-called type II systems) exists still in the probabilistic language only.
- Tripartite quantum states can lead to arbitrary large violations of Bell inequalities (in sharp contrast to the bipartite case). The proof uses random unitary matrices. No other proof is available.
External links
- Probabilistic Proofs of Analytic Facts at MathOverflow