# Dimension of a vector space of functions from a finite field to itself

Let $F$ be a finite field with $q$ elements. Let $V = P(F)$ and let $W = Func(F, F)$ be the vector space of all functions from $F$ to $F$.

I am struggling with two things:

1. Compute $\dim W$.

2.Let $T : V \to W$ be the transformation that sends a polynomial $f(x)$ to the function it represents. Prove that $T$ is a linear transformation.

I know that all functions in $W$ are polynomials, if that's true then $W$ is not finite-dimensional, right? As for $T$, what does the linear transformation do exactly?

• Hint. There are only finitely many functions. They are all polynomials, but different formal polynomials can have the same effect when you look at them as functions. You can even compute exactly when that will happen. Look at $x^p$ when the field has characteristic $p$. Commented Mar 13, 2017 at 19:47
• Why are there only finitely many polynomials? If we have at most a polynomial of degree $n$ on this finite field, we could have add a $x^{n+1}$ and have a polynomial of degree $n+1$.
– AAZ
Commented Mar 13, 2017 at 20:03
• @AAZ there are indeed infinitely many polynomials, but finitely many functions. See my answer below Commented Mar 13, 2017 at 20:28

Let's look at an example to understand what $T$ does. Take the case of $q = 3$. The space $V$ is infinite dimensional, and consists of all "formal sums" of the form $$p(x) = a_0 + a_1 x + a_2x^2 + \cdots + a_n x^n$$ where each $a_i$ is taken from $\Bbb F_3$ (whose elements are $0,1,2$).

Now, the transformation $T$ produces the "function" associated with $p$. For example: if $p(x) = 2x^3$, then $Tp$ is the function $f_p:\Bbb F_3 \to \Bbb F_3$ defined by $$f_p(0) = p(0) = 2(0)^3 =0, \quad f_p(1) = 2(1)^3 = 2, \quad f_p(2) = 2(2)^3 = 1$$ Notice that the polynomial $q(x) = 2x$ produces exactly the same function. That is, $p(x) = q(x)$ for every $x \in \Bbb F_3$. However, $p(x)$ and $q(x)$ are distinct as polynomials. In brief: we have $p \neq q$, but $f_p = f_q$. That is, $p \neq q$, but $Tp = Tq$.

Note that $Func(\Bbb F,\Bbb F)$ has a natural choice of basis. Namely, for $k \in \{0,1,\dots,q-1\}$, define $f_k : \Bbb F_p \to \Bbb F_p$ by $$f_k(j) = \begin{cases} 1 & j = k\\ 0 & j \neq k \end{cases}$$ why is this set a basis?

• Wouldn't it mean that $T(f(x)+g(x)) \not= T(f(x)) + T(g(x))$, because $p \not= q$ yet $T_p = T_q$? Or am I completely missing this?
– AAZ
Commented Mar 13, 2017 at 21:51
• I don't understand how you reached that conclusion. No, that is false. Commented Mar 13, 2017 at 22:54
• How would T(f(x)+g(x)) look like given your explanation of the linear transformation?
– AAZ
Commented Mar 14, 2017 at 23:49
• @AAZ I don't understand your question. Do you have a specific example of $f$ and $g$? Commented Mar 15, 2017 at 0:06
• I have to prove that T is a linear transformation, one of the properties I have, for example, is that: $$T(f(x) + g(x)) = T(f(x)) + T(g(x))$$ But I don't know how I would add $T(f(x)) + T(g(x))$
– AAZ
Commented Mar 15, 2017 at 0:17