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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.