On the characterization of minimal value set polynomials (Q1946718)

Let \(q\) be a power of a prime \(p\), and for any non-constant polynomial \(f \in \mathbb{F}_q[x]\) with degree \(n\), let \(V_f = \{f(\alpha) \mid \alpha \in \mathbb{F}_q\}\) be its value set. It is easy to see that \(|V_f| \geq \lfloor \frac{q-1}{n} \rfloor +1\) because \(f\) has no more than \(n\) zeroes. A polynomial \(f\) attaining this lower bound is called a \textit{minimal value set polynomial} (mvsp). \textit{L. Carlitz} et al. [Mathematika 8, 121--130 (1961; Zbl 0106.01105)] characterized mvsps of degree \(\leq 2p+2\). \textit{W. Mills} [Pac. J. Math. 14, 225--241 (1964; Zbl 0126.03004)] characterized all mvsps of degree \(\leq \sqrt{q}\). In the first part of this paper, the authors extended Mills's result in two ways. One is a complete characterization of all mvsps in \(\mathbb{F}_q[x]\) of degree \(\sqrt{q} +1\); the other one is a proof of the uniqueness (up to composition with degree one polynomials) of a mvsp with degree \(\leq \sqrt{q}\) for a given set of values. In the second part of this paper, the authors address the general problem of characterizing mvsps with an arbitrary prescribed value set. In particular, when the prescribed value set is a subfield \(\mathbb{F}_{q^\prime}\) of \(\mathbb{F}_q\), their characterization is complete and explicit. In this case, they prove that the set of such mvsps, together with the constants in \(\mathbb{F}_{q^\prime}\), is an \(\mathbb{F}_{q^\prime}\)-vector space of dimension \(2^{[\mathbb{F}_q:\mathbb{F}_{q^\prime}]}\). This approach provides both the exact number of such polynomials and a construction of new examples of mvsps.