Locality in Sumsets

MaRDI QIDQ6509486arXivFDO

Authors Peter van Hintum, Peter Keevash

Mathematics Subject Classification ID

Variational problems in a geometric measure-theoretic setting (49Q20) Approximation by convex sets (52A27) Inequalities and extremum problems involving convexity in convex geometry (52A40) Inverse problems of additive number theory, including sumsets (11P70)

Abstract: Motivated by the Polynomial Freiman-Ruzsa (PFR) Conjecture, we develop a theory of locality in sumsets, with applications to John-type approximation and sets with small doubling. First we show that if $AsubsetmathbbZ$ with $|A+A|le(1-epsilon)2^d|A|$ is non-degenerate then $A$ is covered by $O(2^d)$ translates of a $d$-dimensional generalised arithmetic progression ($d$-GAP) $P$ with $|P|le{O}_{d,epsilon}(|A|)$; thus we obtain one of the polynomial bounds required by PFR, under the non-degeneracy assumption that $A$ is not efficiently covered by $O_{d,epsilon}(1)$ translates of a $(d-1)$-GAP. We also prove a stability result showing for any $epsilon,alpha>0$ that if $AsubsetmathbbZ$ with $|A+A|le(2-epsilon)2^d|A|$ is non-degenerate then some $A^{\prime }subsetA$ with $|A^{\prime }|>(1-alpha)|A|$ is efficiently covered by either a $(d+1)$-GAP or $O_{alpha}(1)$ translates of a $d$-GAP. This `dimension-free' bound for approximate covering makes for a stark contrast with exact covering, where the required number of translates grows exponentially with $d$. We further show that if $AsubsetmathbbZ$ is non-degenerate with $|A+A|le(2^d+ell)|A|$ and $ellle0.1cdot{2}^d$ then $A$ is covered by $ell+1$ translates of a $d$-GAP $P$ with $|P|le{O}_d(|A|)$; this is tight, in that $ell+1$ cannot be replaced by any smaller number. The above results also hold for $Asubsetmathbb{R}^d$, replacing GAPs by a suitable common generalisation of GAPs and convex bodies. In this setting the non-degeneracy condition holds automatically, so we obtain essentially optimal bounds with no additional assumption on $A$. These results are all deduced from a unifying theory, in which we introduce a new intrinsic structural approximation of any set, which we call the `additive hull', and develop its theory via a refinement of Freiman's theorem with additional separation properties.

This page was built for publication: Locality in Sumsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6509486)