On large subsets of $\mathbb{F}_q^n$ with no three-term arithmetic progression

Abstract

In this note, we show that the method of Croot, Lev, and Pach can be used to bound the size of a subset of $\mathbb{F}_q^n$ with no three terms in arithmetic progression by $c^n$ with $c < q$. For $q=3$, the problem of finding the largest subset of $\mathbb{F}_3^n$ with no three terms in arithmetic progression is called the cap set problem. Previously the best known upper bound for the affine cap problem, due to Bateman and Katz, was on order $n^{-1-\epsilon} 3^n$.

  • [bateman] Go to document M. Bateman and N. H. Katz, "New bounds on cap sets," J. Amer. Math. Soc., vol. 25, iss. 2, pp. 585-613, 2012.
    @ARTICLE{bateman, zblnumber = {1262.11010},
      number = {2},
      volume = {25},
      author = {Bateman, Michael and Katz, Nets H.},
      title = {New bounds on cap sets},
      year = {2012},
      pages = {585--613},
      journal = {J. Amer. Math. Soc.},
      mrnumber = {2869028},
      doi = {10.1090/S0894-0347-2011-00725-X},
     }
  • [behrend] 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{behrend, mrkey = {0018694},
      issn = {0027-8424},
      author = {Behrend, F. A.},
      mrclass = {10.0X},
      journal = {Proc. Nat. Acad. Sci. U. S. A.},
      zblnumber = {0060.10302},
      volume = {32},
      mrnumber = {0018694},
      fjournal = {Proceedings of the National Academy of Sciences of the United States of America},
      mrreviewer = {P. Erd{ö}s},
      title = {On sets of integers which contain no three terms in arithmetical progression},
      year = {1946},
      pages = {331--332},
      }
  • [brownbuhler] Go to document T. C. Brown and J. P. Buhler, "A density version of a geometric Ramsey theorem," J. Combin. Theory, Ser. A, vol. 32, iss. 1, pp. 20-34, 1982.
    @ARTICLE{brownbuhler, zblnumber = {0476.51008},
      number = {1},
      volume = {32},
      author = {Brown, T. C. and Buhler, J. P.},
      title = {A density version of a geometric {R}amsey theorem},
      year = {1982},
      pages = {20--34},
      journal = {J. Combin. Theory, Ser. A},
      mrnumber = {0640624},
      doi = {10.1016/0097-3165(82)90062-0},
     }
  • [CLP] Go to document E. Croot, V. F. Lev, and P. P. Pach, "Progression-free sets in ${\mathbf{Z}}_4^n$ are exponentially small," Ann. of Math., vol. 185, pp. 000-000, 2017.
    @ARTICLE{CLP, volume = {185},
      author = {Croot, E. and Lev, V. F and Pach, P. P.},
      title = {Progression-free sets in ${\mathbf{Z}}_4^n$ are exponentially small},
      doi = {10.4007/annals.2017.185.1},
      pages = {000--000},
      year = {2017},
      journal = {Ann. of Math.},
      }
  • [edel] Go to document Y. Edel, "Extensions of generalized product caps," Des. Codes Cryptogr., vol. 31, iss. 1, pp. 5-14, 2004.
    @ARTICLE{edel, mrkey = {2031694},
      number = {1},
      issn = {0925-1022},
      author = {Edel, Yves},
      mrclass = {51E20 (05B25)},
      doi = {10.1023/A:1027365901231},
      journal = {Des. Codes Cryptogr.},
      zblnumber = {1057.51005},
      volume = {31},
      mrnumber = {2031694},
      fjournal = {Designs, Codes and Cryptography. An International Journal},
      mrreviewer = {Antonio Cossidente},
      coden = {DCCREC},
      title = {Extensions of generalized product caps},
      year = {2004},
      pages = {5--14},
      }
  • [meshulam] 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{meshulam, mrkey = {1335785},
      number = {1},
      issn = {0097-3165},
      author = {Meshulam, Roy},
      mrclass = {20D60 (05D10 11P99)},
      doi = {10.1016/0097-3165(95)90024-1},
      journal = {J. Combin. Theory Ser. A},
      zblnumber = {0832.11006},
      volume = {71},
      mrnumber = {1335785},
      fjournal = {Journal of Combinatorial Theory. Series A},
      coden = {JCBTA7},
      title = {On subsets of finite abelian groups with no {$3$}-term arithmetic progressions},
      year = {1995},
      pages = {168--172},
      }
  • [timo] F. Rassoul-Agha and T. Seppäläinen, A Course on Large Deviations with an Introduction to Gibbs Measures, Providence, RI: Amer. Math. Soc., 2015, vol. 162.
    @BOOK{timo, mrkey = {3309619},
      author = {Rassoul-Agha, Firas and Sepp{ä}l{ä}inen, Timo},
      mrclass = {60-01 (60F10 60J10 60K35 60K37 82B20)},
      series = {Grad. Stud. Math.},
      isbn = {978-0-8218-7578-0},
      address = {Providence, RI},
      publisher = {Amer. Math. Soc.},
      zblnumber = {1330.60001},
      volume = {162},
      mrnumber = {3309619},
      mrreviewer = {Jean-Ren{é} Chazottes},
      title = {A Course on Large Deviations with an Introduction to {G}ibbs Measures},
      year = {2015},
      pages = {xiv+318},
      }

Authors

Jordan S. Ellenberg

University of Wisconsin, Madison, WI

Dion Gijswijt

Delft University of Technology, Delft, The Netherlands