Regular t-balanced Cayley maps

Marston Conder ^{∗}

Department of Mathematics, University of Auckland, Private Bag 92019,

Auckland, New Zealand conder@math.auckland.ac.nz

Robert Jajcay

Department of Mathematics and Computer Science, Indiana State University,

Terre Haute, IN 47809, U.S.A. jajcay@cayley.indstate.edu

Tom Tucker Mathematics Department, Colgate University,

Hamilton, NY 13346, U.S.A. Ttucker@mail.colgate.edu

April 16, 2003

Abstract

The concept of a t-balanced Cayley map is a natural generalization of the previously studied notions of balanced and anti-balanced Cayley maps (the terms coined by Širáň and Škoviera (1992)). We develop a general theory of t-balanced Cayley maps based on the use of skew-morphisms of groups (Jajcay and Širáň (2002)), and apply our results to the specific case of regular Cayley maps of abelian groups.

1 Introduction

A Cayley map M = CM(H, X, p) is a 2-cell embedding of a Cayley graph C(H, X) in an orientable surface determined by the rotation p of edges incident to a given vertex, with the additional property that the automorphism group Aut(M) contains a vertex-regular subgroup isomorphic to the underlying group H. This additional property makes Cayley maps naturally very symmetric, and puts them at the core of the study of regular maps – maps having the highest level of symmetry possible. A large proportion of classical examples of regular maps turn out to be regular Cayley maps (for more on this see [9] for instance). Prior to the 1990s, almost all known examples of regular Cayley maps were the so-called balanced Cayley maps, stemming from the existence of certain group automorphisms of the underlying group H. The first systematic study of non-balanced Cayley maps appeared with the introduction of anti-balanced Cayley maps in [11], and following that, a general theory of Cayley maps and of the related concept of a skew-morphism was developed in [9] and [4], respectively.

∗supported in part by the N.Z. Marsden Fund (grant no. UOA 124)

In this paper we apply the general theory of skew-morphisms to a class of Cayley maps that is a generalization of the classes studied by Širáň and Škoviera [10, 11], namely regular t-balanced Cayley maps.

The paper splits naturally into three parts. In the first part, we review and extend known results on skew-morphisms of finite groups. In the second part, we apply these to the study of regular t-balanced Cayley maps. The third part of our paper is devoted to the special case of t-balanced and other regular maps derived from abelian groups. Our ultimate goal is a possible classification of all such maps — part of an ongoing project to classify all abelian groups A which admit at least one regular Cayley map CM(A, X, p). Substantial first steps in this project are described in [2].

2 Preliminaries

Throughout this paper, we adopt the notation used in [4], and we will restrict our attention to simple Cayley graphs and Cayley maps with simple underlying graphs. In particular, a Cayley graph Γ = C(H, X) will be a graph based on a group H and a finite set X = {x_{1}, x_{2}, …, x_{k}} of elements in H which does not contain 1_{H}, contains no repeated elements, is closed under the operation of taking inverses, and generates all of H. The vertices of the Cayley graph Γ are the elements of H, and two vertices g and h are joined by an edge if and only if g = hx_{i} for some x_{i} ∈ X. The ordered pairs (h, x) for h ∈ H and x ∈ X are called the arcs or darts of Γ.

Let p be any cyclic permutation of the elements of X. Then the Cayley map M = CM(H, X, p) is the 2-cell embedding of the Cayley graph C(H, X) in an orientable surface for which the orientation-induced local ordering of the darts emanating from any vertex g ∈ H is always the same as the order of generators in X induced by p; that is, the neighbors of any vertex g are always spread counterclockwise around g in the order (gx, gp(x), gp^{2}(x), …, gp^{k−1}(x)). Since X is closed under taking inverses, for each x ∈ X there exists a non-negative integer i such that p^{i}(x) = x^{−1}. The function χ(x) : X → Z_{k} defined for each x ∈ X as the smallest i with this property is called the distribution of inverses of the Cayley map CM(H, X, p).

Based on the properties of this distribution of inverses, a Cayley map is said to be balanced if p(x^{−1}) = p(x)^{−1} for all x ∈ X, and is said to be anti-balanced if p(x^{−1}) = (p^{−1}(x))^{−1} for all x ∈ X. Another way of saying this is that in the balanced case, the local ordering of the neighbors of each vertex g is of the form (gx_{1}, gx_{2}, …, gx_{d}, gx_{1}^{−1}, gx_{2}^{−1}, …, gx_{d}^{−1}), while in the anti-balanced case this ordering is of the form (gx_{1}, gx_{2}, …, gx_{d}, gx_{d}^{−1}, …, gx_{2}^{−1}, gx_{1}^{−1}), with redundancies possible for involutory generators x_{i}.

An automorphism of a Cayley map M is a permutation of the set of darts of M which preserves the incidence relation of the vertices, edges and faces of the map. The full automorphism group of M, denoted by Aut(M), is the group of all automorphisms of M under the operation of composition. This group always acts semiregularly on the set of darts of M, that is, the stabilizer in Aut(M) of each arc of M is trivial. If the action of Aut(M) on the darts of M is transitive (and therefore regular), we say that the Cayley map M is a regular Cayley map. The reader interested in more information on regular maps is advised to consult [3], [1] or [9].

3 Skew-morphisms of finite groups

We will take particular advantage of a necessary and sufficient condition for a Cayley map M to be regular, based on the concept of a skew-morphism introduced in [4].

Let H be a finite group, φ : H → H a permutation of H of order k (in the full symmetric group Sym(H)), and π : H → Z_{k} a function from H to the cyclic group Z_{k}. We say that φ is a skew-morphism of H, with associated power function π, if φ(1_{H}) = 1_{H} and

φ(ab) = φ(a)φ^{π(a)}(b) for all a, b ∈ H  (1)

where φ^{π(a)}(b) is the image of b under φ applied π(a) times.

The relevance of skew-morphisms for regular Cayley maps is summed up in the following theorem:

Theorem 3.1 ([4]) A Cayley map CM(H, X, p) is regular if and only if there exists a skew-morphism φ of H such that φ(x) = p(x) for all x ∈ X.

Note that the skew-morphism φ may be seen as an extension of the function p, allowing the determination of the orientation of edges incident to an arbitrary vertex a ∈ H by the formula φ(a)^{−1}φ(ax) = p^{r}(x) = φ^{r}(x) for all x ∈ X, where r = π(a).

It follows from the above theorem that the regular Cayley maps of a group H are in one-to-one correspondence with the orbits of skew-morphisms of H that are closed under taking inverses and generate all of H. Hence knowing all the skew-morphisms of the finite group H allows one to construct a complete list of all regular Cayley maps on H. In what follows, we shall study the general properties of skew-morphisms of finite groups in order to facilitate the construction of such lists.

Let us assume from now on that CM(H, X, p) is a regular Cayley map, and φ is the corresponding skew-morphism (with restriction to X equal to p, and associated power function π). It is easy to see that π(1_{H}) = 1, and, unless φ = id_{H}, also π(a) ≠ 0 for all a in H (see [4]). The following lemma gives some of the most important algebraic properties of skew-morphisms (as presented in [4]).

Lemma 3.2 Let φ be a skew-morphism of a finite group H and let π be the power function of φ. Then the following hold:

(a) The set ker π = {a ∈ H | π(a) = 1} is a subgroup of H (b) π(g) = π(h) if and only if g and h belong to the same right coset of the subgroup

ker π in H

(c) The set Fixφ = {a ∈ H | φ(a) = a} is a subgroup of H

(d) π(ghg^{−1}) = 1 for all h ∈ ker π ∩ Fixφ and all g ∈ H

(e) The group ker π ∩ Fixφ is a normal subgroup of Fixφ.

A simple counting argument shows that in the case of a skew-morphism φ of a regular Cayley map, it is always true that | ker π| > 1, or equivalently, π(a) = 1 for at least one element a ≠ 1_{H} (see [4]). If π(a) = 1 for all a ∈ H, that is, if ker π = H, then φ is a group automorphism of H and the map is balanced (see [10]). Also if M is an anti-balanced regular Cayley map, then ker π is a subgroup of index 2 in H, with π(a) = |X| − 1 for all a ∉ ker π, and φ is an anti-automorphism of H (see [11]).

The valence of the Cayley map M (equal to the size k of the generating set X) is the true order of the skew-morphism φ, that is, |X| = |φ|. This is easy to see from the fact that the size of the full automorphism group of a regular Cayley map, which is equal to |H||φ|, is also equal to the number of darts of the map, namely |H||X|. It follows that the length of every orbit of φ must divide the valence k = |X|, and that every orbit of φ which is closed under taking inverses and which generates all of H must be of the same length k. Note that two (or more) such orbits may give rise to two (or more) regular Cayley maps, possibly non-isomorphic, but all of the same valence.

Another divisibility constraint on φ and π may be derived from a formula proved in [4], which allows the determination of π(x) for all x ∈ X from the distribution of inverses χ:

π(x) ≡ χ(φ(x)) − χ(x) + 1 mod |X|.  (2)

This yields

∑_{x∈X} π(x) ≡ ∑_{x∈X}(χ(φ(x)) − χ(x) + 1) = ∑_{x∈X} χ(φ(x)) − ∑_{x∈X} χ(x) + ∑_{x∈X} 1 = |X|,

since ∑_{x∈X} χ(φ(x)) = ∑_{x∈X} χ(x), and hence

∑_{x∈X} π(x) ≡ 0 mod |X|.  (3)

In other words, the sum of powers assigned to the elements in the generating set must be divisible by |X|, the valence of the map.

Even more surprisingly, this result extends to the neighbors of all the vertices g of the map M due to another formula from [4] (Lemma 3) proved for all g, h ∈ H :

π(gh) ≡ ∑_{j=0}^{π(g)−1} π(φ^{i}(h)) mod |φ|.  (4)

Using (4) one may deduce for any fixed g ∈ H that

∑_{x∈X} π(gx) ≡ ∑_{x∈X} ∑_{i=0}^{π(g)−1} π(φ^{i}(x)) ≡ ∑_{x∈X} π(g)π(x) ≡ π(g) ∑_{x∈X} π(x)

and hence that

∑_{x∈X} π(gx) ≡ π(g) 0 ≡ 0 mod |X|.  (5)

In other words, also the sum of powers assigned to the neighbors of any vertex of the map is divisible by the valence of the map.

In terms of vertex-colorings, what we have proved is that every Cayley graph C(H, X) which can be regularly embedded as a Cayley map admits a vertex-coloring with colors from {1, 2, …, |X| − 1} such that the sum of colors assigned to the neighbors of each vertex of the graph is divisible by |X|. Of course, any Cayley graph C(H, X) admits trivially a coloring that satisfies this property, by assigning color 1 to each vertex of the graph. If C(H, X) is embeddable as a non-balanced Cayley map, however, then the resulting coloring is not the trivial one.

Next, since X is the orbit of any x ∈ X under φ, formula (3) can also be written in the form

∑_{i=0}^{|X|−1} π(φ^{i}(x)) ≡ 0 mod |X|.

Once again, this extends to a more general statement about the distribution of powers in any orbit of φ. Let g and h be elements of H, and let O_{g} and O_{h} be the respective orbits of g and h under φ. Then

gh = φ^{|X|}(gh) = φ^{|X|}(g) φ^{m}(h) = g φ^{m}(h)

where m = ∑_{i=0}^{|X|−1} π(φ^{i}(g)), and so

∑_{i=0}^{|X|−1} π(φ^{i}(g)) ≡ 0 mod |O_{h}|.  (6)

Since the size of each orbit of φ divides |X|, this last equation can also be rewritten in the form

\frac{|X|}{|O_{g}|} ∑_{i=0}^{|O_{g}|−1} π(φ^{i}(g)) ≡ 0 mod |O_{h}|  (7)

for all g, h ∈ H.

Let us now turn our attention to the fixed elements of φ. First we show that the power π(f) of any fixed element f of φ must divide the power π(h) of any element h ∈ H, and must be invertible in Z_{|X|}. For if φ(f) = f then by (4) we observe that

π(hf) = ∑_{i=0}^{π(h)−1} π(φ^{i}(f)) = ∑_{i=0}^{π(h)−1} π(f) = π(h)π(f) in Z_{|X|} for every h ∈ H,

and replacing h by hf^{−1}, we find π(f) divides π(h) for every h in H.

This simple observation yields further that π restricted to Fixφ (the subgroup of elements of H fixed by φ) is a homomorphism from Fixφ into the multiplicative group of all invertible elements of the ring Z_{|X|}, and so Fixφ/(ker π ∩ Fixφ) is isomorphic to a subgroup of (Z_{|X|}^{×}, ·). This now implies, for instance, that if |H| and the value of the Euler ϕ function at |X| are relatively prime, then all the fixed elements of φ are assigned the π-value 1. Moreover, the set π(H) = {π(a) | a ∈ H} of all powers of elements of H is invariant under multiplication by π(f) for all f in Fixφ, as π(h)π(f) = π(hf) ∈ π(H) for all h ∈ H.

We have seen that the π-values of the fixed elements of φ are quite special. Next we shall argue that their position within the underlying Cayley graph is special too. Given a Cayley graph C(H, X), the vertex-set H can be partitioned into disjoint classes with respect to shortest distance from 1_{H} (equal to the length of the shortest expression for an element of H in terms of the generators from X). Now if f is a fixed element of φ, then the invertibility of π(f) in Z_{|X|} implies that the products 0π(f), 1π(f), 2π(f), …, (|X| − 1)π(f) are all distinct modulo |X|. Consequently, for any x ∈ X we find the |X| successive images of fx under φ, namely

fx, φ(fx) = fφ^{π(f)}(x), φ^{2}(fx) = fφ^{2π(f)}(x), …, φ^{|X|−1}(fx) = fφ^{(|X|−1)π(f)}(x),

are all distinct, and so the neighbors of f constitute a single orbit of φ (noting that no orbit of φ can be longer than |X|).

As skew-morphisms of Cayley maps always correspond to graph automorphisms of the underlying Cayley graph, we know that φ preserves distances from 1_{H}, and hence the elements of any orbit of φ must all be of the same distance from 1_{H}. In particular, the |X| neighbours of f all lie at the same distance from 1_{H}, and by connectedness it follows that unless f = 1_{H}, all these neighbors of f are closer than f to 1_{H}. Thus each fixed element f ≠ 1_{H} is at the ‘end’ of a path in C(H, X) from 1_{H}, and all of its neighbors belong to the class of vertices lying at distance 1 less than f from 1_{H}, so that in some sense f is ‘antipodal’ to 1_{H}. Accordingly, only the identity 1_{H} and the elements antipodal to 1_{H} in this way can be fixed elements of φ.

Finally we point out an important feature which skew-morphisms share with automorphisms of groups. Consider any subgroup K of H which is generated by the elements of an orbit O of a skew-morphism φ of H. As can be easily seen from the defining properties of skew-morphisms, the image of any product of elements of O under φ is again a product of elements of O, and as such, belongs to K = ⟨O⟩. This implies that φ must preserve the subgroup K setwise, and so just like group automorphisms, skew-morphisms preserve all subgroups generated by their orbits.

In general, the subgroup ker π = {a ∈ H | π(a) = 1} does not have to be preserved by φ. Nevertheless, the restriction of φ to ker π is a group isomorphism from ker π onto a (possibly different) subgroup of H, as φ(xy) = φ(x)φ^{π(x)}(y) = φ(x)φ(y) for all x, y ∈ ker π.

4 t-balanced Cayley maps

As mentioned in the Introduction, the first two types of regular Cayley maps studied were balanced and anti-balanced Cayley maps [10, 11]. The skew-morphism φ associated with a balanced regular Cayley map CM(H, X, p) is a group automorphism of the underlying group H which preserves the generating set (and its order), and its associated power function is simply the constant function 1 with ker π = H. On the other hand, the skew-morphism associated with an anti-balanced regular Cayley map is an anti-automorphism of H, and is in some way as close to being a group automorphism of H as possible (as the associated power function π assumes only two values in Z_{|X|}, namely 1 and −1, with ker π being a subgroup of index 2 in H and preserved by φ, and the restriction of φ to ker π being a group automorphism of ker π).

There is also another important characteristic shared by these two special types of skew-morphisms. Applying (2), one can easily see that π(x) = 1 for all x ∈ X in the balanced case, and π(x) = |X| − 1 for all x ∈ X in the anti-balanced case. In both cases, the values of π assigned to the generators in X are constant. This is certainly a very special situation, and one can reasonably expect that skew-morphisms whose associated power functions are constant on X will be both close to being group automorphisms, and helpful.

In this section, we investigate skew-morphisms with this promising feature. Before doing so, we note that the importance of Cayley maps with the sort of distribution of inverses arising from a constant power function has been recognized by several different groups of researchers [7, 8, 6, 13], the first use of the term “t-balanced” going back to a 1998 talk of M. Schultz. We believe, however, that our approach using skew-morphisms will bring a more general understanding of these maps.

Accordingly, let M = CM(H, X, p) be a regular Cayley map, with associated skew-morphism φ and power function π. We will say that M is a t-balanced Cayley map if π(x) = t for all x ∈ X. Note that this concept is simply a property of the distribution χ (from which π can be computed using formula (2)), and does not really require the map to be regular; nevertheless we shall assume the regularity of M throughout this section. Balanced and anti-balanced Cayley maps are 1-balanced and (|X|−1)-balanced respectively.

Now suppose M is t-balanced, where t > 1. Then at least one element of X, say x, is not an involution (see [10]), so that x and x^{−1} are distinct elements. By (4) we obtain

1 = π(1_{H}) = π(xx^{−1}) = ∑_{i=0}^{π(x)−1} π(φ^{i}(x^{−1})) = ∑_{i=0}^{t−1} t = t^{2},

and it follows that t must be a square root of 1 in Z_{|X|}. Moreover, we find

π(xy) = ∑_{i=0}^{π(x)−1} π(φ^{i}(y)) = ∑_{i=0}^{t−1} t = t^{2} = 1 for all x, y ∈ X,

and an easy induction shows that every word on X of even length belongs to ker π. Furthermore, as all the elements of X are assigned the same π-value, they all belong to the same right coset of ker π, and we conclude that ker π is a subgroup of index at most 2 in H, and that π assumes only two values, namely 1 and t.

We summarize our observations in the following lemma:

Lemma 4.1 Let M = CM(H, X, p) be a t-balanced regular Cayley map. Then either M is balanced (in which case t = 1), or otherwise t is a square root of 1 in Z_{|X|} (other than 1 itself), ker π is a subgroup of index 2 in H, the power function π assumes only the two values 1 and t, the skew-morphism φ preserves ker π setwise, and φ restricted to ker π is a group automorphism of ker π.

Proof. We have proved most of the statements of the lemma already above. If t > 1, then ker π must be a proper subgroup of H, and X must contain at least one noninvolutory element (for if X consists entirely of involutions, then the map is balanced). It remains to show that φ preserves ker π. To do this, recall that φ induces a graph automorphism of the underlying Cayley graph C(G, X), and therefore maps paths of even length to paths of even length; in particular, the image φ(x_{i_{1}}x_{i_{2}} … x_{i_{2j}}) of any element x_{i_{1}}x_{i_{2}} … x_{i_{2j}} ∈ ker π still belongs to ker π. Finally, as we have already pointed out, it is easy to see from (1) that φ restricted to ker π is a group isomorphism. □

Thus we see that t-balanced regular Cayley maps share almost all of the important characteristics of anti-balanced regular Cayley maps.

Next, let us focus on the form of the generating orbit X in the case t > 1, with the knowledge that all balanced Cayley maps stem from the relatively well-understood group automorphisms of their underlying group.

Let x be any element of X of order greater than 2. Since X lies entirely in a single right coset of ker π, we have X ⊆ (ker π)x, and so φ(x) = hx for some h ∈ ker π. Applying φ again, we find φ^{2}(x) = φ(φ(x)) = φ(hx) = φ(h)φ^{π(h)}(x) = φ(h)φ(x) = φ(h)hx, since h ∈ ker π. This extends easily by induction to all powers of φ, and so we find that the elements of X can be listed in the form

[ x, hx, φ(h)hx, φ^{2}(h)φ(h)hx, …, φ^{|X|−2}(h)φ^{|X|−3}(h) … φ^{2}(h)φ(h)hx]. (8)

In other words, the generating set X is completely determined by a non-involutory element x ∈ X, the element h = φ(x)x^{−1} ∈ ker π, and the φ-orbit of h. Note also that it is easy to see that the length |O_{h}| of the orbit of φ containing h must divide the length |X| of X (as was argued in general in the previous section).

To complete this section, let us consider the possible distributions of inverses for t-balanced Cayley maps. Rearranging formula (2) gives

χ(φ(x)) ≡ χ(x) + π(x) − 1 mod |X|  (9)

which expresses the distance from its inverse of the successor of x in X in terms of the distance of x from its inverse, for all x ∈ X. The latter formula allows for classification of all possible t-balanced distributions of inverses in X, as follows.

First, suppose t = 1. Substituting 1 for π(x) in (9) yields χ(φ(x)) = χ(x), and then by the definition of χ we obtain

φ(x)^{−1} = φ^{χ(φ(x))}(φ(x)) = φ^{χ(x)}(φ(x)) = φ(φ^{χ(x)}(a)) = φ(x^{−1}) for all x ∈ X.

Hence (as we already know) the map is balanced and the skew-morphism φ is a group automorphism of H.

Similarly, if t = |X|−1, then χ(φ(x)) = χ(x)−2 and we find φ(x^{−1}) = (φ^{−1}(x))^{−1} for all x ∈ X, and the map is anti-balanced, with φ an anti-automorphism of H.

Finally, if we suppose that t is a square root of 1 other than ±1, we obtain a distribution of inverses which is neither balanced nor anti-balanced. This time the formula (9) gives

φ(x)^{−1} = φ^{χ(x)+π(x)−1}(φ(x)) = φ^{χ(x)+t}(x) = φ^{t}(φ^{χ(x)}(x)) = φ^{t}(x^{−1})

and thus

φ(x)^{−1} = φ^{t}(x^{−1}) for all x ∈ X.  (10)

All possibilities for the distribution of inverses of a t-balanced Cayley map are summed up in the following lemma, which is the final result of this section.

Lemma 4.2 Let M = CM(H, X, p) be a t-balanced Cayley map. Then t may be assumed to satisfy 0 < t < |X|, and necessarily t^{2} ≡ 1 mod |X|. Furthermore, the distribution of inverses in p is uniquely determined (up to cyclic shift) and there exists a non-negative integer j <|X| such that j(t + 1) ≡ 0 mod |X| and the ordering p is of the form

(x, φ(x), φ^{2}(x), …, x^{−1}, …, (φ(x))^{−1}, …, (φ^{2}(x))^{−1}, …)

where the distance between φ^{i}(x) and (φ^{i}(x))^{−1} is j+i(t−1) mod |X|, for i = 1, 2, ….

Proof. We have already proved most of the lemma. To complete the proof, we suppose first that CM(H, X, p) is a regular Cayley map, with corresponding skew-morphism φ and constant power function π taking value π(a) = t for all a ∈ X.

If X consists entirely of involutions, then p has the form (x_{1}, x_{2}, x_{3}, x_{4}, …, x_{k}) and the map is balanced, so t = 1 and we can take j = 0.

If X contains non-involutory elements, then pick any one of them and name it x, and let j be the distance χ(x) from x to x^{−1} in the ordering p. Then 0 < j < |X|, and φ^{j}(x) = x^{−1}. Moreover, χ(φ(x)) = χ(x) + π(x) − 1 = j + t − 1 by formula (9), and by induction, we find χ(φ^{i}(x)) = j + i(t − 1) for all i > 0. It follows that the ordering of X is of the form described in the statement of the lemma.

To prove the identity j(t + 1) = 0 mod |X|, notice that χ(x) + χ(x^{−1}) is the length of the full cycle of p, namely |X|. As x^{−1} = φ^{χ(x)}(x) = φ^{j}(x), we thus find

0 ≡ χ(x) + χ(x^{−1}) = χ(x) + χ(φ^{j}(x)) = j + (j + j(t − 1)) = j(t + 1) mod |X| .

Finally, choosing a different non-involutory element x′ to start with may seem to lead to a different j′ = χ(x′), and a different series of equations χ(φ^{i}(x′)) = j′+i(t−1) for i > 0. Since x′ = φ^{i}(x) for some i > 0, however, it follows that j′ = χ(x′) = χ(φ^{i}(x)) = j + i(t − 1), and thus φ^{i}(x) = φ^{i′}(x′) implies χ(φ^{i}(x)) = χ(φ^{i′}(x′)), so that both choices for the starting elements lead to the same distribution of inverses (up to a cyclic shift with respect to placing x or x′ in the first position, respectively). We conclude that the lemma holds for all regular t-balanced Cayley maps.

In order to prove the result for all t-balanced Cayley maps, the above proof can be easily altered to avoid references to skew-morphisms. However, a much simpler argument follows from a result in [9], where the authors proved that there exists a regular Cayley map for each possible distribution of inverses χ. □

Observe that t^{2} ≡ 1 mod |X| if and only if |X| is a divisor of t^{2} − 1. Thus, it is natural to ask whether each pair of numbers t and |X| satisfying the condition t^{2} ≡ 1 mod |X| allows for a valid distribution of inverses of the type described in our lemma. It is not hard to see that this is indeed the case: by choosing j = t − 1, and taking advantage of the fact that t is relatively prime to t^{2} − 1 (for t > 1), one can show that each feasible pair (t, |X|) determines a valid t-balanced distribution of inverses. This does not necessarily imply that each feasible pair allows for the existence of a t-balanced regular Cayley map of valence |X|. Nevertheless, we will prove the latter to be true in Theorem 6.10.

The following two examples illustrate the use of Lemma 4.2.

Example 4.3 Let us consider the possible distribution of inverses in a 3-balanced regular Cayley map CM(H, X, p). In this case (t = 3), the size of the generating set X is uniquely determined by the congruence t^{2} ≡ 1 mod |X|: here 3^{2} ≡ 1 mod |X| so |X| divides 8, and as 3 = t < |X|, we find |X| is 4 or 8, but if |X| were 4 then we would obtain an anti-balanced map. Hence the only “true” 3-balanced regular Cayley maps are of valence 8.

Next let x be any given non-involutory element of X (the existence of which is guaranteed by the fact that our map is not balanced), and let j = χ(x). As 0 < j < 8 and j(t + 1) = 4j ≡ 0 mod 8, we see j must be one of 2, 4 or 6.

Let us first suppose j = 2. Applying Lemma 4.2, we can determine the distribution of inverses in p by the following computations modulo 8:

\begin{matrix}χ(φ^{1}(x)) = j + 1(t − 1) = 2 + 2 = 4, & χ(φ^{2}(x)) = j + 2(t − 1) = 2 + 4 = 6, \\ χ(φ^{3}(x)) = 2 + 6 = 0, & χ(φ^{4}(x)) = 2 + 8 = 2, \\ χ(φ^{5}(x)) = 2 + 10 = 4, & χ(φ^{6}(x)) = 2 + 12 = 6, \\ χ(φ^{7}(x)) = 2 + 14 = 0, & χ(φ^{8}(x)) = 2 + 16 = 2. \end{matrix}

This implies, for example, that in the cycle representing p the third and seventh elements to the right of x are involutions, and in fact p must be of the form

(x, y, x^{−1}, z, v, y^{−1}, v^{−1}, w)  (11)

with z and w being involutions.

If j = 4 instead, we start from an element whose distance from its inverse is 4. One such element in the above permutation is the element y, and an easy computation shows that the permutation resulting from starting with y (in the case j = 4) is of the form (y, x^{−1}, z, v, y^{−1}, v^{−1}, w, x), which is a cyclic shift of (11) above. Similarly, in the case j = 6 we obtain a cyclic shift of (11), equivalent also to its reverse.

We conclude that (11) gives the only possible distribution of inverses for a 3balanced Cayley map. Also for example, as the set of generators listed in p cannot involve repeated or trivial elements, and cyclic groups possess only one non-identity involution, we may further conclude that no cyclic group has a 3-balanced regular Cayley map.

Example 4.4 Let us consider (−3)-balanced regular Cayley maps. Taking t = −3 yields |X| = 8 again, and the only solution to the equation j(t + 1) = −2j ≡ 0 mod 8 is j = 4. This time the computations mod 8 yield

\begin{matrix}χ(φ^{1}(x)) = 0, & χ(φ^{2}(x)) = 4, & χ(φ^{3}(x)) = 0, & χ(φ^{4}(x)) = 4, \\ χ(φ^{5}(x)) = 0, & χ(φ^{6}(x)) = 4, & χ(φ^{7}(x)) = 0, & χ(φ^{8}(x)) = 4, \end{matrix}

so every second element is an involution, and the unique distribution of inverses for a (−3)-balanced Cayley map always corresponds to an 8-cycle of the form

p = (x, y, z, v, x^{−1}, w, z^{−1}, t),  (12)

with y, v, w, and t being involutions.

Note again here that the relatively large number of involutions needed for p provides us with a lower bound on the rank of the underlying Cayley group of the Cayley map. Indeed since the number of elements of order 2 in a finite abelian group H of rank r is at most 2^{r} − 1, and 4 such elements are required in (12), we find that the rank of any finite abelian group H having a (−3)-balanced regular Cayley map CM(H, X, p) must be at least 3.

5 Skew-morphisms of abelian groups

The final four sections of this paper are devoted to the special case of skew-morphisms of abelian groups. Let us start by dealing with some of their most significant features.

Lemma 5.1 If A is a finite abelian group, and φ is a skew-morphism of A, then

(i) φ preserves ker π setwise (that is, φ(ker π) = ker π),

(ii) the restriction of φ to ker π is a group automorphism of ker π, and

(iii) for each a in A, the power π(a) is congruent to 1 modulo the length of every non-trivial orbit of φ on ker π.

Proof. First, since A is abelian, φ(ab) = φ(ba) for all a, b ∈ A. In particular, if a ∈ ker π, then φ(ab) = φ(a)φ(b) while φ(ba) = φ(b)φ^{π(b)}(a) for all b ∈ A, and so

φ^{π(b)}(a) = φ(a) for all a ∈ ker π and b ∈ A.

It follows that either a is a fixed element of φ, or π(b) ≡ 1 modulo the length |O_{a}| of the orbit of a, whenever a ∈ ker π and b ∈ A. Hence the power π(b) associated with any element b ∈ A must be congruent to 1 modulo the length of any orbit of φ on non-fixed points of ker π.

Now let us apply this simple observation to the products of the form φ(a)b, for a ∈ ker π and b ∈ A. On one hand

φ(φ(a)b) = φ^{2}(a)φ^{π(φ(a))}(b),

while on the other hand

φ(φ(a)b) = φ(bφ(a)) = φ(b)φ^{π(b)}(φ(a)).

Clearly, the length of the orbit of a is the same as the length of the orbit of φ(a), and thus π(b) ≡ 1 modulo the length of the orbit of φ(a). This means, however, that φ^{π(b)}(φ(a)) = φ(φ(a)) = φ^{2}(a). Substituting this result in second of the two equations displayed above gives φ(b) = φ^{π(φ(a))}(b), for all b ∈ A whenever a ∈ ker π. Thus π(φ(a)) = 1 and so φ(a) ∈ ker π for all a ∈ ker π, that is, φ(ker π) = ker π. As also φ(ab) = φ(a)φ(b) for all a, b ∈ ker π, this proves the restriction φ↾_{ker π} is a group automorphism of ker π. □

Corollary 5.2 If φ is a t-balanced skew-morphism of the finite abelian group A, then so is every power φ^{i} of φ.

Proof. If a ∈ ker π, then an easy induction gives φ^{i}(ab) = φ^{i}(a)φ^{i}(b) for all b ∈ A, since φ preserves ker π. On the other hand, if a ∈ A \ ker π, then similarly φ^{i}(ab) = φ^{i}(a)φ^{it}(b) = φ^{i}(a)(φ^{i})^{t}(b) for all b ∈ A, since φ also preserves A \ ker π. □

In [4] it was proved that if M = CM(H, X, p) is a regular Cayley map of valence k, where k is smaller than the least index of any non-trivial subgroup of H, then M is necessarily balanced. At the other end of the spectrum, it is well-known that any regular Cayley map of a complete graph (with valence k equal to |H|−1) is also balanced; see [5]. An immediate consequence of Lemma 5.1 extends the second of these two results to regular Cayley maps of abelian groups.

Corollary 5.3 Let A be a finite abelian group, and let m be the smallest order of a non-trivial subgroup of A. Then any regular Cayley map CM(A, X, p) of valence strictly larger than |A|−m is balanced.

Proof. Suppose that M = CM(A, X, p) is regular, with associated skew-morphism φ and power function π, and further suppose |X| > |A| − m. Letting K = ker π, we observe that since X is an orbit of φ and φ preserves K, either X ⊆ K or X ∩K = ∅. As the latter case would imply |X| ≤ |A| − |K| ≤ |A| − m, it is impossible, hence X ⊆ K and therefore A = ⟨X⟩ ⊆ K, which forces K = A and so M is balanced. □

Another consequence of Lemma 5.1 is that φ permutes the cosets of ker π, for if b ∈ ker π and x ∈ A then φ(bx) = φ(b)φ(x), which belongs to the same coset of ker π as φ(x). Recall also that the sizes of the orbits of the group automorphism φ↾_{ker π} must all divide |X|. These two observations provide a lot of additional information about the orbits of skew-morphisms of Cayley maps of finite abelian groups.

Because we are mostly interested in non-balanced Cayley maps, we will suppose from now on that K = ker π is a proper subgroup of A, with X ∩ K = ∅.

If x ∈ X, and x and φ(x) belong to the same right coset of K, then as previously we have φ(x) = hx for some h ∈ K and find that φ^{2}(x) = φ(φ(x)) = φ(hx) = φ(h)φ^{π(h)}(x) = φ(h)φ(x) = φ(h)hx ∈ Kx, so that also φ^{2}(x) belongs to the same coset of K as x and φ(x). By induction, it follows that the whole φ-orbit of x is contained in the same coset of K, and hence all the elements in the orbit are assigned the same value of the power function π, making the map t-balanced for some suitable t. In particular, the orbit X has the same form (8) as encountered in the previous section, namely

(x, hx, φ(h)hx, φ^{2}(h)φ(h)hx, …, φ^{|X|−2}(h)φ^{|X|−3}(h) … φ^{2}(h)φ(h)hx).

Note here that x ∉ ker π while h ∈ ker π, and |X| − 1 must be the smallest positive integer k for which φ^{k}(h)φ^{k−1}(h) … φ^{2}(x)φ(x)h = 1_{A}.

On the other hand, suppose x ∈ X but x and φ(x) do not belong to the same coset of K. Then for each i we find the consecutive elements φ^{i}(x) and φ^{i+1}(x) of X must lie in different cosets of K (or otherwise we have the previous case). We claim, however, that there must be a positive integer ℓ (strictly between 1 and |X|) such that φ^{i}(x) and φ^{i+ℓ}(x) belong to the same coset of K for all i. To prove this, note that π(g) ≠ 0 for all g ∈ A (see [4]) and π(x) ≠ 1 for all x ∈ X (since X ∩ K = ∅), and hence the powers assigned to the elements of X all lie strictly between 1 and |X|. By the pigeonhole principle, X must contain at least two elements which are assigned the same power and hence belong to the same coset of K = ker π. So now let ℓ be the smallest positive integer such that for some i and j differing by ℓ, the elements φ^{i}(x) and φ^{j}(x) lie in the same coset of K. This means that φ^{j}(x) = hφ^{i}(x) for some h ∈ ker π, which implies further by induction that the successors of φ^{j}(x) must visit the same cosets and in exactly the same order as the successors of φ^{i}(x). Moreover, as φ permutes cosets of K in A, we see that φ permutes the cosets containing elements of the φ-orbit of x in a cycle of length ℓ. Hence the elements of X may be listed as

x, φ(x),  φ^{2}(x), …,  φ^{ℓ−1}(x),
h_{1}x, φ(h_{1})φ(x), φ^{2}(h_{1})φ^{2}(x), …, φ^{ℓ−1}(h_{1})φ^{ℓ−1}(x),
h_{2}x, φ(h_{2})φ(x), φ^{2}(h_{2})φ^{2}(x), …, φ^{ℓ−1}(h_{2})φ^{ℓ−1}(x),

… ,
h_{k}x, φ(h_{k})φ(x), φ^{2}(h_{k})φ^{2}(x), …, φ^{ℓ−1}(h_{k})φ^{ℓ−1}(x),
where h_{j} = φ^{ℓ}(h_{j−1})h_{1} for 1 < j ≤ k and φ^{ℓ}(h_{k})h_{1} = 1_{A}.  (13)

Note that at least the first two rows of this list are necessary, so that k ≥ 1, and that each h_{j} is a non-trivial element of H (for 1 ≤ j ≤ k), and that the ℓ elements x, φ(x), φ^{2}(x), …, φ^{ℓ−1}(x) belong to mutually distinct cosets of K = ker π.

These observations lead to the following theorem:

Theorem 5.4 Let M = CM(A, X, p) be a regular Cayley map of the finite abelian group A, with associated skew-morphism φ. If the order |A| of A is odd, then either M is balanced, or ker π is of index greater than 2 in A and X has the form given in (13). On the other hand, if |A| is even, then either M is t-balanced for some t, or ker π is of index greater than 2 in A and X has the form given in (13).

Proof. All that remains for us to prove is the assertion in the case where |A| is odd. In this case A has no subgroup of index 2, so the map M cannot be t-balanced for any t > 1, and hence is either balanced or of the form described by (13). □

6 t-balanced Cayley maps for abelian groups

Next we concentrate our attention on t-balanced regular Cayley maps for abelian groups, where the commutativity of multiplication implies additional results which are not always true for t-balanced Cayley maps of other types of groups.

As we have already proved in Lemma 5.1, when the group is abelian the values of the power function π must be congruent to 1 modulo the length of each of non-trivial orbit of φ on ker π, and therefore t must be congruent to 1 modulo the order of the restriction φ↾_{ker π}, as well as being a square root of 1 modulo X (by Lemma 4.1).

Recall also that when t > 1, the elements of X are completely determined by a non-involutory element x ∈ X, the element h = φ(x)x^{−1} ∈ ker π, and the φ-orbit of h, as described in (8). In particular, as X is closed under inverses, we must have x^{−1} = φ^{j}(h)φ^{j−1}(h) … φ(h)hx for some j, in which case

x^{2} = (φ^{j}(h)φ^{j−1}(h) … φ(h)h)^{−1} ∈ ⟨ h, φ(h), φ^{2}(h), …, φ^{j}(h) ⟩ .

Since X generates A, which is abelian, and x is the only element outside ker π used in the expressions for the elements of X in (8), we conclude that

A = L ∪ Lx where L = ⟨ h, φ(h), φ^{2}(h), …, φ^{j}(h) ⟩ ,

from which it follows that ker π = L.

Furthermore, if we assume t > 1, we know that t must be congruent to 1 modulo the length of any non-trivial orbit of φ on ker π. Considering, in particular, the orbit O_{h} of h, we know that |O_{h}| divides |X| and t ≡ 1 mod |O_{h}|. Since t > 1, it follows that |X| > |O_{h}|, and therefore |X| = k|O_{h}| for some integer k > 1. If, however, h were of order greater than 2 and O_{h} contained h^{−1} ≠ h, then O_{h}, being an orbit of a group automorphism φ| ker π, would have to be closed under inverses, which would imply

φ^{|O_{h}|−1}(h)φ^{|O_{h}|−2}(h) … φ(h)h = 1_{A}.

Consequently, we would obtain

φ^{|O_{h}|−1}(h)φ^{|O_{h}|−2}(h) … φ(h)hx = x,

which would yield the identity |O_{h}| = |X|. It follows that in the case where t > 1 and h is a non-involution, the orbit O_{h} contains the inverse of none of its elements (which are, of course, all of the same order).

On the other hand, if t > 1 and h has order 2, then all the elements of O_{h} are involutions, the product of which cannot possibly be equal to 1_{H} as that would again imply |O_{h}| = |X|. Hence in this case, ker π, being an abelian group generated by involutions, must be an elementary abelian 2-group, isomorphic to Z_{2}^{s} for some s ≤ |O_{h}|, and the whole group A is then isomorphic to a Z_{2}-extension of Z_{2}^{s}.

In the case where t = |X| − 1, we get an additional result for ker π. Here the congruence t ≡ 1 mod |O_{h}| implies that |X| ≡ 2 mod |O_{h}|, but then since |X| is also divisible by |O_{h}|, we find 0 ≡ 2 mod |O_{h}|, and conclude that |O_{h}| is 1 or 2. In turn this implies that ker π (being generated by O_{h}) is an abelian group of rank 1 or 2.

In the case where the orbit O_{h} is of size 1 (that is, when h is a fixed point of φ), our previous observation may be reversed, as follows. Suppose that φ(h) = h. Then the φ-ordering of X has the form

[ x, hx, h^{2}x, h^{3}x, …, h^{|X|−1}x],

where h is an element of ker π of order |X| ≥ 2. In particular, x^{−1} = h^{j}x for some j. But now for any i we have (h^{i}x)^{−1} = x^{−1}h^{−i} = h^{j}xh^{−i} = h^{j−i}x (as A is abelian), so

φ((h^{i}x)^{−1}) = φ(h^{j−i}x) = φ(h^{j−i})φ(x) = h^{j−i+1}x = (h^{i−1}x)^{−1} = (φ^{−1}(h^{i}x))^{−1}

for all i, which shows that the map is anti-balanced. Hence if h is fixed by φ, then ker π is cyclic (generated by the element h = φ(x)x^{−1}), the map is anti-balanced, and φ is an anti-automorphism of A. Many easy examples of this situation can be constructed, as below.

Example 6.1 Let A be the cyclic group Z_{8} under addition mod 8, and let K be the cyclic subgroup generated by 2, of order 4. Take x = 1 and suppose φ(1) = 3 (so that h = 2) while φ↾_{K}= id_{K}. Then φ = (0)(2)(4)(6)(1, 3, 5, 7), giving an antiautomorphism of Z_{8}, and the resulting Cayley map CM(Z_{8}, {1, 3, 5, 7}, φ) is antibalanced.

The observations we have made following Theorem 5.4 may be summarized in the following:

Lemma 6.2 Let M = CM(A, X, p) be a t-balanced regular Cayley map of a finite abelian group A, where t > 1, and let φ be the associated skew-morphism, π the power function, x a non-involutory element of X, and h = φ(x)x^{−1}. Then each of the following holds:

(a) x^{2} ∈ ⟨ h, φ(h), φ^{2}(h), …, φ^{j}(h) ⟩ for some j;

(b) ker π = ⟨h, φ(h), φ^{2}(h), …, φ^{j}(h)⟩, where j is as in (a), and so ker π is generated by the φ-orbit of h;

(c) the length |X| of the φ-orbit X is a proper multiple of the length |O_{h}| of the orbit of φ↾_{ker π} containing h;

(d) π(x)^{2} ≡ 1 mod |X|;

(e) π(x) ≡ 1 modulo the order of φ↾_{ker π};

(f) if h has order 2, then ker π ≅ Z_{2}^{s} for some s ≤ |O_{h}|;

(g) if t = |X| − 1, then |O_{h}| ≤ 2, and ker π is either cyclic or of rank 2;

(h) if |O_{h}| = 1, then φ is an anti-automorphism of A, and ker π is cyclic.

Part (g) of the above result can be further extended to obtain a general upper bound on the rank of the group A itself.

Theorem 6.3 If the finite abelian group A has a t-balanced regular Cayley map CM(A, X, p), with t > 1, then the rank of A is bounded above by min(t−1, |X|−t+1).

Proof. Recall that when t > 1, we know that φ^{t−1} acts trivially on K = ker π, and that the elements of X are completely determined by a single element x ∈ X and the φorbit of the element h = φ(x)x^{−1} ∈ ker π. Letting c = φ^{t−2}(h)φ^{t−3}(h) … φ^{2}(h)φ(h)h, we note that the terms of this product are permuted by φ, and therefore φ(c) = c. It follows that the elements of X may be listed as follows:

x, hx, φ(h)hx, φ^{2}(h)φ(h)hx, …, φ^{t−3}(h)φ^{t−4}(h) … φ^{2}(h)φ(h)hx,

cx, chx, cφ(h)hx, cφ^{2}(h)φ(h)hx, …, cφ^{t−3}(h)φ^{t−4}(h) … φ^{2}(h)φ(h)hx, c^{2}x, c^{2}hx, c^{2}φ(h)hx, c^{2}φ^{2}(h)φ(h)hx, …, c^{2}φ^{t−3}(h)φ^{t−4}(h) … φ^{2}(h)φ(h)hx, c^{3}x, c^{2}hx, c^{2}φ(h)hx, c^{2}φ^{2}(h)φ(h)hx, …, and so on.

In particular, it follows that A = ⟨X⟩ = ⟨x, c, h, φ(h), φ^{2}, …, φ^{t−4}(h), φ^{t−3}(h)⟩, and thus A has rank at most t.

But further, if x is an involution then

1 = φ(1) = φ(x^{2}) = φ(xx) = φ(x)φ^{t}(x) = (hx)(chx) = c(hx)^{2}

and so c = (hx)^{−2}, which reduces the rank of A to at most t − 1.

On the other hand, if x is not an involution, then since x^{−1} ∈ X we find that either x^{−1} = c^{j}x for some j, in which case

1 = φ(xc^{j}x) = φ(x)φ^{t}(c^{j}x) = φ(x)φ^{t}(c^{j})φ^{t}(x) = (hx)(c^{j})(chx) = ch^{2}xc^{j}x = ch^{2}

and therefore c = h^{−2}, or otherwise x^{−1} = c^{j}φ^{k}(h)φ^{k−1}(h) … φ^{2}(h)φ(h)hx for some j and some k with 1 ≤ k ≤ t−3, in which case

φ^{k}(h) ∈ ⟨x, c, h, φ(h), φ^{2}(h), …, φ^{k−2}(h), φ^{k−1}(h)⟩,

and in both cases the rank of A reduces to at most t − 1.

Next let s = |X|−t. Because φ has order |X| and φ^{t−1} acts trivially on K = ker π, we see that also φ^{s+1} acts trivially on K. Adopting a similar approach to the one above, we may take c′ to be the product φ^{s}(h)φ^{s−1}(h) … φ^{2}(h)φ(h)h, and find that φ(c) = c′ and that A = ⟨x, c′, h, φ(h), φ^{2}, …, φ^{s−2}(h), φ^{s−1}(h)⟩, of rank at most s + 2. Moreover, the same arguments as above show that either c′ = h^{−2} or otherwise φ^{k}(h) ∈ ⟨x, c′, h, φ(h), φ^{2}, …, φ^{k−2}(h), φ^{k−1}(h)⟩ for some k with 1 ≤ k ≤ s − 2, and hence the rank of A reduces to at most s + 1. This proves the theorem. □

Hence, for example, if t = 3 then A has rank at most 2, while if t = |X| − 3 then A has rank at most 4. Before proceeding with some more examples, we should note that if t = ±2 then 3 = t^{2} − 1 ≡ 0 (mod |X|), so |X| = 3 and then t = 1 or |X|−1, which are cases covered previously.

Example 6.4 Let us construct a regular 3-balanced abelian Cayley map CM(A, X, p). Except in degenerate cases, when t = 3 the rank of A is at least 2 (as shown in Example 4.3), and hence exactly 2 (by Theorem 6.3). Also |X| = 8, and p must have the form (11). Furthermore, A is a 2-extension of ker π, and the elements in (11) must all belong to A \ ker π. It follows that |A| ≥ 16. If X consisted of all the elements in A \ ker π, it would certainly be closed under inverses and generate all of A. The most obvious possibility to consider is therefore one in which A = Z_{8} × Z_{2}, with ker π = {(i, 0) | i ∈ Z_{8}}, and X = {(i, 1) | i ∈ Z_{8}}. We will also take x = (1, 1) in X.

The restriction of the potential skew-morphism φ to ker π must be an isomorphism of ker π, with t = 3 congruent to 1 modulo its order, hence φ↾_{ker π} has order 1 or 2. If φ↾_{ker π} is trivial then φ is an anti-automorphism (by Lemma 6.2(h)), so its order must be 2. Now there are three automorphisms of Z_{8} × {0} of order 2, taking (1, 0) to (3, 0), (5, 0) and (7, 0) respectively, but if we want χ(x) = 2 as required to achieve the distribution of inverses given by (11) in Example 4.3, then we need x^{−1} = x+h+φ(h), so that h + φ(h) = x^{−1} − x = (7, 0) − (1, 0) = (6, 0). Hence we may choose h = (1, 0) and the automorphism of Z_{8} × {0} taking (1, 0) to (5, 0). This gives a 3-balanced skew-morphism for Z_{8} × Z_{2} which permutes the elements of a generating set in a cycle

p = ( (1, 1), (2, 1), (7, 1), (0, 1), (5, 1), (6, 1), (3, 1), (4, 1) ).

Note also that all regular 3-balanced abelian Cayley maps can be constructed in this manner: the underlying group A must be a rank 2 abelian group with factors of even order and having a subgroup of index 2 that admits an automorphism of order 2 whose orbit can be used to produce the permutation p of the form (11).

Example 6.5 We give an example of a regular (−3)-balanced abelian Cayley map CM(A, X, p). Here we require from Example 4.4 and Theorem 6.3 that |X| = 8, and p takes the form (12), and A must have rank 3 or 4.

Let A = Z_{4} × Z_{2}^{3}, and define the skew-morphism φ on A with kernel K = ker π = {(i, j, k, 0) | i ∈ Z_{4}, j, k ∈ Z_{2}} by setting φ(i, j, k, 0) = (i + 2k, i + k, j, 0) and φ(i, j, k, 1) = (i + 2k − 1, i + k + 1, j, 1) for all i ∈ Z_{4} and j, k ∈ Z_{2}. Note that φ restricts to an automorphism of K taking (1, 0, 0, 0) to (1, 1, 0, 0), (0, 1, 0, 0) to (0, 0, 1, 0), and (0, 0, 1, 0) to (2, 1, 0, 0), and that the cycle of φ containing the element x = (0, 0, 0, 1) under φ is given by p = ( (0, 0, 0, 1), (3, 1, 0, 1), (2, 0, 1, 1), (3, 0, 0, 1), (2, 0, 0, 1), (1, 1, 0, 1), (0, 0, 1, 1), (1, 0, 0, 1) ). This cycle has the required form (12), and its elements generate A, so φ is a (−3)-balanced skew-morphism for A.

The examples presented above suggest that the upper bound given in Theorem 6.3 could be sharp. As we shall prove next, this is indeed the case. The following lemma asserts that automorphisms of the kind used in the above examples exist in general.

Lemma 6.6 For any positive integers m and n of equal parity, there exists an automorphism θ of the abelian group B = Z_{2n} × (Z_{2})^{m−2} such that θ has order m, the orbit under θ of some element b (of order 2n) generates B, and the product b θ(b) θ^{2}(b) … θ^{m−1}(b) equals b^{m+n}.

Proof. Choose generators b_{1}, b_{2}, …, b_{m−1} for B such that b_{1} has order 2n while all the other b_{i} all have order 2, and define θ by setting θ(b_{1}) = b_{1}b_{2}, θ(b_{i}) = b_{i+1} for 2 ≤ i ≤ m−2, and

θ(b_{m−1}) = \{ \begin{matrix}b_{1}^{n}b_{2}b_{4} … b_{m−4}b_{m−2} & if m is even \\ b_{1}^{n}b_{3}b_{5} … b_{m−4}b_{m−2} & if m is odd. \end{matrix}

Then clearly the orbit of b_{1} under θ generates B. Next, θ^{i} takes b_{1} to b_{1}b_{2} … b_{i}b_{i+1} for 0 ≤ i ≤ m−2, and θ^{m−1} takes b_{1} to b_{1}^{n+1}b_{3}b_{5} … b_{m−3}b_{m−1} if m is even, or to b_{1}^{n+1}b_{2}b_{4} … b_{m−3}b_{m−1} if m is odd, and therefore θ^{m} takes b_{1} to b_{1}^{2n+1}b_{2}^{n+2} if m is even, or to b_{1}^{2n+1}b_{2}^{n+1} if m is odd. Because b_{1} has order 2n, and m and n have the same parity, it follows that θ^{m}(b_{1}) = b_{1} in both cases. In particular, θ has order m. Finally if m is even then

b_{1}θ(b_{1})θ^{2}(b_{1}) … θ^{m−1}(b_{1}) = b_{1}^{m+n}b_{2}^{m−2}b_{3}^{m−2}b_{4}^{m−4}b_{5}^{m−4} … b_{m−4}^{4}b_{m−3}^{4}b_{m−2}^{2}b_{m−1}^{2} = b_{1}^{m+n},

while if m is odd then

b_{1}θ(b_{1})θ^{2}(b_{1}) … θ^{m−1}(b_{1}) = b_{1}^{m+n}b_{2}^{m−1}b_{3}^{m−3}b_{4}^{m−3} … b_{m−2}^{2}b_{m−1}^{2} = b_{1}^{m+n},

so in both cases the product of the distinct images of b_{1} under powers of θ is b_{1}^{m+n}. □

We can now prove the following theorem, which provides for each t ≥ 3 examples of regular Cayley maps for which the rank bound from Theorem 6.3 on the underlying group is met.

Theorem 6.7 For every positive integer t ≥ 3 there exists a t-balanced regular Cayley map for the abelian group Z_{2(t+1)} × (Z_{2})^{t−2} of rank t − 1, and a (−t)-balanced regular Cayley map for the abelian group Z_{2(t−1)} × (Z_{2})^{t} of rank t + 1. In both cases, the valence of the map is equal to t^{2} − 1.

Proof. Take m = t − 1 and n = t + 1 in the first case, and m = t + 1 and n = t − 1 in the second case, and let A = Z_{2n} × (Z_{2})^{m−1}. Note that m + n = 2t in both cases. Choose generators b_{1}, b_{2}, …, b_{m} for A such that b_{1} has order 2n while the other b_{i} have order 2, let B be the subgroup generated by b_{1}, b_{2}, …, b_{m−1}, and define θ as in the proof of Lemma 6.6. Now extend the definition of this automorphism θ to a skew morphism φ of A by setting φ(a) = θ(a) and φ(ab_{m}) = θ(a)b_{1}^{−1}b_{2}b_{m} for all a ∈ B.

Let x = b_{m}, and observe that in both cases φ(b_{1}) = b_{1}b_{2}, so φ(b_{1}^{2}) = b_{1}^{2}, and also φ(x) = b_{1}^{−1}b_{2}x, so that φ(b_{1}x) = b_{1}b_{2}b_{1}^{−1}b_{2}x = x, and therefore φ^{−1}(x) = b_{1}x. In particular, it follows that φ^{−2}(x) = θ^{−1}(b_{1})b_{1}x and φ^{−3}(x) = θ^{−2}(b_{1})θ^{−1}(b_{1})b_{1}x, and so on, so that

φ^{−m}(x) = θ^{−(m−1)}(b_{1}) … θ^{−1}(b_{1})b_{1}x = θ(b_{1})θ^{2}(b_{1}) … θ^{m−1}(b_{1})b_{1}x = b_{1}^{m+n}x = b_{1}^{2t}x.

In the first case, this tells us that φ^{−(t−1)}(x) = b_{1}^{2t}x = b_{1}^{−2}x, therefore φ^{t}(b_{1}^{−2}x) = φ(φ^{(t−1)}(b_{1}^{−2}x)) = φ(x), and it follows that

φ^{t}(x) = φ^{t}(b_{1}^{2}b_{1}^{−2}x) = φ^{t}(b_{1}^{2})φ^{t}(b_{1}^{−2}x) = b_{1}^{2}φ(x) = b_{1}^{2}b_{1}^{−1}b_{2}x = b_{1}b_{2}x = φ(x)^{−1},

so that the skew-morphism φ is t-balanced, as required.

In the second case, φ^{−(t+1)}(x) = b_{1}^{2t}x = b_{1}^{2}x, and hence

φ^{−t}(x) = φ(φ^{−(t+1)}(x)) = φ(b_{1}^{2}x) = φ(b_{1}^{2})φ(x) = b_{1}^{2}b_{1}^{−1}b_{2}x = b_{1}b_{2}x = φ(x)^{−1},

so that φ is (−t)-balanced in this case.

Finally, it is easy to see that the valence |X| (which equals the length of the orbit of x under φ ) in each case is the product of the order m of φ↾_{B}= θ and the order of the element b_{1}^{m+n} = b_{1}^{2t}, which is n since t is coprime to n = t ± 1. Hence in each case we have |X| = mn = t^{2} − 1. □

To conclude this section, we revisit the length of X with respect to the length of the orbit O_{h} containing h, under the additional assumption that h is not fixed by φ. We already know that |X| is a proper multiple of |O_{h}|, and as h is not fixed by φ, also |O_{h}| > 1. Thus, |X| ≥ 2|O_{h}| ≥ 4. Denoting |O_{h}| by ℓ, we find the first ℓ elements of the φ-ordering of X are

x, hx, φ(h)hx, φ^{2}(h)φ(h)hx, …, φ^{ℓ−2}(h)φ^{ℓ−3}(h) … φ^{2}(h)φ(h)hx,

and then these are followed by subsequences of length ℓ each of the form

w^{i}, hw^{i}, φ(h)hw^{i}, φ^{2}(h)φ(h)hw^{i}, …, φ^{ℓ−2}(h)φ^{ℓ−3}(h) … φ^{2}(h)φ(h)hw^{i},

where w = φ^{ℓ−1}(h)φ^{ℓ−2}(h) … φ^{2}(h)φ(h)h is an element of ker π of order k = |X|/ℓ.

In addition, if we want φ to be a skew-morphism of A which is neither a group automorphism nor an anti-automorphism of A, then |X| must satisfy the condition that Z_{|X|} contains a square root t of 1 different from ±1, and hence, for example, |X| ≠ 4, 5, 6, 7, 9, 10, 11, 13, …. The possibilities for n = |X| are given precisely by case (c) of the following lemma, which can obtained from properties of the Euler ϕ-function and a simple application of the Chinese Remainder Theorem:

Lemma 6.8 For any positive integer k, the number of square roots of 1 in Z_{k} is

(a) 1 if k = 2,

(b) 2 if k = 4 or k = p^{j} or 2p^{j} where p is an odd prime, j > 0, and

(c) more than 2 if k = 2^{j} where j ≥ 3, or k = 2^{j}s where j ≥ 2 and s > 1 is odd, or k is divisible by two distinct odd primes.

As an illustration we give the following:

Example 6.9 In Z_{12} there are two square roots of 1 other than 1 and −1, namely 5 and 7. Moreover, there exist regular 5- and 7-balanced Cayley maps for numerous finite abelian groups with valence 12. One such map arises from a skew-morphism φ of the cyclic group C_{30}, defined in terms of a multiplicative generator x for C_{30} by

φ(x^{j}) = \{ \begin{matrix}x^{7j} & if j is even \\ x^{7j+10} & if j is odd. \end{matrix}

In this case φ induces the group automorphism h ↦ h^{7} on the kernel of the associated power function π, of index 2 in C_{30}, the generating-set X may be taken as { x^{1}, x^{17}, x^{9}, x^{13}, x^{11}, x^{27}, x^{19}, x^{23}, x^{21}, x^{7}, x^{29}, x^{3} }, with π(y) = 5 for all y ∉ ker π.

In fact, we can show that a t-balanced regular Cayley map of valence |X| exists for every feasible pair (t, |X|), as promised in the comments following Lemma 4.2.

Theorem 6.10 Let t and v be positive integers such that t < v and t^{2} ≡ 1 mod v. Then there exists a t-balanced regular Cayley map CM(A, X, p) of valence |X| = v.

Proof. To begin with, suppose t = 1. In this case take A = Z_{2}^{v} and p = (e_{1}, e_{2}, …, e_{v}), where X = {e_{1}, e_{2}, …, e_{v}} is the standard basis for Z_{2}^{v}. The Cayley map CM(A, X, p) is then a regular 1-balanced Cayley map of valence v, and this construction is valid for every v > 1. Similarly if t ≥ 2 and v = t + 1, we may take A = Z_{2} × Z_{v}, and X = {(1, 0), (1, 1), (1, 2), …, (1, v − 1)}, and p = ( (1, 0), (1, 1), (1, 2), …, (1, v − 1) ), and then CM(A, X, p) is a regular t-balanced Cayley map of valence v. Also recall that if t = v − 2, then 1 ≡ t^{2} ≡ 4 mod v and therefore v = 3 and t = 1. Hence for the remainder of the proof we may suppose that 3 ≤ t ≤ v − 3.

Now let M be the t-balanced Cayley map of valence t^{2} − 1 that was given in the proof of Theorem 6.7 for the group A = Z_{2(t+1)} × (Z_{2})^{t−2}, let φ be the corresponding skew-morphism of A, and let y be the element φ(x) = b_{1}^{−1}b_{2}x = b_{1}^{−1}b_{2}b_{t−1}. Then the orbit of y under φ is X, which is of length t^{2}−1, is closed under inverses and generates A, and furthermore, as φ^{t−1}(y) = φ^{t}(x) = (φ(x))^{−1}, the distance χ(y) between y and y^{−1} in the cycle p representing the action of φ on this orbit is t − 1.

Next, as t^{2} ≡ 1 mod v we know that t^{2} − 1 = kv for some k, and by Corollary 5.2, the function φ^{k} is also a t-balanced skew-morphism of A. As k divides the length of the φ-orbit X, the skew-morphism φ^{k} has exactly k orbits on X, each of length v. We claim that at least one of these new orbits is closed under inverses, namely the orbit (z, φ^{k}(z), φ^{2k}(z), …, φ^{(v−1)k}(z)) containing the element z = φ^{k−1}(y) = φ^{k}(x). To see this, recall that the distance of the latter element z from its inverse in the original orbit of φ may be determined as follows:

χ(z) = χ(φ^{k−1}(y)) = χ(y) + (k − 1)(π(y) − 1) = t − 1 + (k − 1)(t − 1) = k(t − 1).

It follows that z^{−1} = φ^{k(t−1)}(z), and hence the inverse of z belongs to the same orbit of φ^{k} as z. Moreover, for any i we have

χ(φ^{ki}(z)) = χ(φ^{ki+k−1}(y)) = χ(y) + (ki + k − 1)(π(y) − 1) = k(i + 1)(t − 1)

and so (φ^{ki}(z))^{−1} = φ^{k(i+1)(t−1)}(z), which implies that the orbit X′ of z under the action of the t-balanced skew-morphism φ^{k} is closed under inverses.

Finally, recall that skew-morphisms preserve subgroups generated by their orbits (as noted at the end of Section 3). Thus φ^{k} is a t-balanced skew-morphism of the subgroup A′ = ⟨z, φ^{k}(z), φ^{2k}(z), …, φ^{(v−1)k}(z)⟩, and the Cayley map CM(A′, X′, (φ^{k})↾_{A′}) is a regular t-balanced Cayley map of valence v. □

7 Regular anti-balanced maps for abelian groups

We saw in the previous section that 3-balanced regular abelian Cayley maps are all of the same form. The results of the previous section can also be applied to obtain a complete classification in the anti-balanced case t = |X| − 1.

First consider the following three families, each involving an anti-automorphism φ of an abelian group A. Our notation is consistent with Lemma 6.2, namely: x is an element of the generating set X, h is the element of the kernel of φ such that φ(x) = hx, and k is another element of the kernel (if needed). The abelian group A is given by a presentation in terms of generators x and h (and k if needed), however we omit from the presentation those relations which say that the generators commute. Also we describe the effect of φ only on x and the generators of K = ker φ, noting that the definition of φ is naturally extended from K to the coset Kx by φ(ax) = φ(a)φ(x) for any a in K.

(i) A = Z_{2} × Z_{n} = ⟨x, h : x^{2} = h^{n} = 1⟩_{ab}, φ(x) = hx and φ(h) = h; (ii) A = Z_{2n} = ⟨x, h : x^{−2} = h, h^{n} = 1⟩_{ab}, φ(x) = hx and φ(h) = h^{r} where r^{2} ≡ 1

mod n;

(iii) A = Z_{m} × Z_{2mn} = ⟨x, h, k : x^{−2} = h, h^{m} = k^{m}, h^{mn} = k^{mn} = 1⟩_{ab}, φ(x) = hx, φ(h) = k and φ(k) = h.

For each family, it is clear that the subgroup K generated by h (and k in case (iii)) has index 2 in A, and that the restriction of φ to K is an automorphism of order 2, so that φ^{−1} = φ on K. To verify that φ is an anti-automorphism of A, it suffices to check that φ(xb) = φ(x)φ^{−1}(b) for every b in A. This in turn reduces to showing that φ(xx) = φ(x)φ^{−1}(x), and as φ(x) = hx implies x = φ^{−1}(h)φ^{−1}(x) = φ(h)φ^{−1}(x), this is equivalent to showing φ(xx)x^{−1} = hxφ(h)^{−1}. Both sides of the latter equation equal x in case (i), and x^{−1}h^{−r} in case (ii), and x^{−1}k^{−1} in case (iii), so this verification is easy. Finally, the orbit X of x under φ clearly generates A, and is closed under inverses (as the inverse of x is either x or hx in each case). Type (i) appears in [11], and in the discussion before Lemma 6.2.

Our main result for this section is that these are the only types of anti-balanced regular Cayley maps for finite abelian groups.

Theorem 7.1 If the finite group A has an anti-balanced regular Cayley map, then A is isomorphic to one of the groups Z_{2} × Z_{n}, Z_{2n} or Z_{m} × Z_{2mn}, where m and n are positive integers. Furthermore, the group A has an anti-automorphism φ of one of the three types (i), (ii) and (iii) listed above.

Proof. The proof is similar to that of Theorem 6.3, and we use the same notation. Recall that the kernel K of the skew-morphism φ is a subgroup of index 2 in A, and that the restriction of φ to K is an automorphism of K, of order 2. By Lemma 4.2 (with t = −1), the distances between inverses in the cycle representing φ on the generating set X are given by j − 2i for some fixed j and variable i, and it follows that there must be an element x in X such that the distance from x to x^{−1} is 0 or 1. This implies either x^{2} = 1 or φ(x) = x^{−1}. In both cases, let h = φ(x)x^{−1} as usual.

If x^{2} = 1, then h = xφ(x) so φ(h) = φ(xφ(x)) = φ(x)φ^{−1}(φ(x)) = hxx = h, therefore A is generated by x and h, and we have an anti-balanced map of type (i).

If φ(x) = x^{−1}, then hx = x^{−1} so x^{−2} = h, and hence A is generated by x and k = φ(h). If φ(h) lies in the subgroup generated by h, then A is cyclic (generated by x), and we have an anti-balanced map of type (ii). If not, then A has rank 2, and letting n be the order of the intersection of the conjugate cyclic subgroups generated by h and k, and m be the index of this subgroup in the cyclic subgroup generated by h (which equals the smallest positive integer j for which k^{j} is a power of h), we have an anti-balanced map of type (iii). □

8 Other regular Cayley maps for abelian groups

All the maps constructed above have the property that the power function π is constant on the generating set X. Cayley maps CM(A, X, p) for which X contains elements from different cosets of ker π (with index |A : ker π| > 2) appear to be much more difficult to investigate. We have observed that in these cases the ordering of X induced by φ must be of the form (13), given just prior to Theorem 5.4. Although this puts what appear to be restrictive conditions on the elements h_{j}, it turns out there are several examples in which this phenomenon occurs. One is given below.

Example 8.1 Consider the direct product A = C_{6}×C_{3} of two cyclic groups generated by elements u and v of orders 6 and 3, written multiplicatively. This group has a skew-morphism φ given by the permutation (1) (u, u^{−1}, u^{3}v^{−1}, u^{−3}v, u^{−1}v, uv^{−1}) (u^{2}, v^{−1}, v, u^{2}v, u^{−2}v^{−1}, u^{−2}) (u^{3}) (uv, u^{−1}v^{−1}) (u^{2}v^{−1}, u^{−2}v). All the orbits of this skew-morphism φ are closed under inverses, and the second one contains a generating set X for the group; indeed the φ-ordering of X is of the form [a, a^{−1}, b, b^{−1}, c, c^{−1}].

The kernel K = ker π of the associated power function π is the subgroup generated by ab^{2} = uv, of order 6, and contains the elements of the last two orbits plus the two fixed elements of φ. Coset representatives for ker π in the group A may be taken as 1, v and v^{−1}, and the power function π associated with φ is given by π(h) = 1, π(hv) = 3 and π(hv^{−1}) = 5, for all h ∈ K. Note that all π-values are odd, as expected, since the orbits of φ on K are all of length 1 or 2. The distribution of the π-values over the generating set X is [5, 3, 5, 3, 5, 3].

In conclusion we note that there are just two kinds of distributions of the values of power functions assigned to the generators of regular Cayley maps of finite abelian groups: either all these powers are the same, or they form a sequence in which a basic proper subsequence of distinct powers is repeated a number of times. Since the values of the power function on the generators can be computed from the inverse distribution χ alone, it follows that the result in [9] stating the existence of a regular Cayley map for each distribution of inverses does not remain true when restricted to finite abelian groups; in other words, there exist possibilities for χ such that no simple regular Cayley map CM(A, X, p) for a finite abelian group A has distribution of inverses equal to χ.

A substantial amount of further theory of regular Cayley maps for finite abelian groups is given in [2].

References

[1] N. Biggs and A.T. White, Permutation groups and combinatorial structures, Math. Soc. Lect. Notes 33 (Cambridge Univ. Press, Cambridge, 1979).

[2] M. Conder, R. Jajcay and T.W. Tucker, Regular Cayley maps for finite abelian groups, preprint.

[3] J.L.Gross and T.W. Tucker, Topological graph theory, Wiley, New York, 1987.

[4] R. Jajcay and J. Širáň, Skew-morphisms of regular Cayley maps, Discrete Math. 244 (2002), no. 1-3, pp. 167-179.

[5] L.D. James and G.A. Jones, Regular Orientable Imbeddings of Complete Graphs, Journal of Comb. Theory, 39 (1985) 353-367.

[6] Ľ. Lišková, M. Mačaj and M. Škoviera, Regular maps from Cayley graphs, III., preprint.

[7] J. Martino and M. Schultz, Symmetrical Cayley maps with solvable automorphism groups, abstract in SIGMAC ’98, Flagstaff, AR, 1998.

[8] J. Martino, M. Schultz and M. Škoviera, Cayley maps and e-morphisms, preprint.

[9] B. Richter, J. Širáň, R. Jajcay, T. Tucker, M. Watkins, Cayley maps, submitted for publication.

[10] M.Škoviera and J.Širáň, Regular Maps from Cayley Graphs, Part I. Balanced Cayley Maps, Discrete Math. 109 (1992), 265-276.

[11] M.Škoviera and J.Širáň, Regular Maps from Cayley Graphs II. Antibalanced Cayley Maps, Discrete Math. 124 (1994), 179-191.

[12] J.Širáň and M. Škoviera, Groups with sign structure and their antiautomorphisms, Discrete Math. 108 (1992), 189-202.

[13] P.T. Smith, Local symmetries of symmetrical Cayley maps, PhD. dissertation at Western Michigan U., (2002).