# Growth of inner products between two random vectors on the sparse hypercube

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?

• $M_k/2$ is a coefficient of $x^st^k$ in $(1+tx+x/t)^s (1+2x)^{n-s}$. – Fedor Petrov Apr 7 '16 at 21:23
• 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? – kodlu Apr 7 '16 at 22:15
• @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. – Fedor Petrov Apr 8 '16 at 6:54
• Ah, $n-s$ should be of course $d-s$. – Fedor Petrov Apr 8 '16 at 6:56
• Definitely $M_k$ does not depend on $\bf{v}$. – Fedor Petrov Apr 8 '16 at 6:57