2007/12/07 by Carl Pomerance, Pomerance, Carl, Igor E. Shparlinski +1 · 1 citation
Mathematics · #11A15 #11L40 #Algebraic Geometry and Number Theory #Analytic Number Theory Research #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT) #math.NT #msc:11A15 #msc:11L40
paper · pdf · doi:10.48550/arxiv.0712.1081
openalex publication_date 2007/12/07 · arxiv created 2007/12/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Introduced by Kraitchik and Lehmer, an x-pseudosquare is a positive integer n≡1\pmod 8 that is a quadratic residue for each odd prime p≤ x, yet is not a square. We use bounds of character sums to prove that pseudosquares are equidistributed in fairly short intervals. An x-pseudopower to base g is a positive integer which is not a power of g yet is so modulo p for all primes p≤ x. It is conjectured by Bach, Lukes, Shallit, and Williams that the least such number is at most exp(ag x/log x) for a suitable constant ag. A bound of exp(ag xloglog x/log x) is proved conditionally on the Riemann Hypothesis for Dedekind zeta functions, thus improving on a recent conditional exponential bound of Konyagin and the present authors. We also give a GRH-conditional equidistribution result for pseudopowers that is analogous to our unconditional result for pseudosquares.