Functions of several variables over finite fields [closed]

Question

For a finite field $F$ any function $f\colon F\to F$ is given by a polynomial. My question is what happens when we are given a function of two or more variables? Is this necessarily a polynomial function of two or more variables?

Looking at the Lagrange Interpolation formula in the univariate case I try to argue for the 2-variable case this way.

So given some data $(a_i,b_j)\mapsto c_{ij}$ . I can try to fit a many polynomial functions $F_i$'s with $F_i(a_i,b_j)=c_{ij}$ for all $j $. The coefficients of $F_i$'s vary as rational functions in the given data $c_{ij}$. As inversion is also a polynomial function in one variable can I assume I can get a polynomial of two variable to represent all functions of two variables?

Answer 1

For $(a_0,b_0) \in F^2$, the two-variable polynomial

$$P_{a_0,b_0} = \left ( \prod_{a \in F \setminus \{a_0\}} \frac{X-a}{a_0 -a} \right ) \left ( \prod_{b \in F \setminus \{b_0\}} \frac{Y-b}{b_0 -b} \right ) $$ yields the characteristic function of $\{(a_0,b_0)\}$, that is $1$ for $(a_0,b_0)$ and $0$ otherwise.

These characteristic functions span the space of all functions from $F^2 $ to $F$ and the claim follows.

Or concretely, for a function $f$ take $P_f = \sum_{(x,y)\in F^2} f(x,y)P_{x,y}$.

The argument works for $F^n$ for any $n$ just as well.