On the distribution of multiplicative translates of sets of residues \((\text{mod }p)\) (Q1320512)

Let \(p\) be a prime and let \(\mathbb{R}\) be a set of \(r\) distinct nonzero residues modulo \(p\). We draw the random variable \(a\) uniformly from \(\mathbb{Z}^*_ p\) and denote the normalized expected size of the minimal residue in the multiplicative translate \(a\mathbb{R}\) modulo \(p\) by \[ M^*(\mathbb{R}):= {\textstyle {1\over p}} E[\min(a\mathbb{R})]. \] The objective of the authors is to obtain upper and lower bounds for \(M^*(\mathbb{R})\) that depend only on the size \(r=| \mathbb{R}|\). The expected size of \(M^*(\mathbb{R})\), averaged over all sets \(\mathbb{R}\) of cardinality \(r\), is given by \[ E[M^* (\mathbb{R}):\;|\mathbb{R}| =r]= {1\over {r+1}}. \tag{1} \] The authors prove that, for all sets \(\mathbb{R}\pmod p\) with \(r=| \mathbb{R}|\), \(M^*(\mathbb{R})\geq {1\over {2r}}- {1\over {pr}}\). They show that for all primes \(p\) and all sets \(\mathbb{R}\pmod p\) with \(r=| \mathbb{R}|\), \(M^*(\mathbb{R})\leq 100r^{-1/2}\). It is shown by example that the worst-case upper bound cannot be the same order of magnitude as (1). The authors conjecture that, for every \(\varepsilon>0\), there is a constant \(C(\varepsilon)\) such that for all primes \(p\) and all sets \(\mathbb{R} \pmod p\) \[ M^*(\mathbb{R})\leq C(\varepsilon) r^{-1+\varepsilon}. \] The truth of this conjecture would imply a conjecture of Linnik on the magnitude of the minimal quadratic nonresidue modulo \(p\). The central question of this paper is shown to be related to a randomization scheme to select an element of a set \({\mathbf S}\) of distinct integers in \([0, p-1]\), where the size \(|{\mathbf S}|\) is not specified in advance. Further, the relation to some problems concerning pseudorandom numbers of the type \(a\mathbb{R} +b\pmod p\) in \(\{0,1,\dots, p-1\}\), \(a\) and \(b\) drawn independently from the uniform distribution on \(\mathbb{Z}^*_ p\), respectively \(\mathbb{Z}_ p\), is exhibited.