A refinement of the Cameron-Erdős Conjecture

Noga Alon, József Balogh, Robert Morris, Wojciech SamotijarXiv 2012 · DOI · arXiv

TL;DR

This paper provides a "sparse" refinement of the Cameron-Erdős Conjecture by counting the number of sum-free subsets of $\{1, \dots, n\}$ of a specific size $m$. The authors prove that there are at most $2^{O(n/m)} \binom{\lceil n/2 \rceil}{m}$ such subsets, a result that is sharp for $m \ge \sqrt{n}$ and provides a detailed structural description of what these "typical" sum-free sets look like.

What Problem Does This Paper Address?

In additive combinatorics, a set is called sum-free if no two elements (not necessarily distinct) sum to a third element in the set (i.e., the equation $x + y = z$ has no solutions).

For the set of integers $[n] = \{1, \dots, n\}$, there are two obvious large sum-free subsets:

  1. The set of all odd numbers.
  2. The "top half" of the interval: $\{\lfloor n/2 \rfloor + 1, \dots, n\}$.

Both have roughly $n/2$ elements, meaning there are at least $2^{n/2}$ sum-free subsets. In 1990, Cameron and Erdős conjectured that the total number of sum-free subsets is actually $O(2^{n/2})$. While this was proven in the early 2000s, this paper tackles the more granular question: How many sum-free subsets exist of a specific size $m$? This is essentially the "sparse" version of the original problem, moving from counting all subsets to counting subsets of a fixed density.

Methods

The proof is a tour de force of modern combinatorial techniques, combining structural graph theory with probabilistic methods:

  • Hypergraph Independent Sets: The authors treat the problem as finding independent sets in a 3-uniform hypergraph where the edges represent "Schur triples" (triples $(x, y, z)$ such that $x + y = z$). They utilize a powerful general bound for independent sets in hypergraphs previously developed by the same authors.
  • Stability Results: They build upon "stability" theorems (specifically by Ben Green), which state that if a set is almost sum-free and large, it must structurally resemble one of the two extremal examples (odds or the top half).
  • Integer Partitions with Small Sumsets: A significant portion of the paper develops new bounds for counting integer partitions where the resulting set has a "small sumset" ($S+S$). This involves using Freiman’s $3k-4$ Theorem, a cornerstone of additive number theory.
  • Probabilistic Inequalities: The authors use Janson’s inequality and the FKG inequality to bound the number of sum-free sets that contain very few even numbers or very few small numbers.

Datasets

Not discussed in the paper. As a theoretical mathematics paper, it relies on formal proofs and logical derivation rather than empirical datasets.

Key Insights and Ideas

  • The "Typical" Structure: The paper proves that for sufficiently large $m$, almost every sum-free $m$-subset is either composed almost entirely of odd numbers or is almost entirely contained in the upper half of the range $[n/2, n]$.
  • Sharpness at $\sqrt{n}$: The bound $2^{O(n/m)} \binom{n/2}{m}$ is particularly interesting because it becomes sharp once $m$ exceeds $\sqrt{n}$. Below this threshold, the problem becomes more trivial as the number of triples is too small to significantly constrain the number of subsets.
  • The Partition Connection: The authors show that counting sum-free sets is deeply linked to the problem of counting sets with small sumsets. This connection allows them to use tools from Freiman theory to handle the "hard" cases where the set is mostly in the top half of the interval.

Key Results

  • Theorem 1.1 (The Main Bound): For every $1 \le m \le \lceil n/2 \rceil$, the number of sum-free subsets of $[n]$ of size $m$ is at most $2^{O(n/m)} \binom{\lceil n/2 \rceil}{m}$.
  • Theorem 1.2 (Structural Characterization): For $m \ge C\sqrt{n \log n}$, a typical sum-free $m$-subset $I$ either consists only of odd numbers ($I \subset O_n$) or satisfies specific constraints on its "small" elements (those $\le n/2$). Specifically, the number of small elements and their sum are tightly bounded.
  • Refinement of Cameron-Erdős: Because there are fewer than $2^{n/3}$ subsets with fewer than $n/100$ elements, this new result easily implies the original Cameron-Erdős conjecture while providing much more detail for smaller $m$.

Limitations and Future Work

  • The Constant Factor: While the result is sharp up to the constant $C$ in the exponent $O(n/m)$, the exact value of that constant is not determined.
  • Conjecture 1.5: The authors propose a stronger conjecture regarding the number of sets with small sumsets ($|S+S| \le N$). They suggest that their bound could be improved by a factor of $(3/2)^m$, which would bring it closer to being truly optimal.
  • Threshold for $m$: The structural description (Theorem 1.2) requires $m \ge C\sqrt{n \log n}$. Exploring the behavior of "typical" sets for $m$ between $\sqrt{n}$ and $\sqrt{n \log n}$ remains an open area.

Summary updated

Abstract

In this paper we study sum-free subsets of the set $\{1,...,n\}$, that is, subsets of the first $n$ positive integers which contain no solution to the equation $x + y = z$. Cameron and Erdős conjectured in 1990 that the number of such sets is $O(2^{n/2})$. This conjecture was confirmed by Green and, independently, by Sapozhenko. Here we prove a refined version of their theorem, by showing that the number of sum-free subsets of $[n]$ of size $m$ is $2^{O(n/m)} {\lceil n/2 \rceil \choose m}$, for every $1 \le m \le \lceil n/2 \rceil$. For $m \ge \sqrt{n}$, this result is sharp up to the constant implicit in the $O(\cdot)$. Our proof uses a general bound on the number of independent sets of size $m$ in 3-uniform hypergraphs, proved recently by the authors, and new bounds on the number of integer partitions with small sumset.
BibTeX
@misc{alon2012refinement,
  author = {Noga Alon and József Balogh and Robert Morris and Wojciech Samotij},
  title = {{A refinement of the Cameron-Erdős Conjecture}},
  year = {2012},
  eprint = {1202.5200},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1202.5200},
}
Figure