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

NT-AN-001

Birch–Swinnerton-Dyer Conjecture

IconicConjecture1965

Let

E / Q

be an elliptic curve. Write

E (Q) ≅ E (Q)_{tors} \oplus Z^{r}

, and let

L (E, s)

be the Hasse–Weil

L

-function of

E

, continued to an entire function by modularity. Then

ord_{s = 1} L (E, s) = r .

NT-ADD-005

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

Landau’s $n^2+1$ Prime Conjecture

MajorConjecture1912

There are infinitely many positive integers

n

for which

n^{2} + 1

is prime.

NT-PRIME-008

Artin’s Primitive Root Conjecture

MajorConjecture1927

Let

g \in Z ∖ {- 1, 0, 1}

be not a perfect square. For

n \geq 1

, let

ζ_{n} = e^{2 πi / n}

, let

μ (n)

be the Möbius function (zero if a prime square divides

n

, and

(- 1)^{r}

n

is a product of

r

distinct primes), and put

δ (g) = n = 1 \sum \infty \frac{μ ( n )}{[ Q ( ζ _{n} , g ^{1/ n} ) : Q ]} .

Then

δ (g) > 0

and, as

x \to \infty

# {p \leq x : p prime, p ∤ g, g generates (Z / p Z)^{\times}} \sim δ (g) Li (x),

where

Li (x) = \int_{2}^{x} d t / lo g t

; the field in the denominator is independent of the choice of the

n

-th root of

g

NT-DIO-011

Lehmer’s Mahler-Measure Conjecture

MajorExact constant problem1933

There exists a real constant

c > 1

such that every algebraic integer

α \neq = 0

that is not a root of unity satisfies

M (α) \geq c,

where, if

a_{0} \prod_{j = 1}^{d} (x - α_{j}) \in Z [x]

is the minimal polynomial of

α

, then

M (α) = ∣ a_{0} ∣ \prod_{j = 1}^{d} max (1, ∣ α_{j} ∣)

NT-MOD-019

Lehmer’s Nonvanishing Conjecture for Ramanujan’s $\tau$ -function

MajorConjecture1947

Define integers

τ (n)

n = 1 \sum \infty τ (n) q^{n} = q m = 1 \prod \infty (1 - q^{m})^{24} (∣ q ∣ < 1) .

Then

τ (n) \neq = 0

for every integer

n \geq 1

NT-DIOAPP-020

Irrationality of the Euler–Mascheroni Constant

MajorOpen problemUnknown

The number

γ = n \to \infty lim (k = 1 \sum n \frac{1}{k} - lo g n)

is irrational.

NT-LATTICE-027

Gauss Circle-Problem Exponent Conjecture

MajorExact constant problemc. 1915

For

R \geq 1

, let

P (R) = # {(m, n) \in Z^{2} : m^{2} + n^{2} \leq R^{2}} - π R^{2} .

Then for every

ε > 0

P (R) = O_{ε} (R^{1/2 + ε}) (R \to \infty) .

NT-AN-028

Dirichlet Divisor-Problem Exponent Conjecture

MajorExact constant problemc. 1916

Let

d (n) = # {a \in Z_{> 0} : a ∣ n}

and

γ = lim_{N \to \infty} (\sum_{k = 1}^{N} 1/ k - lo g N)

, and put

Δ (x) = n \leq x \sum d (n) - x lo g x - (2 γ - 1) x .

For every

ε > 0

Δ (x) = O_{ε} (x^{1/4 + ε}) (x \to \infty) .

NT-SPECTRAL-029

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.

ALG-NC-003

Dixmier Conjecture for the First Weyl Algebra

MajorCanonical finite case1968

Let

A_{1} (C) = C ⟨ x, y ⟩ / (y x - x y - 1)

be the first Weyl algebra. Every unital

C

-algebra endomorphism

A_{1} (C) \to A_{1} (C)

is an automorphism.

ALG-RING-004

Kaplansky Zero-Divisor Conjecture

MajorConjecturec. 1940

K

is a field and

G

is a torsion-free group, then the group algebra

K [G]

has no nonzero zero divisors: for all

a, b \in K [G]

ab = 0

implies

a = 0

b = 0

ALG-RING-005

Kaplansky Idempotent Conjecture

MajorConjecturec. 1950

G

is a torsion-free group and

e \in C [G]

satisfies

e^{2} = e

, then

e = 0

e = 1

ALG-RING-006

Kaplansky Direct-Finiteness Conjecture

MajorConjecturec. 1940

For every field

K

, every group

G

, and all

a, b \in K [G]

, if

ab = 1

, then

ba = 1

ALG-RING-007

Finitistic Dimension Conjecture

MajorConjecture1960

Let

A

be a finite-dimensional algebra over a field, and let

pd_{A} M

denote the projective dimension of a finitely generated left

A

-module

M

. Then

findim (A) = sup {pd_{A} M : M \in A - mod, pd_{A} M < \infty} < \infty.

ALG-REP-009

Broué’s Abelian Defect Group Conjecture

MajorConjecture1990

Let

p

be a prime, let

(K, O, k)

be a splitting

p

-modular system for a finite group

G

O

is a complete discrete valuation ring with characteristic-

0

fraction field

K

and algebraically closed residue field

k

of characteristic

p

, and both fields split every subgroup of

G

. Let

B

be a block algebra of

O G

with abelian defect group

D

. If

b

is the Brauer-correspondent block of

O N_{G} (D)

, then

D^{b} (B - mod_{fg}) ≃ D^{b} (b - mod_{fg})

as triangulated categories, where these are bounded derived categories of finitely generated left modules.

ALG-MODREP-012

Andrews–Curtis Conjecture

MajorConjecture1965

For every integer

n \geq 1

, let

F_{n} = ⟨ x_{1}, \dots, x_{n} ⟩

be the free group. If

r = (r_{1}, \dots, r_{n}) \in F_{n}^{n}

has normal closure

F_{n}

, then

r

can be transformed to

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

by finitely many moves

r_{i} \mapsto r_{i}^{- 1}, r_{i} \mapsto r_{i} r_{j} (i \neq = j), r_{i} \mapsto w r_{i} w^{- 1} (w \in F_{n}),

their inverses, and permutations of the entries.

ALG-GROUP-015

Boone–Higman Conjecture

MajorConjecture1974

Every finitely generated group with solvable word problem embeds into a finitely presented simple group.

ALG-L2-017

Strong Atiyah Conjecture

MajorConjecture1976

Let

G

be a discrete group for which the orders of finite subgroups are bounded, and put

L = lcm {∣ H ∣ : H \leq G finite}

. For all

m, n \geq 1

and every matrix

A \in M_{m, n} (C G)

, let

r_{A} : ℓ^{2} (G)^{m} \to ℓ^{2} (G)^{n}

be the bounded

G

-equivariant operator given by right convolution by

A

. Then

L dim_{N (G)} ker r_{A} \in Z,

where

N (G)

is the group von Neumann algebra and

dim_{N (G)}

is its von Neumann dimension.

ALG-MODREP-019

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

AG-CYCLE-002

Lefschetz Standard Conjecture $B$

MajorConjecture1968

Let

X

be a smooth projective variety of dimension

d

over an algebraically closed field, let

H^{*}

be a Weil cohomology theory with characteristic-

0

coefficient field, and let

L (α) = h ⌣ α

for the class

h

of an ample divisor. For every

i < d

, the inverse of the hard-Lefschetz isomorphism

L^{d - i} : H^{i} (X) \sim H^{2 d - i} (X)

is induced by an algebraic correspondence in

CH^{i} (X \times X) \otimes Q

, where

CH^{i}

denotes codimension-

i

algebraic cycles modulo rational equivalence.

AG-UNLIKELY-008

Zilber–Pink Conjecture for Abelian Varieties

MajorConjecture1999–2005

Let

A

be a complex abelian variety. For

s \geq 0

, let

A^{[s]}

be the union of all torsion cosets

τ + B

, where

τ \in A

is a torsion point and

B \subseteq A

is an abelian subvariety with

codim_{A} B \geq s

. If

X \subseteq A

is an irreducible closed subvariety not contained in any proper torsion coset, then

X \cap A^{[d i m X + 1]}

is not Zariski dense in

X

AG-SURF-009

Hartshorne Complete-Intersection Conjecture

MajorConjecture1974

X \subset P_{C}^{n}

is a smooth closed subvariety with

dim X > 2 n /3

, then

X

is a complete intersection in

P^{n}

: its homogeneous ideal is generated by

codim_{P^{n}} X

homogeneous polynomials.

AG-ADJ-015

Irrationality of a Very General Cubic Fourfold

MajorOpen problemc. 1969

A very general smooth cubic hypersurface

X \subset P_{C}^{5}

, meaning one outside a countable union of proper Zariski-closed subsets of the parameter space, is not rational over

C

AG-RAT-018

Kuznetsov’s Rationality Conjecture for Cubic Fourfolds

MajorConjecture2010

Let

X \subset P_{C}^{5}

be a smooth cubic fourfold. In the bounded derived category

D^{b} (Coh X)

of coherent sheaves on

X

, put

A_{X} = ⟨ O_{X}, O_{X} (1), O_{X} (2) ⟩^{⊥},

where

^{⊥}

denotes the full right-orthogonal subcategory. Then

X

is rational if and only if there is a complex K3 surface

S

with an exact

C

-linear triangulated equivalence

A_{X} ≃ D^{b} (Coh S)

AG-CONE-019

Morrison–Kawamata Cone Conjecture

MajorConjecture1993–1997

Let

(X, Δ)

be a projective

Q

-factorial Kawamata-log-terminal pair over

C

with

K_{X} + Δ \equiv 0

, and put

Nef^{e} (X) = Nef (X) \cap Eff (X)

inside

N^{1} (X)_{R}

, where

Eff (X)

is the cone generated by classes of effective Cartier divisors. There is a rational polyhedral cone

Π \subset Nef^{e} (X)

such that

Nef^{e} (X) = g \in Aut (X, Δ) ⋃ g^{*} Π,

and interiors of

g^{*} Π

and

h^{*} Π

are disjoint unless the cones coincide.

AG-ZERO-020

Bloch Conjecture for Surfaces with $p_g=0$

MajorConjecture1975

Let

X

be a smooth projective complex surface with

p_{g} (X) = h^{0} (X, K_{X}) = 0

. The Albanese map

alb_{X} : CH_{0} (X)^{0} ⟶ Alb (X) (C)

from degree-zero zero-cycles modulo rational equivalence is an isomorphism.

GEO-TOP-001

Smooth four-dimensional Poincaré conjecture

IconicConjecturec. 1960

Every closed, connected, smooth

4

-manifold

M

that is homotopy equivalent to the standard sphere

S^{4}

is diffeomorphic to

S^{4}

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.

GEO-TOP-003

K-theoretic Farrell–Jones isomorphism conjecture

MajorConjecture1993

For every discrete group

G

, every associative unital ring

R

, and every integer

n

, the assembly map

H_{n}^{G} (E_{VCyc} G; K_{R}) ⟶ K_{n} (RG)

is an isomorphism. Here

E_{VCyc} G

is the terminal

G

-CW complex whose

H

-fixed points are contractible for virtually cyclic

H \leq G

and empty otherwise, and

H_{*}^{G} (-; K_{R})

is the equivariant homology theory whose value at

G / H

K_{*} (R H)

GEO-TOP-009

Bott rational-ellipticity conjecture

MajorConjecturec. 1982

M

is a closed simply connected smooth manifold that admits a Riemannian metric of nonnegative sectional curvature, then

M

is rationally elliptic, meaning

i \geq 2 \sum dim_{Q} (π_{i} (M) \otimes Q) < \infty.

GEO-TOP-011

Cartan–Hadamard isoperimetric conjecture

MajorConjecture1976

Let

(M^{n}, g)

be a complete simply connected Riemannian

n

-manifold with sectional curvature

K \leq 0

, and let

Ω \subset M

be a relatively compact domain with smooth boundary. Then

Area_{g} (\partial Ω) \geq n ω_{n}^{1/ n} Vol_{g} (Ω)^{(n - 1) / n},

where

ω_{n}

is the Euclidean volume of the unit ball in

R^{n}

GEO-TOP-012

Positive sectional curvature on $S^2\times S^2$

MajorOpen problemc. 1965

There exists a smooth Riemannian metric

g

S^{2} \times S^{2}

such that every

2

-plane

σ \subset T_{x} (S^{2} \times S^{2})

, at every

x

, has sectional curvature

K_{g} (σ) > 0

GEO-TOP-013

Purely cosmetic surgery conjecture

MajorConjecture1990

Let

K \subset S^{3}

be a nontrivial knot and, for each slope

t \in Q \cup {\infty}

in the meridian--longitude basis, let

S_{t}^{3} (K)

denote the result of

t

-Dehn filling its exterior. If

r, s \in Q \cup {\infty}

and

S_{r}^{3} (K)

and

S_{s}^{3} (K)

are orientation-preservingly homeomorphic, then

r = s

GEO-TOP-019

$L$ -space conjecture

MajorConjecture2013–2015

Let

Y

be a closed, connected, orientable, irreducible rational-homology

3

-sphere, and let

H F (Y; F_{2})

denote its hat Heegaard Floer homology. The following are equivalent: (i)

rank_{F_{2}} H F (Y; F_{2}) > ∣ H_{1} (Y; Z) ∣

, so

Y

is not an

L

-space; (ii)

π_{1} (Y)

admits a total order

<

satisfying

g < h \Rightarrow f g < f h

for all

f, g, h

; (iii)

Y

admits a coorientable taut codimension-one foliation.

GEO-TOP-020

Hyperbolic volume conjecture

MajorConjecture1997

Let

K \subset S^{3}

be a hyperbolic knot and let

J_{N} (K; q)

be its

N

-colored Jones polynomial normalized by

J_{N} (unknot; q) = 1

. Then

N \to \infty lim \frac{2 π}{N} lo g J_{N} (K; e^{2 πi / N}) = Vol (S^{3} ∖ K),

where the right-hand side is the complete finite-volume hyperbolic volume.

GEO-DIFF-021

Carath\u00e9odory Umbilic Conjecture

MajorConjecture1924

Every closed

C^{2}

, strictly convex surface embedded in

R^{3}

has at least two umbilic points, where the two principal curvatures are equal.

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.

ANAL-FA-002

Separable quotient problem

MajorOpen problem1932

Every infinite-dimensional Banach space

X

has a closed linear subspace

Y \subset X

such that the quotient Banach space

X / Y

is both separable and infinite-dimensional.

ANAL-FA-004

Mazur rotation problem

MajorOpen problem1932

Let

X

be a separable real Banach space such that for every

x, y \in X

with

∥ x ∥ = ∥ y ∥ = 1

, there is a surjective linear isometry

U : X \to X

with

Ux = y

. Then

X

is linearly isometric to a real Hilbert space.

ANAL-FA-005

Beurling–Ahlfors operator norm conjecture

MajorExact constant problem1982

For

1 < p < \infty

, let

d A

be Lebesgue area measure and define the Beurling--Ahlfors transform on Schwartz functions by

B f (z) = - \frac{1}{π} p.v. \int_{C} \frac{f ( w )}{( z - w ) ^{2}} d A (w), p^{*} = max {p, \frac{p}{p - 1}} .

Then its

L^{p} (C)

-operator norm is

∥ B ∥_{L^{p} \to L^{p}} = p^{*} - 1

ANAL-FA-011

Corona problem for the unit ball

MajorOpen problemc. 1962

Let

n \geq 2

and

m \geq 1

be integers, let

B^{n} = {z \in C^{n} : ∥ z ∥_{2} < 1}

, and let

H^{\infty} (B^{n})

be the algebra of bounded holomorphic functions on

B^{n}

. If

f_{1}, \dots, f_{m} \in H^{\infty} (B^{n})

satisfy

z \in B^{n} in f j = 1 \sum m ∣ f_{j} (z) ∣ > 0,

then there exist

g_{1}, \dots, g_{m} \in H^{\infty} (B^{n})

such that

\sum_{j = 1}^{m} f_{j} (z) g_{j} (z) = 1

for every

z \in B^{n}

ANAL-FA-013

Two-dimensional Fuglede conjecture

MajorCanonical finite case1974

Let

Ω \subset R^{2}

be a bounded Lebesgue measurable set of positive measure. The following are equivalent: (i) there is a countable

Λ \subset R^{2}

such that

{∣Ω ∣^{- 1/2} e^{2 πiλ \cdot x} : λ \in Λ}

is an orthonormal basis of

L^{2} (Ω)

; (ii) there is a countable

T \subset R^{2}

such that

\sum_{t \in T} 1_{Ω} (x - t) = 1

for almost every

x \in R^{2}

ANAL-FA-016

Diagonal Fourier extension conjecture for compact paraboloids

MajorConjecturec. 1967

Let

d \geq 3

, let

P^{d - 1} = {(ξ, ∣ ξ ∣^{2}) : ξ \in R^{d - 1}} \subset R^{d}

, and let

d σ = η d S

, where

d S

is surface measure and

0 \leq η \in C_{c}^{\infty} (P^{d - 1})

is nonzero. Define

E_{σ} f (x) = \int_{P^{d - 1}} e^{2 πi x \cdot ω} f (ω) d σ (ω) .

For every

q > 2 d / (d - 1)

there is a constant

C = C (d, q, σ)

such that

∥ E_{σ} f ∥_{L^{q} (R^{d})} \leq C ∥ f ∥_{L^{q} (d σ)}

for every

f \in L^{q} (d σ)

ANAL-FA-019

Connes Rigidity Conjecture for Property- $(T)$ Groups

MajorConjecturec. 1982

G

and

H

are countable ICC groups with Kazhdan's property

(T)

, then every isomorphism of their group von Neumann algebras,

L (G) ≅ L (H),

implies that

G ≅ H

. Here ICC means that every nonidentity conjugacy class is infinite.

ANAL-FA-020

Hyperlinear Group Conjecture

MajorConjecturec. 2000

Every countable group

G

is hyperlinear: there are integers

n_{k}

and an injective homomorphism

G ⟶ k \prod U (n_{k}) / k ⨁ U (n_{k}),

where the metric ultraproduct uses normalized Hilbert--Schmidt distance and a nonprincipal ultrafilter.

ANAL-FA-021

Heil–Ramanathan–Topiwala Conjecture

MajorConjecture1996

For every nonzero

g \in L^{2} (R)

and every finite set of distinct points

(a_{j}, b_{j}) \in R^{2}

, the time--frequency translates

e^{2 πi b_{j} x} g (x - a_{j})

are linearly independent in

L^{2} (R)

PDE-001

Three-dimensional Navier–Stokes existence and smoothness

IconicOpen problem1934

Let

u_{0} : R^{3} \to R^{3}

C^{\infty}

, divergence-free, and satisfy

sup_{x} (1 + ∣ x ∣)^{N} ∣ \partial^{α} u_{0} (x) ∣ < \infty

for every

N

and multi-index

α

. There exist

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

and

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

satisfying

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

for all

t \geq 0

, with

sup_{0 \leq t \leq T} \int_{R^{3}} ∣ u (x, t) ∣^{2} d x < \infty

for every

T < \infty

PDE-007

Weak cosmic censorship (future-null-infinity form)

IconicConjecture1969

Let

D_{AF}

be the space of smooth, complete vacuum initial data

(h, K)

R^{3}

satisfying

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

and

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

. In fixed asymptotic coordinates, put

r = ∣ x ∣

and require

\partial^{α} (h_{ij} - δ_{ij}) = O (r^{- 1 - ∣ α ∣})

and

\partial^{α} K_{ij} = O (r^{- 2 - ∣ α ∣})

for every multi-index

α

. Give

D_{AF}

the relative weighted

C^{\infty}

topology induced by the seminorms

q_{m} (γ, L) = ∣ α ∣ \leq m \sum x sup (1 + r)^{1 + ∣ α ∣} ∣ \partial^{α} γ ∣ + ∣ α ∣ \leq m \sum x sup (1 + r)^{2 + ∣ α ∣} ∣ \partial^{α} L ∣

on differences

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

. There is an open dense subset of

D_{AF}

whose maximal globally hyperbolic developments have a conformal completion with complete future null infinity

I^{+}

, meaning that every physical null geodesic ending at

I^{+}

has infinite affine length.

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.

PDE-004

Global regularity for three-dimensional incompressible MHD

MajorOpen problemc. 1950

For every pair of smooth divergence-free vector fields

u_{0}, b_{0} : T^{3} \to R^{3}

, the unique local smooth solution of

\partial_{t} u + (u \cdot \nabla) u - (b \cdot \nabla) b + \nabla p \partial_{t} b + (u \cdot \nabla) b - (b \cdot \nabla) u \nabla \cdot u = \nabla \cdot b (u, b) ∣_{t = 0} = Δ u, = Δ b, = 0, = (u_{0}, b_{0})

extends smoothly for all

t \geq 0

PDE-005

Global regularity for the two-dimensional inviscid Boussinesq system

MajorOpen problemc. 1980

For every

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

and

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

with

\nabla \cdot u_{0} = 0

, the maximal classical solution of

\partial_{t} u + (u \cdot \nabla) u + \nabla p = θ e_{2}, \partial_{t} θ + u \cdot \nabla θ = 0, \nabla \cdot u = 0, (u, θ) ∣_{t = 0} = (u_{0}, θ_{0})

exists for all

t \geq 0

and is smooth.

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

Uniform finiteness in Hilbert's sixteenth problem

IconicOpen problem1900

For every integer

d \geq 2

, there is an integer

H (d) < \infty

such that every planar polynomial vector field

\overset{x}{˙} = P (x, y), \overset{y}{˙} = Q (x, y), max {de g P, de g Q} \leq d,

having only finitely many limit cycles has at most

H (d)

limit cycles. A limit cycle is an isolated periodic orbit.

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.

DYN-006

Ivrii periodic-billiard conjecture

MajorConjecture1980

Let

Ω \subset R^{n}

be a bounded domain with

C^{\infty}

boundary, and let

B^{*} \partial Ω = {(x, ξ) \in T^{*} \partial Ω : ∣ ξ ∣ < 1}

, equipped with its canonical Liouville measure. The set of points of

B^{*} \partial Ω

that are periodic under the billiard map has measure zero.

DYN-007

Anosov-manifold conjecture

MajorConjecturec. 1970

Every closed connected smooth manifold that admits an Anosov diffeomorphism is homeomorphic to an infranilmanifold, namely a quotient

Γ\ N

, where

N

is a simply connected nilpotent Lie group and

Γ

is a torsion-free discrete subgroup of

N ⋊ C

for some compact subgroup

C \leq Aut (N)

, acting freely and cocompactly on

N

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

Banach simple-Lebesgue-spectrum problem

MajorOpen problem1932

There exist a standard nonatomic probability space

(X, B, μ)

and an invertible ergodic measure-preserving transformation

T : X \to X

such that the Koopman operator

U_{T} f = f \circ T

, restricted to

L_{0}^{2} (X, μ) = {f \in L^{2} (X, μ) : \int_{X} f d μ = 0},

is unitarily equivalent to the bilateral shift

S

ℓ^{2} (Z)

, defined by

S (e_{n}) = e_{n + 1}

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.

DYN-013

Improbability of noncollision singularities

MajorConjecturec. 1984

Fix

N \geq 5

and masses

m_{1}, \dots, m_{N} > 0

. For

q_{i} (t) \in R^{3}

, consider

\overset{q}{¨}_{i} = j \neq = i \sum m_{j} \frac{q _{j} - q _{i}}{∣ q _{j} - q _{i} ∣ ^{3}}, i = 1, \dots, N,

and the collision-free phase space

P = {(q_{1}, \dots, q_{N}, \overset{q}{˙}_{1}, \dots, \overset{q}{˙}_{N}) : q_{i} \neq = q_{j} for i \neq = j} \subset R^{6 N}

. With respect to Lebesgue measure on

P

, the set of initial conditions whose maximal solution has a finite endpoint

T < \infty

while

i \neq = j min ∣ q_{i} (t) - q_{j} (t) ∣ \neq ⟶ 0 as t ↑ T

has measure zero.

DYN-015

Gottschalk Surjunctivity Conjecture

MajorConjecture1973

For every group

G

and every finite alphabet

A

, every continuous

G

-equivariant injective map

τ : A^{G} \to A^{G}

, with

A^{G}

carrying the product topology and the shift action, is surjective.

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.

COMB-004

Lonely Runner Conjecture

MajorConjecture1967

For every integer

n \geq 2

and every set of distinct positive integers

v_{1}, \dots, v_{n - 1}

, there exists

t \in R

such that

∥ t v_{i} ∥_{R / Z} \geq \frac{1}{n} (1 \leq i \leq n - 1),

where

∥ x ∥_{R / Z} = min_{z \in Z} ∣ x - z ∣

COMB-006

Ryser–Brualdi–Stein Latin Transversal Conjecture

MajorConjecture1967–1975

Let

L

be a Latin square of order

n

, meaning an

n \times n

array on

n

symbols in which every symbol occurs once in every row and every column. A partial transversal is a set of cells using no row, column, or symbol twice. Then:

every L has a partial transversal of size n - 1,

and, if

n

is odd, every

L

has a transversal of size

n

COMB-007

Rota's Basis Conjecture

MajorConjecturec. 1989

Let

V

be an

n

-dimensional vector space over a field, and let

B_{1}, \dots, B_{n}

n

(not necessarily distinct) bases of

V

. It is possible to order each

B_{i} = (b_{i 1}, \dots, b_{in})

so that

{b_{1 j}, \dots, b_{nj}}

is a basis of

V

for every

j \in {1, \dots, n}

COMB-008

Turán's Tetrahedron Conjecture

MajorConjecture1941

Let

K_{4}^{(3)}

be the

3

-uniform hypergraph consisting of all four triples on a four-element vertex set, and let

ex (n, K_{4}^{(3)})

be the largest number of edges in an

n

-vertex

K_{4}^{(3)}

-free

3

-uniform hypergraph. Then

n \to \infty lim \frac{ex ( n , K _{4}^{(3)} )}{( 3 n )} = \frac{5}{9} .

COMB-010

Ryser's Conjecture for $r$ -Partite Hypergraphs

MajorConjecturec. 1971

H

is an

r

-uniform

r

-partite hypergraph (its vertices split into

r

classes and every edge contains exactly one vertex from each class), let

ν (H)

be the largest size of a family of pairwise disjoint edges and let

τ (H)

be the smallest size of a vertex set meeting every edge. Then

τ (H) \leq (r - 1) ν (H) .

COMB-011

Alon–Tarsi Latin Square Conjecture

MajorConjecture1990

Let

n

be even. Regard every row and every column of a Latin square

L

of order

n

as a permutation of its symbol set, and define

sgn (L) = i = 1 \prod n sgn (row_{i}) j = 1 \prod n sgn (column_{j}) .

The number of Latin squares of order

n

with sign

+ 1

is different from the number with sign

- 1

COMB-012

Existence of a Finite Projective Plane of Order $12$

MajorCanonical finite caseUnknown

Do there exist sets

P

(points) and

L

(lines), each of size

1 2^{2} + 12 + 1 = 157

, and an incidence relation

I \subseteq P \times L

, such that every line is incident with exactly

13

points, every point is incident with exactly

13

lines, every two distinct points lie on exactly one common line, and every two distinct lines meet in exactly one point?

COMB-013

1/3–2/3 Conjecture for Posets

MajorConjecture1968

Let

P = (X, \leq_{P})

be a finite poset that is not a chain, and let

L (P)

be its set of linear extensions. For incomparable

x, y \in X

, put

p_{P} (x, y) = \frac{∣{ L \in L ( P ) : x < _{L} y }∣}{∣ L ( P )∣} .

Then some incomparable pair

x, y

satisfies

\frac{1}{3} \leq p_{P} (x, y) \leq \frac{2}{3} .

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

GRAPH-005

Barnette's Conjecture

MajorConjecture1969

Every finite simple, cubic, bipartite, planar,

3

-vertex-connected graph has a Hamiltonian cycle.

GRAPH-006

Total Coloring Conjecture

MajorConjecture1964–1965

A total coloring of a finite simple graph

G

assigns colors to

V (G) \cup E (G)

so that adjacent vertices, adjacent edges, and every incident vertex--edge pair receive different colors. If

χ^{''} (G)

is the least number of colors in such a coloring, then

χ^{''} (G) \leq Δ (G) + 2.

Here

Δ (G)

is the maximum vertex degree of

G

GRAPH-007

List Edge-Coloring Conjecture

MajorConjecturec. 1975

For every finite loopless multigraph

G

χ_{ℓ}^{'} (G) = χ^{'} (G),

where

χ^{'} (G)

is its edge-chromatic number and

χ_{ℓ}^{'} (G)

is the least

k

such that, whenever every edge

e

is assigned a list

L (e)

of at least

k

colors, a proper edge coloring

c (e) \in L (e)

exists.

GRAPH-008

Graceful Tree Conjecture

MajorConjecture1963–1967

Every tree

T

with

m

edges admits a bijection

ℓ : V (T) \to {0, 1, \dots, m}

such that

{∣ ℓ (u) - ℓ (v) ∣ : uv \in E (T)} = {1, 2, \dots, m} .

GRAPH-012

Conway's Thrackle Conjecture

MajorConjecture1969

Let a finite simple graph

G

be drawn in the plane with vertices as distinct points and edges as simple arcs, with no edge through a nonincident vertex and no three edges meeting at an interior point. Suppose every pair of distinct edges meets exactly once, either at their common endpoint or in one proper crossing. Then

∣ E (G) ∣ \leq ∣ V (G) ∣.

GRAPH-013

Harary–Hill Conjecture for the Crossing Number of $K_n$

MajorExact constant problem1960–1963

Let

cr (G)

be the minimum number of pairwise edge crossings over plane drawings of a graph

G

in general position. For every integer

n \geq 1

cr (K_{n}) = \frac{1}{4} ⌊ \frac{n}{2} ⌋ ⌊ \frac{n - 1}{2} ⌋ ⌊ \frac{n - 2}{2} ⌋ ⌊ \frac{n - 3}{2} ⌋ .

GRAPH-014

Albertson's Crossing-Number Conjecture

MajorConjecture2007

Every finite simple graph

G

satisfies

cr (G) \geq cr (K_{χ (G)}) .

Here

cr (G)

is the minimum number of edge crossings in a plane drawing of

G

χ (G)

is its chromatic number, and

K_{q}

is the complete graph on

q

vertices.

GRAPH-015

Erdős–Gyárfás Power-of-Two Cycle Conjecture

MajorConjecture1995

Every finite simple graph of minimum degree at least

3

contains a cycle whose length is a power of

2

GRAPH-016

Tuza's Triangle Packing–Covering Conjecture

MajorConjecture1981

For a finite simple graph

G

, let

ν_{3} (G)

be the maximum number of pairwise edge-disjoint triangles and let

τ_{3} (G)

be the minimum number of edges meeting every triangle. Then

τ_{3} (G) \leq 2 ν_{3} (G) .

GRAPH-017

Reed's $\Delta$ – $\omega$ Chromatic Conjecture

MajorConjecture1998

Every finite simple graph

G

satisfies

χ (G) \leq ⌈ \frac{Δ ( G ) + 1 + ω ( G )}{2} ⌉,

where

Δ (G)

is the maximum degree and

ω (G)

the clique number.

GRAPH-018

Linear Arboricity Conjecture

MajorConjecture1980–1981

Let

la (G)

be the least number of linear forests (forests whose components are paths, including isolated edges) whose edge sets partition

E (G)

. Every finite simple graph

G

with maximum degree

Δ (G)

satisfies

la (G) \leq ⌈ \frac{Δ ( G ) + 1}{2} ⌉ .

GRAPH-019

Exact Ramsey Number $R(5,5)$

MajorExact constant problemUnknown

Determine the least integer

N = R (5, 5)

such that every red--blue coloring of the edges of

K_{N}

contains a monochromatic

K_{5}

GRAPH-020

Seymour's Second Neighborhood Conjecture

MajorConjecturec. 1990

Let

D

be a finite oriented graph (no loops and no pair of oppositely directed edges). For

v \in V (D)

, let

N^{+} (v)

be its out-neighborhood and let

N^{++} (v)

be the set of vertices whose directed distance from

v

is exactly

2

. Then some vertex

v

satisfies

∣ N^{++} (v) ∣ \geq ∣ N^{+} (v) ∣.

GRAPH-021

Meyniel's Conjecture on the Cop Number

MajorConjecture1985

In the perfect-information game on a finite connected simple graph

G

, the cops choose their starting vertices and the robber then chooses one. The sides alternate, beginning with the cops; on a cops' turn every cop may independently traverse one edge or stay fixed, and on a robber turn the robber may do the same. The cops win when a cop occupies the robber's vertex. If

c (G)

is the minimum number of cops having a winning strategy, then there is an absolute constant

C

such that every

n

-vertex

G

satisfies

c (G) \leq C n .

GRAPH-022

Chvátal's Toughness Conjecture

MajorConjecture1973

There exists a real constant

t_{0} > 0

such that every finite simple

t_{0}

-tough graph on at least three vertices is Hamiltonian. Here

G

t

-tough if, for every vertex set

S

with

c (G - S) > 1

∣ S ∣ \geq t c (G - S),

where

G - S

is the graph obtained by deleting

S

and

c (\cdot)

denotes the number of connected components.

GRAPH-023

Erdős–Faber–Lovász Conjecture

MajorConjecture1972

Let

H

be a finite linear hypergraph on

n

vertices, meaning that any two distinct hyperedges meet in at most one vertex. Its hyperedges can be colored with at most

n

colors so that intersecting hyperedges receive different colors.

GRAPH-024

Perfect One-Factorization Conjecture

MajorConjecture1964

For every integer

n \geq 2

, the edge set of the complete graph

K_{2 n}

can be partitioned into perfect matchings

M_{1}, \dots, M_{2 n - 1}

such that

M_{i} \cup M_{j}

is a Hamiltonian cycle whenever

i \neq = j

. A perfect matching is a set of pairwise disjoint edges meeting every vertex exactly once, and a Hamiltonian cycle is a cycle containing every vertex.

GRAPH-028

Erd\u0151s–Simonovits Compactness Conjecture

MajorConjecture1982

For every finite nonempty family

F

of graphs, each containing a cycle, there are

F \in F

and

C > 0

such that

ex (n, F) \leq C ex (n, F)

for all sufficiently large

n

, where

ex (n, F)

is the largest number of edges in an

n

-vertex graph containing no member of

F

GRAPH-029

Erd\u0151s Degeneracy Conjecture for Extremal Numbers

MajorConjecture1967

For every integer

r \geq 2

and every fixed bipartite

r

-degenerate graph

H

ex (n, H) = O_{H} (n^{2 - 1/ r}) .

A graph is

r

-degenerate if every nonempty subgraph has a vertex of degree at most

r

GRAPH-030

Zarankiewicz Problem for $K_{4,4}$

MajorOpen problem1951

Determine the asymptotic order of

ex (n, K_{4, 4}),

the largest number of edges in an

n

-vertex graph containing no copy of the complete bipartite graph

K_{4, 4}

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.

DG-003

Exact Growth of the Planar Unit-Distance Function

MajorOpen problem1946

For

n \geq 2

, set

u (n) = P \subset R^{2} ∣ P ∣ = n max {{x, y} \subset P : ∥ x - y ∥_{2} = 1}

and

α_{U} = n \to \infty lim sup \frac{lo g u ( n )}{lo g n} .

Determine the exact value of

α_{U}

(and, more finely, the asymptotic order of

u (n)

DG-005

Erdős–Ulam Rational-Distance Problem

MajorOpen problem1946

Does there exist a countable dense set

S \subset R^{2}

such that

∥ x - y ∥_{2} \in Q for every x, y \in S ?

DG-010

Reinhardt's Smoothed-Octagon Conjecture

MajorConjecture1934

For a centrally symmetric convex disk

K \subset R^{2}

, define

δ_{L} (K) = Λ sup \frac{area ( K )}{det Λ},

where the supremum is over full-rank lattices

Λ \subset R^{2}

for which the interiors of the translates

K + λ

λ \in Λ

, are pairwise disjoint. Let

O

be Reinhardt's smoothed octagon, obtained from a regular octagon by replacing each vertex by the hyperbola arc tangent to its two incident sides and asymptotic to the two adjacent nonincident sides. Then

δ_{L} (K) \geq δ_{L} (O) = \frac{8 - 4 2 - lo g 2}{2 2 - 1} .

DG-011

Kalai's $3^d$ Conjecture

MajorConjecture1989

Every centrally symmetric convex

d

-polytope has at least

3^{d}

nonempty faces in total, counting faces of every dimension

0, \dots, d

and counting the polytope itself.

DG-012

Five-Dimensional Kissing Number

MajorExact constant problemUnknown

Let

S^{4} = {x \in R^{5} : ∥ x ∥_{2} = 1}

. Determine

τ_{5} = max {∣ X ∣ : X \subset S^{4}, ⟨ x, y ⟩ \leq \frac{1}{2} for all distinct x, y \in X} .

Equivalently,

τ_{5}

is the maximum number of nonoverlapping unit

5

-balls that can simultaneously touch a fixed unit

5

-ball.

DG-013

Optimal Sphere Packing in Dimension Five

MajorConjecturec. 1900

For a packing

P

of congruent closed balls in

R^{5}

with disjoint interiors, define its upper asymptotic density by

\overline{ρ} (P) = R \to \infty lim sup x \in R^{5} sup \frac{vol _{5} ( B ( x , R ) \cap ⋃ _{B \in P} B )}{vol _{5} ( B ( x , R ))},

where

B (x, R)

is the radius-

R

ball centered at

x

. Let

Δ_{5}

be the supremum of

\overline{ρ} (P)

over all such packings. Then

Δ_{5} = \frac{π ^{2}}{15 2},

the density attained by the

D_{5}

root-lattice packing.

DG-014

Four-Dimensional Borsuk Problem

MajorCanonical finite case1933

Let

b (4)

be the least

m

such that every bounded set

S \subset R^{4}

of positive diameter can be partitioned into

m

subsets, each having diameter strictly smaller than

diam (S)

. Is

b (4) = 5 ?

DG-015

Lebesgue's Universal Covering Problem

MajorExact constant problem1914

Let

U = in f {area (K) : K \subset R^{2} is convex and every planar set S with diam (S) \leq 1 has an isometric copy contained in K} .

Determine the exact value of

U

, and whether the infimum is attained.

DG-019

Ehrhart Volume Conjecture

MajorConjecture1964

Let

K \subset R^{n}

be a convex body whose barycenter is the origin and whose only interior lattice point is

0

. Then

vol (K) \leq \frac{( n + 1 ) ^{n}}{n !} .

Moreover, equality holds only for unimodular images of the centered simplex

(n + 1) conv (0, e_{1}, \dots, e_{n}) - (1, \dots, 1) .

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

OR-002

Strongly polynomial finite Markov decision processes

MajorOpen problemc. 1983

There is a strongly polynomial algorithm which, given a finite state set

S

, finite nonempty action sets

A_{s}

, rational transition probabilities

p (t ∣ s, a)

, rational rewards

r (s, a)

, and rational

0 < γ < 1

, returns a stationary deterministic policy maximizing

E_{s}^{π} [k = 0 \sum \infty γ^{k} r (S_{k}, π (S_{k}))]

simultaneously for every initial state

s

, using a number of arithmetic operations polynomial only in

∣ S ∣ + \sum_{s} ∣ A_{s} ∣

and maintaining intermediate encoding lengths polynomial in the input length.

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.

OR-004

Modified integer round-up property for bin packing

MajorConjecturec. 1985

Given item sizes

a_{1}, \dots, a_{n} \in (0, 1]

, let

P = {P \subseteq {1, \dots, n} : \sum_{i \in P} a_{i} \leq 1}

. Let

OPT

be the minimum number of patterns from

P

, with repetitions allowed, whose incidence vectors sum coordinatewise to at least

1

, and let

OPT_{f} = min {P \in P \sum x_{P} : x_{P} \geq 0, P ∋ i \sum x_{P} \geq 1 (i = 1, \dots, n)} .

Then

OPT \leq ⌈ OPT_{f} ⌉ + 1

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

OPT-003

Polynomial Hirsch conjecture

MajorConjecturec. 1992

There is a polynomial

p \in R [X, Y]

such that, for all integers

d \geq 1

n \geq d + 1

, and every

d

-dimensional convex polytope

P

having exactly

n

facets, the graph whose vertices and edges are the

0

- and

1

-dimensional faces of

P

has diameter at most

p (n, d)

TCS-001

$P$ versus $NP$

IconicOpen problem1971

P \neq = NP ?

Here

P

is the class of decision languages recognized by deterministic Turing machines in polynomial time, and

NP

is the class recognized by nondeterministic Turing machines in polynomial time (equivalently, languages with polynomial-size certificates verifiable in deterministic polynomial time).

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

TCS-006

$NP\nsubseteq P/poly$

MajorConjecturec. 1980

There is a language in

NP

that is not decided by any family

(C_{n})_{n \geq 1}

of Boolean circuits of size polynomial in

n

, where

C_{n}

decides membership for all inputs of length

n

; in symbols,

NP ⊈ P / p o l y .

Here

NP

is nondeterministic polynomial time, and

P / p o l y

is the class defined by such polynomial-size, nonuniform circuit families.

TCS-010

Strong Exponential Time Hypothesis

MajorConjecture2001

For every

ε > 0

there exists an integer

k \geq 3

such that

k

-SAT—satisfiability of CNF formulas whose clauses contain at most

k

literals—on

n

variables cannot be decided by a deterministic algorithm in time

O ((2 - ε)^{n}) .

TCS-015

Log-Rank Conjecture

MajorConjecture1988

There is an absolute constant

C

such that every nonconstant total Boolean function

f : X \times Y \to {0, 1}

satisfies

D (f) \leq (1 + lo g_{2} rank_{R} M_{f})^{C},

where

M_{f} = (f (x, y))_{x \in X, y \in Y}

and

D (f)

is the minimum worst-case number of communicated bits in a deterministic two-party protocol computing

f

TCS-016

Aanderaa–Karp–Rosenberg Evasiveness Conjecture

MajorConjecturec. 1973

Fix

n

, and let

P

be a nontrivial property of simple labeled

n

-vertex graphs that is invariant under vertex permutations and monotone under adding edges, where nontrivial means that

P

is neither empty nor the set of all such graphs. Every deterministic algorithm that decides whether an unknown graph has

P

by adaptively querying edge presence has worst-case query complexity

(2 n) .

TCS-017

Berman–Hartmanis Isomorphism Conjecture

MajorConjecture1977

A, B \subseteq {0, 1}^{*}

are both

NP

-complete, where

NP

is nondeterministic polynomial time, and completeness is under polynomial-time many-one reductions, then there exists a bijection

f : {0, 1}^{*} \to {0, 1}^{*}

such that

f

and

f^{- 1}

are polynomial-time computable and

x \in A ⟺ f (x) \in B .

TCS-019

APSP Hypothesis

MajorConjecturec. 2010

For every

ε > 0

, there is no

O (n^{3 - ε})

-time word-RAM algorithm which, given an

n

-vertex directed graph with

O (lo g n)

-bit integer edge weights and no negative directed cycle, outputs the shortest-path distance for every ordered pair of vertices. The distance from

u

v

is the minimum total weight of a directed

u

-to-

v

path, or

+ \infty

if no such path exists.

TCS-020

Modern 3SUM Conjecture

MajorConjecturec. 1995

For every

ε > 0

, there is no randomized bounded-error

O (n^{2 - ε})

-time word-RAM algorithm that, given

n

distinct

O (lo g n)

-bit integers, decides whether three distinct input integers

a, b, c

satisfy

a + b + c = 0.

TCS-021

Orthogonal Vectors Conjecture

MajorConjecturec. 2005

For every

ε > 0

, there is a constant

c > 0

such that no randomized bounded-error

O (n^{2 - ε})

-time algorithm, given

A, B \subseteq {0, 1}^{d}

with

∣ A ∣ = ∣ B ∣ = n

and

d = c lo g n

, decides whether there exist

a \in A, b \in B

with

⟨ a, b ⟩ = 0.

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

NP-Hardness of the Minimum Circuit Size Problem

MajorOpen problemc. 1975

The Minimum Circuit Size Problem (MCSP) takes as input the

N = 2^{n}

-bit truth table of a Boolean function

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

and an integer

s \leq N

, and asks whether

f

has a Boolean circuit over the fixed complete basis

{AND, OR, NOT}

, with

AND

and

OR

of fan-in two, and with at most

s

gates. Is MCSP

NP

-hard under deterministic polynomial-time many-one reductions?

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

TCS-029

Quantum Parallel Repetition Conjecture

MajorConjecture2004

For every finite two-player one-round game

G

whose entangled value satisfies

ω^{*} (G) < 1

, there is a constant

c_{G} > 0

such that the entangled value of the

n

-fold parallel repetition obeys

ω^{*} (G^{\otimes n}) \leq e^{- c_{G} n} (n \geq 1) .

TCS-030

Fixed-Polynomial-Factor Hardness of Euclidean Closest Vector

MajorConjecturec. 2003

There exists a constant

ε > 0

for which the following promise problem is

NP

-hard under deterministic polynomial-time many-one reductions: given a lattice basis

B \in Z^{m \times n}

, target

t \in Z^{m}

, and radius

r > 0

, distinguish

dist_{2} (t, L (B)) \leq r from dist_{2} (t, L (B)) > n^{ε} r .

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

INFO-001

Shannon capacity of the seven-cycle

MajorExact constant problem1956

For finite simple graphs

G, H

, define their strong product to have vertex set

V (G) \times V (H)

, with distinct

(g, h)

and

(g^{'}, h^{'})

adjacent exactly when, in each coordinate, the entries are equal or adjacent and in at least one coordinate they are adjacent. Write

G^{⊠ k}

for the

k

-fold strong product and

α (G)

for the maximum size of an independent vertex set. Determine exactly

Θ (C_{7}) := k \geq 1 sup α (C_{7}^{⊠ k})^{1/ k},

where

C_{7}

is the cycle on seven vertices.

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

INFO-003

Binary asymptotic rate–distance improvement problem

MajorOpen problem1952–1957

For

0 < δ < 1/2

, let

A_{2} (n, d)

be the largest cardinality of a set

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

whose distinct words have Hamming distance at least

d

, and define

R_{2} (δ) = n \to \infty lim sup \frac{1}{n} lo g_{2} A_{2} (n, ⌈ δ n ⌉) .

Decide whether there exists

δ \in (0, 1/2)

for which

R_{2} (δ) > 1 - H_{2} (δ), H_{2} (t) = - t lo g_{2} t - (1 - t) lo g_{2} (1 - t) .

INFO-005

Asymptotic Spherical-Code Rate

MajorOpen problem1959

For

- 1 < s < 1

, let

A_{S} (d, s)

be the largest number of unit vectors in

R^{d}

whose pairwise inner products are at most

s

. Determine the asymptotic rate

R_{S} (s) = d \to \infty lim sup \frac{1}{d} lo g_{2} A_{S} (d, s)

for every fixed

s

, and determine where the corresponding limit exists.

INFO-006

Li–Li Undirected Network Coding Conjecture

MajorConjecture2004

For every finite undirected capacitated network with any finite collection of unicast source--sink pairs, the maximum common rate achievable by arbitrary network coding equals the maximum common rate achievable by fractional multicommodity routing.

NUM-001

Twelve-stage ninth-order explicit Runge–Kutta method

MajorCanonical finite casec. 1964

Determine whether there exist real coefficients

a_{ij}

(

1 \leq j < i \leq 12

) and

b_{i}

(

1 \leq i \leq 12

), with

c_{i} = \sum_{j < i} a_{ij}

, such that the explicit Runge--Kutta one-step map

k_{i} = f (t + c_{i} h, y + h j < i \sum a_{ij} k_{j}), y^{+} = y + h i = 1 \sum 12 b_{i} k_{i}

has classical order

9

: for every integer

q \geq 1

, every sufficiently smooth

f : R \times R^{q} \to R^{q}

, and every exact solution of

y^{'} = f (t, y)

, one step initialized at

y (t)

satisfies

y^{+} - y (t + h) = O (h^{10})

h \to 0

MATH-PHYS-001

Yang–Mills existence and mass gap

IconicOpen problem2000

For every compact simple gauge group

G

, construct gauge-invariant Euclidean Yang--Mills Schwinger functions on

R^{4}

satisfying the Osterwalder--Schrader axioms OS0--OS4: regularity/tempered growth, Euclidean covariance, reflection positivity, permutation symmetry, and clustering. Their Osterwalder--Schrader reconstruction must be a nontrivial relativistic quantum field theory whose joint energy--momentum spectrum consists of the vacuum

0

and a subset of

{p : p_{0} \geq 0, p_{0}^{2} - ∥ p ∥^{2} \geq Δ^{2}}

for some

Δ > 0

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

MATH-PHYS-004

Maximal ionization conjecture

MajorConjecture1984

For integers

Z, N \geq 1

, on the fermionic space

⋀^{N} L^{2} (R^{3}; C^{2})

let

H_{Z, N} = i = 1 \sum N (- \frac{1}{2} Δ_{i} - \frac{Z}{∣ x _{i} ∣}) + 1 \leq i < j \leq N \sum \frac{1}{∣ x _{i} - x _{j} ∣}, E_{Z} (N) = in f σ (H_{Z, N}),

and set

E_{Z} (0) = 0

. There is a universal constant

C < \infty

such that

E_{Z} (N) < E_{Z} (N - 1)

implies

N \leq Z + C

for every

Z, N \geq 1

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.

MATH-PHYS-006

Sharp three-dimensional Lieb–Thirring constant

MajorExact constant problem1976

For every real

V \in L^{5/2} (R^{3})

, if

{λ_{j}}

are the negative eigenvalues of

- Δ + V

, counted with multiplicity, then

j \sum ∣ λ_{j} ∣ \leq \frac{1}{15 π ^{2}} \int_{R^{3}} V_{-} (x)^{5/2} d x, V_{-} = max {- V, 0},

and

1/ (15 π^{2})

is the optimal universal constant.

MATH-PHYS-007

Optimal Lieb–Oxford constant

MajorExact constant problemc. 1981

For each

N \geq 1

, let

P_{N}

be the symmetric probability measures

P

(R^{3})^{N}

with finite Coulomb energy and one-particle density

ρ_{P}

, normalized by

\int_{R^{3}} ρ_{P} = N

. Define

E_{ind} (P) = \int_{(R^{3})^{N}} i < j \sum \frac{1}{∣ x _{i} - x _{j} ∣} d P (x_{1}, \dots, x_{N}) - \frac{1}{2} \iint_{R^{3} \times R^{3}} \frac{ρ _{P} ( x ) ρ _{P} ( y )}{∣ x - y ∣} d x d y

and

C_{LO} = N \geq 1 sup P \in P_{N} sup \frac{- E _{ind} ( P )}{\int _{R^{3}} ρ _{P} ( x ) ^{4/3} d x} .

Q_{L} = [- L /2, L /2]^{3}

, define

e_{UEG} = L \to \infty L^{3} \in N lim L^{- 3} in f {E_{ind} (P) : P \in P_{L^{3}}, ρ_{P} = 1_{Q_{L}}} .

Then

C_{LO} = - e_{UEG}

MATH-PHYS-010

Homogeneous interacting Bose-gas condensation

MajorConjecture1925

Let

v \geq 0

be a nonzero radial finite-range potential on

R^{3}

with scattering length

a

, let

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

, and let

v_{L}

be the

L

-periodic extension of

v

. For a normalized bosonic ground state of

H_{N, L} = - i = 1 \sum N Δ_{i} + i < j \sum v_{L} (x_{i} - x_{j}) on L_{sym}^{2} (Λ_{L}^{N}),

let

γ_{N, L}^{(1)}

be its one-particle density matrix, normalized by

Tr γ_{N, L}^{(1)} = N

. Then

ρ a^{3} ↓ 0 lim N, L \to \infty N / L^{3} = ρ lim \frac{λ _{m a x} ( γ _{N, L}^{(1)} )}{N} = 1.

CTRL-001

Generalized Belgian Chocolate Problem

MajorExact constant problem1994

Call a nonzero real polynomial Hurwitz stable if all of its complex zeros have strictly negative real part. Define

δ_{*} = sup {δ \in (0, 1) : there exist nonzero Hurwitz-stable x, y \in R [s] such that (s^{2} - 2 δs + 1) x (s) + (s^{2} - 1) y (s) is Hurwitz stable} .

Determine

δ_{*}

exactly.

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})?

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.

GAME-002

Complete EFX allocation for additive goods

MajorConjecture2016

For every finite agent set

N

, finite set

M

of indivisible goods, and nonnegative additive valuations

v_{i} (S) = \sum_{g \in S} v_{i} (g)

, there is a partition

(X_{i})_{i \in N}

M

such that, for all

i, j \in N

and every

g \in X_{j}

v_{i} (X_{i}) \geq v_{i} (X_{j} ∖ {g}) .

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.

LOG-MODEL-002

Cherlin–Zilber Algebraicity Conjecture

MajorConjecturec. 1979

Every infinite simple group

G

of finite Morley rank is, as an abstract group, isomorphic to the group of

K

-rational points of a simple algebraic group over an algebraically closed field

K

LOG-MODEL-003

Stable Fields Conjecture

MajorConjecturec. 1971

K

is an infinite field whose complete first-order theory in the language of rings is stable, then

K

is separably closed.

LOG-MODEL-004

NIP Fields Conjecture

MajorConjecturec. 2015

Let

K

be an infinite field whose complete first-order theory in the language of rings has no independence property (is NIP). Then at least one of the following holds:

K

is separably closed;

K

is real closed; or

K

admits a nontrivial henselian valuation.

LOG-COMP-008

Martin’s Conjecture for Borel Turing-Invariant Functions

MajorConjecturec. 1978

Let

2^{ω}

be the set of subsets of

N

, identified with the reals, and let

\leq_{T}

\equiv_{T}

, and

x^{'}

denote Turing reducibility, Turing equivalence, and the Turing jump. A map

f : 2^{ω} \to 2^{ω}

is Turing-invariant if

x \equiv_{T} y

implies

f (x) \equiv_{T} f (y)

. A Turing cone is a set

C_{z} = {x : z \leq_{T} x}

. For Borel Turing-invariant maps define

f \leq_{M} g ⟺ (\exists z) (\forall x \in C_{z}) f (x) \leq_{T} g (x),

and write

f \equiv_{M} g

when both

f \leq_{M} g

and

g \leq_{M} f

. Then: 1. Every Borel Turing-invariant

f

is either constant in Turing degree on a cone, or

id \leq_{M} f

. 2. The quotient by

\equiv_{M}

of the maps satisfying

id \leq_{M} f

is well-ordered by

\leq_{M}

, and the immediate successor of

[f]

is represented by

x \mapsto f (x)^{'}

LOG-SET-009

Reinhardt Cardinal Inconsistency Problem

MajorOpen problem1967

Prove in

ZF

, without the axiom of choice, that there is no nontrivial elementary embedding

j : V \to V

. Equivalently, determine whether the existence of a Reinhardt cardinal, the critical point of such an embedding, is inconsistent with

ZF