Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
606 of 1,221 problems match
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Asks whether a set of n integers up to N whose subset sums are all distinct forces N to be at least a constant times 2 to the power n.
Asks whether finite distinct covering systems can have arbitrarily large minimum modulus; Hough proved an absolute bound.
Asks whether every set of natural numbers whose reciprocals sum to infinity must contain arbitrarily long arithmetic progressions.
Asks whether prime gaps exceed any given constant times log n times a slowly growing factor built from repeated logarithms infinitely often.
Asks whether there are infinitely many n for which three consecutive prime gaps are strictly increasing.
Asks whether every finite coloring of the integers admits a covering system whose moduli all receive the same color.
Asks whether a subset of the first N integers with no element dividing the sum of two larger elements has size at most N over 3 plus a constant; proved by Bedert in 2023, with the ceiling of N over 3 exact for large N.
Asks whether the integers up to N lacking a unique representation as a sum of two elements of a set must number nearly the square root of N; yes, and never little-o of it, by two Lean proofs the bounty site Conjectures.io accepted.
Asks whether the odd integers not of the form a power of 2 plus a prime form the union of an infinite arithmetic progression and a set of density zero.
Asks whether the smallest intersecting family of n-element sets in which every set of size at most n minus 1 misses a member has size linear in n.
Asks whether some graph on n vertices has at least n squared over 8 edges, no complete subgraph on 4 vertices, and no large independent set.
Asks whether every triangle-free graph on 5n vertices contains at most n to the fifth power many 5-cycles.
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 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 every infinite set of natural numbers has a density-zero companion whose sumset with it omits only finitely many integers.
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 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 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 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.