Hilbert’s tenth problem over the rationals
Can an algorithm always decide whether an equation with integer coefficients has a solution made of rational numbers?
Mathematics
Within Mathematics · Search all subjects
Hilbert’s sixteenth problem: limit cycles
A polynomial rule for motion in the plane can create isolated repeating trajectories. How many can occur when the polynomial degree is fixed?
Nonnegative inverse eigenvalue problem
Which lists of numbers can be the eigenvalues of a square matrix whose entries are all nonnegative?
Rota’s basis conjecture
Given n bases of an n-dimensional space, can their vectors always be rearranged into n new bases, each taking one vector from every original base?
Caccetta–Häggkvist conjecture
If every vertex of a directed graph points to many others, must the graph contain a correspondingly short directed cycle?
Falconer distance conjecture
A sufficiently large fractal set is predicted to determine a set of pairwise distances with positive ordinary length.
Sphere packing in five dimensions
How densely can identical nonoverlapping spheres fill five-dimensional Euclidean space?
Graph reconstruction conjecture
Delete each vertex of a graph in turn and keep the resulting graphs without labels. Does this collection determine the original graph?
Erdős–Szekeres convex polygon conjecture
How many points in the plane guarantee a convex polygon with a specified number of vertices? The proposed exact threshold remains unproved.
Erdős–Straus conjecture
Can every fraction 4/n, with n at least 2, be written as the sum of three reciprocals of positive integers?
Legendre’s conjecture
Must a prime number occur between n squared and the next integer’s square, however large n becomes?
Artin’s primitive root conjecture
For a fixed eligible integer, how often do its powers generate every nonzero residue modulo a prime?
Leopoldt’s conjecture
Do the independent units of a number field remain independent when measured using p-adic arithmetic?
Sarnak’s conjecture
Does the arithmetic Möbius sequence average to zero against every sequence generated by a system with zero topological entropy?
Kakeya conjecture
A set can contain a unit line segment pointing in every direction and still have zero volume. Must it nevertheless have full fractal dimension?
Turán’s tetrahedron problem
How many triples can a large collection of points contain while never containing all four triples on any four points?
Tutte’s five-flow conjecture
Can every graph without a bridge carry a balanced flow that never vanishes and uses only four positive magnitudes?
Erdős–Gallai cycle decomposition conjecture
Can the edges of any graph be split into only a constant times its number of vertices worth of cycles and individual edges?
Euler–Mascheroni constant
The difference between the harmonic series and a logarithm approaches a famous constant. Is that constant a ratio of integers?
Erdős–Moser equation
Can a power of an integer equal the sum of the same powers of every smaller positive integer, apart from 1 + 2 = 3?
Mersenne primes
Do prime numbers of the form 2 to a prime exponent, minus 1, continue forever?
Frege proof lower bounds
Can one exhibit propositional truths whose proofs must be superpolynomially long even in a flexible standard deductive system?
VP versus VNP
Can every polynomial described as a sum of efficiently computable terms itself be computed by a small arithmetic circuit?
Fourier Entropy–Influence conjecture
Does a yes-or-no rule’s sensitivity to flipped inputs limit how widely its Fourier weight can spread?