To what extent do value sets determine polynomials mod p?

Question

Let $f$ denote a polynomial mod $p$ and associate to it its value set $S_{f} := \{f(x):x \in F_p\}$.

If $|S_{f}|=p$ then $f$ is called a permutation polynomial (because it permutes the elements of $F_p$). Obviously, affine transformations (degree 1 polynomials) are permutation polynomials, but there are less trivial examples as well, and there is a substantial literature on these.

It is a theorem of Wan that if $f$ is not a permutation polynomial then $|S_f| \leq (1-d^{-1})p + 1/d$ where $d$ is the degree of $f$. Put differently, if $f$ is not a permutation polynomial it misses a constant fraction of the elements of $F_p$.

I'd like to understand to what extent does $S_f$ determines $f$. The existence of non-trivial permutation polynomials is one impediment here. For instance if, $\rho$ is a permutation polynomial then $S_f =S_g$ for $g= f \circ \rho$ or $g = \rho \circ f$. Of course the degree of $f$ and $g$ will now differ unless $\rho$ is an affine transformation. But one could also take a two distinct permutation polynomials of the same degree $\rho_1$ and $\rho_2$ and any polynomial $h$ and form $f= \rho_1 \circ h$ and $g = \rho_2 \circ h$, and get two distinct polynomials of the same degree with the same value set.

I'd like to understand if all examples of polynomials with the same degree come from permutation polynomials.

To pose a concrete question:

Let $f$ and $g$ be degree $d$ indecomposable* polynomials which are not permutation polynomials on $F_p$ and $S_f = S_g$. To avoid possible degeneracies further assume that $p$ is sufficiently large compared to $d$. Does this imply that there is an affine map $\rho$ such that $g= f \circ \rho$ or $g = \rho \circ f$?

I'd be interested in any positive results along the lines of what I am asking.

*By indecomposable I mean that $f$ can't be written of the composition of lower degree polynomials at least one of which is degree greater than $1$.

Answer 1

There need not be such a $\rho$. Let $f$ and $g$ be polynomials such that $S_f=S_g$. This means that for every $t_0\in\mathbb F_p$, $f(X)-t_0$ has a root if and only if $g(X)-t_0$ has a root. Modulo some details, and if $p$ is big compared to the degrees of $f$ and $g$, this means the the following: Let $L$ be a splitting field of $(f(X)-t)(g(X)-t)$ over $\mathbb F_p(t)$, and $G$ be its Galois group. Then every $g\in G$ fixes a root of $f(X)-t$ if and only if $g$ fixes a root of $g(X)-t$. That's exactly the notion of Kronecker equivalence of polynomials.

At least in characteristic $0$, the smallest such pair appears in degree $7$. There $G=\text{GL}_3(2)$, and the actions on the roots of $f(X)-t$ or $g(X)-t$ corresponds to the actions of $\text{GL}_3(2)$ on the nonzero points or hyperspaces of $\mathbb F_2^3$, respectively.

Such polynomial examples exist over $\mathbb Q(\sqrt{-7})$. Reducing them modulo $p$ where $-7$ is a square modulo $p$ then gives the desired examples.

Instead of more theoretical arguments, I'll provide an explicit example for some big $p$:

Pick $p=10007$ and set \begin{align} f &= x^7 + 4x^5 + 152x^4 + 2836x^3 + 8172x^2 + 3483x + 1032\\ g &= x^7 + 97x^5 + 3686x^4 + 1231x^3 + 6276x^2 + 9486x + 5012 \end{align} Then $S_f=S_g$, $f$ is not a permutation polynomial, and there are no affine functions $\rho_1,\rho_2$ such that $f=\rho_1\circ g\circ\rho_2$. A SageMath code which verifies these three claims is

p = 10007
R.<x> = GF(p)[]
f = x^7 + 4*x^5 + 152*x^4 + 2836*x^3 + 8172*x^2 + 3483*x + 1032
g = x^7 + 97*x^5 + 3686*x^4 + 1231*x^3 + 6276*x^2 + 9486*x + 5012
S_f = {f(x=z) for z in GF(p)}
S_g = {g(x=z) for z in GF(p)}
print(S_f == S_g and len(S_f) < p)
print([c for c in GF(p) if c != 0 and f == c^7*g(x=x/c)] == [])

Even better, $S_f$ equals $S_g$ as multisets:

M_f = [f(x=z) for z in GF(p)]
M_g = [g(x=z) for z in GF(p)]
print(sorted(M_f) == sorted(M_g))

In fact one would expect this because for each $g\in\text{GL}_3(2)$ the number of nonzero vectors fixed by $g$ equals the number of hyperspaces fixed by $g$.