If $F$ is a finite field, prove that every function in $F^{F}$ is a polynomial function I'm doing Exercise 13 in textbook Algebra by Saunders MacLane and Garrett Birkhoff.


If $F$ is a finite field, prove that every function in $F^{F}$ is a polynomial function.

Could you please verify if my understanding is correct? Thank you so much for your help!

Assume $F = \{a_1,\cdots, a_n\}$ and $f \in F^F$. We define a polynomial $p \in F[x]$ by $$p = \sum_{i=1}^n f(a_i) \frac{\prod_{j \neq i} (x-a_j)}{\prod_{j \neq i} (a_i-a_j)}$$
Because the sum and product are finite, they are well-defined. Then we can verify that $f$ is the polynomial function induced by $p$. This completes the proof.
 A: Even without knowing about polynomial interpolation we can argue as follows, imitating the proof of the Stone-Weierstrass theorem (but much easier!).

Proposition: Let $F$ be a finite field and $X$ be a finite set. Suppose $R \subseteq F^X$ is an $F$-subalgebra of the ring of functions $X \to F$ which separates points in the sense that for any two distinct points $x \neq y \in X$ there exists a function $r \in R$ such that $r(x) \neq r(y)$. Then $R = F^X$.

When $X = F$ and $R$ is the ring of polynomial functions, the linear polynomial $x$ separates points.
Proof. It suffices to show that for every $x \in X$, the subalgebra $R$ contains the indicator function $1_x(y) = \delta_{xy}$ (the function which is equal to $1$ if its input equals $x$ and $0$ otherwise), since $F^X$ is spanned as an $F$-vector space by these indicator functions. By hypothesis, if $y \neq x$ then there is a function $r \in R$ which separates $x$ and $y$, so that $r(x) \neq r(y)$. Replacing $r$ by $\frac{r - r(y)}{r(x) - r(y)}$, this gives a function $s \in R$ such that $s(x) = 1, s(y) = 0$. Taking the product over all such functions for all $y \neq x$, this gives $1_x$ as desired. $\Box$
In polynomial interpolation, of course, we just always select $r$ to be the linear polynomial $x$. One of the interesting things about this proof, to my mind, is that it immediately generalizes to telling us what happens if $R$ does not separate points: namely, if we define an equivalence relation on $X$ by $x \sim y$ if $r(x) = r(y)$ for all $r \in R$, then $R$ must be the subalgebra of $F^X$ given by functions constant on each equivalence class. So every $F$-subalgebra of $F^X$ is of the form $F^Y$ for some surjective map $X \to Y$. (This is part of a contravariant equivalence between certain finite commutative $F$-algebras and the category of finite sets, which form the simplest examples of the equivalence between commutative $F$-algebras and affine schemes over $F$.)
