Large sets with small doubling modulo $p$ are well covered by an arithmetic progression

Serra, Oriol; Zémor, Gilles

Annales de l'Institut Fourier, Volume 59 (2009) no. 5, pp. 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 $\left|2S\right|\le (2+ϵ)\left|S\right|$ and $2\left(\right|2S\left|\right)-2\left|S\right|+3\le p$ is contained in an arithmetic progression of length $\left|2S\right|-\left|S\right|+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 $\left|2S\right|\le (2+ϵ)\left|S\right|$ et $2\left(\right|2S\left|\right)-2\left|S\right|+3\le p$ est contenu dans une progression arithmétique de longueur $\left|2S\right|-\left|S\right|+1$. Il s’agit du premier résultat de cette nature qui ne contraint pas inutilement le cardinal de $S$.

Classification: 11P70
Keywords: Sumset, arithmetic progression, additive combinatorics
Mot clés : somme de parties, progression arithmétique, combinatoire additive

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

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

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

[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 | Zbl

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

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

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

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

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

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

[11] Hamidoune, Yahya O.; Serra, Oriol; Zémor, Gilles On the critical pair theory in $\mathbb{Z}/p\mathbb{Z}$, Acta Arith., Volume 121 (2006) no. 2, pp. 99-115 | DOI | MR | Zbl

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

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

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

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

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

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

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

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