Finding a Low-dimensional Piece of a Set of Integers

Abstract

We show that a finite set of integers |$A \subseteq \mathbb{Z}$| with |$|A+A| \le K |A|$| contains a large piece |$X \subseteq A$| with Freĭman dimension |$O(\log K)$|⁠, where large means |$|A|/|X| \ll \exp(O(\log^2 K))$|⁠. This can be thought of as a major quantitative improvement on Freĭman’s dimension lemma; or as a “weak” Freĭman–Ruzsa theorem with almost polynomial bounds. The methods used, centred around an “additive energy increment strategy”, differ from the usual tools in this area and may have further potential. Most of our argument takes place over |$\mathbb{F}_2^n$|⁠, which is itself curious. There is a possibility that the above bounds could be improved, assuming sufficiently strong results in the spirit of the Polynomial Freĭman–Ruzsa Conjecture over finite fields.

Locations

• International Mathematics Research Notices - View
• arXiv (Cornell University) - View - PDF