# counting monomials and integrality

For $n\in\mathbb{Z}^{+}$, consider the polynomials $$P_n(x)=\prod_{k=0}^{n-1}(x^n-x^k).$$

QUESTION. Is it possible to find a closed formula for the number of monomials in $P_n(x)$, after expansion?

Those interested in such enumeration may like to read this.

Here is an assertion which might be possible to prove.

CLAIM. For any $m\in\mathbb{Z}$, the following are all integers: $$\frac1{n!}P_n(m).$$

UPDATE. If it helps, I've found a stronger divisibility when $m$ is a prime $p$.

$$\frac{P_n(p)}{n!\,\cdot p^{\eta_p(n)}}=\frac{p^{\binom{n}2}\prod_{k=1}^n(p^k-1)}{n!\,\cdot p^{\eta_p(n)}}$$ where $\eta_p(n)=\nu_p\left((p\lfloor n/p\rfloor)!\right)$ and $\nu_p(m)$ is the $p$-adic valuation of an integer $m$.

• So the present question is about proving the claim, and not the enumeration, isn't it? – Pietro Majer Dec 3 '16 at 16:29
• Both are seeking solution and proof. – T. Amdeberhan Dec 3 '16 at 16:31
• thank you. I see the sequence is listed in OEIS as oeis.org/A086781 with no closed formula reported – Pietro Majer Dec 3 '16 at 16:38
• You are correct. – T. Amdeberhan Dec 3 '16 at 16:39
• @MartinRubey: True, which is explained by $Q=x^{\binom{n}2}\prod_{k=1}^n(x^k-1)$. – T. Amdeberhan Dec 3 '16 at 16:53

The claim is correct. We begin with a standard lemma.

Lemma: Let $p$ be an odd prime, and $x$ an integer coprime to $p$. Let $k$ be a positive integer and let $o$ be the multiplicative order of $x$ modulo $p$. Then $$v_p(x^k-1) = \begin{cases} v_p(x^o-1) + v_p(\frac{k}{o}) & o \mid k \\ 0 & o \nmid k \end{cases}.$$

We prove the claim by comparing the $p$-adic valuation of $P_n(m)$ and $n!$ for every prime $p \le n$ (since all prime divisors of $n!$ are $\le n$). We skip the primes in the set $\{ q: q \mid m \} \cup \{2\}$ (they may be treated separately). The lemma implies that your claim is equivalent to the following inequalities: $$(*) \forall p\le n (\text{odd, coprime to }m): v_p((\frac{n}{o})!) + \lfloor \frac{n}{o} \rfloor v_p(m^o-1) \ge v_p(n!),$$ $$\text{where }o \text{ is the multiplicative order of m modulo p},$$ and slightly different inequalities for $p=2$ and $p \mid m$.

We have: $$v_p((\frac{n}{o})!) + \lfloor \frac{n}{o} \rfloor v_p(m^o-1) \ge v_p((\frac{n}{o})!) + \lfloor \frac{n}{o} \rfloor = \sum_{i \ge 1} \lfloor \frac{n}{op^i} \rfloor + \lfloor \frac{n}{o} \rfloor$$ $$= \sum_{i \ge 1} \lfloor \frac{pn}{op^i} \rfloor \ge \sum_{i \ge 1} \lfloor \frac{n}{p^i} \rfloor = v_p(n!),$$ where the last inequality follows from the fact that $o<p$. This proves $(*)$.

To deal with the exceptional primes ($2$ and divisors of $m$), just note that $P_n(m)$ is divisible by $m^{\binom{n}{2}} (m-1)^n$ and that $v_p(n!)\le n,\binom{n}{2}$ for every $p$ and $n$.

• Interesting. Up-voted. – T. Amdeberhan Dec 3 '16 at 19:39
• For some years, I've been interested in a non-prime-counting proof of this one. Anyone? – darij grinberg Dec 4 '16 at 4:08
• What are you referring to when you said "of this one"? – T. Amdeberhan Dec 4 '16 at 4:37
• Of the divisibility claim that Ofir has proven. – darij grinberg Dec 4 '16 at 4:41
• I've tried this and it leads nowhere. There are polynomials taking integer values at all prime powers but not at all integers. – darij grinberg Dec 4 '16 at 17:47