# Polynomials which are functionally equivalent over finite fields

Recall that two polynomials over a finite field are not necessarily considered equal, even if they evaluate to the same value at every point. For example, suppose $$f(x) = x^2 + x + 1$$ and $$g(x) = 1$$. Then $$f$$ and $$g$$ agree at every point in the finite field $$\mathbb{F}_2$$, but $$f$$ has degree 2 and $$g$$ has degree 0, hence $$f$$ and $$g$$ are distinct when viewed as polynomials, even though they are equivalent as functions $$\mathbb{F}_2 \rightarrow \mathbb{F}_2$$.

Let $$f(x) = \sum_{i=0}^d a_i x^i$$ be a univariate polynomial of degree $$d$$ over the finite field $$\mathbb{F}_p$$ and let $$S_f$$ be the set of all polynomials of degree $$\leq d$$ which evaluate to the same value as $$f$$ at every point $$x \in \mathbb{F}_p$$; clearly $$S_f$$ is non-empty, since $$f \in S_f$$. My question is, can you characterize $$S$$? How big is it, as a function of $$d$$ and $$p$$? It is clear that $$S_f$$ includes the set $$T_f$$, where $$T_F = \left\{ \sum_{i=0}^d a_i x^{ip^{r_i} + k_i(p-1)} \mid k_i, r_i \in \mathbb{Z}, 0 \leq ip^{r_i} + k_i(p-1) \leq d \right\},$$ by Fermat's Little Theorem. How much larger can $$S_f$$ be, relative to $$T_f$$?

The cardinality of $$S_f$$ is $$p^{ \max(0, d+1-p)}$$ because $$S_f$$ consists of polynomials of the form $$f + (x^p-x) g$$ with $$g$$ of degree $$\leq d-p$$.
The fact that such polynomials lie in $$S_f$$ follows from Fermat's little theorem. The converse is because any polynomial in $$S_f$$, after subtracting $$f$$, must vanish at $$0,1,\dots,p-1$$, hence be divisible by $$\prod_{i=0}^{p-1}(x-i) = x^p-x$$, and the quotient by $$x^p-x$$ must have degree $$\leq d-p$$ (and in particular must vanish if $$d).