# Primitive roots as roots of a $q$-multinomial.

If $n$ is divisible by $m$, why is it the case that the $m$th primitive roots of unity are also roots of $\binom{n}{k}_q$ if and only if $m$ does not divide $k$?

I'm viewing $\binom{n}{k}_q$ as a polynomial in $q$, but I don't see why the divisibility relations gives this condition of the primitive roots being roots of the polynomial. Thanks.

-

## 1 Answer

The complex $m$th roots of unity are roots of $x^m-1$, and form a regular $m$-gon on the unit circle in the complex plane with one vertex at $1$ (for $0 < m \in \mathbb{N}$). Primitive $m$th roots of unity are roots of the irreducible polynomial factors of $x^m-1$, called cyclotomic polynomials $\phi_d(x)$ and satisfying $$x^m-1 = \prod_{0<d|m}\phi_d(x)\;,$$ which recursively defines them: $\phi_1(x)=x-1$, $\phi_2(x)=x+1$, $\phi_3(x)=x^2+x+1$, $\phi_4(x)=x^2+1$, $\phi_5(x)=x^4+x^3+x^2+x+1$, $\phi_6(x)=x^2-x+1$, etc. In particular, $\phi_d(x)$ has degree $\phi(d)$ and, as stated, its roots are precisely the primitive $m$th roots of unity.

(The polynomial factorization formula above can also be seen as providing a partition of the full set of $m$th roots of unity, which forms a multiplicative subgroup of $\mathbb{C}$ of order $m$, into subsets based on their order -- for which minimal $d$ do they satisfy $x^d=1$ -- comprised of $\phi(d)$ generators $\{e^{2\pi ij/d}|(j,d)=1\}$ of the subgroup of order $d$ for each positive divisor $d$ of $n$. It is worthwhile once to draw some examples of these partitions.)

Now since $$[m]_q=\frac{q^m-1}{q-1}=\prod_{1<d|m}\phi_d(q)\;,$$ its roots are precisely the nontrivial $m$th roots of unity for $m>1$ (all primitive $d$th roots of unity where $d>1$ and $d \mid m$). So a root of $$\binom{n}{k}_q =\prod_{j=1}^{k}\frac{[n-j+1]_q}{[j]_q} =\prod_{1<d \leq n}\phi_d(q)^{e_d} \qquad\text{for some }e_d\in\mathbb{Z}$$ must be a root of the numerator more times than of the denominator (counting multiplicity). It is actually pretty elementary to calculate the $e_d$ (no prime factorization is needed). We simply observe that we need to add one for each time that $d$ divides a number from $\{n, n-1, \dots, n-k+1\}$ and subtract one for each time it divides a number from $\{k, k-1, \dots, 1\}$. This can be expressed using the floor function, by similar reasoning as is used to count powers in the prime factorization of a factorial: $$e_d =\left[\frac{n}{d}\right] -\left[\frac{n-k}{d}\right] -\left[\frac{k}{d}\right]$$ Observing that the each floor function is only taking away the residue or remainder modulo $d$ from the numerator of the fraction it contains, and grouping the two negative terms, we can see that $e_d\geq0$ is in fact positive iff $k$ has smaller (nonnegative) residue than $n$ modulo $d$. To see this, let $n=ud+r$ and $k=vd+s$ for $0 \leq r,s < d$ and note that $$e_d = \left[u+\frac{r}{d}\right] -\left[u-v+\frac{r-s}{d}\right] -\left[v+\frac{s}{d}\right] =-\left[\frac{r-s}{d}\right] =\left\{\begin{matrix} 1 & r < s \\ 0 & r \geq s \end{matrix} \right.$$ since the floor function rounds down to $-\infty$ and $-d<r-s<d$.

In particular for $m=d \mid n$, we can see that the primitive $m$th roots of unity are roots of $\binom{n}{k}_q$ iff $$\phi_m(q) \mid \binom{n}{k}_q \iff e_m = 1 \iff m \nmid{k} \iff m \nmid n-k \;.$$

-
Thanks bgins. Do you mind explaining further the case when $m\mid k$ if you have the time? – Shea Dec 17 '11 at 7:13
Wow, amazing! Thanks again bgins. – Shea Dec 17 '11 at 17:33