Dense sets without large sumsets

Gabriel Dahia; JoÃ£o Pedro Marciano; João Pedro Marciano; Victor Souza

combinatorics

Dense sets without large sumsets

arXiv:2607.15269

summary

The authors prove that for any fixed density δ, a random δ‑dense subset of {1,…,n} (for sufficiently large n) almost surely avoids containing the sumset A+B of any two subsets A and B whose sizes are at least about (3 log n / log (1/δ)), establishing sharp bounds and settling a recent conjecture.

Abstract

We prove, for all fixed $0 < δ < 1$ , and all sufficiently large $n$ , that there exists $S \subset [n]$ with $∣ S ∣ \geq δ n$ such that $A + B \neq \subset S$ for all $A, B \subset N$ satisfying $min {∣ A ∣, ∣ B ∣} \geq (3 + o (1)) \frac{lo g n}{lo g ( 1/ δ )} .$ A very recent result of Hernández and Hetzel shows that our bound is sharp up to a factor of 3, and together our results settle a conjecture of Kra, Moreira, Richter, and Robertson. In fact, we prove that a $δ$ -dense random subset of $[n]$ is a valid choice for $S$ with high probability, and that one can take $n^{- α} \leq δ \leq 1 - c$ where $c > 0$ is fixed and $α > 0$ depends only on the $o (1)$ error, answering another question of the same authors in a strong form.

Minor adjustments for journal submission

Topics & keywords

#additive combinatorics #sumsets #dense subsets #random subsets #extremal combinatoricssumsetδ‑dense setrandom subsetasymptotic boundcombinatorial number theory