Locality in sumsets

Motivated by the Polynomial Freiman-Ruzsa (PFR) Conjecture, we develop a theory of locality in sumsets, with several applications to John-type approximation and stability of sets with small doubling. One highlight shows that if A⊂Z with |A+A|≤(1−ϵ)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|≤Od,ϵ(|A|); thus we obtain one of the polynomial bounds required by PFR, under the non-degeneracy assumption that A is not efficiently covered by Od,ϵ(1) translates of a (d−1)-GAP. We also prove a stability result showing for any ϵ,α>0 that if A⊆Z with |A+A|≤(2−ϵ)2^d|A| is non-degenerate then some A^′⊂A with |A^′|>(1−α)|A| is efficiently covered by either a (d+1)-GAP or Oα(1) translates of a d -GAP. This ‘dimension-free’ bound for approximate covering makes for a surprising contrast with exact covering, where the required number of translates not only grows with d , but does so exponentially. Another highlight shows that if A⊂Z is non-degenerate with |A+A|≤(2^d+ℓ)|A| and ℓ≤0.1⋅2^d then A is covered by ℓ+1 translates of a d -GAP P with |P|≤Od(|A|); this is tight, in that ℓ+1 cannot be replaced by any smaller number. The above results also hold for A⊂R^d, replacing GAPs by a suitable common generalisation of GAPs and convex bodies, which we call generalised convex progressions. In this setting the non-degeneracy condition holds automatically, so we obtain essentially optimal bounds with no additional assumption on A . Here we show that if A⊂R^k satisfies |A+A2|≤(1+δ)|A| with δ∈(0,1), then ∃A^′⊂A with |A^′|≥(1−δ)|A| so that |co(A^′)|≤Ok,1−δ(|A|). This is a dimensionally independent sharp stability result for the Brunn-Minkowski inequality for equal sets, which hints towards a possible analogue for the Prékopa-Leindler inequality. 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. A further application that will be published separately is a proof of Ruzsa's Discrete Brunn-Minkowski Conjecture.