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

2011/04/23 by Michael A. Forbes, Forbes, Michael, Neeraj Kayal +6 · 1 citation
Computer Science · Mathematics · #Algebraic Geometry and Number Theory #Analytic Number Theory Research #Coding theory and cryptography #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation #Symbolic Computation (cs.SC) #cs.SC #math.NT

paper · pdf · doi:10.48550/arxiv.1104.4557

11 pages

arxiv created 2011/04/23 · openalex publication_date 2011/04/23 · arxiv updated 2011/04/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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,1..., over a prime field \F_p, is bounded by 7/√(5) ⋅ b ⋅ √(p/k) + 4b + c. Our proof is inspired by the so called 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.

Cited by

• On Deterministically Finding an Element of High Order Modulo a Composite

Related

• Least primitive root and simultaneous power-non residues
• Conditional bounds for the least quadratic non-residue and related\n problems
• Upper Bound of the Least Quadratic Nonresidues
• On consecutive quadratic non-residues: a conjecture of Issai Schur
• Fourier optimization, the least quadratic non-residue, and the least prime in an arithmetic progression