Riemann Hypothesis
Conjecture1859Let
and let the same symbol denote its meromorphic continuation to , whose only pole is the simple pole at . Every zero of with satisfies .
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 36 of 280 problems in Graph theory
Birch–Swinnerton-Dyer Conjecture
Conjecture1965Let be an elliptic curve. Write , and let be the Hasse–Weil -function of , continued to an entire function by modularity. Then
Strong Goldbach Conjecture
Conjecture1742For every even integer , there exist prime numbers (not necessarily distinct) such that .
Twin Prime Conjecture
Conjecture1849There are infinitely many primes for which is also prime.
Collatz Conjecture
Conjecturec. 1937Define by
For every , there exists such that .
Generalized Riemann Hypothesis for Dirichlet -functions
LandmarkConjecturec. 1884For every primitive Dirichlet character modulo an integer , every zero of the analytically continued Dirichlet function
satisfying has .
Bateman–Horn Conjecture
LandmarkConjecture1962Let be distinct irreducible polynomials with positive leading coefficients. Assume their product has no fixed prime divisor, meaning that no prime divides for every . For a prime , set , and
Then, as ,
Schanuel’s Conjecture
LandmarkConjecturec. 1960For every integer , if are linearly independent over , then
where denotes transcendence degree over .
Hilbert’s Tenth Problem over
LandmarkOpen problem1970There is no Turing machine which, on every input polynomial (where is part of the input), halts and correctly decides whether there exists with .
Generalized Ramanujan Conjecture for
LandmarkConjecturec. 1967For every , every irreducible unitary cuspidal automorphic representation of , where is the adèle ring of , and every place of , the local representation is tempered; equivalently, all its -finite matrix coefficients belong to for every , where is a maximal compact subgroup and is the center.
Fontaine–Mazur Conjecture
LandmarkConjecture1995Let be a prime, put , and let
be a continuous irreducible representation, unramified outside finitely many primes and potentially semistable at , meaning semistable after restriction to the Galois group of a finite extension of . Then there exist a smooth projective variety , integers , and a finite extension such that , after scalar extension to , is a subquotient of .
Elliott–Halberstam Conjecture
LandmarkConjecture1968–1970Let if for a prime and an integer , and let otherwise. Put
For every and every ,
Artin Holomorphy Conjecture
LandmarkConjecture1923Let be a finite Galois extension of number fields with group , and let be a nontrivial irreducible finite-dimensional complex representation. For every nonzero prime ideal of , choose a prime of above it, let be its inertia group, and let denote an arithmetic Frobenius element acting on . The Artin -function
has an analytic continuation to an entire function on .
Montgomery’s Pair-Correlation Conjecture
LandmarkConjecture1973Assume the Riemann hypothesis, write the nontrivial zeros of the Riemann zeta function as , counted with multiplicity, and put . For every fixed ,
as .
Chowla’s Correlation Conjecture
LandmarkConjecture1965Let be the Liouville function, where is the number of prime factors of , counted with multiplicity. For every integer and every choice of distinct nonnegative integers ,
Conjecture
LandmarkConjecture1985For every , there is a constant such that, whenever coprime positive integers satisfy ,
Lindelöf Hypothesis
MajorConjecture1908Let for , and let also denote its meromorphic continuation to . For every ,
Landau’s Prime Conjecture
MajorConjecture1912There are infinitely many positive integers for which is prime.
Legendre’s Conjecture
MajorConjecture1798For every integer , there is a prime such that .
Artin’s Primitive Root Conjecture
MajorConjecture1927Let be not a perfect square. For , let , let be the Möbius function (zero if a prime square divides , and if is a product of distinct primes), and put
Then and, as ,
where ; the field in the denominator is independent of the choice of the -th root of .
Fermat–Catalan Conjecture
MajorConjecture1995There are only finitely many sextuples such that
Beal Conjecture
MajorConjecture1993If positive integers satisfy
then .
Erdős–Straus Conjecture
MajorConjecture1948For every integer , there exist positive integers such that
Odd Perfect Number Conjecture
MajorConjectureUnknownThere is no odd positive integer satisfying , where .
Infinitude of Mersenne Primes
MajorConjectureUnknownThere are infinitely many primes such that is prime.
Lehmer’s Totient Conjecture
MajorConjecture1932For , let be Euler’s totient. If and divides , then is prime.
Lehmer’s Mahler-Measure Conjecture
MajorExact constant problem1933There exists a real constant such that every algebraic integer that is not a root of unity satisfies
where, if is the minimal polynomial of , then .
Lehmer’s Nonvanishing Conjecture for Ramanujan’s -function
MajorConjecture1947Define integers by
Then for every integer .
Littlewood Conjecture
MajorConjecturec. 1930For all real numbers ,
where .
Four Exponentials Conjecture
MajorConjecturec. 1966If are linearly independent over and are linearly independent over , then at least one of the four numbers
is transcendental.
Leopoldt’s Conjecture
MajorConjecture1962Let be a number field and a rational prime. For each place , let be the completion and let be the local -adic logarithm: if is the maximal ideal of , its restriction to is
and it vanishes on torsion units. Then the map
is injective.
Vandiver’s Conjecture
MajorConjecturec. 1929For every prime , let and let be the ideal-class number of the maximal real subfield of the -th cyclotomic field. Then .
Irrationality of the Euler–Mascheroni Constant
MajorOpen problemUnknownThe number
is irrational.
Gauss Circle-Problem Exponent Conjecture
MajorExact constant problemc. 1915For , let
Then for every ,
Dirichlet Divisor-Problem Exponent Conjecture
MajorExact constant problemc. 1916Let and , and put
For every ,
Selberg Eigenvalue Conjecture
MajorConjecture1965Let be a congruence subgroup, meaning that contains for some . If is a discrete -eigenvalue of the positive hyperbolic Laplacian on , where , then .
Plane Jacobian Conjecture
LandmarkCanonical finite case1939If is a polynomial map and
then there is a polynomial map satisfying .
Inverse Galois Conjecture over
LandmarkOpen problemc. 1892For every finite group , there exists a finite Galois extension such that .
Serre’s Conjecture II
LandmarkConjecture1962Let be a perfect field of Galois cohomological dimension at most , and let be a semisimple simply connected linear algebraic group over . Then ; equivalently, every -torsor over has a -rational point.
Soficity Conjecture
LandmarkConjecture2000Every countable group is sofic. Explicitly, for every countable group , finite , and , there are an integer and a map such that ,
and for every , where is normalized Hamming distance.
Dixmier Conjecture for the First Weyl Algebra
MajorCanonical finite case1968Let
be the first Weyl algebra. Every unital -algebra endomorphism is an automorphism.
Kaplansky Zero-Divisor Conjecture
MajorConjecturec. 1940If is a field and is a torsion-free group, then the group algebra has no nonzero zero divisors: for all , implies or .
Kaplansky Idempotent Conjecture
MajorConjecturec. 1950If is a torsion-free group and satisfies , then or .
Kaplansky Direct-Finiteness Conjecture
MajorConjecturec. 1940For every field , every group , and all , if , then .
Köthe Conjecture
MajorConjecture1930For every associative ring (not necessarily unital), if are left ideals such that every element of and every element of is nilpotent, then every element of is nilpotent.
Finitistic Dimension Conjecture
MajorConjecture1960Let be a finite-dimensional algebra over a field, and let denote the projective dimension of a finitely generated left -module . Then
Auslander–Reiten Conjecture
MajorConjecture1975Let be an Artin algebra and a finitely generated left -module. If
then is projective.
Nakayama Conjecture
MajorConjecture1958Let be a finite-dimensional algebra over a field and
its minimal injective resolution as a left module. If every is projective, then is self-injective.
Broué’s Abelian Defect Group Conjecture
MajorConjecture1990Let be a prime, let be a splitting -modular system for a finite group : is a complete discrete valuation ring with characteristic- fraction field and algebraically closed residue field of characteristic , and both fields split every subgroup of . Let be a block algebra of with abelian defect group . If is the Brauer-correspondent block of , then
as triangulated categories, where these are bounded derived categories of finitely generated left modules.
Alperin Weight Conjecture
MajorConjecture1986Let be a finite group, a prime, and an algebraically closed field of characteristic . A -weight is a pair , where is a -subgroup and is an irreducible complex character of of -defect zero. Here defect zero means that the -part of equals the -part of . The number of isomorphism classes of simple -modules equals the number of -conjugacy classes of -weights.
Donovan’s Conjecture
MajorConjecturec. 1976Fix a prime , an algebraically closed field of characteristic , and a finite -group . Among all finite groups , there are only finitely many Morita-equivalence classes of block algebras of whose defect groups are isomorphic to .
Andrews–Curtis Conjecture
MajorConjecture1965For every integer , let be the free group. If has normal closure , then can be transformed to by finitely many moves
their inverses, and permutations of the entries.
Boone–Higman Conjecture
MajorConjecture1974Every finitely generated group with solvable word problem embeds into a finitely presented simple group.
Strong Atiyah Conjecture
MajorConjecture1976Let be a discrete group for which the orders of finite subgroups are bounded, and put . For all and every matrix , let be the bounded -equivariant operator given by right convolution by . Then
where is the group von Neumann algebra and is its von Neumann dimension.
Brauer’s -Conjecture
MajorConjecture1946Let be a finite group, let be a prime, and fix a splitting -modular system for . Let be a -block of , meaning a two-sided summand of the modular group algebra cut out by a primitive central idempotent; let be the set of irreducible ordinary complex characters belonging to , and let be a defect group of . Then
Terao’s Freeness Conjecture
MajorConjecture1983Let be a finite central hyperplane arrangement in a finite-dimensional complex vector space . For each , choose with , and define the module of logarithmic derivations
Call free when is a free -module, and let
be its intersection lattice, ordered by reverse inclusion. If two such arrangements and have isomorphic intersection lattices, then is free if and only if is free.
Hodge Conjecture
Conjecture1950Let be a smooth projective variety over . For every integer ,
where is the singular-cohomology cycle class and is the -summand of the Hodge decomposition of .
Tate Conjecture
LandmarkConjecture1963Let be a finitely generated field, a smooth projective variety, , and a prime. The image of
equals the invariant subspace
where is the group of codimension- algebraic cycles modulo rational equivalence.
Grothendieck Section Conjecture
LandmarkConjecture1983Let be a field finitely generated over , put , and let be a smooth, projective, geometrically connected curve of genus . After choosing a geometric base point, its étale fundamental groups fit into the exact sequence
The map sending to the conjugacy class (under ) of the section determined by is a bijection.
Bombieri–Lang Conjecture
LandmarkConjecturec. 1971If is a number field and is a smooth projective variety of general type, then is not Zariski dense in .
Vojta’s Main Conjecture
LandmarkConjecture1987Let be a smooth projective variety over a number field , let be a simple-normal-crossings divisor, a big divisor, a finite set of places of , , and . There is a proper Zariski-closed containing the support of such that for every with ,
Here is the proximity function, heights use fixed Weil-height choices, the constant may depend on the fixed data but is independent of , and
is the normalized logarithmic relative discriminant, with the relative discriminant ideal.
Abundance Conjecture
LandmarkConjecturec. 1985Let be a projective Kawamata-log-terminal pair over , with a -Cartier -divisor. If is nef, then it is semiample: some positive integral multiple is Cartier and base-point-free.
Termination of Flips Conjecture
LandmarkConjecturec. 1988Let be a projective -factorial Kawamata-log-terminal pair over . Every sequence
in which each arrow is a -flip terminates after finitely many steps.
Resolution of Singularities in Positive Characteristic
LandmarkOpen problem1964Let be a perfect field of positive characteristic and an integral separated scheme of finite type over . There exist a smooth integral -scheme and a proper birational morphism that is an isomorphism over the regular locus .
Grothendieck–Katz -Curvature Conjecture
LandmarkConjecture1969–1972Let be a number field, let be a smooth connected variety, and let be an algebraic vector bundle with integrable connection on . After extending these data over for some finite set of finite places, reduce at a place of residue characteristic . For a local derivation on the reduction , define the -curvature by
where is the -fold iterate of as a derivation. If for every local derivation and all but finitely many , then, after any embedding , the analytic monodromy of on has finite image; equivalently, the connection becomes trivial after a finite étale cover of .
Green–Griffiths–Lang Conjecture
LandmarkConjecture1980Let be a smooth projective complex variety of general type. There exists a proper Zariski-closed subset such that every nonconstant holomorphic map satisfies .
Generalized Hodge Conjecture
MajorConjecture1969Let be integers and let be a smooth projective complex variety. If is a rational Hodge substructure such that whenever or , where , then there exists a closed algebraic subset of codimension at least such that
Lefschetz Standard Conjecture
MajorConjecture1968Let be a smooth projective variety of dimension over an algebraically closed field, let be a Weil cohomology theory with characteristic- coefficient field, and let for the class of an ample divisor. For every , the inverse of the hard-Lefschetz isomorphism
is induced by an algebraic correspondence in , where denotes codimension- algebraic cycles modulo rational equivalence.
Zilber–Pink Conjecture for Abelian Varieties
MajorConjecture1999–2005Let be a complex abelian variety. For , let be the union of all torsion cosets , where is a torsion point and is an abelian subvariety with . If is an irreducible closed subvariety not contained in any proper torsion coset, then
is not Zariski dense in .
Nagata Conjecture
MajorConjecture1959Let , let be very general points of , meaning outside a countable union of proper Zariski-closed subsets of the configuration space, and let . If a plane curve of degree has multiplicity at least at every , then
Nonvanishing Conjecture
MajorConjecturec. 1988Let be a projective Kawamata-log-terminal pair over with a -Cartier -divisor. If is pseudo-effective, then there is an effective -divisor with .
Hartshorne Complete-Intersection Conjecture
MajorConjecture1974If is a smooth closed subvariety with , then is a complete intersection in : its homogeneous ideal is generated by homogeneous polynomials.
Fujita Conjecture
MajorConjecture1985Let be a smooth projective complex variety of dimension , its canonical line bundle, and an ample line bundle. Then is globally generated and is very ample.
Clemens Conjecture
MajorConjecture1986Let be a very general smooth quintic hypersurface, meaning one outside a countable union of proper Zariski-closed subsets of the parameter space. For every , contains only finitely many irreducible rational curves of degree ; every such curve is a smooth embedded with normal bundle .
Irrationality of a Very General Cubic Fourfold
MajorOpen problemc. 1969A very general smooth cubic hypersurface , meaning one outside a countable union of proper Zariski-closed subsets of the parameter space, is not rational over .
Kuznetsov’s Rationality Conjecture for Cubic Fourfolds
MajorConjecture2010Let be a smooth cubic fourfold. In the bounded derived category of coherent sheaves on , put
where denotes the full right-orthogonal subcategory. Then is rational if and only if there is a complex K3 surface with an exact -linear triangulated equivalence .
Morrison–Kawamata Cone Conjecture
MajorConjecture1993–1997Let be a projective -factorial Kawamata-log-terminal pair over with , and put inside , where is the cone generated by classes of effective Cartier divisors. There is a rational polyhedral cone such that
and interiors of and are disjoint unless the cones coincide.
Bloch Conjecture for Surfaces with
MajorConjecture1975Let be a smooth projective complex surface with . The Albanese map
from degree-zero zero-cycles modulo rational equivalence is an isomorphism.
Smooth four-dimensional Poincaré conjecture
Conjecturec. 1960Every closed, connected, smooth -manifold that is homotopy equivalent to the standard sphere is diffeomorphic to .
Smooth four-dimensional Schoenflies conjecture
LandmarkConjecturec. 1960For every smooth embedding , each of the two closures of the components of is diffeomorphic to the standard closed -ball .
Hilbert–Smith conjecture
LandmarkConjecturec. 1940Let be a locally compact Hausdorff topological group and a connected finite-dimensional topological manifold. If is a continuous faithful action, then is a Lie group.
Cannon conjecture
LandmarkConjecture1994If is a Gromov-hyperbolic group whose Gromov boundary is homeomorphic to , then admits a properly discontinuous, cocompact action by isometries on hyperbolic -space .
Borel topological rigidity conjecture
LandmarkConjecture1953Let and be closed, connected, topological -manifolds with and contractible universal covers. Every homotopy equivalence is homotopic to a homeomorphism.
Novikov higher-signature conjecture
LandmarkConjecture1970Let be a closed connected oriented smooth manifold, let , let classify its universal cover, and let . The higher signature
is invariant under orientation-preserving homotopy equivalence. Here is the total Hirzebruch -class of , and only the top-degree component is evaluated.
Weinstein conjecture
LandmarkConjecture1978Let be a closed smooth manifold and let be a contact form, so is nowhere zero. The Reeb vector field , uniquely defined by and , has a nonconstant periodic orbit.
The -conjecture
MajorConjecturec. 1980If is a closed, connected, oriented, smooth spin -manifold, then
where and is the signature of the intersection form on .
K-theoretic Farrell–Jones isomorphism conjecture
MajorConjecture1993For every discrete group , every associative unital ring , and every integer , the assembly map
is an isomorphism. Here is the terminal -CW complex whose -fixed points are contractible for virtually cyclic and empty otherwise, and is the equivariant homology theory whose value at is .
Hopf sign conjecture
MajorConjecturec. 1931If is a closed connected Riemannian manifold with sectional curvature , then
Bott rational-ellipticity conjecture
MajorConjecturec. 1982If is a closed simply connected smooth manifold that admits a Riemannian metric of nonnegative sectional curvature, then is rationally elliptic, meaning
Cartan–Hadamard isoperimetric conjecture
MajorConjecture1976Let be a complete simply connected Riemannian -manifold with sectional curvature , and let be a relatively compact domain with smooth boundary. Then
where is the Euclidean volume of the unit ball in .
Positive sectional curvature on
MajorOpen problemc. 1965There exists a smooth Riemannian metric on such that every -plane , at every , has sectional curvature .
Yau nodal-set conjecture
MajorConjecture1982For every closed smooth Riemannian -manifold there are constants such that every nonzero real eigenfunction satisfying , , obeys
Nearby Lagrangian conjecture
MajorConjecturec. 1980Let be a closed connected smooth manifold and its cotangent projection. Define the canonical Liouville -form by . If is a closed connected Lagrangian submanifold and for some smooth , then a compactly supported Hamiltonian isotopy of carries to the zero section.
Slice–ribbon conjecture
MajorConjecture1962If a smooth knot bounds a smoothly and properly embedded disk , then bounds a smooth immersion whose only self-intersections are ribbon singularities: transverse double arcs for which one preimage arc lies in and the other has both endpoints on .
Cabling conjecture
MajorConjecture1983Let be a nontrivial knot, let be a slope in the meridian--longitude basis, and let denote the result of -Dehn filling the exterior of . If is reducible, then there are coprime integers with such that is obtained by placing the -torus-knot pattern in a tubular neighborhood of a companion knot, and .
Purely cosmetic surgery conjecture
MajorConjecture1990Let be a nontrivial knot and, for each slope in the meridian--longitude basis, let denote the result of -Dehn filling its exterior. If and and are orientation-preservingly homeomorphic, then .
-space conjecture
MajorConjecture2013–2015Let be a closed, connected, orientable, irreducible rational-homology -sphere, and let denote its hat Heegaard Floer homology. The following are equivalent: (i) , so is not an -space; (ii) admits a total order satisfying for all ; (iii) admits a coorientable taut codimension-one foliation.
Hyperbolic volume conjecture
MajorConjecture1997Let be a hyperbolic knot and let be its -colored Jones polynomial normalized by . Then
where the right-hand side is the complete finite-volume hyperbolic volume.
Carath\u00e9odory Umbilic Conjecture
MajorConjecture1924Every closed , strictly convex surface embedded in has at least two umbilic points, where the two principal curvatures are equal.
Invariant subspace problem for Hilbert space
LandmarkOpen problem1935–1950For every separable infinite-dimensional complex Hilbert space and every bounded linear operator , there is a closed linear subspace such that
Kakeya set conjecture in dimensions
LandmarkConjecturec. 1971Let and let be a Borel set such that for every there is with . Then .
Fourier restriction conjecture for the sphere
LandmarkConjecturec. 1967Let , let be surface measure on , and for define
If
(with for ), then there is such that for every .
Bochner–Riesz conjecture
LandmarkConjecturec. 1971Let , , and
For every Schwartz function and , define
Then .
Kannan–Lovász–Simonovits (KLS) conjecture
LandmarkConjecture1995There is a universal constant such that for every , every log-concave probability measure on satisfying and , and every locally Lipschitz ,
Baum–Connes conjecture without coefficients
LandmarkConjecture1982For every countable discrete group , the analytic assembly map
is an isomorphism. Here is the terminal -CW complex whose -fixed-point space is contractible for finite subgroups and empty for infinite ; is equivariant topological -homology with -compact supports; and is the operator-norm closure of the left regular representation of on .
Free-group-factor isomorphism problem
LandmarkOpen problemc. 1943For each integer , let be the free group on generators, let be its left regular representation on , and define the free group factor . Determine which of the following alternatives holds: for every , or whenever , where denotes a unital normal -isomorphism of von Neumann algebras.
Kadison similarity problem
MajorOpen problem1955For every unital -algebra , every complex Hilbert space , and every bounded unital algebra homomorphism , there is an invertible such that is a -homomorphism.
Separable quotient problem
MajorOpen problem1932Every infinite-dimensional Banach space has a closed linear subspace such that the quotient Banach space is both separable and infinite-dimensional.
Mazur rotation problem
MajorOpen problem1932Let be a separable real Banach space such that for every with , there is a surjective linear isometry with . Then is linearly isometric to a real Hilbert space.
Crouzeix conjecture
MajorExact constant problem2004For every complex Hilbert space , every , and every complex polynomial ,
Pompeiu–Schiffer conjecture
MajorConjecture1929Let and let be a bounded connected domain with connected boundary and outward unit normal . If there are and a nonconstant such that
for one constant , then is a Euclidean ball.
Beurling–Ahlfors operator norm conjecture
MajorExact constant problem1982For , let be Lebesgue area measure and define the Beurling--Ahlfors transform on Schwartz functions by
Then its -operator norm is .
Brennan conjecture
MajorConjecture1978Let be Lebesgue area measure, let be simply connected, and let be conformal. For every real with ,
Equivalently, for a conformal , for every .
Corona problem for the unit ball
MajorOpen problemc. 1962Let and be integers, let , and let be the algebra of bounded holomorphic functions on . If satisfy
then there exist such that for every .
Pólya eigenvalue conjecture
MajorConjecture1954Let be a bounded domain with piecewise smooth boundary and volume , and let be the volume of the Euclidean unit ball in . Write for its Dirichlet Laplacian eigenvalues and for its Neumann eigenvalues, with multiplicity. For every ,
Two-dimensional Fuglede conjecture
MajorCanonical finite case1974Let be a bounded Lebesgue measurable set of positive measure. The following are equivalent: (i) there is a countable such that is an orthonormal basis of ; (ii) there is a countable such that for almost every .
Diagonal Fourier extension conjecture for compact paraboloids
MajorConjecturec. 1967Let , let , and let , where is surface measure and is nonzero. Define
For every there is a constant such that
for every .
Connes Rigidity Conjecture for Property- Groups
MajorConjecturec. 1982If and are countable ICC groups with Kazhdan's property , then every isomorphism of their group von Neumann algebras,
implies that . Here ICC means that every nonidentity conjugacy class is infinite.
Hyperlinear Group Conjecture
MajorConjecturec. 2000Every countable group is hyperlinear: there are integers and an injective homomorphism
where the metric ultraproduct uses normalized Hilbert--Schmidt distance and a nonprincipal ultrafilter.
Heil–Ramanathan–Topiwala Conjecture
MajorConjecture1996For every nonzero and every finite set of distinct points , the time--frequency translates
are linearly independent in .
Three-dimensional Navier–Stokes existence and smoothness
Open problem1934Let be , divergence-free, and satisfy for every and multi-index . There exist and satisfying
for all , with for every .
Weak cosmic censorship (future-null-infinity form)
Conjecture1969Let be the space of smooth, complete vacuum initial data on satisfying and . In fixed asymptotic coordinates, put and require and for every multi-index . Give the relative weighted topology induced by the seminorms
on differences . There is an open dense subset of whose maximal globally hyperbolic developments have a conformal completion with complete future null infinity , meaning that every physical null geodesic ending at has infinite affine length.
Global regularity for three-dimensional incompressible Euler
LandmarkOpen problemc. 1930For every divergence-free Schwartz vector field , the maximal classical solution of
exists for all and belongs to .
Global regularity for inviscid surface quasi-geostrophic flow
LandmarkOpen problem1994For every , the unique maximal classical solution of
exists for every and is smooth, where is the -th Riesz transform.
strong cosmic censorship
LandmarkConjecturec. 1979Fix a closed smooth -manifold and a smooth background Riemannian metric . Let be the space of smooth pairs , with Riemannian and symmetric, satisfying and . Give it the relative Fréchet topology induced by , , on differences . In every nonempty connected component of , the data whose maximal globally hyperbolic development admits no proper isometric embedding into a connected Lorentzian manifold with metric form a residual set, meaning a countable intersection of open dense sets.
De Giorgi conjecture in dimensions through
LandmarkConjecture1978Let . If is bounded, satisfies
then is one-dimensional: there are and such that for every .
Nonlinear Stability of Subextremal Kerr Black Holes
LandmarkConjecturec. 1965For every fixed Kerr exterior with mass and angular momentum parameter , 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.
Global regularity for three-dimensional incompressible MHD
MajorOpen problemc. 1950For every pair of smooth divergence-free vector fields , the unique local smooth solution of
extends smoothly for all .
Global regularity for the two-dimensional inviscid Boussinesq system
MajorOpen problemc. 1980For every and with , the maximal classical solution of
exists for all and is smooth.
Global classical solutions of the relativistic Vlasov–Maxwell system
MajorOpen problemc. 1980Let be nonnegative and let satisfy and . With , the system
has a unique classical solution for all .
Uniform finiteness in Hilbert's sixteenth problem
Open problem1900For every integer , there is an integer such that every planar polynomial vector field
having only finitely many limit cycles has at most limit cycles. A limit cycle is an isolated periodic orbit.
closing lemma
LandmarkConjecturec. 1960Let be a closed smooth manifold, , , and a nonwandering point of : every neighborhood has for some . For every neighborhood of , there is for which for some .
Density of hyperbolicity for rational maps
LandmarkConjecturec. 1920For every , hyperbolic maps are dense in the space of degree- rational maps , with its coefficient topology. Here is hyperbolic when the closure of the forward orbits of all its critical points is disjoint from its Julia set .
Mandelbrot local-connectivity conjecture
LandmarkConjecturec. 1982The Mandelbrot set
is locally connected: for every and every neighborhood of , there is a connected neighborhood of in the subspace with .
Birkhoff billiard conjecture
LandmarkConjecture1927Let be bounded with , strictly convex boundary. Its billiard phase space is the open annulus , with the billiard map sending one reflected state to the next. If is foliated by invariant circles homotopic to its boundary, then is an ellipse.
Positive metric entropy for the standard map
LandmarkOpen problemc. 1980There exists such that the area-preserving standard map
of has positive Kolmogorov--Sinai entropy with respect to normalized Lebesgue measure.
Furstenberg measure conjecture
LandmarkConjecture1967Let be a Borel probability measure on that is invariant under and , and ergodic for their joint action: every Borel set invariant modulo under both maps has measure or . Then either is Lebesgue measure or there is a finite set , invariant under both and , such that .
Sarnak Möbius disjointness conjecture
LandmarkConjecture2010Define the Möbius function by , if a prime square divides , and if is a product of distinct primes. For every compact metric space , every continuous map with zero topological entropy, every , and every ,
Ivrii periodic-billiard conjecture
MajorConjecture1980Let be a bounded domain with boundary, and let , equipped with its canonical Liouville measure. The set of points of that are periodic under the billiard map has measure zero.
Anosov-manifold conjecture
MajorConjecturec. 1970Every closed connected smooth manifold that admits an Anosov diffeomorphism is homeomorphic to an infranilmanifold, namely a quotient , where is a simply connected nilpotent Lie group and is a torsion-free discrete subgroup of for some compact subgroup , acting freely and cocompactly on .
Rokhlin multiple-mixing problem
MajorOpen problem1949Let be an invertible measure-preserving transformation of a standard probability space . If as for all , then for every , all , and all integer sequences satisfying, as ,
one has
Banach simple-Lebesgue-spectrum problem
MajorOpen problem1932There exist a standard nonatomic probability space and an invertible ergodic measure-preserving transformation such that the Koopman operator , restricted to
is unitarily equivalent to the bilateral shift on , defined by .
Pugh–Shub stable-ergodicity conjecture
MajorConjecture1997Let be a closed connected manifold with a smooth probability volume , and fix a Riemannian norm on . For a linear map , write . A , -preserving diffeomorphism is partially hyperbolic here if it has a continuous -invariant splitting into nonzero bundles and an integer such that, for every ,
Among these diffeomorphisms, the stably ergodic ones are -dense; stable ergodicity means that every sufficiently -near , -preserving diffeomorphism is ergodic.
Improbability of noncollision singularities
MajorConjecturec. 1984Fix and masses . For , consider
and the collision-free phase space . With respect to Lebesgue measure on , the set of initial conditions whose maximal solution has a finite endpoint while
has measure zero.
Gottschalk Surjunctivity Conjecture
MajorConjecture1973For every group and every finite alphabet , every continuous -equivariant injective map , with carrying the product topology and the shift action, is surjective.
Hadamard Matrix Conjecture
LandmarkConjecture1893For every integer , there is a matrix such that
Here is the identity matrix.
Union-Closed Sets Conjecture (Frankl's Conjecture)
LandmarkConjecture1979Let be a finite, nonempty family of finite sets such that for all , and assume . Then some element belongs to at least members of .
Erdős–Rado Sunflower Conjecture
LandmarkConjecture1960For every integer there is a constant such that, for every , every family of more than distinct -element sets contains distinct satisfying
(Such a family is an -sunflower.)
Erdős–Szekeres Convex Polygon Conjecture
LandmarkConjecture1935For , let be the least integer such that every -point set in the plane with no three collinear contains points that are the vertices of their convex hull. Then
Brown–Erdős–Sós Conjecture
LandmarkConjecture1973For every integer and every real , there is an integer such that every -uniform hypergraph with and has distinct edges satisfying
Here -uniform means that every edge has exactly three vertices.
Lonely Runner Conjecture
MajorConjecture1967For every integer and every set of distinct positive integers , there exists such that
where .
Ryser–Brualdi–Stein Latin Transversal Conjecture
MajorConjecture1967–1975Let be a Latin square of order , meaning an array on 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:
and, if is odd, every has a transversal of size .
Rota's Basis Conjecture
MajorConjecturec. 1989Let be an -dimensional vector space over a field, and let be (not necessarily distinct) bases of . It is possible to order each so that is a basis of for every .
Turán's Tetrahedron Conjecture
MajorConjecture1941Let be the -uniform hypergraph consisting of all four triples on a four-element vertex set, and let be the largest number of edges in an -vertex -free -uniform hypergraph. Then
Ryser's Conjecture for -Partite Hypergraphs
MajorConjecturec. 1971If is an -uniform -partite hypergraph (its vertices split into classes and every edge contains exactly one vertex from each class), let be the largest size of a family of pairwise disjoint edges and let be the smallest size of a vertex set meeting every edge. Then
Alon–Tarsi Latin Square Conjecture
MajorConjecture1990Let be even. Regard every row and every column of a Latin square of order as a permutation of its symbol set, and define
The number of Latin squares of order with sign is different from the number with sign .
Existence of a Finite Projective Plane of Order
MajorCanonical finite caseUnknownDo there exist sets (points) and (lines), each of size , and an incidence relation , such that every line is incident with exactly points, every point is incident with exactly lines, every two distinct points lie on exactly one common line, and every two distinct lines meet in exactly one point?
1/3–2/3 Conjecture for Posets
MajorConjecture1968Let be a finite poset that is not a chain, and let be its set of linear extensions. For incomparable , put
Then some incomparable pair satisfies
Hadwiger's Conjecture
LandmarkConjecture1943Let be the chromatic number of a finite simple graph , and let denote the complete graph on vertices. Then contains as a minor; equivalently, has pairwise-disjoint nonempty connected branch sets with at least one edge between every two branch sets.
Graph Reconstruction Conjecture
LandmarkConjecture1942If and are finite simple graphs on the same number of vertices and the multisets of unlabeled graphs
are equal, then , where denotes the induced graph obtained by deleting .
Tutte's -Flow Conjecture
LandmarkConjecture1954Every finite bridgeless loopless multigraph admits an orientation of its edges and a function such that, for every vertex ,
Here and are respectively the sets of edges directed out of and into .
Berge–Fulkerson Conjecture
LandmarkConjecture1971–1972Every finite bridgeless cubic loopless multigraph has six perfect matchings , repetitions allowed, such that every edge of belongs to exactly two of the .
Caccetta–Häggkvist Conjecture
LandmarkConjecture1978Let be a finite simple loopless digraph on vertices with minimum outdegree at least . Then contains a directed cycle of length at most
Sidorenko's Conjecture
LandmarkConjecture1986–1991For every finite bipartite graph and every symmetric measurable ,
Erdős–Hajnal Conjecture
LandmarkConjecture1977–1989For every finite graph , there exists such that every -vertex simple graph with no induced subgraph isomorphic to has either a clique or an independent set of size at least .
Gyárfás–Sumner Conjecture
LandmarkConjecture1975–1981For every finite tree and integer , there is an integer such that every finite simple graph with chromatic number and no clique on vertices contains an induced subgraph isomorphic to . Here is the least number of colors in a proper vertex coloring, and an induced copy uses exactly the edges of between its chosen vertices.
Lovász Hamiltonian-Path Conjecture
LandmarkConjecture1969Every finite connected vertex-transitive graph has a Hamiltonian path. A graph is vertex-transitive if, for every two vertices , it has an automorphism sending to ; a Hamiltonian path visits every vertex exactly once.
Multicolor Triangle Ramsey Growth
LandmarkOpen problemc. 1970Let be the least such that every coloring of the edges of with colors contains a monochromatic triangle. Determine its exponential order, in particular whether
Barnette's Conjecture
MajorConjecture1969Every finite simple, cubic, bipartite, planar, -vertex-connected graph has a Hamiltonian cycle.
Total Coloring Conjecture
MajorConjecture1964–1965A total coloring of a finite simple graph assigns colors to so that adjacent vertices, adjacent edges, and every incident vertex--edge pair receive different colors. If is the least number of colors in such a coloring, then
Here is the maximum vertex degree of .
List Edge-Coloring Conjecture
MajorConjecturec. 1975For every finite loopless multigraph ,
where is its edge-chromatic number and is the least such that, whenever every edge is assigned a list of at least colors, a proper edge coloring exists.
Graceful Tree Conjecture
MajorConjecture1963–1967Every tree with edges admits a bijection such that
Conway's Thrackle Conjecture
MajorConjecture1969Let a finite simple graph 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
Harary–Hill Conjecture for the Crossing Number of
MajorExact constant problem1960–1963Let be the minimum number of pairwise edge crossings over plane drawings of a graph in general position. For every integer ,
Albertson's Crossing-Number Conjecture
MajorConjecture2007Every finite simple graph satisfies
Here is the minimum number of edge crossings in a plane drawing of , is its chromatic number, and is the complete graph on vertices.
Erdős–Gyárfás Power-of-Two Cycle Conjecture
MajorConjecture1995Every finite simple graph of minimum degree at least contains a cycle whose length is a power of .
Tuza's Triangle Packing–Covering Conjecture
MajorConjecture1981For a finite simple graph , let be the maximum number of pairwise edge-disjoint triangles and let be the minimum number of edges meeting every triangle. Then
Reed's – Chromatic Conjecture
MajorConjecture1998Every finite simple graph satisfies
where is the maximum degree and the clique number.
Linear Arboricity Conjecture
MajorConjecture1980–1981Let be the least number of linear forests (forests whose components are paths, including isolated edges) whose edge sets partition . Every finite simple graph with maximum degree satisfies
Exact Ramsey Number
MajorExact constant problemUnknownDetermine the least integer such that every red--blue coloring of the edges of contains a monochromatic .
Seymour's Second Neighborhood Conjecture
MajorConjecturec. 1990Let be a finite oriented graph (no loops and no pair of oppositely directed edges). For , let be its out-neighborhood and let be the set of vertices whose directed distance from is exactly . Then some vertex satisfies
Meyniel's Conjecture on the Cop Number
MajorConjecture1985In the perfect-information game on a finite connected simple graph , 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 is the minimum number of cops having a winning strategy, then there is an absolute constant such that every -vertex satisfies
Chvátal's Toughness Conjecture
MajorConjecture1973There exists a real constant such that every finite simple -tough graph on at least three vertices is Hamiltonian. Here is -tough if, for every vertex set with ,
where is the graph obtained by deleting and denotes the number of connected components.
Erdős–Faber–Lovász Conjecture
MajorConjecture1972Let be a finite linear hypergraph on vertices, meaning that any two distinct hyperedges meet in at most one vertex. Its hyperedges can be colored with at most colors so that intersecting hyperedges receive different colors.
Perfect One-Factorization Conjecture
MajorConjecture1964For every integer , the edge set of the complete graph can be partitioned into perfect matchings such that is a Hamiltonian cycle whenever . 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.
Erd\u0151s–Simonovits Compactness Conjecture
MajorConjecture1982For every finite nonempty family of graphs, each containing a cycle, there are and such that
for all sufficiently large , where is the largest number of edges in an -vertex graph containing no member of .
Erd\u0151s Degeneracy Conjecture for Extremal Numbers
MajorConjecture1967For every integer and every fixed bipartite -degenerate graph ,
A graph is -degenerate if every nonempty subgraph has a vertex of degree at most .
Zarankiewicz Problem for
MajorOpen problem1951Determine the asymptotic order of
the largest number of edges in an -vertex graph containing no copy of the complete bipartite graph .
Hadwiger–Nelson Problem
LandmarkExact constant problem1950Determine
Erdős Distinct-Distances Conjecture
LandmarkConjecture1946Let
There is an absolute constant such that, for all ,
Falconer's Distance Set Conjecture
LandmarkConjecture1985Let and let be compact. Write for Hausdorff dimension. If
then its distance set has positive one-dimensional Lebesgue measure.
Hadwiger–Levi Illumination Conjecture
LandmarkConjecture1957–1960Let , let be the unit sphere, and let be a convex body. Say that a direction illuminates if for some . There exist at most directions such that every point of is illuminated by at least one of them.
Mahler Volume-Product Conjecture
LandmarkConjecture1939For a convex body containing in its interior, put . If , then
For arbitrary , let be its Santaló point, the minimizer of over . Then
Danzer's Problem
LandmarkOpen problemc. 1965Does there exist a locally finite set and a constant such that every convex set of area meets , while
Toeplitz Square-Peg Conjecture
LandmarkConjecture1911For every continuous injective map , the Jordan curve contains four distinct points that are the vertices of a nondegenerate Euclidean square.
Kneser–Poulsen Conjecture
LandmarkConjecture1954–1955Let , , and satisfy
Writing for the closed Euclidean ball and for -dimensional Lebesgue measure, one has
and
High-Dimensional Sphere-Packing Exponent
LandmarkOpen problemc. 1900Let be the supremal density of a packing of congruent balls in . Determine the exponential asymptotics of , equivalently determine
and decide whether these two quantities are equal.
Exact Growth of the Planar Unit-Distance Function
MajorOpen problem1946For , set
and
Determine the exact value of (and, more finely, the asymptotic order of ).
Erdős–Ulam Rational-Distance Problem
MajorOpen problem1946Does there exist a countable dense set such that
Reinhardt's Smoothed-Octagon Conjecture
MajorConjecture1934For a centrally symmetric convex disk , define
where the supremum is over full-rank lattices for which the interiors of the translates , , are pairwise disjoint. Let 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
Kalai's Conjecture
MajorConjecture1989Every centrally symmetric convex -polytope has at least nonempty faces in total, counting faces of every dimension and counting the polytope itself.
Five-Dimensional Kissing Number
MajorExact constant problemUnknownLet . Determine
Equivalently, is the maximum number of nonoverlapping unit -balls that can simultaneously touch a fixed unit -ball.
Optimal Sphere Packing in Dimension Five
MajorConjecturec. 1900For a packing of congruent closed balls in with disjoint interiors, define its upper asymptotic density by
where is the radius- ball centered at . Let be the supremum of over all such packings. Then
the density attained by the root-lattice packing.
Four-Dimensional Borsuk Problem
MajorCanonical finite case1933Let be the least such that every bounded set of positive diameter can be partitioned into subsets, each having diameter strictly smaller than . Is
Lebesgue's Universal Covering Problem
MajorExact constant problem1914Let
Determine the exact value of , and whether the infimum is attained.
Ehrhart Volume Conjecture
MajorConjecture1964Let be a convex body whose barycenter is the origin and whose only interior lattice point is . Then
Moreover, equality holds only for unimodular images of the centered simplex
No Infinite Cluster at Critical Percolation on
LandmarkConjecturec. 1960For Bernoulli bond percolation on , independently declare each nearest-neighbor edge open with probability , and let be the threshold for an infinite open cluster. Then for every ,
Two-dimensional self-avoiding-walk critical exponents
LandmarkConjecture1972–1982For , let
and put . Let , whose existence is known, and let and denote the uniform probability law on and expectation with respect to that law. There exist constants such that, as ,
Thus the counting and metric critical exponents are respectively and .
KPZ fluctuation exponent for two-dimensional first-passage percolation
LandmarkConjecturec. 1986Give each unoriented nearest-neighbor edge of an independent exponential random variable of mean . For , define
where the minimum is over finite nearest-neighbor paths from to . If , then
Strict Convexity of the First-Passage Percolation Limit Shape
MajorConjecturec. 1965Assign independent mean-one exponential passage times to the nearest-neighbor edges of , . Let be the deterministic compact convex limit shape from the first-passage percolation shape theorem. Then is strictly convex: its boundary contains no nontrivial line segment.
Optimal i.i.d. Berry–Esseen constant
MajorExact constant problem1942Let be the standard normal distribution function. For i.i.d. real-valued random variables , define
Determine exactly.
Gaussian Product Inequality Conjecture
MajorConjecture2012For every integer , every centered jointly Gaussian random vector with for all , and every choice of real exponents ,
Metric-TSP subtour-LP conjecture
LandmarkConjecturec. 1980For every integer , let , and let satisfy for all distinct . Let be the minimum -length of a Hamilton cycle, and define
where is the set of edges having exactly one endpoint in . Then, with the supremum restricted to instances satisfying ,
Strongly polynomial finite Markov decision processes
MajorOpen problemc. 1983There is a strongly polynomial algorithm which, given a finite state set , finite nonempty action sets , rational transition probabilities , rational rewards , and rational , returns a stationary deterministic policy maximizing
simultaneously for every initial state , using a number of arithmetic operations polynomial only in and maintaining intermediate encoding lengths polynomial in the input length.
Beardwood–Halton–Hammersley planar TSP constant
MajorExact constant problem1959Let be independent random points uniformly distributed on , and let be the minimum Euclidean length of a closed polygonal tour visiting . The almost-sure limit
exists and is a deterministic positive constant. Determine exactly.
Modified integer round-up property for bin packing
MajorConjecturec. 1985Given item sizes , let . Let be the minimum number of patterns from , with repetitions allowed, whose incidence vectors sum coordinatewise to at least , and let
Then .
Strongly polynomial linear programming
LandmarkOpen problem1983There is an algorithm which, for every rational , , and , decides whether
is infeasible, unbounded, or has an optimum and, in the last case, returns an exact optimal solution, using at most elementary arithmetic operations and comparisons for one fixed polynomial , while every intermediate rational number has encoding length polynomial in the total input encoding length.
Polynomial pivot rule for the simplex method
LandmarkOpen problemc. 1972There exist a deterministic or randomized simplex pivot rule and a polynomial such that, for every bounded nondegenerate rational linear program
and every feasible starting basis, the simplex method using that rule reaches an optimal basis after at most pivots (in expectation over the rule's randomness in the randomized case).
Polynomial Hirsch conjecture
MajorConjecturec. 1992There is a polynomial such that, for all integers , , and every -dimensional convex polytope having exactly facets, the graph whose vertices and edges are the - and -dimensional faces of has diameter at most .
versus
Open problem1971Is
Here is the class of decision languages recognized by deterministic Turing machines in polynomial time, and is the class recognized by nondeterministic Turing machines in polynomial time (equivalently, languages with polynomial-size certificates verifiable in deterministic polynomial time).
versus
LandmarkOpen problemc. 1970Is
Here and are the languages decidable by, respectively, deterministic and nondeterministic Turing machines using work-tape cells on inputs of length , with read-only input.
Derandomization Conjecture
LandmarkConjecture1977–1985 where is deterministic polynomial time and consists of languages decided by probabilistic polynomial-time Turing machines that give the correct answer with probability at least on every input.
versus
LandmarkOpen problemc. 1980Is
Here , and consists of languages decided by logspace-uniform families of polynomial-size Boolean circuits with bounded fan-in and depth ; is deterministic polynomial time.
Valiant's versus Conjecture
LandmarkConjecture1979Over ,
The class consists of polynomial families , with for some polynomial , whose degrees and arithmetic-circuit sizes are bounded by polynomials in . The class consists of polynomial families for which there are a polynomial and a family such that
Unique Games Conjecture
LandmarkConjecture2002For every , there is an alphabet size , where , such that the following promise problem is -hard. The input is a finite directed constraint graph in which every arc carries a permutation of ; a labeling satisfies that arc when . Distinguish
Exponential Time Hypothesis
LandmarkConjecture1999No deterministic algorithm decides satisfiability of -CNF formulas with variables in time , where a -CNF is a conjunction of clauses, each containing at most three literals.
Graph Isomorphism in Polynomial Time
LandmarkOpen problemc. 1971Is there a deterministic polynomial-time algorithm that, given adjacency matrices of two finite simple -vertex graphs , decides whether there exists a permutation of their vertices satisfying
Deterministic Polynomial-Time Integer Factoring
LandmarkOpen problemc. 1975Is there a deterministic algorithm that, on binary input , outputs the prime factorization of in time polynomial in ?
Existence of One-Way Functions
LandmarkOpen problem1976Does there exist a polynomial-time computable, length-preserving function family such that, for every probabilistic polynomial-time algorithm that outputs an -bit string (or failure), and every polynomial , for all sufficiently large ,
Quantum PCP Conjecture
LandmarkConjecturec. 2006There exist constants and such that the following promise problem is -hard: given an -qubit Hamiltonian , where , each acts on at most qubits and , distinguish
where is the least eigenvalue of . Here is bounded-error quantum polynomial-time verification with a polynomial-size quantum witness.
Matrix Multiplication Exponent
LandmarkConjecturec. 1969Over the concrete field , let
Then
versus
LandmarkOpen problemc. 1994Is
Here is classical probabilistic polynomial time with error at most , and 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 .
Deterministic Polynomial Identity Testing
LandmarkOpen problemc. 1980Is there a deterministic polynomial-time algorithm which, given a division-free arithmetic circuit over 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?
Simple Stochastic Games in Polynomial Time
LandmarkOpen problem1992A simple stochastic game is a finite directed graph whose vertices are partitioned into MAX, MIN, random, and two absorbing sink vertices labeled and . 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 . Starting from a specified vertex , MAX receives payoff exactly when play eventually reaches sink , and payoff otherwise. If
where and range over strategies of MAX and MIN, is there a deterministic polynomial-time algorithm deciding whether ?
Small-Set Expansion Hypothesis
LandmarkConjecture2010For a finite -regular graph and a nonempty set , define its edge expansion by
where is the set of edges with one endpoint in and the other outside . For every constant , there is a rational constant such that the following promise problem is -hard, on input sizes for which is an integer:
MajorConjecturec. 1980
There is a language in that is not decided by any family of Boolean circuits of size polynomial in , where decides membership for all inputs of length ; in symbols,
Here is nondeterministic polynomial time, and is the class defined by such polynomial-size, nonuniform circuit families.
Strong Exponential Time Hypothesis
MajorConjecture2001For every there exists an integer such that -SAT—satisfiability of CNF formulas whose clauses contain at most literals—on variables cannot be decided by a deterministic algorithm in time
Log-Rank Conjecture
MajorConjecture1988There is an absolute constant such that every nonconstant total Boolean function satisfies
where and is the minimum worst-case number of communicated bits in a deterministic two-party protocol computing .
Aanderaa–Karp–Rosenberg Evasiveness Conjecture
MajorConjecturec. 1973Fix , and let be a nontrivial property of simple labeled -vertex graphs that is invariant under vertex permutations and monotone under adding edges, where nontrivial means that is neither empty nor the set of all such graphs. Every deterministic algorithm that decides whether an unknown graph has by adaptively querying edge presence has worst-case query complexity
Berman–Hartmanis Isomorphism Conjecture
MajorConjecture1977If are both -complete, where is nondeterministic polynomial time, and completeness is under polynomial-time many-one reductions, then there exists a bijection such that and are polynomial-time computable and
APSP Hypothesis
MajorConjecturec. 2010For every , there is no -time word-RAM algorithm which, given an -vertex directed graph with -bit integer edge weights and no negative directed cycle, outputs the shortest-path distance for every ordered pair of vertices. The distance from to is the minimum total weight of a directed -to- path, or if no such path exists.
Modern 3SUM Conjecture
MajorConjecturec. 1995For every , there is no randomized bounded-error -time word-RAM algorithm that, given distinct -bit integers, decides whether three distinct input integers satisfy
Orthogonal Vectors Conjecture
MajorConjecturec. 2005For every , there is a constant such that no randomized bounded-error -time algorithm, given with and , decides whether there exist with
Planted Clique Conjecture
MajorConjecture1992–1998For every fixed , there is no randomized polynomial-time algorithm such that, for all sufficiently large , the following hypotheses are distinguished:
More precisely, no such satisfies for both .
NP-Hardness of the Minimum Circuit Size Problem
MajorOpen problemc. 1975The Minimum Circuit Size Problem (MCSP) takes as input the -bit truth table of a Boolean function and an integer , and asks whether has a Boolean circuit over the fixed complete basis , with and of fan-in two, and with at most gates. Is MCSP -hard under deterministic polynomial-time many-one reductions?
Feige's Random -SAT Refutation Hypothesis
MajorConjecture2002For every sufficiently large constant , there is no randomized polynomial-time algorithm having both of the following properties. First, for every satisfiable -CNF formula , never outputs . Second, if is formed on variables by choosing clauses independently and uniformly, each clause using three distinct variables with independent uniformly random signs, then
where the probability includes the randomness of both the formula and .
Quantum Parallel Repetition Conjecture
MajorConjecture2004For every finite two-player one-round game whose entangled value satisfies , there is a constant such that the entangled value of the -fold parallel repetition obeys
Fixed-Polynomial-Factor Hardness of Euclidean Closest Vector
MajorConjecturec. 2003There exists a constant for which the following promise problem is -hard under deterministic polynomial-time many-one reductions: given a lattice basis , target , and radius , distinguish
Main Conjecture for MDS Codes
LandmarkConjecture1955Let be a prime power and . If is a -dimensional linear code whose minimum Hamming distance is , then
except that, when is even and , the asserted bound is . The Hamming distance between two words is the number of coordinates in which they differ; a code meeting the general bound is called maximum-distance separable (MDS).
Shannon capacity of the seven-cycle
MajorExact constant problem1956For finite simple graphs , define their strong product to have vertex set , with distinct and adjacent exactly when, in each coordinate, the entries are equal or adjacent and in at least one coordinate they are adjacent. Write for the -fold strong product and for the maximum size of an independent vertex set. Determine exactly
where is the cycle on seven vertices.
Capacity of the binary deletion channel
MajorExact constant problemc. 1961Fix . On input , independently delete each coordinate with probability and output the undeleted bits in their original order, without deletion markers. Let be the largest cardinality of a code for which some decoder has average error at most under a uniformly selected codeword. Determine, for every ,
Binary asymptotic rate–distance improvement problem
MajorOpen problem1952–1957For , let be the largest cardinality of a set whose distinct words have Hamming distance at least , and define
Decide whether there exists for which
Asymptotic Spherical-Code Rate
MajorOpen problem1959For , let be the largest number of unit vectors in whose pairwise inner products are at most . Determine the asymptotic rate
for every fixed , and determine where the corresponding limit exists.
Li–Li Undirected Network Coding Conjecture
MajorConjecture2004For 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.
Twelve-stage ninth-order explicit Runge–Kutta method
MajorCanonical finite casec. 1964Determine whether there exist real coefficients () and (), with , such that the explicit Runge--Kutta one-step map
has classical order : for every integer , every sufficiently smooth , and every exact solution of , one step initialized at satisfies as .
Yang–Mills existence and mass gap
Open problem2000For every compact simple gauge group , construct gauge-invariant Euclidean Yang--Mills Schwinger functions on 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 and a subset of for some .
Haldane gap for the spin- Heisenberg chain
LandmarkConjecture1983For every integer , on with periodic boundary conditions let
where are the spin- generators at site . If are its two lowest distinct eigenvalues, then
Anderson delocalization in dimension
LandmarkConjecture1958Let and
where the are iid with a bounded compactly supported density that is positive near . For all sufficiently small , there is a nonempty open interval in the interior of on which has almost surely nonempty purely absolutely continuous spectrum.
Quantum unique ergodicity
LandmarkConjecture1994Let be a closed connected Riemannian manifold with strictly negative sectional curvature, and let , , with . For every classical order-zero pseudodifferential operator ,
Here , is the degree-zero principal symbol restricted to , and is normalized Liouville probability measure.
General spacetime Penrose inequality
LandmarkConjecture1973Let be a smooth, connected, orientable, complete asymptotically flat initial data set. Define its energy and momentum densities by
assume the dominant energy condition , 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 and marginally inner trapped components . Define to be the infimum of the total -areas of smooth closed surfaces enclosing relative to the chosen end. If the ADM energy-momentum of the end is and , then
Equality should occur only when the exterior data arise from a spacelike slice of the Schwarzschild spacetime.
Critical three-dimensional Ising spin-field scaling limit
LandmarkConjecturec. 1970Let be the infinite-volume zero-field Gibbs state at the critical inverse temperature of the nearest-neighbor ferromagnetic Ising model on , where is the infimum of the inverse temperatures for which the infinite-volume plus state has positive magnetization. The spins are , and finite-volume weights are proportional to , with the sum over nearest-neighbor edges. For , set , , , and define a random tempered distribution by
As , converges in law in to a non-Gaussian random distribution . For every integer , its -point correlation distribution has a smooth restriction to pairwise distinct points, and there is such that every conformal diffeomorphism between open subsets of satisfies
for all pairwise distinct .
Maximal ionization conjecture
MajorConjecture1984For integers , on the fermionic space let
and set . There is a universal constant such that implies for every .
Three-dimensional Coulomb crystallization
MajorConjecturec. 1934Let , let , and let be the zero-mean periodic Coulomb Green function satisfying . For pairwise distinct , define the neutral-jellium energy, with the point self-energies omitted, by
Then
where is the thermodynamic energy per unit volume of the unit-density body-centered-cubic lattice under the same normalization.
Sharp three-dimensional Lieb–Thirring constant
MajorExact constant problem1976For every real , if are the negative eigenvalues of , counted with multiplicity, then
and is the optimal universal constant.
Optimal Lieb–Oxford constant
MajorExact constant problemc. 1981For each , let be the symmetric probability measures on with finite Coulomb energy and one-particle density , normalized by . Define
and
If , define
Then .
Homogeneous interacting Bose-gas condensation
MajorConjecture1925Let be a nonzero radial finite-range potential on with scattering length , let , and let be the -periodic extension of . For a normalized bosonic ground state of
let be its one-particle density matrix, normalized by . Then
Generalized Belgian Chocolate Problem
MajorExact constant problem1994Call a nonzero real polynomial Hurwitz stable if all of its complex zeros have strictly negative real part. Define
Determine exactly.
Polynomial-Time Computation of a Bimatrix Nash Equilibrium
LandmarkOpen problem1994Is there a deterministic polynomial-time algorithm that, given two rational payoff matrices , outputs mixed strategies and satisfying
Uniform -equilibrium in finite multiplayer stochastic games
MajorConjecturec. 1981Consider any stochastic game with a finite player set , finite state set , finite nonempty action set for each player at state , bounded stage payoff for each action profile , and transition law on . For every and initial state , there exist a behavioral-strategy profile and such that, for every horizon , every player , and every unilateral behavioral deviation ,
where is the state--action process generated by the indicated strategy profile and transition law.
Complete EFX allocation for additive goods
MajorConjecture2016For every finite agent set , finite set of indivisible goods, and nonnegative additive valuations , there is a partition of such that, for all and every ,
Vaught Conjecture
LandmarkConjecture1961Let be a countable first-order language and a complete -theory. The number of isomorphism classes of countable models of is either at most countable or exactly .
Decidability of the Real Exponential Field
LandmarkOpen problemc. 1950There exists an algorithm which, given any first-order sentence in the language , halts and correctly decides whether
Shelah’s Categoricity Conjecture for
LandmarkConjecturec. 1977Let be a sentence of the countable infinitary logic , which permits countable conjunctions and disjunctions but only finite strings of quantifiers. If has, up to isomorphism, exactly one model of some cardinality , then it has exactly one model of every cardinality , where , , and at limit ordinals.
HOD Conjecture
LandmarkConjecturec. 2010Assume there is an extendible cardinal, meaning a cardinal such that for every ordinal there are an ordinal and an elementary embedding with critical point and . Then there is a proper class of regular cardinals that are not -strongly measurable in . Here is the class of hereditarily ordinal-definable sets, and a regular is -strongly measurable in if there is with such that has no partition of into stationary sets.
Cherlin–Zilber Algebraicity Conjecture
MajorConjecturec. 1979Every infinite simple group of finite Morley rank is, as an abstract group, isomorphic to the group of -rational points of a simple algebraic group over an algebraically closed field .
Stable Fields Conjecture
MajorConjecturec. 1971If is an infinite field whose complete first-order theory in the language of rings is stable, then is separably closed.
NIP Fields Conjecture
MajorConjecturec. 2015Let 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: is separably closed; is real closed; or admits a nontrivial henselian valuation.
Martin’s Conjecture for Borel Turing-Invariant Functions
MajorConjecturec. 1978Let be the set of subsets of , identified with the reals, and let , , and denote Turing reducibility, Turing equivalence, and the Turing jump. A map is Turing-invariant if implies . A Turing cone is a set . For Borel Turing-invariant maps define
and write when both and . Then: 1. Every Borel Turing-invariant is either constant in Turing degree on a cone, or . 2. The quotient by of the maps satisfying is well-ordered by , and the immediate successor of is represented by .
Reinhardt Cardinal Inconsistency Problem
MajorOpen problem1967Prove in , without the axiom of choice, that there is no nontrivial elementary embedding . Equivalently, determine whether the existence of a Reinhardt cardinal, the critical point of such an embedding, is inconsistent with .