A finite grid is a set , where is a field and each is a finite subset of . The minimum number of hyperplanes required to cover can easily be shown to be , with the hyperplanes defined by , for providing such a cover (assuming is the index minimising ). Interestingly, if we forbid the hyperplanes to pass through one specific point of , say , and then want to cover everything else, then the minimum number of hyperplanes required is equal to . This number can be pretty large compared to the previous one.
This is the famous result of Alon and Füredi from 1993 which was proved in its full generality using the polynomial method. They were answering a question of Komjáth, which was for the special case of , but this same result had in fact been proved already for another special case in the late 70’s. Jamison, and Brouwer-Schrijver, proved this bound for and . They were motivated by a question in finite geometry about the blocking number of an affine space, asked by Jean Doyen, which is equivalent to the dual statement. Their proofs were also algebraic and in fact they are one of the first instances of what we now call the polynomial method (see this for a history). In finite geometry circles, this method was sometimes even referred to as the Jamison method.
In the 90’s, Bruen proved an interesting generalisation of the Jamison/Brouwer-Schrijver result, motivated by problems in finite geometry, where the (multi)set of hyperplanes covered every point except at least times, while not covering at all. He proved the lower bound of and asked about the sharpness of this bound. The sharpness was addressed in some later papers, for example by Simeon Ball and then Corrado Zanella. In 2009, Ball and Serra generalised this covering with multiplicities result to the case of arbitrary finite grids by proving a general lower bound on the degree of polynomials that vanish everywhere on the grid with a certain multiplicity except at one point. Recently, there has been a lot of interesting activity in this hyperplane covering problem with multiplicities, for the special case of binary hypercubes. This is what I want to focus on in this blog post. I also want to mention some interesting new results over the binary field that I have proved in collaboration with Simona, Shagnik and Tamás, which nicely complements this recent work.
Let’s first write down the main extremal functions that we are interested in. Given a field and positive integers , with , define a -cover of as a multiset of hyperplanes with the property that there are exactly element of passing through the origin and for every point in there are at least element in passing through . We then define:
Note that has the following natural reformulation: it is the smallest number of hyperplanes that cover every non-origin point at least times but only cover the origin at most times. All of these function are the same for and equal to by the result of Alon and Füredi. It is also an easy exercise to show that for any field . I have hidden the field in the notation of these functions, and so I’ll make it clear what field we are talking about before making any statement.
Last year, Clifton and Huang studied the function when and proved the following results:
, for all and , and
for fixed and .
Moreover, they conjectured that we should have for every fixed and large enough as they couldn’t find any better construction than the one where you take the hyperplanes defined by and copies of hyperplanes , for . This seems to be a very challenging problem.
Very recently, Sauermann and Wigderson have managed to improve the Clifton-Huang lower bounds on by proving a general result about polynomials vanishing with multiplicities on binary hypercubes. In particular, they prove the following results:
- for any field .
- for all if we have .
Note that since by the definition of these function, the second statement improves the lower bound of Clifton and Huang for (as the field has characteristic ). They also ask about extending their results to fields of positive characteristic and give some examples over finite fields that shows how their proof fails to give the same bound on (or . In particular, over they show that one can’t prove that using their method.
Last year, while I was still in Berlin, I suggested studying these problems in our group workshop and we managed to obtain some interesting preliminary results for the case of with my colleagues. We now have a paper, which is soon going to be posted on the arXiv, where we prove the following results for .
Theorem 1. For , . For , .
Our proofs don’t involve any polynomials. We simply use some combinatorial arguments where one crucial ingredient in our proof is a coding theoretic interpretation of the function that implies the following:
Theorem 2. For all and , .
(One can also show the upper bound of .)
Another important ingredient is the following statement, which we prove via induction, but it in fact follows from the work of Sauermann and Wigderson as well:
Lemma 3. For , we have .
Moreover, because our methods are combinatorial, we can generalise to covers using smaller dimensional subspaces, which is something that’s not at all easy to do in the polynomial method. If we denote by the function where the cover involves -dimensional affine subspace of , then we show the following:
Theorem 4. For , . For , .
This result in fact generalises the binary case of Jamison’s theorem who proved that for we have . (though there is no condition on being large enough in Jamison’s theorem)
Sadly, our methods don’t give us anything new for the case of when . I believe that for larger fields one needs to improve upon the existing algebraic methods. Also, over while we know that the threshold in Theorem 1 is tight, there is a lot of room for improvement in the bound . We suspect that except for some small exceptions (that arise due to the Golay code), the correct threshold should be . More specifically, we believe that for . We do show that for all , and thus this threshold of , if true, would be tight.
I would love to see a proof (or a counterexample) to the following simpler statement,
for all .
It will also be very interesting to determine what happens between these extreme ranges of parameters, for example when for some constant . We leave these as open problems and we are looking forward to more new developments in this topic which can help solve them.
Edit 29/01/2021: The paper is now available on the arXiv.