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 a minimal basis of order two exists whose kth smallest element divided by k squared tends to a nonzero constant; Erdős first asked it for any basis of order two, which Cassels answered yes.
Asks how large a subset of the first N integers can be if the sum of any two distinct members never divides their product, or never divides twice it.
Asks whether a set in which each n is a sum of two distinct elements at most C times splits into boundedly many parts with fewer than C each; the site's count of ordered pairs makes C = 2 trivial. Nešetřil and Rödl answer no.
The largest possible value of the limiting ratio of the counting function of an infinite Sidon set to the square root of N.
Asks whether a minimal basis of positive density exists in which, for each of its elements, the integers needing that element have positive upper density.
Asks whether two sets of integers, each with counting function at least a constant times the square root of N, must share infinitely many equal nonzero differences.
Determines which conditions on a set of integers force the differences that occur infinitely often to have bounded gaps.
Asks whether every set of integers of density zero lies in the sumset of some set whose counting function is smaller than the square root of N.
The best function f for which every n is a sum of two integers having no prime factor larger than f of n; Erdős asked whether n^epsilon suffices, still open, and whether even n^(1/3) does, which Balog's bound answers yes.
Characterizes the pairs of positive-density sets of integers whose sumset has density exactly the sum of their densities.
Determines the limit of h of r divided by r squared, where h of r is the largest finite exact order of an additive basis of order r.
Asks whether every additive basis of density zero has its sumset counting function grow infinitely faster than its own counting function.
Characterizes when a basis has a restricted order, using distinct summands only, and whether that order is bounded in terms of the ordinary order.
Asks whether the integers that are sums of exactly r distinct elements of a basis of order r must have positive lower density.
The growth rate of the greedy Sidon sequence, and whether its counting function is at least N to the power one half minus any epsilon.
Asks whether the sequence extending a finite set by the least integer that is not a sum of two earlier terms has eventually periodic differences.
Asks what can be said about the sequence whose terms are the least integers uniquely expressible as a sum of two earlier terms, its density and its gaps.
Asks, after Folkman, whether a multiset of integers with linear counting function must have subset sums containing an infinite arithmetic progression, in the form Szemerédi and Vu prove, with one absolute constant; Folkman's question for every constant is open.
Asks whether every set of integers with at least a sufficiently large constant times the square root of N elements up to N, for every N, has subset sums containing an infinite arithmetic progression.
Asks whether infinitely many k make the completeness threshold of the kth powers larger than that of the next powers.
Asks whether a sequence complete after any finite deletion but never after an infinite one, with ratios bounded away from one, must have ratios tending to the golden ratio.
Asks whether some integer sequence with successive ratios tending to two has subset sums of density one even after any finite set of terms is removed.
Determines for which m less than n a complete sequence can stay complete after removing any m elements yet fail after removing any n elements.
Determines for which positive t and alpha the integer parts of t times alpha to the n form a complete sequence, distinct terms summing to all large integers.
Asks whether a finite set of integers with all subset sums distinct must have its reciprocals summing to less than two.