2023/04/03 by Peter van Hintum, Peter Keevash, van Hintum, Peter +1 · 1 citation
Computer Science · Mathematics · #11P70 #49Q20 #52A27 #52A40 #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Approximation and Integration #Metric Geometry (math.MG) #Number Theory (math.NT)
paper · pdf · doi:10.48550/arxiv.2304.01189
openalex publication_date 2023/04/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 A ⊂ ℤ with |A+A| ≤ (1-ε) 2d |A| is non-degenerate then A is covered by O(2d) 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 ⊂ ℤ with |A+A| ≤ (2-ε)2d|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 stark contrast with exact covering, where the required number of translates grows exponentially with d. We further show that if A ⊂ ℤ is non-degenerate with |A+A| ≤ (2d + ℓ)|A| and ℓ ≤ 0.1 ⋅ 2d 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 ⊂ ℝ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.