The distribution of patterns of inverses modulo a prime.
type: Item
instance of: scholarly article
title: The distribution of patterns of inverses modulo a prime.
zbMATH Open document ID: 1086.11045
DOI: 10.1016/S0022-314X(03)00059-3
author: C. I. Cobeli
author: Alexandru Zaharescu
author: Steven M. Gonek
published in: Journal of Number Theory
publication date: 2003-08-07T00:00:00Z
review text: 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.
reviewed by: Pieter Moree
Mathematics Subject Classification ID: 11N69
Mathematics Subject Classification ID: 11T23
Mathematics Subject Classification ID: 11K31
Mathematics Subject Classification ID: 11K45
Mathematics Subject Classification ID: 11L05
zbMATH DE Number: 1961833
zbMATH Keywords: multiplicative inverse
zbMATH Keywords: incomplete Kloosterman sum
MaRDI profile type: MaRDI publication profile
cites work: On Exponential Sums in Finite Fields
cites work: Exponential Sums and Goppa Codes: I
full work available at URL: s0022-314x(03)00059-3
OpenAlex ID: W2067879522
Recommended article: The distribution of inverses modulo a prime in short intervals
Recommended article: The order of inverses mod q
Recommended article: INCOMPLETE KLOOSTERMAN SUMS AND MULTIPLICATIVE INVERSES IN SHORT INTERVALS
Recommended article: Q4831474
Recommended article: On the distribution of inverses modulo \(n\)
description: scientific article; zbMATH DE number 1961833