On the polynomial $\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}$

Question

Let $n = 2m$ be an even integer and let $F_n(X)$ be the polynomial $$F_n(X):=\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}.$$ I observed (but cannot prove) that the polynomial $F_n$ is always divisible by $(1-X)^m$, and the quotient $F_n(X)/(1-X)^m$ always has positive coefficients.

---

Similarly, with $m, n$ as above, let $G_n(X)$ be the polynomial $$G_n(X):=\sum_{k=0}^n\binom{n}{k}(-1)^k X^{(k+1)(n-k)}.$$ Since all the exponents of $X$ are even, the polynomial $G_n$ is essentially a polynomial of $X^2$.

Now it turns out (still without proof) that $G_n$ is always divisible by $(1-X^2)^m$, and the quotient $G(X)/(1-X^2)^m$ always have positive coefficients.

---

Are these polynomials well known? Could someone give a proof of any of the assertions?

My ideas

I spent some time on this, trying to attack by establishing recurrence relations among them, as well as looking at the generating functions (i.e. $\sum F_nT^n$).

I also noted that they are both special values of the polynomial $$H_n(X,Y):=\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}Y^k.$$

However, all my usual tools eventually failed, because of the strange exponent $k(n-k)$ (which is morally $k^2$). I only have seen this kind of exponent in Jacobi triple product before, but that is also not quite relevent...

---

To give some examples:

\begin{eqnarray*} F_2(X) &=& 2(1-X)\\ F_4(X) &=& 2(1-X)^2(1 + 2X + 3X^2)\\ F_6(X) &=& 2(1-X)^3(1 + 3X + 6X^2 + 10X^3 + 15X^4 + 15X^5 + 10x^6)\\ F_8(X) &=& 2(1-X)^4(1 + 4X + 10X^2 + 20X^3 + 35X^4 + 56X^5 + 84X^6 + 112X^7 + 133X^8 + 140X^9+126X^{10}+84X^{11}+35X^{12})\\ \\ G_2(X) &=& (1-X^2)\\ G_4(X) &=& (1-X^2)^2(1+2X^2)\\ G_6(X) &=& (1-X^2)^3(1+3X^2+6X^4+5X^6)\\ G_8(X) &=& (1-X^2)^4(1+4X^2+10X^4+20X^6+28X^8+28X^{10}+14X^{12}) \end{eqnarray*}

The examples are calculated using sagecell.

---

UPDATE

Using the method of Joe Silverman, I am able to prove the following: $$ F_{2m}(X)=2(1-X)^m(a_{m,0} + a_{m,1}X + a_{m,2}X^2 + \cdots),$$ where the coefficients $a_{m,k}$ are given by: $$a_{m,k} = \frac{1}{2}\sum_{j = 0}^{\infty}(-1)^j\binom{2m}{j}\binom{m-1+k-2mj+j^2}{m-1}.$$

Here the convention is that $\binom{z}{y} = 0$ for all integers $z < y$.

A remark: since the degree of $F_{2m}$ is equal to $m^2$, we must have $a_{m,k} = 0$ for all $k > m^2-m$. This, however, is not obvious from the above explicit formula...

For $k \leq m^2-m$, the above formula can also be written as $$a_{m,k} = \sum_{j = 0}^{m}(-1)^j\binom{2m}{j}\binom{m-1+k-2mj+j^2}{m-1}.$$

Now the problem is to show that all the $a_{m,k}$ are positive. According to the comment of Zach Teitler, we have the following guess:

For fixed $m$, the function $k\mapsto a_{m,k}$ is the Hilbert function of an ideal of $k[\mathbb{P}^{m-1}]$ generated by $2m$ general degree $2m-1$ forms.

The positivity of all $a_{m,k}$ would follow from this, since the Hilbert functions, being dimensions, are positive.

Answer 1

It is clear that $F_n(1)=0$. On the other hand, the derivative can be expressed in terms of $F_{n-2}$. Thus $$ \begin{aligned} F_n'(X) &=\sum_{k=0}^n\binom{n}{k}(-1)^k(k(n-k))X^{k(n-k)-1} \\ &= \sum_{k=1}^{n-1} \frac{n!}{(k-1)!(n-k-1)!} (-1)^k X^{k(n-k)-1} \\ &= n(n-1) \sum_{k=1}^{n-1} \frac{(n-2)!}{(k-1)!(n-k-1)!} (-1)^k X^{k(n-k)-1} \\ &= n(n-1) \sum_{k=1}^{n-1} \binom{n-2}{k-1}(-1)^k X^{k(n-k)-1} \\ &= n(n-1) \sum_{k=0}^{n-2} \binom{n-2}{k}(-1)^k X^{(k+1)(n-k-1)-1} \\ &= n(n-1) \sum_{k=0}^{n-2} \binom{n-2}{k}(-1)^k X^{k(n-2-k)+n-2} \\ &= n(n-1)X^{n-2}F_{n-2}(X). \\ \end{aligned} $$ Repeating, one find that the $\ell$'th derivative of $F_n(X)$ is a $\mathbb Z[X]$ linear combination of $F_{n-2}(X),\ldots,F_{n-2\ell}(X)$. So it vanishes at $X=1$ until you get to $\ell=n/2$. Possibly one can get the positivity of the coefficients from this recursion, too, but I haven't tried.

Answer 2

$\def\gz{\frac{z^n}{(1+X)^{\binom n2}n!}} \def\tgz{{z^n}/{(1+X)^{\binom n2}n!}}$ Here's a combinatorial proof of the divisibility property for $F_n(X)$. It's enough to show that $$F_n(1+X) = \sum_{k=0}^n \binom nk (-1)^k (1+X)^{k(n-k)}$$ is divisible by $X^m$ for $n=2m$. It's clear that $F_n(1+X)$ counts ordered partitions $(A,B)$ of $[n]=\{1,2,\dots,n\}$ together with a set of edges joining $A$ and $B$, where the weight of such graph with $e$ edges is $(-1)^{|A|}X^e$. We define a sign-reversing involution on the set of these graphs with at least one isolated vertex: move the least isolated vertex from $A$ to $B$ or from $B$ to $A$. The only graphs that aren't canceled are those with no isolated vertices. A graph with $n$ vertices and no isolated vertices must have at least $\lceil n/2\rceil$ edges, so $F_{2m}(1+X)$ is divisible by $X^m$. Unfortunately, there is further cancellation, so this argument does not prove that $(-1)^m F_{2m}(1+X)$ has nonnegative coefficients (which is weaker than the OP's proposed nonnegativity condition).

Here is another proof that $F_{2m}(1+X)$ is divisible by $X^m$ that is not as simple but may be more interesting. Let $$J(z) = \sum_{n=0}^\infty \gz.$$ Then $$\sum_{n=0}^\infty F_n(1+X)\gz = J(z) J(-z).$$ We call generating functions of the form $\sum_{n=0}^\infty u_n \tgz$ graphic generating functions, as they arise in counting graphs and digraphs of various kinds. It is known that $1/J(-z)$ is the graphic generating for acyclic digraphs, where edges are weighted by $X$, and $-\log J(-z)$ is the graphic generating for initially connected acyclic digraphs (acyclic digraphs in which there is a directed path from the vertex with the least label to every other vertex). See here for some discussion of these generating functions. Thus $-\frac12(\log J(z)+\log J(-z))$ is the graphic generating function for initially connected acyclic digraphs with an even number of vertices and thus (by the exponential formula for graphic generating functions) $$\frac{1}{\sqrt{J(z)J(-z)}}\tag{$*$}$$ is the graphic generating function for acyclic digraphs in which every initially connected component has an even number of vertices. Such a digraph with $2m$ vertices must have at least $m$ edges, so the coefficient of $\tgz$, where $n=2m$, in $(*)$ is divisible by $X^m$. It follows that the same is true for $J(z)J(-z)$. But this argument does not give a combinatorial interpretation for $J(z)J(-z)$ nor does it prove positivity.

Answer 3

The divisibility is easy to prove and a more general phenomenon. Let $Y=1-X$, then $$F_n(X) = \sum_{k=0}^n (-1)^k \binom nk (1-Y)^{k(n-k)}=\sum_{r\ge 0} (-1)^r a_{r,n}Y^r$$ where $$a_{r,n} = \sum_{k=0}^n (-1)^k \binom{n}{k}\binom{k(n-k)}{r}.$$ Note that $a_{r,n}$ is the $n$-th difference of a polynomial in $k$ of degree $2r$, so $a_{r,n}=0$ for $n\gt 2r$.

It means you can use any quadratic function of $k$ in place of $k(n-k)$ and the result is still divisible by $(1-X)^m$.

With some mucking around, we can find the coefficients of the quotient. $$F_n(X)/(1-X)^m = \sum_{t=0}^{m(m-1)} b_{m,t} X^t,$$ where $$b_{m,t} = \sum_{k:k(n-k)\ge m+t} (-1)^{k+m}\binom nk\binom{k(n-k)-t-1}{m-1}.$$ This still hasn't proved that $b_{m,t}\ge 0$. Note that if the sum is taken over the full range $0\le k\le n$, it is 0; I suspect this is a vital clue.

Thus, $b_{m,t}$ is $(-1)^m$ times the $n$-th difference wrt $k$ of $$f_{m,t}(k) = \begin{cases} \binom{k(n-k)-t-1}{m-1}, & \text{if }k(n-k)\ge m+t; \\ 0, & \text{otherwise}. \end{cases}$$

Answer 4

This is a comment on Zach Teitler's question about Hilbert functions.

Fröberg's conjecture implies, as a special case, that the Hilbert function of an ideal generated by $2m$ general degree-$(2m−1)$ forms in $\mathbb{C}[\mathbb{P}^{m−1}]$ is obtained by taking the low-order coefficients of the polynomial $$\frac{(1-t^{2m-1})^{2m}}{(1-t)^m}$$ until you hit a term $a_i t^i$ with $a_i < 0$ (and the Hilbert function $h(j)=0$ for all $j\ge i$). I believe that the conjecture is open even in this special case (the best partial result I know of is by Nicklasson), but using the explicit formula, we can go ahead and compute the predicted Hilbert functions for small $m$ anyway. $$1, 2, 3 \quad (m=2)$$ $$1, 3, 6, 10, 15, 15, 10 \quad (m=3)$$ $$ 1, 4, 10, 20, 35, 56, 84, 112, 133, 140, 126, 84, 7 \quad (m=4)$$ $$ 1, 5, 15, 35, 70, 126, 210, 330, 495, 705, 951, 1215, 1470, 1680, 1800, 1776, 1545, 1035, 210 \quad (m=5)$$ On the other hand, your formula for $a_{m,k}$ (when we correct the factor of 2) yields the following numbers. $$1, 2, 3 \quad (m=2)$$ $$1, 3, 6, 10, 15, 15, 10 \quad (m=3)$$ $$ 1, 4, 10, 20, 35, 56, 84, 112, 133, 140, 126, 84, 35 \quad (m=4)$$ $$ 1, 5, 15, 35, 70, 126, 210, 330, 495, 705, 951, 1215, 1470, 1680, 1800, 1776, 1590, 1260, 840, 420, 126 \quad (m=5)$$ The agreement is pretty striking, but isn't perfect even for $m=4$ (so my calculation disagrees with Zach Teitler's in this case; if I've made an error then I hope that he can point it out).

Answer 5

By construction, for each one of those polynomials, the sequence $(a_n,...,a_0)$ of its coefficients is "piecewise polynomial" of degree $m$. More precisely, instead of differentiating as in Joe Silverman's approach, we can define a difference operator $D$ of a polynomial $f(x)=a_nx^n +\cdots+a_0$ by $$Df(x):=(a_n-a_{n-1})x^{n-1}+\cdots+(a_1-a_0).$$ Then most coefficients of the iterated $d_m(x):=D^mF_{2m}(x)$ vanish. More precisely, computations seem to show that $$ D^mF_{2m}(x)=2\sum_{k=1}^{m-\lceil\sqrt{m}\rceil}(-1)^k\binom {2m}k x^{(2k-1)m-k^2},$$ e.g. for $m=3,...,7$ these are $$\begin{align} d_3(x)&=-6x^2 \\ d_4(x)&=- 8x^3 +28x^8 \\ d_5(x)&= - 10x^4+45x^{11} \\ d_6(x)&= - 12x^5+ 66x^{14 }-220x^{21} \\ d_7(x)&= - 14x^6 + 91x^{17}- 364x^{26} +1001x^{33}. \end{align} $$ The intriguing irregularity is of course the $m-\lceil\sqrt{m}\,\rceil$ in the summation, causing that for $m=j^2$ and $m=j^2+1$, both of these polynomials have the same number of terms. Note that these numbers are, up to an offset 1, the $m-\lfloor\sqrt{m}\rfloor$ of OEIS 028391. I can't see any explanation for this...

In the preceding stage (i.e. applying $D$ only $(m-1)$ times), the coefficients are "piecewise constant", and we have apparently $$\frac12(x-1)D^{m-1}F_{2m}(x)=\\(-1)^{m+1}\binom {2m-1}{m-3}x^{(m-1)^2+1} - \left(\sum_{k=1}^{m-\lceil\sqrt{m}\rceil}(-1)^k\binom {2m}k x^{(2k-1)m-k^2+1}\right)-1.$$ Note that for $m=j^2+1$, the first term and the biggest term of the sum must be "merged", having the same power of $x$).
Possibly by applying the inverse difference operator $m$ times to $d_m$ and adding at each step the appropriate boundary term $a_0$ (seems to be just $\binom m1,\binom m2,...,\binom mm$), we can arrive at a proof not only of the positivity, but also of the conjectured unimodularity of $F_n$.

Doing similarly for $G_n$ (taken as polynomials in $x^2$), the corresponding $n$th iterated differences yield polynomials of a similar lacunarity, with coefficients slightly more complicated: $$D^mG_{2m}(x)=\sum_{k=1}^{m - \lfloor\frac{\sqrt{8m + 1} - 1}2\rfloor}(-1)^k\frac{2m+1-2k}{2m+1}\binom{2m+1}k x^{(k-1)(2m-k)} .$$ For this one, the number of terms features the triangular numbers instead of the squares, with the same number of terms for $m=\binom j2$ and $m=\binom j2+1$.

Answer 6

From \begin{align} F_{2m}(X)=\sum_{k=0}^{2m}(-1)^k\binom{2m}{k}X^{k(2m-k)} \end{align} we have \begin{align} (-1)^mX^{m^2}F_{2m}(1/X)&=\sum_{k=0}^{2m}(-1)^{m+k}\binom{2m}{k}X^{(m-k)^2}\\ &=\binom{2m}{m}+2\sum_{k=1}^m(-1)^k\binom{2m}{m-k}X^{k^2}\\ &=\binom{2m}{m}\sum_{k=-m}^m(-1)^k\frac{m!^2}{(m-k)!(m+k)!}X^{k^2}. \end{align} Therefore, to determine the properties we hoped, its clearly that we just need to show that the polynomial \begin{align} G_{m}(X):=\sum_{k=-m}^m(-1)^k\frac{m!^2}{(m-k)!(m+k)!}X^{k^2}=1+2\sum_{k=1}^m(-1)^k\alpha_kX^{k^2} \end{align}
with $m\in\mathbb{N}$ and $$\alpha_k=\frac{m!^2}{(m-k)!(m+k)!}=\frac{m(m-1)\dots(m-k+1)}{(m+1)(m+2)\dots(m+k)},\; k=1,2,\dots,m$$ has same properties to $F_{2m}(X)$ which we expected.

Remark. We see that $$\lim_{m\rightarrow \infty}G_{m}(X)=\sum_{k\in\mathbb{Z}}(-1)^kX^{k^2}=\prod_{k\ge 1}(1-X^k)(1-X^{2k-1})$$ with $|X|<1$ is the well known Jacobi Theta function.

To be continue!

Answer 7

Here is a proof for the positivity of coefficients. Suppose that $$F_{2m}\,(x)=2(1-x)^m\sum_ka_{m,k}\,x^k,$$ where $a_{m,k}=0$ if $k<0$ or $k>m^2-m$. We shall show that $a_{m,k}>0$ for all other $k$.

First of all, a negative sign was missed in Joe Silverman's deduction from the third last step. The correct formula is $$F_n'(x)=-n(n-1)x^{n-2}F_{n-2}\,(x).$$ Using this, the derivative of $F_{2m}(x)$ is \begin{align} F_{2m}'\,(x) &=-2m(2m-1)x^{2m-2}F_{2m-2}\,(x)\\ &=-2(1-x)^{m-1}\sum_{k}2m(2m-1)a_{m-1,\,k-2m+2}\ \ x^{k}. \end{align} The derivative can be computed alternatively as \begin{align} F_{2m}'(x) &=-2m(1-x)^{m-1}\sum_{k}a_{m,k}x^k+2(1-x)^m\sum_{k}a_{m,k}\ k\,x^{k-1}\\ &=2(1-x)^{m-1}\sum_{k}(\,(k+1)a_{m,\,k+1}-(m+k)a_{m,k}\,)\ x^k. \end{align} Comparing the coefficient of $x^k$ in the sums of the above two formulas we find $$a_{m,k}=\frac{2m(2m-1)a_{m-1,\,k-2m+2}\,+(k+1)a_{m,\,k+1}}{m+k},\quad \text{for $m\ge1$}.$$ The initial value to use this recurrence for each $m$ is the leading coefficient of the sum part in $F_{2m}(x)$, that is, $$a_{m,\,m^2-m}=\frac{1}{2}\binom{2m}{m}=\binom{2m-1}{m},\quad\text{for $m\ge1$}.$$ which is a positive integer. The desired positivity follows from the recurrence immediately by induction on $m$.

For instance, by the initial value formula, we have $a_{1,0}=1>0$. That is all we need to show for $m=1$. For $m=2$, we have $a_{2,2}=3$. Using the recurrence formula for $m=2$, we obtain $$ a_{2,1}=\frac{12a_{1,-1}+2a_{2,2}}{3}=2\quad\text{and}\quad a_{2,0}=\frac{12a_{1,-2}+a_{2,1}}{2}=1.$$ For $m=3$, the initial value formula gives $a_{3,6}=10$; the recurrence formula allows us to compute $a_{3,k}$ for $k=5,4,3,2,1,0$ one by one: $$a_{3,5}=\frac{30a_{2,1}+6a_{3,6}}{8}=15,\quad a_{3,4}=\dots.$$