## Return to Question

3 edited braces

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},$$ 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 = {0,1,x,1+x},$ \lbrace 0,1,x,1+x \rbrace ,\$

$$\mathbb{P}_3 = {0, \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}$$ 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$.
2 edited formula

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

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 = {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}$ 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-1)^{n-1} 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\$.
1

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

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 = {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$.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 82, "mathjax_display_tex": 12, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9518085718154907, "perplexity_flag": "head"}