New applications of the polynomial method: The cap set conjecture and beyond
HTML articles powered by AMS MathViewer
- by Joshua A. Grochow PDF
- Bull. Amer. Math. Soc. 56 (2019), 29-64
Abstract:
The cap set problem asks how large can a subset of $(\mathbb {Z}/3\mathbb {Z})^n$ be and contain no lines or, more generally, how can large a subset of $(\mathbb {Z}/p\mathbb {Z})^n$ be and contain no arithmetic progressions. This problem was motivated by deep questions about structure in the prime numbers, the geometry of lattice points, and the design of statistical experiments. In 2016, Croot, Lev, and Pach solved the analogous problem in $(\mathbb {Z}/4\mathbb {Z})^n$, showing that the largest set without arithmetic progressions had size at most $c^n$ for some $c < 4$. Their proof was as elegant as it was unexpected, being a departure from the tried and true methods of Fourier analysis that had dominated the field for half a century. Shortly thereafter, Ellenberg and Gijswijt leveraged their method to resolve the original cap set problem. This expository article covers the history and motivation for the cap set problem and some of the many applications of the technique: from removing triangles from graphs, to rigidity of matrices, and to algorithms for matrix multiplication. The latter application turns out to give back to the original problem, sharpening our understanding of the techniques involved and of what is needed for showing that the current bounds are tight. Most of our exposition assumes only familiarity with basic linear algebra, polynomials, and the integers modulo $N$.References
- J. Aaronson, A connection between matchings and removal in abelian groups, arXiv:1612.05172 [math.CO] (2016).
- Josh Alman and Virginia Vassilevska Williams, Further limitations of the known approaches for matrix multiplication, 9th Innovations in Theoretical Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 94, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, pp. Art. No. 25, 15. MR 3761761
- J. Alman and V. V. Williams, Limits on all known (and some unknown) approaches to matrix multiplication, FOCS ’18: 59th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 2018.
- Josh Alman and Ryan Williams, Probabilistic rank and matrix rigidity, STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2017, pp. 641–652. MR 3678217, DOI 10.1145/3055399.3055484
- N. Alon and M. Dubiner, Zero-sum sets of prescribed size, Combinatorics, Paul Erdős is eighty, Vol. 1, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 1993, pp. 33–50. MR 1249703
- Noga Alon and Moshe Dubiner, A lattice point problem and additive number theory, Combinatorica 15 (1995), no. 3, 301–309. MR 1357277, DOI 10.1007/BF01299737
- N. Alon, R. A. Duke, H. Lefmann, V. Rödl, and R. Yuster, The algorithmic aspects of the regularity lemma, J. Algorithms 16 (1994), no. 1, 80–109. MR 1251840, DOI 10.1006/jagm.1994.1005
- Noga Alon, Amir Shpilka, and Christopher Umans, On sunflowers and matrix multiplication, Comput. Complexity 22 (2013), no. 2, 219–243. MR 3055780, DOI 10.1007/s00037-013-0060-1
- Andris Ambainis, Yuval Filmus, and François Le Gall, Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract), STOC’15—Proceedings of the 2015 ACM Symposium on Theory of Computing, ACM, New York, 2015, pp. 585–593. MR 3388238
- L. Bary-Soroker, Prime tuples in function fields, Snapshots of modern mathematics from Oberwolfach 10 (2016). DOI 0.14760/SNAP-2016-010-EN.
- Michael Bateman and Nets Hawk Katz, New bounds on cap sets, J. Amer. Math. Soc. 25 (2012), no. 2, 585–613. MR 2869028, DOI 10.1090/S0894-0347-2011-00725-X
- F. A. Behrend, On sets of integers which contain no three terms in arithmetical progression, Proc. Nat. Acad. Sci. U.S.A. 32 (1946), 331–332. MR 18694, DOI 10.1073/pnas.32.12.331
- M. Bennett, Bounds on sizes of caps in $AG(n,q)$ via the Croot–Lev–Pach polynomial method, arXiv:1806.05303 [math.CO] (2018).
- Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, and Chris Umans, On cap sets and the group-theoretic approach to matrix multiplication, Discrete Anal. , posted on (2017), Paper No. 3, 27. MR 3631613, DOI 10.19086/da.1245
- J. Blasiak, T. Church, H. Cohn, J. A. Grochow, and C. Umans, Which groups are amenable to proving exponent two for matrix multiplication?, arXiv:1712.02302 [math.GR] (2017).
- T. F. Bloom, A quantitative improvement for Roth’s theorem on arithmetic progressions, J. Lond. Math. Soc. (2) 93 (2016), no. 3, 643–663. MR 3509957, DOI 10.1112/jlms/jdw010
- R. C. Bose, Mathematical theory of the symmetrical factorial design, Sankhyā 8 (1947), 107–166. MR 26781
- J. Bourgain, On triples in arithmetic progression, Geom. Funct. Anal. 9 (1999), no. 5, 968–984. MR 1726234, DOI 10.1007/s000390050105
- Jean Bourgain, Roth’s theorem on progressions revisited, J. Anal. Math. 104 (2008), 155–192. MR 2403433, DOI 10.1007/s11854-008-0020-x
- T. C. Brown and J. P. Buhler, A density version of a geometric Ramsey theorem, J. Combin. Theory Ser. A 32 (1982), no. 1, 20–34. MR 640624, DOI 10.1016/0097-3165(82)90062-0
- J. P. Buhler, H. W. Lenstra Jr., and Carl Pomerance, Factoring integers with the number field sieve, The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, Berlin, 1993, pp. 50–94. MR 1321221, DOI 10.1007/BFb0091539
- A. R. Calderbank and P. C. Fishburn, Maximal three-independent subsets of $\{0,1,2\}^n$, Des. Codes Cryptogr. 4 (1994), no. 3, 203–211. MR 1277940, DOI 10.1007/BF01388452
- S. Chowla, There exists an infinity of 3—combinations of primes in A. P, Proc. Lahore Philos. Soc. 6 (1944), no. 2, 15–16. MR 14125
- H. Cohn, R. Kleinberg, B. Szegedy, and C. Umans, Group-theoretic algorithms for matrix multiplication, FOCS ’05: 46th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 2005, arXiv:math/0511460 [math.GR], 379–388 (2005).
- H. Cohn and C. Umans, A group-theoretic approach to fast matrix multiplication, FOCS ’03: 44th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 2003, arXiv:math/0307321 [math.GR], 438–449 (2003).
- Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251–280. MR 1056627, DOI 10.1016/S0747-7171(08)80013-2
- Ernest S. Croot III and Vsevolod F. Lev, Open problems in additive combinatorics, Additive combinatorics, CRM Proc. Lecture Notes, vol. 43, Amer. Math. Soc., Providence, RI, 2007, pp. 207–233. MR 2359473, DOI 10.1090/crmp/043/10
- Ernie Croot, Vsevolod F. Lev, and Péter Pál Pach, Progression-free sets in $\Bbb Z^n_4$ are exponentially small, Ann. of Math. (2) 185 (2017), no. 1, 331–337. MR 3583357, DOI 10.4007/annals.2017.185.1.7
- Benjamin Lent Davis and Diane Maclagan, The card game SET, Math. Intelligencer 25 (2003), no. 3, 33–40. MR 2005098, DOI 10.1007/BF02984846
- M. S. Dousti and K. Ghasemloo, Answers to “Adding integers represented by their factorization is as hard as factoring?”, https://cstheory.stackexchange.com/q/7491/129 (2011).
- Zeev Dvir, On the size of Kakeya sets in finite fields, J. Amer. Math. Soc. 22 (2009), no. 4, 1093–1097. MR 2525780, DOI 10.1090/S0894-0347-08-00607-3
- Z. Dvir and B. Edelman, Matrix rigidity and the Croot–Lev–Pach lemma, arXiv:1708.01646 [cs.CC] (2017).
- Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan, Extensions to the method of multiplicities, with applications to Kakeya sets and mergers, SIAM J. Comput. 42 (2013), no. 6, 2305–2328. MR 3143848, DOI 10.1137/100783704
- Yves Edel, Extensions of generalized product caps, Des. Codes Cryptogr. 31 (2004), no. 1, 5–14. MR 2031694, DOI 10.1023/A:1027365901231
- Yves Edel and Jürgen Bierbrauer, Large caps in small spaces, Des. Codes Cryptogr. 23 (2001), no. 2, 197–212. MR 1830941, DOI 10.1023/A:1011216716700
- Y. Edel, S. Ferret, I. Landjev, and L. Storme, The classification of the largest caps in $\rm AG(5,3)$, J. Combin. Theory Ser. A 99 (2002), no. 1, 95–110. MR 1911459, DOI 10.1006/jcta.2002.3261
- Michael Elkin, An improved construction of progression-free sets, Israel J. Math. 184 (2011), 93–128. MR 2823971, DOI 10.1007/s11856-011-0061-1
- Jordan S. Ellenberg, Sumsets as unions of sumsets of subsets, Discrete Anal. , posted on (2017), Paper No. 14, 5. MR 3695477, DOI 10.19086/da.2103
- Jordan S. Ellenberg and Dion Gijswijt, On large subsets of $\Bbb F^n_q$ with no three-term arithmetic progression, Ann. of Math. (2) 185 (2017), no. 1, 339–343. MR 3583358, DOI 10.4007/annals.2017.185.1.8
- Paul Erdős, Résultats et problèmes en théorie des nombres, Séminaire Delange-Pisot-Poitou (14e année: 1972/73), Théorie des nombres, Fasc. 2, Exp. No. 24, Secrétariat Mathématique, Paris, 1973, pp. 7 (French). MR 0396376
- P. Erdős, Problems in number theory and combinatorics, Proceedings of the Sixth Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1976) Congress. Numer., XVIII, Utilitas Math., Winnipeg, Man., 1977, pp. 35–58. MR 532690
- P. Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), no. 1, 25–42. MR 602413, DOI 10.1007/BF02579174
- Paul Erdős, Some of my favorite problems and results, The mathematics of Paul Erdős, I, Algorithms Combin., vol. 13, Springer, Berlin, 1997, pp. 47–67. MR 1425174, DOI 10.1007/978-3-642-60408-9_{3}
- P. Erdős, P. Frankl, and V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin. 2 (1986), no. 2, 113–121. MR 932119, DOI 10.1007/BF01788085
- Paul Erdős and Carl Pomerance, On the largest prime factors of $n$ and $n+1$, Aequationes Math. 17 (1978), no. 2-3, 311–321. MR 480303, DOI 10.1007/BF01818569
- P. Erdős and R. Rado, Intersection theorems for systems of sets, J. London Math. Soc. 35 (1960), 85–90. MR 111692, DOI 10.1112/jlms/s1-35.1.85
- P. Erdős and E. Szemerédi, Combinatorial properties of systems of sets, J. Combinatorial Theory Ser. A 24 (1978), no. 3, 308–313. MR 491202, DOI 10.1016/0097-3165(78)90060-2
- Paul Erdös and Paul Turán, On Some Sequences of Integers, J. London Math. Soc. 11 (1936), no. 4, 261–264. MR 1574918, DOI 10.1112/jlms/s1-11.4.261
- Jacob Fox, A new proof of the graph removal lemma, Ann. of Math. (2) 174 (2011), no. 1, 561–579. MR 2811609, DOI 10.4007/annals.2011.174.1.17
- Jacob Fox and László Miklós Lovász, A tight bound for Green’s arithmetic triangle removal lemma in vector spaces, Adv. Math. 321 (2017), 287–297. MR 3715712, DOI 10.1016/j.aim.2017.09.037
- Jacob Fox and Lisa Sauermann, Erdős-Ginzburg-Ziv constants by avoiding three-term arithmetic progressions, Electron. J. Combin. 25 (2018), no. 2, Paper No. 2.14, 9. MR 3799432, DOI 10.37236/7275
- 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 45 (1987), no. 1, 157–161. MR 883900, DOI 10.1016/0097-3165(87)90053-7
- G. A. Freĭman, Foundations of a structural theory of set addition, Translations of Mathematical Monographs, Vol 37, American Mathematical Society, Providence, R.I., 1973. Translated from the Russian. MR 0360496
- Joel Friedman, A note on matrix rigidity, Combinatorica 13 (1993), no. 2, 235–239. MR 1237045, DOI 10.1007/BF01303207
- Zoltán Füredi, Extremal hypergraphs and combinatorial geometry, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994) Birkhäuser, Basel, 1995, pp. 1343–1352. MR 1404036, DOI 10.1007/978-3-0348-9078-6_{6}5
- P. X. Gallagher, On the distribution of primes in short intervals, Mathematika 23 (1976), no. 1, 4–9. MR 409385, DOI 10.1112/S0025579300016442
- G. Ge and C. Shangguan, Rank counting and maximum subsets of $\mathbb {F}_q^n$ containing no right angles, arXiv:1612.08255 [math.CO] (2016).
- Fulvio Gesmundo, Jonathan D. Hauenstein, Christian Ikenmeyer, and J. M. Landsberg, Complexity of linear circuits and geometry, Found. Comput. Math. 16 (2016), no. 3, 599–635. MR 3494506, DOI 10.1007/s10208-015-9258-8
- W. T. Gowers, A new proof of Szemerédi’s theorem for arithmetic progressions of length four, Geom. Funct. Anal. 8 (1998), no. 3, 529–551. MR 1631259, DOI 10.1007/s000390050065
- W. T. Gowers, A new proof of Szemerédi’s theorem, Geom. Funct. Anal. 11 (2001), no. 3, 465–588. MR 1844079, DOI 10.1007/s00039-001-0332-9
- W. T. Gowers, What is difficult about the cap-set problem?, Gowers’s Weblog, https://gowers.wordpress.com/2011/01/11/what-is-difficult-about-the-cap-set-problem, (2011).
- W. Timothy Gowers, Erdős and arithmetic progressions, Erdös centennial, Bolyai Soc. Math. Stud., vol. 25, János Bolyai Math. Soc., Budapest, 2013, pp. 265–287. MR 3203599, DOI 10.1007/978-3-642-39286-3_{8}
- W. T. Gowers, Reflections on the recent solution of the cap-set problem I, Gowers’s Weblog, https://gowers.wordpress.com/2016/05/19/reflections-on-the-recent-solution-of-the-cap-set-problem-i/ (2016).
- Ben Green, Finite field models in additive combinatorics, Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge Univ. Press, Cambridge, 2005, pp. 1–27. MR 2187732, DOI 10.1017/CBO9780511734885.002
- Ben Green, Roth’s theorem in the primes, Ann. of Math. (2) 161 (2005), no. 3, 1609–1636. MR 2180408, DOI 10.4007/annals.2005.161.1609
- B. Green, A Szemerédi-type regularity lemma in abelian groups, with applications, Geom. Funct. Anal. 15 (2005), no. 2, 340–376. MR 2153903, DOI 10.1007/s00039-005-0509-8
- Ben Green, Sárközy’s theorem in function fields, Q. J. Math. 68 (2017), no. 1, 237–242. MR 3658291, DOI 10.1093/qmath/haw044
- Ben Green and Terence Tao, The primes contain arbitrarily long arithmetic progressions, Ann. of Math. (2) 167 (2008), no. 2, 481–547. MR 2415379, DOI 10.4007/annals.2008.167.481
- Ben Green, Terence Tao, and Tamar Ziegler, An inverse theorem for the Gowers $U^{s+1}[N]$-norm, Ann. of Math. (2) 176 (2012), no. 2, 1231–1372. MR 2950773, DOI 10.4007/annals.2012.176.2.11
- Ben Green and Julia Wolf, A note on Elkin’s improvement of Behrend’s construction, Additive number theory, Springer, New York, 2010, pp. 141–144. MR 2744752, DOI 10.1007/978-0-387-68361-4_{9}
- David J. Grynkiewicz, Structural additive theory, Developments in Mathematics, vol. 30, Springer, Cham, 2013. MR 3097619, DOI 10.1007/978-3-319-00416-7
- Richard K. Guy, Unsolved problems in number theory, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR 2076335, DOI 10.1007/978-0-387-26677-0
- Heiko Harborth, Ein Extremalproblem für Gitterpunkte, J. Reine Angew. Math. 262(263) (1973), 356–360 (German). MR 327666, DOI 10.1515/crll.1973.262-263.356
- D. R. Heath-Brown, Integer sets containing no arithmetic progressions, J. London Math. Soc. (2) 35 (1987), no. 3, 385–394. MR 889362, DOI 10.1112/jlms/s2-35.3.385
- Harald Andrés Helfgott and Anne de Roton, Improving Roth’s theorem in the primes, Int. Math. Res. Not. IMRN 4 (2011), 767–783. MR 2773330, DOI 10.1093/imrn/rnq108
- Stasys Jukna, Extremal combinatorics, 2nd ed., Texts in Theoretical Computer Science. An EATCS Series, Springer, Heidelberg, 2011. With applications in computer science. MR 2865719, DOI 10.1007/978-3-642-17364-6
- B. S. Kashin and A. A. Razborov, New lower bounds for the stability of Hadamard matrices, Mat. Zametki 63 (1998), no. 4, 535–540 (Russian, with Russian summary); English transl., Math. Notes 63 (1998), no. 3-4, 471–475. MR 1680943, DOI 10.1007/BF02311250
- T. Kim and S. Oum, An upper bound on tricolored ordered sum-free sets, arXiv:1708.07263 [math.CO] (2017).
- R. Kleinberg, W. F. Sawin, and D. E. Speyer, The growth rate of tri-colored sum-free sets, Discrete Anal. (2018), Paper No. 12.
- Sergei V. Konyagin and Vsevolod F. Lev, Combinatorics and linear algebra of Freiman’s isomorphism, Mathematika 47 (2000), no. 1-2, 39–51 (2002). MR 1924486, DOI 10.1112/S0025579300015709
- Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, and M. N. Jayalal Sarma, Using elimination theory to construct rigid matrices, Comput. Complexity 23 (2014), no. 4, 531–563. MR 3274825, DOI 10.1007/s00037-013-0061-0
- G. Kuperberg, Answer to question “Open problems with monetary rewards” on MathOverflow, https://mathoverflow.net/a/66219/38434 (2011).
- Jeffrey C. Lagarias, The $3x+1$ problem: an annotated bibliography (1963–1999), The ultimate challenge: the $3x+1$ problem, Amer. Math. Soc., Providence, RI, 2010, pp. 267–341. MR 2560718, DOI 10.1126/science.328.5979.689
- J. M. Landsberg, Geometry and the complexity of matrix multiplication, Bull. Amer. Math. Soc. (N.S.) 45 (2008), no. 2, 247–284. MR 2383305, DOI 10.1090/S0273-0979-08-01176-2
- J. M. Landsberg, New lower bounds for the rank of matrix multiplication, SIAM J. Comput. 43 (2014), no. 1, 144–149. MR 3162411, DOI 10.1137/120880276
- François Le Gall, Powers of tensors and fast matrix multiplication, ISSAC 2014—Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2014, pp. 296–303. MR 3239939, DOI 10.1145/2608628.2608664
- Arjen K. Lenstra, Integer factoring, Des. Codes Cryptogr. 19 (2000), no. 2-3, 101–128. Towards a quarter-century of public key cryptography. MR 1758972, DOI 10.1023/A:1008397921377
- H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
- Vsevolod F. Lev, Progression-free sets in finite abelian groups, J. Number Theory 104 (2004), no. 1, 162–169. MR 2021632, DOI 10.1016/S0022-314X(03)00148-3
- Vsevolod F. Lev, Character-free approach to progression-free sets, Finite Fields Appl. 18 (2012), no. 2, 378–383. MR 2890558, DOI 10.1016/j.ffa.2011.09.006
- Satyanarayana V. Lokam, On the rigidity of Vandermonde matrices, Theoret. Comput. Sci. 237 (2000), no. 1-2, 477–483. MR 1756225, DOI 10.1016/S0304-3975(00)00008-6
- Satyanarayana V. Lokam, Quadratic lower bounds on matrix rigidity, Theory and applications of models of computation, Lecture Notes in Comput. Sci., vol. 3959, Springer, Berlin, 2006, pp. 295–307. MR 2277251, DOI 10.1007/11750321_{2}8
- Satyanarayana V. Lokam, Complexity lower bounds using linear algebra, Found. Trends Theor. Comput. Sci. 4 (2008), no. 1-2, front matter, 1–155 (2009). MR 2539154, DOI 10.1561/0300000020
- L. M. Lovász and Lisa Sauermann, A lower bound for the $k$-multicored sum-free problem in $\mathbb {Z}_m^n$, arXiv:1804.08837 [math.CO] (2018).
- James Maynard, Small gaps between primes, Ann. of Math. (2) 181 (2015), no. 1, 383–413. MR 3272929, DOI 10.4007/annals.2015.181.1.7
- Liz McMahon, Gary Gordon, Hannah Gordon, and Rebecca Gordon, The joy of SET, Princeton University Press, Princeton, NJ; National Museum of Mathematics, New York, 2017. The many mathematical dimensions of a seemingly simple card game. MR 3559496, DOI 10.1515/9781400884483
- Roy Meshulam, On subsets of finite abelian groups with no $3$-term arithmetic progressions, J. Combin. Theory Ser. A 71 (1995), no. 1, 168–172. MR 1335785, DOI 10.1016/0097-3165(95)90024-1
- Pascal Michel, Busy beaver competition and Collatz-like problems, Arch. Math. Logic 32 (1993), no. 5, 351–367. MR 1223396, DOI 10.1007/BF01409968
- Michael A. Morrison and John Brillhart, A method of factoring and the factorization of $F_{7}$, Math. Comp. 29 (1975), 183–205. MR 371800, DOI 10.1090/S0025-5718-1975-0371800-5
- G. Muller, Answer to “What is the importance of the Collatz conjecture?”, https://math. stackexchange.com/a/10608/224688 (2010).
- S. Norin, A distribution on triples with maximum entropy marginal, arXiv:1608.00243 [math.CO] (2016).
- L. Pebody, Proof of a conjecture of Kleinberg–Sawin–Speyer, Discrete Anal. (2018), Paper No. 13.
- Giuseppe Pellegrino, Sul massimo ordine delle calotte in $S_{4,3}$, Matematiche (Catania) 25 (1970), 149–157 (1971) (Italian). MR 363952
- D. H. J. Polymath, Variants of the Selberg sieve, and bounded intervals containing many primes, Res. Math. Sci. 1 (2014), Art. 12, 83. MR 3373710, DOI 10.1186/s40687-014-0012-7
- C. Pomerance, Analysis and comparison of some integer factoring algorithms, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 89–139. MR 700260
- Aaron Potechin, Maximal caps in $\textrm {AG}(6,3)$, Des. Codes Cryptogr. 46 (2008), no. 3, 243–259. MR 2372838, DOI 10.1007/s10623-007-9132-z
- Hans Riesel, Prime numbers and computer methods for factorization, 2nd ed., Progress in Mathematics, vol. 126, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1292250, DOI 10.1007/978-1-4612-0251-6
- K. F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104–109. MR 51853, DOI 10.1112/jlms/s1-28.1.104
- I. Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976) Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam-New York, 1978, pp. 939–945. MR 519318
- 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. 28 (1942), 561–563. MR 7405, DOI 10.1073/pnas.28.12.561
- Tom Sanders, Roth’s theorem in $\Bbb Z^n_4$, Anal. PDE 2 (2009), no. 2, 211–234. MR 2560257, DOI 10.2140/apde.2009.2.211
- Tom Sanders, On Roth’s theorem on progressions, Ann. of Math. (2) 174 (2011), no. 1, 619–636. MR 2811612, DOI 10.4007/annals.2011.174.1.20
- Tom Sanders, On certain other sets of integers, J. Anal. Math. 116 (2012), 53–82. MR 2892617, DOI 10.1007/s11854-012-0003-9
- W. F. Sawin, Bounds for matchings in nonabelian groups, arXiv:1702.00905 [math.CO] (2017).
- Tomasz Schoen and Ilya D. Shkredov, Roth’s theorem in many variables, Israel J. Math. 199 (2014), no. 1, 287–308. MR 3219538, DOI 10.1007/s11856-013-0049-0
- Tomasz Schoen and Olof Sisask, Roth’s theorem for four variables and additive structures in sums of sparse sets, Forum Math. Sigma 4 (2016), Paper No. e5, 28. MR 3482282, DOI 10.1017/fms.2016.2
- Beniamino Segre, Le geometrie di Galois, Ann. Mat. Pura Appl. (4) 48 (1959), 1–96 (Italian). MR 116259, DOI 10.1007/BF02410658
- Beniamino Segre, Introduction to Galois geometries, Atti Accad. Naz. Lincei Mem. Cl. Sci. Fis. Mat. Natur. Sez. Ia (8) 8 (1967), 133–236 (English, with Italian summary). MR 238846
- Set Enterprises, Inc., Marsha Jean Falco—the creative genius behind SET®, https://puzzles.setgame.com/set/history.htm.
- M. A. Shokrollahi, D. A. Spielman, and V. Stemann, A remark on matrix rigidity, Inform. Process. Lett. 64 (1997), no. 6, 283–285. MR 1608240, DOI 10.1016/S0020-0190(97)00190-7
- Peter W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26 (1997), no. 5, 1484–1509. MR 1471990, DOI 10.1137/S0097539795293172
- Alexander Soifer, The mathematical coloring book, Springer, New York, 2009. Mathematics of coloring and the colorful life of its creators; With forewords by Branko Grünbaum, Peter D. Johnson, Jr. and Cecil Rousseau. MR 2458293, DOI 10.1007/978-0-387-74642-5
- A. Stothers, On the complexity of matrix multiplication, Ph.D. thesis, University of Edinburgh, Edinburgh, UK (2010).
- Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354–356. MR 248973, DOI 10.1007/BF02165411
- E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hungar. 20 (1969), 89–104. MR 245555, DOI 10.1007/BF01894569
- E. Szemerédi, On sets of integers containing no $k$ elements in arithmetic progression, Acta Arith. 27 (1975), 199–245. MR 369312, DOI 10.4064/aa-27-1-199-245
- E. Szemerédi, Integer sets containing no arithmetic progressions, Acta Math. Hungar. 56 (1990), no. 1-2, 155–158. MR 1100788, DOI 10.1007/BF01903717
- T. Tao, Open question: best bounds for cap sets, What’s new, https://terrytao.wordpress. com/2007/02/23/open-question-best-bounds-for-cap-sets/ (2007).
- Terence Tao, Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory, EMS Surv. Math. Sci. 1 (2014), no. 1, 1–46. MR 3200226, DOI 10.4171/EMSS/1
- T. Tao, A symmetric formulation of the Croot–Lev–Pach–Ellenberg–Gijswijt capset bound, What’s new, https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation- of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound/ (2016).
- T. Tao and W. F. Sawin, Notes on the “slice rank” of tensors, What’s new, https:// terrytao.wordpress.com/2016/08/24/notes-on-the-slice-rank-of-tensors/ (2016).
- Terence Tao and Van Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012, DOI 10.1017/CBO9780511755149
- Leslie G. Valiant, Graph-theoretic arguments in low-level complexity, Mathematical foundations of computer science (Proc. Sixth Sympos., Tatranská Lomnica, 1977) Lecture Notes in Comput. Sci., Vol. 53, Springer, Berlin, 1977, pp. 162–176. MR 0660702
- J. G. van der Corput, Über Summen von Primzahlen und Primzahlquadraten, Math. Ann. 116 (1939), no. 1, 1–50 (German). MR 1513216, DOI 10.1007/BF01597346
- Virginia Vassilevska Williams, Multiplying matrices faster than Coppersmith-Winograd [extended abstract], STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 887–898. MR 2961552, DOI 10.1145/2213977.2214056
- Samuel S. Wagstaff Jr., The joy of factoring, Student Mathematical Library, vol. 68, American Mathematical Society, Providence, RI, 2013. MR 3135977, DOI 10.1090/stml/068
- J. Wolf, Finite field models in arithmetic combinatorics—ten years on, Finite Fields Appl. 32 (2015), 233–274. MR 3293412, DOI 10.1016/j.ffa.2014.11.003
- D. Zeilberger, A motivated rendition of the Ellenberg–Gijswijt gorgeous proof that the largest subset of $F_3^n$ with no three-term arithmetic progression is $O(c^n)$, with $c = \sqrt [3]{(5589 + 891\sqrt {33}}/8 = 2.75510461302363300022127\dotsc$, arXiv:1607.01804 [math.CO] (2016).
- Yitang Zhang, Bounded gaps between primes, Ann. of Math. (2) 179 (2014), no. 3, 1121–1174. MR 3171761, DOI 10.4007/annals.2014.179.3.7
Additional Information
- Joshua A. Grochow
- Affiliation: Department of Computer Science and Department of Mathematics, University of Colorado Boulder, Boulder, Colorado
- MR Author ID: 930146
- Email: jgrochow@colorado.edu
- Received by editor(s): April 22, 2018
- Published electronically: October 1, 2018
- © Copyright 2018 Joshua A. Grochow
- Journal: Bull. Amer. Math. Soc. 56 (2019), 29-64
- MSC (2010): Primary 11B25, 51E22
- DOI: https://doi.org/10.1090/bull/1648
- MathSciNet review: 3886143