Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given the ring of polynomials $\mathbb{Z}_n[X]$, consider $$\mathbb{P}_n = \{a_0 +a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}| a_i \in \mathbb{Z}_n\},$$ i.e. $\mathbb{P}_n$ is the set of all polynomials in $\mathbb{Z}_n[X]$ with exponents in $\mathbb{Z}_n$.

So, $\mathbb{P}_2 = \{0,1,x,1+x\},$

$$\mathbb{P}_3 = \{0, x^2, 2x^2, x, x+x^2, x+2x^2, 2x, 2x+x^2, 2x+2x^2, 1, 1+x^2, 1+2x^2, 1+x \} \cup $$

$$ \{ 1+x+x^2, 1+x+2x^2, 1+2x, 1+2x+2x^2, 2, 2+x^2, 2+2x^2, 2+x, 2+x+x^2 \} \cup $$

$$ \{ 2+x+2x^2, 2+2x, 2+2x+x^2, 2+2x+2x^2\}$$

The above ordering of the elements is based on the coefficient coordinates pattern: $(0,0,0), (0,0,1),(0,0,2), (0,1,0), (0,1,1), (0,1,2), \cdots, (2,2,0), (2,2,1), (2,2,2).$

Clearly, $\mathbb{P}_n$ has $n^n$ elements. I am counting the number of polynomials in $\mathbb{P}_n$ that vanish in $\mathbb{Z}_n$. Let's denote the count for $\mathbb{P}_n$ by $r_n$ ($r$ loosely stands for 'reducible'). Then, $r_2 = 3, r_3 = 19, \cdots$ It is very early to guess the growth of $r_n$ or its primality but I would like to know if there is any theorem that would help to count or reduce the number of polynomials I should check.

Some work:

  1. Since $\mathbb{Z}_n \subset \mathbb{Z}_n[X]$, $r_n \leq n^n - (n-1)$. (there are $n-1$ nonzero elements)
  2. There are $(n-1)^{n-1}$ polynomials with zero constant term and there are $n-1$ polynomials of degree $1$ with nonzero constant term all of which vanish for some $x$ in $\mathbb{Z}_n$. Hence $(n-1)^{n-1} + (n-1) \leq r_n$. This is not a good bound as it is far less than $n^n$ for large $n$.
share|improve this question

1 Answer 1

Let $n=p$ be a prime (otherwise I'm clueless). Let $q_k$ be the number of monic polynomials of deg $k$ having no root. The number of deg $m$ monic polynomials that split into linear factors is $C(p-1+k,k)$ (here $C(n,k)=n!/(k!(n-k)!)$). The number of all monic deg $n$ polys is $p^n$. Hence $$p^n=\sum_k C(p-1+k,k)q_{n-k}$$ (as any polynomial can be written as a product of those two types). Let $q(x)=\sum_{k=0}^{\infty}q_k x^k$. We get $$\sum p^n x^n=\sum_{k,m} C(p-1+k,k) x^k q_{m}x^m$$ i.e. $$1/(1-px)=(1-x)^{-p} q(x).$$ Hence $q(x)=(1-x)^p/(1-px)$. The number of all (nut just monic) polynomials of degree $\leq p-1$ having no root is therefore the coefficient of $x^{p-1}$ of $$(p-1)(1-x)^{p-1}/(1-px)$$ (expand $1/(1-px)$ to geometrical series to get a formula for the coefficient).

share|improve this answer
    
Thank you very much. I am trying to understand the proof. –  Chulumba Mar 27 '11 at 15:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.