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

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

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

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.