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

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/r^1/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/r^{1 - ε{lunate}} holds for a wide range of r. These results are applicable to the analysis of certain randomization procedures.