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!


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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.