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

[Les grands ensembles d’entiers de petite somme modulo $p$ sont contenus dans des progressions arithmétiques courtes]

Serra, Oriol ; Zémor, Gilles

Annales de l'Institut Fourier, Tome 59 (2009), p. 2043-2060 / Harvested from Numdam

Résumé

Nous démontrons qu’il existe un entier strictement positif $\epsilon $, 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|\le (2+\epsilon )|S|$ et $2(|2S|)-2|S|+3\le p$ 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$.

Abstract

We prove that there is a small but fixed positive integer $\epsilon $ such that for every prime $p$ larger than a fixed integer, every subset $S$ of the integers modulo $p$ which satisfies $|2S|\le (2+\epsilon )|S|$ and $2(|2S|)-2|S|+3\le p$ 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$.

Détail

Publié le : 2009-01-01

MR 2573196 | Zbl pre05641407

DOI : https://doi.org/10.5802/aif.2482
Classification:  11P70
Mots clés: somme de parties, progression arithmétique, combinatoire additive

Bibliographie

[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 $\mathbb{Z}/p\mathbb{Z}$, 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