Signed Multinomial Expansion Coefficients?

I've been spending probably an undue amount of time trying to compute the coefficients of polynomials of the form $p_n(x_1, ..., x_n) = \displaystyle\prod_{\sigma \in \{ -1 , 1 \}^{n-1} } (x_1 + \displaystyle\sum_{i=2}^n \sigma_{i-1} \cdot x_i ) ,$ for $n\ge 3.$ $\sigma_i$ is simply the $i$th component of $\sigma .$ These polynomials arise naturally as the templates for minimial polynomials defining the critical point loci in the Fermat Weber problem. Clearly the resulting polynomial will be homogeneous of degree $2^{n-1},$ and arguing by symmetry shows that the coefficients of a particular monomial are invariant under permutation of the indices. It's not too hard, for instance, to see that the coefficients for terms of the form $x_i^{2^{n-1}}$ and $x_i^2x_j^{2^{n-1}-2}$ are $1$ and $-2^{n-2},$ respectively. Owing to the multitude of signs, I'm not seeing a clear way to compute really any other coefficients. - things I've considered using such as signed generalizations of the Vandermonde identity haven't quite been in the form I've needed, so if these turn out to actually be relatively easy to compute I'd be ecstatic to know how.

Solution 1:

This is more a comment than a full answer, but I had trouble fitting the long equations into a comment.

Let's use the notation $\left[x_1^{e_1}x_2^{e_2}\ldots x_n^{e_n}\right]p_n(x_1,x_2,\ldots,x_n)$ to mean the coefficient of $x_1^{e_1}x_2^{e_2}\ldots x_n^{e_n}$ in $p_n(x_1,x_2,\ldots,x_n)$. By pairing up factors in the product that differ only in the sign of $x_n,$ we see that the power of $x_n$ is even in every term. (Each pair is of the form $[f(x_1,x_2,\ldots,x_{n-1}]^2-x_n^2.$) By the symmetry you observe for $n\ge3,$ this is true of $x_j$ for every $j$.

We can show that $$\left[x_1^{2^{n-1}-2j}x_2^{2j}\right]p_n(x_1,x_2,\ldots,x_n)=(-1)^j\binom{2^{n-2}}{j}.$$ This can be deduced from $$\begin{aligned}\left[x_1^{2^{n-1}-2j}x_2^{2j}\right]p_n(x_1,x_2,\ldots,x_n)&=\left[x_1^{2^{n-1}-2j}x_2^{2j}\right]p_n(x_1,x_2,0,\ldots,0)\\ &=\left[x_1^{2^{n-1}-2j}x_2^{2j}\right](x_1+x_2)^{2^{n-2}}(x_1-x_2)^{2^{n-2}}\\ &=\left[x_1^{2^{n-1}-2j}x_2^{2j}\right](x_1^2-x_2^2)^{2^{n-2}}.\end{aligned}$$ I believe that $\left[x_1^{2^{n-1}-2}x_2^2\right]p_n(x_1,x_2,\ldots,x_n)$ should therefore be $-2^{n-2}$ rather than $-2^{n-3}.$

Interestingly, there appears to be a relatively simple expression for the coefficient of a term in which at most three indeterminates appear. This is a guess at this point: $$\left[x_1^{2i}x_2^{2j}x_3^{2k}\right]p_n(x_1,x_2,\ldots,x_n)=(-1)^{j+k}\binom{i+j+k}{i,j,k}\prod_{\ell=0}^{k-1} \frac{i-j+k-2\ell-1}{i+j+k-2\ell-1},$$ where $i+j+k=2^{n-2}.$ Some experimentation reveals that this expression is symmetric under interchange of $i$, $j$, and $k$, although this is not manifest.

Update (25 March 2013). The symmetry under permutation of the expression for the three-indeterminate coefficient was explained by Darij Grinberg in an answer to this question. The function $Q$ that appears in that answer is precisely the double factorial, as defined by many authors. In particular, if the double factorial is defined in terms of the Gamma function as $$n!!:=\sqrt{\frac{2^{n+1}}{\pi}}\Gamma\left(\frac{n}{2}+1\right),$$ which is consistent with the usual definition for positive odd integers, $(2n-1)!!:=(2n-1)(2n-3)\ldots3\cdot1,$ then the value for negative odd integers matches that given by $Q.$ Using Darij Grinberg's suggestion, we then get $$\begin{aligned}&\left[x_1^{2i}x_2^{2j}x_3^{2k}\right]p_n(x_1,x_2,\ldots,x_n)=\binom{i+j+k}{i,j,k}\frac{(-1)^{(i+j+k)/2}}{\pi}\\ &\quad\times\frac{\Gamma\left(\frac{-i+j+k+1}{2}\right)\Gamma\left(\frac{i-j+k+1}{2}\right)\Gamma\left(\frac{i+j-k+1}{2}\right)}{\Gamma\left(\frac{i+j+k+1}{2}\right)}.\end{aligned}$$ The reciprocal of the ratio involving Gamma functions is almost, but not quite, a generalized trinomial coefficient - "not quite" because the sum of the three arguments in the numerator would have to be greater by 2 than the argument in the denominator for that to be the case, whereas, in fact, it is greater only by 1. (The factor $\pi=\Gamma(\frac{1}{2})\Gamma(\frac{1}{2})$ in the denominator possibly compensates for this.)

A conjecture for the coefficient of the four-indeterminate terms along the same lines, and obtained by a similar style of guesswork/curve fitting is that, for $n\ge4,$ $i,j,k,\ell\ge0,$ $i+j+k+\ell=2^{n-2},$ we have $$\begin{aligned}&\left[x_1^{2i}x_2^{2j}x_3^{2k}x_4^{2\ell}\right]p_n(x_1,x_2,\ldots,x_n)\\ &\quad=(-1)^{j + k + l} \binom{i+j+k+\ell}{i,j,k,\ell}\frac{1}{\prod_{m=0}^{\ell-1}(i+j+k+\ell - 4 m - 2)}\\ &\quad\phantom{=}\times\sum_{t=0}^{\ell} 2^t t! \binom{k}{t}\binom{l}{t}\prod_{m=0}^{t-1}( i+j+k+\ell-4m) \prod_{m=0}^{\ell-t-1}(i+j+k+\ell-4k-4m-2)\\ &\quad\phantom{=\times\sum}\times\frac{\prod_{m=t}^{k+\ell-t-1}(i+j+k+\ell-2j-2m-1)}{ \prod_{m=0}^{k+\ell-t-1}(i+j+k+\ell-2m-1)}.\end{aligned}$$ As in the three-indeterminate case, the value of the expression is invariant under permutation of $i,j,k,\ell,$ although again this is not manifest. Whether these guesses lead to a general expression remains to be seen. It is somewhat encouraging that the same sorts of products keep making an appearance, but discouraging that a sum now appears. Finding a more symmetric way of writing this expression may shed some light on what's going on. Obviously an understanding of how these expressions can be derived would be helpful.

Solution 2:

I can dig slightly deeper than the OP. Enumerate all elements of the form $\pm x_1 \pm x_2 \pm \ldots \pm x_n$ in the lexicographic order, starting with $r_1=-(x_1+x_2+x_3+ \ldots +x_{n-1}+x_n)$ and ending with $r_{2^n}=-r_1$. Let $R=\lbrace r_k | 1 \leq k \leq 2^n\rbrace$ and $P(X)=\prod_{r\in R}(X-r)$. Then the expansion of $P$ starts as follows :

$$ P=X^{2m}-(mS_2)X^{2m-2}+(\binom{m}{2}S_4+m(m-3)S_{2,2})X^{2m-4} -(\binom{m}{3}S_6+\frac{m(m-2)(m-5)}{2}S_{2,4}+m(m^2-9m+30)S_{2,2,2})X^{2m-6} + (...) $$

where $m=2^{n-1}$ and for any nondecreasing sequence $i_1 \leq i_2 \leq \ldots \leq i_t$, $S_{i_1,i_2, \ldots ,i_t}$ denotes the sum of all monomials of multidegree $(i_1,i_2, \ldots ,i_t)$ with indeterminates in $x_1,x_2, \ldots ,x_n$.