# Counting some vanishing polynomials in $\mathbb{Z}_n[X]$

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

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