11
$\begingroup$

Define a digraph $P=(V,E)$ with $V$ equal to the set of prime numbers and an arrow from $p$ to $q$ if $p|q-1$ (definition motivated by Pratt's primality certificates).

Does $P$ indeed admit only the trivial automorphism (as seems reasonable to guess)?

Edit: In light of Gjergji Zaimi's heuristic suggesting a very large automorphism group, perhaps the better question asks what can one say, otherwise unconditionally, about hypothetical nontrivial automorphisms of $P$ and the permutations of ${\Bbb N}$ that they induce.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Is the solution known if p,q are not necessary prime, just naturals? $\endgroup$
    – joro
    Commented Jul 23, 2012 at 10:05
  • 1
    $\begingroup$ @joro I believe Gjergji Zaimi's sketch works unconditionally with the requirement of primality dropped. $\endgroup$
    – David Feldman
    Commented Jul 23, 2012 at 21:48

1 Answer 1

Reset to default
8
$\begingroup$

I would expect this digraph to have a lot of automorphisms, but I cannot prove it unconditionally.

First, notice that $2$ is the only prime with no incoming edges. The primes which have incoming edges only from $2$ are the Fermat primes. You can keep going defining new collection of primes with incoming edges from a specific set of primes that were already considered.

Here is a conjecture: For any primes $2=p_1\le p_2 \le \cdots \le p_k$ there are infinitely many primes $q$ so that $q=1+p_1^{a_1}\cdots p_k^{a_k}$. (This seems like a reasonable conjecture generalizing the infinitude of Fermat primes.)

Assuming this conjecture, for any collection of primes previously considered there is an infinite set of primes whose incoming edges come exactly from this set of primes. This implies that in this graph, for example, the Fermat primes can not be distinguished. But there are of course many more automorphisms.

I must say, however, that for all I know, there are only finitely many Fermat primes, or even better, for every set of primes $S$ there are only finitely many primes so that $q-1$ has $S$ as its set of prime factors. If, moreover, the number of such primes is distinct for ever $S$, then the graph turns out to be rigid (no automorphisms). But deciding unconditionally which is the case should be very hard.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ If one views the potential Fermat primes merely as typical numbers of there size, the prime number theorem would lead you to guess only finitely many. $\endgroup$
    – David Feldman
    Commented Jul 23, 2012 at 6:41
  • 3
    $\begingroup$ @David The same heuristic does suggest infinitely many primes of the form $2^m 3^n + 1$, though. These are called Pierpont primes. $\endgroup$
    – Erick Wong
    Commented Jul 23, 2012 at 7:25
  • $\begingroup$ So if I understand, you expect the automorphism group to look like a countably-iterated wreath product, right? $\endgroup$
    – David Feldman
    Commented Jul 23, 2012 at 8:09
  • 1
    $\begingroup$ And you expect two primes in the same orbit if their "Pratt trees" have the same topology, right? $\endgroup$
    – David Feldman
    Commented Jul 23, 2012 at 8:11
  • $\begingroup$ You don't mention the infinitely many outgoing edges. Can you prove it for p,q in N? $\endgroup$
    – joro
    Commented Jul 23, 2012 at 14:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .