¿^creative	, ars mathematica
^commons	contemporánea
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 499-518
On the automorphism groups of almost all circulant graphs and digraphs*
Soumya Bhoumik
Department of Mathematics, Fort Hays State University
Hays, KS 67601, USA
Edward Dobson t
Department of Mathematics and Statisitics, Mississippi State University Mississippi State, MS 39762 USA and
UP IAM, University ofPrimorska Muzejeski trg 2, 6000 Koper, Slovenia
Joy Morris
Department ofMathematics and Computer Science, University ofLethbridge Lethbridge, AB T1K 3M4 Canada
Received 4 March 2012, accepted 18 June 2013, published online 6 October 2014 Abstract
We attempt to determine the structure of the automorphism group of a generic circulant graph. We first show that almost all circulant graphs have automorphism groups as small as possible. The second author has conjectured that almost all of the remaining circulant (di)graphs (those whose automorphism group is not as small as possible) are normal circulant (di)graphs. We show this conjecture is not true in general, but is true if we consider only those circulant (di)graphs whose order is in a "large" subset of integers. We note that all non-normal circulant (di)graphs can be classified into two natural classes (generalized wreath products, and deleted wreath type), and show that neither of these classes contains almost every non-normal circulant digraph.
Keywords: Circulant graph, automorphism group, Cayley graph, DRR, GRR. Math. Subj. Class.: 05C25, 05E18
* This paper is a part of Bled'11 Special Issue.
t Project sponsored by the National Security Agency under Grant Number H98230-11-1-0179 E-mail addresses: s bhoumik@fhsu.edu (Soumya Bhoumik), dobson@math.msstate.edu (Edward Dobson), joy.morris@uleth.ca (Joy Morris)
©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/
402
Ars Math. Contemp. 7 (2014) 379-187
1 Introduction
We must begin by introducing Cayley (di)graphs and circulant (di)graphs.
Definition 1.1. Let G be a group and S c G such that 1G e S. Define a digraph r = r(G,S) by V(r) = G and E(r) = {(u,v) : v-1u e S}. Such a digraph is a Cayley digraph of G with connection set S. A Cayley graph of G is defined analogously though we insist that S = S-1 = {s-1 : s e S}. If G = Zn, then a Cayley (di)graph of G is a circulant (di)graph of order n.
It is straightforward to verify that for g e G, the map gL : G ^ G by gL(x) = gx is an automorphism of r. Thus GL = {gL : g e G}, the left regular representation of G, is a subgroup of the automorphism group of r, Aut(r).
Determining the full automorphism group of a Cayley (di)graph is one of the most fundamental questions one can ask about a Cayley (di)graph. While it is usually quite difficult to determine the automorphism group of a Cayley (di)graph, characterizing almost all Cay-ley graphs of a group G, based on the structure of G, has been of consistent interest in the last few decades. Babai, Godsil, Imrich, and Lovasz (see [2, Conjecture 2.1]) conjectured that almost all Cayley graphs of any group G that is not generalized dicyclic or abelian with exponent greater than 2 are GRRs (graphs that have automorphism group GL). A similar conjecture (with no exceptions) was made for digraphs being DRRs (digraphs that have automorphism group GL) by Babai and Godsil [2]. Babai and Godsil [2, Theorem 2.2] proved these two conjectures for nilpotent (and nonabelian in the case of undirected graphs) groups of odd order.
Definition 1.2 (Xu [15]). A normal Cayley (di)graph of the group G is a Cayley (di)graph r = r(G, S) such that GL < Aut(r).
Xu also conjectured [15, Conjecture 1] that almost every Cayley (di)graph is normal. The precise formulation of Xu's conjecture is:
Conjecture 1.3 (Conjecture 1, [15]). For any positive integer n, we let Fn denote the class of all groups of order n, and let
# of normal Cayley digraphs of G
f (n) = mmGeF„
# of Cayley digraphs of G
Then lim f (n) = 1.
n^oo
In 2010, the second author showed that almost all Cayley graphs of an abelian group G of odd prime-power order are normal [4].
Before proceeding farther, we specify what we will mean in this paper when we say something about "almost all" graphs in a particular family:
Definition 1.4. Let F2 C F1 be two families of circulant (di)graphs, and Fi(n) (i = 1,2) be the graphs of order n G N in Fj. Then by almost all circulant (di)graphs in F are in F2, we mean that
lim i^j = 1.
|Fi(n)|
If in the above we replace N by some set I of infinitely many integers, we say that "almost all" circulant (di)graphs in F1 of order n, where n € I, are in F2.
S. Bhoumik et al.: On the automorphism groups of almost all circulants
501
Our object in this paper is to determine as far as we can what the automorphism group of a generic circulant (di)graph should look like, by recursively classifying (or attempting to classify) the automorphism groups of almost all circulant (di)graphs that do not fall within a previous step's classification.
The following maps will be used in a number of places in this paper:
Definition 1.5. Let iG : G ^ G be defined by tG(g) = g-1 for every g G G. If G = Zn, we use in instead of .
Let p : Zn ^ Zn by p(i) = i +1 (mod n). Thus (p) = (Zn)L.
Notice that if G is abelian then iG is an automorphism of every Cayley graph r(G, S) since S = S-1. Thus it is not possible for a Cayley graph on an abelian group G to be a GRR unless G = Zf, k > 1, while Imrich [7, Theorem] has shown that Zf has a GRR if and only if k = 2,3,4. Nowitz showed [11] during the classification of GRRs that a Cayley graph on a generalized dicyclic group cannot be a GRR.
Definition 1.6. We say that a Cayley (di)graph r = r(G, S) has automorphism group as small as possible if one of the following holds:
•	r is a GRR or a DRR; or
•	G is either abelian or generalized dicyclic, and |Aut(r)| = 2|G|.
When G = Zn, we let Small(n) denote the set of all circulant graphs whose automorphism group is as small as possible, and Small = U„eNSmall(n).
When G is abelian and Aut(r(G, S)) is as small as possible, we have that Aut(r(G, S)) = (Gl,ig). Clearly in normalizes (Zn)L, so every member of Small will be a normal circulant graph. The first theorem in this paper, Theorem 3.2, shows that almost all circulant graphs are in Small, and thus are normal. This represents some progress towards the proof of Xu's conjecture, and is the first step in our determination of the structure of the automorphism group of a generic circulant graph. It is a natural extension of the work of Babai and Godsil, mentioned above [2, Theorem 2.2].
From there, we proceed to consider classifying the automorphism groups of circulant (di)graphs that are not DRRs. In [4, Conjecture 4.1], the second author conjectured that almost every Cayley (di)graph whose automorphism group is not as small as possible is a normal Cayley (di)graph. We show that this conjecture fails for circulant digraphs of order n, where n = 2 (mod 4) has a fixed number of distinct prime factors (Theorem 3.5), and point out some "gaps" in the proof of [4, Theorem 3.5], which lead to additional counterexamples to [4, Conjecture 4.1] for graphs in the case where n = p or p2 and p is a safe prime, i.e. p = 2q +1 where q is prime, or when n is a power of 3 (Theorem 3.6). Finally, we prove that the conjecture holds for digraphs of order n where n is odd and not divisible by 9 (Theorem 3.7) and for graphs of order n, where n is odd, not a safe prime or the square of a safe prime and not divisible by 9 (Theorem 3.8).
In Section 4, we focus on non-normal circulant (di)graphs. A variety of authors (see [5,6,8,9]) have shown that non-normal Cayley (di)graphs are either generalized wreath products (see Definition 2.5) or have the same automorphism group as a deleted wreath product (see Definition 2.14). We show in general, neither of these classes dominate.
In the next section, we will focus on background results and terminology, as well as developing the counting tools needed in Sections 3 and 4.
402
Ars Math. Contemp. 7 (2014) 379-187
2 Preliminaries and tools
We start by stating basic definitions, and then proceed to known results in the literature that we will need. We will finish with results that will be the main tools throughout the rest of the paper.
Definition 2.1. Let G be a transitive permutation group with block system B. By G/B, we mean the subgroup of SB induced by the action of G on B, and by fixG(B) the kernel of this action. Thus G/B = {g/B : g e G} where g/B(Bx) = B2 if and only if g(Bi) = B2, B1,B2 e B, and fixG(B) = {g e G : g(B) = B for all B e B}.
Let G be a transitive permutation group, B a block system of G, and (p) < G. Since (p) is transitive and abelian, it is regular [13, Proposition 4.4], and so there is a subgroup of (p) (namely fix(p) (B)) whose orbits are precisely the blocks of B. It is therefore not difficult to show that B consists of the cosets of some (cyclic) subgroup of Zn.
A vertex-transitive (di)graph is a (di)graph whose automorphism group acts transitively on the vertices of the (di)graph.
Definition 2.2. The wreath (or lexicographic) product of r1 and r2, denoted r1l r2, is
the digraph such that V(r l r2) = V(ri) x V(r2) and edge set
{((x, x'), (y, y')) : xy e ECF), x', y' e V(r2) or x = y and x'y' e E(r2)}.
We remark that the wreath product of a circulant digraph of order m and a circulant digraph of order n is circulant. Note that what we have just defined as r11 r2 is sometimes defined as r2 l r1, particularly in the work of Praeger, Li, and others from the University of Western Australia.
Definition 2.3. Let Q be a set and G < Sq be transitive. Let G act on QxO by g(w1, w2) = (g(w1), g(w2)) for every g e G and w1, w2 e Q. We define the 2-closure of G, denoted to be the largest subgroup of Sq whose orbits on Q x Q are the same as G's. Let O1,..., Or be the orbits of G acting on Q x Q. Define digraphs r1,..., rr by V(F) = Q and E(F) = Oi. Each F,1 < i < r, is an orbital digraph of G, and it is straightforward to show that G(2)
= nr=1 Aut(rj). A generalized orbital digraph of G is an arc-disjoint union of orbital digraphs of G. We say G is 2-closed if G(2) = G.
Clearly the automorphism group of a graph or digraph is 2-closed. The following theorem appears in [10] and is a translation of results that were proven in [6,8,9] using Schur rings, into group theoretic language. We have re-worded part (1) slightly to clarify the meaning. In the special case of circulant digraphs of square-free order n, an equivalent result was proven independently in [5].
Theorem 2.4. Let G < Sn contain (p). Then one of the following statements holds:
1.	There exist G1,... ,Gr such that G(2) = G1 x ... x Gr, and for each Gjt either Gi = Sni, or Gi contains a normal regular cyclic group of order Ui. Furthermore,
r > 1, gcd(ni, Uj) = 1 for i = j, and n = n^2 • • • nr.
2.	G has a normal subgroup M whose orbits form the block system B of G such that each connected generalized orbital digraph contains a subdigraph r which is an orbital digraph of G and has the form r = (r/B) 11Kb, where b = |M n (p)|.
S. Bhoumik et al.: On the automorphism groups of almost all circulants
503
Definition 2.5. A circulant digraph r(Zn, S) is said to be a (K, H)-generalized wreath circulant digraph (or just a generalized wreath circulant digraph) if there exist groups H, K with 1 < K < H < Zn such that S \ H is a union of cosets of K.
The name generalized wreath is chosen for these digraphs as if K = H, then r is in fact a wreath product. We now wish to investigate the relationship between generalized wreath circulant digraphs and the preceding result. We shall have need of the following lemma.
Lemma 2.6. Let r be a disconnected generalized orbital digraph of a transitive group G. Then the components of r form a block system B of G.
Proof. As the blocks of G(2) are identical to the blocks of G [12, Theorem 4.11] ( [12] is contained in the more accessible [14]), we need to show that the set of components B of r is a block system of G(2). This is almost immediate as G(2) = n[n1Aut(rj), where r1, • • • , rr are all of the orbital digraphs of G. Assume that r = Ufn1r.j, for some s < r. Then nsn1 Aut(r) < Aut(r), so that B is a block system of nf=1 Aut(r). Also, G < G(2) = nr=1Aut(ri) < nsn1 Aut(r). Thus B is a block system of G(2) as B is a block system of nf=1 Aut(r).	□
We will require the following partial order on block systems.
Definition 2.7. We say that B < C if for every B e B there exists C e C with B C C. That is, each block of C is a union of blocks of B. For g e StabG(C), C e C, we denote by g|C the permutation defined by g|C(x) = g(x) if x e C and g|C(x) = x otherwise. For H < StabG(C), we write H|c = jg|G : C e c}.
Our main tool in examining generalized wreath circulants will be the following result.
Lemma 2.8. Let G be 2-closed with a normal subgroup M and a regular subgroup (p). Let B be the block system of G formed by the orbits of M, and suppose that each connected generalized orbital digraph contains a subdigraph r which is an orbital digraph of G and has the form r = (r/B) 1Kb, where b = |M n(p)|. Then there exists a block system C ^ B of G such that fixg(2) (B)|C < G(2) for every C e C.
Proof. Observe that we may choose M = fixG(B), in which case |M n (p)| = |B|, where B e B, so that b is the size of a block of B. First suppose that if B, B' e B, B = B', then any orbital digraph r' that contains some edge of the form xy with x e B, y e B' has every edge of the form xy, with x e B, y e B'. It is then easy to see that every orbital digraph r of G can be written as a wreath product r' = r11 r2, where r1 is a circulant digraph of order n/b and r2 is a circulant digraph of order b. Then G/B I fixG(B)|B < Aut(r') for every orbital digraph r', and so G/B I (fixG(B)|B ) < G(2). Then result then follows with C = B. (Note that G is 2-closed, so G(2) = G.)
Denote the orbital digraph that contains the edge xy by rxy. We may now assume that there exists some B, B' e B, B = B', and x e B, y e B' such that rxy does not have every edge of the form x'y', with x' e B and y' e B'. Note then that no Txiyi with x' e B and y' e B' has every directed edge from B to B'. Let X be the set of all rxy such that if x e B1 e B and y e B2 e B, B1 = B2, then rxy does not have every edge from B1 to B2. Let r be the generalized orbital digraph whose edges consist of all edges from every orbital digraph in X, as well as every directed edge contained within a block of B. Then no
402
Ars Math. Contemp. 7 (2014) 379-187
orbital digraph that is a subgraph of f can be written as a connected wreath product r' l Kb for some r', and so by hypothesis, r must be disconnected.
By Lemma 2.6, the components of r form a block system C X B of G. (To see that C X B, note that r contains every edge from B to B', so B is in a connected component of r. Since G is transitive, C X B.) Let Ti, r2,..., rr be the orbital digraphs of G, and assume that Uf^r* = f. If 1 < i < s, then (G(2)/C) l (fixg(2) (C)|c) < Aut^); this is because G(2) < Aut(Fj), r is disconnected, and each component is contained in a block of C. Thus fixg(2) (B)|C < Aut(Fj) for every 1 < i < s. If s +1 < i < r, then if B, B' € B, B = B' and xy G E(Fj) for some x G B, y G B', then xy G E(r,) for every x G B and y G B'. Also observe that as the subgraph of r induced by B is Kb, the subgraph of r induced by G is Kb. We conclude that r = r^/B l Kb, and so Aut^/B) l Sb < Aut(rj). Then fixg(2) (B)|b < Aut^) for every B G B. As B X C, fixg(2) (B)|c < Aut(ri) for every 1 < i < r and as G(2) = nr=1Aut(ri), fixG(2) (B) | G < G(2) for every C G C.	□
Lemma 2.9. Let r be a circulant digraph of order n. Then r is a (K, H)-generalized wreath circulant digraph if and only if there exists G < Aut(r) such that G contains a regular cyclic subgroup, and fixg(2) (B)|C < G(2) for every C G C, where B X C are formed by the orbits of K and H, respectively.
Proof. Suppose first that G < Aut(r) with p G G, and there exist block systems B X C of G such that fixg(2) (B)|c < G(2) < Aut(r) for every C G C. Since p G G, the action of fixG(2) (B) |C is transitive on every B C C, so between any two blocks B1, B2 G B that are not contained in a block of C, we have that there is either every edge from B1 to B2 or no edges from B1 to B2. Let B be formed by the orbits of K < (p). Then for every edge xy whose endpoints are not both contained within a block of C, (y - x) + K c S. Let C be formed by the orbits of H < (p). Then S \ H is a union of cosets of K as required.
Conversely, suppose that r is a (K, H)-generalized wreath circulant digraph. Then pm|C G Aut(r) for every C G C, where m = [Zn : K]. Let G < Aut(r) be the maximal subgroup of Aut(r) that admits both B and C as block systems; clearly p g G. Also, since G(2) has the same block systems as G and G(2) < Aut(r), G(2) = G. Now, if g G fixG(B), then g|C G Aut(r) as well. But this implies that g|C G G.	□
Combining Lemma 2.8 and Lemma 2.9, and recalling that the full automorphism group of a (di)graph is always 2-closed, we have the following result.
Corollary 2.10. Let r be a circulant digraph whose automorphism group G = Aut(r) satisfies Theorem 2.4(2). Then r is a generalized wreath circulant digraph.
We now wish to count the number of generalized wreath circulant digraphs.
Lemma 2.11. The total number of generalized wreath circulant digraphs of order n is at most
^^ 2n/p-1( ^^ 2(n-n/p)/q
p|n	q|(n/p)
where p and q are prime.
Proof. Let r be a (K, H)-generalized wreath circulant digraph of order n. By Lemma 2.9, there exists G < Aut(r) that admits B and C such that p G G, and fixg(2) (B) |C < Aut(r)
S. Bhoumik et al.: On the automorphism groups of almost all circulants
505
for every C e C, where B is formed by the orbits of K and C is formed by the orbits of H. Let B consist of m blocks of size k. Then pm|C e Aut(T) for every C eC. Choose q|k to be prime, and let G' < Aut(r) be the largest subgroup of Aut(T) that admits a block system D consisting of n/q blocks of size q. Note then that pn/q |C e G' for every C e C. Let p be a prime divisor of the number of blocks of C, and E the block system of (p) consisting of p blocks of size n/p. Then C < E and pn/q|E e G' for every E e E. Thus every (K, H)-generalized wreath circulant digraph is a (Lq, Mp)-generalized wreath circulant digraph, where Lq has prime order q where q divides |K| and Mp has order n/p where p divides n/|H |. Note that there is a unique subgroup of Zn of prime order q for each q|n, and that Mp is also the unique subgroup of Zn of order n/p.
As |Lq | = q, we use the definition of an (Lq, Mp)-generalized wreath circulant digraph to conclude that S \ Mp is a union of some subset of the (n - n/p)/q cosets of Lq that are not in Mp. Thus there are 2(n-n/p)/q possible choices for the elements of S not in Mp. As there are at most 2n/p-1 choices for the elements of S contained in Mp, there are at most 2n/p-i • 2(n-n/p)/q = 2n/p+n/q-n/(pq)-1 choices for S. Summing over every possible choice of q and then p, we see that the number of generalized wreath digraphs is bounded above by
2n/P-1 ( ^^ 2(n-n/p)/M
q|(n/p)
□
We will denote the set of all circulant digraphs of order n whose automorphism groups are of generalized wreath type by GW(n). The corresponding set of all circulant graphs will be denoted by GWG(n). Note that no term in the previous summation given in Lemma 2.11 is larger than 2n/p+n/q-n/(pq)-1, where q is the smallest prime divisor of n and p is the smallest prime divisor of n/q. As the number of prime divisors of n is at most log2 n, we have the following result.
Corollary 2.12. Let q be the smallest prime dividing n, and p the smallest prime prime dividing n/q. Then
|GW(n)| < (log2 n)2n/p+n/q-n/pq-1.
Using the fact that there are at most two elements that are self-inverse in Zn (namely 0 and n/2 if n is even, and 0 ^ S), and at most one coset of Zn/Lq that is self-inverse and not in Mp (as Zn/Lq is cyclic), and the fact that (p + q - 1)/pq < 3/4, a similar argument shows that:
Corollary 2.13. Let q be the smallest prime dividing n, and p the smallest prime prime dividing n/q. Then
|GWG(n)| < (log2 n)2n(P+q-1)/(2Pq)+1/2 < (log2 n)23n/8+1/2.
We now consider circulant (di)graphs r for which Aut(r) satisfies Theorem 2.4 (1), and use the notation of that result. If no Gj = Sni with n > 4, then Aut(r) contains a normal regular cyclic group and r is a normal circulant digraph. Otherwise, we have the following definition.
Definition 2.14. A circulant (di)graph T(Z„, S) is of deleted wreath type if there exists some m > 1 such that:
402
Ars Math. Contemp. 7 (2014) 379-187
•	m | n;
•	gcd(m,n/m) = 1; and
•	if H = (n/m) is the unique subgroup of order m in G, then S n H G {0, H \ {0}}, and for every g G (m)\{0}, S n (g + H) G {0, {g}, (g + H) \{g},g + H}. (Notice that because gcd(m, n/m) = 1, the group (m) contains precisely one representative of each coset of H in G.)
A circulant digraph is said to be of strictly deleted wreath type if it is of deleted wreath type and is not a generalized wreath circulant.
There are deleted wreath type circulants which are not of strictly deleted wreath type. For an example of this, consider a circulant digraph on pqm vertices where m > 4 and p, q and m are relatively prime, whose connection set is S = ((pq) \ {0}) U (m + (mq)). This digraph is an (H, K)-generalized wreath circulant for H = (q) and K = (mq). It is also of deleted wreath type with H = (pq), since S n H = H \ {0}, while for g g (m) \ {0}, we have S n (g + H) = {g} if g g m + (mq) and S n (g + H) = 0 otherwise.
Definition 2.15. For a positive integer m, and a digraph r, we denote by mr the digraph consisting of m vertex-disjoint copies of r. The digraph r l Km — mr is a deleted wreath product. Thus this digraph is the digraph whose vertex set is the vertex set of r l Km and whose edge set is the edge set of r l Km with the edges of mr removed.
The name deleted wreath type is chosen as these digraphs have automorphism groups that are isomorphic to the automorphism groups of deleted wreath products.
Lemma 2.16. Let r = r(Zn, S), and let m > 4 be a divisor of n such that gcd(m,n/m) = 1. Then r is of deleted wreath type with m being the divisor of n that satisfies the conditions of that definition, if and only if Aut(r) contains a subgroup isomorphic to H x Sm with the canonical action, for some 2-closed group H with Zn/m < H < Sn/m.
Proof. In this proof for a given m satisfying n = km and gcd(m, k) = 1, it will be convenient to consider Zn = Zk x Zm in the obvious fashion. For i G Zk, set Bj =
j) : j G Zm}.
First, suppose r is of deleted wreath type with m > 4 being the divisor of n that satisfies the conditions of that definition, and n = mk. Using Zn = Zk x Zm, we see that for every i G Zk \ {0}, we have S n Bj G {0, {(i, 0)},Bj \ {(i, 0)},Bj}. Also, S n Bo G {0,Bo \ {(0,0)}}. Let B = {Bj : i G Zk} and let G < Aut(r) be maximal such that G admits B as a block system. Let H < Sk be the projection of G onto the first coordinate. Since Zk x Zm = (p) < G, clearly Zk < H.
We claim that H xSm < Aut(r). Let ((ii,ji), (i2,j2)) G E(r),and (h,g) G H xSm. Suppose first that i1 = i2. We have S n B0 g {0,Bo \ {(0,0)}}, and i1 = i2 forces S n Bo = 0. Hence r[Bj] is complete, so clearly ((h(ii), g(ji)), (h(i2),g(j2))) G E(r), as h(i2) = h(i1). Now suppose i1 = i2. So h(i1) = h(i2). Let i = i2 - i1 and let i' = h(i2) — h(i1), with 1 < i, i' < k — 1. By the definition of H, there is some g G G that takes Bj1 to Bh(jl) and Bj2 to Bh(j2). Hence the number of arcs in r from Bj1 to Bj2, which is |S n Bj|, must be the same as the number of arcs from Bh(jl) to Bh(j2), which is |S n Bj' |. Since 1 < i,i' < k — 1 and (i1,j1), (i2,j2) G E(r), |Sn Bj| = |S n Bj, | must be 1, m — 1 or m. Since m > 4 > 2, the integers 1, m — 1 and m are all distinct, so S n Bj and S n Bj/ are uniquely determined by their cardinality. If |S n Bj| = 1, then
S. Bhoumik et al.: On the automorphism groups of almost all circulants
507
S n Bi = {(i, 0)} and j2 = ji. Hence g(ji) = gj'2), and since S n B^ = {(i', 0)}, the arc ((h(i1), g(j1)), (h(i2), g(j2))) is in r. Similarly, if the cardinality is m - 1, then S n Bi = {Bi \ {(i, 0)}} so j2 = ji. Hence g(ji) = gja), and since S n Bi, = {Bi/ \ {(i', 0)}}, the arc ((h(ii), g(ji)), (h(i2), g(j2))) is in r. Finally, if the cardinality is m, then S n Bi = Bi, and S n Bi, = Bi,, so the arc ((h(ii), gCn)), (h(i2), g(j2))) is in r. Thus H x Sm < Aut(r).
By [12, Theorem 4.11], we have that (H x Sm)(2) admits B as H x Sm < Aut(r) does. Finally, by [3, Theorem 5.1], Aut(r) > (H x Sm)(2) > H(2) x Sm. As H is the projection of G onto the first coordinate, we conclude that H(2) = H and H is 2-closed.
Conversely, assume that Aut(r) contains a subgroup isomorphic to H x Sm with the canonical action, for some 2-closed group H with Zn/m < H < Sn/m. Clearly StabixSm(0,0) is transitive on Bi \ {(i, 0)}, and so the orbits of StabixSm(0,0) on Bi are {(i,0)} andBi\{(i, 0)}. Also 1xSm < HxSm < Aut(r) implies StabixSm(0,0) < StabHxSm (0,0) < StabAut(r) (0,0). Thus each Sn Bi is a union of some (possibly none) of these two orbits. Hence the only possibilities for each S n Bi are 0, {(i, 0)}, Bi \ {(i, 0)} and Bi if 1 < i < k - 1; and since 0 £ S, S n B0 is either 0 or B0 \ {(0,0)}.	□
We remark that the above lemma shows that a deleted wreath product type circulant digraph is not a normal circulant digraph when m > 4.
The following result is an easy consequence of Lemma 2.16 together with the fact that the 2-closure of a direct product is the direct product of the 2-closures of the factors [3, Theorem 5.1].
Corollary 2.17. A non-normal circulant (di)graph whose automorphism group satisfies the conclusion of Theorem 2.4(1) is of deleted wreath type with m > 4.
Corollary 2.18. There are at most 2n/m+i graphs r and at most 22n/m digraphs r that contain K x Sm for any choice of K that is 2-closed and has Zn/m < K < Sn/m, where m > 4. Equivalently, there are at most 22n/m digraphs of deleted wreath type, and at most 2n/m+i graphs of deleted wreath type, for any fixed m > 4 with m | n and
gcd(m, n/m) = 1.
Proof. A consequence of Lemma 2.16 is that there are 2 • 4n/m-i < 4n/m = 22n/m digraphs r of order n such that K x Sm < Aut(r) for m > 4. Note that a digraph r with Aut(r) = K x Sm, m > 3, is a graph if and only if K contains the map in/m. Then in/m(g + H) = (—g) + H where H = (n/m), and so if n/m is odd, there are at most 4n/(2m) = 2n/m graphs r that contain K x Sm for any choice of K that is 2-closed and has Zn/m < K < Sn/m. Even if n/m is even, only one nontrivial coset of (n/m) is fixed by in/m, so there are at most 2 • 4 • 4(n/m-2)/2 = 2n/m+i graphs r that contain K x Sm for any choice of K that is 2-closed and has Zn/m < K < Sn/m.	□
3 Normal circulants
In this section our main focus is on determining whether or not almost all circulants that do not have automorphism groups as small as possible are normal circulants, as conjectured by the second author [4, Conjecture 1]. We begin by showing that almost every circulant graph of order n has automorphism group as small as possible. We remark that Babai and Godsil [2, Theorem 5.3] have shown this to be true for Cayley graphs on abelian groups of order n, where n = 3 (mod 4).
402
Ars Math. Contemp. 7 (2014) 379-187
We require some additional notation that will be used through the remainder of this paper.
Definition 3.1. Let ACG(n) be the set of all circulant graphs of order n.
Throughout this paper Zn denotes the group of units (invertible elements) of Zn. For a € Zn, we define a : Zn ^ Zn by a(i) = a«. As previously defined, if a = -1 then we denote a by . Finally, by |g| we denote the order of any element g in any group G.
Theorem 3.2. For almost every circulant graph r, Aut(r) is as small as possible. More precisely,
|Small(n)|
lim ---—— = 1
n-ico |ACG(n)|
Proof. We first count the number of circulant graphs of order n not in Small(n). By Corollary 2.13, there are at most log2 n • 23n/8+1/2 generalized wreath circulant graphs of order n.
Now assume r € GWG(n) U Small(n). By Corollary 2.10, Aut(r) satisfies Theorem 2.4(1). Either Aut(r) normalizes (p) or Gj = Sni for some n > 4 (using the notation of Theorem 2.4(1)). We will find an automorphism a of Zn such that a € Aut(r) \ (in). Obviously, if (p) < Aut(r), then since r € Small(n), such an a exists. If Gj = Sni and nj > 4, then Gj contains a nontrivial automorphism b of Zni. Regard Zn as Zn/n. x Zni in the usual way. If nj > 7 then we may choose b = ±1, and a = (1, b). We may assume n is arbitrarily large, so if 4 < nj < 7 we may assume n/nj > 3, and let a = (-1,1). Thus there exists a € Aut(Zn) n Aut(r) but not in (in).
Now observe that has at most two fixed points, and so has at most (n - 2)/2 + 2 orbits. Let a € Aut(Zn) be such that a € (in). Observe that we may divide the orbits of (in, a) into three types: singleton orbits, orbits of length 2, and orbits of length greater than 2. As (in) has at most 2 singleton orbits, (in, a) has at most two singleton orbits, namely 0 and n/2. If x = 0, n/2, then x is contained in an orbit of (in) of length 2. If such an x is contained in an orbit of ((.„, a) of length 2, then setting a = a, a € Z£, we have that {x, —x} = {ax, -ax}, in which case either x = ax and x is a fixed point of a, or x = -ax and x is a fixed point of ina. If x = ax set ft = a and if x = -ax, set ft = ina. Then ((,„, a) = ((,„, ft), and x is a fixed point of ft. It is easy to see that the set of fixed points of ft, say H(ft), forms a subgroup of Zn, and so |H(ft)| < n/2. Thus ((.„, a) has at at most (n/2 -1)/2 orbits of length two, and so at most (n/2 -1)/2+2 orbits of length one or two. Every remaining orbit of (in, a) is a union of orbits of (in) of size 2, and so every remaining orbit of (in, a) has length at least 4. Clearly, the number of orbits of (in, a) is maximized if it has 2 orbits of length 1, (n/2 - 1)/2 orbits of length 2, and the remainder have length greater than 2. In this case, there will be at most (n/2 - 1)/4 = n/8 - 1/4 orbits of length greater than 2. We conclude that there are at most 3n/8 + 5/4 orbits of (in, a), and as S must be a union of orbits of (in, a) not including {0}, there are at most 23n/8+1/4 such circulant graphs for each a € Aut(Zn), a € (in). As there are at most n (actually <^(n) of course) automorphisms of Zn, there are at most n • 23n/8+1/4 circulant graphs that contain an automorphism of Zn other than in.
We have shown that there are at most n • 23n/8+1/4 + log2 n • 23n/8+1/2 < V2(n + log2 n)23n/8 circulant graphs of order n that are not in Small(n). As there are 2(n-2)/2+1 = 2n/2 circulant graphs of order n if n is even and 2(n-1)/2 circulant graphs
S. Bhoumik et al.: On the automorphism groups of almost all circulants
509
of order n if n is odd,
|Small(n) | n^ |ACG(n)|
lim
> 1 — lim
n-

V2(n + log2 n)23n/8 2(n-1)/2
1.
□
The above theorem clearly shows that almost all circulant graphs are normal. In 2010, the second author made the following conjecture for Cayley (di)graphs (not necessarily circulant) whose automorphism group is not as small as possible [4, Conjecture 1].
Conjecture 3.3. Almost every Cayley (di)graph whose automorphism group is not as small as possible is a normal Cayley (di)graph.
It is difficult to determine the automorphism group of a (di)graph, so the main way to obtain examples of vertex-transitive graphs is to construct them. An obvious construction is that of a Cayley (di)graph, and the conjecture of Imrich, Lovasz, Babai, and Godsil says that when performing this construction, additional automorphisms are almost never obtained. The obvious way of constructing a Cayley (di)graph of G that does not have automorphism group as small as possible is to choose an automorphism a of G and make the connection set a union of orbits of a. The above conjecture in some sense says that this construction almost never yields additional automorphisms other than the ones given by the construction.
Throughout the remainder of this paper, all circulant digraphs of order n whose automorphism groups are of deleted wreath, and strictly deleted wreath types will be denoted by DW(n), and SDW(n) respectively. The corresponding set of all graphs whose automorphism groups are of deleted wreath type will be denoted by DWG(n). If we wish to consider a subset of one of these sets with a restriction on m, we indicate this in a subscript, as for example DW(n)m>4. Also, the sets of all digraphs that are circulants, DRR circulants, normal circulants, and non-normal circulants of order n will be denoted as ACD(n), DRR(n), Nor(n) and NonNor(n), respectively. The corresponding sets of all graphs that are circulants, normal circulants, and nonnormal circulants, will be denoted by ACG(n), NorG(n), and NonNorG(n), respectively.
The following lemma will prove useful in determining how many circulant (di)graphs are not normal.
Lemma 3.4. If a circulant digraph r of composite order n that is a (K, H)-generalized wreath circulant digraph is normal, then 4 | n.
Proof. Without loss of generality we may assume that K is of prime order p. Let B be the block system of (p) formed by the orbits of (pm), where |H | = n/m. Then pn/p|B G Aut(r) for every B G B. Set G = (p,pn/p| b : B G B),and let C be the block system of G formed by the orbits of (pn/p), so that fixG(C ) = (pn/p| b : B G B), and has order pn/m. Then C is also a block system of N (n), where N (n) = {x ^ ax + b : a G Zn, b G Zn}. Let n = pi1 pi2 • • • pir be the prime power decomposition of n. As N(n) = nr=1N(p"i ), we see that a Sylow p-subgroup of fixN(n) (C) is a Sylow p-subgroup of 1Sn/pa x N(p1), where p = pj and a = aj for some j. Let E be the block system of N (p1) consisting of blocks of size p. Then a Sylow p-subgroup of fixN(pa ) (E) has order at most p2 as a Sylow p-subgroup of N(p1) is metacyclic. If r G Nor(n), then (p) < G since G < Aut(r), so G < N(n). This implies that a Sylow p-subgroup of fixG(C) has order at most p2, and
402
Ars Math. Contemp. 7 (2014) 379-187
so pn/m < p2. Since H > 1 we have n > m, so this forces n = 2m, and B consists of 2 blocks. Finally, let J = pn/p|B, where B G B with 0 G B. If r G Nor(n), then Y = p-1J-1pJ G (p), and straightforward computations will show that Y(i) = i + n/p if i is even, while y(i) = i - n/p if i is odd. As y G (p), we must have that n/p = -n/p (mod n), and so 2n/p = 0 (mod n). This then implies that p = 2 and so 4|n as required.	□
We first show that Conjecture 3.3 is false for circulant digraphs of order n, where n = 2 (mod 4) has a fixed number of distinct prime factors.
Theorem 3.5. Let n = 2p11 p22 • • • , where the pi are distinct odd primes and r is fixed. Then
|NonNor(n)| > 1 fixed |Nor(n)\DRR(n) | 2(2r — 1)
Proof. By Lemma 3.4, we have that |NonNor(n) | > |GW(n) |. We claim that |GW(n) | > 2n/2+n/(2p)-1, where 1 = p is the smallest divisor of n/2. To see this, we construct this number of distinct generalized wreath circulant digraphs of order n, as follows: B will be the block system formed by the orbits (cosets) of (n/2), and C the block system formed by the orbits (cosets) of (p). Since there are n/p elements in each block of C, there are 2n/p-1 choices for S n C0, where C0 is the block of C that contains 0. Since there are n/2 — n/(2p) orbits (cosets) of (n/2) that are not in C0, there are 2n/2-n/(2p) choices for S — C0 that create a generalized circulant digraph with this choice of B and C. These 2n/p+n/2-n/(2p)—1 = 2n/2+n/(2p)-1 generalized circulant digraphs are all distinct (though not necessarily nonisomorphic), so |GW(n)| > 2n/2+n/(2p)-1 as claimed.
Let S(n) be the set of all circulant digraphs of order n whose automorphism group contains a nontrivial automorphism of Zn. Clearly then |S(n)| > |Nor(n)\DRR(n)|. We now seek an upper bound on |S(n)|. Observe that for any circulant digraph r, if there exists an nontrivial automorphism a G Aut(r) n Aut(Zn), then we may choose such an a of prime order.
Let 1 = a G Z*n have prime order £. We first consider the case that a has a fixed point i = 0. Then ai = i (mod n), so (a — 1)i = 0 (mod n). Since a = 1, we must have gcd(i,n) = m > 1, which clearly implies i G (m). Since a G a = sn/m + 1 for some 0 < s < m must be a unit, i.e., gcd(n, sn/m + 1) = 1. Note that m > 2, since if m = 2 then s = 1, but gcd(n, n/2 + 1) > 2 since n/2 is odd. Now, a fixes n/m points {0, m, • • • , (n/m — 1)m}, and since |a| = £ is prime, every non-singleton orbit of a has length £. So a has n(1 — 1/m)/£ orbits of length £, and n/m + n/£ — n/(m£) orbits in total. We will separate the cases £ = 2 and £ = 3 to make the proof easier. If £ = 2 then 1/m + 1/£ — 1/(m£) = 1/2 + 1/(2m) < (p + 1)/(2p) since m > p (p is still the smallest nontrivial divisor of n/2), so if |a| = 2, then a has at most (p + 1)n/(2p) orbits. If £ = 3 then 1/m + 1/£ — 1/(m£) = 1/3 + 2/(3m) < (p + 2)/(3p) since m > p, so if |a| = 3, then a has at most (p + 2)n/(3p) orbits. Finally, if £ > 5 then 1/m + 1/£ — 1/(m£) < (m + 4)/(5m) < 7/15 since m > 3, so if |a| > 5 then a has at most 7n/15 orbits.
Finally, notice that if a fixes only 0, it will have 1 fixed point and n — 1 points that are not fixed. If |a| = 2 then its orbits are all of length 1 or 2, and since n — 1 is odd, it cannot be partitioned into orbits of length 2. So an element of order 2 must have some fixed point other than 0. Hence if a fixes only 0, it must have order at least 3, so each non-singleton
S. Bhoumik et al.: On the automorphism groups of almost all circulants
511
orbit must have length at least 3. Hence a has at most |(n - 1)/3J < n/3 orbits other than {0}.
We now split the set of all elements of Z*n that have prime order into disjoint subsets: U (consisting of all elements of order 2 that have fixed points); V (consisting of all elements of order 3 that have fixed points); W (consisting of all elements of order 5 or greater that have fixed points) and X (consisting of all elements that have no fixed points other than 0). Notice that Zn = Z*ej x ... x Z*er and each Z^ is cyclic, so contains a unique element of order 2. Any element of order 2 in Zn must be a product of elements of order 1 or 2 from the Zp,, at least one of which must have order 2. So there are 2r - 1 elements of order 2 in Zn. Also, there are at most n elements of any other order in Zn. Thus,
|S(n)| < 2(p+1)"/(2p) + 2(P+2)n/(3P} + Y 27"/15 + Y 2"/3
aeU	a£V	aew	aex
< (2r - 1)2(p+1)n/(2p) + n(2(p+2)n/(3p) + 27"/15 + 2"/3).
Now,
|NonNor(n)|	,	2n/2+n/(2p)-1	1
lim , ' _____V ,, > lim	-
fixed |Nor(n)\DRR(n)| _ n^,r fixed |S(n)|	2(2r - 1)'
□
A safe prime is a prime number p = 2q +1, where q is also prime. We now show that it is not true that almost all circulant graphs of order p or p2, where p is a safe prime, or of order 3k, are normal. This shows that [4, Theorem 3.5] is not correct. We provide a correct statement of [4, Theorem 3.5] as well as point out explicitly where "gaps" occur in the proof. As a consequence, much of the following result is essentially the same as the proof of [4, Theorem 3.5]. The entire argument is included for completeness.
Theorem 3.6. Let X = {p,p2 : p is a safe prime} U {3k : k e N}, T the set of all powers of odd primes, and R = T \ X. Then
lim	|NonNorG(n)| =0
n£R,n^» |ACG(n) \ Small(n)| '
Additionally, if n e X, then more than one fifth of all elements of ACG(n) \ Small(n) are in NonNorG(n).
Proof. Let n = pk e T, where p is an odd prime, r = r(Zn, S).
First suppose that k = 1. The statement about X is vacuously true for p = 3 and easy to verify for p = 5, so we assume p > 5. If p = 2q +1 is a safe prime, then Z* is cyclic of order 2q > 6, so every element of Z* has order 2, q, or 2q. Since ip e Aut(r), if re Small(p) is normal then a e Aut(r) for a e Zp of order q or 2q. Since q > 2, the orbit of length q that contains 1 in Zp does not contain -1, so the orbits of (a, tp) have length 1 (the orbit of 0) and 2q = p - 1 (everything else). So r = Kp or Kp and Aut(r) = Sp contradicting r being normal. Hence ACG(p) \ Small(p) C NonNorG(p). (The proof of [4, Theorem 3.5] overlooks this case.)
Now if p is not a safe prime, then we can write (p -1)/2 = rs where 1 <r < s< (p -1)/2. As Zp is cyclic of order p - 1, there is a e Zp with |a| = 2r. Then a has s +1 orbits
402
Ars Math. Contemp. 7 (2014) 379-187
(the cosets of (a) in Z*, together with 0). Since |a| is even, -1 G (a). If S is a union of these orbits, r is a graph, and since |a| > 2, r G Small(p). Hence | ACG(p) \ Small(p) | > 2s > 2^(p-1)/2. Meanwhile, if Aut(r) < AGL(1,p) then Aut(r) = Sp by [1], and r = Kp or Kp. So |NonNor(p)| = 2 and clearly 2/(2V(p-1)/2) ^ 0 as p ^ to.
Now let k > 2. Through the rest of this proof, let a = pk-1 + 1. We show that a G Aut(r) if and only if r G NonNor(n). Using the binomial theorem, it is easy to see that | a| = p. Furthermore, a fixes every element of (p), and fixes setwise every coset of (pk-1). Since |a| = p and a does not fix any element of any coset of (pk-1) that is not in (p), the orbits of a on each coset of (pk-1) that is not in (p) have length p. Thus if a G Aut(r), then r is a ((pk-1), (p))-generalized wreath circulant digraph, and in fact by Lemma 3.4, r G NonNor(n). Conversely, if r G NonNor(n), then by Theorem 2.4, Aut(r) either falls into category (1) with a single factor in the direct product (since n = pk does not permit coprime factors) and since r G NonNor(n), r is complete (or empty), or category (2) so by Corollary 2.10, r G GW(n). Since K„, K„ G GW(n), r G GW(n). It is straightforward to verify using the definition of a generalized wreath circulant, that a G Aut(r).
Now suppose p = 3. We have Z^fc is cyclic of order 2 • 3k-1. For r G Nor(3k) \ Small(3k), there exists -1 = b G Z3k with b G Aut(r). If |b| is divisible by 3, then since Z*k is cyclic and a generates the unique subgroup of order 3, we have a G (b), so a G Aut(r). Hence r G NonNor(3k). But the only divisor of 2 • 3k-1 not divisible by 3 is 2, and so b = -1. This shows that if r G NorG(3k) then r G Small(3k). Thus ACG(3k) \ Small(3k) C NonNorG(3k).
Now we calculate |NonNorG(n)|. As noted above, if r G NonNorG(n) then a G Aut(r), and the orbits of a all have length 1 or length p. Now since multiplication is commutative, ipk permutes the orbits of (a), and since |a| = p is odd, ipk G (a), so ipk will exchange pairs of orbits of (a), except the orbit {0}. Consequently, (a, ipk) will have one orbit of length 1 ({0}); (pk-1 - 1)/2 orbits of length 2 (whose union is (p) \ {0}); and (pfc - pk-1)/(2p) orbits of length 2p (everything else). So (a, ipk) has exactly pk-1 - (1 + pk-2)/2 orbits other than {0}. Since we have shown that r G NonNor(pk) if and only if (a, ipk) < Aut(r), |NonNor(pk)| = 2Pk-1-(1+Pk-2)/2.
Now we find a lower bound for |ACG(n) \ Small(n)| when n G R and k > 2. Since p is an odd prime, Z*k is cyclic of order (p - 1)pk-1. Let b G Z*k have order p - 1. Note that ipk G (b) since b has even order, and b = ipk since p > 3 (the proof of [4, Theorem 3.5] overlooks the fact that b = ipk when p = 3). Clearly, b fixes 0, and since the order of b is p - 1, every other orbit of b has length at most p - 1, so b has at least (pk - 1)/(p - 1) orbits other than {0}. Thus there are at least 2(p -1)/(p-1) circulant graphs of order pk whose automorphism group contains b, and |ACG(pk) \ Small(pk)| > 21+(p -1)/(p-1), p > 3. Note that as k > 2, (pk - 1)/(p - 1) = 1. Then
|NonNorG(pk )|	2pk-1-(1+pk-2)/2
p^oo |ACG(pk) \ Small(pk)| < p^ 2(pk-1)/(p-1)
lim
pk^o 2(3pk-2 + 1)/2^pi
Thus as k > 3, the result follows. (The proof of [4, Theorem 3.5] concludes the above limit is 1 in all cases - hence the gap in that theorem when k = 2.)
S. Bhoumik et al.: On the automorphism groups of almost all circulants
513
For the remainder of the proof we suppose that k = 2 and p > 3. Substituting k = 2 into our formula for |NonNorG(n)|, we conclude that |NonNorG(p2)| = 2p-1.
If p = 2q +1 is a safe prime, q prime, then (a) is the unique subgroup of order p in Zp2, so any subgroup of Zp2 that contains -1 but does not contain a = p +1, must have even order not a multiple of p. Since Zp2 is cyclic of order p(p - 1) = 2pq, the group C of order 2q is the only such subgroup. Then if r G Nor(p2) \ Small(p2), then Aut(r) = C • (Zp2 )L. Now, C fixes 0 and since C has order 2q and is cyclic, the other orbits of C all have length precisely 2q (it is not hard to show that the only elements of Zp2 that fix anything but 0 are 1 and the elements of order p; this forces the orbit lengths of C to be the order of C), so there are (p2 - 1)/2q = 1 + p orbits of C other than {0}, and hence fewer than 21+p graphs in Nor(p2) are not in Small(p2) (the "fewer than" is due to the fact that some of these graphs are not normal, for example Kp2). Hence NonNor(p2)/(ACG(p2) \ Small(p2)) > 2p-1/(2p-1 + 2p+1) = 1/5.
Suppose now that p is not a safe prime. Then there exists b G Z*2 of order p - 1. Since p is not a safe prime, there exists 1 < r < s < (p - 1)/2 such that rs = (p - 1)/2. As every non-singleton orbit of (b) has length p - 1 (as shown for the orbits of C in the preceding paragraph), every nonsingleton orbit of (bs) has length (p - 1)/s. Then bs has s(p + 1) orbits not including {0} and since |bs| = 2r > 2, bs = ip2. We conclude that there are at least 2s(p+1) graphs of order p2 in ACG(p2) \ Small(p2). As there are 2p-1 non-normal circulant graphs of order p2 and s > \J(p - 1)/2,
|NonNorG(p2)| , 2p-1 lim -|- - < lim -= 0
p2-o |ACG(p2) \ Small(p2)| " p-o 2s(P+1) '
□
We now verify that Conjecture 3.3 does hold for circulant digraphs of order n, and also for circulant graphs of order n, for large families of integers. Note that, using Corollaries 2.10 and 2.17, we have for any n, |NonNor(n)| < |DW(n)m>4| + |GW(n)|.
Theorem 3.7. Let n be any odd integer such that 9 { n. Then almost all circulant digraphs of order n that are not DRRs are normal circulant digraphs.
Proof. A lower bound for | ACD(n) \ DRR(n) | is the number of circulant graphs of order n, which is 2(n-1)/2. We first find an upper bound for |DW(n)m>41. As n is odd, we have 2n/m < 2n/5. Also, n is an upper bound on the number of nontrivial divisors of n. By Corollary 2.18, |DW(n)m>4| < Em|„,m>4 22n/m < n • 22n/5.
By Corollary 2.12, we have |GW(n)| < log2 n • 2n/p+"/q-"/(pq)-1, where q is the smallest prime divisor of n and p is the smallest prime divisor of n/q. Since n is odd we have q > 3, and since 9 \ n we have p > 5. If q > 5 then 1/p + 1/q - 1/(pq) < 1/p + 1/q < 2/5, while if q = 3 then 1/p + 1/q - 1/(pq) = 2/(3p) + 1/3 < 7/15, so we always have 1/p + 1/q - 1/(pq) < 7/15. Note that if 9|n then p = q = 3, and this inequality is not true. Then
|NonNor(n)| „ n • 22n/5 + log2 n • 27n/15 „ lim ----——- lim -2- = 0
n-o |ACD(n) \ DRR(n)| " n^o	2C«-1)/2	'
□
402
Ars Math. Contemp. 7 (2014) 379-187
Theorem 3.8. Let n be any odd integer such that 9 { n, and n is not a safe prime or the square of a safe prime. Then almost all circulant graphs of order n that do not have automorphism group as small as possible are normal circulant graphs.
Proof. We need to show that
|NonNorG(n)|
iim -!--——-= 0,
ngT |ACG(n) \ Small(n)|
where T = {p,p2 : p is a safe prime} U {n : 9 | n} U {n : 2 | n}. This is true if n is a prime power by Theorem 3.6, so we assume there is a proper divisor m of n such that gcd(m, n/m) = 1. We also assume that n/m > m, and regard Zn as Zn/m x Zm in the natural way.
We begin by finding a lower bound for |ACG(n) \ Small(n)|. Let r G ACG(n) such that a G Aut(r) where a = (1, -1). Obviously a G (p, in), so r G Small(n). Straightforward computations will show that the orbits of (a, in) < Aut(r) are the sets
{(0,0)}, {(i, 0), (-i, 0)}, {(0, j), (0, -j)}, and {(i, j), (-i, j), (i, -j), H, -j)}, where i G Zn/m \ {0} and j G Zm \ {0}. We conclude that (a, in) has
n/m 1 m 1 n n/m m + 1 n + n/m + m + 1 n
1 + —--1---1----=--- > -
+ 2+ 2+	4	4	4
orbits. Hence |ACG(n) \ Small(n)| > 2n/4. Recall (by Corollaries 2.10 and 2.17)
|NonNorG(n)| < |DWG(n)m>4| + |GWG(n)|. By Corollary 2.18, we have that |DWG(n)m>4| < J2m|n m>4 2n/m+1. Since n is odd, m is odd, so m > 5, so n/m < n/5, and Em|n,m>4 2n/m+1 < n2n/s+1. By Corollary 2.13, we have that |GWG(n)| <
(log2 n)2n(p+q-1)/(2pq)+1/2, where p is the smallest divisor of n and q is the smallest divisor of n/p. As in the proof of Theorem 3.7, it is straightforward to show that since n is odd and not divisible by 9, (p + q - 1)/(pq) < 7/15. Hence
|NonNorG(n)| <	n2n/s+1 + (log2 n)27n/30+1/2
n^oc3,n0S |ACG(n) \ Small(n)| < n^<x>,n^s	2n/4
= 0.
□
4 Non-normal circulants
By Theorem 2.4, a circulant (di)graph that is not normal is generalized wreath or deleted wreath type. For each of these classes, we will now consider whether or not almost all non-normal circulant (di)graphs lie within this class. The short answer is "No" and is given by the following result.
Theorem 4.1. Let r be a circulant digraph of order pq, where p and q are primes and p, q > 5. Then
1. if q = p then
|GW(pq)| _	2p+q-1 - 2
|SDW(pq)| = 22p-1 + 22q-1 - 2P - 29 - 2,
S. Bhoumik et al.: On the automorphism groups of almost all circulants
515
2.	ifp is fixed, then	|GW(pq)|/|SDW(pq)| = 0,
3.	if q = p + c for some constant c > 2, then
|GW(pq)| 2c
i\TVVi//f/ii
lim
|SDW(pq)| (1 + 22c)'
4. if q = p then all non-normal circulants are generalized wreath products.
Proof. Note that for r G SDW(pq) we have m G {p, q} so m > 5 and r G NonNor(n).
(1):	We require exact counts of |GW(pq)| and of |SDW(pq)|. First, when n = pq a generalized wreath product will actually be a wreath product. For a wreath product digraph with p blocks of size q, there are q - 1 possible elements of S n (p), and p - 1 choices for the cosets of (p) to be in S. Hence there are 2p+q-2 wreath product circulant digraphs with p blocks of size q. Similarly, there are 2q+p-2 wreath product circulant digraphs with q blocks of size p. The only digraphs that have both of these properties are Kpq and its complement, each of which has been counted twice, so |GW(pq)| = 2 • 2p+q-2 - 2 =
2P+q-l - 2.
Now we count strictly deleted wreath products. As mentioned in the first sentence of the proof of Corollary 2.18, there are precisely 2 • 4p-1 digraphs whose automorphism group contains K x Sq, and 2 • 4q-1 digraphs whose automorphism group contains K' x Sp. Of the first set, 2 • 2p-1 are wreath products (those in which S n (rq + (p)) is chosen from {0, rq + (p)}, for every 1 < r < p - 1). Similarly, of the second set, 2 • 2q-1 are wreath products (those in which S n (rp + (q)) is chosen from {0, rp + (q)}, for every 1 < r < q - 1). Finally, notice that if a digraph is counted in both the first and second sets then its automorphism group must contain Sq x Sp. Consequently, the number of elements in S n (rp + (q)) is constant over r, as is the number of elements in S n (rq + (p)). Since we have already eliminated wreath products from our count, the first number must be 1 or p - 1, and the second must be 1 or q - 1. Furthermore, if the first number is 1 then we have p G S but p + q G S, so the second cannot be q - 1 (and the same holds if we exchange p and q), so there are only 2 choices for such digraphs: that in which all of the values are 1, which is KpDKq (where □ denotes the cartesian product), and its complement, in which all of the values are p - 1 or q - 1. Summing up, we see that |SDW(pq)| = 2 • 4p-1 + 2 • 4q-1 - 2 • 2p-1 - 2 • 2q-1 - 2. The result follows.
(2):	This follows from (1) by letting q tend to infinity.
(3):	Substituting q = p + c into (1) and letting p tend to infinity, we have
|GW(pq)|	2c-1 - 21-2p
lim ———7-,—tt = lim
|SDW(pq)|	2-1 + 22c-1 - 2-p - 2c-P - 21-2p '
Deleting the terms that tend to zero, we are left with
2c-1 2c
lim
p^ 2-1 +22c-1 1 + 22c'
as claimed.
(4): By Theorem 2.4, if r G NonNor(p2), then Aut(r) must either fall into category (1) or category (2). If it falls into category (1) then, since n = p2 and the are coprime, there can only be a single factor in the direct product, and since r G NonNor(n), the factor must be Sp2, so r g {Kp2, Kp2} C GW (p2). If it falls into category (2) then by Corollary 2.10, r G GW(p2).	□
402
Ars Math. Contemp. 7 (2014) 379-187
Notice that if we choose a constant c > 2 and define Tc = {pq : q = p+c} where p and q are prime, then as a consequence of Theorem 4.1(3), since 0 < 2c/(1 + 22c) < to, neither generalized wreath circulant digraphs nor strictly deleted circulant digraphs dominates in Tc. The recent breakthrough by Zhang [16] shows that the union of the first 70 million Tcs is infinite, and therefore that at least one of these sets is infinite. Essentially, we have shown that if n = pq is a product of two primes, then generalized wreath products dominate amongst circulant digraphs of order n if p = q (in fact there are no others); neither family dominates if p and q are "close" to each other, and strictly deleted wreath products dominate if one prime is much larger than the other.
We now give two infinite sets N and N2 of integers, each integer in both sets being divisible by three distinct primes. In Ni, almost all non-normal circulant digraphs are of strictly deleted wreath type (and N1 includes all of the square-free integers that are not divisible by 2 or 3). Meanwhile in N2, almost all non-normal circulant digraphs are generalized wreath circulant digraphs.
Theorem 4.2. Let N1 = {n G N| n is the product of at least three primes and q2 \ n where q > 5 is the smallest prime divisor of n}. Then,
lim |SDW(n)| =1 neNi.n^» |NonNor(n)|
Proof. By Corollaries 2.10 and 2.17, NonNor(n) C GW(n) U SDW(n)m>4, and by the definition of SDW(n), these sets are disjoint. Since q > 5 we also have m > 5 for any proper divisor m of n, so SDW(n) = SDW(n)m>4. Hence |NonNor(n)| = |GW(n)| + |SDW(n) |. We show that llmn^TO iN^n^I)| = 0, which implies the result.
The first sentence of the proof of Corollary 2.18 notes that for a proper divisor m of n, the number of digraphs r with H x Sm < Aut(r) for some 2-closed group H < Sn/m is precisely 2 • 4n/m-1. The maximum number of times that a specific circulant digraph r can be counted in ^^ 2 • 4n/m-1, is the number of divisors of n, d(n) < n. Thus
m|n
|DW(n)| > ^ 2 • 4n/m-1/n, and so by Lemma 2.16, |NonNor(n)| > ^ 2 • 4n/m-1/n.
m|n	m|n
By Corollary 2.12, we have that |GW(n)| < (log2 n)2n/p+n/q-n/(pq)-1, where q is the smallest prime divisor of n and p is the smallest prime divisor of n/q. Then
|GW(n)|	, (log2 n)2n/p+n/q-n/(pq)-1
llm —1—.,v	< llm v 62 7
|NonNor(n)| "	Hm\n 2 • 4n/m-1/n
(log2 n)2n/(q+2)+n/q < llm ^^—-—;——-
n^TO 4 • 4"/9-1/n
n log22 n
22n/(q(q+2)) .
llm
n^oo
Since q(q + 2) < n2/3 as q is the smallest prime factor of n, q2 \ n, and n has at least 3 prime factors, we have n/(q(q + 2)) > n1/3, so llmn^TO \N0nW0n(n)\ =0.	□
Theorem 4.3. For any natural number n, let pn be the smallest prime divisor of n, and qn the smallest prime divisor of n such that qn = pn and \ n. Let N2 = {n G N : pn >
S. Bhoumik et al.: On the automorphism groups of almost all circulants
517
| n, n has at least 3 distinct prime divisors, and qn > 2pn}. Then
lim |GW(n)| =1. |NonNor(n)|
Proof. Let p = pn. First notice that there are 2p-1+n/p-1 circulant digraphs that are wreath products r1 l r2 where r1 has order n/p and r2 has order p: 2p-1 choices for S n (n/p) and 2n/p-1 choices for which cosets of (n/p) are in S. All of these digraphs are distinct, so since by Lemma 3.4 these are all non-normal, we have |NonNor(n)| >
2P+n/p-2
By Corollary 2.18, for a proper divisor m > pn > 4 of n, the number of digraphs of deleted wreath type is at most 4n/m. Thus
|DW(n)| < ^ 4n/m.
m|n,gcd(m,n/m=1)
Let nt=1 p^ be the prime decomposition of n, and let p^fc = min jp"i}. Clearly 4n/ (p^k)
1<i<t
is the largest term in this sum, and there are at most d(n) (the number of divisors of n) terms in this sum. Thus |DW(n)| < d(n) • 4n/(pak).
Observe that if ak > 2, then p^fc > 5p > 2p since p > 5 is the smallest divisor of n. Also, if ak = 1, then by hypothesis pk > qn > 2p. Hence p^fc - 2p > 1 since both are integers. Now,
|DW(n)|	, d(n) • 4n/(Pkak)
lim —1-< lim v 7 , .—,-
|NonNor(n)| "	2P+n/P-2
4n
< lim
4n
< lim
n^to 2P+n/(PPkk)
Since n has at least 3 distinct prime divisors, there is some j such that pj = p,pk. Now p°jj > pkk by our choice of k, and p^ > pj > p, so since n/(ppkk) > p^, we have (n/(pp^fc))2 > ppkk. Hence ppkk < n2/3, so n/(pp^fc) > n1/3. So the above limit is at most
4n
lim -r-TTT = 0.
n^to 2P+n1/3
□
Acknowledgement: The authors are indebted to the anonymous referees whose suggestions improved the clarity of the proofs as well as the exposition in this manuscript.
References
[1]	B. Alspach, Point-symmetric graphs and digraphs of prime order and transitive permutation groups of prime degree, J. Combinatorial Theory Ser. B 15 (1973), 12-17.
[2]	L. Babai and C. D. Godsil, On the automorphism groups of almost all Cayley graphs, European J. Combin. 3 (1982), 9-15.
402
Ars Math. Contemp. 7 (2014) 379-187
[3]	P. J. Cameron, Michael Giudici, Gareth A. Jones, William M. Kantor, Mikhail H. Klin, Dragan Marusic and Lewis A. Nowitz, Transitive permutation groups without semiregular subgroups, J. London Math. Soc. 66 (2002), 325-333.
[4]	E. Dobson, Asymptotic automorphism groups of Cayley digraphs and graphs of abelian groups of prime-power order, Ars Math. Contemp. 3 (2010), 200-213.
[5]	E. Dobson and J. Morris, On automorphism groups of circulant digraphs of square-free order, Discrete Math 299 (2005), 79-98.
[6]	S. A. Evdokimov and I. N. Ponomarenko, Characterization of cyclotomic schemes and normal Schur rings over a cyclic group, Algebra iAnaliz 14 (2002), 11-55.
[7]	W. Imrich, Graphs with transitive abelian automorphism group, in Combinatorial theory and its applications, Coll. Math. Soc. Janos Bolyai 4, Balatonfured, Hungary (1969), 651-656.
[8]	K. H. Leung and S. H. Man, On Schur rings over cyclic groups. II, J. Algebra 183 (1996), 273-285.
[9]	K. H. Leung and S. H. Man, On Schur rings over cyclic groups, Israel J. Math. 106 (1998), 251-267.
[10]	C. H. Li, Permutation groups with a cyclic regular subgroup and arc transitive circulants, J. Algebraic Combin. 21 (2005), 131-136.
[11]	L. A. Nowitz, On the non-existence of graphs with transitive generalized dicyclic groups, J. Combinatorial Theory 4 (1968), 49-51.
[12]	H. Wielandt, Permutation groups through invariant relations and invariant functions, lectures given at The Ohio State University, Columbus, Ohio, 1969.
[13]	H. Wielandt, Finite permutation groups, Translated from the German by R. Bercov, Academic Press, New York, 1964.
[14]	H. Wielandt, Mathematische Werke/Mathematical works. Vol. 1, Walter de Gruyter & Co., Berlin, 1994, Group theory, With essays on some of Wielandt's works by G. Betsch, B. Hartley, I. M. Isaacs, O. H. Kegel and P. M. Neumann, Edited and with a preface by Bertram Huppert and Hans Schneider.
[15]	M.-Y. Xu, Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math. 182 (1998), 309-319, Graph theory (Lake Bled, 1995).
[16]	Y. Zhang, Bounded gaps between primes, Annals of Math. 179 (2014), 1121-1174.