TOPICS
Search

Sum-Free Set


A sum-free set S is a subset of an additive group for which the intersection of S and the sumset S+S is empty. The two summands in S+S need not be distinct.

For example, the sum-free sets of {1,2,3} are ⌀, {1}, {2}, {3}, {1,3}, and {2,3}. The numbers of sum-free subsets of {1,2,...,n} for n=0, 1, ... are 1, 2, 3, 6, 9, 16, 24, 42, 61, ... (OEIS A007865).

The numbers of sum-free sets can be computed in the Wolfram Language using the following code (P. Abbott, pers. comm., Nov. 24, 2005):

NumbersOfSumFreeSets[nmax_] := Module[{n = 0},
    Last[Reap[Nest[(++n; Sow[Length[#]];
      Union[#, Union[#, {n}]& /@
        Select[#, Intersection[#, n - #] == {}&]])&,
          {{}}, nmax + 1]
      ]
    ]
  ]

The Cameron-Erdős conjecture determines the order of growth of the number of sum-free subsets of {1,...,n}.

A different extremal question asks for the largest sum-free subset guaranteed inside every N-element set of positive integers. If this guaranteed size is S(N), then Bedert (2025) proved, for an absolute constant c>0,

 S(N)>=N/3+clnlnN

for all sufficiently large N. This settles the question whether the improvement over N/3 tends to infinity. Eberhard et al. (2014) proved the complementary leading-order upper bound S(N)=N/3+o(N). The precise order of the excess remains open.

Bedert (2025) also proved a structural theorem. Let N be positive and A be an N-element set of nonzero integers whose largest sum-free subset has size at most N/3+C. Then A has an F_4-Freiman isomorphism into an interval [-N^(C^(O(1))),N^(C^(O(1)))]. This stronger signed-relation convention preserves a+b=c. For every K>1, A can also be partitioned into pieces A_j of size at least (CK)^(-O(1))N and an exceptional set of size O((CK)^(-10)N). Each A_j has |A_j-A_j|<=(CK)^(O(1))|A_j| and lies in a generalized arithmetic progression of rank (CK)^(O(1)) and size at most exp((CK)^(O(1)))|A_j|. Moreover every subset X subset= A satisfies E(X)>>C^(-O(1))|X|^4/N, where E(X) is its additive energy (Bedert 2025).

These results allow equal summands in a forbidden equation a+b=c. Requiring no element to be the sum of two or more distinct other elements is a different condition. For example, {1,2} satisfies the distinct-other-summands condition but is not sum-free because 1+1=2. Conversely, {3,4,5,12} is sum-free but contains 3+4+5=12.

For the distinct-other-summands convention, let l(N) be the largest size guaranteed in every N-element set of integers. Choi et al. (1975) proved

 sqrt((NlnN)/(lnlnN))<<l(N)<<N/(lnN).

In particular, l(N)/sqrt(N)->infty, but the precise order of growth of l(N) remains open (Bloom 2026).


See also

A-Sequence, Cameron's Sum-Free Set Constant, Double-Free Set, Hofstadter Sequences, Prime Number of Measurement, s-Additive Sequence, Schur Number, Schur's Problem, Stöhr Sequence, Triple-Free Set

Explore with Wolfram|Alpha

References

Abbott, H. L. and Moser, L. "Sum-Free Sets of Integers." Acta Arith. 11, 393-396, 1966. https://doi.org/10.4064/aa-11-4-393-396.Bedert, B. "Large Sum-Free Subsets of Sets of Integers via L^1-Estimates for Trigonometric Series." 12 Feb 2025. https://arxiv.org/abs/2502.08624.Bloom, T. F. "Erdős Problem 790." Erdős Problems. Accessed Nov. 20, 2026. https://www.erdosproblems.com/790.Cameron, P. J. and Erdős, P. "On the Number of Sets of Integers with Various Properties." In Number Theory. Proceedings of the First Conference of the Canadian Number Theory Association Held in Banff, Alberta, April 17-27, 1988 (Ed. R. A. Mollin). Berlin, Germany: de Gruyter, pp. 61-79, 1990.Cameron, P. J. and Erdős, P. "Notes on Sum-Free and Related Sets." Combin. Probab. Comput. 8, 95-107, 1999.Choi, S. L. G.; Komlós, J.; and Szemerédi, E. "On Sum-Free Subsequences." Trans. Amer. Math. Soc. 212, 307-313, 1975. https://doi.org/10.1090/S0002-9947-1975-0376594-1.Eberhard, S.; Green, B.; and Manners, F. "Sets of Integers with No Large Sum-Free Subset." Ann. Math. 180, 621-652, 2014. https://doi.org/10.4007/annals.2014.180.2.5.Exoo, G. "A Lower Bound for Schur Numbers and Multicolor Ramsey Numbers of K_3." Elec. J. Combin. 1, R8, 1994. https://doi.org/10.37236/1188.Finch, S. R. "Cameron's Sum-Free Set Constants." §2.25 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 180-183, 2003.Fredricksen, H. and Sweet, M. M. "Symmetric Sum-Free Partitions and Lower Bounds for Schur Numbers." Elec. J. Combin. 7, R32, 2000. https://doi.org/10.37236/1510.Green, B. "The Cameron-Erdős Conjecture." Bull. London Math. Soc. 36, 769-778, 2004. https://doi.org/10.1112/S0024609304003650.Sloane, N. J. A. Sequence A007865 in "The On-Line Encyclopedia of Integer Sequences."Wallis, W. D.; Street, A. P.; and Wallis, J. S. Combinatorics: Room Squares, Sum-Free Sets, Hadamard Matrices. New York: Springer-Verlag, 1972.Wang, E. T. H. "On Double-Free Sets of Integers." Ars Combin. 28, 97-100, 1989.

Referenced on Wolfram|Alpha

Sum-Free Set

Cite this as:

Weisstein, Eric W. "Sum-Free Set." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Sum-FreeSet.html

Subject classifications