On the distribution of multiplicative translates of sets of residues \((\text{mod }p)\)
type: Item
instance of: scholarly article
title: On the distribution of multiplicative translates of sets of residues \((\text{mod }p)\)
zbMATH Open document ID: 0806.11035
published in: Journal of Number Theory
publication date: 1995-02-13T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 11K99
Mathematics Subject Classification ID: 11A07
Mathematics Subject Classification ID: 11N69
zbMATH DE Number: 556375
zbMATH Keywords: distribution of residues
zbMATH Keywords: minimal residue
zbMATH Keywords: multiplicative translate
author: Johan Hastad
author: Jeffrey C. Lagarias
author: Andrew Odlyzko
reviewed by: Peter Hellekalek
MaRDI profile type: Publication
OpenAlex ID: W2044027384
Wikidata QID: Q56959119
DOI: 10.1006/JNTH.1994.1007
description: scientific article; zbMATH DE number 556375