New, Old, Ancient Results

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:

1. Progress on various forms of `sunflower’ conjectures.

2. Barriers to attempts to show that the exponent of matrix multiplication is .

3. Removing edges to make graphs triangle-free.

4. 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?