New, Old, Ancient Results
Nonexistence theorems and attempts at lower bounds
![]() |
Cropped from src |
Joshua Grochow is an assistant professor in Computer Science and Mathematics at the University of Colorado at Boulder. He was a student of Ketan Mulmuley and Lance Fortnow at Chicago; his dissertation and some subsequent papers did much to widen the horizons of the “Geometric Complexity Theory” (GCT) program. He is also a gifted expositor.
Today we will highlight some of his work and some of his exposition of new and old theorems.
An ancient one is Stephen Mahaney’s famous theorem on the nonexistence of sparse -complete sets (unless
). Grochow discusses a simpler proof of the theorem by Manindra Agrawal and gives some further impacts on GCT.
A recent one with Youming Qiao is on an old topic and is in the 2021 Innovations in Theoretical Computer Science conference. It is titled, “On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness,” and grows out of a 2019 paper by the same authors.
This came to my attention through communications with Grochow’s student, Michael Levet. Indeed, Levet is the reason for my putting this all together. He raised through email some questions about an ancient result of mine on group isomorphism. I reported previously:
Long ago Bob Tarjan and Zeke Zalcstein and I made a simple observation: Group isomorphism could be done in time
This relies on the easy-to-prove fact that every group has at most
generators. We have discussed this idea earlier here.
Levet raised an issue about related observations of mine—ones that were misleading at best. I think he has a good point and we are still trying to unravel exactly what I meant back then. I applaud him for reading ancient stuff, for trying to extend it, and for working on such problems. I wish him well.
No Three In a Row
While Levet and I work that out and think about Grochow’s paper on isomorphism problems with Qiao, Ken and I want to highlight a different expository paper by Grochow on news from 2016 that we covered then. Grochow’s paper appeared in the AMS Bulletin and is titled, “New Applications Of The Polynomial Method: The Cap Set Conjecture And Beyond.”
To lead in to the subject, here is a problem from 1917 by the English puzzlemaster Henry Dudeney titled, “A Puzzle With Pawns”:
Place two pawns in the middle of the chess- board, one at Q 4 and the other at K 5. Now, place the remaining fourteen pawns (sixteen in all) so that no three shall be in a straight line in any possible direction. Note that I purposely do not say queens, because by the words ” any possible direction ” I go beyond attacks on diagonals. The pawns must be regarded as mere points in space — at the centres of the squares.
Sixteen is obviously the maximum possible for a standard chessboard because a seventeenth pawn would make three in some row and some column. For an
board, the limit is
by similar reasoning—this is an example of the pigeonhole principle which we just mentioned.
It is possible to achieve the maximum for all up to
and then the only other cases known are
,
, and
. That’s it. Here are solutions for
and
. The latter was found by Achim Flammenkamp, whose page has encyclopedic information. On the former, the pieces are positioned on gridpoints like stones in Go, which seems a better context for this problem than chess.
![]() |
Composite of src1, src2 |
The conjecture is not only that a -size solution exists for only finitely many
, but also that the maximum size for all sufficiently large
is bounded by
with
, indeed, with
. It is known that
stones can always be placed with no three collinear, where the
depends on the closeness of a prime to
.
The problem can be taken to dimensions that are beyond the plane. We can also extend what is meant by a “line” via various notions of wrapping-around. Then the question is how close the maximum size can stay to being linear in the size of the space—as
and/or the size
of an individual dimension increase.
Not As Easy As Tic-Tac-Toe
The theme of the no-three-in-a-line problem is fundamental to combinatorics. There are tons of problems of the form:
How many objects can one place, so that no pattern of some certain type exists?
In -dimensional space the smallest
of interest is
. This means playing on higher-dimensional versions of the
grid and
cube. Then the only Euclidean lines are the kind we know from tic-tac-toe: straight across or down, or diagonal.
For dimension there are other kinds of diagonals, such as within a face or through the center of the cube, but they all win at
-dimensional tic-tac-toe. So the problem becomes: what is the maximum number of moves you can make by yourself without creating a win at tic-tac-toe? The cap-set problem adds a twist by extending the notion of what is a line. It is like playing tic-tac-toe on a floor of
tiles where a play in one tile is replicated in all of them. Then you can make a line by playing in a corner and in the middle of the two opposite edges, as shown at left in the following diagram (original drawing).
The four orange O’s at right have no 3-in-a-line even with this extended notion of line. Note that the four blank cells in the top two rows also avoid putting 3 in a line. Four is the maximum, however: it is not possible to have a drawn game in extended tic-tac-toe.
The theorem proved by Jordan Ellenberg and Dion Gijswijt in 2016 is that the upper bound is not only a vanishing fraction of the size of the space as
grows, it is bounded by
where
. Namely:
Theorem 1 Every cap set in the
-cube has size at most
.
Using Polynomials
There is a simple way to express the extended notion of “line” that works for all dimensions : Number the coordinates of each dimension
. Make the space
with addition modulo
, that is, make it
. Then the condition for three points
to be in a line is simply
It is easy to write polynomial equations over the field to express the property of a set having such a line. What was unexpected, until Ernie Croot, Vsevolod Lev, and Péter Pál Pach solved a related problem with
, was that there would be
“an ingeniously simple way to split the polynomial[s] into pieces with smaller exponents, which led to a bound on the size of collections with no [lines].”
The quotation comes from an article by Erica Klarreich for Quanta right then in 2016. A 2016 AMS Feature column by David Austin covers how to make this say a set of points is a cap set modulo 3:
where we (not Austin) write to mean the set of sums
where
and
. If there is an element
in the intersection then
, and since
, we get
with
in
and all distinct, a contradiction. (If
then
, so
.) Let
stand for the number of monomials of degree at most
in the
variables. The key first insight is:
Lemma 2 If a polynomial
of degree
vanishes on
, then
for all but at most
points of
.
One could first try to interpret this as saying that “looks like”
to polynomials
of “low” degree
. However, if
stays low relative to
then the “if” part would hold vacuously, opposing the goal of bounding
and making the whole idea self-defeating. In fact, the important tension comes when
is intermediate:
, which for
makes
and
neatly occupy the middle of the range
.
The proof also uses the trick that if a product of two monomials has degree then one of them must have degree at most
. As I (Ken writing these sections) wrote about it back in 2016, this reminds of Roman Smolensky’s degree-halving trick in his celebrated 1987 theorem on lower bounds for mod-
versus mod-
. This trick, however, runs from
to
for all moduli.
In any event, the 2016 papers were a new form of the polynomial method that led to striking new results. What Grochow’s survey does for us now is bring out wider implications of this ingenuity.
Applications in Complexity
Grochow’s four application areas in section 4 of his survey are:
- Progress on various forms of `sunflower’ conjectures.
-
Barriers to attempts to show that the exponent of matrix multiplication is
.
- Removing edges to make graphs triangle-free.
- Matrix rigidity and lower bounds.
We say a little more about the last of these. For any matrix
and
define the rigidity
to be the minimum number of entries in which
differs from some matrix of rank (at most)
. The highest possible rigidity for rank
is
, since zeroing out an
block leaves a matrix of rank at most
. Sufficiently random matrices meet this upper bound with high probability, but the best lower bounds for explicit families of matrices are
, which is only quasi-linear when
is close to
. The question is whether we can inch this up to
for some
.
Definition 3 A family of matrices
is significantly rigid if there is an
such that taking
makes
.
The interest in this definition comes from a lack of lower bounds on linear algebraic circuits computing natural families of linear transformations that seems even more extreme than our lack of super-linear lower bounds on Boolean circuits, nor better than
for general algebraic circuits computing polynomials in
variables of degree
. It is still consistent with our knowledge that every natural family
can be computed by linear algebraic circuits of
size and
depth. Leslie Valiant in 1977 proved the following sufficient condition to improve this state of affairs.
Theorem 4 Every significantly rigid family
cannot be computed by linear algebraic circuits of linear size and logarithmic depth.
So for coming on half a century the question has been:
Can we construct a natural explicit family of significantly rigid matrices?
Beliefs that the Hadamard matrices provided such a family were refuted by Josh Alman and Ryan Williams at STOC 2017, and known results for Vandermonde matrices do not have close enough to
.
One hope had been to derive such matrices from explicit functions over
for
prime by taking
and defining
Unfortunately, the polynomial method for cap sets shows that no such attempt can work. Zeev Dvir and Benjamin Edelman proved that no matter how and
are chosen, there is
such that for all large enough
,
This means we cannot get for
, indeed, far from it. What is most curious to us is that for matrix multiplication, the cap-set related technique frustrates a better complexity upper bound, whereas here it frustrates a better lower bound.
Open Problems
What further applications can we find for the polynomial method?
A Quiz of Quotes
Everything that can be invented has been invented—Charles Duell, Commissioner, U.S. Office of Patents, 1899
![]() |
MathQuotes src |
George Cantor has been featured here and here and here before on GLL. Of course, he invented modern set theory and changed math forever. His birthday is soon, so we thought we would talk about him now—he was born on March 3rd in 1845.
Today we thought it might be fun to have a quiz on math quotes.
Read more…
Riemann Hypothesis—Why So Hard?
“If I were to awaken after having slept a thousand years, my first question would be: has the Riemann Hypothesis been proven?” — David Hilbert
![]() |
Steklov Institute memorial page |
Sergei Voronin was an expert in number theory, who studied the Riemann zeta function, but who sadly died young over twenty years ago. We discussed his amazing 1975 result about the Riemann zeta function here. Others call the result the amazing theorem. I (Dick) am getting old—I almost forgot that we did a post on his theorem again over four years ago.
Today I thought we would recall his theorem, sketch why the theorem is true, and then discuss some extensions.
Read more…
Computing’s Role In The Pandemic
How can we help?
Joe Biden is the 46th president of the USA. Note is called a centered triangular number. These numbers obey the formula:
and start with The previous one, the
, was Herbert Hoover, hmmm. Biden has promised to make controlling the Covid-19 pandemic one of his top priorities.
Today I thought we would discuss how he might use computer technology to help get the virus under control.
Read more…
Alan Selman
A special journal issue in his honor
Elvira Mayordomo, Mitsu Ogihara, and Atri Rudra are going to be the editors of a special issue of the journal Theory of Computing Systems dedicated to Alan Selman. Alan passed away this January 2021.
Today we circulate their request for contributions.
Pigenhole Principle
Mathematics is based on the application of simple ideas over and over: From tiny nuts do big trees grow.
Jorgen Veisdal is an assistant professor at the Norwegian University of Science and Technology. He is also the editor in chief at Cantor’s Paradise, which is a publication of math and science essays.
Today I thought we would discuss a post of his on the famous Pigenhole Princeiple (PP).
Read more…
Graph Products
The power of definitions and notations
Leopold Kronecker was one of the great mathematicians of the 19th century. He thought about foundational issues deeply. We highlighted him before—well not deeply.
Today I thought we would talk about some core math ideas arising out of Kronecker’s work.
Read more…
Alan Selman, 1941–2021
Keeping a promise to structure the field of complexity
![]() |
2017 Who’s Who award |
Alan Selman, my longtime friend and colleague, passed away last Friday, from the one illness that is most cruel for someone who has excelled by brainpower and effervescent joie de vivre alike.
Today, Dick and I join others in mourning and also in appreciation.
Read more…
Happy Un-Birthday Rich
Still going strong
Richard DeMillo just turned 74 years old the other day. Happy Birthday Rich, and many more.
![]() |
Today I want to wish him also a happy un-birthday.
Read more…
Science Advisor
Resources for a new term from our vantage point
![]() |
Crop from Broad Institute src |
Eric Lander has been appointed director of the US Office of Science and Technology Policy, a post newly elevated to Cabinet status. He is thus the top science advisor in Joe Biden’s cabinet.
Today we congratulate Eric, whom we both have known personally, and survey some sources of science advice at his career’s roots.
Read more…