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

✍ Scribed by J. Hastad; J.C. Lagarias; A.M. Odlyzko

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 428 KB
• Volume: 46
• Category: Article
• ISSN: 0022-314X
• DOI: 10.1006/jnth.1994.1007

✦ Synopsis

Let (\mathbf{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, \ldots, p-1}). We show for all sets (\mathbf{R}) that ((p-2) / 2 r) \leqslant E[\min [a \mathbf{R}]] \leqslant 100 p / r^{1 / 2}), where in the set (a \mathbf{R}) each integer is identified with its least positive residue modulo (p). We give examples where (E[\min [a \mathbf{R}]] \leqslant 0.8 p / r) and (E[\min [a \mathbf{R}]] \geqslant 0.4 p(\log r) / r). We conjecture that (E[\min [a \mathbf{R}]] \ll p / r^{1-r}) holds for a wide range of (r). These results are applicable to the analysis of certain randomization procedures. 1994 Academic Press, Inc.