Small residue classes with small reciprocal

Question

Let $p$ be a large prime. For any $m \in \{1,\ldots,p-1\}$, let $\overline{m} \in \{1,\ldots,p-1\}$ be the reciprocal in ${\bf Z}/p{\bf Z}$ (i.e. the unique element of $\{1,\ldots,p-1\}$ such that $m \overline{m} = 1 \hbox{ mod } p$).

I am interested in finding $m$ for which for which $m$ and $\overline{m}$ are both small compared with $p$, excluding the trivial case $m=1$ of course. For instance, using Weil's bound on Kloosterman sums and some Fourier analysis, it is not difficult to show that there exists nontrivial $m$ with $\max(m, \overline{m}) \ll p^{3/4}$. But this does not look sharp; probabilistic heuristics suggest that one should be able to get $\max(m, \overline{m})$ as small as $O(p^{1/2})$ or so (ignoring log factors), which would clearly be best possible. Is some improvement on the $O(p^{3/4})$ bound known? For my specific application I would like to reach $O(p^{2/3})$. (I would also be willing to do some averaging in $p$ if this improves the bounds. I'm actually more interested in asymptotics for the number of $m$ with $\max(m,\overline{m})$ bounded by a given threshold, but the existence problem already looks nontrivial.)

I tried playing around with Karatsuba's bounds for incomplete Kloosterman sums, but it was not clear to me how to use them to get both $m$ and $\overline{m}$ into intervals smaller than $p^{3/4}$.

Answer 1

The following argument proves that for almost all $p\le x$, there are $m,n\le p^{1/2+\epsilon}$ with $mn\equiv1 \pmod p$.

Indeed, let $$ P=\{x/2<p\le x: m\le x^{1/2+\epsilon}\ \implies\ \overline{m}\pmod p>x^{1/2+\epsilon}\}. $$ Let $q$ be a prime in $(x^{1/2-\epsilon/2},x^{1/2-\epsilon/3}]$. If $1+kp\equiv 0\pmod q$ for some $k\le x^{\epsilon/2}/2$, then $1+kp=qd$ for some $d\le (1+kx)/x^{1/2-\epsilon/2}\le x^{1/2+\epsilon}$. In particular, $p$ is not in $P$. Therefore, if $p$ is counted by $P$, then for each $q\in (x^{1/2-\epsilon/2},x^{1/2-\epsilon/3}]$, it must avoid the congruence classes $\{-\overline{k}\pmod q: 1\le k\le x^{\epsilon/2}/2\}$. Since $p$ is prime is prime, it must also avoid the classes $0\pmod q$ for all primes $q\le \sqrt{x}$. We then apply the arithmetic form of the Large Sieve (see, e.g., page 159 in Davenport) to conclude that $$ \#P \ll \frac{\pi(x)}{x^{\epsilon/2}} , $$ which proves the claim.

The above result is essentially sharp: the number of $p\in(x/2,x]$ for which there are $m,n\le p^{1/2}(\log p)^c$ with $mn\equiv 1\pmod p$ is $o(\pi(x))$ for small enough $c$. Indeed, we would then have that there is some $k\le (\log x)^{2c}$ such that $1+kp$ can be written as $1+kp=mn$ with $m\le n\le x^{1/2}(\log x)^c$. In particular, $1+kp$ would have a divisor $m\in[0.1k\sqrt{x}/(\log x)^c, \sqrt{1+kx}]$. The number of such primes $p\in(x/2,x]$ is $$ \asymp f(k) \frac{x}{\log x} \frac{1+\left(\log\frac{(\log x)^{2c}}{k}\right)^\delta}{(\log x)^\delta(\log\log x)^{3/2}}, $$ where $\delta=1-(1+\log\log2)/\log 2$ is the constant appearing in Erdos's multiplication table problem and $f(k)$ is some tame multiplicative function that is usually $\asymp1$ (see http://arxiv.org/abs/math/0401223 and http://arxiv.org/abs/0905.0163. This result is not stated there but it should follow from the methods. The upper bound uses the sieve. For the lower bound, instead of the Bombieri-Friedlander-Iwaniec result on primes in APs to large moduli, we would have to use Zhang's result because we need information about the distribution of primes in progressions $a\pmod q$ with $1+ak\equiv0\pmod q$, so $a$ is not fixed.) Summing over $k\le(\log x)^{2c}$, we find that the number of $p\in(x/2,x]$ for which there are $m,n\le p^{1/2}(\log p)^c$ with $mn\equiv 1\pmod p$ is $$ \ll \frac{x}{\log x} \frac{(\log x)^{2c}}{(\log x)^\delta(\log\log x)^{3/2}} . $$ Taking $c=\delta/2$ yields the claimed result.

The above line of thought should be able to produce, at least heuristically, the optimal value of $c$ for which the following two propositions hold: $$ \#\{p\le x: \exists m,n\le p^{1/2}(\log p)^{c+\epsilon}\ \text{with}\ mn\equiv 1\pmod p\} \sim \pi(x) $$ and $$ \#\{p\le x: \exists m,n\le p^{1/2}(\log p)^{c-\epsilon}\ \text{with}\ mn\equiv 1\pmod p\} =o(\pi(x)). $$ The point is that if $k\neq k'$, then the multiplicative structures of $1+kp$ and of $1+k'p$ should be independent from each other. Therefore the events that $1+kp=mn$ for some $m,n$ in some range and that $1+k'p=m'n'$ for some $m',n'$ in some range should be independent. So a Borel-Cantelli argument would then yield the optimal value of $c$.

Answer 2

Professor Tao,

I do not know whether this answer is in the least useful but will post it anyway!

I'm not sure but perhaps one approach is via Linnik's theorem that the least prime, say, $p(r,q)$ in an arithmetic progression $r \bmod q$, is $\ll q^L$.

(I actually saw that topic on Math Overflow recently: least prime in a arithmetic progression )

If $p \equiv -b \bmod a$ and $p \equiv -1 \bmod b$, with $(a,b)=1$ and $b$ of size about $a^2$, then one can take

$$ m = \frac{p+b}{a} $$

and

$$ \overline{m} = \frac{a(p+1)}{b}. $$

But then $p$ is in an arithmetic progression of modulus of size about $a^3$, so

$$ \max(m,\overline{m}) \ll p^{1-1/(3L)}. $$

However, currently the state of knowledge of $L$ is not good enough.

EDIT:

Actually, one can take $a,b$ about the same size, $(a,b)=1$, $p\equiv -b \bmod a$ and $p \equiv -a \bmod b$, and

$$ m = \frac{p+b}{a} $$

and

$$ \overline{m} = \frac{p+a}{b}. $$

Then $p$ is in an arithmetic progression of modulus of size about $a^2$, and

$$ \max(m,\overline{m}) \ll p^{1-1/(2L)}. $$