TY - JOUR

T1 - On gaps between primitive roots in the hamming metric

AU - Dietmann, Rainer

AU - Elsholtz, Christian

AU - Shparlinski, Igor E.

PY - 2013/12

Y1 - 2013/12

N2 - We consider a modification of the classical number theoretic question about the gaps between consecutive primitive roots modulo a prime p, which by the well-known result of Burgess are known to be at most p1/4+o(1). Here we measure the distance in the Hamming metric and show that if p is a sufficiently large r-bit prime, then, for any integer n∈[1, p], one can obtain a primitive root modulo p by changing at most 0.11002786... r binary digits of n. This is stronger than what can be deduced from the Burgess result. Experimentally, the number of necessary bit changes is very small. We also show that each Hilbert cube contained in the complement of the primitive roots modulo p has dimension at most O(p1/5+ε), improving on previous results of this kind.

AB - We consider a modification of the classical number theoretic question about the gaps between consecutive primitive roots modulo a prime p, which by the well-known result of Burgess are known to be at most p1/4+o(1). Here we measure the distance in the Hamming metric and show that if p is a sufficiently large r-bit prime, then, for any integer n∈[1, p], one can obtain a primitive root modulo p by changing at most 0.11002786... r binary digits of n. This is stronger than what can be deduced from the Burgess result. Experimentally, the number of necessary bit changes is very small. We also show that each Hilbert cube contained in the complement of the primitive roots modulo p has dimension at most O(p1/5+ε), improving on previous results of this kind.

UR - http://www.scopus.com/inward/record.url?scp=84890601108&partnerID=8YFLogxK

U2 - 10.1093/qmath/has022

DO - 10.1093/qmath/has022

M3 - Article

AN - SCOPUS:84890601108

SN - 0033-5606

VL - 64

SP - 1043

EP - 1055

JO - Quarterly Journal of Mathematics

JF - Quarterly Journal of Mathematics

IS - 4

ER -