On colour-preserving automorphisms of Cayley graphs

ARS MATHEMATICA CONTEMPORANEA 11 (2016) 189–213

On colour-preserving automorphisms of Cayley graphs

Ademir Hujdurovi´c

^∗,

Klavdija Kutnar

^†

University of Primorska, FAMNIT, Glagoljaˇska 8, 6000 Koper, Slovenia

Dave Witte Morris

,

Joy Morris

^‡

Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, Alberta, T1K 3M4, Canada

Received 25 November 2014, accepted 26 March 2015, published online 20 October 2015

Abstract

We study the automorphisms of a Cayley graph that preserve its natural edge-colouring.

More precisely, we are interested in groupsG, such that every such automorphism of every connected Cayley graph onGhas a very simple form: the composition of a left-translation and a group automorphism. We find classes of groups that have the property, and we determine the orders of all groups that do not have the property. We also have analogous results for automorphisms that permute the colours, rather than preserving them.

Keywords: Cayley graph, automorphism, colour-preserving, colour-permuting.

Math. Subj. Class.: 05C25

1 Introduction

Definitions 1.1. LetSbe a subset of a groupG, such thatS =S⁻¹. (All groups and all graphs in this paper are finite.)

• TheCayley graphofG, with respect toS, is the graphCay(G;S)whose vertices are the elements ofG, and with an edgex xs, for eachx∈Gands∈S.

∗Partially supported by the Slovenian Research Agency: research program P1-0285.

†Partially supported by the Slovenian Research Agency: research program P1-0285 and research projects N1-0011, J1-6743, and J1-6720.

‡Partially supported by a research grant from the Natural Sciences and Engineering Research Council of Canada.

E-mail addresses:ademir.hujdurovic@upr.si (Ademir Hujdurovi´c), klavdija.kutnar@upr.si (Klavdija Kutnar), dave.morris@uleth.ca (Dave Witte Morris), joy.morris@uleth.ca (Joy Morris)

cbThis work is licensed under http://creativecommons.org/licenses/by/3.0/

• Cay(G;S)has a natural edge-colouring. Namely, each edge of the formx xsis coloured with the set{s, s⁻¹}. (In order to make the colouring well-defined, it is necessary to includes⁻¹, becausex xsis the same as the edgexs x, which is of the formy ys⁻¹, withy =xs.)

Note thatCay(G;S)is connected if and only ifS generatesG. Also note that a permu- tationϕofGis a colour-preserving automorphism ofCay(G;S)if and only if we have ϕ(xs)∈

ϕ(x)s^±1 , for eachx∈Gands∈S.

For anyg ∈ G, the left translationx 7→ gxis a colour-preserving automorphism of Cay(G;S). In addition, ifαis an automorphism of the groupG, such thatα(s)∈ {s^±1} for alls∈S, thenαis also a colour-preserving automorphism ofCay(G;S). We will see that, in many cases, every colour-preserving automorphism ofCay(G;S)is obtained by composing examples of these two obvious types.

Definition 1.2. LetGbe a group.

1. A functionϕ:G→Gis said to beaffineif it is the composition of an automorphism ofGwith left translation by an element ofG. This meansϕ(x) =α(gx), for some α∈AutGandg∈G.

2. A Cayley graphCay(G;S)isCCAif all of its colour-preserving automorphisms are affine functions onG. (CCA is an abbreviation for theCayley Colour Automorphism property.)

3. We say thatGisCCAif every connected Cayley graph onGis CCA.

Here are some of our main results:

Theorem 1.3.

1. There is a non-CCA group of ordernif and only ifn≥8andnis divisible by either 4,21, or a number of the formp^q·q, wherepandqare prime(see Corollary6.13 and Remark6.14).

2. An abelian group is not CCA if and only if it has a direct factor that is isomorphic to eitherZ4×Z2or a group of the formZ2^k×Z2×Z2, withk≥2(see Proposition4.1).

3. Every dihedral group is CCA(see Corollary5.4).

4. No generalized dicyclic group or semidihedral group is CCA, except thatZ4 is di- cyclic, but is CCA(see Corollary2.8).

5. Every non-CCA group of odd order has a section that is isomorphic to either the nonabelian group of order21or a certain generalization of a wreath product(called a semi-wreathed product) (see Theorem6.8).

6. IfG×H is CCA, thenG andH are both CCA (see Proposition 3.1). The con- verse is not always true (for example, Z4 ×Z2 is not CCA), but it does hold if gcd |G|,|H|

= 1(see Proposition3.2).

We also consider automorphisms ofCay(G;S)that permute the colours, rather than preserving them:

Definitions 1.4.

• An automorphismαof a Cayley graphCay(G;S)iscolour-permutingif it respects the colour classes; that is, if two edges have the same colour, then their images underαmust also have the same colour. This means there is a permutationπofS, such thatα(gs)∈ {α(g)π(s)^±1}for allg∈Gands∈S(andπ(s⁻¹) =π(s)⁻¹).

• We say that a groupGisstrongly CCAif every colour-permuting automorphism of every connected Cayley graph onGis affine.

Note that any strongly CCA group is CCA, since colour-preserving automorphisms are colour-permuting (withπ being the identity map on S). The converse is not true. For example, any dihedral group is CCA (as was mentioned above), but it is not strongly CCA if its order is of the form8k+ 4(see Proposition5.6). However, the converse does hold for at least two natural families of groups:

Theorem 1.5. A CCA group is strongly CCA if either:

1. it is abelian(see Proposition4.1), or 2. it has odd order(see Proposition6.4).

Remarks 1.6.

1. It follows from Theorems1.3(2) and1.5(1) that every cyclic group is strongly CCA.

This is also a consequence of the main theorem of [9].

2. Groups that are not strongly CCA seem to be far more likely to be of even order than of odd order. For example, of the28groups of order less than32that are not strongly CCA, only one has odd order (see Section7). In fact, there are only three groups of odd order less than 100 that are not strongly CCA: the non-abelian group G21of order21, the groupG21×Z3 of order63, and the wreath productZ3oZ3, which has order81(see Corollary6.15).

3. If the subgroup consisting of all left-translations is normal in the automorphism group of the Cayley graphCay(G;S), thenCay(G;S)is said to benormal[12]. It is not difficult to see that every normal Cayley graph is strongly CCA (cf. Remark6.2), and that every automorphism of a normal Cayley graph is colour-permuting.

4. The notion of (strongly) CCA generalizes in a natural way to the setting of Cay- ley digraphs−−→Cay(G;S), by putting the colourson each directed edge of the form x→ xs. (There is no need to includes⁻¹in the colour.) However, it is very easy to see that if−−→Cay(G;S)is connected, then every colour-preserving automorphism of−−→Cay(G;S)is left-translation by some element ofG[11, Thm. 4-8, p. 25], and that every colour-permuting automorphism is affine [3, Lem. 2.1]. Therefore, both notions are completely trivial in the directed setting. However, there has been some interest in determining when every automorphism of−−→Cay(G;S)is colour-permuting [1,2] (in which case, the Cayley digraph is normal, in the sense of (3)).

2 Examples of non-CCA groups

Remark 2.1. Since automorphisms are the only affine functions that fix the identity ele- mente(and left-translations are colour-preserving automorphisms of any Cayley graph), it is easy to see that ifCay(G;S)is CCA, then every colour-preserving automorphism that fixes the identity is an automorphism of the groupG. More precisely:

A Cayley graphCay(G;S)is CCA if and only if, for every colour-preserving auto- morphismϕofCay(G;S), such thatϕ(e) =e, we haveϕ∈AutG.

The same is true with “strongly CCA” in the place of “CCA,” if “colour-preserving” is re- placed with “colour-permuting.” This is reminiscent of the CI (Cayley Isomorphism) prop- erty [7], and this similarity motivated our choice of terminology.

We thank Gabriel Verret for pointing out that the quaternion groupQ8is not CCA. In fact, two different groups of order8are not CCA:

Example 2.2(G. Verret). Z4×Z2andQ8are not CCA.

Proof. (Q8) LetΓ = Cay(Q8;{±i,±j}). This is the complete bipartite graphK4,4. (See Figure1with the labels that are inside the vertices.) Letϕbe the graph automorphism that interchanges the verticeskand−kwhile fixing every other vertex. This is clearly not an automorphism ofGsinceiandjare fixed byϕand generateG, butϕ6= 1. It is, however, a colour-preserving automorphism ofΓ.

(Z4 ×Z2) Let Γ = Cay Z4×Z2;{±(1,0),±(1,1)}

. This is again the complete bipartite graphK4,4. (See Figure1 with the labels that are outside the vertices.) Letϕ be the graph automorphism that interchanges the vertices(0,1)and(2,1)while fixing all of the other vertices. This is clearly not an automorphism ofGsince(1,0)and(1,1)are fixed byϕand generateG, butϕ6= 1. It is, however, a colour-preserving automorphism ofΓ.

1

−1

j

−j

−i i

−k k (0,0)

(2,0)

(1,1)

(3,1)

(3,0)

(1,0) (0,1)

(2,1)

Figure 1: Interchanging the two black vertices while fixing all of the white vertices is a colour-preserving graph automorphism that fixes the identity vertex but is not a group automorphism.

Both of the groups in Example2.2are generalized dicyclic (cf. Definition2.6):

• Q8is the generalized dicyclic group overZ4, and

• Z4×Z2is the generalized dicyclic group overZ2×Z2.

More generally, we will see in Corollary2.8(4) below that no generalized dicyclic group is CCA (unless the cyclic groupZ4is considered to be dicyclic).

We will see in Theorem6.8that the following example is the smallest group of odd order that is not CCA.

Example 2.3. The nonabelian group of order21is not CCA.

Proof. LetG=ha, x|a³ =e, a⁻¹xa =x²i. (Sincex=e⁻¹xe =a⁻³xa³=x⁸, the relations implyx⁷=e, soGhas order21.) By lettingb=ax, we see thatGalso has the presentation

G=ha, b|a³=e, (ab⁻¹)²=b⁻¹ai.

As illustrated in Figure2, every element ofGcan be written uniquely in the form aⁱb^ja^k, where i, j, k∈ {0,±1} and j= 0⇒k= 0.

Define

ϕ(aⁱb^ja^k) =







b^ja^−k ifi= 0, ab^−ja^k ifi= 1, a⁻¹b^−ja^−k ifi=−1.

Thenϕis a colour-preserving automorphism ofCay G;{a^±1, b^±1}

(see Figure2). How- ever,ϕis not affine, since it fixese, but is not an automorphism ofG(becauseϕ(ab) = ab⁻¹6=ab=ϕ(a)ϕ(b)).

e

b ba

ba⁻¹ b⁻¹

b⁻¹a b⁻¹a⁻¹

ab a aba aba⁻¹

ab⁻¹ ab⁻¹a ab⁻¹a⁻¹

a⁻¹ a⁻¹b

a⁻¹ba a⁻¹ba⁻¹

a⁻¹b⁻¹

a⁻¹b⁻¹a

a⁻¹b⁻¹a⁻¹ 1 1 2

2 3

3

4 4

5

5

6 6 7

7 8

8

Figure 2: The colour-preserving automorphismϕfixes every black vertex, but interchanges the two vertices labeled

^{i , for1}≤i≤8. Since the neighbours of both copies of

^{i have}

the same labels (for example, the vertices labeled

⁷ are connected by a black edge to

¹

and

⁵ , and by a white edge to

^{6 and}

⁸ ), we see thatϕis indeed a colour-preserving automorphism of the graph (if the orientations of the edges are ignored).

See Proposition3.3for a generalization of the following example.

Example 2.4. The wreath productZmoZnis not CCA wheneverm≥3andn≥2.

Proof. This group is a semidirect product

(Zm×Zm× · · · ×Zm)o Zn. For the generatorsa= (1,0,0, . . . ,0),0

andb= (0,0, . . . ,0),1

, the map (x1, x2, x3, . . . , xn), y

7→ (−x1, x2, x3, . . . , xn), y

(negate a single factor of the abelian normal subgroup) is a colour-preserving automor- phism ofCay ZmoZn;{a^±1, b^±1}

that fixes the identity element but is not a group auto- morphism.

The following construction provides many additional examples of non-CCA groups by generalizing the idea of Example2.2.

Proposition 2.5. Suppose there is a generating set S of G, an element τ of G, and a subsetT ofS, such that:

• τis an element of order2,

• each element ofSis either centralized or inverted byτ,

• t²=τfor allt∈T,

• the subgrouph(SrT)∪ {τ}iis not all ofG, and

• either

G:h(SrT)∪ {τ}i

>2orτis not in the centre ofG.

ThenGis not CCA.

Proof. For convenience, letH =h(SrT)∪ {τ}i. SincehSi=G, but, by assumption, H 6=G, there exists somex∈TrH. Define

ϕ(g) =

(gτ ifg∈xH, g otherwise.

It is obvious thatϕfixese, sincee /∈xH.

We claim thatϕis is not an automorphism ofG. If|G:H|>2, this follows from the fact that a nonidentity automorphism cannot fix more than half of the elements ofG. Thus, we may assume|G:H|= 2. Then, by assumption, there is some elementhofGthat does not commute withτ. Sinceτcommutes with every element ofT(becauseτ =t²), we see that we may assumeh∈ H. Ifϕis an automorphism, then, since it is the identity on the normal subgroupH ofG, butx⁻¹=xx⁻²=xτ ∈xH, we have:

x⁻¹hx=ϕ(x⁻¹hx) =ϕ(x⁻¹)·ϕ(h)·ϕ(x) =x⁻¹τ·h·xτ 6=x⁻¹hxτ²=x⁻¹hx.

This is a contradiction.

Since each element of S is either centralized or inverted byτ, we know that right- multiplication byτis a colour-preserving automorphism ofCay(G;S). Restricting toxH,

this tells us thatϕpreserves colours (and existence) of all edges ofCay(G;S)that have both endvertices inxH.

Now consider an edge fromgtoh, whereg∈xHandh6∈xH. There is some element t∈T such thatgt=h, and there is an edge of the same colour fromϕ(g) =gτ togτ t⁻¹. Sincet²=τandτ²=e, we havet⁻¹=τ t. Hence, the edge is fromϕ(g)to

gτ t⁻¹=gt²t⁻¹=gt=h=ϕ(h).

Thusϕpreserves the existence and colour of every edge from a vertex inxHto a vertex outside ofxH. Since the only vertices moved by ϕare in xH, this shows that ϕis a colour-preserving automorphism ofCay(G;S).

Here are a few particular examples to which Proposition2.5can be applied.

Definition 2.6. LetAbe an abelian group of even order. Choose an involutionyofA. The correspondinggeneralized dicyclic groupis

Dic(y, A) =hx, A|x²=y, x⁻¹ax=a⁻¹, ∀a∈Ai.

Definition 2.7. Forn≥1, let

SemiD16n =ha, x|a⁸ⁿ =x²=e, xa=a⁴ⁿ⁻¹xi.

This is asemidihedral(orquasidihedral) group. The term is usually used only whennis a power of2, but the construction is valid more generally.

Corollary 2.8. The following groups are not CCA:

1. Z4×Z2,

2. Z2^k×Z2×Z2, for anyk≥2, 3. Q8,

4. every generalized dicyclic group exceptZ4(this generalizes(3)), and 5. every semidihedral group.

Proof. (1) Apply Proposition2.5withτ= (2,0)andS=T ={(1,0),(1,1)}.

(2) Apply Proposition2.5withτ= (2^k−1,0,0),T ={(2^k−2,1,0),(2^k−2,0,1)}, and S={(1,0,0)} ∪T.

(3) Sincei² =j² =−1, we may apply Proposition2.5withτ =−1andS = T = {i, j}.

(4) ForG= Dic(y, A) =hx, y, Ai, apply Proposition2.5withτ =yandS =T = xA. (We have

G:h(SrT)∪ {τ}i

=|G:hτi|=|G|/2>2, sinceG6∼=Z4.)

(5) ForG= SemiD16n =ha, xi, apply Proposition2.5withτ=a⁴ⁿ,T ={(ax)^±1}, andS={x} ∪T. (Note that

G:h(SrT)∪ {τ}i

=|G:hx, τi|=|G|/4≥4.)

3 Direct products and semidirect products

Proposition 3.1. IfG1is not strongly CCA, and G2is any group, then G1×G2 is not strongly CCA. Furthermore, the same is true with “CCA” in the place of “strongly CCA.”

Proof. SinceG1is not strongly CCA, some connected Cayley graphCay(G1;S1)onG1

has a colour-permuting automorphismϕ1that is not affine. Letπbe a permutation ofS1, such thatϕ1(g1s)∈ {ϕ1(g1)π(s)^±1}for allg1 ∈G1. (IfG1is not CCA, then we may assumeπis the identity permutation.) Now, fix any connected Cayley graphCay(G2;S2) onG2, and let

S= S1× {e}

∪ {e} ×S2 ,

soCay(G1×G2;S)is connected. (It is isomorphic to the Cartesian productCay(G1;S1) Cay(G2;S2).)

Define a permutationϕofG1×G2byϕ(g1, g2) = ϕ(g1), g2

. For all(g1, g2) ∈ G1×G2andsi∈Si, we have

• ϕ (g1, g2)·(s1, e)

= ϕ1(g1s1), g2

∈

ϕ g1, g2

· π(s1), e±1

, and

• ϕ (g1, g2)·(e, s2)

= ϕ1(g1), g2s2

=ϕ(g1, g2)·(e, s2).

Therefore,ϕis a colour-permuting automorphism ofCay(G1×G2;S)(and it is colour- preserving ifπis the identity permutation ofS1).

However, ϕis not affine (since its restriction toG1 is the permutationϕ1, which is not affine). So Gis not strongly CCA (and is not CCA ifπis the identity permutation ofS1).

Proposition3.1tells us that ifG1×G2is CCA, thenG1 andG2must both be CCA.

The converse is not true. (For example,Z4andZ2are both CCA, but Example2.2tells us that the direct productZ4×Z²is not CCA.) However, the converse is indeed true when the groups are of relatively prime order:

Proposition 3.2. Assumegcd |G1|,|G2|

= 1. ThenG1×G2is CCA(or strongly CCA) if and only ifG1andG2are both CCA(or strongly CCA, respectively).

Proof. (⇒) Proposition3.1.

(⇐) Let

• G=G1×G2,

• Sbe a generating set ofG,

• ϕbe a colour-permuting automorphism ofCay(G;S)that fixes the identity element (see Remark2.1),

• πi:G1×G2→Gibe the natural projection, and

• kbe a multiple of|G2|that is≡1 (mod|G1|), sog^k=π1(g)for allg∈G.

Consider somes∈S, and lett=ϕ(s), soϕ(xsⁱ) =ϕ(x)t^±ifor allx∈Gandi∈Z. Then, for allg∈G, we have

ϕ g π1(s)

=ϕ(gs^k) =ϕ(g)t^±k=ϕ(g)·π1(t)^±1. (∗) Sinceπ1(S)generatesG1, this implies there is a well-defined permutationϕ2ofG2, such that

ϕ(G1× {g2}) =G1× {ϕ2(g2)}.

By repeating the argument with the roles ofG1andG2 interchanged, we conclude that there is a permutationϕ1ofG1, such that

ϕ(g1, g2) = ϕ1(g1), ϕ2(g2) .

Now, (∗) implies that ϕ1 is a colour-permuting automorphism of Cay G1;π1(S) . Similarly, ϕ2 is a colour-permuting automorphism of Cay G2;π2(S)

. Since each Gi

is CCA, we conclude thatϕi is an automorphism of Gi. Soϕ is an automorphism of G1×G2.

The idea used in Example2.4yields the following result that generalizes the CCA part of Proposition3.1.

Proposition 3.3. SupposeG = H oK is a semidirect product, andCay(H;S0) is a connected Cayley graph ofH, such that:

• S0is invariant under conjugation by every element ofK, and

• there is a colour-preserving automorphismϕ0ofCay(H;S0), such that either

◦ ϕ0is not affine, or

◦ ϕ0(e) = e, and there exist s ∈ S0 and k ∈ K, such thatϕ0(k⁻¹sk) 6= k⁻¹ϕ0(s)k.

ThenGis not CCA.

Proof. Defineϕ: G→ Gbyϕ(hk) = ϕ0(h)k. We claim thatϕis a colour-preserving automorphism ofCay(G;S0∪K)that is not affine (soGis not CCA, as desired).

Fork1∈K, we have

ϕ(hk k1) =ϕ0(h)kk1=ϕ(hk)k1,

soϕpreserves the colour ofK-edges. Now consider somes∈S0and let^ks=ksk⁻¹ ∈ S0. Then, sinceϕ0is colour preserving, we have

ϕ(hk s) =ϕ(h^ks k) =ϕ0(h^ks)k= ϕ0(h) (^ks)^±1

k=ϕ0(h)ks^±1=ϕ(hk)s^±1, soϕalso preserves the colour ofS0-edges. Hence,ϕis colour-preserving.

Now, suppose ϕis affine. Then the restriction ϕ0 of ϕto H is also affine, so, by assumption, we must haveϕ(e) =e, soϕis an automorphism ofG. Hence, for alls∈S0

andk∈K, we have

ϕ0(k⁻¹sk) =ϕ(k⁻¹sk) =ϕ(k)⁻¹ϕ(s)ϕ(k) =k⁻¹ϕ(s)k=k⁻¹ϕ0(s)k.

This contradicts the hypotheses of the proposition.

Remark 3.4. Proposition3.3can be generalized slightly: assumeG =HK andH / G (but do not assumeH∩K ={e}, which would makeGa semidirect product). Then the above proof applies if we make the additional assumption thatϕ0(hk) = ϕ0(h)kfor all h∈H andk∈H∩K.

4 Abelian groups

The following result shows that all non-CCA abelian groups can be constructed from ex- amples that we have already seen in Corollary2.8(and that CCA and strongly CCA are equivalent for abelian groups).

Proposition 4.1. For an abelian groupG, the following are equivalent:

1. Ghas a direct factor that is isomorphic to eitherZ4×Z2 or a group of the form Z2^k×Z2×Z2, withk≥3.

2. Gis not CCA.

3. Gis not strongly CCA.

Proof. (1⇒2) This is immediate from Corollary2.8and Proposition3.1.

(2⇒3) Obvious.

(3 ⇒ 1) Letϕbe a colour-permuting automorphism of any connected Cayley graph Cay(G;S)onG, such thatϕ(0) = 0. From Proposition3.2(and the fact that any abelian group is the direct sum of its Sylow subgroups), we may assumeGis ap-group for some primep. Then

G∼=Zp^k1 ×Zp^k2× · · · ×Zp^km, withk1≥k2≥ · · · ≥km≥1.

SinceSis a generating set, it is easy to see that there is somes1∈S, such that|s1|=p^k1. Also, it is a basic fact about finite abelian groups that every cyclic subgroup of maximal order is a direct summand [4, Lem. 1.3.3, p. 10]. Therefore, by induction oni, we see that there exists1, . . . , sm∈S, such that if we letGi=hs1, . . . , sii, then

Gi∼=Gi−1×Zp^ki and G∼=Gi×Zp^ki+1× · · · ×Zp^km, for eachi.

It is important to note that each element ofGican be written uniquely in the form

g+rsi, withg∈Gi−1and−p^ki/2< r≤p^ki/2(andr∈Z). (†) For convenience, also let

ti=ϕ(si) and Hi=ht1, . . . , tii.

We will show, by induction oni, that ifGdoes not have any direct summands of the form specified in the statement of the proposition, thenHiis a direct factor ofG, and the restriction ofϕtoGiis an isomorphism ontoHi. (Note that this impliesG/Gi ∼=G/Hi, by the uniqueness of the decomposition ofGas a direct sum of cyclic groups.) Taking i=myields the desired conclusion thatϕis an automorphism ofG.

The base casei= 0is trivial. For the induction step, writeG=Gi−1×G, so G∼=G/Gi−1∼=Zp^ki ×Zp^ki+1 × · · · ×Zp^km,

and let :G→Gbe the natural projection. Thenhsii=Gi∼=Zp^kiis a direct summand ofG. Sinceϕis colour-permuting (andHi−1=ϕ(Gi−1)is a subgroup), it is easy to see that the order oftiinG/Hi−1is equal top^ki (the same as the the order ofsiinG/Gi−1), and thatϕ(p^kisi) =p^kiti. This implies that if we define

α:Gi→Hi by α(g+rsi) =ϕ(g) +rti forg∈Gi−1andr∈Z,

thenαis a well-defined isomorphism. So we need only show that the restriction ofϕtoGi

is equal toα(unlessGhas a direct summand of the desired form).

Supposeϕ|^Gi 6= α. (This will lead either to a contradiction or to a summand of the desired form.) Sinceϕis colour-permuting and, by definition,αagrees withϕonGi−1, this implies there is someg∈Gi−1, such thatϕ(g+si)6=α(g+si). However, sinceϕis colour-permuting, we know

ϕ(g+si) =ϕ(g)±ϕ(si) =α(g)±ti. Sinceα(g+si) =α(g) +ti, the preceding two sentences imply

ϕ(g+si) =α(g)−ti∈Hi−1−ti.

Furthermore, sinceϕis colour-permuting (andϕ(sj) =tj), we know that it maps edges of colour{s^±1₁ }, . . . ,{s^±1_i−1}to edges of colour{t^±1₁ }, . . . ,{t^±1_i−1}, so

ϕ(x+h)∈ϕ(x) +Hi−1for allx∈Gandh∈Hi−1. Takingx=siandh=gyields

ϕ(g+si)∈Hi−1+ϕ(si) =Hi−1+ti.

This contradicts the uniqueness ofrin the analogue of (†) forHi, unless1 =p^ki/2. Hence, we must havep^ki= 2(soZ2is a direct summand ofG), which meansp= 2andki= 1.

We have

ϕ(g) + 2ti=α(g+ 2si) (definition ofα)

=ϕ(g+ 2si) (g+ 2si=g+p^kisi ∈Gi−1)

=ϕ(g)−2ti (ϕ(g+si) =α(g)−ti=ϕ(g)−ti), so4ti = 0. Also note that, since

ϕ(g) +ti =α(g+si)6=ϕ(g+si) =ϕ(g)−ti, we must have2ti6= 0. So|ti|= 4.

Sincehs1, . . . , si−1i=Gi−1, there must existg⁰∈Gi−1, andj < i, such that ϕ(g⁰+si) =α(g⁰) +ti, but ϕ(g⁰+sj+si) =α(g⁰+sj)−ti=α(g⁰) +tj−ti. Sinceϕis colour-permuting, we also have

ϕ(g⁰+sj+si) =ϕ(g⁰+si)±tj=α(g⁰) +ti±tj.

Hence,tj−ti = ti±tj, sotj∓tj = 2ti. Since2ti 6= 0, we conclude that2tj = 2ti; hence,|tj|= 4.

Since2^kj =|Hj :Hj−1|is a divisor of|tj|, and|tj|= 4, there are two possibilities for kj:

• Ifkj = 2, thenZ4×Z2∼=Z₂kj ×Z2^ki is a direct summand ofG, as desired.

• Ifkj = 1, then, since|tj| = 4, there must be some` < j, such thatk` ≥2. This implies thatZ2^{k`</sup> ×Z2×Z2 ∼=Z2<sup>k`} ×Z₂kj ×Z2^ki is a direct summand ofG, as desired.

Corollary 4.2. Forn ∈ Z⁺, there is a non-CCA abelian group of ordernif and only if nis divisible by8.

5 Generalized dihedral groups

Definition 5.1. Thegeneralized dihedral groupover an abelian groupAis the group hσ, A|σ²=e, σaσ=a⁻¹∀a∈Ai.

Lemma 5.2. SupposeDis the generalized dihedral group over an abelian groupA, and ϕis a colour-permuting automorphism of a connected Cayley graphCay(D;S), such that ϕ(e) =e. IfAis strongly CCA, andϕ(S∩A) =S∩A, thenϕis an automorphism ofD.

Proof. Label the elements ofSasS={a1, a2, . . . , ak, σ1, σ2, . . . , σt}, whereai∈Afor 1≤i≤k, andσi6∈Afor1≤i≤t(so eachσiis an involution that inverts the elements ofA). By assumption,{a1, a2, . . . , ak}and{σ1, σ2, . . . , σt}are invariant underϕ. Thus, for eachi, we have

• ϕ(ai) =a⁰_ifor somea⁰_i∈ {a1, a2, . . . , ak}, and

• ϕ(σi) =σ⁰_ifor someσ_i⁰ ∈ {σ1, σ2, . . . , σt}.

Notice that since σ1, . . . , σt are involutions, eachσi is its own inverse. Therefore, whenever σ is a word in σ1, . . . , σt andg ∈ D, the fact thatϕ is a colour-permuting automorphism means thatϕ(gσ) =ϕ(g)σ⁰, whereσ⁰ is formed fromσby replacing each instance ofσiinσbyσ_i⁰. Therefore, if we letΣbe the subgroup generated by{σ1, . . . , σt}, thenϕis a colour-preserving automorphism of the Cayley graphCay(D;S∪Σ). Hence, there is no harm in assuming thatS=S∪Σ, soΣ⊆S.

SincehS∩Aiis normal inD(in fact, every subgroup ofAis normal, because every element ofD either centralizes or inverts it), we haveD = hS ∩AiΣ. ThereforeA = hS∩Ai(Σ∩A) =hS∩Ai, soCay(A;S∩A)is connected. Sinceϕis colour-preserving, and ϕ(S∩A) =S∩A, this implies thatϕ(A) =A. Soϕis a colour-permuting automorphism of the connected Cayley graphCay(A;S∩A). Since, by assumption,Ais strongly CCA, this implies thatϕ|^Ais an automorphism ofA. Soϕ(ab) =ϕ(a)ϕ(b)for alla, b∈ A and∈Z.

Now we are ready to show thatϕis an automorphism ofD. Letg, h∈ D. Then we may writeg =aσandh=beσ, wherea, b∈ Aandσ,eσ∈ {e, σ1}. For convenience, let ∈ {±1}, such thatσcσ=cfor allc∈A. Note that, sinceσ⁰₁∈ {σ1, . . . , σt}, we know thatσ1andσ₁⁰ both invertA, so we also haveσ⁰cσ⁰ =c. Then

ϕ(gh) =ϕ(aσ·beσ) =ϕ(ab·σσ) =e ϕ(a)ϕ(b)·σ⁰eσ⁰=ϕ(a)σ⁰·ϕ(b)eσ⁰=ϕ(g)·ϕ(h).

Sinceg, h∈Dare arbitrary, this proves thatϕis an automorphism ofD.

Proposition 5.3. The generalized dihedral groupDover an abelian groupAis CCA if and only ifAis CCA.

Proof. (⇐) Note that ifϕis any colour-preserving automorphism of a connected Cayley graphCay(D;S), thenϕ(S∩A) =S∩A, sinceAis closed under inverses. Furthermore, Ais strongly CCA, since it is assumed to be CCA and every CCA abelian group is strongly CCA (see Proposition4.1). Therefore, Lemma5.2implies thatϕis a group automorphism.

SoDis CCA.

(⇒) WriteD =Aohσi. SinceAis not CCA, there is a colour-preserving automor- phismϕ0 of some connected Cayley graphCay(A;S), such thatϕ0 is not affine. Since

σinverts every element ofS, it is easy to see thatCay D;S∪ {σ}

is isomorphic to the Cartesian productCay(A;S)P2. So the proof of Proposition 3.1provides a colour- preserving automorphismϕofCay D;S∪ {σ}

whose restriction toAisϕ0, which is not an affine map. Therefore,ϕis not affine.

The following result is the special case whereAis cyclic (since Proposition4.1implies that every cyclic group is CCA).

Corollary 5.4. Every dihedral group is CCA.

Lemma 5.5. IfT is a generating set of a groupH, andσis a nontrivial automorphism ofH, such thatσ(t)∈ {t^±1}for everyt∈T, then the groupG= (Hohσi)×Z2is not strongly CCA.

Proof. LetG⁰ = H ×Z2×Z2 and define ϕ: G → G⁰ byϕ(h, σ^x, y) = (h, x, y)for h ∈ H andx, y ∈ Z2. Sinceσ(t) ∈ {t^±1} for everyt, it is easy to verify that ϕis a colour-respecting isomorphism

from Cay G; (H, e,0)∪ {(e, σ,0),(e,0,1)} to Cay G; (H,0,0)∪ {(e,1,0),(e,0,1)} .

Permuting the twoZ2 factors of G⁰ provides an automorphism of G⁰ that preserves the generating set, and therefore corresponds to a colour-permuting automorphism of the two Cayley graphs. However, it is not an automorphism ofG, since it takes the central element (e, e,1)to(e, σ,0), which is not central (since the automorphismσis nontrivial).

Proposition 5.6. The generalized dihedral group over an abelian groupAis strongly CCA if and only if eitherAdoes not haveZ2as a direct factor, orAis an elementary abelian 2-group(in which case, the generalized dihedral group is also an elementary abelian2- group).

Proof. (⇒) SupposeA=A⁰×Z2, andA⁰is not elementary abelian. Then the generalized dihedral groupAohσioverAis isomorphic to(A⁰ohσi)×Z2, so Lemma5.5tells us that it is not strongly CCA.

(⇐) LetD=Aohσibe the generalized dihedral group overA, and letϕbe a colour- permuting automorphism of a connected Cayley graphCay(D;S), such thatϕ(e) =e. We may assumeAdoes not haveZ2as a direct factor (otherwise, the desired conclusion follows from the fact that every elementary abelian2-group is strongly CCA (see Proposition4.1)).

From Proposition4.1, we see thatAis strongly CCA. Hence, the desired conclusion will follow from Lemma5.2if we show thatϕ(S∩A) =S∩A.

Leta∈S∩A. Sinceϕis colour-permuting, we have|ϕ(s)|=|s|for alls∈S. Also, we know that|g| = 2for allg ∈ DrA. Therefore, it is obvious thatϕ(a) ∈ S∩Aif

|a| 6= 2.

So we may assume|a|= 2. SinceAdoes not haveZ2as a direct factor, this implies thatais a square inA: that is, we havea=x², for somex∈A. Also, sinceCay(D;S)is connected, we may writex=s1s2· · ·snfor somes1, . . . , sn ∈S. Soa= (s1s2· · ·sn)² can be written as a word in which every element ofS occurs an even number of times.

Sinceϕis colour-permuting, this implies thatϕ(a)can be written as a word in which, for eachs∈S, the total number of occurrences of eithersors⁻¹is even. Sincesands⁻¹both either centralizeAor invert it, this implies thatϕ(a)centralizesA. Since every element of DrAinvertsA, we conclude thatϕ(a)∈A, as desired.

6 Groups of odd order

The following notation will be assumed throughout this section.

Notation 6.1. For a fixed Cayley graphCay(G;S):

• A⁰is the group of all colour-preserving automorphisms ofCay(G;S).

• Gb is the subgroup of A⁰ consisting of all left translations by elements ofG. (Al- though we do not need this terminology, it is often called theleft regular representa- tionofG.)

• He is the stabilizer of the identity element ein Cay(G;S), for any subgroupH ofA⁰.

Remark 6.2. It is well known (and very easy to prove) that a permutation ofGis affine if and only if it normalizesGb(see, for example [10, Lem. 2]).

Lemma 6.3. A⁰eis a2-group.

Proof. Letϕ∈A⁰e, soϕis a colour-preserving automorphism ofCay(G;S)that fixese.

IfCis any monochromatic cycle throughe, then eitherϕis the identity onCorϕreverses the orientation ofC. Therefore,ϕ²acts trivially on the union of all monochromatic cycles that containe. This implies thatϕ²acts trivially on all vertices at distance≤1frome.

Repeating the argument shows thatϕ^2kacts trivially on all vertices at distance≤k−1 frome. Forklarger than the diameter ofCay(G;S), this implies thatϕ^2kis trivial. So the order ofϕis a power of2.

Proposition 6.4. Let Cay(G;S)be a connected Cayley graph on a groupGof odd or- der. If every colour-preserving automorphism of Cay(G;S)is affine, then every colour- permuting automorphism is affine.

Proof. LetA^• be the group of all colour-permuting automorphisms ofCay(G;S). Since A^• acts on the set of colours, and A⁰ is the kernel of this action (and the kernel of a homomorphism is always normal), it is obvious thatA⁰/ A^•. Also, since Gis CCA, we haveG /b A⁰ (cf. Remark 6.2). Furthermore, |G| is odd,|A⁰e|is a power of 2, and A⁰=Gb·A⁰e. Therefore,Gbis the (unique) largest normal subgroup of odd order inA⁰. The uniqueness implies thatGbischaracteristicinA⁰. (That is, it is fixed by all automorphisms ofA⁰.) SoGbis a characteristic subgroup of the normal subgroupA⁰ofA^•. Although a normal subgroup of a normal subgroup need not be normal, it is well known (and easy to prove) that any characteristic subgroup of a normal subgroup is normal [4, Thm. 2.1.2(ii), p. 16]. ThereforeG /b A^•. This implies thatGis strongly CCA (see Remark6.2).

Wreath productsZmoZⁿprovide examples of non-CCA groups of odd order (see Exam- ple2.4). We will see in Theorem6.8that the following slightly more general construction is essential for understanding many of the other non-CCA groups of odd order.

Example 6.5. Letαbe an automorphism of a groupA, and letn ∈ Z⁺. Then we can define an automorphismαeofAⁿby

α(we 1, . . . , wn) = α(wn), w1, w2, . . . , wn−1 .

It is easy to see that the order ofαeisntimes the order ofα, so we may form the corre- sponding semidirect productAⁿo Zn|α|. Let us call this thesemi-wreathed product of AbyZn, with respect to the automorphismα, and denote itAo^αZn. (Ifαis the trivial automorphism, then this is the usual wreath productAoZn.)

Negating the first coordinate, as in Example2.4, shows that ifn >1andAis abelian, but not an elementary abelian2-group, thenAo^αZnis not CCA.

Remark 6.6. Because it may be of interest to find minimal examples, we point out that any semi-wreathed product of odd order satisfying the conditions in the final paragraph of Example6.5must contain a subgroup that is isomorphic to a semi-wreathed product Ao^αZq, where Ais an elementary abelianp-group,pandqare primes (not necessarily distinct),αis an automorphism ofq-power order, and no nontrivial, proper subgroup ofA is invariant underα.

Definition 6.7([4, p. 5]). LetGbe a group. For any subgroupsH andKofG, such that K / H, the quotientH/Kis said to be asectionofG.

Theorem 6.8. Any non-CCA group of odd order has a section that is isomorphic to either:

1. a semi-wreathed productAo^αZn (see Example6.5), whereAis a nontrivial, ele- mentary abelian group(of odd order)andn >1, or

2. the(unique)nonabelian group of order21.

Proof. AssumeCay(G;S)is a connected Cayley graph on a group Gof odd order that does not have a section as described in either (1) or (2). We will show, by induction on the order, that ifAis any subgroup ofA⁰that containsG, thenb Gbis a normal subgroup ofA. (Then takingA=A⁰implies thatGis CCA (see Remark6.2).)

It is important to note that this conclusion impliesGbis acharacteristicsubgroup ofA (because Lemma6.3implies thatGb is the unique largest normal subgroup of odd order).

For convenience, we writeGbJAwhenGbis characteristic.

LetNbe a minimal normal subgroup ofA. Then Nis either elementary abelian or the direct product of (isomorphic) nonabelian simple groups [4, Thm. 2.1.5, p. 17], and we consider the two possibilities as separate cases.

Case 1.AssumeNis elementary abelian. Since the Sylow2-subgroupAe, being the sta- bilizer of a vertex, does not contain any normal subgroups ofA, we know thatNis not contained in a Sylow2-subgroup. Hence, Nis not a 2-group, so it must be a p-group for some odd primep. Therefore, sinceGb is a maximal subgroup of odd order, we have N⊆G, sob

N=N, for some (elementary abelian) normal subgroupb NofG.

LetN⁺ be the largest normal subgroup ofAthat is contained inNAe. SinceNAeis the stabilizer of a point under the action ofAon the spaceG/N ofN-orbits, we know that N⁺ is the kernel of the action ofAonG/N, soA/N⁺ is a group of colour-preserving automorphisms of Cay(G/N;S), where S is the image ofS in G/N.. Therefore, by induction on|A|, we know thatGNb ⁺/N⁺ is normal inA/N⁺, soGNb ⁺is normal inA. Then we may assumeGbN⁺ = A, for otherwise, by induction on|A|, we would know GbJGNb ⁺, soG /b A, as desired. Since|G|is odd, this implies thatN⁺contains a Sylow 2-subgroup ofA. In fact, sinceN⁺is normal and all Sylow2-subgroups are conjugate, this

implies thatN⁺contains every Sylow2-subgroup. In particular, it containsAe. Therefore N⁺=NAe, so

NAe/A.

This means thatAeacts trivially onG/N, so, for every s ∈ S rN,Aepreserves the orientation of everys-edge. (This uses the fact that, since|s|is odd,s6≡s⁻¹ (mod N)if s /∈N.) This implies:

forϕ∈Ae,g∈G, andx∈ hSrNi, we haveϕ(gx) =ϕ(g)x. (6.9) Let (S ∩N)^hSrNi = {gsg⁻¹ | s ∈ S ∩N, g ∈ hS rNi }. Now, suppose t ∈ (S∩N)^hSrNiandh∈N. There existss∈S∩Nandx∈ hSrNi, such thatxsx⁻¹=t.

From (6.9) and the fact thatϕis colour-preserving, we see that

ϕ(h t) =ϕ(h xsx⁻¹) =ϕ(h)x s^±1x⁻¹=ϕ(h)t^±1. Hence,ϕ|^N is a colour-preserving automorphism of

Cay

N; (S∩N)^hSrNi∪ hSrNi ∩N . SinceSgeneratesG, it is easy to see that this Cayley graph is connected.

Note thatC_Ae(N)is normalized by bothNandAe, so it is a normal subgroup ofNAe. Therefore, it must be trivial (since the largest normal2-subgroup ofNAeis characteristic, and is therefore normal inA, but the stabilizerAedoes not contain any nontrivial normal subgroups ofA). So

Aeacts faithfully by conjugation onN. (6.10) Also, we know thatϕ|^N is an automorphism ofN (by Remark6.2, sinceϕnormal- izes N = N). Since, being a colour-preserving automorphism,b ϕeither centralizes or inverts every element of the generating set ofN, this implies thatϕ²|^N is trivial. Since this is true for everyϕ∈ Ae, we conclude thatAeacts onN via an elementary abelian 2-group. From (6.10), we conclude thatAeis elementary abelian.

We can think ofNas a vector space overZp, and, for each homomorphismγ: A→ {±1}, let

Nγ ={n∈N|ana⁻¹=γ(a)nfor alla∈Ae}.

(This is called the “weight space” associated to γ.) Since every linear transformation satisfying T² = I is diagonalizable, and Ae is commutative, the elements of Ae can be simultaneously diagonalized. This means that if we let Γ =

γ | Nγ 6= {0} , then, since eigenspaces for different eigenvalues are always linearly independent, we have N = L

γ∈ΓNγ. This direct-sum decomposition is canonically defined from the action ofAeonN. SinceGbacts onNAe(by conjugation), we conclude that the action ofGbonN by conjugation must permute the weight spaces. More precisely, there is an action ofG onΓ, such thatbgNγbg⁻¹=Ngγ for allg∈G. SinceN is abelian, this factors through to a well-defined action ofG/N onΓ.

If theG-action onΓis trivial, then every weight space isG-invariant, which implies that the action ofGbonNcommutes with the action ofAe. SinceAeacts faithfully, we conclude thatGbcentralizesAeN/N; that is,[G,b Ae]⊆N⊆G. Sob AenormalizesG, asb desired.

We may now assume that theG-action is nontrivial, so there is someg ∈ Gwith an orbit of some lengthn >1onΓ. Letγ0be an element of this orbit, sobgⁿnormalizesNγ0. SinceSrNgeneratesG/N, we may assumeg∈SrN, so (6.9) tells us thathbgi ∩Nis centralized byAe. However, the minimality ofNimplies thatC_N(Ae) =N∩Z(NAe)is trivial. Therefore,hN,bgi=Nohbgiis a semidirect product. So

hNγ0,gbi=

M

γ∈hgiγ₀Nγ

ohbgi.

Then modding outC_hbgi(Nγ₀)yields a section ofGbthat is isomorphic toNγ₀o^αZn, where αis the automorphism ofNγ0induced by the conjugation action ofbgⁿ. SoGhas a semi- wreathed section, as described in (1). This completes the proof of this case.

Case 2.AssumeN = L1× · · · ×Lr, where eachLi is a nonabelian simple group, and Li ∼= L1 for alli. We know thatA = GAe e,Aeis a2-group, and|G| is odd, soGb is a2-complement inA. (By definition, this means that|Gb|is odd and|A : Gb|is a power of2 [6, p. 88].) SoL1 is a nonabelian simple group that has a2-complement (namely, Gb∩L1). By using the Classification of Finite Simple Groups, it can be shown that this impliesL1∼= PSL(2, p), for some Mersenne primep≥7(see [8, Thm. 1.3]).

Note thatAe∩Li is a Sylow 2-subgroup ofPSL(2, p). Therefore, it is dihedral [4, Lem. 15.1.1(iii)] and has orderp+ 1(becausepis a Mersenne prime). Let

• Cibe the unique cyclic subgroup of order(p+ 1)/2inAe∩Li,

• C²i be the unique subgroup of index2inCi, and

• C²=C²1× · · ·C²r⊂Ae∩(L1× · · · ×Lr).

Since every element ofCi is a colour-preserving automorphism, it either fixes or inverts each element ofS, so we know thatC²i fixes every element ofS. Since stabilizers are conjugate, this impliesbs⁻¹C²bs⊆Ae, for everys∈S. We must havep >7, for otherwise Gb∩Li, being the2-complement ofPSL(2,7), would be the nonabelian group of order21, as in (2). This implies thatC²i is the unique cyclic subgroup of order (p+ 1)/4 in the dihedral groupAe∩Li, so we must havebs⁻¹C²bs=C², which means thatbsnormalizesC². Since this holds for everysin the generating setS, we conclude thatGbnormalizesC².

Note thatAenormalizesAe∩N, and thatC²JAe∩N(since, as was mentioned above, Ciis the unique cyclic subgroup of its order inAe∩Li). Therefore,C²/Ae. We conclude thatC²is normal inGAb e =A. SoC²1=C²∩L1is normal inL1, contradicting the fact thatL1is simple.

Lemma 6.11. To prove a groupGis strongly CCA(or CCA), it suffices to consider only the connected Cayley graphsCay(G;S), such that every element ofS has prime-power order.

Proof. Supposeϕis a colour-permuting automorphism of some connected Cayley graph Cay(G;S). There is a permutationπofS, such thatϕ(gs) =ϕ(g)π(s)^±1, for allg∈G ands∈S. (Furthermore, ifϕis colour-preserving, thenπcan be taken to be the identity permutation.) By induction onk, this implies ϕ(gs^k) = ϕ(g)π(s)^±k, for all k ∈ Z. Hence, if we letS^∗ ={s^k |s∈S, k∈Z}, thenϕis a colour-permuting automorphism ofCay(G;S^∗). Now, let

S0={t∈S^∗| |t|is a prime-power}.

Thenϕis a colour-permuting automorphism ofCay(G;S0), andS0 generates G, since every elementsof the generating setScan be written as a product of elements ofhsithat have prime-power order [4, Thm. 1.3.1(iii), p. 9], and therefore belong toS0. (Furthermore, ϕis colour-preserving if the permutationπis the identity permutation.)

Lemma 6.12. Suppose

• Cis a cyclic, normal subgroup of a groupH,

• |C|is relatively prime to|H:C|,

• no element ofHrCcentralizesC, and

• αis any automorphism ofH. Thenα(h)∈hC, for everyh∈H.

Proof. Since no other subgroup ofH has the same order asC, we know thatα|^C is an automorphism ofC, so there existsr∈Z, such thatα(c) =c^r, for everyc∈C. Then, for anyh∈Handc∈C, we have

α(h)c^rα(h)⁻¹=α(h)α(c)α(h)⁻¹=α(hch⁻¹) = (hch⁻¹)^r=hc^rh⁻¹, soh⁻¹α(h)centralizesC. By assumption, this impliesh⁻¹α(h)∈C, as desired.

Corollary 6.13. The following are equivalent:

1. There is a group of ordernthat is not CCA.

2. There is a group of ordernthat is not strongly CCA.

3. n ≥ 8, andnis divisible by either4,21, or a number of the formp^q ·q, wherep andqare primes(not necessarily distinct)andpis odd.

Proof. We prove (1⇔3) and (1⇔2).

(3 ⇒ 1) Ifnis divisible by4, then there is a generalized dicyclic group of ordern, which is not CCA (see Corollary2.8(4)). The nonabelian group of order 21 and the wreath productZpoZq (which is of orderp^q·q) are not CCA (see Examples2.3and2.4). Taking an appropriate direct product yields a non-CCA group whose order is any multiple of these (see Proposition3.1).

(1⇒3) Assume there is a groupGof ordernthat is not CCA, butnis not divisible by 4,21, or a number of the formp^q·q. From Theorem6.8, we see thatnis even. (Otherwise, n=|G|is divisible by the order of a semi-wreathed product|Ao^αZk|. If we letpandqbe prime divisors of|A|andk, respectively, then|Ao^αZk|=|A|^k·kis a multiple ofp^q·q.) Furthermore,nmust be square-free, for otherwise it is a multiple of either4orp²·2, for some primep. Therefore,Gis a semidirect productZko Z`.

We may assume the centre ofGis trivial, for otherwise we can writeGas a nontrivial direct product, so Proposition3.2(and induction onn) implies thatGis CCA. Therefore, kis odd (so`is even), so we may writeG=Zko(Zm×Z2), andZm×Z2acts faithfully onZk. LetH =Zko Zm, so|H|=kmis odd, andHis the (unique) subgroup of index2 inG.

Letϕbe a colour-preserving automorphism of a connected Cayley graphCay(G;S).

(We wish to show thatϕis affine.) There is no harm in assuming that every element ofS has prime order (see Lemma6.11). Fix somet∈Swith|t|= 2.

We claim we may assume thatt is the only element of order2 inS, and thatH = hSr{t}i. To see this, let

• Tbe the set of all elements of order2inS, and

• S⁰={t} ∪ {uv|u, v∈T, u6=v} ∪(SrT).

It is easy to see thatϕis a colour-preserving automorphism of the connected Cayley graph Cay(G;S⁰), and thatG=hSr{t}ihti. This establishes the claims.

From Theorem 6.8(and the fact that |H| is odd), we know that ϕ|^H is affine. By composing with a left translation, we may assume thatϕfixese. Thenϕ|^H is a group automorphism. By composing with an automorphism ofZk o(Zm×Z2)of the form (x, y, z)7→(x^r, y, z), we may assumeϕ|Zkis the identity map. Also, sinceϕ(s)∈ {s^±1} for everys ∈ S, and|H/Zk| = mis odd, Lemma6.12implies that ϕalso fixes every element of(S∩H)r Zk. Hence,ϕ|^His an automorphism that fixes every element of a generating set, soϕ(h) =hfor everyh∈H. Sinceϕ(ht) =ϕ(h)t=ht, for allh∈H (becauseϕis colour-preserving andt=t⁻¹), we conclude thatϕfixes every element ofG, and is therefore affine, as desired.

(1⇒2) Obvious.

(2 ⇒1) Assume there is a groupGof ordernthat is not strongly CCA, butnis not divisible by4,21, or a number of the formp^q·q. Letϕbe a colour-permuting automorphism of some connected Cayley graphCay(G;S), such thatϕ(e) =e.

As in the proof of (1⇒3) above, we see that we may assume|G|is square-free, and we may writeG=Zko(Zm×Z2), whereZm×Z2acts faithfully onZk. LetH =Zko Zm

be the (unique) subgroup of index2inG. From (1 ⇒3) above, we know thatGis CCA, soG /b A⁰. Hence,Hb JA0(since it is the unique largest normal subgroup of odd order), soϕnormalizesHb. This implies that the restriction ofϕtoHis an automorphism ofH.

For each s ∈ S, letes = ϕ(s) ∈ S. To prove that ϕ is affine, it suffices to show ϕ(xs) = ϕ(x)esfor allx ∈ Gands ∈ S (see Remark1.6(4)). If this is not the case, then, sinceϕis colour-permuting, there must be somex, such thatϕ(xs) =ϕ(x)se⁻¹(and es⁻¹6=es, which means|s| 6= 2). This will lead to a contradiction.

We may assume every element ofShas prime order (see Lemma6.11). Since|s| 6= 2, this impliess∈H. Then, sinceϕ|^H is an automorphism, but

ϕ(xs) =ϕ(x)es⁻¹=ϕ(x)ϕ(s)⁻¹6=ϕ(x)ϕ(s),

we must havex /∈H. SinceH has only two cosets, and there must be some element ofS that is not inH, this implies that we may assumex∈ S, after multiplying on the left by an appropriate element ofH (and using the fact thatϕnormalizesHb). Note that, since x /∈H, and every element ofShas prime order, this implies|x|= 2. So the order ofxeis also2, which impliesx /e∈H(since|H|is odd).

Sinceϕis colour-permuting, we have

ϕ(xs) =ϕ(^xs x) =ϕ(^xs)ex.

Also, by the choice ofxands, we have

ϕ(xs) =ϕ(x)es⁻¹=exes⁻¹. Therefore

ϕ(^xs) =^exse⁻¹.

SinceZmacts faithfully onZk, we haveα(h)≡h (mod Zk), for every automorphismα of H (see Lemma 6.12). Since ϕand conjugation by xare automorphisms of H, this impliess≡s⁻¹ (modZ^k). Since|s|is odd, we conclude thats∈Z^k.

Then, since the automorphism group of a cyclic group is abelian, we have ϕ(^xs) =^xϕ(s) =^xes,

sox⁻¹xemust invertes. But this is impossible, because, as was mentioned above,xandex, being of order2, cannot be inH, so they are both in the other coset ofH, sox⁻¹xe∈H has odd order. This contradiction completes the proof thatϕis affine.

Remark 6.14. It is not necessary to assumepis odd in the statement of Corollary6.13(3), because2^q·qis divisible by4, which is already in the list of divisors.

Theorem6.8implies that very few small groups of odd order fail to be strongly CCA:

Corollary 6.15. LetG21 =Z7o Z3be the(unique)nonabelian group of order21. Then the only groups of odd order less than100that are not strongly CCA areG21,G21×Z3, andZ3oZ3.

Proof. SupposeGis a group of odd order, such thatGis not strongly CCA and|G|<100.

From Corollary 6.13, we see that |G| is divisible by either 21 or 3³· 3 = 81. Since

|G|<100, this implies that|G|is either21,21×3 = 63, or3³·3 = 81. Also,Gmust be nonabelian (see Corollary4.2).

• The nonabelian groupG21of order21is not CCA (see Example2.3).

• There are two nonabelian groups of order63. One of them, the direct productG21× Z3, is not CCA (see Proposition3.1).

• Theorem6.8implies thatZ3oZ3is the only non-CCA group of order81(see also Example2.4).

To complete the proof, we sketch a verification that the following group of order63is CCA:

G=Z7o Z9=hx, a|x⁷=a⁹=e, a⁻¹xa=x²i.

Letϕbe a colour-preserving automorphism of a connected Cayley graphCay(G;S), such thatϕ(e) =e. We may assumeSis either{a^±1, x^±1}or{a^±1,(ax)^±1}, after discarding redundant generators, applying an automorphism ofG, and replacing some elements by appropriate powers (cf. the proof of Lemma6.11).

If S = {a^±1, x^±1}, then we may assume ϕ(x) = x, by composing with an au- tomorphism of G. Also, since ϕ is colour-preserving, it must pass to a well-defined automorphism of the cycle Cay G/hxi;{a^±1}

, so there exists ∈ {±1}, such that ϕ(ga) = ϕ(g)afor allg ∈ G. Then, since(1,1)is the only pair(, δ) ∈ {±1}² that satisfiesa⁻x^δa = x², we see thatϕ(xⁱa^j) = xⁱa^j for alliandj, soϕis the identity map, which is certainly affine.

Assume, now, thatS = {a^±1,(ax)^±1}. Leta1 = aanda2 = xa. For anyg ∈ G and ∈ {±1}, ifϕ(g a1) = ϕ(g)a₁, then, sincea³₁ = a³₂ (andϕis colour-preserving), we haveϕ(g s^m) =ϕ(g)s^m, for allmand alls∈S. SinceSgeneratesG, this implies ϕ(gs) =ϕ(g)sfor allgand alls∈S. Soϕis affine.