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

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: http://mathoverflow.net/questions/80865/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)}. $$