Classification of regular embeddings of n-dimensional cubes

DOI 10.1007/s10801-010-0242-8

Classification of regular embeddings of n-dimensional cubes

Domenico A. Catalano·Marston D.E. Conder· Shao Fei Du·Young Soo Kwon·Roman Nedela· Steve Wilson

Received: 25 October 2009 / Accepted: 14 June 2010 / Published online: 9 July 2010

© Springer Science+Business Media, LLC 2010

Abstract An orientably-regular map is a 2-cell embedding of a connected graph or multigraph into an orientable surface, such that the group of all orientation-preserving automorphisms of the embedding has a single orbit on the set of all arcs (incident vertex-edge pairs). Such embeddings of then-dimensional cubesQnwere classified for all oddnby Du, Kwak and Nedela in 2005, and in 2007, Jing Xu proved that for n=2mwheremis odd, they are precisely the embeddings constructed by Kwon in 2004. Here, we give a classification of orientably-regular embeddings ofQnfor alln.

In particular, we show that for all evenn(=2m), these embeddings are in one-to-one correspondence with elementsσ of order 1 or 2 in the symmetric groupSnsuch that σ fixesn, preserves the set of all pairsB_i= {i, i+m}for 1≤i≤m, and induces

D.A. Catalano

Departamento de Matemática, Universidade de Aveiro, 3810-193 Aveiro, Portugal e-mail:domenico@ua.pt

M.D.E. Conder (

Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand e-mail:m.conder@auckland.ac.nz

S.F. Du

School of Mathematical Sciences, Capital Normal University, Beijing 100048, China e-mail:dushf@mail.cnu.edu.cn

Y.S. Kwon

Department of Mathematics, Yeungnam University, Kyongsan 712-749, Republic of Korea e-mail:ysookwon@ynu.ac.kr

R. Nedela

Mathematical Institute, Slovak Academy of Sciences, 975 49 Banská Bystrica, Slovakia e-mail:nedela@savbb.sk

S. Wilson

Department of Mathematics and Statistics, Northern Arizona University, Flagstaff, AZ 86011, USA e-mail:Stephen.Wilson@nau.edu

the same permutation on this set as the permutationB_i→B_{f (i)}for some additive bijectionf :Zm→Zm. We also give formulae for the numbers of embeddings that are reflexible and chiral, respectively, showing that the ratio of reflexible to chiral embeddings tends to zero for large evenn.

Keywords Hypercubes·Cubes·Regular maps·Regular embeddings·Chiral

1 Introduction

A (topological) map is a cellular decomposition of a closed surface. A common way to describe such a map is to view it as a 2-cell embedding of a connected graph or multigraphX into the surfaceS. The components of the complementS\X are simply-connected regions called the faces of the map (or the embedding).

An automorphism of a mapM=(X, S) is an automorphism of the underlying (multi)graphXwhich extends to a self-homeomorphism of the supporting surfaceS.

It is well known that the automorphism group of a map acts semi-regularly on the set of all incident vertex-edge-face triples (sometimes called the flags ofM); in other words, every automorphism is uniquely determined by its effect on a given flag.

If for any given flag (v, e, f ) the automorphism group contains two automor- phisms that induce (respectively) a single cycle on the edges incident with v and a single cycle on the edges incident withf, then the mapMis called rotary. In the orientable case, this condition implies that the group of all orientation-preserving au- tomorphisms ofMacts regularly on the set of all incident vertex-edge pairs (or arcs) ofM, and we callM an orientably-regular map. Such maps fall into two classes:

those that admit also orientation-reversing automorphisms, which are called reflex- ible, and those that do not, which are chiral. In the non-orientable case (and in the reflexible case), the automorphism group acts regularly on flags, while in the chiral case, there are two orbits on flags, such that the two flags associated with each arc lie in different orbits.

A regular embedding (or more technically, a rotary embedding) of a graphX is then a 2-cell embedding ofXas a rotary map on some closed surface.

Classification of rotary maps by their underlying graphs is one of the central problems in topological graph theory. An abstract characterization of graphs hav- ing regular embeddings was given by Gardiner et al. in [12]. The classification problem has been solved only for few families of graphs, including the complete graphs [1,13,14], their canonical double covers [23], and complete multipartite graphsK_p,p,...,pfor primep[8,10]. Particular contributions towards the classifica- tion of regular embeddings of complete bipartite graphsK_n,ncan be found in papers [6,7,16,17,19,20,26], and this classification was recently completed by Gareth Jones [15]. In this paper we focus on the classification of regular embeddings of n-dimensional cubesQ_n.

The existence of at least two different regular embeddings ofQ_n for eachn >2 has been known for some time: in [24], Nedela and Škoviera constructed a regular embedding ofQ_nfor every solutioneof the congruencee²≡1 modn, with differ- ent solutions giving rise to non-isomorphic maps. Later, Du, Kwak and Nedela [9]

proved that there are no other regular embeddings of Q_n into orientable surfaces whennis odd. In contrast, Kwon [21] constructed new regular embeddings for all evenn6,by applying a ‘switch’ operator (as defined in [25]); he thereby also de- rived an exponential lower bound in terms ofnfor the number of non-isomorphic regular embeddings ofQ_n.

Recently, Jing Xu [28] proved that the embeddings constructed by Kwon cover all regular embeddings ofQ_n into orientable surfaces, whenn=2mfor oddm. In [22], Kwon and Nedela proved that there are no regular embeddings ofQ_ninto non- orientable surfaces, for all n >2. Also recently, the first and fifth authors of this paper gave a characterization of all orientably-regular embeddings ofQ_n (in terms of certain ‘quadrilateral identities’), and a construction for new regular embeddings ofQ_nfor allndivisible by 16, not covered by the family of embeddings found by Kwon; see [3].

The aim of the present paper is to classify the regular embeddings ofQ_nfor alln.

By [22], these are orientable forn >2, and by [9] they are known for all oddn, so we concentrate on the case wherenis even, sayn=2m.

In our main theorem (Theorem 5.1), we will show that when n=2m the orientably-regular embeddings are in one-to-one correspondence with elements σ of order 1 or 2 in the symmetric groupSn such thatσ fixesn, preserves the set of all pairsBi= {i, i+m}for 1≤i≤m, and induces the same permutation on this set as the permutationBi→Bf (i)for some additive bijectionf:Zm→Zm. (Note: by additive, we mean thatf (i+j )≡f (i)+f (j )modmfor alli, j∈Zm; and sinceσ² is trivial, this is equivalent tof being given byf:i→eifor some square rooteof 1 inZm(namelye=f (1)).) In particular, it follows that every regular embedding of Qnbelongs to one of the families constructed by Kwon [21] and Catalano and Nedela [3]. This also gives rise to formulae for the numbers of embeddings that are reflexible and chiral, respectively, which show that the ratio of reflexible to chiral embeddings tends to zero for large evenn.

Before proving our main theorem in Sect.5, we give some further background in Sects. 2 and 3, and introduce a reduction process in Sect. 4. Reflexibility and the enumeration formulae are then considered in Sect.6, and the genera and other properties of the resulting maps are dealt with in Sect.7.

2 Further background

Let M be an orientably-regular map, and let G=Aut^o(M) be the group of all orientation-preserving automorphisms ofM. Then G acts transitively on vertices, on edges, and on faces ofM; in particular, every face has the same sizek, say, and every vertex has the same degree (valency)m, say. The pair{k, m}is then called the type of the mapM.

Moreover, for any given flag(v, e, f )ofM, there exists an automorphismR in Ginducing a single-step rotation of the edges incident withf, and an automorphism S in G inducing a single-step rotation of the edges incident with v, with product RSan involutory automorphism that reverses the edgee. By connectedness,R and SgenerateG, which is therefore a quotient of the ordinary(k, m,2)triangle group

^o(k, m,2)= x, y|x^k=y^m=(xy)²=1(under an epimorphism taking x toR andytoS). The mapMis reflexible if and only if the groupGadmits an automor- phism of order 2 takingRtoR⁻¹andStoS⁻¹, or equivalently (by conjugation), an automorphism of order 2 takingStoS⁻¹andRStoS⁻¹R⁻¹=(RS)⁻¹=RS.

Conversely, given any epimorphismθ from^o(k, m,2)to a finite groupGwith torsion-free kernel, a mapM can be constructed using (right) cosets of the images ofx,yandxyas vertices, faces and edges, with incidence given by non-empty intersection, and thenGacts regularly on the arcs of M by (right) multiplication.

From this point of view the study of regular maps is simply the study of smooth finite quotients of triangle groups, with ‘smooth’ here meaning that the orders of the elementsx, yandxyare preserved.

An isomorphism between maps is an isomorphism between their underlying graphs that preserves oriented faces. Isomorphic regular maps have the same type, and therefore come from the same triangle group; in fact, two orientably-regular maps of the same type{k, m}are isomorphic if and only if they are obtainable from the same torsion-free normal subgroup of^o(k, m,2).

Rotary maps can be classified according to the genus or the Euler characteristic of the supporting surface, or by the underlying graph, or by the automorphism group of the map. Deep connections exist between maps and other branches of mathematics, which go far beyond group theory, and include hyperbolic geometry, Riemann sur- faces and, rather surprisingly, number fields and Galois theory, based on observations made by Bely˘ı and Grothendieck; see [18] for example.

The correspondence between rotary maps and normal subgroups of finite index in triangle groups has been exploited to develop the theory of such maps and produce or classify many families of examples. In particular, it was used by Conder and Dobc- sányi in [5] to determine all rotary maps of Euler characteristic−1 to−28 inclusive, and subsequently extended by Conder in [4] for characteristic−1 to−200.

Now we turn to the cube graphsQ_n.For each integern >1, then-dimensional cube graphQ_nis the graph on vertex-setV =Z2n,with two verticesu, v∈V adja- cent if and only if the Hamming distanced(u, v)between them is 1 (that is, if and only ifuandvdiffer in exactly one coordinate position).

The automorphism group ofQ_n is well known to be the wreath productZ2 S_n, which is a semi-direct productZ2nS_nofV =Z2n by the symmetric groupS_n. In particular, we may view any element of Aut(Qn)as a product of somev∈V with a permutation π∈S_n,and multiplication follows from the rule vπ =π v^π where v^π denotes the vector inV obtained fromv by applying the permutationπ to the coordinates ofv.

In any orientably-regular embedding ofQn, we may choose the rotationS about the vertexv=0 to be then-cycle ρ=(1,2,3, . . . , n) inSn, and then choose the rotationR about a facef incident withv so thatRS is the involutionenσ, where e_n=(0,0, . . . ,0,1)is thenth standard basis vector forV, andσ is a permutation of order 1 or 2 inS_nfixingn. This is explained further in [21], wheree0is used in place ofe_nfor the purposes of consistency with taking residues modulon.

For any such permutation σ (of order 1 or 2 and fixingn) in S_n, let G(σ )= ρ, e_nσ. By [21, Lemma 3.1], this subgroup of Aut(Qn)acts transitively on the arcs ofQ_n. Next, if G(σ )acts regularly on the arcs ofQ_n, so that|G(σ )| =n2ⁿ,

then we call the permutationσ an admissible involution (allowing an ‘involution’

to have order 1), and we denote the corresponding regular embedding byM(σ ). In particular, the identity permutationι is an admissible involution in Sn,giving the standard embeddingM(ι).

We can now state the following theorem.

Theorem 2.1 (Kwon [21, Theorem 3.1]) Every regular embedding ofQ_nis isomor- phic toM(σ )for some admissible involutionσ∈Sn.Moreover, for any admissible involutionsσ1, σ2∈Sn,the mapsM(σ1)andM(σ2)are isomorphic if and only if σ₁=σ₂.

Hence the classification of regular embeddings ofQ_n is equivalent to the clas- sification of admissible involutionsσ inS_n. We remark that forn=2 the standard embedding is the only regular orientable embedding ofQ2,and so from now on, we supposen >2.

For some time it has been known (see [24], for example) that for every square root eof 1 inZn,the mapping τ_e:Zn→Zn given by τ_e:i→ei(multiplication bye) gives rise to an admissible involution inSn(when we think of 0 asn).

The classification of regular embeddings ofQ_nfornodd was achieved by proving the following:

Theorem 2.2 (Du, Kwak & Nedela [9]) Ifn is odd and σ ∈S_n is an admissible involution, thenσ=τefor someesatisfyinge²≡1 modn.

In this paper we focus attention on the even-dimensional case. In this case, the following partial results are known:

Theorem 2.3 (Kwon [21, Theorems 4.1 & 5.2)] Forn=2m(even), letebe a square root of 1 inZn,and letχ_A be the characteristic function of a subsetA⊆Zn\ {0}

preserved byτe, ρ^m, whereρ=(1,2, . . . , n). Then the mappingσ:Zn→Zngiven by

σ:i→ei+mχA(i) (K)

gives an admissible involution inS_n.

Theorem 2.4 (Catalano & Nedela [3, Theorem 5.3]) Forn=2mwheremis divisible by 8, letebe a square root ofm+1 inZn,and letχAbe the characteristic function of a subsetA⊆Zn\ {0}such thatχ_A(i+m)=χ_A(i)andχ_A(ei)≡χ_A(i)+imod 2 for alli∈Zn. Then the mappingσ:Zn→Zngiven by

σ:i→ei+mχ_A(i) (CN)

is an admissible involution.

Admissible involutions defined by (K) and (CN) may be called K-involutions and CN-involutions, respectively. Jing Xu extended the classification fornodd to the case n=2mwheremis odd, by proving the following:

Theorem 2.5 (Xu [28]) Letn=2mwhere mis odd. Then an involution σ inS_n fixingnis admissible if and only if it is a K-involution.

One may observe that any K- or CN-involution commutes withρ^m, whenn=2m.

In fact, this holds for any admissible involution:

Proposition 2.6 LetH be a permutation group of even degree 2mcontaining a reg- ular element y (acting as a 2m-cycle), such that the stabilizer of each point is a 2-group. Theny^mis central inH, so themorbits ofy^mform a system of imprimi- tivity forH.

Proof We prove this by induction onm. If m=1 then the result is trivial. Now supposem >1. The lengths of orbits of a point-stabilizerH_αare powers of 2, so the fixed point setP ofH_αmust have even size. If|P| =2m, thenH= yand the result is immediate. If not, thenP is a block of imprimitivity forH, and the action of the setwise stabilizerH_{P} onP satisfies the hypotheses, withy^2m/|P|acting regularly, so that by induction, we may assume thaty^mis central inH_{P}and that the orbits of y^monP form a system of imprimitivity forH_{P}. It then follows that the translates of those orbits form a system of imprimitivity forH. As y^m induces a 2-cycle on

each such block,y^mis central inH.

Corollary 2.7 Ifσ is any admissible involution inS2m, thenσ commutes withρ^m, and the orbits{i, i+m}ofρ^mform a system of imprimitivity forρ, σ.

3 Some technical observations

Let{e1, e2, . . . , en}be the standard orthonormal basis forV =Z2n, and for any subset J of{1,2, . . . , n}, lete_J be the characteristic vector ofJ (so thate_{i}=e_i for alli).

Then multiplication inZ2 S_n∼=V S_nis given by

(eJπ )(eKμ)=eLπ μ forJ, K⊆ {1,2, . . . , n}andπ, μ∈Sn, whereLis the symmetric difference ofJ andK^π−1.

Now supposeσ is an admissible involution inS_n, soG(σ )= ρ, e_nσhas order n2ⁿ. For 1≤i≤n, conjugatinge_nσ by powers ofρgivesρ⁻ⁱ(e_nσ )ρⁱ=e_i(ρ⁻ⁱσρⁱ) as an element ofG(σ ), and the above multiplication then gives elements inG(σ )of the forme_Lθfor every subsetLof{1,2, . . . , n}. Furthermore, post-multiplication by powers ofρgives at leastnpossibilities for the elementθinSn, for each subsetL.

In fact since|G(σ )| =n2ⁿ, we have the following:

Lemma 3.1 Ifσ is an admissible involution inS_n, then for eachL⊆ {1,2, . . . , n}, the set of all elements ofG(σ )of the formeLπ forπ∈Sn is a left coset ofρ, of sizen.

In particular, for eachi∈ {1,2, . . . , n}there is a unique permutationγ_i∈S_nfixing nsuch thateiγi ∈G(σ ). Clearlyγn=σ, and more generally, sinceG(σ )contains ρ⁻ⁱ(e_nσ )ρⁱ=e_i(ρ⁻ⁱσρⁱ),we find thatγ_i=ρ⁻ⁱσρ^−(−i)σ for 1≤i≤n.

This leads to an alternative proof of the quadrilateral identities given in [3], in- volving the permutationτ inS_ninduced by multiplication by−1 inZn:

Proposition 3.2 Ifσ is an admissible involution inSn, then σρ^jσρ^{jσ τ}σρ^{j(σ τ )}

2

σρ^{j(σ τ )}

3 =1 for allj∈Zn. (∗) Proof First note that ifi∈ {1,2, . . . , n}andi^γn=i^σ=then

(eiγi)(enγn)=eienγiγn while(enγn)(eγ)=eneiγnγ.

Bute_ie_n=e_ne_i sinceV is Abelian, andγ_iγ_nandγ_nγboth fixn, so we deduce that γ_iγ_n=γ_nγ whenever=i^σ.

Nowγ_iγ_n=ρ⁻ⁱσρ^−(−i)σσ while γ_nγ =σρ⁻σρ^−(−)σ =σρ^−iσσρ^{−(−iσ)σ}, and hence

1=(γ_iγ_n)⁻¹γ_nγ=

σρ^(−i)σσρⁱ

σρ^−iσσρ^{−(−iσ)σ}

=σρ^{iτ σ}σρⁱσρ^{iσ τ}σρ^{i(σ τ )}

2

.

Takingi=j^{σ τ} (or, equivalently,j=i^{τ σ}) gives the required identity.

Corollary 3.3 Ifσis an admissible involution inS_n, then(σ τ )⁴=1.

Proof Takej=k^{σ τ}in the above identity, to obtainσρ^{kσ τ}σρ^{k(σ τ )}

2

σρ^{k(σ τ )}

3

σρ^{k(σ τ )}

4 =1, and put this together with σρ^kσρ^{kσ τ}σρ^{k(σ τ )}

2

σρ^{k(σ τ )}

3 =1, to give ρ^{k(σ τ )}

4 =ρ^k for

allk.

The converse of Proposition3.2holds as well. This was shown in [3], but again we give an alternative proof (below).

Proposition 3.4 Ifσis an involution inS_nthat fixesnand satisfies the quadrilateral identities (∗), thenσ is admissible.

Proof We prove thatG(σ )= ρ, e_nσhas ordern2ⁿ, by showing it contains a unique left coset of the forme_Lγ_Lρwithγ_L∈S_nfixingn, for everyL⊆ {1,2, . . . , n}.

Defineγ_i=ρ⁻ⁱσρ^−(−i)σ for 1≤i≤n, as previously. Then eachγ_i is an element ofS_nfixingnsuch thate_iγ_i=ρ⁻ⁱ(e_nσ )ρⁱρ^{−(−i)σ−i} lies inG(σ ). Moreover, since G(σ )= ρ, e_nσ, every elementwofG(σ )can be expressed as a product of conju- gates ofe_nσ by powers ofρ, followed by some power ofρ, and hence has the form w=e_i1γ_i1e_i2γ_i2· · ·e_irγ_irρ^sfor somei1, i2, . . . , i_r ands. The multiplication rule

(eaγa)(ebγb)=(eaec)γaγb wheneverb=c^γa

can then be used to rewrite w in the form w=e_Lγ_i1γ_i2· · ·γ_irρ^s for some L⊆ {1,2, . . . , n}.

The quadrilateral identities (∗) imply that for givenL, the elementγ_i1γ_i2· · ·γ_ir is uniquely determined.

To see this, note that if b =c^γa and d =a^γc, then the above multiplica- tion rule gives(e_aγ_a)(e_bγ_b)=(e_ae_c)γ_aγ_b while(e_cγ_c)(e_dγ_d)=(e_ce_a)γ_cγ_d. Since e_ae_c=e_ce_a, all we have to do is to prove that γ_aγ_b=γ_cγ_d wheneverb=c^γa = c^{ρ−aσρ−(−a)σ} =(c−a)^σ−(−a)^σ andd=a^γc=a^{ρ−cσρ−(−c)σ} =(a−c)^σ −(−c)^σ. The quadrilateral identity forj=(a−c)^σ is

1=σρ^(a−c)σσρ^c−aσρ^{(c−a)σ τ}σρ^{(c−a)(σ τ )}

2

,

which can be rewritten as 1=σρ^d+(−c)σσρ^c−aσρ^{−(−a)σ−b}σρ^{(c−a)(σ τ )}

2

. Upon con- jugation this becomes

1=ρ^−aσρ^{−(−a)σ−b}σρ^{(c−a)(σ τ )}

2

σρ^d+(−c)σσρ^c,

which can be rewritten as 1=γ_aγ_bρ^uγ_d⁻¹γ_c⁻¹whereu=(−b)^σ +(c−a)^{(σ τ )2}− (−d)^σ. Thus(γaγb)⁻¹γcγd=ρ^u, and as the left-hand side of this identity fixesn, we findρ^u=1, so(γaγb)⁻¹γcγd=1 and thereforeγaγb=γcγd, as required.

Corollary 3.5 Letσ be any involution inS_2m such thatσ fixesn=2m, preserves the set of all pairsB_i= {i, i+m}for 1≤i≤m, and induces the same permutation on this set as the permutationB_i→B_{f (i)}for some additive bijectionf :Zm→Zm. Thenσ is admissible.

Proof It is an easy exercise to verify thatσ satisfies the quadrilateral identities (∗).

Note that the condition thatσpreserves the set{Bi:1≤i≤m}is equivalent toσ commuting withρ^m=(1, m+1)(2, m+2)· · ·(m,2m).

4 Reduction

In this section we describe a reduction from the case ofQ_nto the case ofQ_mwhen n=2m(even). This can be used to provide an alternative proof of Theorem2.5, as well as assist with the proof of our main theorem in the next section. To do this, we consider the natural action of the wreath productZ2 S_n on the set {1,2, . . . ,2n}, with block-set{{i, i+n} :1≤i≤n}preserved by V =Z2n and permuted by S_n. Indeed lete_i induce the transposition(i, i+n)for 1≤i≤n, and letρ induce the permutation(1,2, . . . , n)(n+1, n+2, . . . ,2n).

Lemma 4.1 Supposen=2m, andσ is an admissible involution inS_n. LetKbe the subgroup ofZ2 S_ngenerated byρ^mande_ie_i+mfor 1≤i≤m. ThenKis an Abelian subgroup ofG(σ ), of order 2^m+1. Moreover,K is a normal subgroup ofG(σ ), and consists of all elements that preserve each of the sets P_i = {{i, i+m},{i+2m, i+3m}}(and each of the setsQ_i= {{i, i+3m},{i+2m, i+m}}),for 1≤i≤m.

Proof First, let G=G(σ ), and let γ_j =ρ^−jσρ^{−(−j )σ} be the elements defined in Sect.3. By Corollary2.7, we know thatσ permutes the setsB_i = {i, i+m}among themselves, and hence that(i+m)^σ =i^σ +m (modn) for alli. Then since ρ^m commutes withσ, we find that

γ_i+m=ρ^−(i+m)σρ^{−(−(i+m))σ}=ρ⁻ⁱρ^−mσρ^mρ^−(−i)σ

=ρ⁻ⁱσρ^−(−i)σ =γ_i for 1≤i≤m.

In particular, asGcontainse_iγ_i ande_i+mγ_i+m=e_i+mγ_i, it follows thatGcontains (eiγi)(ei+mγi)⁻¹=eiei+mfor alli, soKis a subgroup ofG. Also the generators of Kare commuting involutions, soKis Abelian, of order 2^m+1.

Observe that bothρ andσ centralizeρ^mand conjugate thee_ie_i+mamong them- selves, whileen centralizes all the eiei+m and conjugates ρ^m toeme2mρ^m. It fol- lows thatKis normalized by each ofρ, σ ande_n, and in particular,Kis normal in ρ, e_nσ =G.

Next, letH be the stabilizer inGof the two pointsmand 2m(or equivalently, of the four pointsm,2m,3mand 4m). Since the stabilizer inGofmfixes 3mand has {2m,4m}as one of its orbits, and has index 2n=4minG, this subgroupHhas index 4ninG, so has order 2ⁿ⁻². Now consider the subgroupH K. The intersectionH∩K contains all thee_ie_i+m fori=m,2m, but does not containe_me_2m,ρ^more_me_2mρ^m (which takem to 3m,2mand 4mrespectively), so H∩K has index 4 in K and therefore has order 2^m−1. Thus|H K| = |H||K|/|H∩K| =2^n−2+m+1/2^m−1=2ⁿ, so the index ofH K inGisn=2m. It follows thatH K is the stabilizer inGof the setP_m= {{m,2m},{3m,4m}}, the images of which under other elements ofGare the setsPi andQi given in the statement of this Lemma. Moreover, the core ofH inGis trivial (being the stabilizer of all points), so the core ofH K inGisK. This

completes the proof.

The above lemma gives a quotientG(σ )/K that acts transitively on a set of size 2m, namely the set of all Pi and Qi. The permutation induced byρ is a pair of m-cycles, namely(P₁, P₂, . . . , P_m)and(Q₁, Q₂, . . . , Q_m). But also the generators e_i of V =Z2n

and the involution σ induce permutations of this set, with each e_i interchanging the pointsPi andQi while fixing all others, and σ inducing effec- tively the same permutation on theQ_i as it does on theP_i. In particular, since σ commutes withρ^m, the orbits{P_i, P_i+m}and{Q_i, Q_i+m}ofρ^mform a system of imprimitivity forG(σ )/K, which accordingly can be viewed as a subgroup of the wreath productZ2 S_m. Furthermore, we may note thatσ fixesQ_m (andP_m), and hence thate_nσ interchangesP_mandQ_mwhile otherwise acting to preserve the sets {P1, P2, . . . , Pm−1}and{Q1, Q2, . . . , Qm−1}.

In other words,Kis the kernel of a reduction, fromG(σ )as a subgroup ofZ2 S_n, toG(σ )/Kwhich is a subgroup ofZ2 S_min its natural action on theP_iandQ_i(with {Pi, Qi}as the ‘base pairs’). In particular,G/Khas order 2^mm, and is the group of orientation-preserving automorphisms of a regular embedding ofQ_m.

In fact this permutation induced byσ is effectively the same as the one induced byσ on the blocksBi= {i, i+m}of the natural action ofρ, σon{1,2, . . . , n}. This gives another way of defining the reduction. As explained in [3], we may di- rectly define the projectionsρ andσ ofρ andσ inS_m by lettingi^ρ andi^σ be the

residues modmofi^ρandi^σ respectively, for 1≤i≤m. Thenσ obviously satisfies the quadrilateral identities, and is therefore an admissible involution inS_m. Recipro- cally, we may callσ an admissible lift ofσ. By the above remarks, we now have the following:

Proposition 4.2 Every admissible involutionσ ∈S2m is an admissible lift of some admissible involution inSm.

Note that every K-involution and every CN-involution inS2mis an admissible lift of the involutionτe:Zm→Zm given by multiplication by some square rooteof 1 inZm. This was observed in [3], where it was also proved that every admissible lift of such an involutionτ_e in S_m is a K-involution or CN-involution inS_2m; see [3, Theorem 5.3].

We also now have the following:

Alternative proof of Theorem2.5 Forn=2mwheremis odd, letσ be an admissible involution inSn. By the above reduction, σ is an admissible involution in Sm, so by Theorem2.2, we know that σ =τe for some square root e of 1 in Zm. Now replaceebye+mifeis even. Thene²≡1 mod 2 and modm, soe²≡1 modn.

TakingA= {i∈Zn:i^σ=ei (modn)} = {i∈Zn:i^σ=ei+m (modn)}, we see that 0∈Aand thatAis preserved by bothρ^mand multiplication byemodn, soσ is a

K-involution.

5 Classification theorem

In this section, we give a characterization of all admissible involutions inS2m, for every positive integerm. When taken together with Theorem2.2, this gives a com- plete classification of all regular embeddings of hypercubesQn.

Theorem 5.1 Letn=2mbe an even positive integer, and let ρ=(1,2,3, . . . , n) inSn. Then every regular embedding ofQn is isomorphic to the embeddingM(σ ) for some permutationσ of order 1 or 2 inS_nand fixingn, such that:

(1) σ commutes withρ^m, so that the setsBi = {i, i+m}(for 1≤i≤m) form a system of imprimitivity forρ, σon{1,2, . . . , n}, and

(2) σ permutes the blocksB_i in the same way as the permutationB_i→B_{f (i)}for some additive bijectionf:Zm→Zm.

Moreover, every suchσ gives a regular embedding ofQ_n, and distinctσ give non- isomorphic embeddings.

Part (1) follows from Corollary2.7, and we will prove part (2) by induction onm.

We have already seen that whenm is odd, this follows from Theorem2.5, so we suppose thatmis even, saym=2k, and letσ be any admissible involution inS2m. By the reduction described in Sect.4, we know that the action ofσ on the blocksBi

is the same as that of an admissible involutionσ inS_m, and now by induction, we may assume that the projection ofσ inS_kis an additive bijection fromZk toZk.

Lete=1^σ if this is odd, or otherwise lete=1^σ +k(which will be odd, since kis odd when 1^σ is even). Then by additivity of the projection ofσ inS_k, we can prove by induction thati^σ ≡eimodkfor alli∈Zn. Hence we may define a function ψ:Zn→Z4satisfying

i^σ =ei+kψ (i) for alli∈Zn.

The remainder of our proof will depend heavily on properties of this functionψand related objects.

Lemma 5.2 Ife∈Znandψ:Zn→Z4are defined as above, then:

(a) ψ (0)=ψ (m)=0,andψ (k)andψ (3k)are both even;

(b) e²≡δk+1 modnfor someδ∈Z4;

(c) δi+eψ (i)+ψ (i^σ)≡0 mod 4, for alli∈Zn; (d) ψ (i+m)=ψ (i)for alli∈Zn;

(e) ψ (i+k)≡ψ (i)mod 2 for alli∈Zn.

Proof Parts (a) and (b) are obvious from the definitions. For part (c), observe that i=

i^σ_σ

=ei^σ+kψ i^σ

=e

ei+kψ (i) +kψ

i^σ

=i+k

δi+eψ (i)+ψ i^σ inZn,since e²=1+kδ by part (b). Part (d) is a consequence of the fact thatσ commutes withρ^m:

0=(i+m)^σ− i^σ+m

=em+k

ψ (i+m)−ψ (i)

−m

=k

ψ (i+m)−ψ (i) .

Similarly,(i+k)^σ−i^σ=ek+k(ψ (i+k)−ψ (i))=k(e+ψ (i+k)−ψ (i)),and since the left-hand side is eitherkor 3k(modn), andeis odd, we obtain part (e).

We wish to prove thatσ is additive when reduced modulom. Now since (i+j )^σ−i^σ−j^σ =e(i+j )+kψ (i+j )−ei−kψ (i)−ej−kψ (j )

=k

ψ (i+j )−ψ (i)−ψ (j ) we can define

ψ (i, j )=ψ (i+j )−ψ (i)−ψ (j ) inZ4, and then it suffices to prove thatψ (i, j )is even for alli, j∈Zn.

We will call a pair(i, j )good ifψ (i, j )is even, and bad otherwise. In a sequence of further observations (Lemma5.3to Proposition5.18) we will prove that there are no bad pairs, and henceσ is an admissible lift of its additive projectionσ. Note here that−i^σ stands for−(i^σ), rather than(−i)^σ (which can differ from−(i^σ)).

Lemma 5.3 ψ (i^σ,−i^σ)≡ψ (ei,−ei)≡ψ (i,−i)mod 2 for alli∈Zn.

Proof Sincei^σ =ei+kψ (i),we haveψ (i^σ)≡ψ (ei)mod 2 by Lemma5.2(e), and similarly,ψ (−i^σ)≡ψ (−ei)mod 2. Then by Lemma5.2(c) and sinceeis odd we find thatψ (ei)≡ψ (i^σ)≡ −δi−eψ (i)≡ −δi−ψ (i)mod 2, and replacingiby−i gives alsoψ (−ei)≡δi−ψ (−i).Adding these last two congruences gives

ψ i^σ

+ψ

−i^σ

≡ψ (ei)+ψ (−ei)≡ −ψ (i)−ψ (−i)≡ψ (i)+ψ (−i)mod 2, and the rest follows sinceψ (t,−t )=ψ (0)−ψ (t )−ψ (−t )= −(ψ (t )+ψ (−t ))for

allt.

Corollary 5.4 i^{(σ τ )2}≡i+kψ (i,−i)modmfor alli∈Zn. Proof

i^{(σ τ )2}= −

−i^σσ

=ei^σ −kψ

−i^σ

=e

ei+kψ (i)

−kψ

−i^σ

=i+k

δi+eψ (i)−ψ

−i^σ

by Lemma5.2(b)

=i+k

−ψ i^σ

−ψ

−i^σ

by Lemma5.2(c)

=i+kψ

i^σ,−i^σ ,

and thusi^{(σ τ )2}≡i+kψ (i,−i)modm, by Lemma5.3.

Lemma 5.5 ψ (i, j )+ψ (i+kψ (i,−i), j+kψ (i, j ))≡0 mod 4 for alli, j∈Zn. Proof First we observe that for everyt, i∈Zn, Lemma5.2gives

t^{σρiσρiσ τ} = i+t^σσ

−i^σ

=et^σ+k ψ

i+t^σ

−ψ (i)

=e

et+kψ (t ) +k

ψ i+t^σ

−ψ (i)

=t+k

δt+eψ (t )+ψ i+t^σ

−ψ (i)

by Lemma5.2(b)

=t+k

−ψ t^σ

+ψ i+t^σ

−ψ (i)

by Lemma5.2(c)

=t+kψ i, t^σ

.

Replacingt byt^{σρiσρiσ τ} andibyi^{(σ τ )2} here, and applying the quadrilateral identity (∗) fortthen gives

t=t^{σρiσρiσ τ} +kψ

i^{(σ τ )2}, t^{σρiσρiσ τσ}

=t+k ψ

i, t^σ +ψ

i^{(σ τ )2}, t^{σρiσρiσ τσ}

=t+k ψ

i, t^σ +ψ

i^{(σ τ )2}, t+kψ

i, t^σ_σ

by the above.

Lettingt=j^σ (so that alsoj=t^σ), we find that ψ (i, j )+ψ

i^{(σ τ )2},

j^σ+kψ (i, j )σ

≡0 mod 4.

Further application of Lemma5.2gives j^σ+kψ (i, j )σ

=e

j^σ+kψ (i, j ) +kψ

j^σ+kψ (i, j )

=e

ej+kψ (j )+kψ (i, j ) +kψ

j^σ+kψ (i, j )

=j+k

δj+eψ (j )+eψ (i, j )+ψ

j^σ+kψ (i, j )

by Lemma5.2(b)

=j+k

−ψ j^σ

+ψ

j^σ+kψ (i, j )

+eψ (i, j )

by Lemma5.2(c)

≡j+keψ (i, j )modm by Lemma5.2(e)

≡j+kψ (i, j )modm sinceeis odd,

and inserting this into the previous equation (and using Lemma5.2(d)) we obtain ψ (i, j )+ψ

i^{(σ τ )2}, j+kψ (i, j )

≡0 mod 4.

On the other hand, by Lemma5.4we havei^{(σ τ )2}≡i+kψ (i,−i)modm, and so the

required congruence follows from Lemma5.2(d).

Next, by Lemma5.2(e), we may define another functionc:Zn→Z2

ψ (t+k)=ψ (t )+2c(t ) for allt∈Zn.

It is easy to see thatc(0)=c(m)=0, and thatψ (t+kd)=ψ (t )+2dc(t )for alld, again by parts (d) and (e) of Lemma5.2. We use this function and the previous lemma to prove the following:

Lemma 5.6 ψ (i,−i)is even, for alli∈Zn.

Proof Assume the contrary, so thatψ (i,−i)is odd for somei. By Lemma5.5and the definition ofc, for alli, j∈Znwe have

0≡ψ (i, j )+ψ

i+kψ (i,−i), j+kψ (i, j )

≡ψ (i, j )+ψ

i+j+k

ψ (i,−i)+ψ (i, j )

−ψ

i+kψ (i,−i)

−ψ

j+kψ (i, j )

≡2ψ (i, j )+2

ψ (i,−i)+ψ (i, j ) c(i+j )

−2ψ (i,−i)c(i)−2ψ (i, j )c(j )mod 4, and hence (from the assumption thatψ (i,−i)is odd), we have

ψ (i, j )+

1+ψ (i, j )

c(i+j )−c(i)−ψ (i, j )c(j )≡0 mod 2, or equivalently,

1+ψ (i, j )

c(i+j )≡c(i)+ψ (i, j )

c(j )−1 mod 2.

This can be used to prove by induction thatc(t )=c(i)whenevert is a multiple of i inZn. For if that is true for t =j, then ψ (i, j )must be even (or otherwise (1+ψ (i, j ))c(i+j )would be even whilec(i)+ψ (i, j )(c(j )−1)≡2c(i)−1≡ 1 mod 2); and it then follows easily thatc(i+j )≡(1+ψ (i, j ))c(i+j )≡c(i)mod 2, so it is true also fort=i+j.

But on the other hand, sincec(0)=0 andψ (i,−i)is odd, takingj = −iin the last displayed congruence above gives

0≡c(i)+c(−i)−1 mod 2,

soc(−i)=c(i), a contradiction. This completes the proof.

Corollary 5.7 (σ τ )²acts trivially modulom; that is,i^{(σ τ )2}≡imodmfor alli∈Zn. Proof We knowi^{(σ τ )2}≡i+kψ (i,−i)modm, by Corollary5.4, and the rest follows

from Lemma5.6.

Also Lemma5.6can be used to provide a simpler version of Lemma5.5:

Corollary 5.8 ψ (i, j )((1+c(i+j )−c(j ))≡0 mod 2 for alli, j∈Zn. Proof First Lemma5.5gives this congruence mod 4:

0≡ψ (i, j )+ψ

i+kψ (i,−i), j+kψ (i, j )

≡ψ (i, j )+ψ

i+j+k

ψ (i,−i)+ψ (i, j )

−ψ

i+kψ (i,−i)

−ψ

j+kψ (i, j ) .

Sinceψ (i,−i)is even, it follows that 0≡ψ (i, j )+ψ

i+j+kψ (i, j )

−ψ (i)−ψ

j+kψ (i, j )

by Lemma5.2(d)

≡2ψ (i, j )+2ψ (i, j )c(i+j )−2ψ (i, j )c(j ) by the definition ofc

≡2ψ (i, j )

1+c(i+j )−c(j ) mod 4,

and the result follows.

Lemma 5.9 c(i+k)=c(i)andc(ei)=c(i)for alli∈Zn. Proof The first of these is an easy consequence of the following:

ψ (i)=ψ (i+m)=ψ (i+k+k)=ψ (i+k)+2c(i+k)

=ψ (i)+2c(i)+2c(i+k).

For the second, note that by Lemma5.2(c) and the definitions ofψandc, we have 0≡iδ+eψ (i)+ψ (ei)+2c(ei)ψ (i)mod 4.

Replacingibyi+k, we have also

0≡(i+k)δ+eψ (i+k)+ψ (ei+ek)+2c(ei+ek)ψ (i+k)mod 4.

But nowψ (ei+ek)=ψ (ei)+2ec(ei), and by what we proved above,c(ei+ek)= c(ei), so the latter congruence can be rewritten as

0≡(i+k)δ+eψ (i+k)+ψ (ei)+2ec(ei)+2c(ei)ψ (i+k)mod 4.

Subtracting the earlier congruence (namely the one fori) from this one (fori+k), and again usingψ (i+k)=ψ (i)+2c(i), we find that

0≡kδ+2ec(i)+2ec(ei)+4c(ei)c(i)≡kδ+2e

c(i)+c(ei) mod 4.

Finally, sinceeis odd andnis divisible by 4, we know thatkδ+1≡e²≡1 mod 4,

and soc(i)+c(ei)must be even.

Corollary 5.10 iδ+(e+2c(i))ψ (i)+ψ (ei)≡0 mod 4 for alli∈Zn.

Proof We observed that 0≡iδ+eψ (i)+ψ (ei)+2c(ei)ψ (i)mod 4 in the proof of

Lemma5.9. Sincec(ei)=c(i), the result follows.

Next, recall that a pair(i, j )is good ifψ (i, j )=ψ (i+j )−ψ (i)−ψ (j )is even, or equivalently, if(i+j )^σ ≡i^σ+j^σ modm, and bad otherwise. Clearly(i,0)and (0, j )are good for alliandj. Moreover, since(i+m)^σ =i^σ +m=i^σ +m^σ, we know that(i, m)is good, for alli∈Zn, and it follows that(i, mj )is good for allj. We also have the following:

Lemma 5.11 If(i, j )is a bad pair, then the pairs(j, i),(i^σ, j^σ),(j^σ, i^σ),(−i,−j ), (−j,−i)and(−i, i+j )are all bad.

Proof The first of these six follows from the definition, the second one from σ²=1, and the third is a combination of the first two. The fourth and fifth fol- low from Corollary 5.7. For the last one, note that j^σ ≡(−i)^σ +(i +j )^σ ≡

−(i^σ)+(i+j )^σ modm.

Lemma 5.12 If(i, j )is a bad pair, then c(i)=c(j )=c

−(i+j )

=c(−i)=c(−j )=c(i+j ).

Equivalently, if c(u) and c(v)have opposite parities, then the pair(u, v) must be good.

Proof By Lemma5.8, we know thatψ (i, j )((1+c(i+j )−c(j ))≡0 mod 2 for every pair(i, j ), whether good or bad. Now if(i, j )is bad, thenψ (i, j )is odd, and therefore 1+c(i+j )−c(j )is even, soc(j )andc(i+j )have opposite parities. The

rest follows from Lemma5.11.