2
$\begingroup$

Let $\Delta_n(x_1, \ldots, x_n)$ denote the Vandermonde determinant $\displaystyle \prod_{1 \leq i < j \leq n}(x_j - x_i)$. Let $c_1, \ldots, c_n$ and $K$ be nonnegative integers satisfying $$c_1 + \cdots +c_n = K + m\frac{n(n-1)}{2},$$ where $m$ is a positive integer. Then the coefficient of $x_1^{c_1}\cdots x_n^{c_n}$ in the polynomial $(x_1 + \cdots + x_n)^{K}\Delta_n(x_1^m, \ldots, x_n^m)$ is \begin{equation} \sum_{\sigma \in S_n}\mathrm{sgn}(\sigma)\frac{K!}{\prod_{i=1}^{n}(c_i - \sigma(i)m + m)!}. \end{equation} My questions are the following:

  1. Is it possible to express this coefficient as product of terms? We know that this is possible for $m = 1$ (see Lemma $9.8$ in Tao and Vu: Additive Combinatorics on page $336$) and in the case of $c_i = k-i$ for $i = 1, \ldots, n$ for any positive integer $m$ (see Lemma $9.9$ in Tao and Vu: Additive Combinatorics on page $336$).
  2. If that is not possible in general for $m \geq 2$, for which choices of $c_i$, is it possible (in particular for $m = 2$)?

Any help in this regard will be greatly appreciated. Thanks.

$\endgroup$

1 Answer 1

3
$\begingroup$

Note that $\Delta_n(x_1^m,\ldots,x_n^m)=\det(x_i^{k_j})$, where $k_j:=(j-1)m$. Two key observations are the following (both work for arbitrary non-negative integers $k_1<k_2<\ldots<k_n$, if $\sum c_j=\sum k_j+K$):

  1. (algebraic) $$\left[x_1^{c_1}x_2^{c_2}\ldots x_n^{c_n}\right](x_1+\ldots+x_n)^K\det(x_i^{k_j})=\frac{(K-\sum k_j)!}{\prod c_j!}\det(c_i^{\underline{k_j}}),\quad\quad\quad(\heartsuit)$$ where we use Knuth's notation $x^{\underline{n}}=x(x-1)\ldots(x-n+1)$. To prove $(\heartsuit)$, replace the polynomial $F:=(x_1+\ldots+x_n)^K\det(x_i^{k_j})$ to $$\tilde{F}= \left(x_1+\ldots+x_n-\sum k_j\right)^{\underline{K}}\det(x_i^{\underline{k_j}})$$ (which has of course the same highest degree coefficients as $F$)
    and apply this formula for the sets $A_i=\{0,1,\ldots,c_i\}$. Note that if $a_i\in A_i$, and $\tilde{F}(a_1,\ldots,a_n)\ne 0$, expanding the determinant we see that there must exist a permutation $\pi$ for which $a_i(a_i-1)\ldots (a_i-k_{\pi_i}+1)\ne 0$, i.e., $a_i\geqslant k_{\pi_i}$, in particular $\sum a_j\geqslant \sum k_j$. Further, $\sum a_j-\sum k_j$ is a non-negative integer which can not be equal to $0,1,\ldots,K-1$, thus $\sum a_j\geqslant \sum k_j+K=\sum c_j$. But $a_j\leqslant c_j$ for all $j$, thus this all is possible only if $a_j=c_j$ for all $j$. Therefore, in the RHS of the cited formula there is (at most) unique non-zero term, and this immediately gives $(\heartsuit)$.
  1. (combinatorial) If $c_1<c_2<\ldots<c_n$ are non-negative integers and $\sum c_j=\sum k_j+K$, then both parts of $(\heartsuit)$, which we denote by $\theta(c_1,\ldots,c_n)$ are equal to the number of paths from the point $(k_1,\ldots,k_n)$ to the point $(c_1,\ldots,c_n)$, for which each of $K$ paths constitutes of increasing exactly one coordinate by 1, and all intermediate points belong to a domain $\{(t_1,\ldots,t_n):t_1<t_2<\ldots<t_n\}$. This may be proved by induction on $K$ for fixed $k_1,\ldots,k_n$. The base case $K=0$ is clear. For the induction step, note that $\Theta$ satisfies a recurrence $$ \Theta(c_1,\ldots,c_n)=\Theta(c_1-1,c_2,\ldots,c_n)+ \Theta(c_1,c_2-1,\ldots,c_n)+\ldots+\Theta(c_1,c_2,\ldots,c_n-1), $$ which corresponds to considering the summand taken from the last bracket $x_1+\ldots+x_n$. And in RHS we may remove all summands in which $\Theta$ has two equal arguments (say, if $c_5-1=c_4$, remove the fifth summand), because they are anyway equal to 0, as is seen from RHS of $(\heartsuit)$ (or from general properties of antisymmetric polynomials, if you prefer.) Now exactly the same recurrence is enjoyed by the number of paths (consider the last step). This proves the induction step.

So, your question reduces either to computing the determinants, or computing the number of such paths. In combinatorics, such paths are traditionally viewed as skew standard Young tableaux: consider the Young diagrams $\lambda$ with row lengths $c_1\leqslant c_2-1\leqslant c_3-2\leqslant \ldots \leqslant c_n-(n-1)$ and $\mu$ with row lengths $k_1\leqslant k_2-1\leqslant k_3-2\leqslant \ldots \leqslant k_n-(n-1)$. Then the path corresponds to getting $\mu$ from $\lambda$ be consecutively adding the boxes, with a condition that on each step we get a Young diagram again. If you write the numbers $1,2,\ldots,K$ consequently when adding the boxes, you get what is called a skew standard Young tableaux.

Now $(\heartsuit)$ reads as Feit's determinantal formula for the number of skew standard Young tableaux, case $m=1$, that is, $\lambda=\emptyset$, corresponds to some variant of a hook length formula, and the case $c_j=\ell+j$ (up to permutation it is your second case) corresponds to counting skew standard Young tableaux of a shape which is a reverse Young diagram ($\mu$ is a rectangle), that is, again to hook length formula.

An interesting and rather enigmatic story is that there are other shapes for which the number of skew standard Young tableaux may be computed as a product formula. Some such cases were found in a series of papers by Igor Pak, Greta Panova and Alejandro Morales which you can find on Igor's homepage.

$\endgroup$
7
  • $\begingroup$ Thank you for the answer, nice explanation and relevant references. Actually, I was also interested in determining whether the coefficient is zero or not for distinct $c_i$ if we consider the polynomial over a finite field with characteristic $p$ and if we assume that $K < p$ and each $c_i < p$. The R.H.S. of $(\heartsuit)$ contains $\det(c_i^{\underline{k_j}})$. Can we hope that the coefficient in case of $m = 2$ will be nonzero for distinct $c_i$ subject to above conditions on $K$ and $c_i$? $\endgroup$
    – Rajkumar
    Oct 25, 2021 at 16:11
  • $\begingroup$ For $m=1$, this determinant is clearly Vandermonde determinant which has nice expression as products and it becomes easy to determine whether the expression is nonzero. $\endgroup$
    – Rajkumar
    Oct 25, 2021 at 16:12
  • $\begingroup$ For $m=2$ you can use the feature of the difference of square factorization. $\endgroup$ Oct 27, 2021 at 13:13
  • $\begingroup$ Say, for $n=2$ the determinant is 0 modulo $p$ if $c_1+c_2=p-1$ $\endgroup$ Oct 27, 2021 at 13:27
  • $\begingroup$ Sorry, I was asking regarding the factorisation of determinant part in the formula of coefficient in case of $m = 2$. Would you please elaborate the above comment? $\endgroup$
    – Rajkumar
    Oct 27, 2021 at 13:29

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.