# Functions on vector spaces over finite fields

Can every function $\psi ~\colon \mathbb{F_{p}^n} \to \mathbb{F_{p}}$ be regarded as a polynomial function for some polynomial in $\mathbb{F_{p}[x_1, \ldots,x_n]}$?

I believe this is true, but am having trouble proving it.

-

For each point $y=(y_1,...,y_n)$ in $\mathbb{F}_p^n$, the polynomial

$$\prod_{i=1}^n\prod_{z_i=0\atop z_i\neq y_i}^{p-1}(x_i-z_i)$$

is non-zero at $y$ and zero everywhere else, so these polynomials form a basis of the function space.

-
Note that this shows more generally that you can interpolate a function defined on any finite subset of $F^n$ with polynomials in $F[x_1, ... x_n]$. The crucial observation from here is that $\mathbb{F}_p^n$ is, well, a finite subset of itself. –  Qiaochu Yuan Mar 6 '11 at 22:11

The answer is yes. Suppose that the elements of $F_p$ are given by $\{{a_1,\dots,a_p\}}$. First, let us note that the function $f(x) =1$ if $x=a_i$, and $f(x)=0$ otherwise is a polynomial, given by (up to a constant) $f(x) = (x-a_1)\dots \widehat{(x-a_i)} \dots (x-a_p)$.

Let us denote this function by $f_i$. For an $n$-tuple $(a_{i_1},\dots,a_{i_n})$ let $f_{i_1,\dots,i_n}(x_1,\dots,x_n) = f_{i_1}(x_1) \cdot f_{i_2}(x_2) \cdot \dots \cdot f_{i_n}(x_n)$.

Now, given a function $f:F_p^n \to F_p$, we may write it as:

$f(x_1,\dots,x_n) = \sum_{ (a_{i_1},\dots,a_{i_n}) \in F_p^n } f_{i_1,\dots,i_n}(x) f(a_{i_1},\dots,a_{i_n})$ which is a finite sum of polynomials, and therefore, a polnomial.

-