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

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.

• To prove the divisibility, just argue that the first $m$ derivatives at $1$ are zero, being $n$-th finite differences of polynomials of degree $<n$. – darij grinberg Mar 29 '18 at 0:23
• @ZachTeitler Thank you for your precious comment. These sequences cannot be found on OEIS. Since I'm almost null on Hilbert functions, the complexity now goes beyond my expectation... I have updated the question and added explicit formulas for these numbers. Is it possible to confirm that these are exactly the Hilbert functions? – WhatsUp Mar 29 '18 at 16:23
• @ZachTeitler: By "Hilbert function of an ideal", do you mean "Hilbert function of the quotient ring modulo this ideal"? (Since otherwise, how do you get a polynomial?) Also, what is $k\left[\mathbb{P}^h\right]$? I thought projective spaces weren't affine varieties... – darij grinberg Mar 29 '18 at 21:27
• @darijgrinberg My understanding is, e.g. in the case $m=3$, you take the quotient of $k[X_0, X_1, X_2]$ by $6$ homogeneous polynomials of degree $5$, and look at the Hilbert function of this quotient. I can verify Zach Teitler's claim for $m=2, 3$, by taking some random homogenenous polynomials. However, I don't know how to do the calculation in the general case. – WhatsUp Mar 29 '18 at 21:40
• @WhatsUp : I don't understand your formula for $a_{m,k}$. The upper part of the second binomial coefficient, $m-1+k-2mj+j^2$, seems to be negative most of the time, and the usual convention is that the binomial coefficient is zero in that case. – Timothy Chow Mar 30 '18 at 21:14

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.

• Great job! Taking derivative w.r.t. $X$ was my blind spot, because $k(n-k)-1$ looks chaotic... With your method, I am able to work out explicit formulas for the coefficients, and surprisingly Zach Teitler noticed (without proof) that the coefficients are Hilbert functions... I have updated the question with these points. – WhatsUp Mar 29 '18 at 16:28

$\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.

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}$$

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).

• For given $m \geq 4$, the two polynomials only agree up to degree $4(m-1)$. And it seems that my series is always bigger. But I don't know how to verify Fröberg's conjecture directly... For example, how do I calculate this Hilbert function in case $m=4$ (without assuming the conjecture)? – WhatsUp Apr 1 '18 at 21:31
• @WhatsUp : "Generic" just means that the coefficients are all algebraically independent, so in principle you can let the coefficients be independent indeterminates and compute the resulting Hilbert function. In practice an easier way is to pick random integer coefficients and hope you get the predicted Hilbert function; that suffices because Fröberg showed that any Hilbert function is at least equal to the one in the conjecture. (So by the way, there could still be some ideal whose Hilbert function is given by your $a_{m,k}$; it just won't be generated by generic forms.) – Timothy Chow Apr 2 '18 at 15:11
• Ugh, I made the error, not you. Sorry. I was too careless. – Zach Teitler Apr 2 '18 at 15:52

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$.

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!

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.$$