Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
1,221 problems
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Asks whether every infinite set of natural numbers has a shift k for which almost all integers have a divisor that is a member plus k.
Asks whether one constant C lets every tolerance and every N admit an almost covering system with distinct moduli all between N and C times N.
Asks whether a set whose sumset omits only finitely many integers must have integers with arbitrarily many representations as sums of two elements.
Asks for an explicit set whose sumset is all natural numbers while the number of representations of n grows slower than every power of n.
Asks whether the largest Sidon set in the first N integers has size the square root of N plus an error smaller than every power of N.
Asks whether every infinite set of natural numbers has a density-zero companion whose sumset with it omits only finitely many integers.
Asks how sparse a set can be if every large integer is a prime plus one of its members, measured against the square of the logarithm of N.
Asks how sparse a set can be if every large integer is a square plus one of its members, measured against the square root of N.
Asks whether every permutation of the first n integers has only o(n squared) distinct sums of consecutive terms; false, by Hegyvári's 1986 construction and Konieczny's explicit permutation with at least n squared over 4 distinct sums, the maximum lying between 0.286 and 0.446 times n squared.
Asks whether adding an additive basis of order k to a set of Schnirelmann density alpha raises the density by at least alpha times one minus alpha over k.
Asks for the largest constant c such that every split of the first 2N integers into two equal halves has a difference realized at least c times N ways.
Asks whether a lacunary set can be an essential component, that is, can strictly raise the Schnirelmann density of every set it is added to.
Asks whether a set that is not an additive basis can still always supply a shift raising the count of any set of Schnirelmann density strictly between 0 and 1 by a positive fraction depending on the density; proved in 2026.
Asks whether an infinite Sidon set can contain nearly the square root of N elements up to N, for every positive tolerance.
Asks which growth rates just below the square root of N force some integers to have arbitrarily many representations as sums of two elements.
Asks whether an infinite set with all triple sums distinct must have its counting function up to N infinitely often much smaller than the cube root of N.
Asks whether every Sidon set in the first N integers can be paired with a Sidon set of any fixed size whose difference set meets its own only at zero.
Asks whether two Sidon sets in the first N integers whose difference sets meet only at zero together have at most as many pairs as a largest Sidon set plus a constant, and a constant fraction fewer when equal in size.
Asks whether every Sidon set in the first N integers extends to a Sidon set in a longer interval that is nearly as large as the largest possible.
Asks whether for each k some integer has its nontrivial divisors so arranged that any k-coloring leaves a monochromatic set of reciprocals summing to one.
Asks whether every finite coloring of the integers admits a monochromatic set of distinct integers above one whose reciprocals sum to one.
Asks whether a subset of the first N integers whose reciprocal sum exceeds a fixed multiple of the logarithm of N has a subset of reciprocals summing to one.
Asks whether there are infinitely many pairs of integers for which Euler's totient of one equals the sum of the divisors of the other.
Asks whether a set of integers up to N on which Euler's totient function is strictly increasing has at most (1+o(1))π(N) elements, or even o(N); Erdős's exact conjecture, that the primes are a largest such set, is open.
Asks whether the density of integers whose totient is below a given fraction of the integer, as a function of that fraction, ever has a positive derivative.