Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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

1 Answer 1

up vote 10 down vote accepted

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.

share|improve this answer
1  
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
1  
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
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.