Methods to bound the number of solutions to $x^x \equiv 1 \mod p$ with $1 \le x \le p$

Question

For a prime $p$, let $N(p)$ be the number of solutions $1 \le x \le p$ to $x^x \equiv 1 \mod p$. I am interested in methods to bound $N(p)$.

Background: This quantity appears in Problem 1 of the Miklós Schweitzer Competition 2010 where it was asked to prove $N(p) \ll p^{c}$ for some $c<\frac{1}{2}$. Let me quickly explain how one can solve this problem and why the exponent $\frac{1}{2}$ is critical. For each divisor $d$ of $p-1$, let $A_d$ be the set of numbers $1 \le x \le p$ for which $(x;p-1)=d$ and $x^x \equiv 1 \mod p$ so $N(p)=\sum_{d \mid p-1} \vert A_d\vert$. The condition $x^x \equiv 1 \mod p$ now just says that $x$ is a $e$-th power modulo $p$ where $e=\frac{p-1}{d}$ is the complementary divisor. So trivially $\vert A_d\vert \ll \min(d,e) \ll p^{1/2}$ and hence $N(p) \ll p^{1/2+\varepsilon}$.

To improve this exponent, it clearly suffices to improve the bound for $\vert A_d\vert$ when $d \approx e \approx p^{1/2}$. Here the sum-product theorem over finite fields comes in handy: Since $A_d+A_d$ still contains essentially only multiples of $d$, it is easy to see that $\vert A_d+A_d\vert \le 2e$ and similarly $A_d \cdot A_d$ still contains only $e$-th powers so that $\vert A_d \cdot A_d\vert \le d$. Hence $\max(\vert A_d +A_d\vert, \vert A_d \cdot A_d\vert) \ll \max(d,e)$. But by the (currently best-known version of the) sum-product theorem the LHS is at least $\vert A_d\vert^{5/4-\varepsilon}$ so that we get the bound $\vert A_d\vert \ll \max(d,e)^{4/5+\varepsilon}$ and we win. Indeed, working out the exponents, we can prove $N(p) \ll p^{4/9+\varepsilon}$ this way.

Now I would be curious to learn about

Question 1: What are some other techniques that can be applied to get a non-trivial bound for $N(p)$? To be clear, I would be equally interested in (possibly more difficult) techniques that lead to an exponent $c<\frac{4}{9}$ as well as more elementary techniques that lead to a (possibly worse, but) non-trivial result.

Now even if one assumes a best possible sum-product conjecture to be true, it seems that by the method described above we could only prove $N(p) \ll p^{1/3+\varepsilon}$. On the other hand, it seems natural to conjecture that even $N(p) \ll p^{\varepsilon}$ is true, albeit very hard to prove. Given this gap, I am wondering about

Question 2: Are there some "natural/standard" conjectures that would imply an exponent less than $\frac{1}{3}$, possibly even as small as an $\varepsilon$? Or is there a good heuristic why the exponent $\frac{1}{3}$ is a natural barrier here?

EDIT: As pointed out in the answers, Cilleruelo and Garaev (2016) proved $N(p) \ll p^{27/82}$. This leaves us with the question of whether there is a natural/standard conjecture that would imply that $N(p) \ll p^{\varepsilon}$.

PS: To be clear, I don't claim that this is a very important problem on its own right. It just seems like a good toy problem to test our understanding of the interference between multiplicative and additive structures.

Answer 1

The $1/3 + \varepsilon$ is not a barrier anymore!

Resorting to estimates of exponential sums over subgroups due to Shkredov and Shteinikov, in the paper "On the congruence $x^{x} \equiv 1 \pmod{p}$" (PAMS, 144 (2016), no. 6, pp. 2411 - 2418), J. Cilleruelo (†) and M. Z. Garaev proved the following result:

Let $J(p)$ denote the number of solutions to the congruence $$x^{x} \equiv 1 \pmod{p}, \quad 1 \leq x \leq p-1.$$ Then, for any $\varepsilon>0$, there exists $c:=c(\varepsilon)>0$ such that $J(p) < c \, p^{27/82 + \varepsilon}$.

I am not totally sure, but I believe that this theorem is the state of the art on this problem...

Answer 2

Another answer already gives a reference to a smaller exponent, but since the OP states that they are interested in an elementary proof, this is a proof I came up with which shows $c < \frac{3}{7} + \varepsilon$ (which is smaller than $\frac{4}{9}$).

For $A \subset \left( \mathbb{Z} / p \mathbb{Z} \right)^{*}$ we define $A A = \left\{ xy : x, y \in A \right\} \subset \mathbb{Z} / p \mathbb{Z}$ and $r (a) = \# \left\{ xy \equiv a : x, y \in A \right\}$, where throughout we will let $\equiv$ denote equality $\bmod p$ (just to simplify writing). We define the multiplicative energy of $A$ to be $E(A) = \# \left\{ x, y, z, w \in A : xy \equiv zw \right\}$. Notice that $$\sum_{x \in A A} 1 = \lvert A A \rvert$$ $$\sum_{x \in A A} r(x) = \lvert A \rvert^2$$ $$\sum_{x \in A A} r(x)^2 = E(A)$$ and so by Cauchy-Schwarz, $\lvert A \rvert^4 \leq \lvert A A \rvert E(A)$.

As stated in the post, it is sufficient to show $\lvert A_d \rvert \leq p^{3/7 + \varepsilon}$. Our strategy will be to bound $\lvert A_d A_d \rvert$ and $E(A)$. Notice that since every element of $A_d$ is a $d$-th root of unity, so is every element of $A_d A_d$, and therefore $\lvert A_d A_d \rvert \leq d$. Also, every element of $A_d$ is of the form $d x$, where $x < \frac{p}{d}$. This means that the multiplicative energy of $A_d$ is at most $$\# \left\{ x, y, z, w < \frac{p}{d} : xy \equiv zw \right\}$$ We split into cases according to the larger among $d$ and $\sqrt{p}$.

Case 1: $d > \sqrt{p}$. In this case, $xy \equiv zw$ is equivalent to $xy = zw$. Fixing $x, y$, the number of solutions is at most the number of divisors of $xy$, which is $\ll p^{\varepsilon}$, and so $E(A_d) \ll \frac{p^{2 + \varepsilon}}{d^2}$. This means that $$\lvert A_d \rvert \ll \left( d \cdot \frac{p^{2 + \varepsilon}}{d^2} \right)^{1/4} \ll p^{3/8 + \varepsilon}$$ which is even stronger than what we require.

Case 2: $d < \sqrt{p}$. Now, $xy \equiv zw$ means that $xy + pk = zw$ for some $k \leq \frac{p}{d^2}$. Fixing $x, y, k$ we have as before $\ll p^{\varepsilon}$ solutions, and so the multiplicative energy is at most $$\frac{p^{3 + \varepsilon}}{d^4}$$ which as before gives that $$\lvert A_d \rvert \ll \left( \frac{p}{d} \right)^{3/4 + \varepsilon}$$ This bound is relatively good for $d \approx \sqrt{p}$, however when $d$ is small this is quite bad. Luckily, we always have the trivial bound $\lvert A_d \rvert \leq d$. Optimizing, we get that $\lvert A_d \rvert \ll p^{3/7 + \varepsilon}$, as required.