3
$\begingroup$

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$.
Improve this question
$\endgroup$
9
  • $\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$
    – Gerhard Paseman
    Commented 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$
    – Gerhard Paseman
    Commented 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$
    – Gerhard Paseman
    Commented 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
    Commented 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
    Commented Apr 17, 2011 at 5:37

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ @Myerson, please include the reference to the book Cojocaru and Murty and I will accept your answer. $\endgroup$
    – Chulumba
    Commented 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
    Commented 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
    Commented 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$
    – Gerry Myerson
    Commented Apr 17, 2011 at 23:21
  • $\begingroup$ @Gerry, yes that's what I meant. I have already browsed through the book. $\endgroup$
    – Chulumba
    Commented Apr 18, 2011 at 5:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .