On the largest sum-free subset of the lattice cube

1. Problem Statement

The paper addresses the problem of determining the asymptotic density of the largest sum-free subset within a $d$-dimensional lattice cube.

• Definitions: A subset $S$ of an abelian group is sum-free if there are no $x, y, z \in S$ such that $x + y = z$. The authors study subsets of the lattice cube $[n+1]^d = \{0, 1, \dots, n\}^d$.
• Objective: Determine the limit $c_d = \lim_{n \to \infty} \frac{|S|}{n^d}$, where $S$ is the largest sum-free subset.
• Context:
  • For $d=1$, it is well-known that $c_1 = 1/2$.
  • For $d=2$, Elsholtz and Rackham proved $c_2 = 3/5$.
  • For $d=3, 4$, Lepsveridze and Sun recently resolved the cases.
  • The Conjecture: It was conjectured that for all $d$, the optimal set is a "slice" of the cube defined by a hyperplane. Specifically, the set $S^* = \{x \in [n+1]^d \mid u \le \sum x_i < 2u\}$, where $u$ is chosen to maximize the volume of the slice, yields the maximum density.
  • Let $c^*_d$ be the maximum volume of such a slice in the continuous limit $[0,1]^d$. The conjecture states $c_d = c^*_d$.

2. Methodology

The proof follows the approach established by Lepsveridze and Sun, utilizing a combination of linear programming duality and probabilistic coupling (joint mixability).

A. Reduction to Linear Programming

The problem of bounding $|S|$ is reformulated as a linear program (LP).

• Primal Problem: Maximize $\sum |S(x)|$ (where $S(x)$ are fibers of the set $S$) subject to the constraint that for any $x, y, z$ with $x+y=z$, $|S(x)| + |S(y)| + |S(z)| \le 2(n+1)$.
• Dual Problem: To find an upper bound, one must construct a feasible solution (weights) for the dual LP. The existence of such weights relies on the ability to couple specific probability distributions.

B. Joint Mixability

The core technical innovation is the proof of a Joint Mixability result.

• Definition: Distributions $\mu_1, \mu_2, \mu_3$ are jointly mixable if there exists a coupling $(X_1, X_2, X_3)$ with these marginals such that $X_1 + X_2 + X_3 = \mathbb{E}[X_1] + \mathbb{E}[X_2] + \mathbb{E}[X_3]$ almost surely.
• The Key Theorem (Theorem 1.5): The authors prove that for any non-negative integers $r, s, t$ such that $r+s+t = dn$, the uniform distributions on the discrete slices $L_d(r), L_d(s), L_d(t)$ (where $L_d(k) = \{x \in [n+1]^d : \sum x_i = k\}$) are jointly mixable.
• Proof Technique:
  • Induction on $d$: The base case $d=2$ relies on known results regarding intervals and triangle inequalities.
  • Inductive Step ($d \ge 3$): The authors construct a coupling for the first coordinates using a fixed-point argument (Brouwer's Fixed Point Theorem or Perron-Frobenius). They define a map on the space of probability distributions over the support of the first coordinates and show a fixed point exists. This fixed point ensures the marginals match the required uniform distributions on the slices, allowing the induction hypothesis to be applied to the remaining $d-1$ coordinates.

C. Weight Construction and Slice Estimates

To apply the joint mixability to the dual LP:

1. Partitioning: The domain $[n+1]^{d-1}$ is partitioned into five sets ($A, B, C, D, E$) based on the sum of coordinates relative to the optimal slice parameter $u^*_d$.
2. Weight Function: Using the joint mixability result, the authors construct a weight function $w(x,y,z)$ supported on specific triples of these sets.
3. Analytic Estimates: They utilize log-concavity properties of the probability density function of the sum of uniform random variables (Irwin-Hall distribution). They derive explicit bounds on the ratios of slice volumes (Lemma 3.1) to ensure the constructed weights satisfy the dual constraints.
   • For large $d$, they use large deviation estimates.
   • For small $d$ ($5 \le d < 200$), they verify the inequalities numerically.

3. Key Contributions

1. Resolution of the Conjecture for All $d$: The paper proves that $c_d = c^*_d$ for all dimensions $d \ge 1$. This confirms that the optimal sum-free subset is indeed the slice defined by the hyperplane $\sum x_i \in [u^*_d n, 2u^*_d n)$.
2. General Joint Mixability Theorem: The proof of Theorem 1.5 is a significant contribution to probability theory and combinatorics. It establishes that uniform distributions on discrete slices of a hypercube summing to a constant are jointly mixable, a result that generalizes previous findings for specific low dimensions.
3. Refinement of the Lepsveridze-Sun Approach: The authors generalize the method used for $d=3,4$ to arbitrary dimensions, overcoming the complexity of constructing couplings in higher dimensions through a rigorous inductive fixed-point argument.

4. Main Results

• Theorem 1.1: For any $d \ge 1$ and any sum-free subset $S \subseteq [n+1]^d$, the size is bounded by:
  $$|S| \le c^*_d n^d + O(n^{d-1})$$
  where $c^*_d$ is the maximum volume of the slice $S_d(u) = \{x \in [0,1]^d : u \le \sum x_i < 2u\}$.
• Corollary: The limiting density is exactly the volume of the optimal slice, resolving the natural conjecture posed by Cameron, Green, and others.

5. Significance and Extensions

• Combinatorial Number Theory: This result settles a long-standing open problem regarding the structure of sum-free sets in high-dimensional lattices. It confirms that the "slice" construction is universally optimal, not just for low dimensions.
• Probabilistic Methods: The paper demonstrates the power of joint mixability and coupling techniques in solving extremal combinatorial problems. The inductive construction of couplings via fixed-point theorems is a novel and robust technique.
• General Convex Sets: The authors briefly discuss whether this "slice" optimality holds for general convex sets. They provide a counterexample (Proposition 5.1) showing that for sufficiently large $d$, there exist convex sets where the largest sum-free subset is not a single slice defined by a linear functional. This highlights that the hypercube's symmetry is crucial for the slice optimality.
• Open Problem: The paper leaves open the question of whether the slice optimality holds for all bounded convex sets in dimension $d=2$.

In summary, this paper provides a complete solution to the asymptotic density of the largest sum-free subset in a lattice cube, unifying previous partial results and introducing powerful probabilistic tools to handle arbitrary dimensions.