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]
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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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},
}
Full Article