Counting Polynomials with Distinct Zeros in Finite Fields

Abstract

Let ${\mathbb{F}}_q$ be a finite field with $q=p^e$ elements, where $p$ is a prime and $e\ge 1$ is an integer. Let $\ell <n$ be two positive integers. Fix a monic polynomial $u(x)=x^n+u_{n-1}{x}^{n-1}+\cdots +u_{\ell +1}{x}^{\ell +1}\in {\mathbb{F}}_q[x]$ of degree $n$ and consider all degree $n$ monic polynomials of the form $$f(x)=u(x)+v_{\ell }(x),v_{\ell }(x)=a_{\ell }{x}^{\ell }+a_{\ell -1}{x}^{\ell -1}+\cdots +a_{1}x+a_0\in {\mathbb{F}}_q[x].$$ For integer $0\le k\le \min \{n,q\}$, let $N_k(u(x),\ell )$ denote the total number of $v_{\ell }(x)$ such that $u(x)+v_{\ell }(x)$ has exactly $k$ distinct roots in ${\mathbb{F}}_q$, i.e. $$N_k(u(x),\ell )=|\{f(x)=u(x)+v_l(x)|f(x)\mathrm{has}\mathrm{exactly}k\mathrm{distinct}\mathrm{zeros}\mathrm{in}{\mathbb{F}}_q\}|.$$ In this paper, we obtain explicit combinatorial formulae for $N_k(u(x),\ell )$ when $n-\ell$ is small, namely when $n-\ell =1,2,3$. As an application, we define two kinds of Wenger graphs called jumped Wenger graphs and obtain their explicit spectrum.