1
$\begingroup$

I am working on a review for a graduate level Complex Analysis course. The following problem is on the review:

Let $\zeta= e^{\frac{2\pi i}{n}}$ $(n\in \mathbb{N})$; show that

$\displaystyle{\prod_{k=0}^{n-1} (1-\zeta^k z)=1-z^n}$

$\displaystyle{\prod_{k=1}^{n-1} (1-\zeta^k z)=1+z\ +...+\ z^n}$

I have proved it to myself for $n=3$ and recognized a "telescoping" behavior if you will. I know I have seen this formula before but can't remember where. Could someone please either point me in the right direction or help prove it? Thank you for your help.

$\endgroup$
4
$\begingroup$

Just note this the first one nothing but the factorization of the of the polynomial

$$z^n-1=0\,. $$

Can you solve it? Here is how you find the roots

$$ z^n = e^{2\pi k i} \implies z = e^{2\pi k i/n}\, , \quad k=0,1,2,\dots,n-1$$

You should be able to figure out the other one!

$\endgroup$
  • $\begingroup$ Thank you for your help. Unfortunately, I'm still not entirely sure where this takes me. Could you possibly elaborate? $\endgroup$ – hungryformath Mar 20 '16 at 2:14
1
$\begingroup$

Hints: For your first formula, notice that $$(1-\zeta^kz) = (1-\overline{\zeta^{n-k}}z),$$ so that their product gives $1 - 2\Re(\zeta^k) + z^2$. Now you only have to separate the cases where $n$ is even or odd, and do some dirty work.

The second formula follows easily from the first by division of polynomials.

$\endgroup$
1
$\begingroup$

For the first formula, notice that $p(z)=1-z^n$ and $q(z)=\prod_{k=0}^{n-1} (1-\zeta^k z)$ are both polynomials of degree $n$ with exactly the same roots because $z^n=1$ iff $z^{-n}=1$.

To conclude that $p(z)=q(z)$ we need to prove that they have the same leading coefficient, $-1$.

The leading coefficient $q_n$ of $q(z)$ is $(-1)^n \prod_{k=0}^{n-1} \zeta^k$.

But $\prod_{k=0}^{n-1} \zeta^k$ is the product of the roots of $p(z)$, and so is $(-1)^n\dfrac{1}{-1}=(-1)^n(-1)$ by Vieta's formulas.

Therefore, $q_n = (-1)^n (-1)^n (-1) = -1 = p_n$.

The second formula follows from the first: $$ 1-z^n =\prod_{k=0}^{n-1} (1-\zeta^k z) =(1-z)\prod_{k=1}^{n-1} (1-\zeta^k z) $$ and so $$ \prod_{k=1}^{n-1} (1-\zeta^k z) =\frac{1-z^n}{1-z}=1+z\ +\cdots+\ z^n $$

$\endgroup$
  • $\begingroup$ You said to notice that $p$ and $q$ have exactly the same roots. For $p$, I see, $z^n=1 \Rightarrow z=\exp (2k\pi i /n)$ However, for the factors of $q$ I see ($k=1$ for example), $\exp (2\pi i/n) z=1 \Rightarrow z=\exp (-2\pi i/n)$. Forgive me if this is obvious, but I'm a total noob. $\endgroup$ – hungryformath Mar 20 '16 at 2:17
  • 1
    $\begingroup$ @hungryformath, I've added a short explanation. $\endgroup$ – lhf Mar 20 '16 at 10:27
0
$\begingroup$

It was remarked that we can easily derive the second formula from the first by polynomial division, therefore we will prove the first formula here using what appears to be a somewhat exotic method, namely the Polya Enumeration Theorem (PET).

Given that $$\rho = \exp(2\pi i/n) \quad\text{we seek to show that}\quad f(z) = \prod_{k=0}^{n-1} (1-\rho^k z) = 1 - z^n.$$

Suppose $Z(P_n)$ is the cycle index of the set operator $\mathfrak{P}_{=n}$ given by the recurrence by Lovasz which is

$$Z(P_n) = \frac{1}{n} \sum_{l=1}^n (-1)^{l+1} a_l Z(P_{n-l}) \quad\text{where}\quad Z(P_0) = 1.$$

Now observe that $$[z^q] f(z) = (-1)^q \left. Z(P_q)(1+v+v^2+\cdots+v^{n-1}) \right|_{v=\rho}.$$

Next recall the OGF of the set operator $\mathfrak{P}_{=q}$ which is (this is the so-called exponential formula)

$$Z(P_q) = [w^q] \exp\left(a_1 w - a_2 \frac{w^2}{2} + a_3 \frac{w^3}{3} - a_4 \frac{w^4}{4} +\cdots \right).$$

or

$$Z(P_q) = [w^q] \exp\left(\sum_{r\ge 1} (-1)^{r+1} a_r \frac{w^r}{r}\right).$$

Nóte that $$\left.a_r\right|_{v=\rho} = \left.(1+v^r+v^{2r}+\cdots+v^{(n-1)r})\right|_{v=\rho} = n \times [[n|r]].$$

Therefore $$[z^q] f(z) = (-1)^q [w^q] \exp\left(\sum_{r\ge 1} (-1)^{nr+1} n \frac{w^{nr}}{nr}\right) \\ = (-1)^q [w^q] \exp\left(-\sum_{r\ge 1} \frac{(-w)^{nr}}{r}\right) \\ = (-1)^q [w^q] \exp\left(-\log\frac{1}{1-(-w)^n}\right) = (-1)^q [w^q] (1-(-w)^n).$$

It now follows that the constant coefficient (on $q=0$) is one, the coefficients on $[z^q]$ where $1\le q\lt n$ are zero, and the coefficient on $[z^n]$ i.e. $q=n$ is $$(-1)^n [w^n] (-(-w)^n) = - (-1)^{2n} = -1$$

and hence $$f(z) = 1 - z^n.$$

Commentary. The recurrence for the cycle index is included here for reference and can be used to prove the exponential formula and vice versa. We have also made use of the fact that for $r$ a positive integer

$$\sum_{q=0}^{n-1} \rho^{rq} = n \quad\text{when}\quad n|r.$$

On the other hand when $r$ is not a multiple of $n$ we get $$\frac{\rho^{rn}-1}{\rho^r-1} = 0.$$

$\endgroup$

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.