4
$\begingroup$

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?

  • 1
    See http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1247509&sid=a35296463057eb34184e3a6042de7b93#p1247509 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.2012-12-16

1 Answers 1

10

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.

  • 0
    Thank you! Helped me a lot.2012-12-16