7
$\begingroup$

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

$\endgroup$

1 Answer 1

17
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.