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