New applications of the polynomial method: The cap set conjecture and beyond
Open accessAbstract
The cap set problem asks how large can a subset of ( Z / 3 Z ) n be and contain no lines or, more generally, how can large a subset of ( Z / p 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 ( Z / 4 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 .
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472 · see citing works
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904 · see citing works
Gaussian elimination is not optimal
Strassen, V. (1969) · Numerische Mathematik · doi:10.1007/bf02165411 · Cited by 2,509 · see citing works
Matrix multiplication via arithmetic progressions
Coppersmith, D., & Winograd, S. (1990) · Journal of Symbolic Computation · doi:10.1016/s0747-7171(08)80013-2 · Cited by 2,248 · see citing works
Unsolved Problems in Number Theory
Guy, R. K. (1994) · Problem books in mathematics · doi:10.1007/978-1-4899-3585-4 · Cited by 1,208 · see citing works
Factoring Integers with Elliptic Curves
Lenstra, H. W. (1987) · Annals of Mathematics · doi:10.2307/1971363 · Cited by 995 · see citing works
Multiplying matrices faster than coppersmith-winograd
Williams, V. V. (2012) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2213977.2214056 · Cited by 853 · see citing works
Powers of tensors and fast matrix multiplication
Gall, F. L. (2014) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/2608628.2608664 · Cited by 843 · see citing works
A new proof of Szemerédi's theorem
Gowers, W. T. (2001) · Geometric and Functional Analysis · doi:10.1007/s00039-001-0332-9 · Cited by 834 · see citing works
The primes contain arbitrarily long arithmetic progressions
Green, B., & Tao, T. (2008) · Annals of Mathematics · doi:10.4007/annals.2008.167.481 · Cited by 825 · see citing works
Tao, T., & Vu, V. H. (2006) · doi:10.1017/cbo9780511755149 · Cited by 816 · see citing works
On sets of integers containing k elements in arithmetic progression
Szemerédi, E. (1975) · Acta Arithmetica · doi:10.4064/aa-27-1-199-245 · Cited by 812 · see citing works
Intersection Theorems for Systems of Sets
Erdös, P., & Rado, R. (1960) · Journal of the London Mathematical Society · doi:10.1112/jlms/s1-35.1.85 · Cited by 643 · see citing works
Roth, K. F. (1953) · Journal of the London Mathematical Society · doi:10.1112/jlms/s1-28.1.104 · Cited by 620 · see citing works
Yitang, Z. (2014) · Annals of Mathematics · doi:10.4007/annals.2014.179.3.7 · Cited by 461 · see citing works
A New Proof of Szemer�di's Theorem for Arithmetic Progressions of Length Four
Gowers, W. T. (1998) · Geometric and Functional Analysis · doi:10.1007/s000390050065 · Cited by 457 · see citing works
On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
Behrend, F. A. (1946) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.32.12.331 · Cited by 424 · see citing works
Prime Numbers and Computer Methods for Factorization
Riesel, H. (1985) · Birkhäuser Boston eBooks · doi:10.1007/978-1-4757-1089-2 · Cited by 385 · see citing works
Foundations of a Structural Theory of Set Addition
Freiman, G. A. (2007) · Translations of mathematical monographs · doi:10.1090/mmono/037 · Cited by 361 · see citing works
On the combinatorial problems which I would most like to see solved
Erdös, P. (1981) · COMBINATORICA · doi:10.1007/bf02579174 · Cited by 321 · see citing works
Erdos, P. L., & Túrán, P. (1936) · Journal of the London Mathematical Society · doi:10.1112/jlms/s1-11.4.261 · Cited by 320 · see citing works
Unsolved Problems in Number Theory
Guy, R. K. (2004) · Problem books in mathematics · doi:10.1007/978-0-387-26677-0 · Cited by 317 · see citing works
Graph-theoretic arguments in low-level complexity
Valiant, L. G. (1977) · Lecture notes in computer science · doi:10.1007/3-540-08353-7_135 · Cited by 314 · see citing works
Maynard, J. (2014) · Annals of Mathematics · doi:10.4007/annals.2015.181.1.7 · Cited by 311 · see citing works
The Algorithmic Aspects of the Regularity Lemma
Alon, N., Duke, R. A., Lefmann, H., Rödl, V., & Yuster, R. (1994) · Journal of Algorithms · doi:10.1006/jagm.1994.1005 · Cited by 294 · see citing works
Erdős, P. L., Frankl, P., & Rödl, V. (1986) · Graphs and Combinatorics · doi:10.1007/bf01788085 · Cited by 282 · see citing works
On Triples in Arithmetic Progression
Bourgain, J. (1999) · Geometric and Functional Analysis · doi:10.1007/s000390050105 · Cited by 267 · see citing works
The Mathematical Coloring Book
Soifer, A. (2008) · Springer eBooks · doi:10.1007/978-0-387-74642-5 · Cited by 237 · see citing works
On the size of Kakeya sets in finite fields
Dvir, Z. (2008) · Journal of the American Mathematical Society · doi:10.1090/s0894-0347-08-00607-3 · Cited by 210 · see citing works
Group-theoretic Algorithms for Matrix Multiplication
Cohn, H., Kleinberg, R., Szegedy, B., & Umans, C. (2005) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2005.39 · Cited by 197 · see citing works
Climate Change and the Integrity of Science
Gleick, P. H., Adams, R. M., Amasino, R. M., Anders, E., Anderson, D. J., Anderson, W. W., Anselin, L., Arroyo, M. K., Asfaw, B., Ayala, F. J., et al. (2010) · Science · doi:10.1126/science.328.5979.689 · Cited by 192 · see citing works
A Szemerédi-type regularity lemma in abelian groups, with applications
Green, B. (2005) · Geometric and Functional Analysis · doi:10.1007/s00039-005-0509-8 · Cited by 191 · see citing works
Factoring integers with the number field sieve
Buhler, J. P., Lenstra, H. W., & Pomerance, C. (1993) · Lecture Notes in Mathematics · doi:10.1007/bfb0091539 · Cited by 188 · see citing works
Defining and Measuring Entrepreneurship
Iversen, J., Jørgensen, R. L., & Malchow‐Møller, N. (2007) · Foundations and Trends® in Entrepreneurship · doi:10.1561/0300000020 · Cited by 179 · see citing works
Grynkiewicz, D. J. (2013) · Developments in mathematics · doi:10.1007/978-3-319-00416-7 · Cited by 175 · see citing works
On the distribution of primes in short intervals
Gallagher, P. X. (1976) · Mathematika · doi:10.1112/s0025579300016442 · Cited by 175 · see citing works
A method of factoring and the factorization of 𝐹₇
Morrison, M. A., & Brillhart, J. D. (1975) · Mathematics of Computation · doi:10.1090/s0025-5718-1975-0371800-5 · Cited by 170 · see citing works
Integer Sets Containing No Arithmetic Progressions
Heath-Brown, D. R. (1987) · Journal of the London Mathematical Society · doi:10.1112/jlms/s2-35.3.385 · Cited by 168 · see citing works
On the complexity of matrix multiplication
Stothers, A. J. (2010) · ERA · Cited by 167 · see citing works
A new proof of the graph removal lemma
Fox, J. (2011) · Annals of Mathematics · doi:10.4007/annals.2011.174.1.17 · Cited by 167 · see citing works
Green, B. (2005) · Annals of Mathematics · doi:10.4007/annals.2005.161.1609 · Cited by 165 · see citing works
Jukna, S. P. (2011) · Texts in theoretical computer science · doi:10.1007/978-3-642-17364-6 · Cited by 163 · see citing works
On sets of integers containing no four elements in arithmetic progression
Szemerédi, E. (1969) · Acta Mathematica Academiae Scientiarum Hungaricae · doi:10.1007/bf01894569 · Cited by 159 · see citing works
On Roth’s Theorem on ProgressionsPreprint
Sanders, T. (2011) · Cited by 158 · see citing works
Variants of the Selberg sieve, and bounded intervals containing many primes
Polymath, D. (2014) · Research in the Mathematical Sciences · doi:10.1186/s40687-014-0012-7 · Cited by 153 · see citing works
An inverse theorem for the Gowers U^(s+1)[N]-norm
Green, B., Tao, T., & Ziegler, T. (2012) · Annals of Mathematics · doi:10.4007/annals.2012.176.2.11 · Cited by 153 · see citing works
Prime Numbers and Computer Methods for Factorization
Riesel, H. (1994) · Birkhäuser Boston eBooks · doi:10.1007/978-1-4612-0251-6 · Cited by 152 · see citing works
On large subsets of $\mathbb{F}_q^n$ with no three-term arithmetic progression
Ellenberg, J., & Gijswijt, D. (2017) · Annals of Mathematics · doi:10.4007/annals.2017.185.1.8 · Cited by 146 · see citing works
On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
Salem, R., & Spencer, D. C. (1942) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.28.12.561 · Cited by 135 · see citing works
Segre, B. (1959) · Annali di Matematica Pura ed Applicata (1923 -) · doi:10.1007/bf02410658 · Cited by 129 · see citing works
On subsets of finite abelian groups with no 3-term arithmetic progressions
Meshulam, R. (1995) · Journal of Combinatorial Theory Series A · doi:10.1016/0097-3165(95)90024-1 · Cited by 129 · see citing works
Integer sets containing no arithmetic progressions
Szemerédi, E. (1990) · Acta Mathematica Academiae Scientiarum Hungaricae · doi:10.1007/bf01903717 · Cited by 123 · see citing works
Progression-free sets in $\mathbb{Z}_4^n$ are exponentially small
Croot, E., Lev, V. F., & Pach, P. P. (2016) · Annals of Mathematics · doi:10.4007/annals.2017.185.1.7 · Cited by 112 · see citing works
A Szemeredi-type regularity lemma in abelian groups, with applications
Green, B. (2003) · Bristol Research (University of Bristol) · doi:10.48550/arxiv.math/0310476 · Cited by 111 · see citing works
Roth’s theorem on progressions revisited
Bourgain, J. (2008) · Journal d Analyse Mathématique · doi:10.1007/s11854-008-0020-x · Cited by 110 · see citing works
A Group-theoretic Approach to Fast Matrix MultiplicationPreprint
Cohn, H., & Umans, C. (2003) · Cited by 105 · see citing works
Finite field models in additive combinatorics
Green, B. (2005) · Cambridge University Press eBooks · doi:10.1017/cbo9780511734885.002 · Cited by 102 · see citing works
A Method of Factoring and the Factorization of F 7
Morrison, M. A., & Brillhart, J. D. (1975) · Mathematics of Computation · doi:10.2307/2005475 · Cited by 99 · see citing works
An improved construction of progression-free sets
Elkin, M. (2011) · Israel Journal of Mathematics · doi:10.1007/s11856-011-0061-1 · Cited by 94 · see citing works
On Roth's theorem on progressions
Sanders, T. (2011) · Annals of Mathematics · doi:10.4007/annals.2011.174.1.20 · Cited by 93 · see citing works
Complexity Lower Bounds using Linear Algebra
Lokam, S. V. (2009) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000011 · Cited by 92 · see citing works
On cap sets and the group-theoretic approach to matrix multiplication
Blasiak, J., Church, T., Cohn, H., Grochow, J. A., Naslund, E., Sawin, W. F., & Umans, C. (2017) · Discrete Analysis · doi:10.19086/da.1245 · Cited by 89 · see citing works
Self-citationExtensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
Dvir, Z., Kopparty, S., Saraf, S., & Sudan, M. (2009) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2009.40 · Cited by 85 · see citing works
Über Summen von Primzahlen und Primzahlquadraten
van der Corput, J. G. (1939) · Mathematische Annalen · doi:10.1007/bf01597346 · Cited by 78 · see citing works
Lenstra, A. K. (2000) · Designs Codes and Cryptography · doi:10.1023/a:1008397921377 · Cited by 77 · see citing works
A lattice point problem and additive number theory
Alon, N., & Dubiner, M. (1995) · COMBINATORICA · doi:10.1007/bf01299737 · Cited by 75 · see citing works
Extensions of Generalized Product Caps
Edel, Y. (2004) · Designs, Codes and Cryptography · doi:10.1023/a:1027365901231 · Cited by 72 · see citing works
Friedman, J. (1993) · COMBINATORICA · doi:10.1007/bf01303207 · Cited by 72 · see citing works
A quantitative improvement for Roth's theorem on arithmetic progressions: Table 1.
Bloom, T. F. (2016) · Journal of the London Mathematical Society · doi:10.1112/jlms/jdw010 · Cited by 66 · see citing works
On subsets of abelian groups with no 3-term arithmetic progression
Frankl, P., Graham, R., & Rödl, V. (1987) · Journal of Combinatorial Theory Series A · doi:10.1016/0097-3165(87)90053-7 · Cited by 66 · see citing works
Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
Dvir, Z., Kopparty, S., Saraf, S., & Sudan, M. (2013) · SIAM Journal on Computing · doi:10.1137/100783704 · Cited by 65 · see citing works
On Sunflowers and Matrix Multiplication
Alon, N., Shpilka, A., & Umans, C. (2012) · Computational Complexity · doi:10.1007/s00037-013-0060-1 · Cited by 62 · see citing works
Geometry and the complexity of matrix multiplication
Landsberg, J. M. (2008) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-08-01176-2 · Cited by 62 · see citing works
Ein Extremalproblem für Gitterpunkte.
Harborth, H. (1973) · Journal für die reine und angewandte Mathematik (Crelles Journal) · doi:10.1515/crll.1973.262-263.356 · Cited by 61 · see citing works
A Note on Elkin’s Improvement of Behrend’s Construction
Green, B., & Wolf, J. (2010) · Springer eBooks · doi:10.1007/978-0-387-68361-4_9 · Cited by 61 · see citing works
A density version of a geometric ramsey theorem
Brown, T. C., & Buhler, J. (1982) · Journal of Combinatorial Theory Series A · doi:10.1016/0097-3165(82)90062-0 · Cited by 59 · see citing works
Shokrollahi, M. A., Spielman, D. A., & Stemann, V. (1997) · Information Processing Letters · doi:10.1016/s0020-0190(97)00190-7 · Cited by 59 · see citing works
Davis, B. L., & Maclagan, D. (2003) · The Mathematical Intelligencer · doi:10.1007/bf02984846 · Cited by 58 · see citing works
Combinatorial properties of systems of sets
Erdös, P., & Szemerédi, E. (1978) · Journal of Combinatorial Theory Series A · doi:10.1016/0097-3165(78)90060-2 · Cited by 54 · see citing works
Open problems in additive combinatorics
Croot, E. S., & Lev, V. F. (2007) · CRM proceedings & lecture notes · doi:10.1090/crmp/043/10 · Cited by 51 · see citing works
Probabilistic rank and matrix rigidity
Alman, J., & Williams, R. (2017) · ACM SIGACT Symposium on Theory of Computing (STOC) · doi:10.1145/3055399.3055484 · Cited by 51 · see citing works
Tao, T. (2014) · EMS Surveys in Mathematical Sciences · doi:10.4171/emss/1 · Cited by 49 · see citing works
The Classification of the Largest Caps in AG(5, 3)
Edel, Y., Ferret, S., Landjev, I., & Storme, L. (2002) · Journal of Combinatorial Theory Series A · doi:10.1006/jcta.2002.3261 · Cited by 48 · see citing works
1 ON CERTAIN OTHER SETS OF INTEGERSPreprint
Sanders, T. (2016) · Cited by 44 · see citing works
Prime numbers and computer methods for factorization (2nd ed.)
Riesel, H. (1994) · Cited by 42 · see citing works
Potechin, A. H. (2008) · Designs Codes and Cryptography · doi:10.1007/s10623-007-9132-z · Cited by 40 · see citing works
The growth rate of tri-colored sum-free sets
Kleinberg, R., Sawin, W., & Speyer, D. E. (2018) · Discrete Analysis · doi:10.19086/da.3734 · Cited by 40 · see citing works
Improved lower bounds on the rigidity of Hadamard matrices
Кашин, Б. С., & Razborov, A. A. (1998) · Mathematical Notes · doi:10.1007/bf02311250 · Cited by 38 · see citing works
On the rigidity of Vandermonde matrices
Lokam, S. V. (2000) · Theoretical Computer Science · doi:10.1016/s0304-3975(00)00008-6 · Cited by 32 · see citing works
Extremal Hypergraphs and Combinatorial Geometry
Füredi, Z. (1995) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-9078-6_129 · Cited by 32 · see citing works
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
Alman, J., & Williams, V. V. (2018) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2018.00061 · Cited by 31 · see citing works
New Lower Bounds for the Rank of Matrix Multiplication
Landsberg, J. M. (2014) · SIAM Journal on Computing · doi:10.1137/120880276 · Cited by 31 · see citing works
Finite field models in arithmetic combinatorics – ten years on
Wolf, J. (2014) · Finite Fields and Their Applications · doi:10.1016/j.ffa.2014.11.003 · Cited by 30 · see citing works
Further Limitations of the Known Approaches for Matrix MultiplicationPreprint
Alman, J., & Williams, V. V. (2017) · arXiv (Cornell University) · doi:10.4230/lipics.itcs.2018.25 · Cited by 30 · see citing works
Busy beaver competition and Collatz-like problems
Pascal, M. (1993) · Archive for Mathematical Logic · doi:10.1007/bf01409968 · Cited by 29 · see citing works
ROTH’S THEOREM FOR FOUR VARIABLES AND ADDITIVE STRUCTURES IN SUMS OF SPARSE SETS
Schoen, T., & Sisask, O. (2016) · Forum of Mathematics Sigma · doi:10.1017/fms.2016.2 · Cited by 28 · see citing works
On the largest prime factors ofn andn + 1
Erdos, P. L., & Pomerance, C. B. (1978) · Aequationes Mathematicae · doi:10.1007/bf01818569 · Cited by 28 · see citing works
Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd MethodPreprint
Ambainis, A., Filmus, Y., & Gall, F. L. (2015) · arXiv (Cornell University) · Cited by 25 · see citing works
On the largest prime factors ofn andn + 1
Erdös, P., & Pomerance, C. B. (1978) · Aequationes Mathematicae · doi:10.1007/bf01818551 · Cited by 25 · see citing works
Maximal three-independent subsets of {0, 1, 2} n
Calderbank, A. R., & Fishburn, P. C. (1994) · Designs Codes and Cryptography · doi:10.1007/bf01388452 · Cited by 24 · see citing works
On certain other sets of integers
Sanders, T. (2012) · Journal d Analyse Mathématique · doi:10.1007/s11854-012-0003-9 · Cited by 24 · see citing works
A tight bound for Green's arithmetic triangle removal lemma in vector spaces
Fox, J., & Lovász, L. M. (2017) · Advances in Mathematics · doi:10.1016/j.aim.2017.09.037 · Cited by 24 · see citing works
Edel, Y., & Bierbrauer, J. (2001) · Designs, Codes and Cryptography · doi:10.1023/a:1011216716700 · Cited by 22 · see citing works
Progression-free sets in finite abelian groups
Lev, V. F. (2003) · Journal of Number Theory · doi:10.1016/s0022-314x(03)00148-3 · Cited by 22 · see citing works
Roth’s theorem in many variables
Schoen, T., & Shkredov, I. D. (2013) · Israel Journal of Mathematics · doi:10.1007/s11856-013-0049-0 · Cited by 21 · see citing works
A DISTRIBUTION ON TRIPLES WITH MAXIMUM ENTROPY MARGINAL
Norin, S. (2019) · Forum of Mathematics Sigma · doi:10.1017/fms.2019.47 · Cited by 20 · see citing works
Some of My Favorite Problems and Results
Erdös, P. (2013) · Springer eBooks · doi:10.1007/978-1-4614-7258-2_3 · Cited by 19 · see citing works
Quadratic Lower Bounds on Matrix Rigidity
Lokam, S. V. (2006) · Lecture notes in computer science · doi:10.1007/11750321_28 · Cited by 19 · see citing works
Wagstaff, S. S. (2013) · Student mathematical library · doi:10.1090/stml/068 · Cited by 19 · see citing works
Some of My Favorite Problems and Results
Erdös, P. (1997) · Algorithms and combinatorics · doi:10.1007/978-3-642-60408-9_3 · Cited by 18 · see citing works
Combinatorics and linear algebra of Freiman's isomorphism
Konyagin, S. V., & Lev, V. F. (2000) · Mathematika · doi:10.1112/s0025579300015709 · Cited by 17 · see citing works
Which groups are amenable to proving exponent two for matrix multiplication?Preprint
Blasiak, J., Church, T., Cohn, H., Grochow, J. A., & Umans, C. (2017) · arXiv (Cornell University) · doi:10.4230/lipics.ccc.2025.9 · Cited by 17 · see citing works
Self-citationA tight bound for Green's arithmetic triangle removal lemma in vector spaces
Fox, J., & Lovász, L. (2017) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611974782.106 · Cited by 16 · see citing works
Erdős-Ginzburg-Ziv Constants by Avoiding Three-Term Arithmetic Progressions
Fox, J., & Sauermann, L. (2018) · The Electronic Journal of Combinatorics · doi:10.37236/7275 · Cited by 15 · see citing works
Proof of a conjecture of Kleinberg-Sawin-Speyer
Peabody, L. (2018) · Discrete Analysis · doi:10.19086/da.3733 · Cited by 15 · see citing works
Improving Roth's Theorem in the Primes
Helfgott, H. A., & de Roton, A. (2010) · International Mathematics Research Notices · doi:10.1093/imrn/rnq108 · Cited by 12 · see citing works
Using Elimination Theory to Construct Rigid Matrices
Kumar, A., Lokam, S. V., Patankar, V. M., & Sarma, M. N. J. (2013) · Computational Complexity · doi:10.1007/s00037-013-0061-0 · Cited by 12 · see citing works
A lower bound for the k‐multicolored sum‐free problem in Zmn
Lovász, L. M., & Sauermann, L. (2018) · Proceedings of the London Mathematical Society · doi:10.1112/plms.12223 · Cited by 11 · see citing works
Sárközy's Theorem in Function Fields
Green, B. (2016) · The Quarterly Journal of Mathematics · doi:10.1093/qmath/haw044 · Cited by 10 · see citing works
Bateman, M., & Katz, N. H. (2011) · Journal of the American Mathematical Society · doi:10.1090/s0894-0347-2011-00725-x · Cited by 10 · see citing works
Erdős and Arithmetic Progressions
Gowers, W. T. (2013) · Bolyai Society mathematical studies · doi:10.1007/978-3-642-39286-3_8 · Cited by 9 · see citing works
Bounds for Matchings in Nonabelian Groups
Sawin, W. (2018) · The Electronic Journal of Combinatorics · doi:10.37236/7520 · Cited by 9 · see citing works
Tijdeman, R. (2009) · Lecture notes in mathematics · doi:10.1007/978-3-540-48208-6_3 · Cited by 8 · see citing works
Matrix rigidity and the Croot-Lev-Pach lemmaPreprint
Dvir, Z., & Edelman, B. (2017) · arXiv (Cornell University) · doi:10.4230/lipics.ccc.2020.17 · Cited by 8 · see citing works
Sanders, T. (2009) · Analysis & PDE · doi:10.2140/apde.2009.2.211 · Cited by 8 · see citing works
Bounds on sizes of generalized caps in AG(n,q) via the Croot-Lev-Pach polynomial method
Bennett, M. A. (2019) · Journal of Combinatorial Theory Series A · doi:10.1016/j.jcta.2019.06.001 · Cited by 8 · see citing works
Genuine Representations of the Metaplectic Group and Epsilon Factors
Adams, J. (1995) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-9078-6_65 · Cited by 7 · see citing works
Complexity of Linear Circuits and Geometry
Gesmundo, F., Hauenstein, J. D., Ikenmeyer, C., & Landsberg, J. M. (2015) · Foundations of Computational Mathematics · doi:10.1007/s10208-015-9258-8 · Cited by 6 · see citing works
Tao, T. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1310.6482 · Cited by 6 · see citing works
Sumsets as unions of sumsets of subsets
Ellenberg, J. S. (2018) · Discrete Analysis · doi:10.19086/da.2103 · Cited by 6 · see citing works
McMahon, E. W., Gordon, G., Gordon, H., & Gordon, R. (2017) · Princeton University Press eBooks · doi:10.1515/9781400884483 · Cited by 6 · see citing works
Character-free approach to progression-free sets
Lev, V. F. (2011) · Finite Fields and Their Applications · doi:10.1016/j.ffa.2011.09.006 · Cited by 5 · see citing works
Rank counting and maximum subsets of $\mathbb{F}^n_q$ containing no right anglesPreprint
Ge, G., & Shangguan, C. (2016) · arXiv (Cornell University) · Cited by 4 · see citing works
Résultats et problèmes en théorie des nombres
Erdös, P. (1973) · French digital mathematics library (Numdam) · Cited by 4 · see citing works
A connection between matchings and removal in abelian groupsPreprint
Aaronson, J. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1612.04172 · Cited by 3 · see citing works
Bounds for Matchings in Nonabelian GroupsPreprint
Sawin, W. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1702.00905 · Cited by 3 · see citing works
An upper bound on tricolored ordered sum-free setsPreprint
Kim, T., & Oum, S. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1708.07263 · Cited by 2 · see citing works
Glass, D. (2018) · American Mathematical Monthly · doi:10.1080/00029890.2018.1412661 · Cited by 2 · see citing works
Zeilberger, D. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1607.01804 · Cited by 1 · see citing works
Bounds on sizes of general caps in $AG(n,q)$ via the Croot-Lev-Pach polynomial methodPreprint
Bennett, M. A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.05303 · Cited by 1 · see citing works
Flagged first, then by citations
Research works printed but not linked: 4
- Bose, R. C., 1947, Mathematical theory of the symmetrical factorial design, Sankhy\={a}, 8, 107
- Chowla, S., 1944, There exists an infinity of 3—combinations of primes in A. P, Proc. Lahore Philos. Soc., 6, 15
- Pellegrino, Giuseppe, 1970, Sul massimo ordine delle calotte in 𝑆_{4,3}, Matematiche (Catania), 25, 149
- Segre, Beniamino, 1967, Introduction to Galois geometries, Atti Accad. Naz. Lincei Mem. Cl. Sci. Fis. Mat. Natur. Sez. Ia (8), 8, 133
Cited by
Sorted by citations
Mathematical discoveries from program search with large language models
Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J. R., Ellenberg, J. S., Wang, P., Fawzi, O., et al. (2024) · Nature · doi:10.1038/s41586-023-06924-6 · Cited by 544 · see citing works
“The cap set problem 21 , once described by Terence Tao as ‘perhaps my favourite open question’ 29 , refers to the task of finding the largest possible set of vectors in n 3 Z (known as a cap set) such that no three vectors sum to zero.”
BackgroundZhang, R., Liu, F., Lin, X., Wang, Z., Lu, Z., & Zhang, Q. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-70068-2_12 · Cited by 15 · see citing works
Artificial Intelligence and Inherent Mathematical Difficulty
Dean, W., & Naibo, A. (2025) · Philosophia Mathematica · doi:10.1093/philmat/nkaf005 · Cited by 10 · see citing works
On the size of subsets of $$\mathbb{F}_p^n$$ without p distinct elements summing to zero
Sauermann, L. (2021) · Israel Journal of Mathematics · doi:10.1007/s11856-021-2145-x · Cited by 10 · see citing works
Finding solutions with distinct variables to systems of linear equations over $$\mathbb {F}_p$$
Sauermann, L. (2022) · Mathematische Annalen · doi:10.1007/s00208-022-02391-y · Cited by 8 · see citing works
Tensor slice rank and Cayley's first hyperdeterminant
Amanov, A., & Yeliussizov, D. (2022) · Linear Algebra and its Applications · doi:10.1016/j.laa.2022.09.027 · Cited by 4 · see citing works
Maximum subsets of $${{\mathbb {F}}}^n_q$$ containing no right angles
Ge, G., & Shangguan, C. (2019) · Journal of Algebraic Combinatorics · doi:10.1007/s10801-019-00908-4 · Cited by 3 · see citing works
Exponentially larger affine and projective caps
Elsholtz, C., & Lipnik, G. F. (2022) · Mathematika · doi:10.1112/mtk.12173 · Cited by 2 · see citing works
Saketos, V., Kaltenbach, S., Litvinov, S., & Koumoutsakos, P. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-23607-4_13 · Cited by 1 · see citing works
Complete Caps in Affine Geometry AG(n, 3)
Karapetyan, I. A., & Karapetyan, K. (2024) · Pattern Recognition and Image Analysis · doi:10.1134/s1054661824010097 · Cited by 1 · see citing works
Karapetyan, I. A., & Karapetyan, K. (2025) · Pattern Recognition and Image Analysis · doi:10.1134/s1054661825700683 · Cited by 1 · see citing works
Saturation of Rota's basis conjecturePreprint
Yeliussizov, D. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.12926 · Cited by 1 · see citing works
The cap set problem and standard diagrams
Thackeray, H. R. (2021) · Discrete Mathematics · doi:10.1016/j.disc.2021.112558
Stability of the Levi-Civita tensors and an Alon–Tarsi type theorem
Yeliussizov, D. (2023) · Comptes Rendus Mathématique · doi:10.5802/crmath.505
Duede, E., & Davey, K. J. (2025) · Philosophy of Science · doi:10.1017/psa.2025.10160
The Slice Rank Polynomial Method – A Survey a Few Years Later
Sauermann, L. (2024) · Cambridge University Press eBooks · doi:10.1017/9781009490559.008
- Authors
- Grochow, J.
- Affiliations
- University of Colorado Boulder (US)
- Corresponding author
- Grochow, Joshua
- ORCID
- Grochow, Joshua
- Venue
- Bulletin of the American Mathematical Society
- Publisher
- American Mathematical Society (AMS)
- Published
- 2018-10-01
- Volume
- 56
- Issue
- 1
- Pages
- 29-64
- ISSN
- 0002-9904 (ISSN-L)
- 1088-9485
- 0273-0979
- OpenAlex
- W2895170202
- Semantic Scholar
- 69cb36923959f409220d2cf40e40c6c276f18d07
- Cited by
- 16
- References
- 140
- Citations by year
- 2026: 1 · 2025: 3 · 2024: 3 · 2023: 2 · 2022: 3 · 2021: 3 · 2019: 1
- FWCI
- 1.74
- Type
- journal article
- Language
- en
- Open access
- diamond
- doi.org
- Locations
- Bulletin of the American Mathematical Society (publishedVersion)
- Funders
- American Institute of Mathematics
- Topics
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Limits and Structures in Graph Theory
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Advanced Combinatorial Mathematics
- Physical Sciences › Mathematics › Algebra and Number Theory › Analytic Number Theory Research
- Keywords
- polynomial method, arithmetic progressions, finite fields, triangle-free graphs, matrix rigidity, matrix multiplication algorithms, additive combinatorics, Fourier analysis
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
