The distribution of patterns of inverses modulo a prime. (Q1398947)

Let \(p\) be an odd prime and denote by \(\overline \nu\) the multiplicative inverse of \(\nu \pmod p\). Set \(S=\{{\overline \nu}\pmod p:M<\nu\leq M+N\}\), where \(M\geq 0\) and \(N\geq 1\) are integers such that \((M,M+N]\) is contained in the interval \((0,p)\). For \(1\leq s\leq N\), let \({\mathbf a}=(a_1,\dots,a_s)\) and \({\mathbf b}=(b_1,\dots,b_s)\) be \(s\)-tuples of integers such that the \(a_i\) are coprime to \(p\) and the elements \({\overline a_i}b_i,\ldots,{\overline a_s}b_s\) are distinct modulo \(p\). Let \[ X=X(a, b, S, p) =\{x: 1\leq x<p,\;a_jx+b_j \bmod p \text{ is in }S\text{ for }1\leq j<s\}. \] Heuristically, assuming that the events \(a_jx+b_j(\text{ ~mod~}p)\) is in \(S\) for \(1\leq j\leq s\) are independent, the probability that \(x\) is in \(X\) should be \((N/p)^s\) and so \(| X| \approx p(N/p)^s\). This suggests the conjecture that \(X\) is non-empty when \(N\gg p^{1-{1\over s}+\varepsilon}\). The authors prove that \(| X| =p(N/p)^s + O(sp^{1/2}\log^sp)\) uniformly for \(1\leq s\leq N<p\), whence \(X\) is non-empty if \(N\gg p^{1-{1\over 2s}}\log^{1+\varepsilon}p\). The authors also consider the distribution of \(X\) in short intervals through estimates for \(f(m,H)=| \{x \text{ in} X: m<x<M+H\}| \). The main result gives \(f(m,H)>0\) for a positive proportion of \(m\) in \([1,p]\) if \(N\gg p^{3/4}\log p\) (on heuristic grounds probably \(N\gg p^{\varepsilon}\) suffices). The proofs make use of estimates on incomplete Kloosterman sums.