On Roth’s theorem on progressions

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] Go to document 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] Go to document 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] Go to document 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::] Go to document 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] Go to document 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::] Go to document 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::] Go to document 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::] Go to document 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::] Go to document 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] Go to document 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] Go to document 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::] Go to document 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] Go to document 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::] Go to document 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::] Go to document 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},
     }

Authors

Tom Sanders

DPMMS
Centre for Mathematical Sciences
University of Cambridge
Wilberforce Road
Cambridge CB3 0WA
England