On many-to-one mappings over finite fields

Abstract

We introduce the definition of $m$-to-$1$ mappings between two finite sets, which unifies and generalizes the definitions of $2$-to-$1$ and $n$-to-$1$ mappings in recent literature. We also characterize these $m$-to-$1$ mappings in terms of the generalized local criterion and thus provide three generic constructions of $m$-to-$1$ mappings, which unify and generalize the previous known constructions. Using these constructions, the problem whether $x^{r}h(x^s)$ is $m$-to-$1$ on the multiplicative group ${\mathbb{F}}_q^{\ast }$ is converted into that whether an associated polynomial $x^{r_1}h(x{)}^{s_1}$ is $m_2$-to-$1$ on the order~$\ell$ subgroup~$U_{\ell }$ of ${\mathbb{F}}_q^{\ast }$, where $m_2=m/(r,s)$ and $\ell =(q-1)/s$. Furthermore, the $m_2$-to-$1$ property of $x^{r_1}h(x{)}^{s_1}$ on $U_{\ell }$ is studied in detail in four different cases. In addition, a recursive construction of $m$-to-$1$ mappings from $m$-to-$1$ mappings is proposed.