Let \(F\) be a finite field with \(q\) elements. For \(f\in F[x]\), write \[ \varphi_f(a)=f(a) \qquad(a\in F). \] Prove that every function \(\varphi:F\to F\) equals \(\varphi_f\) for some \(f\in F[x]\), and that \(f\) is determined by \(\varphi\) up to addition of a multiple of \[ x^q-x. \]
Solution
1. For each \(a\in F\), define\[ \ell_a(x) \coloneqq \prod_{\substack{b\in F\\ b\ne a}} \frac{x-b}{a-b}. \]Then\[ \ell_a(c) = \begin{cases} 1,&c=a,\\ 0,&c\ne a, \end{cases} \]for every \(c\in F\).
Every denominator \(a-b\) in the product is nonzero and hence invertible in the field \(F\), so \(\ell_a\in F[x]\). If \(c=a\), every factor is \(1\). If \(c\ne a\), the factor indexed by \(b=c\) is \(0\).
2. Every function \(\varphi:F\to F\) is represented by a polynomial in\(F[x]\).
Define \[ f(x) \coloneqq \sum_{a\in F}\varphi(a)\ell_a(x). \] For any \(c\in F\), step 1 gives \[ f(c) = \sum_{a\in F}\varphi(a)\ell_a(c) = \varphi(c). \] Thus \(\varphi=\varphi_f\).
3. In \(F[x]\) one has\[ \boxed{\prod_{a\in F}(x-a)=x^q-x}. \]
If \(a=0\), then \(a^q=a\). If \(a\ne0\), then \(a\in F^\times\), whose order is \(q-1\). Lagrange’s theorem gives \[ a^{q-1}=1, \] and hence again \(a^q=a\). Therefore every \(a\in F\) is a root of \(x^q-x\).
The polynomial \[ \prod_{a\in F}(x-a) \] is monic of degree \(q\) and has exactly these \(q\) distinct roots. The polynomial \(x^q-x\) is also monic of degree \(q\) and has all of them as roots. Their difference has degree less than \(q\) and at least \(q\) roots, so it is zero.
4. If \(f,g\in F[x]\) satisfy \(\varphi_f=\varphi_g\), then\[ x^q-x\mid f-g. \]
For every \(a\in F\), \[ (f-g)(a)=0. \] By the factor theorem, \(x-a\) divides \(f-g\) for every \(a\in F\). The distinct linear factors \(x-a\) are pairwise coprime, so their product divides \(f-g\). Step 3 identifies this product with \(x^q-x\).
5. Conversely, if\[ f-g=(x^q-x)r \]for some \(r\in F[x]\), then \(\varphi_f=\varphi_g\).
For every \(a\in F\), step 3 gives \[ a^q-a=0. \] Hence \[ f(a)-g(a) = (a^q-a)r(a) =0, \] so the two polynomials define the same function on \(F\).
6. Q.E.D.
Step 2 proves existence. Steps 4 and 5 show that two representing polynomials define the same function exactly when their difference is a multiple of \(x^q-x\), which is the asserted uniqueness.