MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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...



Also posted on:

share|cite|improve this question
Crossposted to math.SE: Shaywei, you should know that it is not polite to post your question in multiple places simultaneously. If someone put a lot of work into giving you a good answer here, only to hear from you that you already got the answer elsewhere, that would be quite frustrating. Please delete one of the two copies of your question, and re-ask it only if you are unsuccessful in getting an answer for some time. – Zev Chonoles Jul 25 '11 at 15:36
OK. Thanks for comment. – Shaywei Jul 25 '11 at 15:43
I don't see how to delete one of the posts. Added relevant P.S instead. I will monitor both threads closely and as soon as I get an answer I will update both posts. – Shaywei Jul 25 '11 at 15:48
That sounds fair, I suppose there is no need to delete then. But for future reference, the "delete" button should be right below the tags of your question, next to an "edit" and "close" button. – Zev Chonoles Jul 25 '11 at 16:04
As far as I can tell, the 'delete' button is not for the author of the thread. In fact, it is DISABLED for the original author. The purpose of the delete button is for other viewers to vote to delete said post. That is, in this case, you are the one who should use the delete button to vote that this post will be deleted. Perhaps I am wrong though. – Shaywei Jul 25 '11 at 16:41

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

share|cite|improve this answer

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.)

share|cite|improve this answer

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.

share|cite|improve this answer
Shouldn't "where $q$ is prime" be "where $p$ is prime"? – DavidLHarden Jul 25 '11 at 17:10
... and shouldn't "$a$ in $GF(q)\setminus\{0\}$" be "$a$ is a quadratic residue in $GF(q)"? – Seva Jul 25 '11 at 17:59
Thanks. I've made both corrections. – Chris Godsil Jul 25 '11 at 21:33

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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