On fixed point probability in discrete logarithm

Question

Fix an integer $n>2$.

Question. What is the probability that, for a given $h\in\Bbb Z_n,$ there is no $$x\in[0,\varphi(n)-1]\cap\Bbb Z$$ such that $h^{x\bmod\varphi(n)}\equiv x\bmod n$?

Answer 1

It is not an answer but some additional information.

The problem about fixed points of discrete logarithms is known the Brizolis problem. In particular for the average number of solutions $$N(p)=\frac{1}{\varphi(p-1)}\sum_g\left|\{0\le x\le p-1:g^x=x\pmod p\}\right|$$ is known that (Grechnikov, 2012, PhD thesis; published in Two-side estimates of the number of fixed points of a discrete logarithm) $N(p)=1+S(p)$, where $$-C(\varepsilon)p^{-1/4+\varepsilon}\le S(p)\le \exp(C'\mathrm{Li}((\log p)^{c\frac{\log\log\log\log p}{\log\log\log p}})).$$

Answer 2

This is more a collection of numerical experiments than an answer, but it's too long for a comment.

I've reinterpreted the question slightly; hopefully this keeps to the spirit of the OP's intent.

• First, it feels more natural (to me) to take $x$ from $[0,n-1]$ rather than $[0,\phi(n)-1]$, so the following experiments consider that case.
• Second, the question as posed isn't probabilistic: for a given $n,h$, the answer is deterministically "yes" or "no". To address that, let $A(N)$ be the number of fixed points if we select $h$ uniformly at random from $[0,n-1]$ (so, $A(N)$ is a random variable).

We can then consider: $$L_{all}(c)=\lim_{n\rightarrow \infty} \Pr[A(n)=c]$$ where $c$ is a count of the number of fixed points. So, if $c=0$, we're asking about the probability of no fixed points; if $c=3$, we're asking about the probability that, for a randomly chosen $h$, that there are exactly 3 fixed points as $x$ varies.

Note: there is no reason to think that this limit actually exists.

Rather than considering the limit over all $n$, we can restrict to, for example the primes. Let $\mathcal{P}$ be the set of primes, and let $$L_{primes}(c)=\lim_{n\rightarrow \infty, n\in\mathcal{P}} \Pr[A(n)=c]$$

Now, if we pretend that $h^x \bmod n$ is a uniformly random draw from $[0,n-1]$, then the probability of a fixed point is $1/n$. In that case, the distribution of the number of fixed points would be a Poisson distribution with $\lambda=1$, so we would have $$L_{primes}(c)=\frac{1}{e(c!)}$$ (In particular, the probability of no fixed points is $1/e\approx 0.36788$.)

We can estimate $L_{primes}$ through the Monte Carlo method: we choose some large $n$ (I took all prime $n$ from 20,000 to 24,000), select a few $h$ for each $n$ (I took 100) and measure the fraction of $h$ with $c=0,1,2,...$ fixed points. My experiment matches the "uniform draw" model extremely tightly: (It's actually a little hard to tell that there are two lines plotted there.)

At the other extreme, we can consider the limit across smooth numbers. I took all the numbers between $20,000$ and $124,000$ whose largest prime factor was at most 11 and did the same Monte Carlo experiment. Let $L_{smooth}(c)$ be the corresponding limit. The plot of $L_{smooth}(c)$ is quite different:

To get some sense of why this these cases are so different, we can consider $\Pr[A(n)>0]$ for particular values of $n$. If we range over the primes, this probability hovers around 0.63 (i.e., 1-1/e), give or take 0.2: On the other hand, if we range over smooth numbers, we frequently have $\Pr[A(n)>0] = 1$ (which never happens in the prime case): Be warned that these probability estimates are Monte Carlo sampled, so may not be exactly 1. Nevertheless, the difference is pretty striking.