Counting with tensor products

Question

Suppose I've got vectors $v = (1,-1)$ and $w = (1,1)$ and any $m \in \mathbb{N}$. Let $a = v \otimes v \otimes w^{\otimes m}$ and let $\tilde{a}$ be the sum over all $\binom{m}{2}$ unique vectors obtained by permuting the tensor coordinates of $a$. I'm interested in identifying the asymptotics of a function $f(m) = \|\tilde{a}\|_1$ where $\|\cdot\|_1$ is the usual $1$-norm in terms of $m$.

For example, when $m=0$, we simply have $\tilde{a} = v \otimes v$ and so $f(0) = 4$.

When $m=1$ we have $\tilde{a} = v \otimes v \otimes w + v \otimes w \otimes v + w \otimes v \otimes v$ and one can check that $f(1) = 12$.

When $m = 2$ we have $$\tilde{a} = v \otimes v \otimes w \otimes w + v \otimes w \otimes v \otimes w + v \otimes w \otimes w \otimes v\\+ w \otimes v \otimes v \otimes w + w \otimes v \otimes w \otimes v + w \otimes w\otimes v \otimes v$$

and one can check that $f(2) = 24$.

The problem seems simple, but I'm having a tough time finding a nice expression approximating $f(m)$. It seems related to some type of signed Chu-Vandermonde identity. Any insights or suggestions are appreciated. Thank you!

Answer 1

You are looking at the vector of coefficients of the polynomial $$\sum_{\epsilon}\prod_{i=1}^{m+2}(1-\epsilon_i x_i)$$ where $\epsilon$ runs over all choices of signs $\pm$ provided there are exactly two $-$ signs. There are $\binom{m+2}{2}$ terms being summed. After expanding we get a multilinear symmetric polynomial in the $x_i$'s. this tells us that since we only care about the $|\cdot|_1$ norm, we can set all $x_i=t$ and observe the expression becomes $$\binom{m+2}{2}(1-t)^2(1+t)^m.$$ The coefficient of $t^k$ is $$\binom{m+2}{2}\left[\binom{m}{k}-2\binom{m}{k-1}+\binom{m}{k-2}\right]=\frac{1}{2}\binom{m+2}{k}\left[(m-k+1)(m-k+2)+k(k-1)-2k(m-k+2)\right]=\frac{1}{2}\binom{m+2}{k}\left[(m-2k+2)^2-2-m\right]$$ which means these coefficients are positive everywhere except in the interval $$\frac{m+2-\sqrt{m+2}}{2}<k<\frac{m+2+\sqrt{m+2}}{2}.$$ Therefore the $|\cdot|_1$ norm of the sequence of coefficients telescopes everywhere except at the endpoints of this interval. Denoting $s=\frac{m-\sqrt{m+2}}{2}$ we have that your $f(m)$ is equal to $$4\binom{m+2}{2}\left[\binom{m}{s}-\binom{m}{s-1}\right]$$ and you can approximate this with Stirling to get asymptotics of desired accuracy.