Erdős problems
Questions first asked or popularised by Paul Erdős, the prolific 20th-century mathematician who posed hundreds of problems, often with cash prizes.
13 AI-made results on Erdős problems, from 16 papers in the OpenAI math collection, each explained in plain English. 11 have a formal Lean proof listed; 2 are claimed in a paper and not yet machine-checked. They span 3 fields, led by combinatorics (8), number theory (4) and real and complex analysis (1). The oldest question here dates back to 1936: Erdős’s reciprocal-sum conjecture and quasipolynomial Szemerédi bounds. Rated Landmark: Planar distinct distances and unit-distance bounds.
Number theory4
-
Independent largest prime factors of consecutive integers
Resolves the Erdős–Pomerance joint Dickman conjecture: the logarithmic sizes of the largest prime factors of n and are asymptotically independent in ordinary natural density. In particular, the integers satisfying have density 1/2.
Formal proof listed -
An asymptotic formula for the number of totients
Gives an asymptotic equivalent for the number of distinct totient values up to x, with a positive bounded phase-dependent factor determined by convergent arithmetic approximations. In particular, for every fixed c > 0, answering Erdős and Hall’s scaling question.
Formal proof listed -
Short Egyptian fractions
Every rational with is a sum of distinct positive unit fractions. The worst-case minimum number of terms has the same order, resolving Erdős’s conjecture on short Egyptian fractions.
Formal proof listed -
Positive lower density of large prime gaps
For every fixed C > 0, a positive proportion of consecutive prime gaps exceed , throughout every sufficiently large initial segment of the primes. The proportion may depend on C. Consequently, the indices where increases have positive lower density, answering Erdős and Prachar.
Formal proof listed
Real and complex analysis1
-
The geometric case of the Erdős similarity conjecture
For every fixed , constructs compact subsets of with measure arbitrarily close to one containing no translated and nontrivially dilated copy of , with dilations of either sign. This resolves the geometric-progression case of the Erdős similarity conjecture for every ratio.
Formal proof listed
Combinatorics8
-
Erdős’s reciprocal-sum conjecture and quasipolynomial Szemerédi bounds
Proves Erdős's conjecture that every set of positive integers with divergent reciprocal sum contains arithmetic progressions of every finite length. Quantitatively, for each fixed k ≥ 3, every subset of with no nonconstant k-term progression has size at most , with positive constants depending only on k.
Formal proof listed -
Superexponential van der Waerden numbers
Resolves Erdős's superexponential-growth question for van der Waerden numbers. If is the least interval length forcing a monochromatic k-term progression in every r-coloring, then for an absolute c > 0, all r ≥ 2 and sufficiently large k, uniformly in r. In particular, for each fixed r.
Formal proof listed -
The higher-dimensional Erdős distinct-distances conjecture
For every fixed d ≥ 3, any n ≥ 2 distinct points in ℝd determine at least distinct distances, with depending only on dimension. This matches the integer-grid order and resolves the higher-dimensional Erdős distinct-distances conjecture with a constant-factor bound.
Claimed, not checked -
Planar distinct distances and unit-distance bounds
Proves the weak pinned Erdős distance conjecture: for every fixed ε > 0, all but points of any n-point planar set determine at least distinct nonzero distances. A complementary theorem bounds the number of unit-distance pairs by for an absolute δ > 0.
Formal proof listed -
The hypercube Ramsey conjecture
Resolves the Burr–Erdős hypercube Ramsey conjecture: the two-color Ramsey number of the n-dimensional cube is . Thus every red-blue coloring of a complete graph on a universal constant times the cube's number of vertices contains a monochromatic copy of the cube.
Claimed, not checked -
The Erdős–Gallai cycle-decomposition conjecture
Proves that the edges of every finite simple undirected graph on n vertices can be partitioned into at most simple cycles and single edges, for an absolute constant C. This resolves the Erdős–Gallai cycle-decomposition conjecture, bounding the number of pieces linearly even for dense graphs.
Formal proof listed -
Correspondence coloring with a fixed forbidden subgraph
Proves the Alon–Krivelevich–Sudakov coloring conjecture in correspondence-coloring form: graphs avoiding any fixed subgraph F need colors when their maximum degree Δ is sufficiently large. Also proves the Ajtai–Erdős–Komlós–Szemerédi independence conjecture: for fixed r ≥ 4, every n-vertex Kr-free graph of average degree d ≥ 2 has an independent set of size .
Formal proof listed -
Cycle–clique Ramsey numbers
Proves the Erdős–Faudree–Rousseau–Schelp conjecture: for every , except . This is the exact threshold forcing a red m-cycle or a blue n-clique in every red–blue coloring of a complete graph.
Formal proof listed