Exponential sums and the distribution of inversive congruential pseudorandom numbers with prime-power modulus (Q4486448)

Let \({\mathcal U}_m= (\mathbb{Z}/ p^m\mathbb{Z})^*\) be the group of reduced residue classes modulo \(p^m\), where \(p\geq 3\) is prime and \(m\in \mathbb{N}\). For \(a,b\in \mathbb{Z}/ p^m\mathbb{Z}\) with \(\text{gcd} (a,p)=1\) and \(b\equiv 0\pmod p\), define a map \(\psi:{\mathcal U}_m\to \mathbb{Z}/ p_m\mathbb{Z}\) by \(\psi(w)= aw^{-1}+ b\), \(w\in {\mathcal U}_m\). Taking \(u_0\in {\mathcal U}_m\) and setting \(u_{n+1}= \psi(u_n)\), \(n=0,1,\dots\), we obtain a sequence of elements of \({\mathcal U}_m\). It is purely periodic with least period length \(\tau\leq (p-1)p^{m-1}\). Denote \(S_N(h)= \sum_{n=0}^{N-1} \exp (2\pi ihu_n/ p^m)\). The authors prove that if \(m\geq 2\) and \(h\in \mathbb{Z}\) with \(\text{gcd} (h,p^m)= p^d\), \(0\leq d< m\), then \[ |S_N(h)|< \tfrac{49}{16} (p^m \tau^{-1})^{1/2} N^{1/2} p^{(m+d)/4} \quad\text{for }1\leq N\leq \tau. \] Using this estimate, they also give the discrepancy of the sequence \(\{u_n/ p^m\}_{n=0}^{N-1}\) \[ D_N< (p^m/ \tau)^{1/2} N^{-1/2} p^{m/4} (1.8\log N+15.1) \quad\text{for }1\leq N\leq \tau. \] It is the first nontrivial discrepancy bound for parts of the period of inverse congruential pseudorandom numbers with prime-power modulus.