Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant

Abstract

We give a new elementary proof of the fact that the value of the least $k^{th}$ power non-residue in an arithmetic progression $\{bn+c{\}}_{n=0,\mathrm{1...}}$, over a prime field $\F_p$, is bounded by $7/\sqrt{5}\cdot b\cdot \sqrt{p/k}+4b+c$. Our proof is inspired by the so called \emph{Stepanov method}, which involves bounding the size of the solution set of a system of equations by constructing a non-zero low degree auxiliary polynomial that vanishes with high multiplicity on the solution set. The proof uses basic algebra and number theory along with a determinant identity that generalizes both the Sylvester and the Vandermonde determinant.

11 pages