Progression-free sets in $\mathbb Z_4^n$ are exponentially small

Pages 331-337 from Volume 185 (2017), Issue 1 by Ernie Croot, Vsevolod F. Lev, Péter Pál Pach

Abstract

We show that for an integer $n\ge 1$, any subset $A\subseteq \mathbb{Z}_4^n$ free of three-term arithmetic progressions has size $|A|\le 4^{\gamma n}$, with an absolute constant $\gamma\approx 0.926$.

  • [b:bk] 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{b:bk, mrkey = {2869028},
      number = {2},
      issn = {0894-0347},
      author = {Bateman, Michael and Katz, Nets Hawk},
      mrclass = {11B30 (05D40 11B75)},
      doi = {10.1090/S0894-0347-2011-00725-X},
      journal = {J. Amer. Math. Soc.},
      zblnumber = {1262.11010},
      volume = {25},
      mrnumber = {2869028},
      fjournal = {Journal of the American Mathematical Society},
      mrreviewer = {Peter James Dukes},
      title = {New bounds on cap sets},
      year = {2012},
      pages = {585--613},
      }
  • [b:bl] Go to document T. F. Bloom, "A quantitative improvement for Roth’s theorem on arithmetic progressions," J. Lond. Math. Soc., vol. 93, iss. 3, pp. 643-663, 2016.
    @ARTICLE{b:bl, mrkey = {3509957},
      number = {3},
      issn = {0024-6107},
      author = {Bloom, T. F.},
      mrclass = {11B25 (11B30 11T55)},
      doi = {10.1112/jlms/jdw010},
      journal = {J. Lond. Math. Soc.},
      zblnumber = {06618266},
      volume = {93},
      mrnumber = {3509957},
      fjournal = {Journal of the London Mathematical Society. Second Series},
      title = {A quantitative improvement for {R}oth's theorem on arithmetic progressions},
      year = {2016},
      pages = {643--663},
      }
  • [b:b] Go to document J. Bourgain, "On triples in arithmetic progression," Geom. Funct. Anal., vol. 9, iss. 5, pp. 968-984, 1999.
    @ARTICLE{b:b, mrkey = {1726234},
      number = {5},
      issn = {1016-443X},
      author = {Bourgain, J.},
      mrclass = {11P55 (11B25 11N64)},
      doi = {10.1007/s000390050105},
      journal = {Geom. Funct. Anal.},
      zblnumber = {0959.11004},
      volume = {9},
      mrnumber = {1726234},
      fjournal = {Geometric and Functional Analysis},
      mrreviewer = {Serge{\u\i} V. Konyagin},
      coden = {GFANFB},
      title = {On triples in arithmetic progression},
      year = {1999},
      pages = {968--984},
      }
  • [b:bb] 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{b:bb, mrkey = {0640624},
      number = {1},
      issn = {0097-3165},
      author = {Brown, T. C. and Buhler, J. P.},
      mrclass = {05A17 (05C55 10L10)},
      doi = {10.1016/0097-3165(82)90062-0},
      journal = {J. Combin. Theory Ser. A},
      zblnumber = {0476.51008},
      volume = {32},
      mrnumber = {0640624},
      fjournal = {Journal of Combinatorial Theory. Series A},
      mrreviewer = {R. L. Graham},
      coden = {JCBTA7},
      title = {A density version of a geometric {R}amsey theorem},
      year = {1982},
      pages = {20--34},
      }
  • [b:fgr] Go to document P. Frankl, R. L. Graham, and V. Rödl, "On subsets of abelian groups with no $3$-term arithmetic progression," J. Combin. Theory Ser. A, vol. 45, iss. 1, pp. 157-161, 1987.
    @ARTICLE{b:fgr, mrkey = {0883900},
      number = {1},
      issn = {0097-3165},
      author = {Frankl, P. and Graham, R. L. and R{ö}dl, V.},
      mrclass = {05A99 (20D60 20K01)},
      doi = {10.1016/0097-3165(87)90053-7},
      journal = {J. Combin. Theory Ser. A},
      zblnumber = {0613.10043},
      volume = {45},
      mrnumber = {0883900},
      fjournal = {Journal of Combinatorial Theory. Series A},
      mrreviewer = {Joe P. Buhler},
      coden = {JCBTA7},
      title = {On subsets of abelian groups with no {$3$}-term arithmetic progression},
      year = {1987},
      pages = {157--161},
      }
  • [b:h] 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{b:h, mrkey = {0889362},
      number = {3},
      issn = {0024-6107},
      author = {Heath-Brown, D. R.},
      mrclass = {11B25 (11N35)},
      doi = {10.1112/jlms/s2-35.3.385},
      journal = {J. London Math. Soc.},
      zblnumber = {0589.10062},
      volume = {35},
      mrnumber = {0889362},
      fjournal = {Journal of the London Mathematical Society. Second Series},
      mrreviewer = {Andr{á}s S{á}rk{ö}zy},
      coden = {JLMSAK},
      title = {Integer sets containing no arithmetic progressions},
      year = {1987},
      pages = {385--394},
      }
  • [b:l1] Go to document V. F. Lev, "Progression-free sets in finite abelian groups," J. Number Theory, vol. 104, iss. 1, pp. 162-169, 2004.
    @ARTICLE{b:l1, mrkey = {2021632},
      number = {1},
      issn = {0022-314X},
      author = {Lev, Vsevolod F.},
      mrclass = {11B75 (20K01)},
      doi = {10.1016/S0022-314X(03)00148-3},
      journal = {J. Number Theory},
      zblnumber = {1043.11022},
      volume = {104},
      mrnumber = {2021632},
      fjournal = {Journal of Number Theory},
      mrreviewer = {David J. Grynkiewicz},
      coden = {JNUTA9},
      title = {Progression-free sets in finite abelian groups},
      year = {2004},
      pages = {162--169},
      }
  • [b:l2] Go to document V. F. Lev, "Character-free approach to progression-free sets," Finite Fields Appl., vol. 18, iss. 2, pp. 378-383, 2012.
    @ARTICLE{b:l2, mrkey = {2890558},
      number = {2},
      issn = {1071-5797},
      author = {Lev, Vsevolod F.},
      mrclass = {11B25 (11B75)},
      doi = {10.1016/j.ffa.2011.09.006},
      journal = {Finite Fields Appl.},
      zblnumber = {1284.11020},
      volume = {18},
      mrnumber = {2890558},
      fjournal = {Finite Fields and their Applications},
      mrreviewer = {Ben Joseph Green},
      title = {Character-free approach to progression-free sets},
      year = {2012},
      pages = {378--383},
      }
  • [b:mcwsl] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Amsterdam: North-Holland Publ. Co., 1977.
    @BOOK{b:mcwsl,
      author = {MacWilliams, F. J. and Sloane, N. J. A.},
      title = {The Theory of Error-Correcting Codes},
      publisher = {North-Holland Publ. Co.},
      address = {Amsterdam},
      year = {1977},
      zblnumber = {0369.94008},
      mrnumber = {0465509},
      }
  • [b:m] 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{b:m, 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},
      }
  • [b:r1] K. Roth, "Sur quelques ensembles d’entiers," C. R. Acad. Sci. Paris, vol. 234, pp. 388-390, 1952.
    @ARTICLE{b:r1, mrkey = {0046374},
      author = {Roth, Klaus},
      mrclass = {10.0X},
      journal = {C. R. Acad. Sci. Paris},
      zblnumber = {0046.04302},
      volume = {234},
      mrnumber = {0046374},
      mrreviewer = {P. Erd{ö}s},
      title = {Sur quelques ensembles d'entiers},
      year = {1952},
      pages = {388--390},
      }
  • [b:r2] Go to document K. Roth, "On certain sets of integers," J. London Math. Soc., vol. 28, pp. 104-109, 1953.
    @ARTICLE{b:r2, mrkey = {0051853},
      issn = {0024-6107},
      author = {Roth, Klaus},
      mrclass = {10.0X},
      doi = {10.1112/jlms/s1-28.1.104},
      journal = {J. London Math. Soc.},
      zblnumber = {0050.04002},
      volume = {28},
      mrnumber = {0051853},
      fjournal = {Journal of the London Mathematical Society. Second Series},
      mrreviewer = {P. Erd{ö}s},
      title = {On certain sets of integers},
      year = {1953},
      pages = {104--109},
      }
  • [b:s1] Go to document T. Sanders, "Roth’s theorem in $\Bbb Z^n_4$," Anal. PDE, vol. 2, iss. 2, pp. 211-234, 2009.
    @ARTICLE{b:s1, mrkey = {2560257},
      number = {2},
      issn = {1948-206X},
      author = {Sanders, Tom},
      mrclass = {11B30 (11B25)},
      doi = {10.2140/apde.2009.2.211},
      journal = {Anal. PDE},
      zblnumber = {1197.11017},
      volume = {2},
      mrnumber = {2560257},
      fjournal = {Analysis \& PDE},
      mrreviewer = {William A. Cherry},
      title = {Roth's theorem in {$\Bbb Z\sp n\sb 4$}},
      year = {2009},
      pages = {211--234},
      }
  • [b:s2] Go to document T. Sanders, "On certain other sets of integers," J. Anal. Math., vol. 116, pp. 53-82, 2012.
    @ARTICLE{b:s2, mrkey = {2892617},
      issn = {0021-7670},
      author = {Sanders, Tom},
      mrclass = {11B25 (11B05)},
      doi = {10.1007/s11854-012-0003-9},
      journal = {J. Anal. Math.},
      zblnumber = {1280.11009},
      volume = {116},
      mrnumber = {2892617},
      fjournal = {Journal d'Analyse Mathématique},
      mrreviewer = {Mei Chu Chang},
      coden = {JOAMAV},
      title = {On certain other sets of integers},
      year = {2012},
      pages = {53--82},
      }
  • [b:s3] Go to document T. Sanders, "On Roth’s theorem on progressions," Ann. of Math., vol. 174, iss. 1, pp. 619-636, 2011.
    @ARTICLE{b:s3, mrkey = {2811612},
      number = {1},
      issn = {0003-486X},
      author = {Sanders, Tom},
      mrclass = {11B25 (11B30)},
      doi = {10.4007/annals.2011.174.1.20},
      journal = {Ann. of Math.},
      zblnumber = {1264.11004},
      volume = {174},
      mrnumber = {2811612},
      fjournal = {Annals of Mathematics. Second Series},
      mrreviewer = {Julia Wolf},
      coden = {ANMAAH},
      title = {On {R}oth's theorem on progressions},
      year = {2011},
      pages = {619--636},
      }
  • [b:sz] 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{b:sz, mrkey = {1100788},
      number = {1-2},
      issn = {0236-5294},
      author = {Szemer{é}di, E.},
      mrclass = {11N64 (11B25 11P55)},
      doi = {10.1007/BF01903717},
      journal = {Acta Math. Hungar.},
      zblnumber = {0721.11007},
      volume = {56},
      mrnumber = {1100788},
      fjournal = {Acta Mathematica Hungarica},
      mrreviewer = {D. R. Heath-Brown},
      title = {Integer sets containing no arithmetic progressions},
      year = {1990},
      pages = {155--158},
      }

Keywords
, , ,
Mathematical Subject Classification
Primary: Secondary: , , , ,
DOI
https://doi.org/10.4007/annals.2017.185.1.7
MR
3583357
Zbl
06686589
Milestones
Received: 5 May 2016
Accepted: 8 September 2016
Published online: 2 December 2016

Authors

Ernie Croot

Georgia Institute of Technology, Atlanta, GA

Vsevolod F. Lev

The University of Haifa at Oranim, Tivon, Israel

Péter Pál Pach

Budapest University of Technology and Economics, Budapest, Hungary