Polynomials which are functionally equivalent over finite fields

Question

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$?

Answer 1

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<p$).