We define the $s$-sparse hypercube in $\mathbb{R}^d$ as \begin{align} \mathbb{H}_s = \bigl \{ {\bf{v}} \in \{ -1, 0 , 1\}^d \colon \| {\bf{v}} \|_0 = s \bigr\}, \end{align} where $ \| {\bf v} \|_0 $ is the number of nonzeros of vector ${\bf v}$. Note that $\mathbb{H}_s$ contains ${d \choose s}\cdot 2^s$ elements. I was wondering what is the structure of $ |\langle {\bf v}_1 , {\bf v}_2 \rangle| $ for $ {\bf v}_1 , {\bf v}_2 \in \mathbb{H}_s$.

For any fixed ${\bf v}$, define $$ M_k = \#\bigl \{ {\bf v}_1 \in \mathbb{H}_s\colon | \langle {\bf v}_1 , {\bf v} \rangle| = k \bigr\} $$ as the number of vectors in $\mathbb{H}_s$ whose inner product with ${\bf v}$ is $k$ or $-k$. Here $k \in \{ 0, 1,\ldots, s\}$.

I was wondering if we can derive some upper bound on $M_k/ M_{k-1}$ for all $k$. Or can we directly compute $M_k$ or derive some simple upper bound that can tell us the growth of this number?

From a probabilistic point of view, if ${\bf v}$ is uniformly taken over $\mathbb{H}_s$, what is the distribution of $M_k$ like?

  • $\begingroup$ $M_k/2$ is a coefficient of $x^st^k$ in $(1+tx+x/t)^s (1+2x)^{n-s}$. $\endgroup$ – Fedor Petrov Apr 7 '16 at 21:23
  • $\begingroup$ It would be wonderful to have this explained in a full answer. I can see the $t$ and $t^{-1}$ account for +1 and -1, in up to $s$ positions (thus raise to power $s$) but how does the $(1+2x)$ term work? $\endgroup$ – kodlu Apr 7 '16 at 22:15
  • $\begingroup$ @kodlu each other coordinate is 0, +1 or -1, this is what $1+2x$ is about: 1 is for 0, $x$ for +1, $x$ for -1. $\endgroup$ – Fedor Petrov Apr 8 '16 at 6:54
  • $\begingroup$ Ah, $n-s$ should be of course $d-s$. $\endgroup$ – Fedor Petrov Apr 8 '16 at 6:56
  • $\begingroup$ Definitely $M_k$ does not depend on $\bf{v}$. $\endgroup$ – Fedor Petrov Apr 8 '16 at 6:57

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.