Counting polynomials with distinct zeros in finite fields (Q503699)

Let \(F_q\) be a finite field with \(q=p^e\) elements, \(p\) a prime. Fix integers \(\ell\) and \(n\), \(0 < \ell < n < q\), and fix \(u(x)=x^n+u_{n-1}x^{n-1}+\cdots + u_{\ell +1}x^{\ell +1}\in F_q[x]\). Let \(N_k(u(x), \ell )\) be the number of \(v_{\ell}(x)\in F_q[x]\) such that \(\deg v_{\ell} \leq \ell\) and \(u(x)+v_{\ell}(x)\) has exactly \(k\) roots in \(F_q\). \(N_k(u, \ell)\) appears in graph theory, for computing the spectrum of certain Wenger graphs, and in coding theory where \(N_k(u, \ell)\) is the number of codewords \(v_{\ell}\) in a \([q, \ell +1]\) Reed-Solomon code of distance \(q-k\) from the received word \(u(x)\). When \(n-\ell =1\), a formula for \(N_k(u, \ell)\) was given by \textit{A. Knopfmacher} and \textit{J. Knopfmacher} [Linear Multilinear Algebra 26, No. 4, 287--292 (1990; Zbl 0699.12028)]. Here the authors give a formula for \(N_k(u, \ell )\) when \(n-\ell =2\) and when \(n-\ell =3\), \(p\) odd, \(e\) even and \(u(x)=x^n\). The proofs use the inclusion-exclusion principle (which also yields a simple proof of the \(n-\ell =1\) case) and results on the number of zeros of a quadratic form that lie in a hyperplane.