MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a question I asked on Math.SE and got only a partial answer. I hope I will have better chances here.

Given the ring of polynomials $\mathbb{Z}_n[X]$, consider $$\mathbb{P}_n = \lbrace a_0 +a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}| a_i \in \mathbb{Z}_n \rbrace,$$ 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 = \lbrace 0,1,x,1+x \rbrace ,$

$$\mathbb{P}_3 = \lbrace 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 \rbrace \cup $$

$$ \lbrace 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 \rbrace \cup $$

$$ \lbrace 2+x+2x^2, 2+2x, 2+2x+x^2, 2+2x+2x^2 \rbrace $$

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^{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^{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|cite|improve this question
It is more clear if instead of vanish (suggesting p(x) is identically 0 on Z_n) you say p has a root in Z_n, or say p(k) = 0 for at least one k in Z_n. Gerhard "Ask Me About System Design" Paseman, 2011.04.16 – Gerhard Paseman Apr 17 '11 at 5:22
@Gerhard, point taken. Thanks. – Chulumba Apr 17 '11 at 5:24
Also, there are n^(n-1) of your polynomials with zero constant term. Gerhard "Ask Me About System Design" Paseman, 2011.04.16 – Gerhard Paseman Apr 17 '11 at 5:25
Finally, someone mentioned a result in a book of Cojocaru and Murty that used sieve methods to estimate something like your r_n. You might search MathOverflow to see if you can find the details. Gerhard "Ask Me About System Design" Paseman, 2011.04.16 – Gerhard Paseman Apr 17 '11 at 5:27
Edited. I found the link but it is about random polynomials which is not what I am after:… – Chulumba Apr 17 '11 at 5:36
up vote 4 down vote accepted

I think there's a simple answer when $n$ is prime. Count instead the polynomials that don't have a zero. Such a polynomial must map $\lbrace0,1,\dots,n-1\rbrace$ to $\lbrace1,\dots,n-1\rbrace$. There are $(n-1)^n$ such maps. But each of those maps corresponds to a unique polynomial, since Lagrange interpolation works over a field. So the number you are looking for is $n^n-(n-1)^n$.

share|cite|improve this answer
@Myerson, please include the reference to the book Cojocaru and Murty and I will accept your answer. – Chulumba Apr 17 '11 at 14:47
If $n$ is not prime, isn't $n^n-(n-1)^n$ always a good answer ? $n^n-(n-1)^n=\sum_{i=1}^{n} (-1)^{i-1} C^{i}_{n} n^{n-i}$. If $A_i$ is the set of polynomials that vanish in $i \in \mathbb{Z}_n$. $|A_0 \cup A_1 \cup ... \cup A_n|= \sum_i |A_i| - \sum_{i\neq j} |A_i \cap A_j| + \sum_{i \neq j \neq k} |A_i \cap A_j \cap A_k|-...$. $A_{i_1} \cap ... \cap A_{i_k}$ is the set of polynomial that have roots $i_1,...,i_k$. So we can write such polynomial $(X-i_1)...(X-i_k)P$ with $\deg(P) \leq n-1-k$. So So $|A_{i_1} \cap ... \cap A_{i_k}|= n^{n-k}$. And there are $C^k_n$ subsets with $k$ elements – user12806 Apr 17 '11 at 14:49
My answer is false if $n$ is not prime because $2X(X-1)=2X(X-3)$ in $\mathbb{Z}_4[X]$. – user12806 Apr 17 '11 at 15:03
@Chulumba, I assume you mean Alina Carmen Cojocaru and M Ram Murty, An Introduction to Sieve Methods and their Applications, London Mathematical Society Student Texts 66, Cambridge University Press, 2006. – Gerry Myerson Apr 17 '11 at 23:21
@Gerry, yes that's what I meant. I have already browsed through the book. – Chulumba Apr 18 '11 at 5:29

Your Answer


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.