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 106 of 280 problems

NT-AN-003

Generalized Riemann Hypothesis for Dirichlet $L$ -functions

LandmarkConjecturec. 1884

For every primitive Dirichlet character

χ

modulo an integer

q \geq 1

, every zero

ρ

of the analytically continued Dirichlet function

L (s, χ) = n = 1 \sum \infty \frac{χ ( n )}{n ^{s}} (ℜ s > 1)

satisfying

0 < ℜ ρ < 1

has

ℜ ρ = \frac{1}{2}

NT-PRIME-009

Hilbert’s Tenth Problem over $\mathbb Q$

LandmarkOpen problem1970

There is no Turing machine which, on every input polynomial

f \in Z [x_{1}, \dots, x_{n}]

(where

n

is part of the input), halts and correctly decides whether there exists

(q_{1}, \dots, q_{n}) \in Q^{n}

with

f (q_{1}, \dots, q_{n}) = 0

NT-AUTO-030

Generalized Ramanujan Conjecture for $\mathrm{GL}_n$

LandmarkConjecturec. 1967

For every

n \geq 2

, every irreducible unitary cuspidal automorphic representation

π = ⨂_{v}^{'} π_{v}

GL_{n} (A_{Q})

, where

A_{Q}

is the adèle ring of

Q

, and every place

v

Q

, the local representation

π_{v}

is tempered; equivalently, all its

K_{v}

-finite matrix coefficients belong to

L^{2 + ε} (GL_{n} (Q_{v}) / Z_{v})

for every

ε > 0

, where

K_{v}

is a maximal compact subgroup and

Z_{v}

is the center.

NT-GALOIS-031

Montgomery’s Pair-Correlation Conjecture

LandmarkConjecture1973

Assume the Riemann hypothesis, write the nontrivial zeros of the Riemann zeta function as

\frac{1}{2} + iγ

, counted with multiplicity, and put

N (T) = # {γ : 0 < γ \leq T}

. For every fixed

0 < α < β

\frac{1}{N ( T )} # {(γ, γ^{'}) : 0 < γ, γ^{'} \leq T, α \leq \frac{( γ - γ ^{'} ) lo g T}{2 π} \leq β} ⟶ \int_{α}^{β} (1 - (\frac{sin π u}{π u})^{2}) d u

T \to \infty

NT-CORR-035

Chowla’s Correlation Conjecture

LandmarkConjecture1965

Let

λ (n) = (- 1)^{Ω (n)}

be the Liouville function, where

Ω (n)

is the number of prime factors of

n

, counted with multiplicity. For every integer

k \geq 2

and every choice of distinct nonnegative integers

h_{1}, \dots, h_{k}

n \leq x \sum j = 1 \prod k λ (n + h_{j}) = o (x) (x \to \infty) .

NT-DIO-036

Inverse Galois Conjecture over $\mathbb Q$

LandmarkOpen problemc. 1892

For every finite group

G

, there exists a finite Galois extension

L / Q

such that

Gal (L / Q) ≅ G

ALG-GALCOH-018

Soficity Conjecture

LandmarkConjecture2000

Every countable group is sofic. Explicitly, for every countable group

G

, finite

F \subseteq G

, and

ε > 0

, there are an integer

n

and a map

σ : G \to Sym (n)

such that

σ (1) = 1

d_{H} (σ (g h), σ (g) σ (h)) < ε (g, h \in F),

and

d_{H} (σ (g), 1) > 1 - ε

for every

g \in F ∖ {1}

, where

d_{H}

is normalized Hamming distance.

AG-CYCLE-003

Tate Conjecture

LandmarkConjecture1963

Let

k

be a finitely generated field,

X / k

a smooth projective variety,

r \geq 0

, and

ℓ \neq = char k

a prime. The image of

cl_{ℓ} : CH^{r} (X) \otimes_{Z} Q_{ℓ} ⟶ H_{\overset{e}{ˊ} t}^{2 r} (X_{\overset{ˉ}{k}}, Q_{ℓ} (r))

equals the invariant subspace

H_{\overset{e}{ˊ} t}^{2 r} (X_{\overset{ˉ}{k}}, Q_{ℓ} (r))^{Gal (\overset{ˉ}{k} / k)},

where

CH^{r} (X)

is the group of codimension-

r

algebraic cycles modulo rational equivalence.

AG-ANAB-005

Grothendieck Section Conjecture

LandmarkConjecture1983

Let

K

be a field finitely generated over

Q

, put

G_{K} = Gal (\overset{ˉ}{K} / K)

, and let

X / K

be a smooth, projective, geometrically connected curve of genus

g \geq 2

. After choosing a geometric base point, its étale fundamental groups fit into the exact sequence

1 \to π_{1}^{\overset{e}{ˊ} t} (X_{\overset{ˉ}{K}}) \to π_{1}^{\overset{e}{ˊ} t} (X) \to G_{K} \to 1.

The map sending

x \in X (K)

to the conjugacy class (under

π_{1}^{\overset{e}{ˊ} t} (X_{\overset{ˉ}{K}})

) of the section

G_{K} \to π_{1}^{\overset{e}{ˊ} t} (X)

determined by

x

is a bijection.

AG-DIO-006

Vojta’s Main Conjecture

LandmarkConjecture1987

Let

X

be a smooth projective variety over a number field

K

, let

D

be a simple-normal-crossings divisor,

A

a big divisor,

S

a finite set of places of

K

r \geq 1

, and

ε > 0

. There is a proper Zariski-closed

Z \subset X

containing the support of

D

such that for every

P \in X (\overset{ˉ}{K}) ∖ Z

with

[K (P) : K] \leq r

m_{D, S} (P) + h_{K_{X}} (P) \leq d_{K} (P) + ε h_{A} (P) + O (1) .

Here

m_{D, S}

is the proximity function, heights use fixed Weil-height choices, the

O (1)

constant may depend on the fixed data

(X, D, A, K, S, r, ε)

but is independent of

P

, and

d_{K} (P) = \frac{lo g N _{K / Q} D _{K (P) / K}}{[ K ( P ) : K ]}

is the normalized logarithmic relative discriminant, with

D_{K (P) / K}

the relative discriminant ideal.

AG-MMP-010

Abundance Conjecture

LandmarkConjecturec. 1985

Let

(X, Δ)

be a projective Kawamata-log-terminal pair over

C

, with

K_{X} + Δ

Q

-Cartier

Q

-divisor. If

K_{X} + Δ

is nef, then it is semiample: some positive integral multiple is Cartier and base-point-free.

AG-MMP-012

Termination of Flips Conjecture

LandmarkConjecturec. 1988

Let

(X_{0}, Δ_{0})

be a projective

Q

-factorial Kawamata-log-terminal pair over

C

. Every sequence

(X_{0}, Δ_{0}) ⇢ (X_{1}, Δ_{1}) ⇢ (X_{2}, Δ_{2}) ⇢ \dots

in which each arrow is a

(K_{X_{i}} + Δ_{i})

-flip terminates after finitely many steps.

AG-SING-013

Resolution of Singularities in Positive Characteristic

LandmarkOpen problem1964

Let

k

be a perfect field of positive characteristic and

X

an integral separated scheme of finite type over

k

. There exist a smooth integral

k

-scheme

Y

and a proper birational morphism

f : Y \to X

that is an isomorphism over the regular locus

X_{reg}

AG-DIFF-021

Grothendieck–Katz $p$ -Curvature Conjecture

LandmarkConjecture1969–1972

Let

K

be a number field, let

X / K

be a smooth connected variety, and let

(E, \nabla)

be an algebraic vector bundle with integrable connection on

X

. After extending these data over

O_{K} [S^{- 1}]

for some finite set

S

of finite places, reduce at a place

p \in / S

of residue characteristic

p

. For a local derivation

D

on the reduction

X_{p}

, define the

p

-curvature by

ψ_{p} (D) = \nabla_{D}^{p} - \nabla_{D^{[p]}},

where

D^{[p]}

is the

p

-fold iterate of

D

as a derivation. If

ψ_{p} (D) = 0

for every local derivation

D

and all but finitely many

p

, then, after any embedding

K ↪ C

, the analytic monodromy of

(E, \nabla)

X (C)

has finite image; equivalently, the connection becomes trivial after a finite étale cover of

X_{C}

AG-HYP-022

Green–Griffiths–Lang Conjecture

LandmarkConjecture1980

Let

X

be a smooth projective complex variety of general type. There exists a proper Zariski-closed subset

Y ⊊ X

such that every nonconstant holomorphic map

f : C \to X

satisfies

f (C) \subseteq Y

GEO-TOP-002

Smooth four-dimensional Schoenflies conjecture

LandmarkConjecturec. 1960

For every smooth embedding

e : S^{3} ↪ S^{4}

, each of the two closures of the components of

S^{4} ∖ e (S^{3})

is diffeomorphic to the standard closed

4

-ball

D^{4}

GEO-TOP-004

Borel topological rigidity conjecture

LandmarkConjecture1953

Let

M

and

N

be closed, connected, topological

n

-manifolds with

n \geq 5

and contractible universal covers. Every homotopy equivalence

f : N \to M

is homotopic to a homeomorphism.

GEO-TOP-007

Novikov higher-signature conjecture

LandmarkConjecture1970

Let

M

be a closed connected oriented smooth manifold, let

Γ = π_{1} (M)

, let

u : M \to B Γ

classify its universal cover, and let

α \in H^{*} (B Γ; Q)

. The higher signature

⟨ L (M) ⌣ u^{*} α, [M] ⟩ \in Q

is invariant under orientation-preserving homotopy equivalence. Here

L (M)

is the total Hirzebruch

L

-class of

TM

, and only the top-degree component is evaluated.

GEO-TOP-015

Weinstein conjecture

LandmarkConjecture1978

Let

M^{2 n - 1}

be a closed smooth manifold and let

α

be a contact form, so

α \land (d α)^{n - 1}

is nowhere zero. The Reeb vector field

R_{α}

, uniquely defined by

α (R_{α}) = 1

and

d α (R_{α}, \cdot) = 0

, has a nonconstant periodic orbit.

ANAL-FA-001

Invariant subspace problem for Hilbert space

LandmarkOpen problem1935–1950

For every separable infinite-dimensional complex Hilbert space

H

and every bounded linear operator

T : H \to H

, there is a closed linear subspace

M

such that

{0} ⊊ M ⊊ H, T (M) \subseteq M .

ANAL-FA-006

Kakeya set conjecture in dimensions $n\ge4$

LandmarkConjecturec. 1971

Let

n \geq 4

and let

E \subset R^{n}

be a Borel set such that for every

v \in S^{n - 1}

there is

x_{v} \in R^{n}

with

{x_{v} + t v : 0 \leq t \leq 1} \subset E

. Then

dim_{H} E = n

ANAL-FA-007

Fourier restriction conjecture for the sphere

LandmarkConjecturec. 1967

Let

n \geq 3

, let

d σ

be surface measure on

S^{n - 1}

, and for

1 \leq p, q < \infty

define

E g (x) = \int_{S^{n - 1}} e^{2 πi x \cdot ω} g (ω) d σ (ω) .

q > \frac{2 n}{n - 1} and \frac{n + 1}{q} \leq \frac{n - 1}{p ^{'}}, p^{'} = \frac{p}{p - 1}

(with

p^{'} = \infty

for

p = 1

), then there is

C = C (n, p, q)

such that

∥ E g ∥_{L^{q} (R^{n})} \leq C ∥ g ∥_{L^{p} (S^{n - 1}, d σ)}

for every

g \in L^{p} (S^{n - 1}, d σ)

ANAL-FA-008

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

ANAL-FA-017

Baum–Connes conjecture without coefficients

LandmarkConjecture1982

For every countable discrete group

G

, the analytic assembly map

μ_{G} : K_{*}^{G} (\underline{E} G) ⟶ K_{*} (C_{r}^{*} (G))

is an isomorphism. Here

\underline{E} G = E_{Fin} G

is the terminal

G

-CW complex whose

H

-fixed-point space is contractible for finite subgroups

H \leq G

and empty for infinite

H

;

K_{*}^{G}

is equivariant topological

K

-homology with

G

-compact supports; and

C_{r}^{*} (G)

is the operator-norm closure of the left regular representation of

C G

ℓ^{2} (G)

ANAL-FA-018

Free-group-factor isomorphism problem

LandmarkOpen problemc. 1943

For each integer

n \geq 2

, let

F_{n}

be the free group on

n

generators, let

λ_{n}

be its left regular representation on

ℓ^{2} (F_{n})

, and define the free group factor

L (F_{n}) = {λ_{n} (g) : g \in F_{n}}^{''}

. Determine which of the following alternatives holds:

L (F_{m}) ≅ L (F_{n})

for every

m, n \geq 2

, or

L (F_{m}) \neq ≅ L (F_{n})

whenever

m \neq = n

, where

≅

denotes a unital normal

*

-isomorphism of von Neumann algebras.

PDE-002

Global regularity for three-dimensional incompressible Euler

LandmarkOpen problemc. 1930

For every divergence-free Schwartz vector field

u_{0} \in S (R^{3}; R^{3})

, the maximal classical solution of

\partial_{t} u + (u \cdot \nabla) u = - \nabla p, \nabla \cdot u = 0, u (\cdot, 0) = u_{0}

exists for all

t \geq 0

and belongs to

C^{\infty} (R^{3} \times [0, \infty))

PDE-003

Global regularity for inviscid surface quasi-geostrophic flow

LandmarkOpen problem1994

For every

θ_{0} \in S (R^{2})

, the unique maximal classical solution of

\partial_{t} θ + u \cdot \nabla θ = 0, u = \nabla^{⊥} (- Δ)^{- 1/2} θ = (- R_{2} θ, R_{1} θ), θ (\cdot, 0) = θ_{0}

exists for every

t \geq 0

and is smooth, where

R_{j}

is the

j

-th Riesz transform.

PDE-008

$C^2$ strong cosmic censorship

LandmarkConjecturec. 1979

Fix a closed smooth

3

-manifold

Σ

and a smooth background Riemannian metric

b

. Let

D_{vac} (Σ)

be the space of smooth pairs

(h, K)

, with

h

Riemannian and

K

symmetric, satisfying

R_{h} - ∣ K ∣_{h}^{2} + (tr_{h} K)^{2} = 0

and

div_{h} K - d (tr_{h} K) = 0

. Give it the relative Fréchet topology induced by

q_{m} (γ, L) = ∥ γ ∥_{C^{m} (b)} + ∥ L ∥_{C^{m} (b)}

m = 0, 1, \dots

, on differences

(γ, L) = (h - h^{'}, K - K^{'})

. In every nonempty connected component of

D_{vac} (Σ)

, the data whose maximal globally hyperbolic development admits no proper isometric embedding into a connected Lorentzian manifold with

C^{2}

metric form a residual set, meaning a countable intersection of open dense sets.

PDE-009

De Giorgi conjecture in dimensions $4$ through $8$

LandmarkConjecture1978

Let

n \in {4, 5, 6, 7, 8}

. If

u \in C^{2} (R^{n})

is bounded, satisfies

Δ u = u^{3} - u and \partial_{x_{n}} u > 0 on R^{n},

then

u

is one-dimensional: there are

ν \in S^{n - 1}

and

h \in C^{2} (R)

such that

u (x) = h (ν \cdot x)

for every

x \in R^{n}

PDE-010

Nonlinear Stability of Subextremal Kerr Black Holes

LandmarkConjecturec. 1965

For every fixed Kerr exterior with mass

m > 0

and angular momentum parameter

∣ a ∣ < m

, all sufficiently small asymptotically flat vacuum perturbations of compatible initial data have a complete exterior development that, after gauge adjustment, remains close to and asymptotically approaches a nearby Kerr exterior.

DYN-002

$C^r$ closing lemma

LandmarkConjecturec. 1960

Let

M

be a closed smooth manifold,

r \geq 2

f \in Diff^{r} (M)

, and

x \in M

a nonwandering point of

f

: every neighborhood

U ∋ x

has

f^{n} (U) \cap U \neq = \emptyset

for some

n > 0

. For every

C^{r}

neighborhood

U

f

, there is

g \in U

for which

g^{m} (x) = x

for some

m > 0

DYN-003

Density of hyperbolicity for rational maps

LandmarkConjecturec. 1920

For every

d \geq 2

, hyperbolic maps are dense in the space

Rat_{d}

of degree-

d

rational maps

f : C \to C

, with its coefficient topology. Here

f

is hyperbolic when the closure of the forward orbits of all its critical points is disjoint from its Julia set

J (f)

DYN-004

Mandelbrot local-connectivity conjecture

LandmarkConjecturec. 1982

The Mandelbrot set

M = {c \in C : {f_{c}^{n} (0) : n \geq 0} is bounded}, f_{c} (z) = z^{2} + c,

is locally connected: for every

c \in M

and every neighborhood

U

c

, there is a connected neighborhood

V

c

in the subspace

M

with

V \subset U

DYN-005

Birkhoff billiard conjecture

LandmarkConjecture1927

Let

Ω \subset R^{2}

be bounded with

C^{\infty}

, strictly convex boundary. Its billiard phase space is the open annulus

A = {(x, v) : x \in \partial Ω, ∣ v ∣ = 1, v points inward and is not tangent to \partial Ω}

, with the billiard map sending one reflected state to the next. If

A

is foliated by invariant circles homotopic to its boundary, then

\partial Ω

is an ellipse.

DYN-008

Positive metric entropy for the standard map

LandmarkOpen problemc. 1980

There exists

K \in R ∖ {0}

such that the area-preserving standard map

S_{K} (x, y) = (x + y + K sin (2 π x), y + K sin (2 π x)) (mod Z^{2})

T^{2}

has positive Kolmogorov--Sinai entropy with respect to normalized Lebesgue measure.

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-014

Sarnak Möbius disjointness conjecture

LandmarkConjecture2010

Define the Möbius function by

μ (1) = 1

μ (n) = 0

if a prime square divides

n

, and

μ (n) = (- 1)^{k}

n

is a product of

k

distinct primes. For every compact metric space

X

, every continuous map

T : X \to X

with zero topological entropy, every

f \in C (X; C)

, and every

x \in X

\frac{1}{N} n = 1 \sum N μ (n) f (T^{n} x) ⟶ 0 as N \to \infty.

COMB-001

Hadamard Matrix Conjecture

LandmarkConjecture1893

For every integer

m \geq 1

, there is a matrix

H \in {- 1, 1}^{4 m \times 4 m}

such that

H H^{T} = 4 m I_{4 m} .

Here

I_{4 m}

is the

4 m \times 4 m

identity matrix.

COMB-002

Union-Closed Sets Conjecture (Frankl's Conjecture)

LandmarkConjecture1979

Let

F

be a finite, nonempty family of finite sets such that

A \cup B \in F

for all

A, B \in F

, and assume

⋃ F \neq = \emptyset

. Then some element

x \in ⋃ F

belongs to at least

∣ F ∣ /2

members of

F

COMB-003

Erdős–Rado Sunflower Conjecture

LandmarkConjecture1960

For every integer

r \geq 3

there is a constant

C_{r} > 0

such that, for every

k \geq 1

, every family of more than

C_{r}^{k}

distinct

k

-element sets contains distinct

A_{1}, \dots, A_{r}

satisfying

A_{i} \cap A_{j} = A_{i^{'}} \cap A_{j^{'}} for all i \neq = j, i^{'} \neq = j^{'} .

(Such a family is an

r

-sunflower.)

COMB-009

Erdős–Szekeres Convex Polygon Conjecture

LandmarkConjecture1935

For

k \geq 3

, let

f (k)

be the least integer

N

such that every

N

-point set in the plane with no three collinear contains

k

points that are the vertices of their convex hull. Then

f (k) = 2^{k - 2} + 1.

COMB-014

Brown–Erdős–Sós Conjecture

LandmarkConjecture1973

For every integer

k \geq 3

and every real

δ > 0

, there is an integer

n_{0} = n_{0} (k, δ)

such that every

3

-uniform hypergraph

H = (V, E)

with

∣ V ∣ = n \geq n_{0}

and

∣ E ∣ \geq δ n^{2}

has distinct edges

e_{1}, \dots, e_{k}

satisfying

e_{1} \cup \dots \cup e_{k} \leq k + 3.

Here

3

-uniform means that every edge has exactly three vertices.

GRAPH-001

Hadwiger's Conjecture

LandmarkConjecture1943

Let

χ (G)

be the chromatic number of a finite simple graph

G

, and let

K_{q}

denote the complete graph on

q

vertices. Then

G

contains

K_{χ (G)}

as a minor; equivalently,

V (G)

has

χ (G)

pairwise-disjoint nonempty connected branch sets with at least one edge between every two branch sets.

GRAPH-002

Graph Reconstruction Conjecture

LandmarkConjecture1942

G

and

H

are finite simple graphs on the same number

n \geq 3

of vertices and the multisets of unlabeled graphs

{G - v : v \in V (G)} and {H - w : w \in V (H)}

are equal, then

G ≅ H

, where

G - v

denotes the induced graph obtained by deleting

v

GRAPH-003

Tutte's $5$ -Flow Conjecture

LandmarkConjecture1954

Every finite bridgeless loopless multigraph

G

admits an orientation of its edges and a function

φ : E (G) \to {1, 2, 3, 4}

such that, for every vertex

v

e \in δ^{+} (v) \sum φ (e) \equiv e \in δ^{-} (v) \sum φ (e) (mod 5) .

Here

δ^{+} (v)

and

δ^{-} (v)

are respectively the sets of edges directed out of and into

v

GRAPH-004

Berge–Fulkerson Conjecture

LandmarkConjecture1971–1972

Every finite bridgeless cubic loopless multigraph

G

has six perfect matchings

M_{1}, \dots, M_{6}

, repetitions allowed, such that every edge of

G

belongs to exactly two of the

M_{i}

GRAPH-009

Caccetta–Häggkvist Conjecture

LandmarkConjecture1978

Let

D

be a finite simple loopless digraph on

n

vertices with minimum outdegree at least

r \geq 1

. Then

D

contains a directed cycle of length at most

⌈ \frac{n}{r} ⌉ .

GRAPH-010

Sidorenko's Conjecture

LandmarkConjecture1986–1991

For every finite bipartite graph

H

and every symmetric measurable

W : [0, 1]^{2} \to [0, 1]

t (H, W) := \int_{[0, 1]^{V (H)}} uv \in E (H) \prod W (x_{u}, x_{v}) v \in V (H) \prod d x_{v} \geq (\int_{[0, 1]^{2}} W (x, y) d x d y)^{∣ E (H) ∣} .

GRAPH-011

Erdős–Hajnal Conjecture

LandmarkConjecture1977–1989

For every finite graph

H

, there exists

ε (H) > 0

such that every

n

-vertex simple graph

G

with no induced subgraph isomorphic to

H

has either a clique or an independent set of size at least

n^{ε (H)}

GRAPH-025

Gyárfás–Sumner Conjecture

LandmarkConjecture1975–1981

For every finite tree

T

and integer

t \geq 2

, there is an integer

c = c (T, t)

such that every finite simple graph

G

with chromatic number

χ (G) > c

and no clique on

t

vertices contains an induced subgraph isomorphic to

T

. Here

χ (G)

is the least number of colors in a proper vertex coloring, and an induced copy uses exactly the edges of

G

between its chosen vertices.

GRAPH-026

Lovász Hamiltonian-Path Conjecture

LandmarkConjecture1969

Every finite connected vertex-transitive graph has a Hamiltonian path. A graph is vertex-transitive if, for every two vertices

u, v

, it has an automorphism sending

u

v

; a Hamiltonian path visits every vertex exactly once.

GRAPH-027

Multicolor Triangle Ramsey Growth

LandmarkOpen problemc. 1970

Let

R_{k} (3)

be the least

N

such that every coloring of the edges of

K_{N}

with

k

colors contains a monochromatic triangle. Determine its exponential order, in particular whether

R_{k} (3) = k^{Θ (k)} (k \to \infty) .

DG-001

Hadwiger–Nelson Problem

LandmarkExact constant problem1950

Determine

χ (R^{2}) = min {k : \exists c : R^{2} \to {1, \dots, k}, ∥ x - y ∥_{2} = 1 \Rightarrow c (x) \neq = c (y)} .

DG-002

Erdős Distinct-Distances Conjecture

LandmarkConjecture1946

Let

g (n) = P \subset R^{2} ∣ P ∣ = n min {∥ x - y ∥_{2} : x, y \in P, x \neq = y} .

There is an absolute constant

c > 0

such that, for all

n \geq 2

g (n) \geq c \frac{n}{lo g n} .

DG-004

Falconer's Distance Set Conjecture

LandmarkConjecture1985

Let

d \geq 2

and let

E \subset R^{d}

be compact. Write

dim_{H}

for Hausdorff dimension. If

dim_{H} (E) > \frac{d}{2},

then its distance set

Δ (E) = {∥ x - y ∥_{2} : x, y \in E}

has positive one-dimensional Lebesgue measure.

DG-006

Hadwiger–Levi Illumination Conjecture

LandmarkConjecture1957–1960

Let

d \geq 2

, let

S^{d - 1}

be the unit sphere, and let

K \subset R^{d}

be a convex body. Say that a direction

u \in S^{d - 1}

illuminates

x \in \partial K

x + t u \in int K

for some

t > 0

. There exist at most

2^{d}

directions such that every point of

\partial K

is illuminated by at least one of them.

DG-007

Mahler Volume-Product Conjecture

LandmarkConjecture1939

For a convex body

K \subset R^{d}

containing

0

in its interior, put

K^{\circ} = {y : ⟨ x, y ⟩ \leq 1 \forall x \in K}

. If

K = - K

, then

vol (K) vol (K^{\circ}) \geq \frac{4 ^{d}}{d !} .

For arbitrary

K

, let

s (K)

be its Santaló point, the minimizer of

vol ((K - x)^{\circ})

over

x \in int K

. Then

vol (K) vol ((K - s (K))^{\circ}) \geq \frac{( d + 1 ) ^{d + 1}}{( d ! ) ^{2}} .

DG-009

Danzer's Problem

LandmarkOpen problemc. 1965

Does there exist a locally finite set

S \subset R^{2}

and a constant

C > 0

such that every convex set of area

1

meets

S

, while

∣ S \cap [- R, R]^{2} ∣ \leq C R^{2} for every R \geq 1 ?

DG-016

Toeplitz Square-Peg Conjecture

LandmarkConjecture1911

For every continuous injective map

γ : S^{1} \to R^{2}

, the Jordan curve

γ (S^{1})

contains four distinct points that are the vertices of a nondegenerate Euclidean square.

DG-017

Kneser–Poulsen Conjecture

LandmarkConjecture1954–1955

Let

d, N \geq 1

r > 0

, and

p_{1}, \dots, p_{N}, q_{1}, \dots, q_{N} \in R^{d}

satisfy

∥ q_{i} - q_{j} ∥_{2} \leq ∥ p_{i} - p_{j} ∥_{2} for all i, j .

Writing

B (x, r)

for the closed Euclidean ball and

vol_{d}

for

d

-dimensional Lebesgue measure, one has

vol_{d} (i = 1 ⋃ N B (q_{i}, r)) \leq vol_{d} (i = 1 ⋃ N B (p_{i}, r))

and

vol_{d} (i = 1 ⋂ N B (q_{i}, r)) \geq vol_{d} (i = 1 ⋂ N B (p_{i}, r)) .

DG-018

High-Dimensional Sphere-Packing Exponent

LandmarkOpen problemc. 1900

Let

Δ_{d}

be the supremal density of a packing of congruent balls in

R^{d}

. Determine the exponential asymptotics of

Δ_{d}

, equivalently determine

d \to \infty lim inf \frac{1}{d} lo g_{2} Δ_{d} and d \to \infty lim sup \frac{1}{d} lo g_{2} Δ_{d},

and decide whether these two quantities are equal.

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

OR-001

Metric-TSP subtour-LP $4/3$ conjecture

LandmarkConjecturec. 1980

For every integer

n \geq 3

, let

K_{n} = (V, E)

, and let

c : E \to R_{\geq 0}

satisfy

c_{{u, v}} \leq c_{{u, w}} + c_{{w, v}}

for all distinct

u, v, w

. Let

TSP (c)

be the minimum

c

-length of a Hamilton cycle, and define

HK (c) = min ⎩ ⎨ ⎧ e \in E \sum c_{e} x_{e} : x_{e} \geq 0, e \in δ (v) \sum x_{e} = 2 (v \in V), e \in δ (S) \sum x_{e} \geq 2 (\emptyset \neq = S ⊊ V) ⎭ ⎬ ⎫,

where

δ (S)

is the set of edges having exactly one endpoint in

S

. Then, with the supremum restricted to instances satisfying

HK (c) > 0

n, c sup \frac{TSP ( c )}{HK ( c )} = \frac{4}{3} .

OPT-001

Strongly polynomial linear programming

LandmarkOpen problem1983

There is an algorithm which, for every rational

A \in Q^{m \times n}

b \in Q^{m}

, and

c \in Q^{n}

, decides whether

max {c^{T} x : A x \leq b, x \in R^{n}}

is infeasible, unbounded, or has an optimum and, in the last case, returns an exact optimal solution, using at most

p (m, n)

elementary arithmetic operations and comparisons for one fixed polynomial

p

, while every intermediate rational number has encoding length polynomial in the total input encoding length.

OPT-002

Polynomial pivot rule for the simplex method

LandmarkOpen problemc. 1972

There exist a deterministic or randomized simplex pivot rule and a polynomial

p

such that, for every bounded nondegenerate rational linear program

max {c^{T} x : A x = b, x \geq 0}, A \in Q^{m \times n},

and every feasible starting basis, the simplex method using that rule reaches an optimal basis after at most

p (m, n)

pivots (in expectation over the rule's randomness in the randomized case).

TCS-002

$NP$ versus $coNP$

LandmarkOpen problemc. 1971

NP \neq = co NP,

where

NP

is nondeterministic polynomial time,

\overline{L} = {0, 1}^{*} ∖ L

, and

co NP = {L : \overline{L} \in NP}

TCS-003

$L$ versus $NL$

LandmarkOpen problemc. 1970

L \neq = N L ?

Here

L

and

N L

are the languages decidable by, respectively, deterministic and nondeterministic Turing machines using

O (lo g n)

work-tape cells on inputs of length

n

, with read-only input.

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-005

$P$ versus $NC$

LandmarkOpen problemc. 1980

NC \neq = P ?

Here

NC = ⋃_{k \geq 1} N C^{k}

, and

N C^{k}

consists of languages decided by logspace-uniform families of polynomial-size Boolean circuits with bounded fan-in and depth

O (lo g^{k} n)

;

P

is deterministic polynomial time.

TCS-007

Valiant's $VP$ versus $VNP$ Conjecture

LandmarkConjecture1979

Over

Q

V P \neq = V NP .

The class

V P

consists of polynomial families

(f_{n})

, with

f_{n} \in Q [x_{1}, \dots, x_{p (n)}]

for some polynomial

p

, whose degrees and arithmetic-circuit sizes are bounded by polynomials in

n

. The class

V NP

consists of polynomial families

(g_{n})

for which there are a polynomial

q

and a family

(h_{n}) \in V P

such that

g_{n} (x) = y \in {0, 1}^{q (n)} \sum h_{n} (x, y) .

TCS-008

Unique Games Conjecture

LandmarkConjecture2002

For every

ε, δ \in (0, 1)

, there is an alphabet size

q

, where

[q] = {1, \dots, q}

, such that the following promise problem is

NP

-hard. The input is a finite directed constraint graph in which every arc

u \to v

carries a permutation

π_{uv}

[q]

; a labeling

ℓ : V \to [q]

satisfies that arc when

ℓ (v) = π_{uv} (ℓ (u))

. Distinguish

YES: NO: some labeling satisfies at least 1 - ε of the constraints; every labeling satisfies at most δ of them.

TCS-009

Exponential Time Hypothesis

LandmarkConjecture1999

No deterministic algorithm decides satisfiability of

3

-CNF formulas with

n

variables in time

2^{o (n)}

, where a

3

-CNF is a conjunction of clauses, each containing at most three literals.

TCS-011

Graph Isomorphism in Polynomial Time

LandmarkOpen problemc. 1971

Is there a deterministic polynomial-time algorithm that, given adjacency matrices of two finite simple

n

-vertex graphs

G, H

, decides whether there exists a permutation

π

of their

n

vertices satisfying

uv \in E (G) ⟺ π (u) π (v) \in E (H) for all u, v ?

TCS-012

Deterministic Polynomial-Time Integer Factoring

LandmarkOpen problemc. 1975

Is there a deterministic algorithm that, on binary input

N \geq 2

, outputs the prime factorization of

N

in time polynomial in

lo g N

TCS-013

Existence of One-Way Functions

LandmarkOpen problem1976

Does there exist a polynomial-time computable, length-preserving function family

f_{n} : {0, 1}^{n} \to {0, 1}^{n}

such that, for every probabilistic polynomial-time algorithm

A

that outputs an

n

-bit string (or failure), and every polynomial

p

, for all sufficiently large

n

x \leftarrow {0, 1}^{n}, A Pr [f_{n} (A (1^{n}, f_{n} (x))) = f_{n} (x)] < \frac{1}{p ( n )} ?

TCS-014

Quantum PCP Conjecture

LandmarkConjecturec. 2006

There exist constants

q \in N

and

0 \leq a < b \leq 1

such that the following promise problem is

QM A

-hard: given an

n

-qubit Hamiltonian

H = \sum_{i = 1}^{m} H_{i}

, where

m = poly (n)

, each

H_{i}

acts on at most

q

qubits and

0 ⪯ H_{i} ⪯ I

, distinguish

λ_{m i n} (H) \leq am from λ_{m i n} (H) \geq bm,

where

λ_{m i n} (H)

is the least eigenvalue of

H

. Here

QM A

is bounded-error quantum polynomial-time verification with a polynomial-size quantum witness.

TCS-018

Matrix Multiplication Exponent $\omega=2$

LandmarkConjecturec. 1969

Over the concrete field

Q

, let

ω = in f {τ : two n \times n matrices can be multiplied using O (n^{τ + ε}) field operations for every ε > 0} .

Then

ω = 2.

TCS-023

$BQP$ versus $BPP$

LandmarkOpen problemc. 1994

BPP \neq = BQP ?

Here

BPP

is classical probabilistic polynomial time with error at most

1/3

, and

BQP

is the analogous class decided by polynomial-time-uniform, polynomial-size quantum circuits over a fixed universal gate set, measured at the end, with error at most

1/3

TCS-024

Deterministic Polynomial Identity Testing

LandmarkOpen problemc. 1980

Is there a deterministic polynomial-time algorithm which, given a division-free arithmetic circuit over

Q

with binary-encoded rational constants, decides whether the formal polynomial computed by the circuit is identically zero, in time polynomial in the circuit's binary encoding length?

TCS-026

Simple Stochastic Games in Polynomial Time

LandmarkOpen problem1992

A simple stochastic game is a finite directed graph whose vertices are partitioned into MAX, MIN, random, and two absorbing sink vertices labeled

0

and

1

. Every nonsink vertex has exactly two outgoing arcs. At a MAX or MIN vertex the corresponding player chooses the next vertex; at a random vertex each outgoing arc is chosen with probability

1/2

. Starting from a specified vertex

s

, MAX receives payoff

1

exactly when play eventually reaches sink

1

, and payoff

0

otherwise. If

val (s) = σ sup τ in f σ, τ Pr [reach sink 1],

where

σ

and

τ

range over strategies of MAX and MIN, is there a deterministic polynomial-time algorithm deciding whether

val (s) > \frac{1}{2}

TCS-028

Small-Set Expansion Hypothesis

LandmarkConjecture2010

For a finite

D

-regular graph

G = (V, E)

and a nonempty set

S \subseteq V

, define its edge expansion by

Φ_{G} (S) = \frac{∣ E ( S , V ∖ S ) ∣}{D ∣ S ∣},

where

E (S, V ∖ S)

is the set of edges with one endpoint in

S

and the other outside

S

. For every constant

η \in (0, 1/2)

, there is a rational constant

δ \in (0, 1/2)

such that the following promise problem is

NP

-hard, on input sizes for which

δ ∣ V ∣

is an integer:

YES: NO: some S \subseteq V with ∣ S ∣ = δ ∣ V ∣ has Φ_{G} (S) \leq η; every S \subseteq V with ∣ S ∣ = δ ∣ V ∣ has Φ_{G} (S) \geq 1 - η .

INFO-004

Main Conjecture for MDS Codes

LandmarkConjecture1955

Let

q

be a prime power and

2 \leq k \leq q - 1

. If

C \subseteq F_{q}^{n}

is a

k

-dimensional linear code whose minimum Hamming distance is

n - k + 1

, then

n \leq q + 1,

except that, when

q

is even and

k \in {3, q - 1}

, the asserted bound is

n \leq q + 2

. The Hamming distance between two words is the number of coordinates in which they differ; a code meeting the general bound

n - k + 1

is called maximum-distance separable (MDS).

MATH-PHYS-002

Haldane gap for the spin- $1$ Heisenberg chain

LandmarkConjecture1983

For every integer

L \geq 2

, on

(C^{3})^{\otimes L}

with periodic boundary conditions let

H_{L} = j = 1 \sum L S_{j} \cdot S_{j + 1}, S_{L + 1} = S_{1},

where

S_{j}

are the spin-

1

S U (2)

generators at site

j

. If

E_{0} (L) < E_{1} (L)

are its two lowest distinct eigenvalues, then

L \to \infty lim inf (E_{1} (L) - E_{0} (L)) > 0.

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-008

Quantum unique ergodicity

LandmarkConjecture1994

Let

(M, g)

be a closed connected Riemannian manifold with strictly negative sectional curvature, and let

- Δ_{g} φ_{j} = λ_{j}^{2} φ_{j}

∥ φ_{j} ∥_{L^{2}} = 1

, with

λ_{j} \to \infty

. For every classical order-zero pseudodifferential operator

A \in Ψ^{0} (M)

⟨ A φ_{j}, φ_{j} ⟩ ⟶ \int_{S^{*} M} σ_{0} (A) d L .

Here

S^{*} M = {(x, ξ) \in T^{*} M : ∣ ξ ∣_{g} = 1}

σ_{0} (A)

is the degree-zero principal symbol restricted to

S^{*} M

, and

L

is normalized Liouville probability measure.

MATH-PHYS-009

General spacetime Penrose inequality

LandmarkConjecture1973

Let

(M^{3}, g, k)

be a smooth, connected, orientable, complete asymptotically flat initial data set. Define its energy and momentum densities by

16 π μ = R_{g} + (tr_{g} k)^{2} - ∣ k ∣_{g}^{2}, 8 π J = div_{g} (k - (tr_{g} k) g),

assume the dominant energy condition

μ \geq ∣ J ∣_{g}

, and fix an asymptotically flat end. Let

Σ

be an outermost apparent horizon relative to that end, allowing a disjoint union of marginally outer trapped components

H + tr_{Σ} k = 0

and marginally inner trapped components

H - tr_{Σ} k = 0

. Define

A

to be the infimum of the total

g

-areas of smooth closed surfaces enclosing

Σ

relative to the chosen end. If the ADM energy-momentum of the end is

(E, P)

and

m_{ADM} = E^{2} - ∣ P ∣^{2}

, then

m_{ADM} \geq \frac{A}{16 π} .

Equality should occur only when the exterior data arise from a spacelike slice of the Schwarzschild spacetime.

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

GAME-003

Polynomial-Time Computation of a Bimatrix Nash Equilibrium

LandmarkOpen problem1994

Is there a deterministic polynomial-time algorithm that, given two rational payoff matrices

A, B \in Q^{m \times n}

, outputs mixed strategies

x \in Δ_{m}

and

y \in Δ_{n}

satisfying

x^{T} A y \geq x^{'}^{T} A y (x^{'} \in Δ_{m}), x^{T} B y \geq x^{T} B y^{'} (y^{'} \in Δ_{n})?

LOG-MODEL-001

Vaught Conjecture

LandmarkConjecture1961

Let

L

be a countable first-order language and

T

a complete

L

-theory. The number

I (T, ℵ_{0})

of isomorphism classes of countable models of

T

is either at most countable or exactly

2^{ℵ_{0}}

LOG-DEC-005

Decidability of the Real Exponential Field

LandmarkOpen problemc. 1950

There exists an algorithm which, given any first-order sentence

φ

in the language

{0, 1, +, \cdot, <, exp}

, halts and correctly decides whether

(R; 0, 1, +, \cdot, <, x \mapsto e^{x}) ⊨ φ .

LOG-INF-006

Shelah’s Categoricity Conjecture for $L_{\omega_1,\omega}$

LandmarkConjecturec. 1977

Let

ψ

be a sentence of the countable infinitary logic

L_{ω_{1}, ω}

, which permits countable conjunctions and disjunctions but only finite strings of quantifiers. If

ψ

has, up to isomorphism, exactly one model of some cardinality

λ \geq ℶ_{ω_{1}}

, then it has exactly one model of every cardinality

μ \geq ℶ_{ω_{1}}

, where

ℶ_{0} = ℵ_{0}

ℶ_{α + 1} = 2^{ℶ_{α}}

, and

ℶ_{λ} = sup_{α < λ} ℶ_{α}

at limit ordinals.

LOG-SET-007

HOD Conjecture

LandmarkConjecturec. 2010

Assume there is an extendible cardinal, meaning a cardinal

δ

such that for every ordinal

λ > δ

there are an ordinal

θ

and an elementary embedding

j : V_{λ} \to V_{θ}

with critical point

δ

and

j (δ) > λ

. Then there is a proper class of regular cardinals

κ

that are not

ω

-strongly measurable in

HOD

. Here

HOD

is the class of hereditarily ordinal-definable sets, and a regular

κ

ω

-strongly measurable in

HOD

if there is

η < κ

with

(2^{η})^{HOD} < κ

such that

HOD

has no partition of

S_{ω}^{κ} = {α < κ : cf (α) = ω}

into

η

stationary sets.