6
$\begingroup$

Let $p$ be an odd prime, $g$ a primitive root of $p$ and $A=\{1, 2, \ldots, p-1 \}$.

Obviously, $\sigma_g(p)=\begin{pmatrix} 1 & 2 & \ldots & {p-1} \\ g^1\pmod{p} & g^2\pmod{p} & \ldots & g^{p-1}\pmod{p} \end{pmatrix}$ is a permutation of $A$.

I observed that "almost always" $\sigma$ is a product of cycles whose length is strictly less than $p-1$.
If $p=3$ and $g=2$, then $\sigma_2(3)=\begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}=(1\quad2)$ is a cycle of length $3-1=2$.

If $p=5$ and $g=3$, then $\sigma_3(5)=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{pmatrix}=(1\quad 3\quad 2\quad 4)$ is a cycle of length $5-1=4$.
But these two cases seem to be just exceptions.
For other (small) values of $p$ and every primitive root $g$ of $p$, there are no cycles of length $p-1$.

I can prove that $g=2$ and $g=\frac{p+1}{2}$ cannot produce such a big cycle, but I do not have any idea how to attack the problem for other values of $g$.
I conjecture that for every $g$ there is not such a big cycle (for sufficiently large $p$)

My question is:

Do only finitely many primes $p$ exist, such that for some primitive root $g$ the permutation $\sigma_g(p)=\begin{pmatrix} 1 & 2 & \ldots & {p-1} \\ g^1\pmod{p} & g^2\pmod{p} & \ldots & g^{p-1}\pmod{p} \end{pmatrix}$ is a cycle?

$\endgroup$
  • 1
    $\begingroup$ Apparently, there are a lot of counterexamples. Smallest ones are $p = 23, g = 20$; $p = 41, g = 6$; $p = 59, g = 39$; $p = 61, g = 10$; $p = 107, g = 94$. They don't stop appearing as $p$ grows either (and there are $p$-s, for which more than one $g$ is suitable). So it seems that the answer is more probably "No" than "Yes". $\endgroup$ – Kaban-5 Jul 29 '18 at 22:04
  • $\begingroup$ @Kaban-5 what are the first few $p$ for which there is more than one $g$ leading to a $(p-1)$-cycle, and what are all such $g$ for those $p$? $\endgroup$ – KConrad Jul 30 '18 at 11:42
  • $\begingroup$ Two possible $g$'s: $p = 587, g = 150, 375$; $p = 751, g = 240, 263$; $p = 809, g = 265, 750$; $p = 811, g = 113, 165$. Three: $p = 1889, g = 479, 859, 1248$; $p = 2267, g = 61, 976, 2010$; $p = 2699, g = 427, 639, 1256$; $p = 3491, g = 1472, 1626, 1833$. Four: $p = 5417, g = 1319, 1566, 3486, 5290$; $p = 7691, g = 558, 1434, 6244, 6760$. Five and more does not happen for $p \leqslant 10^4$. I believe that this should happen eventually anyway because heuristics suggest that, at least assuming that the number of Sophie Germain primes is infinite (probably unnecessary). $\endgroup$ – Kaban-5 Jul 30 '18 at 16:21
3
$\begingroup$

As pointed out in the comments, primitive roots with a single cycle appear to be rather common. The standard heuristic argument suggests that there are infinitely many such $p$, and a bit more.

The share of $N$-cycles among all permutations on $N$ symbols is $1/N$. By the Borel-Cantelli lemma, given an infinite sequence $\{\sigma_i\}$ of independent uniformly distributed random permutations on $N_i$ symbols, if $\sum 1/N_i$ diverges then with probability one infinitely many $\sigma_i$ constitute a single cycle. Since the series of reciprocal primes diverges, we may expect that given a random sequence $\{g_i\}$ of primitive roots mod $p_i$ over all primes, with probability one there are infinitely many $\sigma_i=\sigma_{g_i}(p_i)$ that constitute a single cycle. Of course, since uniform distribution and independence are only heuristic, this is not a proof!

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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