While trying to answer this question, I arrived at another question:

How many translates of $\{0,1\}^n$ does it take to cover $\mathbb F_3^n$?

The broader context is: consider a set $S$ and a collection $\mathcal P$ of subsets of $S$; each subset of the same size, $t$, and each element of $S$ belonging to the same number, $k$, of elements of $\mathcal P$. Write $N(S,\mathcal P)$ for the minimal number of elements of $\mathcal P$ to cover $S$.

By analogy with definitions about covering and packing of subsets of $\mathbb R^d$, define the covering density of $\mathcal P$ to be $t\times N(S,\mathcal P)/|S|$, that is the average number of times than an element of $S$ is covered by a minimal covering from $\mathcal P$.

By random methods, I can show that one can find $n\times (\frac 32)^n$ translates of $\{0,1\}^n$ that cover $\mathbb F_3^n$ for a covering density of at most $n$.

  • Are there any known lower bounds on the covering density?
  • Are there well known places to look for good examples with large covering density?
  • Are random methods the standard approach to questions of this type?

  • $\endgroup$

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

    Browse other questions tagged or ask your own question.