Sets of integers with no large sum-free subset

Abstract

Answering a question of P. Erdős from 1965, we show that for every $\varepsilon> 0$ there is a set $A$ of $n$ integers with the following property: every set $A’ \subset A$ with at least $\left(\frac{1}{3} + \varepsilon\right) n$ elements contains three distinct elements $x,y,z$ with $x + y = z$.

  • [erdos1] P. ErdHos, "Extremal problems in number theory," in Proc. Sympos. Pure Math., Vol. VIII, Providence, R.I.: Amer. Math. Soc., 1965, pp. 181-189.
    @incollection{erdos1, address = {Providence, R.I.},
      author = {Erd{ő}s, P.},
      booktitle = {Proc. {S}ympos. {P}ure {M}ath., {V}ol. {VIII}},
      pages = {181--189},
      publisher = {Amer. Math. Soc.},
      title = {Extremal problems in number theory},
      year = {1965},
      }
  • [alonkleitman] Go to document N. Alon and D. J. Kleitman, "Sum-free subsets," in A Tribute to Paul Erdős, Cambridge: Cambridge Univ. Press, 1990, pp. 13-26.
    @incollection{alonkleitman, address = {Cambridge},
      author = {Alon, Noga and Kleitman, D. J.},
      booktitle = {A Tribute to {P}aul {E}rdős},
      pages = {13--26},
      publisher = {Cambridge Univ. Press},
      title = {Sum-free subsets},
      year = {1990},
      doi = {10.1017/CBO9780511983917.003},
      }
  • [bourgain] Go to document J. Bourgain, "Estimates related to sumfree subsets of sets of integers," Israel J. Math., vol. 97, pp. 71-92, 1997.
    @article{bourgain,
      author = {Bourgain, Jean},
      journal = {Israel J. Math.},
      pages = {71--92},
      title = {Estimates related to sumfree subsets of sets of integers},
      volume = {97},
      year = {1997},
      doi = {10.1007/BF02774027},
      issn = {0021-2172},
      }
  • [malouf] Go to document J. L. Malouf, Combinatorial Approaches to Integer Sequences, ProQuest LLC, Ann Arbor, MI, 1994.
    @book{malouf,
      author = {Malouf, Janice L.},
      note = {Ph.D. thesis, University of Illinois at Urbana-Champaign},
      pages = {64},
      publisher = {ProQuest LLC, Ann Arbor, MI},
      title = {Combinatorial Approaches to Integer Sequences},
      year = {1994},
      url = {http://gateway.proquest.com/ openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/ fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:9512476},
      }
  • [guy] Go to document R. K. Guy, Unsolved Problems in Number Theory, Third ed., New York: Springer-Verlag, 2004.
    @book{guy, address = {New York},
      author = {Guy, Richard K.},
      edition = {Third},
      pages = {xviii+437},
      publisher = {Springer-Verlag},
      series = {Problem Books in Math.},
      title = {Unsolved Problems in Number Theory},
      year = {2004},
      doi = {10.1007/978-0-387-26677-0},
      isbn = {0-387-20860-7},
      }
  • [lewko] Go to document M. Lewko, "An improved upper bound for the sum-free subset constant," J. Integer Seq., vol. 13, iss. 8, p. i, 2010.
    @article{lewko,
      author = {Lewko, Mark},
      journal = {J. Integer Seq.},
      number = {8},
      pages = {Article 10.8.3, 15},
      title = {An improved upper bound for the sum-free subset constant},
      volume = {13},
      year = {2010},
      issn = {1530-7638},
      url = {https://cs.uwaterloo.ca/journals/JIS/VOL13/Lewko/ lewko3.pdf},
      }
  • [erdosklarner] Go to document P. ErdHos, Letter to Klarner, 1992.
    @misc{erdosklarner,
      author = {Erd{ő}s, P.},
      title = {Letter to {K}larner},
      year = {1992},
      url = {http://www.plambeck.org/oldhtml/mathematics/klarner/ep/ index.htm},
      }
  • [alon] Go to document N. Alon, "Paul Erdős and probabilistic reasoning," in Erdős Centennial, New York: Springer-Verlag, 2013, vol. 25, pp. 11-33.
    @incollection{alon, address = {New York},
      author = {Alon, Noga},
      booktitle = {Erdős Centennial},
      pages = {11--33},
      publisher = {Springer-Verlag},
      series = {Bolyai Soc. Math. Stud.},
      title = {Paul {E}rdős and probabilistic reasoning},
      volume = {25},
      year = {2013},
      doi = {10.1007/978-3-642-39286-3_1},
      }
  • [alonspencer] Go to document N. Alon and J. H. Spencer, The Probabilistic Method, Third ed., Hoboken, NJ: John Wiley & Sons, 2008.
    @book{alonspencer, address = {Hoboken, NJ},
      author = {Alon, Noga and Spencer, Joel H.},
      edition = {Third},
      note = {with an appendix on the life and work of Paul Erd{ő}s},
      pages = {xviii+352},
      publisher = {John Wiley \& Sons},
      series = {Wiley-Intersci. Ser. Discrete Math. Optim.},
      title = {The Probabilistic Method},
      year = {2008},
      doi = {10.1002/9780470277331},
      isbn = {978-0-470-17020-5},
      }
  • [crootlev] E. S. Croot III and V. F. Lev, "Open problems in additive combinatorics," in Additive Combinatorics, Providence, RI: Amer. Math. Soc., 2007, vol. 43, pp. 207-233.
    @incollection{crootlev, address = {Providence, RI},
      author = {Croot, III, Ernest S. and Lev, Vsevolod F.},
      booktitle = {Additive Combinatorics},
      pages = {207--233},
      publisher = {Amer. Math. Soc.},
      series = {CRM Proc. Lecture Notes},
      title = {Open problems in additive combinatorics},
      volume = {43},
      year = {2007},
      }
  • [erdos2] P. ErdHos, "Problems and results on combinatorial number theory," in A Survey of Combinatorial Theory, Amsterdam: North-Holland, 1973, pp. 117-138.
    @incollection{erdos2, address = {Amsterdam},
      author = {Erd{ő}s, P.},
      booktitle = {A Survey of Combinatorial Theory},
      pages = {117--138},
      publisher = {North-Holland},
      title = {Problems and results on combinatorial number theory},
      year = {1973},
      }
  • [kolountzakis] M. N. Kolountzakis, "Some applications of probability to additive number theory and harmonic analysis," in Number Theory, New York: Springer-Verlag, 1996, pp. 229-251.
    @incollection{kolountzakis, address = {New York},
      author = {Kolountzakis, Mihail N.},
      booktitle = {Number Theory},
      pages = {229--251},
      publisher = {Springer-Verlag},
      title = {Some applications of probability to additive number theory and harmonic analysis},
      year = {1996},
      }
  • [green-tao-arithregularity] Go to document B. Green and T. Tao, "An arithmetic regularity lemma, an associated counting lemma, and applications," in An Irregular Mind, Budapest: János Bolyai Math. Soc., 2010, vol. 21, pp. 261-334.
    @incollection{green-tao-arithregularity, address = {Budapest},
      author = {Green, Ben and Tao, Terence},
      booktitle = {An Irregular Mind},
      pages = {261--334},
      publisher = {János Bolyai Math. Soc.},
      series = {Bolyai Soc. Math. Stud.},
      title = {An arithmetic regularity lemma, an associated counting lemma, and applications},
      volume = {21},
      year = {2010},
      doi = {10.1007/978-3-642-14444-8_7},
      }
  • [tao-blog] Go to document T. Tao, A variant of Kemperman’s theorem, blog post.
    @misc{tao-blog,
      author = {Tao, Terence},
      title = {A variant of {K}emperman's theorem, blog post},
      url = {http://terrytao.wordpress.com/2011/12/26/ a-variant-of-kempermans-theorem/},
      }
  • [tao-kemperman] Go to document T. Tao, Spending Symmetry.
    @misc{tao-kemperman,
      author = {Tao, Terence},
      note = {in preparation},
      title = {\emph{Spending Symmetry}},
      url = {http://terrytao.wordpress.com/books/spending-symmetry/},
      }
  • [macbeath] Go to document A. M. Macbeath, "On measure of sum sets. II. The sum-theorem for the torus," Proc. Cambridge Philos. Soc., vol. 49, pp. 40-43, 1953.
    @article{macbeath,
      author = {Macbeath, A. M.},
      journal = {Proc. Cambridge Philos. Soc.},
      pages = {40--43},
      title = {On measure of sum sets. {II}. {T}he sum-theorem for the torus},
      volume = {49},
      year = {1953},
      doi = {10.1017/S0305004100028012},
      }
  • [green-ruzsa] Go to document B. Green and I. Z. Ruzsa, "Sum-free sets in abelian groups," Israel J. Math., vol. 147, pp. 157-188, 2005.
    @article{green-ruzsa,
      author = {Green, Ben and Ruzsa, Imre Z.},
      journal = {Israel J. Math.},
      pages = {157--188},
      title = {Sum-free sets in abelian groups},
      volume = {147},
      year = {2005},
      doi = {10.1007/BF02785363},
      issn = {0021-2172},
      }
  • [brunn-minkowski-survey] Go to document R. J. Gardner, "The Brunn-Minkowski inequality," Bull. Amer. Math. Soc., vol. 39, iss. 3, pp. 355-405, 2002.
    @article{brunn-minkowski-survey,
      author = {Gardner, R. J.},
      journal = {Bull. Amer. Math. Soc.},
      number = {3},
      pages = {355--405},
      title = {The {B}runn-{M}inkowski inequality},
      volume = {39},
      year = {2002},
      doi = {10.1090/S0273-0979-02-00941-2},
      issn = {0273-0979},
      }
  • [ruzsa-measure] Go to document I. Z. Ruzsa, "Diameter of sets and measure of sumsets," Monatsh. Math., vol. 112, iss. 4, pp. 323-328, 1991.
    @article{ruzsa-measure,
      author = {Ruzsa, Imre Z.},
      journal = {Monatsh. Math.},
      number = {4},
      pages = {323--328},
      title = {Diameter of sets and measure of sumsets},
      volume = {112},
      year = {1991},
      doi = {10.1007/BF01351772},
      issn = {0026-9255},
      }
  • [lev] Go to document V. F. Lev, "Optimal representations by sumsets and subset sums," J. Number Theory, vol. 62, iss. 1, pp. 127-143, 1997.
    @article{lev,
      author = {Lev, Vsevolod F.},
      journal = {J. Number Theory},
      number = {1},
      pages = {127--143},
      title = {Optimal representations by sumsets and subset sums},
      volume = {62},
      year = {1997},
      doi = {10.1006/jnth.1997.2012},
      issn = {0022-314X},
      }
  • [sarkozy] Go to document A. Sárközy, "Finite addition theorems. I," J. Number Theory, vol. 32, iss. 1, pp. 114-130, 1989.
    @article{sarkozy,
      author = {S{á}rk{ö}zy, A.},
      journal = {J. Number Theory},
      number = {1},
      pages = {114--130},
      title = {Finite addition theorems. {I}},
      volume = {32},
      year = {1989},
      doi = {10.1016/0022-314X(89)90102-9},
      issn = {0022-314X},
      }
  • [tv] Go to document T. Tao and V. H. Vu, Additive Combinatorics, Cambridge: Cambridge Univ. Press, 2010, vol. 105.
    @book{tv, address = {Cambridge},
      author = {Tao, Terence and Vu, Van H.},
      note = {paperback edition of [\mr{2289012}]},
      pages = {xviii+512},
      publisher = {Cambridge Univ. Press},
      series = {Cambridge Stud. Adv. Math.},
      title = {Additive Combinatorics},
      volume = {105},
      year = {2010},
      doi = {10.1017/CBO9780511755149},
      isbn = {978-0-521-13656-3},
      }
  • [green-ruzsa-rectification] Go to document B. Green and I. Z. Ruzsa, "Sets with small sumset and rectification," Bull. London Math. Soc., vol. 38, iss. 1, pp. 43-52, 2006.
    @article{green-ruzsa-rectification,
      author = {Green, Ben and Ruzsa, Imre Z.},
      journal = {Bull. London Math. Soc.},
      number = {1},
      pages = {43--52},
      title = {Sets with small sumset and rectification},
      volume = {38},
      year = {2006},
      doi = {10.1112/S0024609305018102},
      issn = {0024-6093},
      }
  • [freiman-book] G. A. Freuiman, Foundations of a Structural Theory of Set Addition, Providence, R. I.: Amer. Math. Soc., 1973.
    @book{freiman-book, address = {Providence, R. I.},
      author = {Fre{\u\i}man, G. A.},
      note = {translated from the Russian, \emph{Trans. Math. Monogr.} {\bf 37}},
      pages = {vii+108},
      publisher = {Amer. Math. Soc.},
      title = {Foundations of a Structural Theory of Set Addition},
      year = {1973},
      }
  • [lev-smeliansky] V. F. Lev and P. Y. Smeliansky, "On addition of two distinct sets of integers," Acta Arith., vol. 70, iss. 1, pp. 85-91, 1995.
    @article{lev-smeliansky,
      author = {Lev, Vsevolod F. and Smeliansky, Pavel Y.},
      journal = {Acta Arith.},
      number = {1},
      pages = {85--91},
      title = {On addition of two distinct sets of integers},
      volume = {70},
      year = {1995},
      issn = {0065-1036},
      }
  • [bilu] Y. Bilu, "Structure of sets with small sumset," in Structure Theory of Set Addition, Paris: Soc. Math. France, 1999, vol. 258, p. xi, 77-108.
    @incollection{bilu, address = {Paris},
      author = {Bilu, Yuri},
      booktitle = {Structure Theory of Set Addition},
      pages = {xi, 77--108},
      publisher = {Soc. Math. France},
      series = {Astérisque},
      title = {Structure of sets with small sumset},
      volume = {258},
      year = {1999},
      issn = {0303-1179},
      }
  • [sean-writeup] Go to document S. Eberhard, The abelian arithmetic regularity lemma.
    @misc{sean-writeup,
      author = {Eberhard, Sean},
      note = {unpublished},
      title = {The abelian arithmetic regularity lemma},
      url = {https://www.dpmms.cam.ac.uk/~se288/abelianregularity.pdf},
      }
  • [green-tao-quadraticuniformity] Go to document B. Green and T. Tao, "Quadratic uniformity of the Möbius function," Ann. Inst. Fourier $($Grenoble$)$, vol. 58, iss. 6, pp. 1863-1935, 2008.
    @article{green-tao-quadraticuniformity,
      author = {Green, Ben and Tao, Terence},
      journal = {Ann. Inst. Fourier $($Grenoble$)$},
      number = {6},
      pages = {1863--1935},
      title = {Quadratic uniformity of the {M}öbius function},
      volume = {58},
      year = {2008},
      doi = {10.5802/aif.2401},
      issn = {0373-0956},
      }

Authors

Sean Eberhard

Mathematical Institute, University of Oxford, Oxford, United Kingdom

Ben Green

Mathematical Institute, University of Oxford, Oxford, United Kingdom

Freddie Manners

Mathematical Institute, University of Oxford, Oxford, United Kingdom