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$.
  • $\begingroup$ 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 $\endgroup$ Apr 17, 2011 at 5:22
  • $\begingroup$ Also, there are n^(n-1) of your polynomials with zero constant term. Gerhard "Ask Me About System Design" Paseman, 2011.04.16 $\endgroup$ Apr 17, 2011 at 5:25
  • $\begingroup$ 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 $\endgroup$ Apr 17, 2011 at 5:27
  • $\begingroup$ Edited. I found the link but it is about random polynomials which is not what I am after: mathoverflow.net/questions/60101/… $\endgroup$
    – Chulumba
    Apr 17, 2011 at 5:36
  • $\begingroup$ Are the braces for the sets visible on other people screens? They are not on mine. How do I fix that? $\endgroup$
    – Chulumba
    Apr 17, 2011 at 5:37

1 Answer 1


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$.

  • $\begingroup$ @Myerson, please include the reference to the book Cojocaru and Murty and I will accept your answer. $\endgroup$
    – Chulumba
    Apr 17, 2011 at 14:47
  • $\begingroup$ 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 $\endgroup$
    – user12806
    Apr 17, 2011 at 14:49
  • $\begingroup$ My answer is false if $n$ is not prime because $2X(X-1)=2X(X-3)$ in $\mathbb{Z}_4[X]$. $\endgroup$
    – user12806
    Apr 17, 2011 at 15:03
  • $\begingroup$ @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. $\endgroup$ Apr 17, 2011 at 23:21
  • $\begingroup$ @Gerry, yes that's what I meant. I have already browsed through the book. $\endgroup$
    – Chulumba
    Apr 18, 2011 at 5:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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