# Number of polynomfunctions $\mathbb{Z}_3 \rightarrow \mathbb{Z}_3$

I need to determine the number of polynomfunctions over $\mathbb{Z}_3 \rightarrow \mathbb{Z}_3$. I have no clue how to attempt this problem. I know that $\mathbb{Z}_3 =$ {0, 1, 2}. The polynomfunction is defined as: $f(x) = a_kX^k + ... a_1X^1 + a_0X^0$. Now in $\mathbb{Z}_3$ we get the following possible polynomfunctions:
1. $f(x) = a_0X^0$
2. $f(x) = a_1X^1 + a_0X^0$
3. $f(x) = a_2X^2 + a_1X^1 + a_0X^0$
4. $f(x) = a_2X^2 + a_1X^1$
5. $f(x) = a_2X^2$
6. $f(x) = a_2X^2 + a_0X^0$
7. $f(x) = a_1X^1$
Does anyone know how to calculate the number of possible polynomfunctions?

-
See artofproblemsolving.com/Forum/… for a heavy extension of this problem. Using the ideas of math154, one can find the number of polynomial functions from Z_n to Z_n for any n. – dinoboy Dec 16 '12 at 20:16

All functions from $\mathbb{Z}_3$ to $\mathbb{Z}_3$ are polynomial functions.

And there are $3^3$ functions from $\mathbb{Z}_3$ to $\mathbb{Z}_3$.

This is because you have $3$ choices as to what $f(0)$ should be. And for every such choice, there are $3$ choices as to what $f(1)$ should be. And for every choice of what $f(0)$ and $f(1)$ are, there are $3$ choices for $f(2)$.

Remarks: $1.$ If $F$ is any finite field, all functions from $F$ to $F$ are polynomial functions. Let the field have $n$ elements $a_1,\dots,a_n$. Let $P_i(x)$ be the polynomial $$\frac{1}{x-a_i}\prod_{j=1}^n (x-a_j).$$ Then for any function $f$, we can find constants $c_i$ such that $$f(x)=\sum_i c_iP_i(x).$$ This is the same as the usual Lagrange interpolation process.

$2.$ In your case, any two distinct polynomials of degree $\le 2$ produce distinct polynomial functions, and all polynomial functions arise in this way. So your polynomial functions are all functions $f(x)=a_0+a_1x+a_2x^2$, where the $a_i$ range over $\mathbb{Z}_3$.

Polynomials of degree $\ge 3$ do not produce any new functions. You can think of this as a consequence of the fact that the function $x^3$ is the same function as the function $x$.

This gives us another way of seeing that all $27$ functions are polynomial functions. Suppose that $P(x)$ and $Q(x)$ are polynomials of degree $\le 2$ which determine the same function. Then $P(x)-Q(x)$ determines the identically $0$ function. But a non-zero polynomial cannot have more roots than its degree. There are therefore $27$ different polynomial functions that only use polynomials of degree $\le 2$. Since there are only $27$ functions in total, any function must be given by a polynomial of degree $\le 2$. The same idea works is any finite field.

-
To prove this, incidentally, you can show that the Lagrange interpolation formula (mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html) works correctly over finite fields (or at least over $\mathbb{Z}/p\mathbb{Z}$ for prime $p$). – Steven Stadnicki Dec 16 '12 at 19:43
I think I asked the wrong question. I need to determine the number of possible polynomfunctions "all" however is something I can not write down since it requires me to give an exact number. – Just a Student Dec 16 '12 at 19:47
There are 27 functions from $\mathbb Z_3 \to \mathbb Z_3$. Are polynomial functions considered equal iff they have the same coefficients, or are the equal iff they are equal as functions? – process91 Dec 16 '12 at 19:48
Equal as functions. So for example $x^3$ produces the same function as $x$. For infinite fields, two polynomials are identical if and only if they produce the same function. That is not true for finite fields. – André Nicolas Dec 16 '12 at 19:52
Thank you! Helped me a lot. – Just a Student Dec 16 '12 at 20:05