2
$\begingroup$

suppose we are given the $d$-dimensional hypercube $H^d$ defined as

$$ H^d:=\left\{\sum_{i=1}^d\epsilon_ie_i:\ \epsilon_i\in \{0,1\}\mbox{ for }i=1,\dots , d\right\} $$ and $(e_i)_{i=1}^d$ the standard unit vectors in $\mathbb{R}^d$.

what is the asymptotics of the minimal number of (translates of) balls of radius $r>0$ convering $H^d$?

note that $H^d$ consists only of its vertices.

$\endgroup$
13
  • $\begingroup$ Do you want only the corners ($\epsilon_i\in\{0,1\}$) or the whole cube ($\epsilon_i\in[0,1]$)? $\endgroup$ Jan 8, 2015 at 20:43
  • $\begingroup$ only the corners $\endgroup$
    – dime
    Jan 8, 2015 at 20:44
  • 2
    $\begingroup$ You are asking about the smallest possible size of a (not necessarily linear) binary code of covering radius $1$. There are lots of results in this direction, just google to find them. $\endgroup$
    – Seva
    Jan 8, 2015 at 20:50
  • $\begingroup$ @seva thank you. yes, coding is the context for this question. i am looking for an elementary proof of a lower (asymptotic) bound. i would be very greatful if you could point me to a reference $\endgroup$
    – dime
    Jan 8, 2015 at 20:55
  • $\begingroup$ You can find a comprehensive account, say, in "Covering Codes" by G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein. $\endgroup$
    – Seva
    Jan 8, 2015 at 21:03

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.