The catalog

All problems

Every statement in the catalog, readable in place. Filters apply instantly; search covers names, IDs, and the LaTeX statements themselves.

Showing 20 of 280 problems in Probability theory

ANAL-FA-015

Kannan–Lovász–Simonovits (KLS) conjecture

LandmarkConjecture1995

There is a universal constant

C < \infty

such that for every

n

, every log-concave probability measure

μ

R^{n}

satisfying

\int x d μ (x) = 0

and

\int x_{i} x_{j} d μ (x) = δ_{ij}

, and every locally Lipschitz

f : R^{n} \to R

Var_{μ} (f) \leq C \int_{R^{n}} ∥\nabla f (x) ∥_{2}^{2} d μ (x) .

PDE-006

Global classical solutions of the relativistic Vlasov–Maxwell system

MajorOpen problemc. 1980

Let

f_{0}^{\pm} \in C_{c}^{\infty} (R_{x}^{3} \times R_{p}^{3})

be nonnegative and let

E_{0}, B_{0} \in C_{c}^{\infty} (R^{3}; R^{3})

satisfy

\nabla \cdot E_{0} = \int (f_{0}^{+} - f_{0}^{-}) d p

and

\nabla \cdot B_{0} = 0

. With

v (p) = p / 1 + ∣ p ∣^{2}

, the system

\partial_{t} f^{\pm} + v \cdot \nabla_{x} f^{\pm} \pm (E + v \times B) \cdot \nabla_{p} f^{\pm} = 0, \partial_{t} E - \nabla \times B = - j, \partial_{t} B + \nabla \times E = 0, \nabla \cdot E = ρ, \nabla \cdot B = 0, ρ = \int_{R^{3}} (f^{+} - f^{-}) d p, j = \int_{R^{3}} v (p) (f^{+} - f^{-}) d p

has a unique classical solution for all

t \geq 0

DYN-009

Furstenberg $\times2,\times3$ measure conjecture

LandmarkConjecture1967

Let

μ

be a Borel probability measure on

T = R / Z

that is invariant under

T_{2} (x) = 2 x (mod 1)

and

T_{3} (x) = 3 x (mod 1)

, and ergodic for their joint action: every Borel set invariant modulo

μ

under both maps has measure

0

1

. Then either

μ

is Lebesgue measure or there is a finite set

F \subset T

, invariant under both

T_{2}

and

T_{3}

, such that

μ (F) = 1

DYN-010

Rokhlin multiple-mixing problem

MajorOpen problem1949

Let

T

be an invertible measure-preserving transformation of a standard probability space

(X, B, μ)

. If

μ (A \cap T^{- n} B) \to μ (A) μ (B)

n \to \infty

for all

A, B \in B

, then for every

k \geq 2

, all

A_{0}, \dots, A_{k} \in B

, and all integer sequences

n_{1}^{(j)}, \dots, n_{k}^{(j)}

satisfying, as

j \to \infty

i min ∣ n_{i}^{(j)} ∣ \to \infty, i \neq = l min ∣ n_{i}^{(j)} - n_{l}^{(j)} ∣ \to \infty,

one has

μ (A_{0} \cap i = 1 ⋂ k T^{- n_{i}^{(j)}} A_{i}) ⟶ i = 0 \prod k μ (A_{i}) .

DYN-012

Pugh–Shub stable-ergodicity conjecture

MajorConjecture1997

Let

M

be a closed connected manifold with a smooth probability volume

μ

, and fix a Riemannian norm on

TM

. For a linear map

A

, write

m (A) = in f_{∥ v ∥ = 1} ∥ A v ∥

. A

C^{2}

μ

-preserving diffeomorphism

f

is partially hyperbolic here if it has a continuous

D f

-invariant splitting into nonzero bundles

TM = E^{s} \oplus E^{c} \oplus E^{u}

and an integer

N \geq 1

such that, for every

x \in M

∥ D f_{x}^{N} ∣_{E_{x}^{s}} ∥ < m (D f_{x}^{N} ∣_{E_{x}^{c}}) \leq ∥ D f_{x}^{N} ∣_{E_{x}^{c}} ∥ < m (D f_{x}^{N} ∣_{E_{x}^{u}}), ∥ D f_{x}^{N} ∣_{E_{x}^{s}} ∥ < 1 < m (D f_{x}^{N} ∣_{E_{x}^{u}}) .

Among these diffeomorphisms, the stably ergodic ones are

C^{2}

-dense; stable ergodicity means that every sufficiently

C^{2}

-near

C^{2}

μ

-preserving diffeomorphism is ergodic.

PROB-003

No Infinite Cluster at Critical Percolation on $\mathbb Z^d$

LandmarkConjecturec. 1960

For Bernoulli bond percolation on

Z^{d}

, independently declare each nearest-neighbor edge open with probability

p

, and let

p_{c} (d)

be the threshold for an infinite open cluster. Then for every

d \geq 2

P_{p_{c} (d)} (0 \leftrightarrow \infty) = 0.

PROB-001

Two-dimensional self-avoiding-walk critical exponents

LandmarkConjecture1972–1982

For

n \geq 0

, let

S_{n} = {ω = (ω_{0}, \dots, ω_{n}) \in (Z^{2})^{n + 1} : ω_{0} = 0, ∥ ω_{j + 1} - ω_{j} ∥_{1} = 1 (0 \leq j < n), ω_{i} \neq = ω_{j} (0 \leq i < j \leq n)}

and put

c_{n} = ∣ S_{n} ∣

. Let

μ = lim_{n \to \infty} c_{n}^{1/ n}

, whose existence is known, and let

P_{n}

and

E_{n}

denote the uniform probability law on

S_{n}

and expectation with respect to that law. There exist constants

A, D \in (0, \infty)

such that, as

n \to \infty

c_{n} \sim A μ^{n} n^{11/32} and E_{n} [∥ ω_{n} ∥_{2}^{2}] \sim D n^{3/2} .

Thus the counting and metric critical exponents are respectively

γ = 43/32

and

ν = 3/4

PROB-002

KPZ fluctuation exponent for two-dimensional first-passage percolation

LandmarkConjecturec. 1986

Give each unoriented nearest-neighbor edge

e

Z^{2}

an independent exponential random variable

τ_{e}

of mean

1

. For

x, y \in Z^{2}

, define

T (x, y) = π : x \to y min e \in π \sum τ_{e},

where the minimum is over finite nearest-neighbor paths from

x

y

. If

e_{1} = (1, 0)

, then

n \to \infty lim \frac{lo g Var T ( 0 , n e _{1} )}{lo g n} = \frac{2}{3} .

PROB-004

Strict Convexity of the First-Passage Percolation Limit Shape

MajorConjecturec. 1965

Assign independent mean-one exponential passage times to the nearest-neighbor edges of

Z^{d}

d \geq 2

. Let

B \subset R^{d}

be the deterministic compact convex limit shape from the first-passage percolation shape theorem. Then

B

is strictly convex: its boundary contains no nontrivial line segment.

STAT-001

Optimal i.i.d. Berry–Esseen constant

MajorExact constant problem1942

Let

Φ

be the standard normal distribution function. For i.i.d. real-valued random variables

X_{1}, \dots, X_{n}

, define

C_{BE} = n \geq 1, X_{1}, \dots, X_{n} i.i.d. E X_{1} = 0, E X_{1}^{2} = 1, 0 < ρ := E ∣ X_{1} ∣^{3} < \infty sup \frac{n}{ρ} x \in R sup P {\frac{X _{1} + \dots + X _{n}}{n} \leq x} - Φ (x) .

Determine

C_{BE}

exactly.

STAT-002

Gaussian Product Inequality Conjecture

MajorConjecture2012

For every integer

n \geq 1

, every centered jointly Gaussian random vector

X = (X_{1}, \dots, X_{n})

with

Var (X_{i}) > 0

for all

i

, and every choice of real exponents

α_{1}, \dots, α_{n} > 0

E [i = 1 \prod n ∣ X_{i} ∣^{α_{i}}] \geq i = 1 \prod n E [∣ X_{i} ∣^{α_{i}}] .

OR-003

Beardwood–Halton–Hammersley planar TSP constant

MajorExact constant problem1959

Let

X_{1}, X_{2}, \dots

be independent random points uniformly distributed on

[0, 1]^{2}

, and let

L_{n}

be the minimum Euclidean length of a closed polygonal tour visiting

X_{1}, \dots, X_{n}

. The almost-sure limit

β_{2} = n \to \infty lim \frac{L _{n}}{n}

exists and is a deterministic positive constant. Determine

β_{2}

exactly.

TCS-004

$P=BPP$ Derandomization Conjecture

LandmarkConjecture1977–1985

P = BPP,

where

P

is deterministic polynomial time and

BPP

consists of languages decided by probabilistic polynomial-time Turing machines that give the correct answer with probability at least

2/3

on every input.

TCS-022

Planted Clique Conjecture

MajorConjecture1992–1998

For every fixed

ε \in (0, 1/2)

, there is no randomized polynomial-time algorithm

A

such that, for all sufficiently large

n

, the following hypotheses are distinguished:

H_{0} : each edge of a graph on [n] is independently present with probability \frac{1}{2};

H_{1} : sample as under H_{0}, choose uniformly a k = ⌊ n^{1/2 - ε} ⌋ -vertex set, and add all its missing edges .

More precisely, no such

A

satisfies

Pr [A (G) = i ∣ H_{i}] \geq 2/3

for both

i \in {0, 1}

TCS-027

Feige's Random $3$ -SAT Refutation Hypothesis

MajorConjecture2002

For every sufficiently large constant

Δ > 0

, there is no randomized polynomial-time algorithm

A

having both of the following properties. First, for every satisfiable

3

-CNF formula

F

A (F)

never outputs

UNSAT

. Second, if

F_{n, Δ}

is formed on variables

x_{1}, \dots, x_{n}

by choosing

m = ⌊ Δ n ⌋

clauses independently and uniformly, each clause using three distinct variables with independent uniformly random signs, then

Pr [A (F_{n, Δ}) = UNSAT] ⟶ 1 as n \to \infty,

where the probability includes the randomness of both the formula and

A

INFO-002

Capacity of the binary deletion channel

MajorExact constant problemc. 1961

Fix

d \in (0, 1)

. On input

x = (x_{1}, \dots, x_{n}) \in {0, 1}^{n}

, independently delete each coordinate with probability

d

and output the undeleted bits in their original order, without deletion markers. Let

M_{n} (d, ε)

be the largest cardinality of a code

C \subseteq {0, 1}^{n}

for which some decoder has average error at most

ε

under a uniformly selected codeword. Determine, for every

d \in (0, 1)

C_{del} (d) = ε ↓ 0 lim n \to \infty lim sup \frac{1}{n} lo g_{2} M_{n} (d, ε) .

MATH-PHYS-003

Anderson delocalization in dimension $d\ge3$

LandmarkConjecture1958

Let

d \geq 3

and

(H_{λ, ω} ψ) (x) = - ∣ y - x ∣ = 1 \sum ψ (y) + λ ω_{x} ψ (x) on ℓ^{2} (Z^{d}),

where the

ω_{x}

are iid with a bounded compactly supported density that is positive near

0

. For all sufficiently small

λ > 0

, there is a nonempty open interval

I

in the interior of

[- 2 d, 2 d]

on which

H_{λ, ω}

has almost surely nonempty purely absolutely continuous spectrum.

MATH-PHYS-011

Critical three-dimensional Ising spin-field scaling limit

LandmarkConjecturec. 1970

Let

⟨ \cdot ⟩_{β_{c}}

be the infinite-volume zero-field Gibbs state at the critical inverse temperature

β_{c}

of the nearest-neighbor ferromagnetic Ising model on

Z^{3}

, where

β_{c}

is the infimum of the inverse temperatures for which the infinite-volume plus state has positive magnetization. The spins are

σ_{x} \in {- 1, 1}

, and finite-volume weights are proportional to

exp (β \sum_{⟨ x, y ⟩} σ_{x} σ_{y})

, with the sum over nearest-neighbor edges. For

a > 0

, set

e_{1} = (1, 0, 0)

n_{a} = ⌊ a^{- 1} ⌋

c_{a} = ⟨ σ_{0} σ_{n_{a} e_{1}} ⟩_{β_{c}}^{- 1/2}

, and define a random tempered distribution by

Φ_{a} (f) = a^{3} c_{a} x \in Z^{3} \sum σ_{x} f (a x), f \in S (R^{3}) .

a ↓ 0

Φ_{a}

converges in law in

S^{'} (R^{3})

to a non-Gaussian random distribution

Φ

. For every integer

k \geq 1

, its

k

-point correlation distribution has a smooth restriction

S_{k}

to pairwise distinct points, and there is

Δ_{σ} > 0

such that every conformal diffeomorphism

φ : U \to V

between open subsets of

R^{3}

satisfies

S_{k} (φ (x_{1}), \dots, φ (x_{k})) = i = 1 \prod k λ_{φ} (x_{i})^{- Δ_{σ}} S_{k} (x_{1}, \dots, x_{k}), λ_{φ} (x) = ∣ det D φ (x) ∣^{1/3},

for all pairwise distinct

x_{1}, \dots, x_{k} \in U

MATH-PHYS-005

Three-dimensional Coulomb crystallization

MajorConjecturec. 1934

Let

Λ_{L} = (R / L Z)^{3}

, let

N = L^{3} \in N

, and let

G_{L}

be the zero-mean periodic Coulomb Green function satisfying

- Δ G_{L} = 4 π (δ_{0} - L^{- 3})

. For pairwise distinct

x_{1}, \dots, x_{N} \in Λ_{L}

, define the neutral-jellium energy, with the point self-energies omitted, by

E_{L} (x_{1}, \dots, x_{N}) = 1 \leq i < j \leq N \sum G_{L} (x_{i} - x_{j}) - i = 1 \sum N \int_{Λ_{L}} G_{L} (x_{i} - y) d y + \frac{1}{2} \iint_{Λ_{L}^{2}} G_{L} (x - y) d x d y .

Then

L \to \infty L^{3} \in N lim L^{- 3} x_{1}, \dots, x_{L^{3}} \in Λ_{L} x_{i} \neq = x_{j} (i \neq = j) in f E_{L} (x_{1}, \dots, x_{L^{3}}) = e_{BCC},

where

e_{BCC}

is the thermodynamic energy per unit volume of the unit-density body-centered-cubic lattice under the same normalization.

GAME-001

Uniform $\varepsilon$ -equilibrium in finite multiplayer stochastic games

MajorConjecturec. 1981

Consider any stochastic game with a finite player set

I

, finite state set

S

, finite nonempty action set

A_{i} (s)

for each player

i

at state

s

, bounded stage payoff

g_{i} (s, a)

for each action profile

a \in \prod_{i \in I} A_{i} (s)

, and transition law

q (\cdot ∣ s, a)

S

. For every

ε > 0

and initial state

s_{0}

, there exist a behavioral-strategy profile

σ

and

N \in N

such that, for every horizon

n \geq N

, every player

i

, and every unilateral behavioral deviation

τ_{i}

E_{s_{0}, σ} [\frac{1}{n} t = 1 \sum n g_{i} (s_{t}, a_{t})] \geq E_{s_{0}, (τ_{i}, σ_{- i})} [\frac{1}{n} t = 1 \sum n g_{i} (s_{t}, a_{t})] - ε,

where

(s_{t}, a_{t})

is the state--action process generated by the indicated strategy profile and transition law.