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

NT-AN-004

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

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

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

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

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

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

Barnette's Conjecture

MajorConjecture1969

Every finite simple, cubic, bipartite, planar,

3

-vertex-connected graph has a Hamiltonian cycle.

GRAPH-006

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