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

Oriol Serra[1]; Gilles Zémor[2]

  • [1] Universitat Politècnica de Catalunya Matemàtica Aplicada IV Campus Nord - Edif. C3, C. Jordi Girona, 1-3 08034 Barcelona (Spain)
  • [2] Université Bordeaux 1 Institut de Mathématiques de Bordeaux, UMR 5251 351, cours de la Libération 33405 Talence (France)

Annales de l’institut Fourier (2009)

  • Volume: 59, Issue: 5, page 2043-2060
  • ISSN: 0373-0956

Abstract

top
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 | 2 S | ≤ ( 2 + ϵ ) | S | and 2 ( | 2 S | ) - 2 | S | + 3 ≤ p is contained in an arithmetic progression of length | 2 S | - | S | + 1 . This is the first result of this nature which places no unnecessary restrictions on the size of S .

How to cite

top

Serra, Oriol, and Zémor, Gilles. "Large sets with small doubling modulo $p$ are well covered by an arithmetic progression." Annales de l’institut Fourier 59.5 (2009): 2043-2060. <http://eudml.org/doc/10446>.

@article{Serra2009,
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$.},
affiliation = {Universitat Politècnica de Catalunya Matemàtica Aplicada IV Campus Nord - Edif. C3, C. Jordi Girona, 1-3 08034 Barcelona (Spain); Université Bordeaux 1 Institut de Mathématiques de Bordeaux, UMR 5251 351, cours de la Libération 33405 Talence (France)},
author = {Serra, Oriol, Zémor, Gilles},
journal = {Annales de l’institut Fourier},
keywords = {Sumset; arithmetic progression; additive combinatorics; sumset},
language = {eng},
number = {5},
pages = {2043-2060},
publisher = {Association des Annales de l’institut Fourier},
title = {Large sets with small doubling modulo $p$ are well covered by an arithmetic progression},
url = {http://eudml.org/doc/10446},
volume = {59},
year = {2009},
}

TY - JOUR
AU - Serra, Oriol
AU - Zémor, Gilles
TI - Large sets with small doubling modulo $p$ are well covered by an arithmetic progression
JO - Annales de l’institut Fourier
PY - 2009
PB - Association des Annales de l’institut Fourier
VL - 59
IS - 5
SP - 2043
EP - 2060
AB - 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$.
LA - eng
KW - Sumset; arithmetic progression; additive combinatorics; sumset
UR - http://eudml.org/doc/10446
ER -

References

top
  1. Y. F. Bilu, V. F. Lev, I. Z. Ruzsa, Rectification principles in additive number theory, Discrete Comput. Geom. 19 (1998), 343-353 Zbl0899.11002MR1608875
  2. G. A. Freĭman, The addition of finite sets. I, Izv. Vysš. Učebn. Zaved. Matematika 1959 (1959), 202-213 Zbl0096.25904MR126388
  3. G. A. Freĭman, Inverse problems in additive number theory. Addition of sets of residues modulo a prime, Dokl. Akad. Nauk SSSR 141 (1961), 571-573 Zbl0109.27203MR155810
  4. G. A. Freĭman, Foundations of a structural theory of set addition, (1973), American Mathematical Society, Providence, R. I. Zbl0271.10044MR360496
  5. Ben Green, Imre Z. Ruzsa, Sets with small sumset and rectification, Bull. London Math. Soc. 38 (2006), 43-52 Zbl1155.11307MR2201602
  6. Yahya O. Hamidoune, On the connectivity of Cayley digraphs, European J. Combin. 5 (1984), 309-312 Zbl0561.05028MR782052
  7. Yahya O. Hamidoune, An isoperimetric method in additive theory, J. Algebra 179 (1996), 622-630 Zbl0842.20029MR1367866
  8. Yahya O. Hamidoune, Subsets with small sums in abelian groups. I. The Vosper property, European J. Combin. 18 (1997), 541-556 Zbl0883.05065MR1455186
  9. Yahya O. Hamidoune, Some results in additive number theory. I. The critical pair theory, Acta Arith. 96 (2000), 97-119 Zbl0985.11011MR1814447
  10. Yahya O. Hamidoune, Øystein J. Rødseth, An inverse theorem mod p , Acta Arith. 92 (2000), 251-262 Zbl0945.11003
  11. Yahya O. Hamidoune, Oriol Serra, Gilles Zémor, On the critical pair theory in ℤ / p ℤ , Acta Arith. 121 (2006), 99-115 Zbl1147.11060MR2216136
  12. Yahya O. Hamidoune, Oriol Serra, Gilles Zémor, On the critical pair theory in abelian groups: beyond Chowla’s theorem, Combinatorica 28 (2008), 441-467 Zbl1192.11071MR2452844
  13. Vsevolod F. Lev, Pavel Y. Smeliansky, On addition of two distinct sets of integers, Acta Arith. 70 (1995), 85-91 Zbl0817.11005MR1318763
  14. Melvyn B. Nathanson, Additive number theory, 165 (1996), Springer-Verlag, New York Zbl0859.11002MR1477155
  15. Øystein J. Rødseth, On Freiman’s 2.4-Theorem, Skr. K. Nor. Vidensk. Selsk. (2006), 11-18 Zbl1162.11010
  16. Imre Z. Ruzsa, An application of graph theory to additive number theory, Sci. Ser. A Math. Sci. (N.S.) 3 (1989), 97-109 Zbl0743.05052MR2314377
  17. Oriol Serra, Gilles Zémor, On a generalization of a theorem by Vosper, Integers (2000) Zbl0953.11031MR1771980
  18. Terence Tao, Van Vu, Additive combinatorics, 105 (2006), Cambridge University Press, Cambridge Zbl1127.11002MR2289012
  19. A. G. Vosper, The critical pairs of subsets of a group of prime order, J. London Math. Soc. 31 (1956), 200-205 Zbl0072.03402MR77555

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.