4
$\begingroup$

For non-negative integer $d\le n$ and $k\le 2^n$, how many affine subspaces of co-dimension $d$ are needed to cover all, but exactly $k$ elements of the vector space ${\mathbb F}_2^n$, and what are the possible values of $k$?

I know the answer in two particular cases. The case $d=1$ is about hyperplane coverings. It is not difficult to see that in this case $k$ must be a power of $2$, and for all but $k=2^s$ elements to be covered, one needs at least $n-s$ hyperplanes.

Another situation where the answer is known to me is $k=1$: by a year 1977 result of R. Jamison, to cover all but exactly one element of ${\mathbb F}_2^n$, one needs at least $n+2^d-d-1$ affine co-$d$-subspaces.

What is the answer in the general case? Has it ever been studied?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ What is the easy proof for d=1 and k=1? I thought you need algebraic methods to prove this. math.uiuc.edu/~z-furedi/PUBS/furedi_alon_cube-covering.pdf $\endgroup$
    – domotorp
    Commented Jan 5, 2013 at 16:48
  • $\begingroup$ @domotorp: By a straightforward induction on $p$, the subset uncovered by $p$ hyperplanes, if nonempty, is an affine subspace of codimension at most $p$. $\endgroup$
    – Ilya Bogdanov
    Commented Jan 5, 2013 at 16:53
  • $\begingroup$ @domotorp: I know that paper of Alon and Furedi, but this is what I call "easy to see"! Another (an maybe, yet easier) way to get the conclusion is to observe that the complement of a union of $d$ hyperplanes is an intersection of $d$ hyperplanes, hence is given by a system of $d$ linear equations. And, I do not claim that I know a simple proof for $k=1$ and $d$ arbitrary. $\endgroup$
    – Seva
    Commented Jan 5, 2013 at 17:41
  • 1
    $\begingroup$ @domotorp. There is an easy proof for $k=d=1$ using a variant of the proof of Chevalley-Warning. Let $V$ be a $n$-dimensional affine space over a finite field $F$ with $q$ elements. (Here $q=2$.) Take the product $P$ of all equations of the involved affine hyperplanes. Then $\sum_{x\in V}P(x)\neq 0$ since all terms are zero but one. On the other hand, if $\deg(P)<n(q-1)$, the sum is zero (because the monomials of $P$ are of the form $x_1^{d_1}\dots x_n^{d_n}$ and $d_i<q-1$ for at least one $i$). So $\deg(P)\geq n(q-1)$. $\endgroup$
    – ACL
    Commented Jan 5, 2013 at 20:04
  • $\begingroup$ @domotorp (followed). Moreover, you can cover $V$ minus one point by $n(q-1)$ hyperplanes. Just take translates of coordinates hyperplanes with equations $x_i=a$, for $1\leq i\leq n$ and $a\neq 0$. $\endgroup$
    – ACL
    Commented Jan 5, 2013 at 20:05

1 Answer 1

Reset to default
2
$\begingroup$

Here are some partial answers to your question.

Let $A = A_1 \times \dots \times A_n \subseteq F^n$ be a finite grid. Alon and Furedi proved that you need at least $\sum (\# A - 1)$ hyperplanes to cover all but one points of $A$. If your $k$ is small enough (less than $\min \# A_i$), then you can use this bound to show that to cover all but $k$ points you need at least $\sum (\# A_i - 1) - k + 1$ hyperplanes, since by adding $k - 1$ hyperplanes you'll be covering all but one. This seems to be a tight bound for small enough $k$.

Now let $B = B_1 \times \dots \times B_n$ be a sub-grid of $A$, i.e., $B_i \subseteq A_i$ for all $i$. S. Ball and O. Serra have proved a theorem that they called ``Punctured Combinatorial Nullstellensatz'' which can be used here to show the following:

The minimum number of hyperplanes you need to cover all points of $A$ except some point of $B$ is at least $\sum (\# A_i - \# B_i)$.

This can also be proved directly by induction on the degree of polynomial associated with the hyperplane cover, or on $\sum (\# A_i - \# B_i)$. And in fact, easier proofs of the punctured combinatorial nullstellensatz can be given.

This might give you better bounds for certain values of $k$. Especially when the $k$ points are arranged nicely.

Some other results in this general direction that can be useful are, Covering all points except one, How many $s$-subspaces must miss a point set in $PG(d , q)$. The latter could probably give you the best possible results for the general case of covering all points but some by affine subspaces.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .