Automorphism Group of Paley Graph

Question

Hello all,

I would like an explanation as to the structure description of the automorphism group of a Paley graph.

Paley graphs are a specific case of Cayley graphs where the group is $Z_q$ (q is a prime power for some prime p = 1 mod 4) and the connection set is all the quadratic residues in GF(q).

I'll be satisfied even with the less general case where q is prime.

I'm pretty sure that the said group is a semi-direct product of CyclicGroup(q) and CyclicGroup(q-1/2) but I have trouble showing it in the general case...

Thanks!

P.S

Also posted on: https://math.stackexchange.com/questions/53668/automorphism-group-of-paley-graph

Answer 1

A simple, "out-of-nothing", one-page proof for the case where $q$ is a prime by Peter Muller can be found at http://arxiv.org/PS_cache/math/pdf/0310/0310200v1.pdf. (It suffices to look at Muller's Proposition 1, and indeed, it gives even more than one needs for isomorphisms of the Paley graph.)

Answer 2

It is a natural first guess to think that if $F$ is a finite field and $S$ is a subgroup of the multiplicative group $F^{\times}$ containing $-1$ which generates $F$ additively, then the automorphism group of the Cayley graph (of the additive group $F^{+}$, using $S$ as the generating set) is the semidirect product of the additive group $F^{+}$ and the multiplicative group $S$. But that group needs, in turn, to have its semidirect product taken with the group of automorphisms of $F$ (as an extension of its prime subfield). But even this modified conjecture should have (verification, please?) at least two counterexamples:

(i) $|F| = 2048$ and $|S| = 23$, in which case the automorphism group should be $2^{11}: M_{23}$
(ii) $|F| = 243$ and $|S| = 22$, in which case the automorphism group should be $3^{5}: (M_{11}\times 2)$.

But since these apparent counterexamples involve sporadic groups, this version of the conjecture is probably largely on the right track. (This should not come into play in the Paley graph question, but it should serve as a warning that sometimes the problem of determining the automorphism group for such a family of graphs can exhibit unexpected irregularities.)

Answer 3

It is easy to verify from the definition for each non-zero square $a$ in $GF(q)$ and each $b$ in $GF(q)$, the each map $$ t_{a,b}: x \mapsto ax+b $$ is an automorphism of the Paley graph. Suppose $q=p^d$ where $p$ is prime. Then the Frobenius map $x\mapsto x^p$ is an automorphism of $GF(q)$ with order $d$, and this is also an automorphism of the Paley graph. Combining all this we get a group of automorphisms of order $dq(q-1)$.

Proving that this is the entire automorphism group is difficult. One of the first proofs is in Carlitz, L. "A theorem on permutations in a finite field". Proc. Amer. Math. Soc. 11 (1960) 456–459. Even the case when $q$ itself is prime is non-trivial. The obvious approach is to use the theorem that a transitive group of prime degree which is not 2-transitive is solvable, and then apply a theorem due to Galois that a solvable group of prime degree consists of translations, as above.

Answer 4

This `answer' is a contribution to the question raised in DavidLHarden's answer: There are many more examples where the automorphism group is larger than the expected group, besides the two nice Mathieu cases and the trivial case where $S=F^\times$.

For this let $p$ be an odd prime, $F$ be the field with $p^2$ elements, $\mathbb F_p$ be the subfield of order $p$, and $S$ be the subgroup of $F^\times$ of order $2(p-1)$. So distinct elements $u,v\in F$ are joined if and only if $(u-v)^2\in\mathbb F_p$. Let $\omega\in F$ be of order $2(p-1)$. Identify the element $a+b\omega\in F$ with $(a,b)\in\mathbb F_p\times \mathbb F_p$. Then distinct pairs $(a,b)$, $(c,d)$ are joined if and only if $a=c$ or $b=d$. But any permutation on the first and another permutation on the second component preserves the graph structure, and so does the involution which switches the two components. Thus the automorphism group is at least as big as $(S_p\times S_p)\rtimes C_2$, where $S_p$ is the symmetric group on $p$ letters. (One easily shows that this is the full automorphism group.)

Of course one can generalize this example to get even more examples. One also gets examples where the automorphism group has more interesting composition factors, like $\text{PSL}_2(q)$ for certain prime powers $q$. Thus, I find the question interesting, and I'm not aware of results in the literature.