• 検索結果がありません。

Elementary abelian p-groups of rank 2p + 3 are not CI-groups

N/A
N/A
Protected

Academic year: 2022

シェア "Elementary abelian p-groups of rank 2p + 3 are not CI-groups"

Copied!
13
0
0

読み込み中.... (全文を見る)

全文

(1)

DOI 10.1007/s10801-011-0273-9

Elementary abelian p-groups of rank 2p + 3 are not CI-groups

Gábor Somlai

Received: 7 December 2009 / Accepted: 6 January 2011 / Published online: 2 February 2011

© Springer Science+Business Media, LLC 2011

Abstract For every primep >2 we exhibit a Cayley graph onZ2pp +3which is not a CI-graph. This proves that an elementary abelianp-group of rank greater than or equal to 2p+3 is not a CI-group. The proof is elementary and uses only multivariate polynomials and basic tools of linear algebra. Moreover, we apply our technique to give a uniform explanation for the recent works of Muzychuk and Spiga concerning the problem.

Keywords Cayley graph·CI-group·Elementary abelianp-group

1 Introduction

LetGbe a finite group andSa subset ofG. The Cayley graph Cay(G, S)is defined by having the vertex setGandgis adjacent tohif and only ifgh1S. The setSis called the connection set of the Cayley graph Cay(G, S). A Cayley graph Cay(G, S) is undirected if and only ifS=S1, whereS1= {s1G|sS}. Every right multiplication via elements ofGis an automorphism of Cay(G, S), so the automor- phism group of every Cayley graph on Gcontains a regular subgroup isomorphic toG. Moreover, this property characterises the Cayley graphs onG.

It is clear that Cay(G, S)∼=Cay(G, Sσ)for everyσ∈Aut(G). A Cayley graph Cay(G, S)is said to be a CI-graph if, for eachTG, the Cayley graphs Cay(G, S) and Cay(G, T )are isomorphic if and only if there is an automorphismσ ofGsuch thatSσ =T. Furthermore, a groupGis called a CI-group if every Cayley graph on Gis a CI-graph.

Research supported by the Hungarian Scientific Fund (OTKA), grant no. NK72523.

G. Somlai (

)

Department of Algebra and Number Theory, Eötvös University, Budapest, Hungary e-mail:[email protected]

(2)

For our discussion two previous results are relevant. It is easy to prove that ifGis a CI-group, then every subgroup ofGis a CI-group. Babai and Frankl proved in [1]

that the Sylow subgroups of a CI-group can only beZ4,Z8,Z9,Z27, the quaternion group of order 8 or an elementary abelianp-group. Also, they asked whether every elementary abelianp-group is a CI-group.

Hirasaka and Muzychuk proved in [3] thatZ4p is a CI-group for every primep and this was also proved by Morris [4]. On the other hand, Muzychuk [5] proved that an elementary abelianp-group of rank 2p−1+2p1

p

is not a CI-group and most recently as a strengthening of this result Spiga [7] showed that ifn≥4p−2, then Znp is not a CI-group. Spiga [8] also proved that Z53is a CI-group but Z83 is not a CI-group. The problem of determining whether or not an elementary abelian group Znp is a CI-group is solved ifp=2 as the CI property holds forZ52, see [2], and a non-CI-graph forZ62was constructed by Nowitz [6].

Further improving the upper bounds in [5] and [7], we prove the following.

Theorem 1 For every primep >2, the groupZ2pp +3has a Cayley graph of valency (2p+3)pp+1which is not a CI-graph. Consequently, an elementary abelianp-group of rank greater than or equal to 2p+3 is not a CI-group.

We can formulate a similar theorem for undirected Cayley graphs.

Theorem 2 For every primep >3, the groupZ2pp +3has an undirected Cayley graph which is not a CI-graph.

The problem of finding undirected non-CI-graphs of elementary abelian 3-groups is still open.

The proof of Theorem1is elementary and uses only the definition of the CI prop- erty. We will construct two isomorphic Cayley graphs in Sect.2. The connection sets in both graphs are the union of affine subspaces inZ2p+p 3and the isomorphism between the Cayley graphs is given in terms of polynomials. Finally, the proof in Sect.5that our Cayley graphs are not CI-graphs uses only elementary tools of linear algebra. Section6is devoted to prove Theorem2. In addition, in Sect.7we will in- dicate how the previous results of Muzychuk and Spiga can be obtained applying our technique.

2 The construction

LetU∼=Zpp+1andV ∼=Zpp+2, then the groupsU andV can be regarded as vector spaces over the fieldZpwith bases{e1, e2, . . . , ep+1}and{f0, f1, . . . , fp+1}, respec- tively. We endowV with the natural bilinear form:

p+1

j=0

αjfj,

p+1 j=0

βjfj

=

p+1

j=0

αjβj.

(3)

Let us define the following affine subspaces ofG=UV: Ai=ei+

vV | v, f0+fi =0

, (i=1, . . . , p+1),

Bi=

j =i

ej+ vV

v, fi+

p+1 j=0

fj

=0

, (i=1, . . . , p+1),

C0=

p+1

i=1

ei+ vV

v,

p+1

j=0

fj

=0

,

C1=

p+1

i=1

ei+ vV

v,

p+1

j=0

fj

=1

.

Now

S=

p+1 i=1

(AiBi)C0 and T =

p+1 i=1

(AiBi)C1 (1) will be the connection sets of two Cayley graphs defined onG=UV. Note that the setsSandT are the union of affine subspaces ofG. Namely,SandT are the union of 2p+3 affine subspaces of dimensionp+1. Therefore,|S| = |T| =(2p+3)pp+1, as desired.

We are going to show in Sect.4 that Cay(G, S)∼=Cay(G, T )but we will also prove in Sect.5that there is no automorphism ofGmappingStoT. Taken together, these two facts establish Theorem1.

3 Preliminary facts

In this section we introduce some notation concerning polynomials and we establish certain equations over the fieldZp. These will be used in the proof of the isomorphism between the two Cayley graphs Cay(G, S)and Cay(G, T ).

For a sequence of integersn:=(n1, . . . , np+1)we denotexn:=x1n1· · ·xpnp+1+1 and letk(xn)= |{i|ni >0}|denote the number of variables occurring in xn. Let M be the set of monomials of degreep involving at least two variables and for each i=1, . . . , p+1 we divide it into two subsetsM=M0iM+i , whereM0i = {xn| ni=0}andM+i = {xn|ni>0}. For a monomialxnMwe define the numbercn=

(p1)!

n1!···np+1!. An obvious consequence of the Multinomial Theorem is that n p!

1!···np+1! is an integer. IfxnM, thenk(xn)≥2 sopdoes not divide the denominator ofcnand hencecnis an integer. Finally, forα∈Zkpandf (x)∈Zp[x1, . . . , xk]we denote

αf (x)=f (x+α)f (x).

Lemma 1 Lets=p+1

i=1xi andsi=sxi=

j =ixj. The following two equations hold overZ[x1, . . . , xp+1].

(4)

(a)

sp=

p+1

j=1

xjp+

xn∈M

pcnxn.

(b)

spi =

j =i

xjp+

xn∈M0i

pcnxn.

Proof These identities are obvious.

Define the following polynomials inZp[x1, . . . , xp+1]: ri=

xn∈M0i

1−k xn

cnxn+

xn∈M+i

2−k xn

cnxn (2)

fori=1, . . . , p+1 and

r0=

xn∈M

k xn

−2

cnxn. (3)

Lemma 2

p+1

j=0

rj=pspp+1 j=1sjp

p . (4)

The polynomial ps

pp+1 j=1spj

p is defined inZ[x1, . . . , xp+1], while (4) holds over Zp.

Proof

p+1

j=0

rj=

xn∈M

p+1−k xn

1−k xn

+ k

xn

−1 2−k

xn cnxn

=(1p)

xn∈M

k xn

−1

cnxn=

xn∈M

k xn

−1

cnxn (5)

and Lemma1gives

pspp+1 j=1sjp

p =

xn∈M

k xn

−1 cnxn

as well.

(5)

4 Isomorphism

Proposition 1 Cay(G, S)∼=Cay(G, T ).

Proof Letφ:Z2pp +3→Z2pp +3be defined by φ (x1, . . . , xp+1, y0, y1, . . . , yp+1)

=

x1, . . . , xp+1, y0+r0(x1, . . . , xp+1), . . . , yp+1+rp+1(x1, . . . , xp+1) , whereri∈Zp[x1, . . . , xp+1]are defined by (2) and (3).

We claim thatφ is an isomorphism from Cay(G, S)to Cay(G, T ). Note thatφ acts by translation onu+V for everyuUsoφis bijective. It remains to show that fora, bGifbaS, thenφ (b)φ (a)T.

SinceGis the direct sum ofU andV, an elementu+vGcan be written as (x, y), wherexUandyV. We will also writeu+vGas(x1, . . . , xp+1, y0, y1, . . . , yp+1).

Assume first thatbaAi for some 1≤ip+1 and writea=(x, y)with xUandyV. Then we may setb=a+(ei+v), wherevV such thatv, f0+ fi =0. Clearlyφdoes not affect the firstp+1 coordinates hence we need to show φ (b)φ (a)Ai. Now we have

φ (b)φ (a)

(ba)=

φ (b)b

φ (a)a

=

0, . . . ,0, eir0(x), eir1(x), . . . , eirp+1(x) . Thus we have to check that (eir0(x), eir1(x), . . . , eirp+1(x)), f0+fi =0.

Now

eir0(x), eir1(x), . . . , eirp+1(x) , f0+fi

=eir0(x)+eiri(x)

=ei

r0(x)+ri(x)

=0, sincer0+ri does not involvexi.

By the same argument ifbaC0, then using Lemma2we get

p+1 j=1ej

p+1

j=0

rj

=p(s+p+1)pp+1

j=1(sj+p)p

ppspp+1

j=1spj p

=(s+1)psp=1.

These equations hold overZp since(t+p)ptp (modp2). Hence ifbaC0, thenφ (b)φ (a)C1.

Finally, ifbaBi we need a little more computation. Equation (5) shows that

p+1 j=0

rj=

xn∈M

k xn

−1 cnxn.

(6)

Hence ri+

p+1

j=0

rj=

xn∈M0i

1−k xn

cnxn+

xn∈M+i

2−k xn

cnxn

+

xn∈M

k xn

−1 cnxn

=

xn∈M+i

cnxn,

which is, by Lemma1, equal to

spxipsip

p .

Therefore,

j =iej

ri+

p+1

j=0

rj

=(s+p)pxip(si+p)p

pspxipsip

p =0,

using again the fact that (t +p)ptp (modp2). Hence if baBi, then φ (b)φ (a)Bi and this finishes the proof of the fact that φ is indeed a graph

isomorphism.

5 Checking the CI property

Now in order to show that Cay(G, S)is not a CI-graph we have to show that there is noσ∈Aut(G)=GL(U⊕V )such thatσ (S)=T.

Proposition 2 There is no linear transformation σ ∈ GL(U ⊕ V ) such that σ (S)=T.

Proof Assume by way of contradiction that σ ∈GL(U ⊕V ) with σ (S)=T. Let M denote the matrix of the linear transformation σ with respect to the basis {e1, . . . , ep+1, f0, f1, . . . , fp+1}and writeM=M1,1M1,2

M2,1M2,2

as a block matrix, where M1,1∈Z(p+p 1)×(p+1)andM2,2∈Z(p+p 2)×(p+2).

For the purpose of the following we modify our notation as follows. Let S= 2p+3

i=1 Si andT =2p+3

i=1 Ti, where Si=Ti=Ai,Si+p+1=Ti+p+1=Bi for i= 1, . . . , p+1 andS2p+3=C0,T2p+3=C1.

Now we prove two lemmas from which the proof of Proposition2will follow.

Lemma 3 V is an invariant subspace ofσ, i.e.,M1,2=0.

(7)

Proof Considering only the firstp+1 coordinates it is easy to see using the assump- tionp >2 that fori =j ifaSi andbSj, then 2a−bSand similarly forT. This implies that bothSandT contain exactly 2p+3 affine subspaces of dimension p+1. Hence for 1≤i≤2p+3 we must haveσ (Si)=Tj for somej and ifa,b

Si, thenσ (a)σ (b)V. Now

Span p+1

i=1

{ab|a, bSi}

=V ,

soσ (V )V and this finishes the proof of the fact thatV is an invariant subspace

ofσ.

It is immediate from Lemma3 that σ induces a linear transformation of(UV )/V ,which we also denote byσ. Set

Sˆ=

ei,

j =i

ej|1≤ip+1

p+1

j=1

ej

U. (6)

In the following, Lemma4, we shall identify the elements inSˆ+V(UV )/V with those inS. Asˆ σ (S)=σ (T )andS+V =T +V, we haveσ (S)ˆ = ˆS.

Lemma 4 M1,1is a permutation matrix.

Proof In this proof we will use the natural bilinear form onUdefined as follows:

p+1

i=1

αiei,

p+1 i=1

βiei

=

p+1 i=1

αiβi.

Lete:=p+1

i=1ei. Note thateis the unique element ofSˆ which is the sum of two others withinS, henceˆ σ (e)=e. The rest of the points can be paired such that the sum of every pair iseand by the linearity ofσ the setH= {σ (ei)|1≤ip+1}

contains exactly one element of each pair. Furthermore,

hHh=p+1

i=1 σ (ei)= σ (p+1

i=1 ei)=σ (e)=e.

For everys∈ ˆS we have[s, e] =0 or 1, hence if H contains an elementx such that[x, e] =0, thenHcontainspelements with the same property as[

hHh, e] = [e, e] =1. By permuting the coordinates we obtain that if H contains an element x such that [x, e] =0, then H = {e1} ∪ {

j =iej |2≤ip+1}but

hHh= e1e2− · · · −ep+1 =p+1

i=1ei=ein this case, a contradiction.

Now we continue the proof of Proposition2.

For every permutation of{e1, . . . , ep+1}if we apply the same permutation to the indices of{f1, . . . , fp+1}and fixf0we obtain an automorphism of Cay(G, S). Hence we may assume for the rest of the proof thatM1,1=I.

(8)

This assumption implies thatσ (ei)Ai andσ (

j =iej)Bi for 1≤ip+1.

From this we get

M2,1ei, f0+fi =0,

M2,1

j =i

ej, fi+

p+1

j=0

fj

=0

for 1≤ip+1.

The sum of these 2p+2 equations overZpis

p+1

i=1

M2,1ei, f0+fi +

p+1 i=1

M2,1

j =i

ej, fi+

p+1

j=0

fj

=0,

so using bilinearity

M2,1

p+1

i=1

ei,

p+1

j=0

fj

=0.

We also haveσ (p+1

j=1ej)C1,which gives

M2,1 p+1

i=1

ei,

p+1

j=0

fj

=1.

This contradiction finishes the proof of Proposition2.

Finally, Proposition1and Proposition2prove Theorem1.

6 Undirected graphs

In this section we study undirected Cayley graphs and we will prove Theorem2.

IfGis an abelian group we write−S= {−sG|sG}instead ofS1. For a subset S of Gwe define S¯=S∪ −S. It is also clear that ifφ is an isomorphism between Cay(G, S)and Cay(G, T ), thenφis an isomorphism between Cay(G,S)¯ and Cay(G,T )¯ as well.

In Sect.2we defined two isomorphic directed Cayley graphs Cay(Z2pp +3, S)and Cay(Z2p+p 3, T )ofZ2p+p 3, whereSandT were defined in (1). Therefore, we have a pair of isomorphic undirected Cayley graphs: Cay(Z2pp +3,S)¯ and Cay(Z2pp +3,T ).¯ Proposition 3 For every primep >3, the graph Cay(Z2pp +3,S)¯ is an undirected Cayley graph on the groupZ2pp +3which is not a CI-graph.

(9)

Proof It is enough to show that there is no linear transformationσ such thatσ (S)¯ = T¯. Seeking a contradiction, let us assume thatσ∈GL(U⊕V )withσ (S)¯ = ¯T.

The same kind of reasoning as in Lemma3shows thatV is an invariant subspace ofσ, but here we have to use the extra condition thatp >3. Henceσ induces a linear transformation of(UV )/V ,which we also denote byσ. Set

S˜=

ei,ei,

j =i

ej,

j =i

ej

1≤ip+1

p+1

j=1

ej,

p+1

j=1

ej

,

which is a subset ofU. We shall identify the elements inS˜+V(UV )/V with those inS. As˜ σ (S)¯ =σ (T )¯ andS¯+V = ¯T +V, we haveσ (S)˜ = ˜S. Note that we can writeS˜= ˆS∪ − ˆSwithSˆ∩ − ˆS= ∅, whereSˆis defined in (6).

Now we prove a lemma from which the proof of Proposition3will follow.

Lemma 5 One of the two linear transformationsσ andσ permutes the elements ofS.ˆ

Proof Sinceσ induces an automorphism of Cay(U,S)˜ andσ (0)=0, it gives an au- tomorphism of the induced subgraph on the neighbourhood of 0 as well. In this sub- graph the verticeseand−ehave degree 2p+2, the other vertices have degree 2. This implies thatσ (e)=eorσ (e)= −e. So eitherσ or−σ fixese. The neighbourhood ofeinS˜isS, hence the proof of Lemmaˆ 4yields the result.

As a consequence of Lemma5we get a linear transformation (σ or −σ) which mapsSontoT. This contradicts Proposition2, finishing the proof of Theorem2.

7 Connection to previous results

In this section, we modify our construction a little bit to get non-CI-graphs of the groupsZ4pp 2andZ2p1+(2p−p1)

p . These results provide a uniform explanation for the recent work of Spiga [7] and Muzychuk [5], respectively. The proof of these results only simplifies the heavy machinery used in [5] and [7].

7.1 Rank 4p−2

Let U ∼=V ∼=Z2pp 1 and W =UV with the bases {e1, . . . , e2p 1} and {f1, . . . , f2p 1}, respectively. We denote byL the set of multilinear monomials of degreepin 2p−1 variables. LetL0i = {xnL|ni=0}andL+i =L\L0i. IfxnL, then the exponent vectorncan be treated as ap-element subset of{1, . . . ,2p−1}.

Let

Ai =ei+

vV| v, fi =0 ,

(10)

Bi=

j =i

ej+ vV

v, fi+

2p1 j=1

fj

=0

,

C0 =

2p1 j=1

ej+ vV

v,

2p1 j=1

fj

=0

,

C1 =

2p1 j=1

ej+ vV

v,

2p1 j=1

fj

= −1

.

Similarly to the construction in Sect. 2 let S=2p1

i=1 (AiBi)C0 andT= 2p−1

i=1 (AiBi)C1. We claim that Cay(W, S)∼=Cay(W, T)and the isomor- phism is given in the same manner:

φ(x1, . . . , x2p1, y1, . . . , y2p1)

=

x1, . . . , x2p1, y1+l1(x1, . . . , x2p1), . . . , y2p1+l2p1(x1, . . . , x2p1) , whereli denotes the sum of the monomials inL0i fori=1, . . . ,2p−1.

In this case the computations needed to show thatφis an isomorphism of the two Cayley graphs are easier.

Lemma 6 Assume thatxnLandm∈ {0,1}2p1U (a)

mxn

(x)=xn\m

knm

xk.

(b)

j=1ejxn

(x)=

kn

xk.

Proof (a) is obvious and (b) is just a particular case of (a).

The proof thatφis an isomorphism is similar to the proof of Proposition1. We leave it to the reader to prove, using Lemma7(a), that ifbaAi, then φ(b)φ(a)Ai, to prove, using Lemma7(c), that ifbaBi, thenφ(b)φ(a)Bi, and finally to prove, using Lemma7(b), that ifbaC0, thenφ(b)φ(a)C1. Lemma 7

(a)

e ili=0.

(11)

(b)

2p−1 j=1 ej

2p1

j=1

lj

= −1.

(c)

j =iej

li+

2p1 j=0

lj

=0.

Proof (a) Obvious, sincelidoes not involvexi. (b) We have

2p1 j=1

lj=

2p1 j=1

xn∈L0i

xn=

xn∈L

(p−1)xn= −

xn∈L

xn (7)

and hence 2p−1

j=1 ej

2p1

j=1

lj

= −2p−1 j=1 ej

xn∈L

xn= −

xn∈L

2p−1 j=1 ejxn

applying Lemma6(b)

= −

n∈{0,1}2p−1

|n|=p

kn

xk= −

|k|<p

xk

kn

|n|=p

1

= −

|k|<p

2p−1− |k| p− |k|

xk.

The binomial coefficient2p1−|k|

p−|k|

is divisible bypif 1≤ |k|< pand this implies that the remaining polynomial is just the constant polynomial−2p1

p

overZp. Tak- ing into account that2p1

p

≡1 (modp), we obtain (b).

(c) Making use of (7) we get

li+

2p1 j=1

lj=

xn∈L0i

xn

xn∈L

xn= −

xn∈L+i

xn.

Now

j =iej

xn∈L+i

xn

= −

xn∈L+i

j =iejxn

(12)

and by Lemma6(a)

= −

xn∈L+i

xi

kn\{i}

xk= −xi

i /k

|k|<p1

xk

{i}∪kn

|n|=p

1

= −xi

i /k

|k|<p1

2p−1− |k| −1 p− |k| −1

xk.

Now if|k|< p−1, then2p1−|k|−1

p−|k|−1

≡0 (modp)and this proves the result.

The proof of the fact that there is no linear transformation which mapsStoTis nearly the same as in Proposition2providedp >3. We leave it to the reader to work out the details and we will do so in the next case as well. Ifp=3, then the statement analogous to Lemma4does not hold.

7.2 Rank 2p−1+2p1

p

Here we only give the connection sets and the isomorphism of the Cayley graphs.

The proof goes along the same lines as in the previous cases.

LetO= {k⊂ {1, . . . ,2p−1} | |k| =p}and let U∼=Z2p−p 1 andV∼=Z(2pp1)

p

with the bases{e1, e2, . . . , e2p 1}and{fk|kO}, respectively. Since |O| equals to the dimension ofV, for every yVwe can write y=(. . . , yk, . . .), where kO. For(x, y)UVwe define

φ(x, y)=

x, . . . , yk+xk, . . . .

For each 1≤i≤2p−1 we define the set Ai =ei +

vV

v,

i /k

fk

=0

.

For everykOthere are exactlypelementsk1, . . . , kp ofOsuch that|k∩ki| =1 and hence we can define

Bk=

jk

ej+

vVv, fk

1+ · · · +fk

p

=0 .

The third type of affine subspaces are defined by

C0=

2p1 j=1

ej+

vV

v,

k∈O

fk

=0

(13)

and

C1=

2p1 j=1

ej+

vV

v,

k∈O

fk

=1

.

Finally, the connection sets are given similarly to the previous cases:

S=

i

Ai

k∈O

Bk

C0

and

T=

i

Ai

k∈O

Bk

C1

andφgives the isomorphism between the two Cayley graphs.

Acknowledgements The author is very grateful to Péter P. Pálfy for many valuable suggestions and dis- cussions throughout the preparation of this paper and to the referee for many extremely helpful comments and thorough work.

References

1. Babai, L., Frankl, P.: Isomorphism of Cayley graphs I. In: Colloquia Mathematica Societatis János Bolyai, Keszthely, 1976. Combinatorics, vol. 18, pp. 35–52. North-Holland, Amsterdam (1978) 2. Conder, M., Li, C.H.: On isomorphism of Cayley graphs. Eur. J. Comb. 19, 911–919 (1998) 3. Hirasaka, M., Muzychuk, M.: An elementary abelian group of rank 4 is a CI-group. J. Comb. Theory,

Ser. A 94(2), 339–362 (2001)

4. Morris, J.: Results towards showingZ2p−1p is a CI-group. In: Proceedings of the Thirty-third South- eastern International Conference on Combinatorics, Graph Theory and Computing, Boca Raton, FL, 2002. Congr. Numer, vol. 156, pp. 143–153 (2002)

5. Muzychuk, M.: An elementary abelian group of large rank is not a CI-group. Discrete Math. 264(1–3), 167–185 (2003)

6. Nowitz, L.A.: A non-Cayley-invariant Cayley graph of the elementary abelian group of order 64. Dis- crete Math. 110, 223–228 (1992)

7. Spiga, P.: Elementary abelian p-groups of rank greater than or equal to 4p2 are not CI-groups.

J. Algebraic Combin. 26, 343–355 (2007)

8. Spiga, P.: CI-property for elementary abelian 3-groups. Discrete Math. 309, 3393–3398 (2009)

参照

関連したドキュメント