Sumsets and Arithmetic Progressions

../

E0001/: 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.

E0003/: Asks whether every set of natural numbers whose reciprocals sum to infinity must contain arbitrarily long arithmetic progressions.

E0036/: 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.

E0037/: 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.

E0052/: Asks whether the larger of the sumset and product set of a finite set of integers always has size at least the set's size squared, up to a small power loss.

E0053/: Asks whether, for every k, a large enough finite set of integers gives at least its size to the power k integers that are sums or products of distinct elements.

E0109/: Shows that any set of natural numbers with positive upper density contains the sumset of two infinite sets.

E0138/: Improves bounds on the van der Waerden number, the least N forcing a monochromatic k-term progression in any two-coloring, and whether its k-th root grows.

E0139/: Asks whether the largest subset of the first N integers with no non-trivial k-term arithmetic progression has size a vanishing proportion of N.

E0140/: Asks whether the largest subset of the first N integers with no three-term arithmetic progression is smaller than N over any fixed power of the logarithm of N.

E0141/: Asks whether, for every k at least three, there are k consecutive primes forming an arithmetic progression.

E0142/: Asks for an asymptotic formula for the largest subset of the first N integers containing no non-trivial k-term arithmetic progression.

E0160/: Estimates the least number of colors needed for the first N integers so that every four-term arithmetic progression receives at least three distinct colors.

E0168/: The limiting density of the largest subset of the first N integers containing no triple of the form n, twice n, three times n, and whether it is irrational.

E0169/: Estimates the largest possible sum of reciprocals of a set of integers with no arithmetic progression of k terms, and compares it to van der Waerden numbers.

E0170/: The limiting value, divided by the square root of N, of the smallest subset of zero through N whose difference set covers every integer up to N.

E0171/: Asks whether every subset of a fixed positive density of a large grid of words must contain a combinatorial line.

E0179/: Bounds how many k-term arithmetic progressions a set of N integers can have before it must contain a longer progression of a given length.

E0185/: Asks whether the largest subset of the ternary cube of dimension n with no three points on a line has size a vanishing fraction of three to the n.

E0186/: The order of growth of the largest subset of the first N integers in which no element is the average of two or more other elements.

E0190/: Asks whether the least N forcing a monochromatic or a rainbow k-term arithmetic progression in every coloring of [N] has k-th root growing faster than k; proved by Bae and by Fox and Hunter in 2026 preprints.

E0192/: Determines in which dimensions an infinite walk taking positive unit-vector steps must contain a three-term arithmetic progression.

E0194/: Asks whether every ordering of the real numbers contains an increasing or decreasing arithmetic progression of k terms, for k at least 3.

E0195/: The largest number of terms k such that every permutation of the integers contains a monotone arithmetic progression of k terms.

E0196/: Asks whether every permutation of the positive integers contains a monotone arithmetic progression of four terms; a Lean-checked construction certified by the bounty site Conjectures.io in September 2026 gives one with none.

E0197/: Asks whether the positive integers split into two sets, each of which can be permuted to avoid monotone three-term arithmetic progressions.

E0198/: Asks whether the complement of a set of integers with all pairwise sums distinct must contain an infinite arithmetic progression.

E0199/: Asks whether the complement of a set of reals with no three-term arithmetic progression must contain an infinite arithmetic progression.

E0200/: Asks whether the longest arithmetic progression of primes below N has length a vanishing fraction of the logarithm of N.

E0201/: Determines how large a subset free of k-term arithmetic progressions can be guaranteed inside any N integers, and how that compares with the case of one to N.

E0219/: Asks whether the primes contain arithmetic progressions of every finite length.

E0245/: Asks whether a sparse infinite set of naturals must have its sumset, counted up to N, at least three times as large as the set, up to o(1), along a sequence of N.

E0271/: Determines explicitly, and bounds the growth of, the greedy sequence starting at 0 and n that avoids any three-term arithmetic progression.

E0272/: The largest number of subsets of {1,...,N} with every pairwise intersection a non-empty arithmetic progression; open for the exact value, while Szabó's linear-error question, N^2/2 + O(N), has a Lean proof Conjectures.io accepted.

E0328/: 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.

E0331/: 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.

E0335/: Characterizes the pairs of positive-density sets of integers whose sumset has density exactly the sum of their densities.

E0350/: Asks whether a finite set of integers with all subset sums distinct must have its reciprocals summing to less than two.

E0475/: Whether every finite set of nonzero residues modulo a prime can be ordered with all partial sums distinct (Graham's rearrangement conjecture); proved for all large primes by four range results with no explicit threshold.

E0476/: Asks whether the set of sums of distinct pairs from a subset of the integers modulo a prime has size at least twice the subset size minus three, or the prime (the Erdős–Heilbronn conjecture); proved in 1994.

E0494/: Asks whether, for k greater than two, the multiset of all sums of k distinct elements of a finite set of complex numbers determines the set, given its size.

E0656/: Asks whether every set of positive upper density contains, after some shift, all pairwise sums of distinct members of an infinite subset.

E0658/: Asks whether every subset of the N by N grid of positive density contains the four vertices of a square, once N is large enough.

E0741/: Asks whether every set of naturals whose sumset has positive upper density splits into two parts whose sumsets both do, and whether some basis of order two has no split in which both self-sumsets have bounded gaps.

E0749/: Asks whether a set of naturals can have a sumset of lower density near one while every integer has boundedly many representations as a sum of two elements.

E0763/: Asks whether a set of naturals can have its count of representations as a sum of two elements, summed up to N, equal to cN plus O(1) for a constant c > 0.

E0764/: Asks whether a set of naturals can have its count of representations as a sum of three elements, summed up to N, equal to cN plus O(1) for a constant c > 0.

E0781/: Estimates the least n such that every two-coloring of one to n has a monochromatic k-term descending wave, and whether it is k squared minus k plus one.

E0785/: Asks whether two infinite sets whose sumset covers all large integers and whose counting functions multiply to about x must have that product exceed x by an amount tending to infinity.

E0787/: The largest subset guaranteed inside any n real numbers with no two distinct elements summing to a member of the set; the Erdős–Moser function, between a power of log n above the first and exp(O(sqrt(log n))).

E0788/: The least total size of a set B in (2n, 4n) plus a largest C in (n, 2n) whose distinct pairs never sum into B; Choi's interval function, between n^(1/2) and n^(3/5+o(1)), with an unreviewed 2026 claim of the conjectured n^(1/2+o(1)).

E0789/: The largest subset guaranteed inside any n integers in which equal sums of elements can only occur between equally many terms.

E0790/: The largest subset guaranteed inside any n integers in which no element equals the sum of two or more other distinct elements of the subset; known to lie between the square root of n log n over log log n and n over log n.

E0791/: Estimates the fewest elements of zero to n whose pairwise sums cover zero to n (the smallest finite additive 2-basis); its square lies between 2.181 n and 3.458 n, and the guess 2 sqrt(n) is refuted (Hämmerer-Hofmeister, Mrose).

E0792/: Estimates the largest sum-free subset, having no solution to a plus b equals c, guaranteed inside any set of n integers; the main term n/3 is settled and the second-order term lies between c log log n and o(n).

E0806/: Asks whether every set of at most sqrt(n) integers up to n lies in B + B for some B of size o(sqrt(n)); proved by Alon, Bukh and Sudakov with a basis of order sqrt(n) log log n / log n, the sharp order.

E0808/: Asks whether, for a graph on a set of n integers with many edges, the sums or the products along its edges must number nearly as many as the edge count.

E0817/: Estimates the least N for which some n-element set of integers up to N has all subset sums free of k-term progressions, and asks whether the k = 3 case grows like 3^n; open, with a 2026 preprint claiming a negative answer.

E0818/: Asks whether a finite set of integers with small sumset must have product set nearly the square of its size, up to a power of a logarithm.

E0819/: Estimates the largest possible size of the sumset within the integers up to N of a subset of them having about root N elements; open, with Erdős and Freud's 1991 bounds 3/8 and 1/2 and an unreviewed 2026 note claiming 0.469.

E0847/: Asks what follows for an infinite set of naturals in which every n of its members contain a fixed proportion forming no three-term arithmetic progression.

E0865/: Asks whether every set of integers up to N of size just above five eighths of N contains three members whose three pairwise sums also lie in the set; proved in a 2026 preprint, developed with GPT-5.5 Pro, that the site accepted.

E0866/: Estimates, for k at least three, how far above N a subset of the integers up to 2N must be to force k integers whose pairwise sums all lie in the set; open, with the thresholds 1 and 3 for k = 3 and 4 and bounded for k = 5.

E0867/: Asks whether a set of integers up to N in which no sum of consecutive members lies in the set has size at most half of N plus a constant; false, by Freud's 1993 construction of density 19/36.

E0874/: Estimates the largest set of integers up to N whose sets of sums of r distinct members are disjoint for distinct r, and whether it nears two root N.

E0875/: Determines how slowly an infinite set of naturals can grow while its sets of sums of r distinct members stay disjoint for different r.

E0876/: Determines how small the gaps of an infinite sum-free set of naturals can be, and whether the nth gap can stay below n.

E0877/: Estimates the number of maximal sum-free subsets of the integers up to n and whether it is o(2^(n/2)); yes, and the count is a residue-dependent constant times two to the power of n over 4.

E0895/: Asks whether every large triangle-free graph on one to n contains three pairwise nonadjacent numbers of the form a, b and a plus b.

E0899/: Asks whether every infinite set of density zero has difference set counts that are infinitely often arbitrarily larger than its own counting function.

E0984/: Asks whether the naturals can be two-colored so that every monochromatic arithmetic progression starting at a has fewer terms than any fixed power of a.

E1097/: Determines how many values can arise as the common difference of a three-term arithmetic progression inside a set of n integers.

E1112/: Asks whether, for given gap bounds and k at least 3, every sufficiently lacunary sequence misses the k-fold sumset of some sequence with those gaps.

E1179/: Estimates the least size of a random subset of an abelian group of order N whose subset sums hit every group element nearly equally often.

E1185/: Asks whether a dense set of integers has a k-term arithmetic progression whose common difference is a difference of two members of any large enough set.

E1186/: Estimates the least density of monochromatic k-term arithmetic progressions forced in every two-coloring of the first n integers.

E1187/: Asks whether every coloring of the integers with finitely many colors contains k primes in arithmetic progression all of the same color.

E1193/: Asks whether, for a set A of natural numbers and a positive non-decreasing g, the set of n at which the number of representations of n as a sum of two elements of A equals g(n) always has lower density 0, and upper density below some c < 1.

E1213/: Asks whether, for every starting value a and gap bound K, any long enough integer sequence starting at a with gaps at most K has two intervals with equal sums; yes by Hegyvári's 1986 Theorem 3, with an explicit bound.

---

Sumsets and difference sets, densities and sum-free sets, arithmetic progressions in dense sets of integers together with the coloring problems that force them (van der Waerden numbers), difference bases and perfect rulers, and sets with distinct subset sums.

Site tags routed here: additive combinatorics, analysis, arithmetic progressions, combinatorics, graph theory, number theory, primes, probability, sidon sets.