ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 10 (2016) 113-134 On the split structure of lifted groups Aleksander Malnic * Univerza v Ljubljani, Pedagoška fakulteta, Kardeljeva pl. 16, 1000 Ljubljana, Slovenia Univerza na Primorskem, Institut Andrej Marusic, Muzejski trg 2, 6000 Koper, Slovenia Rok Požar t Univerza v Ljubljani, Pedagoška fakulteta, Kardeljeva pl. 16, 1000 Ljubljana, Slovenia Univerza na Primorskem, FAMNIT, Glagoljaška 8, 6000 Koper, Slovenia Received 18 May 2014, accepted 23 November 2014, published online 24 July 2015 Let p: X ^ X be a regular covering projection of connected graphs with the group of covering transformations CTP being abelian. Assuming that a group of automorphisms G < Aut X lifts along p to a group G < Aut X, the problem whether the corresponding exact sequence id ^ CTP ^ G ^ G ^ id splits is analyzed in detail in terms of a Cayley voltage assignment that reconstructs the projection up to equivalence. In the above combinatorial setting the extension is given only implicitly: neither G nor the action G ^ AutCTp nor a 2-cocycle G x G ^ CTP, are given. Explicitly constructing the cover X together with CTp and G as permutation groups on X is time and space consuming whenever CTP is large; thus, using the implemented algorithms (for instance, HasComplement in Magma) is far from optimal. Instead, we show that the minimal required information about the action and the 2-cocycle can be effectively decoded directly from voltages (without explicitly constructing the cover and the lifted group); one could then use the standard method by reducing the problem to solving a linear system of equations over the integers. However, along these lines we here take a slightly different approach which even does not require any knowledge of cohomology. Time and space complexity are formally analyzed whenever CTP is elementary abelian. Keywords: Algorithm, abelian cover, Cayley voltages, covering projection, graph, group extension, group presentation, lifting automorphisms, linear systems over the integers, semidirect product. Math. Subj. Class.: 05C50, 05C85, 05E18, 20B40, 20B25, 20K35, 57M10, 68W05 * Corresponding author. Supported in part by "Agencija za raziskovalno dejavnost Republike Slovenije", research program P1-0285, and research projects J1-5433 and J1-6720. t Supported in part by "Agencija za raziskovalno dejavnost Republike Slovenije", research program P1-0285. The author also thanks the University of Auckland, New Zealand, for hospitality during his 6 months research visit in 2011-12. Abstract charchar This work is licensed under http://creativecommons.org/licenses/by/3.0/ 170 Ars Math. Contemp. 10 (2016) 114-181 1 Introduction A large part of algebraic graph theory is devoted to analyzing structural properties of graphs with prescribed degree of symmetry in order to classify, enumerate, construct infinite families, and to produce catalogs of particular classes of interesting graphs up to a certain reasonable size. References are too numerous to be listed here, but see for instance [2, 6, 8, 9, 10, 11, 12, 14, 16, 24, 25, 26, 29, 31, 36, 39,40, 42, 46, 47, 52, 53, 55], and the references therein. It is not surprising, then, that the techniques employed in these studies are fairly rich and diverse, ranging from pure combinatorial and computational methods to methods from abstract group theory, permutation groups, combinatorial group theory, linear algebra, representation theory, and algebraic topology. Covering space techniques, and lifting groups of automorphisms along regular covering projections in particular, play a prominent role in this context. (See Section 2 for exact definitions of all notions used in this Introduction.) The idea goes back to Djokovic [9] (and to an unpublished work of Conway, see [3, Corollary 19.6]), who constructed first examples of infinite families of graphs of small valency and maximal degree of transitivity, and to Biggs [3, Proposition 19.3], who gave a sufficient condition for a group of automorphisms to lift as a semidirect product. While Djokovic's approach is classical in terms of fundamental groups, Biggs expressed his particular lifting condition combinatorially. A combinatorial approach to covering projections of graphs in terms of voltages was systematically developed in the early 70' by Gross and Tucker, see [20], after having been introduced by Alpert and Gross [18, 19] in the context of maps on surfaces. A systematic combinatorial treatment of lifting automorphisms along covering projections (either in the context of graphs, maps on surfaces, or cell complexes) has been considered by several authors, see [1, 21, 32, 33,48, 50] and the references therein. More specific types of covers, say, with cyclic or elementary abelian groups of covering transformations, have been extensively studied in [22, 35, 37,49]; for the applications we refer the reader to [8, 11, 13, 14, 26, 27, 28, 30, 36, 40, 41, 52, 55]. For some recent results on arc transitive cubic graphs arising as regular covers with an abelian group of covering transformations we refer the reader to [7]. Basic lifting techniques in terms of voltages are now well understood, yet several important issues still remain to be considered. In view of the fact that structural properties of graphs often rely on the structure and the action of their automorphism groups, one such topic is investigating the structure of lifted groups - although certain particular questions along these lines have been addressed, see [3, 15, 33, 51]. Other points of interest are algorithmic and complexity aspects of lifting automorphisms, which have so far received even less attention. Certain aspects, but not those considered here, were touched upon in [34, 48]. Specifically, let p: X ^ X be a regular covering projection of connected graphs given in terms of voltages. Assuming that a group G < Aut X lifts along p, it is of particular interest to study the corresponding exact sequence id ^ CCTp ^ G ^ G ^ id. A natural question in this context is to ask whether the extension is split: on one hand, split extensions are the most easy ones to analyze, while on the other hand, a restrictive situation stemming from the fact that the group G, acting on X, acts also on X via its isomorphic complement E-mail addresses: aleksander.malnic@guest.arnes.si (Aleksander Malnic), pozar.rok@gmail.com (Rok Požar) A. Mainte: and R. Pozar: On the split structure of lifted groups 115 G to CTP within G, implies that a lot more information about symmetry properties of X can be derived; moreover, split extensions are frequently encountered in many concrete examples of graph covers. Describing efficient methods for testing whether a given group lifts as a split extension of CTP is the main objective of this paper. Methods for testing whether a given extension 1 ^ K ^ E ^ Q ^ 1 of finite groups is split, are known, see [5] and [23, Chapters 7 and 8]. In some way or another, all these methods use the fact that a set of coset representatives of K in E is a complement to K if and only if these representatives satisfy the defining relations of Q. The essential case to be resolved in the first place is that of K being (elementary) abelian. The idea is to modify an arbitrarily chosen set of coset representatives of K so that the defining relations of Q are satisfied, if possible. Since K is normal and abelian, this modification can be traced in the frame of a certain group algebra, which finally leads to a system of linear equations over the integers (or rather, over prime fields); the complement exists if and only if such a system has a solution. In practice, the extension can be given in several different ways: either (i) in terms of an epimorphism E ^ Q, or (ii) in terms of E and the generators of a normal subgroup K, or (iii) via an action 0: Q ^ Aut K together with a 2-cocycle t : Q x Q ^ K .In cases (i) and (ii), an essential requirement is that one must have enough information about the extended group E; at least one must know its generators and must be able to perform basic computations in E. In contrast with (i) and (ii), explicit knowledge about E is not needed in case (iii) since the extension can be, up to equivalence of extensions, reconstructed as K x Q with multiplication rule (a, x)(b, y) = (a + 0x(b) + t(x, y), xy). In our setting of graph covers, however, the situation is different and does not fall in any of the above three cases. Namely, the extension id ^ CTP ^ G ^ G ^ id is given only implicitly: all the information is encoded in the base graph in terms of voltages that allow G to lift; in particular, neither G nor the action of G on CTP nor a 2-cocycle are given. Naively translating our setting into the frame of (i) or (ii) and then applying the algorithm already implemented in Magma [4] in terms of permutation groups would mean to first compute the covering graph X together with CTP and G acting on X, which, unfortunately, is time and space consuming whenever CTP is large. Our situation best fits into the frame of (iii). But in order to follow the approach described in [5] and [23, Chapters 7 and 8] we first need to compute the action G ^ Aut CTp and the 2-cocycle G x G ^ CTP. As we here show, the minimal required information about these data can indeed be effectively decoded directly from voltages (without explicitly constructing the cover and the lifted group). In the actual algorithm, however, we take an approach which is slightly different and even does not require any knowledge of cohomology. Namely, instead of modifying an initial transversal and working within an appropriate group algebra, a potential complement is constructed directly in terms of certain parameters - in view of the fact that a lift of an automorphism is uniquely determined by the mapping of a single vertex - from which the required system of equations is obtained. Although the method works whenever CTP is abelian, it can be adapted - similarly as in the general context - to treat the case when CTP is solvable as well. The paper is organized as follows. In Section 2 we review some basic facts about regular covering projections and lifting automorphisms. In Section 3 we show how to recapture the lifted group G as a crossed product of CTP by G via reconstructing the coupling G ^ Out CTP and the factor set G x G ^ CTP in terms of voltages, see Theorem 3.1. In Section 4 we give the necessary and sufficient conditions for G to lift as a split extension 170 Ars Math. Contemp. 10 (2016) 116-181 of CTP, see Theorem 4.1, and a similar result regarding direct product extensions, see Theorem 4.3. In Section 5 we provide an algorithm for testing whether the extension is split whenever CTP is abelian, see Subsection 5.1 and Theorem 5.2 in particular. The special case when CTP is elementary abelian together with formal analysis of time and space complexity is treated in Subsection 5.2, see Theorem 5.6. In Subsection 5.3 we briefly mention the case when CTP is solvable. Concluding remarks are given in Section 6. For a more substantial account on complexity issues and further applications we refer the reader to [44, 45]. 2 Preliminaries Graphs. Formally, a graph is an ordered 4-tuple X = (D, V; beg,-1), where D(X) = D and V(X) = V are disjoint sets of darts and vertices, respectively, beg is the function assigning to each dart its initial vertex, and -1 is an arbitrary involution on D that creates edges arising as orbits of -1. For a dart x, its terminal vertex is the vertex end(x) = beg(x-1). An edge e = {x,x-1} is called a link whenever beg(x) = end(x). If beg(x) = end(x), then the respective edge is either a loop or a semi-edge, depending on whether x = x-1 or x = x-1, respectively. There are several reasons for treating graphs formally in a manner just described. For one thing, it is quite versatile for writing down formal proofs; moreover it is indeed natural, even necessary, to consider graphs with semi-edges in different contexts, for instance when dealing with graph covers or when studying graphs that are embedded into surfaces. For a nice use of semi-edges in the context of Cayley graphs we refer the reader to [17]. A walk W: u ^ v of length n > 0 from a vertex u0 = u to a vertex un = v is a sequence of vertices and darts W = u0 x1 u1 x2 u2 ... un-1 xn un where beg(xj) = uj-1 and end(xj) = uj for all indices j = 1,..., n. Its inverse walk W-1: v ^ u is the walk obtained by listing the vertices and darts appearing in W in reverse order. The walk u is the trivial walk at the vertex u. Walks of length 1 are sometimes referred to as arcs. A graph is connected if any two vertices are connected by a walk. A walk is reduced if no two consecutive darts in the walk are inverse to each other. Clearly, each walk W has an associated reduced walk W obtained by recursively deleting all appearances uxvx-1 of consecutive pairs of inverse darts (together with the respective vertices). Two walks W, W': u ^ v with the same reduction are called homotopic. Homotopy is an equivalence relation on the set of all walks, with homotopy classes denoted by [W]. Observe that the naturally defined product of walks W1W2 by 'concatenation', when defined, carries over to homotopy classes, [W1][W2] = [W1W2]. Assuming the graph X to be connected, the set of homotopy classes of closed walks u ^ u, equipped with the above product, defines the first homotopy group n(X, u). The trivial class 1u = [u] consists of all walks contractible to u. Note that the isomorphism class of n(X, u) does not depend on u. More precisely, n(X, u) is isomorphic to the free product of cyclic groups Z or Z2 (where the Z2 factors correspond bijectively to the set of all semi-edges in X). A generating set for n(X, u) is provided by fundamental closed walks at u relative to an arbitrarily chosen spanning tree. Let X and X' be graphs. A graph homomorphism f: X ^ X' is an adjacency preserving mapping taking darts to darts and vertices to vertices, or more precisely, f (beg(x)) = beg(f (x)) and f (x-1) = f (x)-1. Homomorphisms are composed as functions, (fg)(x) = f (g(x)). Given a graph X we frequently need to consider the restricted (and the induced) left action of its group of automorphisms Aut X on certain subsets of X, for instance A. Mainte: and R. Pozar: On the split structure of lifted groups 117 the sets of vertices, darts, edges etc. As Aut X is by definition a permutation group on the union V (X )UD(X) of disjoint sets of vertices and darts, it acts faithfully on V (X )UD(X). However, its action on V(X) need not be faithful unless X is simple, that is, if it has no parallel links, loops, or semi-edges. We say that a group G < Aut X acts semiregularly on X whenever it acts freely on V (X) (meaning that if g G G fixes a vertex it must be the identity on vertices and darts). Covers. To fix the notation and terminology, and for easier reading, we quickly review some essential facts about covers. The interested reader is referred to [20, 33, 54] for more information. A covering projection of graphs is a surjective homomorphism p: X ^ X mapping the set of darts with a common initial vertex in the covering graph X bijectively to the set of darts at the image of that vertex in the base graph X. The preimages fibu = p-1 (u), u G V(X), and fibx = p-1(x), x G D(X), are the vertex- and dart-fibres, respectively. From the definition of a covering projection it immediately follows that for any walk W: u ^ v in X and an arbitrary vertex U G fib(u) there is a unique liftedwalk Wu withbeg(TTr") = U that projects to W. This is known as the unique-path lifting property. Consequently, if X is connected (which will be our standard assumption without loss of generality) then all fibres have equal cardinality, usually referred to as the number of folds. It is also immediate that homotopic walks lift to homotopic walks, and that u • [W] = end(Wu) defines a 'right action' of homotopy classes on the vertex set of X. In particular, the fundamental group n(X, u) acts on the right on fibu, with the stabilizer of u G fibu being isomorphic to n(X, u). It is precisely this action that is responsible for the structural properties of the covering. Covering projections that are particularly important when studying symmetry properties of covers are the regular covering projections. By definition, a covering projection p: X ^ X is regular if there exists a semiregular group C < Aut X such that its orbits on vertices and on darts coincide with vertex- and dart-fibres, respectively. In other words, C acts regularly on each fibre (hence the name), and so the covering projection is |C| -fold. Regular covering projections can be grasped combinatorially as follows. First of all, given a graph X and an (abstract) group r, let Z: D(X) ^ r be a function such that Z(x-1) = (Z(x))-1. (For convenience we shall write Zx = Z(x) and Z-1 = (Zx)-1.) In this context, r is called a voltage group, Z is a Cayley voltage assignment on X, and Zx is the voltage of the dart x. We remark that a voltage assignment as above is known as an ordinary voltage assignment in the literature [20]. With these data we may define the derived graph Cov(Z) with vertex set V(X) x r and dart set D(X) x r, where beg(x, c) = (beg(x), c) and (x, c)-1 = (x-1, cZx). The projection onto the first coordinate defines a regular covering projection pz: Cov(Z) ^ X. The required semiregular group C is obtained by viewing C = r as a group of automorphisms of Cov(Z) via its left action on the second coordinates by left multiplication on itself: an element a G r maps the vertex (u, c) to (u, ac) and the dart (x, c) to (x, ac). In addition, call the right action of r on itself by right multiplication a voltage-action. This action determines how walks of length 1 lift: a walk uxv lifts to walks (u, c)(x, c)(v, cZx), for c G r. Conversely, with any regular covering projection p: X ^ X we can associate a Cayley voltage assignment Z on X such that pz : Cov(Z) ^ X 'essentially reconstructs' the projection p in a sense to be described below. Indeed, let r = C be the semiregular group from the definition of a regular covering. As r acts regularly on each fibre we may label 170 Ars Math. Contemp. 10 (2016) 118-181 the vertices and the darts of X by elements of V(X) x r and D(X) x r, respectively, as follows. Choosing arbitrarily a vertex u G fibu we label the vertex c(u) G fibu, c G r, by (u, c). This way we obtain a bijective labeling of fibu by {u} x r. Similarly, the darts in fibx are labeled by {x} x r, where (x, c) is the label of the dart in fibx having its initial vertex labeled by (u, c). For x g D(X), let Zx G r be such an element of the voltage group that (end(x), Zx) is the label of the terminal vertex of the dart in fibx labeled by (x, 1). Then the terminal vertex of any dart in fibx, say, labeled by (x, c), is labeled by (end(x), cZx). Clearly, Zx-i = Z-1. The respective regular covering projection p^: Cov(Z) ^ X is equivalent to p, a concept that we are now going to define. Two covering projections p: X ^ X and p': X' ^ X are isomorphic if there exists an automorphism g G Aut X and an isomorphism g: X ^ X' such that the following diagram X X is commutative. If in the above diagram one can choose g = id, then the projections are equivalent. Covering projections are usually studied up to equivalence, or possibly up to isomorphism (which is considerably more difficult). A voltage assignment Z : D(X) ^ r can be naturally extended to walks as follows: if W = mo x1 u1 x2 u2 ... m„_i xn un, then Zw = ZxZx2 ... ZXn. Clearly, homotopic walks carry the same voltage, and so voltages can be assigned to homotopy classes. Moreover, the 'right action' of homotopy classes via unique path-lifting along pz : Cov(Z) ^ X is essentially the voltage-action: if W : u ^ v is a walk in X and M g fibu is labeled by (u, c), then M • [W] g fibv is labeled by (v, cZW). We may therefore say that the voltage-action faithfully represents the 'action' of homotopy classes, and in particular, the action of n(X, u). It immediately follows that Z defines a group homomorphism Z : n(X, u) ^ r (denoted by the same symbol for convenience). Lifts of automorphisms. An automorphism g G Aut X lifts along a covering projection p: X ^ X if there exists an automorphism g G Aut X such that the diagram X X p is commutative. The automorphism g then projects to g. A group G < Aut X lifts if all g G G lift. We call such a covering projection G-admissible. The collection of all lifts of all elements in G form a subgroup G < Aut X, the lift of G. In particular, the lift of the trivial group is known as the group of covering transformations (or self-equivalences of p) and denoted by CTP. Moreover, the sequence id ^ CTp ^ G ^ G ^ id A. Mainte: and R. Pozar: On the split structure of lifted groups 119 is short exact. In other words, G is an extension of CTP by G, and hence g G G has exactly |CTP| distinct lifts, a coset of CTP within G. Furthermore, if G lifts along a given projection p, then it lifts along any covering projection equivalent to p. This allows us to study lifts of automorphisms combinatorially in terms of voltages, see for instance [1, 21, 32, 33, 48, 50]. Also note that if G and G' are the lifts of G along equivalent projections p and p', respectively, then the short exact sequences id ^ CTP ^ G ^ G ^ id and id ^ CTp/ ^ G' ^ G ^ id are isomorphic. Thus, structural properties of lifted groups can be studied combinatorially in terms of voltages as well. In this paper we focus on G-admissible covering projections such that the extension id ^ CTP ^ G ^ G ^ id is split. We call such a covering projection G-split-admissible. Note, however, that the lifted group G might contain a subgroup H isomorphic to CTP such that the extension id ^ H ^ G ^ G ^ id is split even if id ^ CTP ^ G ^ G ^ id is not. From now on we shall be assuming that covering projections are regular and moreover, that covering graphs are connected as well. By assuming connectedness we essentially do not loose on generality, however, we technically gain a lot. Let us remark that if X is connected, then the covering graph is connected if and only if the fundamental group n(X, u) acts transitively on fibu. An equivalent requirement in terms of a voltage assignment Z: D(X) ^ r is that the homomorphic image Z(n(X, u)) < r acts transitively relative to its voltage-action on r, that is, Z(n(X, u)) = r, which in turn amounts to saying that the voltages assigned to fundamental closed walks at u generate the voltage group r. With the assumption on connectedness, the group CTP acts regularly on each fibre, and hence any lift g of g G Aut X, if it exists, is uniquely determined by the mapping of just one vertex (or dart). Also, the semiregular group C from the definition of a regular covering is now C = CTP, and the voltage assignment Z: D(X) ^ r that reconstructs the projection takes values in an abstract group r = CTP. Consider now a regular covering projection pz : Cov(Z) ^ X of connected graphs, where X is assumed to be finite, and let u0 G V(X) be an arbitrarily chosen base vertex. By the basic lifting lemma, see [32, Theorem 4.2] and [33, Theorem 7.1], a group G < Aut X lifts along pz if and only if any closed walk W at u0 with Zw = 1 is mapped to a walk with ZgW = 1, for all g G G. This is equivalent to requiring that for each g G G there exists an induced automorphism g#u° g Aut r of the voltage group defined locally at u0 by g#u° (Zw) = ZgW, W G n(X,uo). Note that if the condition is satisfied at u0, it holds locally at any vertex. In general, for g, h G G the automorphisms g#u and g#v at distinct vertices, as well as the automorphisms (gh)#u and g#u h#u, differ by an inner automorphism of r. More precisely, the following holds. (Throughout the paper, denotes the inner automorphism ^t(a) = tat-1, whatever the group. Note further that all automorphisms are composed as functions.) Proposition 2.1. Let G < Aut X be a group of automorphisms that lifts along a regular covering projection of connected graphs p: X ^ X given in terms of a voltage assignment Z: D(X) ^ r. Then for any g, h G G we have V- (zqk;q g#v = g#u, Q: v ^ u, V- (zq)z^ (gh)#u = g#u h#u, Q : hu ^ u. 170 Ars Math. Contemp. 10 (2016) 120-181 Proof. Let W be a closed walk at v and Q: v ^ u an arbitrary walk. Then Q 1WQ is a closed walk at u, and by the definition of induced automorphisms of r at v and u we have g#v(Cw) = CgW and g#u(Cq-iwq) = Zg(Q-iWQ). Clearly, Cq-^wq = Cq1CwCq and Zg(Q-iWQ) = C-QCgWCgQ. Since g#u is an automorphism we have g#u (Cq)- 1g#u (Cw )g#u (Cq) = C;Q,Cgw CgQ. Hence ^g#„ )£-i g#v = g#", and the first part is proved. For the second part, let W be a closed walk at u and Q: hu ^ u an arbitrary walk. Then (gh)#u (Cw ) = Cghw = g#hu (Chw) = g#hu (h#u (Cw )). Hence (gh)#u = g#hu h#u. By the first part we have ^g#„ (^g#hu = g#u, and consequently, ^g#„ (^(gh)#u = g#" h#u, as required. □ Clearly, the function #„0: G ^ Autr, g ^ g#u°, is not a group homomorphism in general. But if we define g# = g#uo mod Inn r, then, by Proposition 2.1, g# does not depend on u0, and #: G ^ Outr, g ^ g#, is a homomorphism. In particular, if the covering projection is abelian, meaning that r = CTP is abelian, then # = #Uo: G ^ Autr is a homomorphism, which turns r into a Z[G]-module. We shall make substantial use of this fact later on. If g lifts, denote by $v,g the permutation on the voltage group r corresponding to the restriction g: fibv ^ fibgv. In other words, g(v,c) = (gv, $„,g(c)). (2.1) As it was shown in [32, 33], the mappings of labels at different fibres relate to each other as follows: Wc) = W1) g#u (c) (2.2) Cg Q' *v,g(c) = $u,~g(c) g#u (Cq)C1, (2.3) where Q: v ^ u is an arbitrary walk. Finally, for t e r we denote by gt the uniquely defined lift of g mapping the vertex in fibUo labeled by 1 e r to the vertex in fibguo labeled by t e r, that is, gt(uo, 1) = (guo,t). In particular, idt is the covering transformation acting on the second coordinates in Cov(C) by left multiplication by t on r. Indeed, since id#" = id for all u e V(X), it follows from (2.2) and (2.3) that idt(u, c) = (u, tc). A. Mainte: and R. Pozar: On the split structure of lifted groups 121 3 Extensions in terms of voltages The method how to recapture a given group extension 1 ^ K ^ E ^ Q ^ 1 in the form of a crossed product is known and goes back to Schreier (cf. [38]). First choose a system of coset representatives of K within E (also called an algebraic transversal) T = {tx | x G Q} (and usually normalized in the sense that t\ = 1). Then compute the factor set F: Q x Q ^ K defined by F : (x, y) ^ txtyt-y , and the function Q Aut K, x ^ (recall that (a) = txat-1); in general, ^ is not a group homomorphism, and is often referred to as the weak action of Q on K (which, when reduced modulo inner automorphisms of K, gives rise to a homomorphism Q ^ Out K known as the coupling or the twisting map). These data determine a group operation on K x Q defined by (a,x)(b,y) = (a^ix (b)F(x,y),xy). The resulting group is called the crossed product of K by Q and denoted K x Q. The mapping K Q ^ E defined by (a, x) ^ atx is an isomorphism taking K x 1 onto K and 1 x Q onto the algebraic transversal T, and establishes an equivalence of short exact sequences K x Q Suppose now that a regular covering projection p = pz: Cov(Z) ^ X of connected graphs is given in terms of a Cayley voltage assignment Z: D(X) ^ r, and let a group G < Aut X of automorphisms lift to G < Aut Cov(Z). In order to recapture G as a crossed product of CTP by G let us choose a particular algebraic transversal by taking tg = 1 for all g G G, that is, T = {g1 | g g G}. To compute the factor set G x G ^ CTp we need to identify c g r such that g1h1(gh)-1 = idc. We do that by evaluating g1h1 = idc(gh)1 at (u0,1). Using (2.2) and (2.3) we get g7"(Zq )ZgQ, where Q: huo ^ uo is arbitrary. As for the weak action G ^ Aut CTp we need to find t G r such that g1idag—1 = idt. Evaluating g1ida = idtg1 at (u0,1) and using (2.2) we obtain t = g#"0 (a). In view of the isomorphism CTP = r, idt ^ t, we have an isomorphism of short exact sequences id CT G G id. r i 170 Ars Math. Contemp. 10 (2016) 122-181 Hence the lifted group G can be written, up to isomorphism, as a crossed product r x G, where F: G x G ^ r is given by F(g, h) = g#uo (CqK— and ^: G ^ Aut r is defined by = g#uo. Note that the weak action ^ is precisely #„0 defined in Preliminaries. We have therefore proved the following theorem. Theorem 3.1. Let p = pz : Cov(Z) ^ X be a regular covering projection of connected graphs given in terms of a Cayley voltage assignment (: D(X) ^ r, and let a group G < Aut X of automorphisms lift to G < Aut Cov(Z). Choosing a base vertex u0 G V (X), let ^: G ^ Aut r and F: G x G ^ r be functions defined by = g#u0 and F(g, h) = g#u° (Cq)C-q1, Q: hu0 ^ uo, respectively. Then there is an isomorphism r x$i f G ^ G, (a, g) ^ g0 taking r x id onto CTP and 1 x G onto the algebraic transversal {g1 | g G G}. □ 4 Split extensions in terms of voltages Recall that a short exact sequence 1 ^ K ^ E ^ Q ^ 1 is split if there exists an algebraic transversal T = {tx |x G Q} which is a subgroup, called a complement to K within E. Relative to such a complement, the respective factor set F = 1 is trivial and the weak action ^ is in fact an action, that is, ^: Q ^ Aut K is a homomorphism. Consequently, recapturing E as the corresponding crossed product results in a semidirect product K x^ Q with the group operation (a, x)(b, y) = (a^tx (b), xy). In the next theorem, the necessary and sufficient condition for a regular covering projection p to be G-split-admissible, together with an explicit description of the lifted group as a semidirect product of CTP by G, are given in terms of voltages. Theorem 4.1. Let p = pz : Cov(Z) ^ X be a regular covering projection of connected graphs given in terms of a Cayley voltage assignment (: D(X) ^ r, and let a group G < Aut X of automorphisms lift to G < AutCov(Z). Then p is G-split admissible if and only if there exists a normalized function t: G ^ r (that is, tid = 1) such that tgh = tgg#u0 (th) g#u0 (CQ)CgQ1 (4.1) where Q: hu0 ^ u0 is an arbitrary walk. In this case there exists a homomorphism 6: G ^ Aut r given by 6g (c)= tgg#u0 (c)t-1, (4.2) and (a, g) ^ ga tg defines an isomorphism r x g G ^ G which takes r x id onto CTP and id x G onto the algebraic transversal G = {i;tg | g G G}, a complement to CTP. Proof. Let us recover the lifted group G as in Theorem 3.1. The extension splits if and only if there exists an algebraic transversal {(tg, g), g G G} to r x id in r x ^ f G which is a subgroup. Equivalently, we must have (tgh, gh) = (tg, g)(th, h). By the definition of multiplication in r x G the right hand side is equal to (tgg#u0 (th)F(g, h), gh). Hence the necessary and sufficient condition (4.1) can be expressed as stated in the theorem. That (4.2) defines a homomorphism can be shown by computation, using (4.1) and Proposition 2.1. The rest is straightforward as well. □ A. Mainte: and R. Pozar: On the split structure of lifted groups 123 Remark 4.2. In the abelian case, (4.1) rewrites as tgh = tg + g#uo (th) + t(g, h), where "9 t(g, h) = F(g, h) = g#u° (Zq) - Z9q is the 2-cocycle. Thus, (4.1) is equivalent to the fact that t(g, h) = tgh —19 — g#u° (th) must be a 2-coboundary. □ From Theorem 4.1 we readily obtain the necessary and sufficient conditions for G to lift as a direct product extension of CTP, that is, when CTP has a normal complement within the lifted group G. Theorem 4.3. Let p = pz : Cov(Z) ^ X be a regular covering projection of connected graphs given in terms of a Cayley voltage assignment Z: D(X) ^ r. Then G lifts along p as a direct product extension of CTP if and only if there exists a normalized function t: G ^ r (that is, tid = 1) satisfying tgh = thZQtg ZgQ, (4.3) where Q: hu0 ^ u0 is an arbitrary walk. In this case, (a, g) ^ ga tg defines an isomorphism r x G ^ G which takes r x id onto CTp and id x G onto the algebraic transversal G = {gtg | g € G}, a normal complement to CTP. Proof. Suppose that G lifts as a direct product such that CTP has a normal complement G = {gtg | g € G}. By Theorem 4.1 the respective function t: G ^ r satisfies (4.1). Normality of G implies that d9 (c) given by (4.2) must be the identity automorphism. Hence g#uo (c) = t-1ctg, and by (4.1) we have tgh = thZQtgZ-Q, as required. For the converse suppose that a function t: G ^ r satisfies tgh = thZQt9Z"Q. Taking h = id we obtain Z9q = t- 1ZQt9 for all closed walks Q: u0 ^ u0. Therefore, if Zq = 1 then Z9q = 1 for all g € G. By the basic lifting lemma G lifts, and g#u° takes the form g#u° (c) = t-1 ctg. It follows that tgh = tgg#u° (th) g#u° (Zq)ZgQ1. By Theorem 4.1 we have G = r G where 6g (c) = tgg#u° (c)t-1 = c. Hence G = r x G, and the proof is complete. □ Remark 4.4. Notice the subtle difference in assumptions in Theorems 4.1 and 4.3. While in 4.1 we had to assume in advance that G had a lift, this assumption is not required in 4.3 as condition (4.3) does not involve g#u°. □ We also note the following. Suppose that G lifts as a split extension of CTP. In general, normal and non-normal complements to CTP might exist. So a priori knowledge about a given extension being split does not make it easier to check whether the extension is actually a direct product extension. In the abelian case, however, things are different since complements are either all normal or all non-normal. This means that if t: G ^ Aut r is just any normalized function satisfying (4.1), the extension will be a direct product extension if and only if the corresponding homomorphism 6 as in (4.2) is trivial. For later reference, see Corollary 5.5, we explicitly record the following corollary. Corollary 4.5. Let p = pz: Cov(Z) ^ X be a regular covering projection of connected graphs given in terms of a Cayley voltage assignment Z: D(X) ^ r. Suppose that G < Aut X lifts along p as a split extension. Then G lifts as a direct product extension of CTp if and only if Z9w = Zw holds for all closed walks W from a basis of the first homology group H1 (X, Z) and all g from some generating set of G. 170 Ars Math. Contemp. 10 (2016) 124-181 Proof. By Theorem 4.1 there exists a normalized function t: G ^ r satisfying (4.1). Now, in the abelian case the extension is a direct product extension if and only if 0 as in (4.2) is trivial. Since 0g(c) = g#uo (c), this amounts to saying that ZgW = ZW must hold for all closed walks based at u0 and all g G G. Moreover, recall that in the abelian case g#uo does not depend on u0. Hence the above necessary and sufficient condition can be replaced by only considering closed walks from a basis of the first homology group. Clearly, it is enough to consider just the automorphisms from a generating set of G. □ Remark 4.6. Note that if the covering projection is abelian and the condition ZgW = ZW holds true for all closed walks and all g G G, then G clearly lifts (by the basic lifting lemma). However, the extension might not be split. As an example, let X be the 2-dipole with vertices 1 and 2 and two parallel links from 1 to 2 defined by the darts a and b. The voltage assignment Za = Za-i =0, Z& = C&-1 = 1 in the group Z2 gives rise to a connected covering graph isomorphic to the 4-cycle C4. Clearly, ZgW = ZW holds for all g G Aut X = Z2 x Z2 and all closed walks W. However, the lifted group is isomorphic to D4, viewed as a central extension of Z2 by Z2 x Z2, and this extension is clearly not split. □ 5 Algorithmic aspects Let p = pz : Cov(Z) ^ X be a regular covering projection of connected graphs given in terms of a Cayley voltage assignment Z: D(X) ^ r, where X is assumed to be finite, and let G < Aut X be a group of automorphisms. Speaking of algorithmic and complexity issues related to lifting automorphisms one would certainly first need to address the question of how difficult is to test whether G lifts at all. However, this will not be our concern here; the problem has been considered, to some extent, in [48]. Assuming that G is known to have a lift we focus on efficient algorithms (in terms of voltages) for testing if G lifts as a split extension of CTP. Testing condition (4.1) of Theorem 4.1 is hard even if r is abelian - as one has to take into account all group elements of G. (Indeed, Theorem 4.1 is of purely theoretical interest.) A much better alternative would be to consider just the generators, and in fact, one must then assume that G is given by a presentation, which is sensible assumption. Proposition 5.1 below is a reformulation of a standard result, c.f. [23, Lemma 2.76], tailored to our present needs. For completeness we provide the proof. Proposition 5.1. Let p: X ^ X be a regular covering projection of connected graphs, and let G < Aut X be a group given by the presentation G = (S | R), where S = {gi, g2,..., gn} and the R-relations are Rj(gi, g2,..., gn) = id, j = 1,2,..., m. Suppose that G lifts. Then the lifted group G is a split extension of CTP if and only if there are lifts g1, g2,..., gn of g1, g2,..., gn, respectively, satisfying the defining relations Rj (gi ,g2,...,gn) = id, j = 1, 2,..., m. Proof. Suppose first that there are lifts g1, g2,..., gn of g1, g2,..., gn satisfying the R-relations, and let C = (g1, g2,..., gn) < G. Since the R-relations are the defining relations of G there exists an epimorphism G ^ C, gj ^ gj. On the other hand, C projects onto G, with gj ^ gj. Consequently, C = G. As C isomorphically projects onto G it must intersect the kernel CTP of the projection G ^ G trivially. Hence C is a complement to CTp within (5. A. Mainte: and R. Pozar: On the split structure of lifted groups 125 Conversely, suppose that there are lifts g1,g2,... ,gn of g1,g2,... ,gn such that C = (g1, g2,... ,gn) < G is a complement to CTP within G. Then C = G, and since gn ^ gi we have that each automorphism Rj (g1,g2,..., gn) projects to Rj (g1,g2,..., gn) = id. So Rj(g1,g2,...,gn) € C belongs to CTP. As C is the complement we have Rj (g1,g2,---,gn) = id, and the proof is complete. □ The condition Rj (g1,g2,... ,gn) = id can be tested just by checking whether the automorphism Rj(g1,g2,..., gn), which necessarily belongs to CTP, fixes a vertex. With our assumption that the covering graph is reconstructed as Cov(Z) we choose this vertex to be (u0,1). Let gi(u0, 1) = (giu0,ti), and recall that a lift is uniquely determined by the image of a single vertex. If t1, t2,... ,tn are explicitly given, then Rj (g1, g2,..., gn) can be evaluated recursively using (2.2) and (2.3). To find whether the required lifts g1,g2,... ,gn exist by checking the whole set rn for all possible values of t1,t2,... ,tn is far from optimal. The core of the problem is therefore to evaluate Rj (g1,g2,..., gn) efficiently when t1,t2,... ,tn are seen as symbolic variables, in which case the requirements Rj (g1,g2,...,gn)(u0,1) = (u0,1) translate to an equivalent problem of solving a system of equations in the variables t1,t2,... ,tn € r. We are faced with two main difficulties. First, to evaluate Rj (g1, g2,..., gn) using symbolic variables we need to express g#uo by a 'closed formula', and second, we have to solve a (possibly a non-linear) system of equations over r. Both are rather hopeless if r is nonabelian. On the other hand, if r = CTP is a finitely presented abelian group, then the automorphisms of r can be represented by integer matrices acting on the left on integer column vectors representing group elements. (In what follows, we shall be freely using the term 'vector' for ease of expression.) Moreover, as we shall see, in the abelian case the system of equations results in a linear system over the integers. 5.1 Abelian covers Let us therefore assume that r is abelian, given by a presentation r = (A | A), where A = {c1, c2,..., cr } is a generating set and Ak (c1,c2,... ,cr) = 0, where k =1,2,... ,s, are the A-relations. Each element c € r can be represented by a column vector c € Zr1 such that c = [Ai, X2,..., Xr]T, where c = ^^ A¿ i=i This representation is unique modulo the kernel (generated by the defining relations Aj) of the natural quotient projection k : Zr>1 ^ r. Moreover, any automorphism $ G Aut r can be represented (again not in a unique way) as a matrix over Z by expressing each as ) = J2Tj=1 aji Cj, and taking M$ = [a^] G Zr,r. Clearly, the following diagram Zr,1 zr,1 k| I« r -> r c is commutative, or in other words, evaluation of the automorphism $ is given by $(c) = k(m0c). 170 Ars Math. Contemp. 10 (2016) 126-181 Coming back to our original setting of evaluating the lifted automorphisms, recall from Preliminaries that in the abelian case the automorphism g# = g#uo does not depend on the base vertex, and that (gh)# = g#h#. Also, we shall simplify the notation for the matrix representing g# by writing Mj = Mg#. In view of (2.2) and (2.3), the formula for evaluating the lifted automorphism < at an arbitrary vertex (v, c) is now given by ^(c) = tj + g#(c) + g#(Zq) - CSiQ, where Q: v ^ u0 is an arbitrary walk. This can be rewritten in vector form as (c) = ti + MiC + MiCq - CgzQ. (5.1) So far we have overcome part of the problem: representation of g#'s by a 'closed formula'. However, since tj's and the vector c (which linearly depends on tj's when the formula is applied recursively while processing Rj) are symbolic variables, the evaluation requires symbolic computation - and that is something we still want to avoid. To this end we do the following. Let t = [tiT,t^T,... ,tnT]T G Zrn,i be the 'extended' column of all the vectors ti, t2,..., tn, and let E, = [0,..., 0,1,0,..., 0] G Zr,rn be the matrix consisting of n -1 zero submatrices 0 G Zr,r and one identity submatrix I G Zr,r at 'i-th position'. Clearly, tj = Ejt. At each iteration step of the evaluation we can express the vector c linearly in terms of t as c = Aj t + bj, for an appropriate matrix Aj G Zr,rn and vector bj G Zr,x, neither of which depends on t. Indeed. Suppose that while scanning the relator Rj from right to left we need to evaluate <7, at vertex (v, kc). Substituting c with Ajt + bj in (5.1) we get (c) = (Ej + MjAj)t + Mj (bj + ZQ) - ZgiQ, Q: v ^ u0, and so the label (kc) (the modified c as the input at the next step) is again of the form Aj t + bj, with Aj substituted by E, + MjAj and bj substituted by Mj(bj + Zq) - ZgiQ. Initially, Aj is the zero matrix and bj the zero vector. The method for evaluating the automorphism Rj (1, list M of n matrices Mj G Zr,r representing g# Output: matrix Aj G Zr,rn, vector bj G Zr>1 set Aj G Zr,rn to be the zero matrix and bj G Zr>1 the zero vector; v ^ u0; suppose Rj = gfci • • • gfcl; for i ^ 1 to l do (*scan word Rj from right to left*) Aj- ^ M[ki]Aj; (*multiply A^- on the left by Mfc. *) for s ^ 1 to r do (*add Efc. to Aj *) Aj [s][r * kj + s] ^ Aj [s][r * kj + s] + 1; let Zq G T and ZSfc.q G Z[kj] with Q : v ^ uo; 1: 2: 3 4 5 6 7 8 9 10 bj ^M[ki](6j + Zq) - Zgk^; v ^ gfci(v); return Aj, bj The problem of testing whether a given extension is split-admissible has now been reduced to an equivalent problem of checking whether the linear system (5.3) has a solution. Efficient algorithms for solving a system of linear equations over Z are long known, and are based on reducing the matrix of coefficients into Hermite or Smith normal form, see [23, Sections 9.2.3 and 9.2.4]. Theorem 5.2. Let X be a finite connected graph and G < Aut X a group of automorphisms given by a presentation G = (S | R), where S = {g^ g2,..., gn} is a generating set and Rj(g1, g2,..., gn) = id, j = 1,2,..., m, are the R-relations. Further, let p = pz : Cov(Z) ^ X be an abelian G-admissible regular covering projection of connected graphs arising from a Cayley voltage assignment Z : D(X ) ^ r. Suppose that the abelian group r is given by a presentation r = (A | A), where A = {c1, c2,..., cr} is a generating set and Ak(c1, c2,..., cr) = 0, k =1,2,..., s, are the A-relations. Then the short exact sequence id ^ CTP ^ G ^ G ^ id is split if and only if the system of linear equations (5.3) has a solution in Z. Moreover, let Q Ç rn be the set of all solutions of (5.3) reduced relative to the defining relations in A. Then Q is in bijective correspondence with all complements to CTP within G (which correspond to all derivations G ^ T), and two solutions in Q correspond to conjugate complements if and only if they differ by an inner derivation. Proof. In view of Proposition 5.1 and the above discussion it is clear that the extension splits if and only if the linear system (5.3) has an integer solution. It is also clear that each complement to CTp in G corresponds to some solution of (5.3), and hence to a solution in Q. Moreover, two distinct solutions from Q give rise to distinct complements. Indeed. Suppose that (t1, t2,..., tn) and (ti, t2,..., tJ are two distinct solutions from Q giving rise to the same complement G. Then there is an index i such that tj = tj, that is, g.j = g-. As gj and g- are two lifts of the same automorphism gj, we must have gj = idc gj, where idc G CTp. But since G is a complement to CTp we must have gj = gj, and therefore 170 Ars Math. Contemp. 10 (2016) 128-181 ti = ti, contrary to the assumption. It follows that all solutions in Q correspond bijectively to all complements. Let G and G be two conjugate complements. Without loss of generality we may assume they are conjugate by an element idc G CTP, that is, g' = idc G idc . Since for any g G G the elements idc <7 icic and g' from g' both project to g G G we must have g' = idc g idc , for all g G G. Rewrite as g' idc = idc g, and let g(u0, 0) = (gu0,tg) and g'(u0, 0) = (gu0,tg). Then the left hand side maps the vertex (u0,0) to (gu0, t'g + g#(c)), while the right hand side maps (u0,0) to (gu0, tg + c). Hence tg + g#(c) = tg + c, and so tg- tg = ¿c(g^ where ¿c G Inn(G, r) is an inner derivation. In particular, the above relation holds for (ti, t2,..., tn) and (tl, t2,..., tn) from Q giving rise to G and G . For the converse, let (ti, t2,..., tn) and (ti, t2,..., tn) from Q give rise to G and G such that ti - ti = ¿c(gi) for i = 1, 2..., n. Then we can work backwards to find that g' = idc gi iclc for all indices. Hence G and g' are conjugate subgroups. This completes the proof. □ Remark 5.3. Theorem 5.2 can be used to compute the first cohomology group H 1(G, r), c.f. [23, Section 7.6]. Next, observe that each solution (t1,t2,... ,tn) G Q extends uniquely to a function t: G ^ r satisfying condition (4.1), and that two such functions differ precisely by a derivation, t' - t g Der(G, r). Thus, the set of functions G ^ r satisfying condition (4.1) forms a coset of Der(G, r) in the group of all functions G ^ r equipped with pointwise addition. Consequently, an alternative proof of the last statement in Theorem 5.2 can be given using the standard result which states that two derivations give rise to conjugate complements if and only if they differ by an inner derivation. □ Remark 5.4. Algorithm Evaluate requires some precomputations. First, we need to compute the vectors Zq G Zr'\ for some Q : v ^ u0 and all v G V(X), and consequently, the vectors representing voltages of fundamental walks at u0. This can be done efficiently using breadth first search. During the search we also compute the vectors representing voltages of the mapped paths in order to obtain, upon completion of the search, the vectors ZgiQ G together with the vectors representing voltages of the mapped fundamental walks, for each gi. Second, with these data in hand we then build the systems of linear equations over Z whose solutions give rise to the matrices Mi g Zr,r representing g#. □ Theorem 5.2 can also be used for testing whether a given group lifts as a direct product extension. In view of Corollary 4.5 we first check if the condition Zgw = Zw holds for all g G S and all closed walks W from a basis of H1 (X, Z). If true then G lifts, and we test whether the extension splits by solving the linear system (5.3) using algorithm Evaluate with all g# = id. Algorithm Evaluate simplifies in that all matrices Mi are now equal to the identity matrix. Also, since the covering projection is abelian, recall that if some complement to CTP is normal, then all complements are normal. We record this formally as Corollary 5.5. A. Mainte: and R. Pozar: On the split structure of lifted groups 129 Corollary 5.5. With assumptions and notation above, id ^ CTP ^ G ^ G ^ id is a direct product extension if and only if the following two conditions are satisfied: (i) Cgw = Zw holds for all g G S and all closed walks W from a basis of H1(X, Z); (ii) the (simplified) system of linear equations (5.3) has a solution in Z. Moreover, in this case the set of solutions of (5.3), reduced relative to the defining relations in A, is in bijective correspondence with normal complements to CTP within G. □ 5.2 Elementary abelian covers One particular special case worth mentioning is that of CTP being elementary abelian. In this case, r can be identified with the vector space over the corresponding prime field, and the automorphisms of r are then viewed as invertible linear transformations. More precisely, let r = Zp. The generating set {c1,c2,... ,cr} is now understood to be the standard generating set (of a vector space), and (5.1) can be viewed as a formula in this vector space. Consequently, instead of (5.3) we need to find solutions of (5.2) over Zp, which can be done using Gaussian elimination. This makes computation easier; in particular, we do not experience difficulties which might otherwise be present with computations over Z (like uncontrolled integer growth). An algorithm for testing whether the extension is split now immediately follows from the above discussion. It is formally encoded in algorithm IsSplit. Algorithm: IsSplit Input: Cayley voltage assignment Z: D(X) ^ Zp giving rise to connected cover, automorphism group G = (g1,g2,... ,gn | R1,R2,..., Rm) that lifts Output: true, if the lifted group is split extension, false otherwise set A G Z0'dn to be the zero matrix and b G Z0'1 the zero vector; take an arbitrary vertex u0 in X; compute set T of |V(X)| vectors Zq G Zp'1 with Q : v ^ u0 for all v G V(X); 9 10 11 12 compute list Z of n sets each containing |V(X)| vectors ZgiQ G Zp'1; compute list M of n matrices Mi G Zd,d representing gf; for j ^ 1 to m do let Aj and bj be the output of evaluating the relator Rj at (u0,0) using the algorithm Evaluate; A A Aj b b l bj j if system At = —b has a solution then return true else return false Theorem 5.6. Let p = p^: Cov(Z) ^ X be an elementary abelian regular covering projection of connected graphs arising from a Cayley voltage assignment Z: D(X) ^ Zp. Further, let a given group of automorphisms G = (g1,g2,... ,gn | R1,R2,..., Rm) lift 170 Ars Math. Contemp. 10 (2016) 130-181 along p. Then the algorithm IsSplit tests whether the lifted group is a split extension of CTP by G in O(n|V (X )| + nd|D(X )| + d3r + nd2 r + nd3L + nd3m2) steps using O(n|V (X )| + nd|D(X )| + nd2m) memory space, where r is the Betti number of X and L = 2 m |Rj |. Proof. It remains to consider time and space complexity. The vectors Zwk representing the voltages of the fundamental walks Wk, k = 1, 2,..., r, at u0 together with the vectors CSiWfc representing the voltages of the mapped fundamental walks gjWfc, i = 1, 2,..., n, as well as the vectors Zq and ZgiQ can be computed as described in Remark 5.4 using breadth first search at the cost of O(d) steps per edge; altogether this takes O(n|V(X)| + nd|D(X)|) steps. As for constructing the matrices Mj G Zd,d we first need to solve d systems of linear equations: xi,i Zwi + xi,2 Zw2 +-----+ xi,r ZWr = e1 X2,1 Zwl + X2,2 ZW2 +-----+ X2,r ZWr = e2 . (5.4) xd,i Zwi + Xd,2 Zw2 + ••• + xd,r Zwr = ed, where ej's are the standard basis vectors of Zp>i. Solving d systems using Gaussian elimination requires O(d3r) steps. An arbitrary matrix Mj can then be computed in O(d2r) steps; thus O(nd2r) steps are required to compute n such matrices. Algorithm Evaluate takes O(nd3|Rj |) steps for evaluating an arbitrary relator Rj. Hence all relators can be evaluated in O(nd3L) steps, where L = J2j=i 2 m |Rj |. It remains to solve the system A b = -b for A G Zpm,dn and b G Zdn'1, which takes O(nd3m2) steps using Gaussian elimination. Hence the problem of testing whether the extension splits can be solved in O(n|V(X)| + nd|D(X)| + d3r + nd2r + nd3L + nd3m2) steps. Representing the graph X using adjacency list takes O(|V(X)| + |D(X)|) space, while representing a vector in Zd>i takes O(d) space. Therefore the representation of the Cayley voltage assignment Z takes O (| V (X )| + d|D(X )|) space. As for the representation of automorphisms as permutations, this takes O(n|D(X)|) space. During breadth first search we also need O(n|V(X)|) space to store the mapped vertices, and O(nd|D(X)|) additional space to store the voltages of the mapped walks. It takes O(nd2) space to store all the matrices Mj, while storing the matrix A G Z K1 > ... > Kn = id with elementary abelian factors Kj-1/Kj. The method is known, see [23, Chapter 8]. The covering projection p then decomposes as X = Xn ^ Xn-1 ^ ... ^ X1 ^ X0 = X, where pj: Xj ^ Xj-1 is a regular elementary abelian covering projection with CTPj isomorphic to Kj-1/Kj. At each step we may then recursively apply Lemma 5.8. To this end, one has to explicitly construct (among other things) the voltage assignments that define the intermediate projections in the above decomposition. For more details we refer the reader to [44]. 6 Concluding remarks In order to evaluate the performance of the above method for testing whether a given solvable covering projection is split-admissible the second author has implemented it in Magma [4], as a part of a larger package for computing with graph covers, see [43], and [44] for a more detailed account on experimental results. We further remark that in the case of solvable covers one can take an alternative approach that even does not require explicit reconstruction of the intermediate covering projections. It is enough to first compute the automorphisms g#uo and the factor set F(g, h) = g#"0 (Zq)Z-Q (partially as needed) in order to reconstruct the lifted group as a crossed product, and then consider the decomposition abstractly without reference to covers. This is discussed in [45]. Acknowledgement. The authors would like to thank the referee for detailed comments that helped us improve the presentation. References [1] D. Archdeacon, P. Gvozdjak and J. Siran, Constructing and forbidding automorphisms in lifted maps, Math. Slovaca 47 (1997), 113-129. [2] S. Bhoumik, T. Dobson and J. Morris, On the automorphism groups of almost all circulant graphs and digraphs, Ars Math. Contemp. 7 (2014), 499-518. [3] N. L. Biggs, Algebraic Graph Theory, Cambridge Univ. Press, Cambridge, 1974. [4] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language, J. Symbolic Comput. 24 (1997), 235-265. [5] F. Celler, J. Neubser and C. R.B. Wright, Some remarks on the computation of complements and normalizers in solvable groups, Acta Applicandae Mathematicae 21 (1990), 57-76. [6] M. D. E. Conder and P. Dobcsanyi, Trivalent symmetric graphs on up to 768 vertices, J. Com-bin. Math. Combin. Comput. 40 (2002), 41-63. [7] M. D. E. Conder and J. Ma, Arc-transitive abelian regular covers of cubic graphs, J. Algebra 387 (2013), 215-242. [8] M. D. E. Conder, A. Malnic, D. Marusic and P. Potocnik, A census of cubic semisymmetric graphs on up to 768 vertices, J. Algebraic Combin. 23 (2006), 255-294. [9] D. Z. Djokovic, Automorphisms of graphs and coverings, J. Combin. Theory Ser. B 16 (1974), 243-247. A. Mainte: and R. Pozar: On the split structure of lifted groups 133 [10] D. Z. Djokovic and G. L. Miller, Regular groups of automorphisms of cubic graphs, J. Combin Theory 29 (1980), 195-230. [11] S. F. Du, J. H. Kwak and M. Y. Xu, 2-arc-transitive regular covers of complete graphs having the covering transformation group Zp, J. Combin. Theory Ser. B 93 (2005), 73-93. [12] S. F. Du, A. Malnic and D. Marusic, Classification of 2-arc-transitive dihedrants, J. Combin. Theory Ser. B 98 (2008), 1349-1372. [13] S. F. Du, D. Marusic and A. O. Waller, On 2-arc transitive covers of complete graphs, J. Combin. Theory Ser. B 74 (1998), 276-290. [14] Y. Q. Feng and J. H. Kwak, Classifying cubic symmetric graphs of order 10p or 10p2, Science China Ser. A: Math 49 (2006), 300-319. [15] Y. Q. Feng, A. Malnic, D. Marusic and K. Kutnar, On 2-fold covers of graphs, J. Combin. Theory Ser. B 98 (2008), 324-341. [16] M. Giudici, C. H. Li and C. E. Praeger, Analysing finite locally s-arc transitive graphs, Trans. Amer. Math Soc. 356 (2004), 291-317. [17] R. Gramlich, G. W. Hofmann and K. H. Neeb, Semi-edges, reflections and Coxeter groups, Trans. Amer. Math. Soc. 359 (2007), 3647-3668. [18] J. L. Gross and S. R. Alpert, Branched coverings of graph imbeddings, Bull. Amer. Math. Soc. 79 (1973), 942-945. [19] J. L. Gross, Voltage graphs, Discrete Math. 9 (1974), 239-246. [20] J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley - Interscience, New York, 1987. [21] M. Hofmeister, Isomorphisms and automorphisms of graph coverings, Discrete Math. 98 (1991), 175-183. [22] M. Hofmeister, Graph covering projections arising from finite vector spaces over finite fields, Discrete Math. 143 (1995), 87-97. [23] D. Holt, B. Eick and E. A. O'Brien, Handbook of Computational Group Theory, Chapman and Hall/CRC, Boca Raton London New York Washington D.C., 2005. [24] A. Hujdurovic, Quasi m-Cayley circulants, Ars Math. Contemp. 6 (2013), 147-154. [25] H. Koike and I. Kovacs, Isomorphic tetravalent cyclic Haar graphs, Ars Math. Contemp. 7 (2014), 215-235. [26] I. Kovacs, K. Kutnar, D. Marusic, Classification of edge-transitive rose window graphs, J. Graph Theory 65 (2010), 216-231. [27] I. Kovacs, B. Kuzman and A. Malnic, On non-normal arc transitive 4-valent dihedrants, Acta Math. Sin. (Engl. ser.) 26 (2010), 1485-1498. [28] B. Kuzman, Arc-transitive elementary abelian covers of the complete graph K5, Linear Algebra Appl. 433 (2010), 1909-1921. [29] J. H. Kwak and J. Lee, Counting some finite-fold coverings of a graph, Graphs Combin. 8 (1992), 277-285. [30] J. H. Kwak and J. M. Oh, Arc-transitive elementary abelian covers of the octahedron graph, Linear Algebra Appl. 429 (2008), 2180-2198. [31] P. Lorimer, Vertex-transitive graphs: Symmetric graphs of prime valency, J.Graph Theory 8 (1984), 55-68. [32] A. Malnic, Group actions, coverings and lifts of automorphisms, Discrete Math. 182 (1998), 203-218. 170 Ars Math. Contemp. 10 (2016) 134-181 [33] A. Malnic, R. Nedela and M. Skoviera, Lifting graph automorphisms by voltage assignments, European J. Combin. 21 (2000), 927-947. [34] A. Malnic, Action graphs and coverings, Discrete Math. 244 (2002), 299-322. [35] A. Malnic, D. Marusic and P. Potocnik, Elementary abelian covers of graphs, J. Alg. Combin. 20 (2004), 71-96. [36] A. Malnic, D. Marusic and P. Potocnik, On cubic graphs admitting an edge-transitive solvable group, J. Algebraic Combin. 20 (2004), 99-113. [37] A. Malnics and P. Potocsnik, Invariant subspaces, duality, and covers of the Petersen graph, European J. Combin. 27 (2006), 971-989. [38] S. McLane, Homology, Springer-Verlag, Berlin Gottingen Heidelberg, 1963. [39] A. Mednykh and R. Nedela, Enumeration of unrooted maps a given genus, J. Combin. Theory Ser. B 96 (2006), 706-729. [40] P. Potocsnik, Edge-colourings of cubic graphs admitting a solvable vertex-transitive group of automorphisms, J. Combin. Theory Ser. B 91 (2004), 289-300. [41] P. Potocnik, M. Skoviera and R. Skrekovski, Nowhere-zero 3-flows in abelian Cayley graphs, Discrete math. 297 (2005), 119-127. [42] R. Pozsar, Sectional split extensions arising from lifts of groups, Ars Math. Contemp. 6 (2013), 393-408. [43] R. Pozar, http://osebje.famnit.upr.si/- rok.pozar [44] R. Pozsar, Some computational aspects of solvable regular covers of graphs, J. Symbolic Com-put. (2014), doi: 10.1016/j.jsc.2014.09.023 [45] R. PoZar, Testing whether the lifted group splits, Ars Math. Contemp., to appear. [46] C. E. Praeger, Imprimitive symmetric graphs, Ars Combin. 19 (1985), 149-163. [47] C. E. Praeger, An O'Nan-Scott Theorem for finite quasiprimitive permutation groups, and an application to 2-arc transitive graphs, J. London Math. Soc.(2) 47 (1993), 227-239. [48] S. Rees, L. H. Soicher, An algorithmic approach to fundamental groups and covers of combinatorial cell complexes, J. Symbolic Comput. 29 (2000), 59-77. [49] J. Siran, Coverings of graphs and maps, orthogonality, and eigenvectors, J. Algebraic Combin. 14 (2001), 57-72. [50] M. Skoviera, A contribution to the theory of voltage graphs, Discrete Math. 61 (1986), 281292. [51] A. Venkatesh, Covers in imprimitevely symmetric graphs, Honours dissertation, Department of Mathematics and Statistics, University of Western Australia, 1997. [52] C. Q. Wang and Y. H. Hao, Edge-transitive regular Zn -covers of the Heawood graph, Discrete Math. 310 (2010), 1752-1758. [53] L. Wang, S. F. Du and X. Li, A class of semisymmetric graphs, Ars Math. Contemp. 7 (2014), 40-53. [54] A. T. White, Graphs, Groups, and Surfaces, North-Holland, Amsterdam, 1984 (rev. ed.). [55] J. X. Zhou and Y. Q. Feng, Semisymmetric elementary abelian covers of the Heawood graph, Discrete Math 310 (2010), 3658-3662.