# Calculating $\frac{\Phi_p(x^n)}{\Phi_p(x)}$ using generating functions or inclusion-exclusion

Where$$\Phi_p(x^n)=1+x^n+\cdots+x^{n(p-1)}$$ is the $p$th cyclotomic polynomial in $x^n$, and $p$ is prime. For instance,

$$\frac{\Phi_5(x^3)}{\Phi_5(x)}=\frac{1+x^3+x^6+x^9+x^{12}}{1+x+x^2+x^3+x^4}$$ $$=x^8-x^7+x^5-x^4+x^3-x+1=\Phi_{15}(x)$$ which, although I could mechanistically calculate, I find a coincidental and unintuitive answer. However, the alternating signs look a lot like the inclusion-exclusion principle may be at work underneath. Also, the little I know about generating functions suggests that this problem may be amenable to a generating-function approach.

TL,DR: Is there a general form for $$\frac{\Phi_p(x^n)}{\Phi_p(x)}$$ , and, if so, can it be arrived at via the inclusion-exclusion principle or generating functions?

-
My apologies, I was confused. –  Qiaochu Yuan Aug 13 '13 at 17:24

NB: This doesn't use the inclusion-exclusion principle nor generating functions, and it is for $n$ prime only, but I think it generalises with some care.

Conjecture: For $n, p$ prime the cyclotomic polynomials satisfy the following equation: $$\Phi_p(x)\Phi_{pn}(x)=\Phi_p(x^n).$$

Recall that $$\Phi_m(x) = \prod_{d|m}(1-x^d)^{\mu(m/d)}$$ where $\mu$ is the Möbius function. Plug this into $LHS$ above to find that $$LHS=\prod_{d|p}(1-x^d)^{\mu(p/d)}\cdot\prod_{d|pn}(1-x^d)^{\mu(pn/d)}.$$

Since $p$ and $n$ are prime, for the first product we have $d=1$ and $d=p$, and for the second product we have that $d$ takes the values $1,p,n$ and $pn$. Grouping similar terms we find that $$LHS=\underbrace{\underbrace{(1-x)^{\mu(p)+\mu(pn)}}_{d=1}\cdot\underbrace{(1-x^p)^{\mu(1)+\mu(n)}}_{d=p}}_{1}\cdot \underbrace{\underbrace{(1-x^n)^{\mu(p)}}_{d=n}\cdot\underbrace{(1-x^{pn})^{\mu(1)}}_{d=pn}}_{RHS}=RHS.$$

(The exponents of the first two factors are both $0$, so these factors vanish, and the last two factors is precisely $RHS$.)

-
I'm a novice, and so don't recall. Could you link to the proof? –  Alyosha Aug 15 '13 at 17:18
@Alyosha If you are familiar with the Möbius function and Möbius inversion, there's a derivation on page 63 in generatingfunctionology by Wilf. –  ET3 Aug 19 '13 at 14:34
I did know of them, but had forgotten. Thanks! –  Alyosha Aug 19 '13 at 15:42
Now I understand it, it's quite a pretty answer, it easily generalises to non-prime $n$. –  Alyosha Aug 19 '13 at 15:48
If link rot occurs, use this math.upenn.edu/~wilf/gfology2.pdf instead, it's still page 63. –  Alyosha Sep 28 '13 at 19:31