2
$\begingroup$

In an explicit construction in combinatorics I need to study the following problem: assume we pick a odd prime number $p$, a generator $g$ of the multiplicative group $(Z/pZ)^{\ast}$.

Question 1: for how many $x\in\{2,\dots,p-2\}$, is it true that $x\equiv g^x\, (p)$.

Question 2: how the previous counting depends on the choice of $g$?

In general I would need indeed the number of solutions of the congruence equation $x\equiv a+g^x\, (p)$ (for fixed $a$), but already the base case $a=0$ is interesting for me.

$\endgroup$
1
$\begingroup$

Just to take an arbitrary example, mod $p = 23$ there are $\phi(22) = 10$ primitive roots. Of those, four ($14, 19, 20, 21$) have no solutions to $x \equiv g^x \mod 23$, two have one, three have two, and one ($11$) has five.

Here, for each of the first $30$ primes, are the number of primitive roots $g$ for which there are no solutions to $x \equiv g^x \mod p$ with $2 \le x \le p-2$:

$$1, 1, 1, 1, 2, 1, 1, 3, 4, 2, 1, 6, 5, 2, 9, 11, 12, 5, 7, 9, 8, 8, 17, 12, 11, 16, 12, 23, 20, 16$$

This sequence does not seem to be in the OEIS (yet).

[EDIT: Although this one is not in OEIS, the number of $g$ for where there are solutions is: OEIS sequence A174407].

For each prime $< 1000$, the number of such $g$ is at least $1$.

The probability of a random permutation of $[1\ldots p-1]$ being a derangement is approximately $1/e$, so heuristically we might expect about that fraction of the primitive roots to have no solution to $x \equiv g^x \mod p$.

$\endgroup$
  • $\begingroup$ Maybe we should not include $g=\pm1$ in the discussion, as these are not generators? $\endgroup$ – T. Amdeberhan May 9 '17 at 21:55
  • $\begingroup$ This was just counting generators $g$. $\endgroup$ – Robert Israel May 9 '17 at 22:59
  • $\begingroup$ Dumb (?) question: Is it obvious there should be at least one generator with no fixed points for each odd prime? $\endgroup$ – kodlu May 10 '17 at 22:37
  • 1
    $\begingroup$ No, it is not at all obvious to me. Heuristically, if the probability of a generator having no fixed points is about $1/e$, and there are $\phi(p-1)$ generators, the probability that none of them have a fixed point is about $(1-1/e)^{\phi(p-1)}$, and this goes to $0$ rapidly enough that it's not surprising. But that's not a proof. $\endgroup$ – Robert Israel May 10 '17 at 23:04
  • $\begingroup$ @RobertIsrael The paper by Levin, Pomerance and Soundararajan pointed out in the comment to the question by Lucia actually proves this. $\endgroup$ – kodlu May 11 '17 at 1:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.