Abstract
We show that if $A \subset \{1,\dots,N\}$ contains no nontrivial three-term arithmetic progressions then $|A|=O(N/\log^{1-o(1)}N)$.
-
[beh::] F. A. Behrend, "On sets of integers which contain no three terms in arithmetical progression," Proc. Nat. Acad. Sci. U.S.A., vol. 32, pp. 331-332, 1946.
@article {beh::, MRKEY = {0018694},
AUTHOR = {Behrend, F. A.},
TITLE = {On sets of integers which contain no three terms in arithmetical progression},
JOURNAL = {Proc. Nat. Acad. Sci. U.S.A.},
FJOURNAL = {Proceedings of the National Academy of Sciences of the United States of America},
VOLUME = {32},
YEAR = {1946},
PAGES = {331--332},
ISSN = {0027-8424},
MRCLASS = {10.0X},
MRNUMBER = {0018694},
MRREVIEWER = {P. Erd{ö}s},
ZBLNUMBER = {0060.10302},
} -
[bou::4] J. Bourgain, "On arithmetic progressions in sums of sets of integers," in A Tribute to Paul Erdős, Cambridge: Cambridge Univ. Press, 1990, pp. 105-109.
@incollection {bou::4, MRKEY = {1117007},
AUTHOR = {Bourgain, Jean},
TITLE = {On arithmetic progressions in sums of sets of integers},
BOOKTITLE = {A Tribute to {P}aul {E}rdős},
PAGES = {105--109},
PUBLISHER = {Cambridge Univ. Press},
ADDRESS = {Cambridge},
YEAR = {1990},
MRCLASS = {11B25 (11N64)},
MRNUMBER = {1117007},
MRREVIEWER = {Armel Mercier},
ZBLNUMBER = {0715.11006},
} -
[bou::5]
J. Bourgain, "On triples in arithmetic progression," Geom. Funct. Anal., vol. 9, iss. 5, pp. 968-984, 1999.@article {bou::5, MRKEY = {1726234},
AUTHOR = {Bourgain, Jean},
TITLE = {On triples in arithmetic progression},
JOURNAL = {Geom. Funct. Anal.},
FJOURNAL = {Geometric and Functional Analysis},
VOLUME = {9},
YEAR = {1999},
NUMBER = {5},
PAGES = {968--984},
ISSN = {1016-443X},
CODEN = {GFANFB},
MRCLASS = {11P55 (11B25 11N64)},
MRNUMBER = {1726234},
MRREVIEWER = {Serge{\u\i} V. Konyagin},
DOI = {10.1007/s000390050105},
ZBLNUMBER = {0959.11004},
} -
[bou::1] J. Bourgain, "Roth’s theorem on progressions revisited," J. Anal. Math., vol. 104, pp. 155-192, 2008.
@article {bou::1, MRKEY = {2403433},
AUTHOR = {Bourgain, Jean},
TITLE = {Roth's theorem on progressions revisited},
JOURNAL = {J. Anal. Math.},
FJOURNAL = {Journal d'Analyse Mathématique},
VOLUME = {104},
YEAR = {2008},
PAGES = {155--192},
ISSN = {0021-7670},
CODEN = {JOAMAV},
MRCLASS = {11B25 (11N64 11P55)},
MRNUMBER = {2403433},
MRREVIEWER = {Serge{\u\i} V. Konyagin},
DOI = {10.1007/s11854-008-0020-x},
ZBLNUMBER = {1155.11011},
} -
[cha::0] M. Chang, "A polynomial bound in Freiman’s theorem," Duke Math. J., vol. 113, iss. 3, pp. 399-419, 2002.
@article {cha::0, MRKEY = {1909605},
AUTHOR = {Chang, Mei-Chu},
TITLE = {A polynomial bound in {F}reiman's theorem},
JOURNAL = {Duke Math. J.},
FJOURNAL = {Duke Mathematical Journal},
VOLUME = {113},
YEAR = {2002},
NUMBER = {3},
PAGES = {399--419},
ISSN = {0012-7094},
CODEN = {DUMJAO},
MRCLASS = {11P70 (11B13 11B25)},
MRNUMBER = {1909605},
MRREVIEWER = {Ben Joseph Green},
DOI = {10.1215/S0012-7094-02-11331-3},
ZBLNUMBER = {1035.11048},
} -
[crosis::] E. Croot and O. Sisask, "A probabilistic technique for finding almost-periods of convolutions," Geom. Funct. Anal., vol. 20, iss. 6, pp. 1367-1396, 2010.
@article {crosis::, MRKEY = {2738997},
AUTHOR = {Croot, Ernie and Sisask, Olof},
TITLE = {A probabilistic technique for finding almost-periods of convolutions},
JOURNAL = {Geom. Funct. Anal.},
FJOURNAL = {Geometric and Functional Analysis},
VOLUME = {20},
YEAR = {2010},
NUMBER = {6},
PAGES = {1367--1396},
ISSN = {1016-443X},
CODEN = {GFANFB},
MRCLASS = {11B30 (20P05)},
MRNUMBER = {2738997},
DOI = {10.1007/s00039-010-0101-8},
ZBLNUMBER = {05833796},
} -
[cwasch::] K. Cwalina and T. Schoen, A linear bound on the dimension in Green-Ruzsa’s theorem, 2010.
@misc{cwasch::,
author={Cwalina, K. and Schoen, T.},
TITLE={A linear bound on the dimension in {G}reen-{R}uzsa's theorem},
NOTE={preprint},
YEAR={2010},
} -
[elk::] M. Elkin, "An improved construction of progression-free sets," in Symposium on Discrete Algorithms, , 2010, pp. 886-905.
@incollection{elk::,
author={Elkin, M.},
TITLE={An improved construction of progression-free sets},
BOOKTITLE={Symposium on Discrete Algorithms},
PAGES={886--905},
YEAR={2010},
} -
[gre::8] B. Green, "Roth’s theorem in the primes," Ann. of Math., vol. 161, iss. 3, pp. 1609-1636, 2005.
@article {gre::8, MRKEY = {2180408},
AUTHOR = {Green, Ben},
TITLE = {Roth's theorem in the primes},
JOURNAL = {Ann. of Math.},
FJOURNAL = {Annals of Mathematics. Second Series},
VOLUME = {161},
YEAR = {2005},
NUMBER = {3},
PAGES = {1609--1636},
ISSN = {0003-486X},
CODEN = {ANMAAH},
MRCLASS = {11N13 (11B25)},
MRNUMBER = {2180408},
MRREVIEWER = {Mei Chu Chang},
DOI = {10.4007/annals.2005.161.1609},
ZBLNUMBER = {1160.11307},
} -
[gowwol::] W. T. Gowers and J. Wolf, "The true complexity of a system of linear equations," Proc. Lond. Math. Soc., vol. 100, iss. 1, pp. 155-176, 2010.
@article {gowwol::, MRKEY = {2578471},
AUTHOR = {Gowers, W. T. and Wolf, J.},
TITLE = {The true complexity of a system of linear equations},
JOURNAL = {Proc. Lond. Math. Soc.},
FJOURNAL = {Proceedings of the London Mathematical Society. Third Series},
VOLUME = {100},
YEAR = {2010},
NUMBER = {1},
PAGES = {155--176},
ISSN = {0024-6115},
MRCLASS = {11B30 (11T24 37A45)},
MRNUMBER = {2578471},
MRREVIEWER = {Randall McCutcheon},
DOI = {10.1112/plms/pdp019},
ZBLNUMBER = {05658776},
} -
[grewol::] B. Green and J. Wolf, "A note on Elkin’s improvement of Behrend’s construction," in Additive Number Theory: Festschrift in Honor of the Sixtieth Birthday of Melvyn B. Nathanson, 1st ed., New York: Springer-Verlag, 2010, pp. 141-144.
@incollection{grewol::,
author={Green, Ben and Wolf, J.},
TITLE={A note on {E}lkin's improvement of {B}ehrend's construction},
BOOKTITLE={Additive Number Theory: Festschrift in Honor of the Sixtieth Birthday of {M}elvyn {B}. {N}athanson},
PUBLISHER={Springer-Verlag},
ADDRESS={New York},
PAGES={141--144},
EDITION={1st},
YEAR={2010},
} -
[hea::] D. R. Heath-Brown, "Integer sets containing no arithmetic progressions," J. London Math. Soc., vol. 35, iss. 3, pp. 385-394, 1987.
@article {hea::, MRKEY = {0889362},
AUTHOR = {Heath-Brown, D. R.},
TITLE = {Integer sets containing no arithmetic progressions},
JOURNAL = {J. London Math. Soc.},
FJOURNAL = {Journal of the London Mathematical Society. Second Series},
VOLUME = {35},
YEAR = {1987},
NUMBER = {3},
PAGES = {385--394},
ISSN = {0024-6107},
CODEN = {JLMSAK},
MRCLASS = {11B25 (11N35)},
MRNUMBER = {0889362},
MRREVIEWER = {Andr{á}s S{á}rk{ö}zy},
DOI = {10.1112/jlms/s2-35.3.385},
ZBLNUMBER = {0589.10062},
} -
[katkoe::] N. H. Katz and P. Koester, "On additive doubling and energy," SIAM J. Discrete Math., vol. 24, iss. 4, pp. 1684-1693, 2010.
@article {katkoe::, MRKEY = {2746716},
AUTHOR = {Katz, Nets Hawk and Koester, Paul},
TITLE = {On additive doubling and energy},
JOURNAL = {SIAM J. Discrete Math.},
FJOURNAL = {SIAM Journal on Discrete Mathematics},
VOLUME = {24},
YEAR = {2010},
NUMBER = {4},
PAGES = {1684--1693},
ISSN = {0895-4801},
MRCLASS = {11B30 (05B99 05E99)},
MRNUMBER = {2746716},
DOI = {10.1137/080717286},
} -
[mes::] R. Meshulam, "On subsets of finite abelian groups with no $3$-term arithmetic progressions," J. Combin. Theory Ser. A, vol. 71, iss. 1, pp. 168-172, 1995.
@article {mes::, MRKEY = {1335785},
AUTHOR = {Meshulam, Roy},
TITLE = {On subsets of finite abelian groups with no {$3$}-term arithmetic progressions},
JOURNAL = {J. Combin. Theory Ser. A},
FJOURNAL = {Journal of Combinatorial Theory. Series A},
VOLUME = {71},
YEAR = {1995},
NUMBER = {1},
PAGES = {168--172},
ISSN = {0097-3165},
CODEN = {JCBTA7},
MRCLASS = {20D60 (05D10 11P99)},
MRNUMBER = {1335785},
DOI = {10.1016/0097-3165(95)90024-1},
ZBLNUMBER = {0832.11006},
} -
[rot::] K. Roth, "Sur quelques ensembles d’entiers," C. R. Acad. Sci. Paris, vol. 234, pp. 388-390, 1952.
@article {rot::, MRKEY = {0046374},
AUTHOR = {Roth, Klaus},
TITLE = {Sur quelques ensembles d'entiers},
JOURNAL = {C. R. Acad. Sci. Paris},
VOLUME = {234},
YEAR = {1952},
PAGES = {388--390},
MRCLASS = {10.0X},
MRNUMBER = {0046374},
MRREVIEWER = {P. Erd{ö}s},
ZBLNUMBER = {0046.04302},
} -
[rot::0] K. Roth, "On certain sets of integers," J. London Math. Soc., vol. 28, pp. 104-109, 1953.
@article {rot::0, MRKEY = {0051853},
AUTHOR = {Roth, Klaus},
TITLE = {On certain sets of integers},
JOURNAL = {J. London Math. Soc.},
FJOURNAL = {Journal of the London Mathematical Society. Second Series},
VOLUME = {28},
YEAR = {1953},
PAGES = {104--109},
ISSN = {0024-6107},
MRCLASS = {10.0X},
MRNUMBER = {0051853},
MRREVIEWER = {P. Erd{ö}s},
DOI = {10.1112/jlms/s1-28.1.104},
ZBLNUMBER = {0050.04002},
} -
[san::01] T. Sanders, On certain other sets of integers, 2010.
@misc{san::01,
author={Sanders, T.},
TITLE={On certain other sets of integers},
NOTE={{\it J. Anal. Math.},
to appear},
ARXIV={1007.5444},
YEAR={2010},
} -
[sch::1] T. Schoen, "Near optimal bounds in Freiman’s theorem," Duke Math. J., vol. 158, pp. 1-12, 2011.
@article{sch::1,
author={Schoen, T.},
TITLE={Near optimal bounds in {F}reiman's theorem},
JOURNAL={Duke Math. J.},
VOLUME={158},
YEAR={2011},
PAGES={1--12},
DOI = {10.1215/00127094-1276283},
} -
[salspe::] R. Salem and D. C. Spencer, "On sets of integers which contain no three terms in arithmetical progression," Proc. Nat. Acad. Sci. U. S. A., vol. 28, pp. 561-563, 1942.
@article {salspe::, MRKEY = {0007405},
AUTHOR = {Salem, R. and Spencer, D. C.},
TITLE = {On sets of integers which contain no three terms in arithmetical progression},
JOURNAL = {Proc. Nat. Acad. Sci. U. S. A.},
FJOURNAL = {Proceedings of the National Academy of Sciences of the United States of America},
VOLUME = {28},
YEAR = {1942},
PAGES = {561--563},
ISSN = {0027-8424},
MRCLASS = {10.0X},
MRNUMBER = {0007405},
MRREVIEWER = {P. Erd{ö}s},
ZBLNUMBER = {0060.10301},
} -
[schshk::] T. Schoen and I. Shkredov, Additive properties of multiplicative subgroups in $\mathbb{F}_p$, 2011.
@misc{schshk::,
author={Schoen, T. and Shkredov, I.},
TITLE={Additive properties of multiplicative subgroups in {$\mathbb{F}_p$}},
NOTE={{\it Quart. J. Math.},
to appear},
YEAR={2011},
DOI = {10.1093/qmath/har002},
} -
[sze::2] E. Szemerédi, "Integer sets containing no arithmetic progressions," Acta Math. Hungar., vol. 56, iss. 1-2, pp. 155-158, 1990.
@article {sze::2, MRKEY = {1100788},
AUTHOR = {Szemer{é}di, E.},
TITLE = {Integer sets containing no arithmetic progressions},
JOURNAL = {Acta Math. Hungar.},
FJOURNAL = {Acta Mathematica Hungarica},
VOLUME = {56},
YEAR = {1990},
NUMBER = {1-2},
PAGES = {155--158},
ISSN = {0236-5294},
MRCLASS = {11N64 (11B25 11P55)},
MRNUMBER = {1100788},
MRREVIEWER = {D. R. Heath-Brown},
DOI = {10.1007/BF01903717},
ZBLNUMBER = {0721.11007},
} -
[taovu::] T. Tao and V. Vu, Additive Dombinatorics, Cambridge: Cambridge Univ. Press, 2006, vol. 105.
@book {taovu::, MRKEY = {2289012},
AUTHOR = {Tao, Terence and Vu, Van},
TITLE = {Additive Dombinatorics},
SERIES = {Cambridge Stud. Adv. Math.},
VOLUME = {105},
PUBLISHER = {Cambridge Univ. Press},
ADDRESS = {Cambridge},
YEAR = {2006},
PAGES = {xviii+512},
ISBN = {978-0-521-85386-6; 0-521-85386-9},
MRCLASS = {11-02 (05-02 05D10 11B13 11P70 11P82 28D05 37A45)},
MRNUMBER = {2289012},
MRREVIEWER = {Serge{\u\i} V. Konyagin},
DOI = {10.1017/CBO9780511755149},
ZBLNUMBER = {1127.11002},
} -
[yaohan::] R. Yao-Feng and L. Han-Ying, "On the best constant in Marcinkiewicz-Zygmund inequality," Stat. Prob. Lett., vol. 53, pp. 227-233, 2001.
@article{yaohan::,
author={Yao-Feng, R. and Han-Ying, L.},
TITLE={On the best constant in {M}arcinkiewicz-{Z}ygmund inequality},
JOURNAL={Stat. Prob. Lett.},
VOLUME={53},
YEAR={2001},
PAGES={227--233},
MRNUMBER = {1841623},
ZBLNUMBER = {0991.60011},
DOI = {10.1016/S0167-7152(01)00015-3},
}
Full Article