On the Distribution of Multiplicative Translates of Sets of Residues (mod p)

AbstractLet 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 − ϵ holds for a wide range of r. These results are applicable to the analysis of certain randomization procedures