8
$\begingroup$

Denote $\pmb{X}_n=(x_1,x_2,\dots,x_n)$. Consider the symmetric polynomial $$f_n(\pmb X_n)=\prod_{1\leq i<j\leq n}(x_i+x_j).$$ Expand these in terms of elementary symmetric polynomials, say $$f_n(\pmb{X}_n)=\sum_{\mu}c_{\mu,n}\cdot e_{\mu}(\pmb{X}_n).$$

For example, \begin{align*} f_3&=-e_{(3)}+e_{(2,1)} \\ f_5&=-e_{(5,5)}+2e_{(5,4,1)}+e_{(5,3,2)}-e_{(5,2,2,1)}-e_{(4,4,1,1)}-e_{(4,3,3)}+e_{(4,3,2,1)}. \end{align*}

QUESTION 1. Is it true that, for integers $n \geq 1$, we have $$\sum_{\mu}c_{\mu,2n+1}=0?$$

POSTSCRIPT. Fedor's reply (to Question 1) shown below suggests to me to ask:

QUESTION 2. Is it true that, for integers $n \geq 1$, we have $$\sum_{\mu}c_{\mu,2n}=(-1)^{\binom{n}2}?$$

$\endgroup$
  • $\begingroup$ The proofs given so far are great. Now I'd like to point out that $f_n(\boldsymbol{X}_n)$ is the generating function for simple graphs by degree sequence. For example, with $n=4$, the coefficient of $x_1x_2^3x_3^2x_4^2$ is the number of graphs with degree sequence $1,3,2,2$. It would be fun to prove the two claims by an argument based on graph manipulation, but I don't know how to do it. $\endgroup$ – Brendan McKay Mar 4 at 1:11
  • $\begingroup$ That is a very interesting idea. $\endgroup$ – T. Amdeberhan Mar 4 at 1:25
  • $\begingroup$ @BrendanMcKay I see how it is a generating function of out-degrees of tournaments. Is it what you mean? $\endgroup$ – Fedor Petrov Mar 4 at 22:22
  • $\begingroup$ @FedorPetrov, ooops you are correct. My error is all the more embarrassing given that I'm working on a paper about oriented graphs (with coauthors) that uses a generalisation of this. Thanks. $\endgroup$ – Brendan McKay Mar 4 at 23:54
10
$\begingroup$

Choose $n$ numbers $x_1,\dots,x_n$ for which all elementary symmetric polynomials are equal to 1 and substitute them to our $f_n$. We should get zero value for odd $n$. Well, what are these numbers? The roots of $x^{n}-x^{n-1}+x^{n-2}-\ldots-1=(x^{n+1}-1)/(x+1)$. This polynomial indeed has two roots with sum equal to 0 when $n$ is odd.

If $n=2k$ is even, we substitute the roots $w_1,\dots,w_n$ of the polynomial $f(x)=x^{2k}-x^{2k-1}+\ldots+1=(x^{2k+1}+1)/(x+1)=(x-w_1)\dots (x-w_n)$. Then your claim reads as $$A:=\prod_{1\leqslant i<j\leqslant n} (w_i+w_j)=(-1)^{\binom{k}2}.$$ This is done by the standard trick (and is well known itself). At first, $$ |A|^2=\prod_{i=1}^n \prod_{j\ne i,1\leqslant j\leqslant n}|w_i+w_j|=2^{-n}\prod_{i=1}^n \prod_{j=1}^n|(-w_i)-w_j|=2^{-n}\prod_{i=1}^n |f(w_i)|=\\=2^{-n}\prod_{i=1}^n\left|\frac{(-w_i)^{2k+1}+1}{-w_i+1}\right|=1, $$ since $1+(-w_i)^{2k+1}=2$ for all $i=1,2,\dots,n$ and $\prod_{i=1}^n (1-w_i)=f(1)=1$.

At second, we need to find the argument of the complex number $A$. This may be done for example as follows: all pairs $w_i+w_j$ for which $w_i$ and $w_j$ are not complex conjugate are partitioned onto complex conjugate pairs. In each pair the product is positive reals. If $w_i$ and $w_j$ are complex conjugate, the sum $w_i+w_j$ is a real number whose sign is the sign of the real part of $w_i$. Therefore $A$ is the real number whose sign equals $(1)^{m/2}$, where $m$ is the number of $w$'s in the left half-plane. It is easy to see that $m/2=[k/2]$ and that $(-1)^{[k/2]}=(-1)^{k(k-1)/2}$.

$\endgroup$
  • 4
    $\begingroup$ An alternative to your "standard trick" is to observe that $w_i + w_j = \dfrac{w_i^2 - w_j^2}{w_i - w_j}$. This yields $\prod\limits_{i<j} \left(w_i+w_j\right) = \dfrac{\prod\limits_{i<j}\left(w_i^2 - w_j^2\right)}{\prod\limits_{i<j}\left(w_i-w_j\right)}$. But the $n$ numbers $-w_1^2, -w_2^2, \ldots, -w_n^2$ are just a permutation of the $n$ numbers $w_1, w_2, \ldots, w_n$, and thus $\dfrac{\prod\limits_{i<j}\left(w_i^2 - w_j^2\right)}{\prod\limits_{i<j}\left(w_i-w_j\right)}$ equals a power of $-1$ times the sign of this permutation. Both are easy to compute. $\endgroup$ – darij grinberg Mar 2 at 21:26
  • 2
    $\begingroup$ Yes, this is another standard trick:) Actually possibly the shortest proof is to combine them: the absolute values equals 1 since the differences $w_i^2-w_j^2$ and $w_i-w_j$ are the same up to sign, and the sign may be obtained by looking at the argument. $\endgroup$ – Fedor Petrov Mar 2 at 21:38
6
$\begingroup$

Here is another method using more of the theory of symmetric functions. By Enumerative Combinatorics, vol. 2, Exercise 7.30, we have $f_n(\boldsymbol{X}_n)= s_{(n-1,n-2,\dots,1)}(\boldsymbol{X}_n)$ (a Schur function). By the dual Jacobi-Trudi identity, $$ s_{(n-1,n-2,\dots,1)} = \det[e_{n-2i+j}]_{i,j=1}^{n-1},\ \ (*) $$ where $e_0=1$ and $e_k=0$ for $k<0$. Since $e_k(\boldsymbol{X}_n)=0$ for $k>n$, it follows that $\sum_\mu c_{\mu,n}$ is obtained by substituting $e_1=e_2=\cdots=e_n=1$ and $e_{n+1}=e_{n+2}=\cdots=0$ into the right-hand side of (*). When $n$ is odd, the two middle rows of the determinant are equal (in fact, they are all 1's), so the determinant is 0. If $n=2m$ then subtract row $m-1$ from row $m$, then row $m-2$ from row $m-1$, up to row 1 from row 2. Also subtract row $m+2$ from row $m+1$, row $m+3$ from $m+2$, etc. The resulting matrix $A$ can be transformed into a triangular matrix $B$ with 1's on the diagonal by row and column permutations. The permutation indexing the 1's in $A$ that become the diagonal elements of $B$ is $1,3,5,\dots,n-1,2,4,6,\dots,n-2$, which has ${m\choose 2}$ inversions, and the proof follows.

$\endgroup$
  • $\begingroup$ This is a really cool alternative proof. Thanks, Richard! $\endgroup$ – T. Amdeberhan Mar 3 at 22:51
  • $\begingroup$ It looks interesting that again we get that the answer is the sign of the permutation $x\to 2x+1$ of residues modulo $n$, before establishing the explicit value $(-1)^{m\choose 2}$. $\endgroup$ – Fedor Petrov Mar 4 at 8:56
1
$\begingroup$

The polynomial in question is an instance of the Boolean product polynomials, which might give some extra insight. For example, I believe Lascoux have studied the Schur expansion of that exact expression.

$\endgroup$
  • $\begingroup$ Thanks for the pointers. $\endgroup$ – T. Amdeberhan Mar 4 at 22:50

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.