TY - JOUR

T1 - On the distribution of multiplicative translates of sets of residues (mod p)

AU - Håstad, J.

AU - Lagarias, J. C.

AU - Odlyzko, A. M.

PY - 1994/1

Y1 - 1994/1

N2 - Let R be a set of r distinct nonzero residues modulo a prime p, and suppose that the random variable a is drawn with the uniform distribution from {1, 2,…, p - 1}. We show for all sets R that (p - 2)/(2r) ≤ E[min[aR]] ≤ 100 p/r1/2, where in the set aR each integer is identified with its least positive residue modulo p. We give examples where E[min[aR]] ≤ 0.8 p/r and E[min[aR]] ≥ 0.4 p(log r)/r. We conjecture that E[min[aR]] ≪ p/r1 - ε{lunate} holds for a wide range of r. These results are applicable to the analysis of certain randomization procedures.

AB - Let R be a set of r distinct nonzero residues modulo a prime p, and suppose that the random variable a is drawn with the uniform distribution from {1, 2,…, p - 1}. We show for all sets R that (p - 2)/(2r) ≤ E[min[aR]] ≤ 100 p/r1/2, where in the set aR each integer is identified with its least positive residue modulo p. We give examples where E[min[aR]] ≤ 0.8 p/r and E[min[aR]] ≥ 0.4 p(log r)/r. We conjecture that E[min[aR]] ≪ p/r1 - ε{lunate} holds for a wide range of r. These results are applicable to the analysis of certain randomization procedures.

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

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

U2 - 10.1006/jnth.1994.1007

DO - 10.1006/jnth.1994.1007

M3 - Article

AN - SCOPUS:43949161644

SN - 0022-314X

VL - 46

SP - 108

EP - 122

JO - Journal of Number Theory

JF - Journal of Number Theory

IS - 1

ER -