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.
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.