TOPICS
Search

Erdős-Graham Subset Sum Problem

The Erdős-Graham subset sum problem asks for the asymptotic size of the largest subset of an interval of positive integers having no subset sum equal to a prescribed target. For c>0, let f_c(n) be the largest |A| for A subset= {1,...,|_cn_|} with n not a sum of distinct elements of A (Matijasevick 2026). Here |_x_| is the floor function.

For c>=1, the elementary exact formula is f_c(n)=|_cn_|-[n/2], where [x] is the ceiling function. Matijasevick (2026) proved that f_c(n)/n converges iff c>=1. For 0<c<1 its upper limit is c/2, also attained along odd n. At c=1/2 its complete set of limit points is {1/6,1/4}.

A more detailed classification uses the least positive integer q not dividing n, necessarily a prime power. If 0<c<1 and 2^(q-2)min(c,1-c)<=1, then along the integers with this value of q,

lim(f_c(n))/n=max(c/q,c-1/2+(1-c)/q).

The restriction on c and q is essential and does not provide an exact finite formula in the remaining cases.

See also

Subset Sum, Subset Sum Problem

Explore with Wolfram|Alpha

References

Matijasevick, M. "Forbidden Subset Sums in a Linear Range: An Inverse Theorem and the Erdős-Graham Irregularity Problem." 12 Nov 2026. https://arxiv.org/abs/2611.17205v1.

Cite this as:

Weisstein, Eric W. "Erdős-Graham Subset Sum Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Erdos-GrahamSubsetSumProblem.html

Subject classifications