Last week, I gave a seminar on the slice rank of functions (probably one of many concerning that particular subject since last year). The motivation being mainly that I, together with my advisors Jan De Beule and Philippe Cara, wanted to understand this method better, so what better way to understand something than to talk about it with fellow mathematicians?
I want to write down some of the material I presented on the blackboard, primarily to have a reference and some notes for myself, but perhaps they can also give someone else a better understanding of the ideas and concepts regarding this topic. I have not seen the visual interpretation of the different notions of rank is anywhere else, so this might be interesting as well. Let me know if this has helped you or if something needs more explanation!
Last year, the combinatorial world was stunned by a series of results by Croot-Lev-Pach, Ellenberg-Gijswijt regarding arithmetic progressions in certain groups. I will not try and give an complete account of these, as several sources around the web have done so already quite extensively (blog post by Anurag Bishnoi; a rendition of the proof by Doron Zeilberger and references on Gil Kalai’s blog). As an indicator of the gravity of these two results, both have been published in the Annals of Mathematics in the beginning of this year. Instead, I will try to elude the idea of ‘slice rank’ of a tensor, as was defined by Terry Tao in his reformulation of the Ellenberg-Gijswijt proof. I will try to indicate where the idea might have come from and how one can understand it in a sort of geometrical way. Most, if not all, of the theory can be developed for general tensors (see again Terry’s blog), but we will restrict ourselves to to a special case, which we will explain in the next paragraph. The reason for this is that I find the concepts easier to explain in this specific setting. So without further ado, let’s get on with it.
Functions of a finite set to a field
People comfortable with tensor products and know why an n-variable function , where each is a finite set and is a field, is a special case of a tensor, can skip this section.
For those who aren’t (like myself), here’s a short explanation why. Consider a finite set , a field and the set of functions , denoted by . For every element , we can consider its characteristic function , which is 1 if and 0 otherwise. Endowing the set with an addition and multiplication with a scalar from in the natural way, we see that is isomorphic as a vector space to , with a natural basis , .
Therefore, for two finite sets and , we can consider the tensor product . One can check that this is a vector space isomorphic to , which can be seen by the isomorphism . This means for example that any function can be expanded in the natural basis of delta functions as
In the same way, one can write as a sum of functions of the form , where , and is therefore a tensor.
Tensor rank versus (multi-)slice rank
For most instances of ‘rank of an object’, we have the following heuristic rule:
object of rank k = sum of k objects of rank one (and not less)
Meaning that, in order to define a rank function, it suffices to specify the rank one objects. This is for example the case for the usual definition of tensor rank, and will also be the case for the other two rank functions we define. As previously remarked, we will only define these rank function for the special case of n-variable functions.
In order to avoid cumbersome notation, we use the following convention. Let and . Then by we mean and for a function we write instead of .
A function is of tensor rank one if and only if there exist functions such that . In a way, the function ‘splits’ completely.
A function is of slice rank one if and only if there exists and functions such that . In words: we can ‘slice off’ one variable from the function.
A function is of multi-slice rank one if and only if there exists and functions such that . Here we relax the notion of rank even more, by slicing off several variables at once.
Bounds and examples
Let be an n-variable function. The first inequality is immediate when comparing the definitions:
multi-slice rank() slice rank() tensor rank().
A decomposition of into a basis of delta functions shows that
tensor rank() slice rank()
and if is another n-variable function then
multi-slice rank() tensor rank() slice rank().
We can show some examples to see that tensor rank, slice rank and multi-slice rank may differ heavily. Let be a finite set, the k-fold Cartesian product of with itself and a field.
Example 1. Consider the function which is 1 if and 0 otherwise. Define . This function has tensor rank and slice rank 1.
This example shows that the second inequality is sharp. The gap between slice rank and multi-slice rank can also be big, as shown in the next example.
Example 2. Define . This function has slice rank and multi-slice rank 1.
Visually representing the differences
Clearly for , the three notions coincide, so we will consider the case to see the difference between tensor rank and (multi-)slice rank (in this case, the last two definitions of rank coincide). We will use a higher-dimensional version of the following fact: consider a function and construct the matrix of values . Its rows are indexed by , its columns by and the -entry equals . Then the following should be clear: has tensor rank (or (multi-)slice rank) 1 if and only if its matrix of values has matrix rank one.
When considering a function , we can construct a hypermatrix of values instead of a matrix, which should be seen as a 3D array of points. Here the notions of tensor rank and (multi-)slice are clearly not equivalent. For simplicity, suppose that , so we can draw the values of on the cube .
We can first consider the case when a function has tensor rank one. When drawing its associated hypermatrix with the values, we get the following picture.
We see that in all three directions, we have ‘scalarity’ (by lack of a better word), by which I mean that (every value on) every hyperplane is a scalar multiple of (a value on) any parallel hyperplane. This clearly also holds if and are arbitrary finite sets. This is a quite strong condition, which seems natural to relax.
Suppose that the function has slice rank one, then the picture is the following.
Clearly, the property of scalarity of the hyperplanes in all directions / all parallel classes is now replaced by scalarity of hyperplanes in one direction, namely in the direction indexed by the set whose variable can be split off.
To understand the difference between slice rank and multi-slice rank, using this same idea of a hypermatrix of values, we would need to draw a 4D hypermatrix. We will make an attempt in doing so. We will again consider the simple case when all sets involved are . First we need to understand how one can draw a 4D cube in 2D.
A cube in 2D can be drawn as below: draw two squares, one sitting inside the other, and connect corresponding points of the squares.
A 4D cube can be realised in 3D in the same way: take two cubes, one inside the other and connect corresponding points. However, this blog is as of now restricted to two dimensions (high hopes for the distant future!), so we need to draw these two cubes again the in plane. This can be done in the following way.
Using this visual representation, we can try to distinguish functions of slice rank one and of multi-slice rank one. First we start with a function of slice rank one and its hypercube of values.
As you can see, the red and blue cubes, contained in the hypercube, exhibit the scalarity phenomenon. This indeed means that we have scalarity of hyperplanes (which in this case are three-dimensional spaces on the hypercube, i.e. cubes) in one direction. In contrast, below is the hypercube of values for a function of multi-slice rank one.
In this case, we have scalarity of the red and blue subspace, but in this case the subspaces are planes, as opposed to cubes. The pictured red and blue planes are not the only pair of planes related by scalarity, can you find more?
Applications to combinatorics
The definition of slice rank and multi-slice rank of an n-variable function are not pulled from thin air. They have appeared implicitly in the Croot-Lev-Pach and Ellenberg-Gijswijt paper and are roughly based on the following basic fact.
Fact. Consider a polynomial one variable of degree . When we consider and expand this into a sum of monomials , we know that for every monomial either or .
This means that if we define a two variable function by , one can bound the tensor rank of by twice the number of monomials where . When considering three or more variables (e.g. ), we need to replace tensor rank by slice rank.
This gives one half of an inequality. The other half comes from a generalization of the fact that the matrix rank of a diagonal matrix is the number of non-zero elements on its diagonal.
Lemma. Let , let be a finite set, let be a field, and for each , let be a coefficient. Then the slice rank of the function
is equal to the number of non-zero coefficients .
This result was first shown by Tao on his blog and Naslund has extended this by showing that also its multi-slice rank equals the number of non-zero coefficients.
Now how to combine these two ideas? First, have a certain finite set for which you want to bound its size. Create a tensor that is diagonal upon restricting to , so that the slice rank of this tensor is at least . Then try to bound the slice rank of this function by above, using for example the properties of the field in which this function maps. In this way, several (highly) non-trivial bounds have been obtained.
For example in the Ellenberg-Gijswijt paper, one considers the affine space and tries to bound the size of set not containing three collinear points. As any three collinear points in this space are of the form , it is clear to see that three points are collinear if and only if . Therefore, when taking a set not containing three collinear points, the function , restricted to , is zero if and only if . We can expand this function in another way as
and find bounds for the slice rank of using this decomposition. When doing so, one can find that the size of is at most by .