Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper establishes improved average-case bounds for $G(n)$, the smallest integer such that coprime integers up to $G(n)$ generate the multiplicative group of integers modulo $n$. The authors prove $\sum_{n\leq x}G(n)\ll_\varepsilon x(\log x)^{8/3+\varepsilon}$, a significant improvement over prior work. Furthermore, they show that $G(n)\leq(\log n)^2$ for almost all $n$ unconditionally, matching the GRH-predicted pointwise bound.
For almost all integers $n$, the generators of $(\mathbb Z/n\mathbb Z)^\times$ are surprisingly small, bounded by $(\log n)^2$ unconditionally.
In this paper we study the least positive integer $G(n)$ such that the integers $a\leq G(n)$ with $(a,n)=1$ generate $(\mathbb Z/n\mathbb Z)^\times$. We prove that, for every $\varepsilon>0$, \[ \sum_{n\leq x}G(n)\ll_\varepsilon x(\log x)^{8/3+\varepsilon}, \] improving the previously known bound $\ll x(\log x)^{97}$. We also prove that $G(n)\leq(\log n)^2$ for almost all $n$, unconditionally. Thus, for almost all $n$, we obtain the same logarithmic exponent $2$ as in the classical pointwise bound under GRH.