Covering the binary hypercube

A finite grid is a set $S = S_1 \times \cdots \times S_n \subseteq F^n$, where $F$ is a field and each $S_i$ is a finite subset of $F$. The minimum number of hyperplanes required to cover $S$ can easily be shown to be $\min |S_i|$, with the hyperplanes defined by $x_1 - \lambda = 0$, for $\lambda \in S_j$ providing such a cover (assuming $j$ is the index minimising $|S_i|$). Interestingly, if we forbid the hyperplanes to pass through one specific point of $S$, say $\vec{a} = (a_1, \dots, a_n)$, and then want to cover everything else, then the minimum number of hyperplanes required is equal to $\sum_{i = 1}^n (|S_i| - 1)$. 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 $S = \{0, 1\}^n$, 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 $F = \mathbb{F}_q$ and $S = \mathbb{F}_q^n$. 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 $\vec{a} \in \mathbb{F}_q^n$ at least $k$ times, while not covering $\vec{a}$ at all. He proved the lower bound of $(n + k - 1)(q-1)$ 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 $\mathbb{F}_2$ 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 $F$ and positive integers $n, k, s$, with $s \leq k - 1$, define a $(k, s)$-cover of $\{0, 1\}^n \subseteq F^n$ as a multiset $\mathcal{H}$ of hyperplanes with the property that there are exactly $s$ element of $\mathcal{H}$ passing through the origin and for every point $\vec{p}$ in $\{0, 1\}^n \setminus \{\vec{0}\}$ there are at least $k$ element in $\mathcal{H}$ passing through $\vec{p}$. We then define:

$h(n, k, s) = \{\min |\mathcal{H}| : \mathcal{H} \text{ is a } (k, s)-\text{cover of } \{0, 1\}^n\}$;

$g(n, k) = \min_{s} h(n, k, s)$;

$f(n, k) = h(n, k, 0)$.

Note that $g(n, k)$ has the following natural reformulation: it is the smallest number of hyperplanes that cover every non-origin point at least $k$ times but only cover the origin at most $k - 1$ times. All of these function are the same for $k = 1$ and equal to $n$ by the result of Alon and Füredi. It is also an easy exercise to show that $f(n, 2) = g(n, 2) = n + 1$ for any field $F$. I have hidden the field $F$ 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 $f(n, k)$ when $F = \mathbb{R}$ and proved the following results:

$f(n, 3) = n + 3$,

$n + k + 1 \leq f(n, k) \leq n + \binom{k}{2}$, for all $k \geq 4$ and $n \geq 3$, and

$f(n, k) = (1 + 1/2 + \cdots + 1/n + o(1))k$ for fixed $n$ and $k \rightarrow \infty$.

Moreover, they conjectured that we should have $f(n, k) = n + \binom{k}{2}$ for every fixed $k \geq 3$ and $n$ large enough as they couldn’t find any better construction than the one where you take the $n$ hyperplanes defined by $x_i = 1$ and $k - t$ copies of hyperplanes $\sum_{i = 1}^n x_i = t$, for $1 \leq t \leq k - 1$. This seems to be a very challenging problem.

Very recently, Sauermann and Wigderson have managed to improve the Clifton-Huang lower bounds on $f$ by proving a general result about polynomials vanishing with multiplicities on binary hypercubes. In particular, they prove the following results:

1. $h(n, k, k - 1) = n + 2k - 2$ for any field $F$.
2. $g(n, k) = n + 2k - 3$ for all $n \geq 2k - 3$ if we have $\mathrm{char}~F = 0$.

Note that since $f(n, k) \geq g(n, k)$ by the definition of these function, the second statement improves the lower bound of Clifton and Huang for $n \geq 2k - 3$ (as the field $\mathbb{R}$ has characteristic $0$). 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 $g(n, k)$ (or $f(n, k)$. In particular, over $\mathbb{F}_2$ they show that one can’t prove that $f(n, 4) \geq n + 5$ 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 $\mathbb{F}_2$ 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 $F = \mathbb{F}_2$.

Theorem 1. For $n > 2^k$, $g(n, k) = n + 2k - 3$. For $k \geq 2^{n - 2}$ , $g(n, k) = 2k - \lfloor k/2^{n-1} \rfloor$.

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 $f(n, k)$ that implies the following:

Theorem 2. For all $k \geq 2$ and $n \geq 1$, $f(n, k) \geq n + \lfloor (k -1)/2 \rfloor \log (2n/(k-1))$.

(One can also show the upper bound of $f(n, k) \leq n + (k - 1) \log(n/(k-1))$.)

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 $n, k \geq 1$, we have $h(n, k, k - 1) = n + 2k - 2$.

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 $g(n, k, d)$ the function where the cover involves $(n - d)$-dimensional affine subspace of $\mathbb{F}_2^n$, then we show the following:

Theorem 4. For $n > 2^{k2^d -d - k + 1}$, $g(n, k, d) = k2^d + n - d - 2$. For $k \geq 2^{n - d - 1}$, $g(n, k, d) = k2^d - \lfloor k/2^{n-d} \rfloor$.

This result in fact generalises the binary case of Jamison’s theorem who proved that for $F = \mathbb{F}_q$ we have $g(n, 1, d) = q^d - 1 + (n - d)(q - 1)$. (though there is no condition on $n$ being large enough in Jamison’s theorem)

Sadly, our methods don’t give us anything new for the case of $F = \mathbb{F}_q$ when $q > 2$. I believe that for larger fields one needs to improve upon the existing algebraic methods. Also, over $\mathbb{F}_2$ while we know that the threshold $k \geq 2^{n - 2}$ in Theorem 1 is tight, there is a lot of room for improvement in the bound $n \geq 2^k$. We suspect that except for some small exceptions (that arise due to the Golay code), the correct threshold should be $k + 1$. More specifically, we believe that $g(n, k) = n + 2k - 3$ for $n \geq \max\{k+1,13\}$. We do show that $g(k, k) \leq 3k - 4$ for all $k$, and thus this threshold of $k + 1$, if true, would be tight.

I would love to see a proof (or a counterexample) to the following simpler statement,

$g(n, k) = n + 2k - 3$ for all $n \geq poly(k)$.

It will also be very interesting to determine what happens between these extreme ranges of parameters, for example when $n \sim k^{c}$ for some constant $c < 1$. 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.

About Anurag Bishnoi

A mathematician working at TU Delft. I am broadly interested in combinatorics and finite geometry.
This entry was posted in Combinatorics, Extremal Combinatorics, Finite Geometry, Polynomial Method and tagged , , , , , , , , , , . Bookmark the permalink.

1 Response to Covering the binary hypercube

1. Jon Awbrey says:

Maybe some bits of Differential Logic would be of use here?