On Sets with Small Doubling Property

I. D. Shkredov

Matematičeskie zametki, Tome 84 (2008) no. 6, pp. 927-947.

Résumé

Suppose that $G$ is an arbitrary Abelian group and $A$ is any finite subset $G$. A set $A$ is called a set with small sumset if, for some number $K$, we have $|A+A|\le K|A|$. The structural properties of such sets were studied in the papers of Freiman, Bilu, Ruzsa, Chang, Green, and Tao. In the present paper, we prove that, under certain constraints on $K$, for any set with small sumset, there exists a set $\Lambda$, $\Lambda\ll_{\varepsilon}K\log|A|$, such that $|A\cap \Lambda|\gg |A|/K^{1/2+\varepsilon}$, where $\varepsilon>0$. In contrast to the results of the previous authors, our theorem is nontrivial even for a sufficiently large $K$. For example, for $K$ we can take $|A|^\eta$, where $\eta>0$. The method of proof used by us is quite elementary.

Détail

Keywords: Abelian group, sumset (Minkowski sum), set with small doubling property, arithmetic progression, connected set, dissociate set, Cauchy–Bunyakovskii inequality.

Bibliographie

[1] G. A. Freiman, Osnovaniya strukturnoi teorii slozheniya mnozhestv, Kazansk. gos. ped. in-t, Kazan, 1966 | MR | Zbl

[2] Y. Bilu, “Structure of sets with small sumset”, Structure Theory of Sets Addition, Astérisque, 258, Soc. Math. France, Montrouge, 1999, 77–108 | MR | Zbl

[3] I. Ruzsa, “Generalized arithmetic progressions and sumsets”, Acta Math. Hungar., 65:4 (1994), 379–388 | DOI | MR | Zbl

[4] Mei-Chu Chang, “A polynomial bound in Freiman's theorem”, Duke Math. J., 113:3 (2002), 399–419 | DOI | MR | Zbl

[5] I. Ruzsa, “An analog of Freiman's theorem in groups”, Structure Theory of Set Addition, Astérisque, 258, Soc. Math. France, Montrouge, 1999, 323–326 | MR | Zbl

[6] B. Green, I. Ruzsa, “An analoge of Freiman's theorem in an arbitrary abelian group”, J. London Math. Soc. (to appear)

[7] B. Green, Notes on the Polynomial Freiman–Ruzsa Conjecture, http://www.maths.bris.ac.uk/~mabjg/ papers/PFR.pdf

[8] B. Green, “Boolean functions with small spectral norm”, Geom. Funct. Anal. (to appear)

[9] B. Green, “An inverse theorem for the Gowers $U^3$-norm, with applications”, Proc. Edin. Math. Soc. (to appear)

[10] B. Green, A Note on the Freiman and Balog–Szemerédi–Gowers Theorems in Finite Fields, arXiv: math/0701585v2

[11] T. Sanders, A Note on Freiman's Theorem in Vector Spaces, arXiv: math/0605523v1

[12] B. Green, “Finite field model in additive combinatorics”, Surveys in Combinatorics 2005, London Math. Soc. Lecture Note Ser., 327, Cambridge Univ. Press, Cambridge, 2005, 1–27 | MR | Zbl

[13] A. Balog, E. Szemerédi, “A statistical theorem of set addition”, Combinatorica, 14:3 (1994), 263–268 | DOI | MR | Zbl

[14] W. T. Gowers, “A new proof of Szemerédi's theorem for arithmetic progressions of length four”, Geom. Funct. Anal., 8:3 (1998), 529–551 | DOI | MR | Zbl

[15] W. T. Gowers, “A new proof of Szemerédi's theorem”, Geom. Funct. Anal., 11:3 (2001), 465–588 | DOI | MR | Zbl

[16] G. Elekes, I. Ruzsa, The Structure of Sets with Few Sums along a Graph, http://www.cs.elte.hu/~elekes/ Abstracts/alag.ps

[17] W. Rudin, Fourier Analysis on Groups, John Wiley Sons, Inc., New York, 1990 | MR | Zbl

[18] B. Green, “Spectral structure of sets of integers”, Fourier Analysis and Convexity, Appl. Numer. Harmon. Anal., Birkhäuser Boston, Boston, MA, 2004, 83–96 | MR | Zbl

[19] W. Rudin, “Trigonometric series with gaps”, J. Math. Mech., 9 (1960), 203–227 | MR | Zbl

[20] T. Tao, V. Vu, Additive Combinatorics, Cambridge Stud. Adv. Math., 105, Cambridge Univ. Press, Cambridge, 2006 | MR | Zbl

[21] J. Bourgain, S. Konyagin, “Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order”, C. R. Math. Acad. Sci. Paris, 337:2 (2003), 75–80 | MR | Zbl