Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.14/118660
43 Visitors
48 Hits
1 Downloads
- Title
- On pseudosquares and pseudopowers
- Related
- Landman, Bruce; Nathanson, Melvyn B.; Nešetřil, Jaroslav; Nowakowski, Richard J.; Pomerance, Carl and Robertson, Aaron. Combinatorial number theory : proceedings of the 'Integers Conference 2007', Carrollton, Georgia, USA, October 24-27, 2007, p.171-184
- Publisher
- Berlin ; New York : Walter de Gruyter
- Date
- 2009
- FoR/RFCD Code(s)
-
080200 Computation Theory and Mathematics
- Author/Creator
- Pomerance, Carl
- Author/Creator
- Shparlinski, Igor E
- Description
- Introduced by Kraitchik and Lehmer, an x-pseudosquare is a positive integer n ≡ I (mod 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(agXI log x) for a suitable constant ag. A bound of exp(agx log log xl 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.
- Description
- 14 page(s)
- Subject Keyword
- 080200 Computation Theory and Mathematics
- Subject Keyword
- pseudosquare
- Subject Keyword
- pseudopower
- Subject Keyword
- character sums
- Resource Type
- book chapter
- Organisation
- Macquarie University. Dept. of Computing
- Identifier
- http://hdl.handle.net/1959.14/118660
- Identifier
- ISBN:9783110202212
- Identifier
- mq-rm-2009006858
- Language
- eng
