Large sets with small doubling modulo p are well covered by an arithmetic progression
Annales de l'Institut Fourier, Volume 59 (2009) no. 5, p. 2043-2060

We prove that there is a small but fixed positive integer ϵ such that for every prime p larger than a fixed integer, every subset S of the integers modulo p which satisfies |2S|(2+ϵ)|S| and 2(|2S|)-2|S|+3p is contained in an arithmetic progression of length |2S|-|S|+1. This is the first result of this nature which places no unnecessary restrictions on the size of S.

Nous démontrons qu’il existe un entier strictement positif ϵ, petit mais fixé, tel que pour tout nombre premier p plus grand qu’un entier fixé, tout sous-ensemble S des entiers modulo p qui vérifie |2S|(2+ϵ)|S| et 2(|2S|)-2|S|+3p est contenu dans une progression arithmétique de longueur |2S|-|S|+1. Il s’agit du premier résultat de cette nature qui ne contraint pas inutilement le cardinal de S.

DOI : https://doi.org/10.5802/aif.2482
Classification:  11P70
Keywords: Sumset, arithmetic progression, additive combinatorics
@article{AIF_2009__59_5_2043_0,
     author = {Serra, Oriol and Z\'emor, Gilles},
     title = {Large sets with small doubling modulo $p$ are well covered by an arithmetic progression},
     journal = {Annales de l'Institut Fourier},
     publisher = {Association des Annales de l'institut Fourier},
     volume = {59},
     number = {5},
     year = {2009},
     pages = {2043-2060},
     doi = {10.5802/aif.2482},
     mrnumber = {2573196},
     zbl = {pre05641407},
     language = {en},
     url = {http://www.numdam.org/item/AIF_2009__59_5_2043_0}
}
Serra, Oriol; Zémor, Gilles. Large sets with small doubling modulo $p$ are well covered by an arithmetic progression. Annales de l'Institut Fourier, Volume 59 (2009) no. 5, pp. 2043-2060. doi : 10.5802/aif.2482. http://www.numdam.org/item/AIF_2009__59_5_2043_0/

[1] Bilu, Y. F.; Lev, V. F.; Ruzsa, I. Z. Rectification principles in additive number theory, Discrete Comput. Geom., Tome 19 (1998) no. 3, Special Issue, pp. 343-353 (Dedicated to the memory of Paul Erdős) | Article | MR 1608875 | Zbl 0899.11002

[2] Freĭman, G. A. The addition of finite sets. I, Izv. Vysš. Učebn. Zaved. Matematika, Tome 1959 (1959) no. 6 (13), pp. 202-213 | MR 126388 | Zbl 0096.25904

[3] Freĭman, G. A. Inverse problems in additive number theory. Addition of sets of residues modulo a prime, Dokl. Akad. Nauk SSSR, Tome 141 (1961), pp. 571-573 | MR 155810 | Zbl 0109.27203

[4] Freĭman, G. A. Foundations of a structural theory of set addition, American Mathematical Society, Providence, R. I. (1973) (Translated from the Russian, Translations of Mathematical Monographs, Vol 37) | MR 360496 | Zbl 0271.10044

[5] Green, Ben; Ruzsa, Imre Z. Sets with small sumset and rectification, Bull. London Math. Soc., Tome 38 (2006) no. 1, pp. 43-52 | Article | MR 2201602 | Zbl 1155.11307

[6] Hamidoune, Yahya O. On the connectivity of Cayley digraphs, European J. Combin., Tome 5 (1984) no. 4, pp. 309-312 | MR 782052 | Zbl 0561.05028

[7] Hamidoune, Yahya O. An isoperimetric method in additive theory, J. Algebra, Tome 179 (1996) no. 2, pp. 622-630 | Article | MR 1367866 | Zbl 0842.20029

[8] Hamidoune, Yahya O. Subsets with small sums in abelian groups. I. The Vosper property, European J. Combin., Tome 18 (1997) no. 5, pp. 541-556 | Article | MR 1455186 | Zbl 0883.05065

[9] Hamidoune, Yahya O. Some results in additive number theory. I. The critical pair theory, Acta Arith., Tome 96 (2000) no. 2, pp. 97-119 | Article | MR 1814447 | Zbl 0985.11011

[10] Hamidoune, Yahya O.; Rødseth, Øystein J. An inverse theorem mod p, Acta Arith., Tome 92 (2000) no. 3, pp. 251-262 | Zbl 0945.11003

[11] Hamidoune, Yahya O.; Serra, Oriol; Zémor, Gilles On the critical pair theory in /p, Acta Arith., Tome 121 (2006) no. 2, pp. 99-115 | Article | MR 2216136 | Zbl 1147.11060

[12] Hamidoune, Yahya O.; Serra, Oriol; Zémor, Gilles On the critical pair theory in abelian groups: beyond Chowla’s theorem, Combinatorica, Tome 28 (2008) no. 4, pp. 441-467 | Article | MR 2452844

[13] Lev, Vsevolod F.; Smeliansky, Pavel Y. On addition of two distinct sets of integers, Acta Arith., Tome 70 (1995) no. 1, pp. 85-91 | MR 1318763 | Zbl 0817.11005

[14] Nathanson, Melvyn B. Additive number theory, Springer-Verlag, New York, Graduate Texts in Mathematics, Tome 165 (1996) (Inverse problems and the geometry of sumsets) | MR 1477155 | Zbl 0859.11002

[15] Rødseth, Øystein J. On Freiman’s 2.4-Theorem, Skr. K. Nor. Vidensk. Selsk. (2006) no. 4, pp. 11-18 | Zbl 1162.11010

[16] Ruzsa, Imre Z. An application of graph theory to additive number theory, Sci. Ser. A Math. Sci. (N.S.), Tome 3 (1989), pp. 97-109 | MR 2314377 | Zbl 0743.05052

[17] Serra, Oriol; Zémor, Gilles On a generalization of a theorem by Vosper, Integers (2000), pp. A10, 10 pp. (electronic) | MR 1771980 | Zbl 0953.11031

[18] Tao, Terence; Vu, Van Additive combinatorics, Cambridge University Press, Cambridge, Cambridge Studies in Advanced Mathematics, Tome 105 (2006) | MR 2289012 | Zbl 1127.11002

[19] Vosper, A. G. The critical pairs of subsets of a group of prime order, J. London Math. Soc., Tome 31 (1956), pp. 200-205 | Article | MR 77555 | Zbl 0072.03402