4

How many coefficients of the polynomial $P_n(x_1,...,x_n) = \prod_{1\leq i < j \leq n}(x_i+x_j)$ are odd?

I computed a couple small cases first. for $n = 1$ the problem doens't make sense. For $n=2$ there are 2 odd coefficients, and for $n = 3$ there are 6. I'm pretty sure I need to plug something in for $x_i$ and do some modular arithmetic but I'm not sure what I need to do.

Some hints would be greatly appreciated.

Math_Day
  • 1,227
  • maybe you can generalize the identity $\prod_{i=1}^n(x_i+1)=\sum_{S\subseteq [n]}\prod_{i\in S}x_i$, where $\prod_{i\in \emptyset}x_i=1$, in the right way? This also looks like a Vandermond determinant https://en.wikipedia.org/wiki/Vandermonde_matrix so maybe that's another way to think about it.... – Condo Jan 21 '21 at 16:00
  • For $n=4$ the answer is $24$, so I'm going to guess $n!$ – saulspatz Jan 21 '21 at 16:27
  • Please provide a source. Is this an on-going contest? – Neat Math Jan 21 '21 at 17:44
  • I can confirm that the sequence is identical to $n!$ for $n\leq 8$. Larger values take too long to compute with my python script. – Aldoggen Jan 21 '21 at 17:54
  • 1
    For $n=5$ they are $120$. They are definitely $n!$ @saulspatz – Raffaele Jan 21 '21 at 18:02
  • @Raffaele It works up through $n=7$ Then my script gets too slow. (Also, all the odd coefficients equal $1$.) I'm fairly sure I know how to prove it now. – saulspatz Jan 21 '21 at 18:33

2 Answers2

7

The answer is $n!$. The cleanest strategy, to my mind, is contained in the comments to saulspatz's answer: working $\bmod 2$ we can equivalently count the number of nonzero monomials in $\prod_{i < j} (x_i - x_j)$ over $\mathbb{F}_2$. This is the Vandermonde determinant. The Leibniz formula expresses the Vandermonde determinant is a sum of $n!$ terms, each of which is a monomial with coefficient $\pm 1$ (so $1 \bmod 2$) and each of which is distinct, so there's no additional cancellation.

(By the way, the product does still make sense when $n = 1$, it's just empty, so it's equal to $1$ and has $1! = 1$ odd coefficients. This is consistent with the $1 \times 1$ Vandermonde determinant $\det(1) = 1$ also.)

Qiaochu Yuan
  • 419,620
4

First, we convert this to a combinatorial problem. Suppose we have $n-1$ balls of each of $n$ colors, and $\binom{n}2$ buckets, each with two balls in it, such that every color combination occurs exactly once. We draw a ball from each bucket, and record the result as an ordered $n$-tuple $(c_1,c_2,\dots,c_n)$ where $c_k$ is the number of times we drew color $k$ for $k=1,\dots n$.

There is an obvious correspondence between the tuple $(c_1,c_2,\dots,c_n)$ and the term $x_1^{c_1}\cdots x_n^{c_n}$, and we are asked how many tuples can be obtained in an odd number of ways.

I claim that only the $n!$ tuples comprising the numbers $0,1,,2,\dots n-1$ in some order can be obtained in an odd number of ways, and that in fact, they can only be obtained in one way.

It is easy to see that each of these tuples can be obtained in exactly one way. If $c_k=n-1$, we must draw all $n-1$ balls of color $k$. Then there remain $n-2$ balls of each color other than $k$, so if $c_j=n-2$, then we must draw all the balls of color $j$ and so on.

It remains to show that every other combination can be obtained in an even number of ways. If the numbers in the tuple $(c_1,c_2,\dots,c_n)$ are not all different, then there must be two nonzero numbers that are the same, because the sum has to be $\binom n2$. Suppose that $0<c_i=c_j$ where $i\neq j$. We must draw a ball from the bucket containing $i$ and $j$, and I claim that there are just as many ways to achieve $(c_1,c_2,\dots,c_n)$ by drawing $i$ as there are by drawing $j$. Indeed, this is clear, because the problem is symmetric in $i$ and $j$.

saulspatz
  • 53,131