Skip to main content
2 of 3
added 11 characters in body
Seva
  • 23k
  • 2
  • 59
  • 141

Covering all, but $k$ points with affine subspaces

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?

Seva
  • 23k
  • 2
  • 59
  • 141