Minimal generating sets and Cayley graphs of Sylow p-subgroups of finite symmetric groups
Minimal generating sets of a Sylow p-subgroup Pn of the symmetric group Spn are characterized. The number of ordered minimal generating sets of Pn is calculated. The notion of the type of a generating set of Pn is introduced and it is proved that Pn contains minimal generating sets of all possible t...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2009
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/154503 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Minimal generating sets and Cayley graphs of Sylow p-subgroups of finite symmetric groups / A.J. Slupik, V.I. Sushchansky // Algebra and Discrete Mathematics. — 2009. — Vol. 8, № 4. — С. 167–184. — Бібліогр.: 11 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-154503 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1545032019-06-16T01:31:18Z Minimal generating sets and Cayley graphs of Sylow p-subgroups of finite symmetric groups Slupik, A.J. Sushchansky, V.I. Minimal generating sets of a Sylow p-subgroup Pn of the symmetric group Spn are characterized. The number of ordered minimal generating sets of Pn is calculated. The notion of the type of a generating set of Pn is introduced and it is proved that Pn contains minimal generating sets of all possible type. The isomorphism problem of Cayley graphs of Pn with respect to their minimal generating sets is discussed. 2009 Article Minimal generating sets and Cayley graphs of Sylow p-subgroups of finite symmetric groups / A.J. Slupik, V.I. Sushchansky // Algebra and Discrete Mathematics. — 2009. — Vol. 8, № 4. — С. 167–184. — Бібліогр.: 11 назв. — англ. 1726-3255 2000 Mathematics Subject Classification:20B35, 05C25, 05C12, 20F65. http://dspace.nbuv.gov.ua/handle/123456789/154503 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
Minimal generating sets of a Sylow p-subgroup Pn of the symmetric group Spn are characterized. The number of ordered minimal generating sets of Pn is calculated. The notion of the type of a generating set of Pn is introduced and it is proved that Pn contains minimal generating sets of all possible type. The isomorphism problem of Cayley graphs of Pn with respect to their minimal generating sets is discussed. |
| format |
Article |
| author |
Slupik, A.J. Sushchansky, V.I. |
| spellingShingle |
Slupik, A.J. Sushchansky, V.I. Minimal generating sets and Cayley graphs of Sylow p-subgroups of finite symmetric groups Algebra and Discrete Mathematics |
| author_facet |
Slupik, A.J. Sushchansky, V.I. |
| author_sort |
Slupik, A.J. |
| title |
Minimal generating sets and Cayley graphs of Sylow p-subgroups of finite symmetric groups |
| title_short |
Minimal generating sets and Cayley graphs of Sylow p-subgroups of finite symmetric groups |
| title_full |
Minimal generating sets and Cayley graphs of Sylow p-subgroups of finite symmetric groups |
| title_fullStr |
Minimal generating sets and Cayley graphs of Sylow p-subgroups of finite symmetric groups |
| title_full_unstemmed |
Minimal generating sets and Cayley graphs of Sylow p-subgroups of finite symmetric groups |
| title_sort |
minimal generating sets and cayley graphs of sylow p-subgroups of finite symmetric groups |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2009 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/154503 |
| citation_txt |
Minimal generating sets and Cayley graphs of Sylow p-subgroups of finite symmetric groups / A.J. Slupik, V.I. Sushchansky // Algebra and Discrete Mathematics. — 2009. — Vol. 8, № 4. — С. 167–184. — Бібліогр.: 11 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT slupikaj minimalgeneratingsetsandcayleygraphsofsylowpsubgroupsoffinitesymmetricgroups AT sushchanskyvi minimalgeneratingsetsandcayleygraphsofsylowpsubgroupsoffinitesymmetricgroups |
| first_indexed |
2025-07-14T06:35:45Z |
| last_indexed |
2025-07-14T06:35:45Z |
| _version_ |
1837603169196048384 |
| fulltext |
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 4. (2009). pp. 167 – 184
c⃝ Journal “Algebra and Discrete Mathematics”
Minimal generating sets and Cayley graphs of
Sylow p-subgroups of finite symmetric groups
Anna J. Slupik and Vitaly I. Sushchansky
Dedicated to L.A. Kurdachenko on the occasion of his 60th birthday
Abstract. Minimal generating sets of a Sylow p-subgroup
Pn of the symmetric group Spn are characterized. The number of
ordered minimal generating sets of Pn is calculated. The notion of
the type of a generating set of Pn is introduced and it is proved
that Pn contains minimal generating sets of all possible type. The
isomorphism problem of Cayley graphs of Pn with respect to their
minimal generating sets is discussed.
1. Introduction
For any finite p-group (p is a prime) all minimal (in the sense of an
inclusion) generating sets have the same size. IfX is a minimal generating
set of a finite p-group G, then for every automorphism � ∈ Aut(G)
image X� is also a minimal generating set of G. Hence Aut(G) acts
on the set ΣG of all minimal generating sets of G. The investigation
of orbits of Aut(G) on the set ΣG is interesting from the point of view
of the isomorphism problem for Cayley graphs of the group G [1, 2, 9].
Namely, if generating sets X, Y belong to the same orbit of Aut(G) on
ΣG, then Cayley graphs Cay(G,X) and Cay(G, Y ) are isomorphic. For
many p-groups G the inverse statement is also true, i.e. if Cay(G,X) is
isomorphic to Cay(G, Y ) then X, Y belong to the same orbit of Aut(G)
on ΣG. We call p-groups with such property MCI-groups. For MCI-
group G the isomorphism problem of connected Cayley graphs of minimal
branch degree is equivalent to characterization of orbits of the group
Aut(G) on ΣG. If G is not the MCI-group then some orbits Aut(G)
2000 Mathematics Subject Classification: 20B35, 05C25, 05C12, 20F65.
Key words and phrases: Cayley graph, Sylow p-subgroup, Frattini subgroup.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.168 Minimal generating sets and Cayley graphs
on ΣG can join together into one equivalence class of the Cayley graphs
isomorphism relation. Hence, in both cases, the investigation of different
types of minimal sets of generators and the action of automorphism group
on that sets can be use to solve the isomorphism problem of Cayley graphs
in the natural way .
In this paper we investigate minimal sets of generators of the Sylow
p-subgroup Pn of symmetric group Spn of the degree pn (n ∈ ℕ), using
special polynomial representation of this group proposed by L. Kalouj-
nine in [4, 5]. The outline of this paper is as follows. In the section 2
we remind basic definitions and facts about Sylow p-subgroups Pn and
characterize some calculation techniques connected with the polynomial
representation of those groups. In the section 3 the theorem about the
number of minimal ordered generating sets of Pn is proved and the char-
acterization of all those sets for n = 2 is presented. In the section 4 we
focus on investigation of triangular and diagonal generating sets. We give
a short description of the decomposition algorithm for elements from Pn
into the product of generators from a diagonal generating set. In the sec-
tion 5 we introduce the notion of the type of generating set and we give
a complete description of the set of types for all minimal generating sets
of Pn. In the section 6 we discuse sufficient condition for the group Pn
to be a MCI-group and we construct examples of generating sets with
isomorphic or non-isomorphic Cayley graphs.
2. Preliminaries
Let Sm be the symmetric group of the degree m andm = a0+a1p+a2p
2+
...+ akp
k, where p is a prime. By Pn we denote the Sylow p-subgroup of
the symmetric group Spn (n = 1, 2, . . .). Then a Sylow p-subgroup of Sm
is isomorphic (see [3]) to the direct product
P a1
1 × P a2
2 × . . .× P ak
k .
So the investigation of the structure of Sylow p-subgroups of the sym-
metric group Sm can be reduced to analysis of Sylow p-subgroups of the
symmetric group Spn (n = 1, 2, . . . , k). It is easy to verify that the order
of the group Pn is equal to:
∣Pn∣ = p1+p+p2+...+pn−1
.
It is well known that Pn is isomorphic to the wreath product of n regular
cyclic groups of order p (see, for example [3]):
Pn
∼= Cp ≀ Cp ≀ ⋅ ⋅ ⋅ ≀ Cp︸ ︷︷ ︸
n
.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.A. J. Slupik, V. I. Sushchansky 169
For our considerations we can use very convenient presentation of Pn
introduced by L. Kaloujnine (see [4],[5]).
Let ℤp be the field of residues modulo p. Every function f of n vari-
ables over ℤp can be represented by a polynomial of n variables over
ℤp. Let I be an ideal of the ring ℤp[x1, . . . , xm] generated by polyno-
mials xp1 − x1, . . . , x
p
m − xm. Polynomials g, ℎ ∈ ℤp[x1, . . . , xm] define
the same function if and only if g ≡ ℎ (mod I). Any residue class of
ℤp[x1, . . . , xm]/I contains an unique polynomial such that degrees of all
its variables x1, . . . , xm are equal at most p−1. This polynomial is called
a reduced polynomial modulo ideal I.
The sequence of the type:
u = [f1, f2(x1), f3(x1, x2), . . . , fn(x1, . . . , xn−1)] (1)
where f1 ∈ ℤp and fi is a reduced polynomial for i = 2, 3, ..., n is called
a tableau of the length n over ℤp (see, [5]).
Every tableau of the form (1) acts on the set ℤ
n
p in the following way:
(x1, x2, . . . , xn)
u = (x1 + f1, x2 + f2(x1), . . . , xn + fn(x1, . . . , xn−1)) (2)
for any (x1, x2, . . . , xn) ∈ ℤ
n
p .
Lemma 1. For any tableau u the action (2) defines some permutation
on ℤ
n
p .
Proof. Simply checking.
The set of all tableaux forms a group according to the following operation:
If
u = [f1, f2(x1), . . . , fn(x1, . . . , xn−1)]
and
v = [g1, g2(x1), . . . , gn(x1, . . . , xn−1)]
then:
uv = [f1 + g1, f2(x1) + g2(x1 + f1), . . . ,
fn(x1, . . . , xn−1) + gn(x1 + f1, . . . , xn−1 + fn−1(x1, . . . , xn−2))] .
(3)
The tableau e = [0, . . . , 0] is the neutral element for this operation. The
inverse element for u is equal:
u−1 = [−f1,−f2(x1 − f1),−f3(x1 − f1, x2 − f2(x1 − f1)), . . .
. . . ,−fn(x1 − f1, . . . , xn−1 − fn−1(...))] .
(4)
The order of this group is equal to p1+p+p2+...+pn−1
and hence it
is isomorphic to Sylow p-subgroup of symmetric group Spn . Thus every
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.170 Minimal generating sets and Cayley graphs
element of the Sylow p-subgroup Pn may be represented by a tableau (1).
We call this representation as a polynomial or Kaloujnine representation
of Pn.
It is convenient to use the following notation. The sequence of vari-
ables x1, x2, . . . , xi we denote by Xi. Let us take any tableau
u = [f1, f2(X1), . . . , fn(Xn−1)] .
By the symbol u(i) we denote the beginnig of the tableau u of the length
i. For any reduced polynomial g(Xi) we denote by g(Xu
i ) = g(X
u(i)
i ) the
following polynomial
g(x1 + f1, x2 + f2(X1), . . . , xi + fi(Xi−1)) .
According to our notation, the product of tableaux u(i) = [u(i−1), a(Xi)]
and v(i) = [v(i−1), b(Xi)] has the form
[u(i−1)v(i−1), a(Xi−1) + b(X
u(i−1)
i−1 )] .
Let us denote by [u]i the i-th coordinate of the tableau u. The tableau u
has the depth k if [u]1 = . . . = [u]k = 0 and [u]k+1 ∕= 0.
Technique of calculations using the Kaloujnine representation is based
on the following simple facts:
Fact 1. We have the following equalities:
1. [(u, v)]i = [ uvu−1v−1]i =
= a(Xi−1)− a(X
u(i−1)v(i−1)
i−1 ) + b(X
u(i−1)
i−1 )− b(X
u(i−1)v(i−1)u
−1
(i−1)
i−1 ) ,
2. [uvu−1]i+1 = a(X
v(i)
i ) + b(Xi)− a(X
u(i)v(i)u
−1
(i)
i ) ,
3. [uk]i =
k−1∑
j=0
a(X
u
j
(i−1)
i−1 ) .
For every polynomial of k-variables we can define the height of a
polynomial.
Definition 1. The height of the nonzero monomial x�1
1 x�2
2 ⋅ ... ⋅ x�k
k is
called the number:
ℎ(x�1
1 x�2
2 ⋅ ... ⋅ x�k
k ) = 1 + �1 + �2p+ ...+ �kp
k−1.
We assume that ℎ(0) = 0. The height of the reduced polynomial f of k
variables is equal to the maximum height of its monomials.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.A. J. Slupik, V. I. Sushchansky 171
Fact 2. 1. For any reduced polynomial f(Xk) and a tableau u ∈ Pn the
following equality holds
ℎ(f(Xu
k )) = ℎ(f(Xk)) .
2. For any reduced polynomial f(Xk) and a tableau u ∈ Pn the following
inequality holds
ℎ(f(Xk)− f(Xu
k )) ≤ max{ℎ(f(Xk))− 1, 0} .
3. For any reduced polynomial f(Xk) there exists a tableau u ∈ Pn such
that
ℎ(f(Xk)− f(Xu
k )) = max{ℎ(f(Xk))− 1, 0} .
4. For any reduced polynomial f(Xk) and a tableau u ∈ Pn of depth s ≤ k
the following inequality holds
ℎ(f(Xk)− f(Xu
k )) ≤ pk − ps .
5. For every tableau u ∈ Pn of depth s ≤ k there exists a reduced polyno-
mial f(Xk) such that
ℎ(f(Xk)− f(Xu
k )) = pk − ps .
6. For every tableaux u, v ∈ Pn the following inequalities hold:
ℎ([vu]k) ≤ max{ℎ([v]k), ℎ([u]k)− 1} ,
ℎ([(u, v)]k) ≤ max{ℎ([u]k)− 1, ℎ([v]k)− 1, 0} .
Moreover, for every tableau u ∈ Pn and k ≥ 1 there exists a tableau
v ∈ Pn such that
ℎ([(u, v)]k) ≤ max{ℎ([u]k)− 1, 0} .
By pc(f(x1, ..., xk)) we denote the coefficient of the monomial of f
which has the maximal height.
Lemma 2. The commutator subgroup of Pn is equal to:
P ′
n = {[0, f2(X1), f3(X2), ..., fn(Xn−1)]; ℎ(fi) < pi−1, i = 2, ..., n} .
The quotient group Pn/P
′
n is elementary abelian group of the order pn.
Proof. See [5].
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.172 Minimal generating sets and Cayley graphs
3. Bases of Sylow p-subgroups of symmetric groups
An element g ∈ G is called a non-generating element of G if it can be
deleted from any generating set of G. All non-generating elements of G
form a subgroup which is called the Frattini subgroup of the group G
and denoted by Φ(G). The subgroup Φ(G) may be defined also as the
intersection of all maximal subgroups of G. If G is a finite p-group then
Φ(G) is the intersection of all subgroups of the index p. As usual, by Gn
we denote the group generated by all powers gn, g ∈ G. The following
statement about Frattini subgroups is well known (see for example [11]):
Lemma 3. If G is a finite p-group, then Φ(G) = G′Gp.
So if G is a p-group then G/Φ(G) is an elementary abelian p-group
which may be idetified with an additive group of a linear space over ℤp.
Lemma 4. Let G be a p-group and let ' be a natural epimorphism from G
to G/Φ(G) and G/Φ(G) ≃ ℤ
k
p. The set {u1, u2, . . . , uk} of elements from
G will be the minimal set of generators, if and only if '(u1), '(u2), . . . ,
'(uk) is a basis of the linear space ℤ
k
p over ℤp.
Hence any two minimal (according inclusions) generating sets of G
has the same size. For the group Pn the epimorhism ' is defined in the
following way. Every element of u ∈ Pn can be written in the form
[a1, a2x
p−1
1 +f2(X1), a3x
p−1
1 xp−1
2 +f3(X2), ..., anx
p−1
1 ⋅...⋅xp−1
n−1+fn(Xn−1)],
where ℎ(fi) < pi−1 (i = 2, . . . , n). Then:
' (u) = (a1, a2, . . . , an) .
Now for a Sylow p-subgroup of a symmetric group we can formulate
such statement:
Lemma 5. For any Sylow p-subgroup H of symmetric group Sm, m ≥ 2,
the Frattini subgroup Φ(H) is equal to H ′.
Proof. 1) Let m = pn, p is a prime number, n ≥ 1. Then H ≃ Pn.
Because Φ(Pn) = P ′
n ⋅ P p
n it is sufficient to prove the inclusion P p
n ⊂
P ′
n. Let u = [f1, f2(X1), . . . , fn(Xn−1)] ∈ Pn. If [u]k = g
(1)
k (Xk−1) +
g
(2)
k (Xk−1), where g
(1)
k (Xk−1) = akx
p−1
1 ⋅ ⋅ ⋅xp−1
k−1, ℎ(g
(2)
k ) ≤ pk−1− 1, then
according to fact 1.3 the following equalities hold:
[up]k =
p−1∑
i=0
g
(1)
k (X
ui
(k−1)
k−1 ) +
p−1∑
i=0
g
(2)
k (X
ui
(k−1)
k−1 ) .
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.A. J. Slupik, V. I. Sushchansky 173
Because
ℎ
(
p−1∑
i=0
g
(1)
k (X
ui
(k−1)
k−1 )
)
< pk−1
we have
ℎ([up]k) ≤ pk−1 − 1
for all k = 1, 2, . . . , n. Hence, by lemma 2, up ∈ P ′
n and this case is
proved.
2) Let m is a positive integer and m = a0 + a1p+ . . .+ anp
n. Then
H ≃ P a1
1 × . . .× P an
n .
Hence
H ′ ≃ (P ′
1)
a1 × . . .× (P ′
n)
an and Hp ≃ (P p
1 )
a1 × . . .× (P p
n)
an .
Using the first part of the proof we obtain Hp ⊂ H ′ and hence H ′ ⋅Hp =
H ′.
Corollary 1. Any minimal generating set of Sylow p-subgroups of finite
symmetric group Sm, m = a0 + a1p+ . . .+ akp
k, contains
d(m) = 1 ⋅ a1 + 2 ⋅ a2 + . . .+ k ⋅ ak
generators. In particular, if m = pn then d(m) = n.
We call an ordered minimal set of generators of some finite p-group G
a basis of this group. Let b(G) be the number of different bases of the
group G.
Theorem 1. For any integer n ≥ 2 and prime p the following equality
holds:
b(Pn) = pM
n∏
k=1
(pk − 1) ,
where M = n
(
pn−1
p−1 − 1
2(1 + n)
)
.
Proof. Every basis of Pn/P
′
n can be written in the form:
u1 ⋅ P
′
n, u2 ⋅ P
′
n, . . . , un ⋅ P ′
n
where '(u1), . . . , '(un) is a basis of the vector space ℤ
n
p .
So every basis of Pn has a form:
u1v1, u2v2, . . . , unvn
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.174 Minimal generating sets and Cayley graphs
where vi ∈ P ′
n and [ui]k is a monomial of maximal height equal pk−1
or 0 for i, k = 1, . . . , n and the set of {'(u1), . . . , '(un)} is a basis in
the vector space ℤ
n
p . The set u′1v
′
1, u
′
2v
′
2, . . . , u
′
nv
′
n forms different basis
of Pn if there exist i such that ui ∕= u′i or vi ∕= v′i. It means that there
exist j such that [ui]j ∕= [u′i]j (or [vi]j ∕= [v′i]j). If [ui]j ∕= [u′i]j then
pc([ui]j) ∕= pc([u′i]j). So pc([uivi]j) ∕= pc([u′iv
′
i]j) and we have different
basis. If [vi]j ∕= [v′i]j then [uivi]j = [ui]j + [vi]j(X
(ui)(j−1)
j−1 ) and [uiv
′
i]j =
[ui]j+[v′i]j(X
(ui)(j−1)
j−1 ) so [uivi]j ∕= [uiv
′
i]j and we also have different basis.
So b(Pn) = ∣GLn(ℤp)∣∣P
′
n∣
n. Beacuse
∣GLn(ℤp)∣ = (pn − 1)(pn − p) ⋅ . . . ⋅ (pn − pn−1) = p
(n−1)n
2
n∏
k=1
(pk − 1)
and
∣P ′
n∣
n =
(
p1+p+...+pn−1
pn
)n
= p
(
pn−1
p−1
−n
)
n
our proof is completed.
Now, we give a complete classification of 2-element generating sets of P2.
Let
∙ A be the family of pairs { [f1, f2(x1)] , [0, g(x1)] }, such that f1 ∕= 0,
f2 is an arbitrary reduced polynomial and ℎ(g) = p;
∙ B be the family of pairs { [f1, f2(x1)] , [g1, g2(x1)] }, such that
f1, g1 ∕= 0, ℎ(f2) < p, ℎ(g2) = p;
∙ C be the family of pairs { [f1, ax
p−1 + f2(x)] , [g1, bx
p−1 + g2(x)] }
such that f1, g1, a, b ∕= 0, ℎ(f2) < p, ℎ(g2) < p and a ∕= f1g
−1
1 b.
Then A ∪B ∪ C is the set of all minimal generating set of P2. It follows
from definitions of sets A, B and C that their pairwise intersection is
empty and
∣A∣ = (p− 1)2p2p−1 ,
∣B∣ = (p− 1)3p2p−2 ,
∣C∣ = 1
2(p− 1)3(p− 2)p2p−2 .
Hence b(P2) = 2(∣A∣+ ∣B∣+ ∣C∣) = (p− 1)(p2 − 1)p2p−1.
The proof, that families A, B and C consists of generating sets of P2 is
the conclusion from lemma 4. We have to show that there is no other
pairs of generators. It is obvious that one of the generators must have an
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.A. J. Slupik, V. I. Sushchansky 175
element not equal 0 on the first coordinate, and one of them must have a
polynomial of degree p− 1 on the second coordinate. There are only two
possibilities left:
1) pairs u = [f1, ax
p−1 + f2(x)], v = [g1, bx
p−1 + g2(x)] such that degrees
of polynomials f2 and g2 are lower then p− 1 and a = f1g
−1
1 b;
2) pairs u = [f1, f2(x)], v = [0, g(x)], such that f1 ∕= 0, f2 is a polynomial
of degree p− 1 and g is a polynomial of degree lower then p− 1;
In both cases we can easily check that we cannot generate an element
which has 0 on the first coordinate and a polynomial of degree p− 1 on
the second coordinate.
4. Triangular bases of Pn
A sequence of tableaux of the type
u1 = [a11, a
1
2(X1), a
1
3(X2), . . . , a
1
n(Xn−1)],
u2 = [0, a22(X1), a
2
3(X2), . . . , a
2
n(Xn−1)],
...
un = [0, 0, 0, . . . , ann(Xn−1)]
(5)
is called an upper triangular sequence and a sequence of tableaux
v1 = [a11, 0, 0, . . . , 0],
v2 = [a21, a
2
2(X1), 0 . . . , 0],
...
vn = [an1 , a
n
2 (X1), a
n
3 (X2), . . . , a
n
n(Xn−1)]
(6)
is called a lower triangular sequence.
Theorem 2. An upper triangular sequence (5) (resp. a lower triangular
sequence (6)) of tableaux from Pn is a basis of Pn if, and only if, the
following equalities hold:
ℎ(aii(Xi−1)) = pi−1 , i = 1, 2, . . . , n . (7)
Proof. We verify this statement only for upper triangular sequences of
the type (5). Let the equality (7) holds. Then from lemma 4 we only
need to show that '(u1), '(u2), . . . , '(un) is a basis in the vector space
ℤ
n
p . According to the definition of the epimorphism ' : Pn → ℤ
n
p we have
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.176 Minimal generating sets and Cayley graphs
'(u1) = [pc(a11), pc(a
1
2), pc(a
1
3), . . . , pc(a
1
n)],
'(u2) = [0, pc(a22), pc(a
2
3), . . . , pc(a
2
n)],
'(u3) = [0, 0, pc(a33), . . . , pc(a
3
n)],
...
'(un) = [0, 0, 0, . . . , pc(ann)],
where pc(aii) ∕= 0, because ℎ(aii) = pi−1. This is of course a basis of vector
space ℤ
n
p because we have pc(a11) ⋅ pc(a
2
2) ⋅ . . . ⋅ pc(a
n
n) ∕= 0.
In the other hand, if there exist index i such that ℎ(aii(Xi−1)) < pi−1
then pc(aii) = 0 and pc(a11) ⋅ pc(a
2
2) ⋅ . . . ⋅ pc(a
n
n) = 0. Hence '(u1),
'(u2), . . . , '(uk) is not a basis of ℤn
p and u1, u2, . . . , un is not a basis of
Pn.
For sequences of the type (6) the proof is similar.
A particular case of upper triangular sequences is diagonal sequence
of elements from Pn. A sequence of the type
u1 = [a11, 0, 0, . . . , 0],
u2 = [0, a22(X1), 0, . . . , 0],
...
un = [0, 0, 0, . . . , ann(Xn−1)]
(8)
where ℎ(aii(Xi−1)) = pi−1, is called a diagonal basis of Pn. Let D be the
set of all diagonal bases of Pn. Then
∣D∣ = (p− 1)n ⋅ p
pn−1
p−1
−n
.
From the point of view of the polynomial representation, diagonal
bases are very natural for construction of decomposition elements of
Pn into a product of generators. Namely, an arbitrary tableau w =
[f1, f2(X1), f3(X2), ..., fn(Xn−1)] can be decomposed into the product
w = unun−1 ⋅ ⋅ ⋅u1 ,
where ui = [0, . . . , 0[w]i, 0, . . . , 0] (1 ≤ i ≤ n). Hence it is sufficient to
construct decompositions for “coordinate” tableaux
ui = [0, . . . , 0, fi(Xi−1), 0, . . . , 0] .
Using statements from facts 1 and 2 for any height ℎ, 0 ≤ ℎ ≤ pi−1 it is
possible to construct (step by step) the tableau
v
(ℎ)
i = [0, . . . , 0, f
(ℎ)
i (Xi−1), 0, . . . , 0]
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.A. J. Slupik, V. I. Sushchansky 177
such that ℎ(f
(ℎ)
i (Xi−1)) = ℎ and pc(f
(ℎ)
i (Xi−1)) = 1. In such a way we
obtain a sequence of tableaux v
(pi−1)
i , v
(pi−1−1)
i , . . . , v
(1)
i . Next, using such
tableaux we can construct the sequence of tableaux w
(1)
i , . . . , w
(pi−1)
i , for
which [w
(k)
i ]i is a monomial of the height k with the coefficient 1. And
finally, using tableaux w
(k)
i (1 ≤ k ≤ pi−1) we can construct tableau ui
in the unique way.
5. The action Aut(Pn) on minimal sets of generators
Let Σn be the family of all minimal generating sets of Pn, i.e.
Σn = {{u1, u2, . . . , un} ; ⟨u1, u2, . . . , un⟩ = Pn} .
The group Aut(Pn) of all automorphisms of Pn acts on the set Σn ac-
cording to the rule
{u1, u2, . . . , un}
� = {u�1 , u
�
2 , . . . , u
�
n} ,
where {u1, u2, . . . , un} ∈ Σn and � ∈ Aut(Pn).
Note that, for any element u ∈ Pn, u ∕= e, the order ∣u∣ belongs to the
set {p, p2, . . . , pn}.
Definition 2. Let U = {u1, u2, . . . , un} be a minimal generating set of
Pn. The multiset {logp ∣u1∣, logp ∣u2∣, . . . , logp ∣un∣} is called the type of
the set U and denoted by t(U). For any basis u1, u2, . . . , un the type of
the set {u1, u2, . . . , un} is called the type of this basis.
We write the type t(U) as a vector (k1, k2, . . . , kn), k1 ≤ k2 ≤ . . . ≤ kn,
where ki = logp ∣u�(i)∣ for some permutation � ∈ Sn.
Lemma 6. Let u = [f1, f2(X1), . . . , fn(Xn−1)], where
fi(Xi−1) = aix
p−1
1 xp−1
2 ⋅ ⋅ ⋅xp−1
i−1
for i = 1, . . . , n. Then ∣u∣ = ps, where s = ∣{i ; ai ∕= 0}∣.
Proof. Let j be the smallest index of nonzero aj in u. Then u(j−1) = 0
and u(j) = [0, fj(Xj−1)]. We have
up(j) = [0, p ⋅ fj(Xj−1)] = [0, 0] ,
thus ∣u(j)∣ = p. Now, let us assume that for some l the order of u(l) is
equal to pm (m > 0). If fl+1 ∕= 0, then according to the fact 1.3 we have
uk(l+1) = [uk(l),
k−1∑
i=0
fl+1(X
ui
(l)
j−1)] .
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.178 Minimal generating sets and Cayley graphs
The smallest k, such that the first part uk(l) is equal zero, is pm. Then
up
m
(l+1) = [0,
pm−1∑
i=0
fl+1(X
ui
(l)
j−1)] ,
but
pm−1∑
i=0
fl+1
(
(0, 0, . . . , 0)︸ ︷︷ ︸
j−1
ui
(l)
)
= al(p − 1)m ∕= 0 . Hence ∣u(l+1)∣ > pm.
Since
up
m+1
(l+1) = [0, p ⋅
pm−1∑
i=0
fl+1(X
ui
(l)
j−1)] = [0, 0] ,
then ∣u(l+1)∣ = pm+1.
Using lemma 6 we prove
Lemma 7. The group Pn has minimal generating sets of types (1, 1, ..., 1)
and (n, n, ..., n).
Proof. The basis
u1 = [1, 0, 0, . . . , 0],
u2 = [0, xp−1
1 , 0, . . . . , 0],
u3 = [0, 0, xp−1
1 xp−1
2 , . . . , 0],
...
un = [0, 0, 0, . . . , xp−1
1 xp−1
2 ⋅ . . . ⋅ xp−1
n−1]
of Pn has the type (1, 1, . . . , 1).
For n = 1 there exist bases of the second type obviously. Let n = 2.
Then we take elements u1 = [1, xp−1
1 ] and u2 = [1, (p− 1)xp−1
1 ] from P2.
By lemma 6, ∣u1∣ = ∣u2∣ = p2. Since
det
[
'(u1)
'(u2)
]
= det
[
1 1
1 p− 1
]
= (p− 2) ∕= 0 ,
then u1 and u2 form a basis of P2.
Now, if n > 2, then we take tableaux
u1 = [(p− 1), xp−1
1 , xp−1
1 xp−1
2 , . . . , xp−1
1 xp−1
2 ⋅ xp−1
n−1] ,
u2 = [1, (p− 1)xp−1
1 , xp−1
1 xp−1
2 , . . . , xp−1
1 xp−1
2 ⋅ xp−1
n−1] ,
...
un = [1, xp−1
1 , xp−1
1 xp−1
2 , . . . , (p− 1)xp−1
1 xp−1
2 ⋅ xp−1
n−1] .
By lemma 6, ∣u1∣ = ∣u2∣ = . . . = ∣un∣ = pn. Since
det
⎡
⎢⎢⎢⎣
'(u1)
'(u2)
...
'(un)
⎤
⎥⎥⎥⎦ = det
⎡
⎢⎢⎢⎣
p− 1 1 . . . 1
1 p− 1 . . . 1
...
. . .
1 1 . . . p− 1
⎤
⎥⎥⎥⎦ =
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.A. J. Slupik, V. I. Sushchansky 179
= (p− 2)n−1(n− 2) ∕= 0
then u1, u2, . . . , un form a basis of Pn.
Let T = {(k1, k2, . . . , kn) ; 1 ≤ k1 ≤ . . . ≤ kn ≤ n}. We introduce the
componentwise partial order ⪯ on the set T , i.e. for (k1, k2, . . . , kn) and
(l1, l2, . . . , ln) from T we put (k1, k2, . . . , kn) ⪯ (l1, l2, . . . , ln) if, and only
if, ki ≤ li for i = 1, 2, . . . , n.
A vector (1, 1, . . . , 1) is the minimal element of the partially ordered
set (T,⪯) and a vector (n, n, . . . , n) is the maximal element of (T,⪯).
Theorem 3. For any vector t = (k1, k2, . . . , kn) ∈ T there exists a basis
of Pn of the type t.
Proof. Let us take some basis U = {u1, . . . , un} of Pn, where
[uj ]i = ajix
p−1
1 xp−1
2 ⋅ ⋅ ⋅xp−1
i−1 for i, j ∈ {1, . . . , n}. Let us denote by MU
the matrix
MU =
⎡
⎢⎢⎢⎣
'(u1)
'(u2)
...
'(un)
⎤
⎥⎥⎥⎦ =
⎡
⎢⎢⎢⎣
a11 a12 . . . a1n
a21 a22 . . . a2n
...
. . .
an1 an2 . . . ann
⎤
⎥⎥⎥⎦ .
We choose coefficients of MU according to the rules:
1) For every j ∈ {1, . . . , n} the number of nonzero coefficients aji of uj is
equal to kj ;
2) detMU ∕= 0.
First we assume that (1, 1, . . . , 1) ⪯ t ⪯ (1, 2, 3, . . . , n). Then we can
choose coefficients such that MU has zeroes over its diagonal:
MU =
⎡
⎢⎢⎢⎣
1 0 . . . 0
a21 1 . . . 0
...
. . .
an1 an2 . . . 1
⎤
⎥⎥⎥⎦ .
Coefficients under the diagonal are equal 0 or 1 according to the order of
elements. Hence detMU = 1.
Now, let (1, 2, 3, . . . , n) ⪯ t ⪯ (n, n, . . . , n). We define coefficients of
MU in the following way:
- if j = kj , then aji =
{
1 , for 1 ≤ i ≤ j
0 , j < i ≤ n
;
- if j < kj , then aji =
⎧
⎨
⎩
2 , for 1 ≤ i ≤ j
1 , for j < i ≤ kj
0 , kj < i ≤ n
.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.180 Minimal generating sets and Cayley graphs
Note that, the last row of MU always consists of 1. Now, we need to
use Gauss elimination starting from the last row. We reduce MU to the
following form: ⎡
⎢⎢⎢⎣
1 0 . . . 0
1 1 . . . 0
...
. . .
1 1 . . . 1
⎤
⎥⎥⎥⎦ .
So detMU = 1. This ends the proof.
Corollary 2. The set of all types of bases of Pn has (2n−1)!
n!(n−1)! elements.
Since for arbitrary basis U and any automorphism � ∈ Aut(Pn) the
equality
t(U�) = t(U)
holds, then the partition of Σ into subsets of generating sets with the
same type is coarser than the partition of Σ into orbits of the action
Aut(Pn).
6. The isomorphism problem of Cayley graphs of Pn
Let us denote by Cay(G,X) the Cayley graph of group G with respect to
the set of generators X. We consider Cay(G,X) as an undirected graph
with the set of vertices G. Every vertex g ∈ G is connected with vertex
gx±1 for all x ∈ X.
A Cayley graph Cay(G,X) with respect to a minimal set of generators
X is called a minimal Cayley graph of G [1].
Definition 3. A Caley graph Cay(G,S) is called a CI-graph of G if,
for any Cayley graph Cay(G, T ), whenever Cay(G,S) ∼= Cay(G, T ), we
have S� = T for some � ∈ Aut(G).
Definition 4. A p-group G is called MCI-group if all Cayley graphs with
recpect to minimal sets of generators are CI-graphs.
One of the very interesting problems is a characterization of groups
such that all its Cayley graphs are CI-graphs. This question has been
strongly investigated. Many criterions for a Cayley graph to be a CI-
graph were obtained. One of them mentioned below is very useful for our
consideration (for details and examples see [9]):
Lemma 8. [10] Let p be a prime and let G be a p-group. Then all Cayley
graphs of degree at most (2p− 2) are CI-graphs.
Using this statement for the group Pn we obtain the following result.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.A. J. Slupik, V. I. Sushchansky 181
Theorem 4. Let n ba a positive integer n ≥ 2, p be a prime p ≥ 3. If
n+ 1 ≤ p then Pn is a MCI-group.
Proof. It follows from corollary 1 that every minimal (according to in-
clusion) generating set of Pn has the size n. Since p ≥ 3, then for any
generator u we have u ∕= u−1. Hence degrees of all vertices of the Cayley
graph Cay(Pn, U) are equal to 2n for any minimal generating set U . If
n + 1 ≤ p, then 2n ≤ 2p − 2 and by lemma 8 the graph Cay(Pn, U) is
the CI-graph. Since U is an arbitrary minimal generating set, then the
group Pn is a MSI-group.
Due to this theorem, under the assumption n + 1 ≤ p, the isomor-
phism problem for minimal Cayley graphs of Pn can be reduced to the
characterization of orbits of the action of the group Aut(Pn) on the set
Σn. The automorphism group Aut(Pn) is well known (see [7], [8], [2]).
Aut(Pn) contains two natural subgroups: the subgroup of inner automor-
phisms Inn(Pn) and the subgroup A(Pn) consists of automorphisms of
the type
[a1, a2(x1), . . . , an(x1, x2, . . . xn−1)] 7→
[�1a1, �2a2(x1�
−1
1 ), . . . , �nan(x1�
−1
1 , x2�
−1
2 , . . . , xn−1�
−1
n−1)] ,
where [a1, a2(X1), . . . , an(Xn−1)] ∈ Pn, �i ∈ ℤ
∗
p (1 ≤ i ≤ n). It is easy
to verify that the group Aut0(Pn) = ⟨Inn(Pn), A(Pn)⟩ is decomposed
into the semidirect product A(Pn) ⋌ Inn(Pn). For n = 2 the equality
Aut0(Pn) = Aut(Pn) holds, and for n > 2 we have inequality Aut0(Pn) <
Aut(Pn).
Using the polynomial techniques described in the section 2 and a
characterization of some automorphisms of Pn, we can formulate various
necessary or sufficient conditions for an isomorphism of minimal Cayley
graphs. We will present the following examples.
1. Let us consider the following class U of bases of Pn:
u1(a1) = [a1, 0, 0, . . . , 0],
u2(a2) = [0, a2x
p−1
1 , 0, . . . , 0],
u3(a3) = [0, 0, a3x
p−1
1 xp−1
2 , . . . , 0],
...
un(an) = [0, 0, 0, . . . , anx
p−1
1 xp−1
2 ⋅ ⋅ ⋅xp−1
n−1],
where ai ∈ ℤ
∗
p for i = 1, 2, . . . , n.
Then, for any U, V ∈ U Cayley graphs Cay(Pn, U) and Cay(Pn, V )
are isomorphic, because there exists an automorphism ' from the sub-
group A(Pn), which maps any basis {u1(a1), u2(a2), . . . , un(an)} onto
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.182 Minimal generating sets and Cayley graphs
{u1(1), u2(1), . . . , un(1)}. The coefficients of ' are the following:
�1 = a−1
1 , �2 = a−1
2 , . . . , �n = a−1
n . □
2. Let us take an arbitrary basis U
u1 = [a
(1)
1 , a
(1)
2 (X1), . . . , a
(1)
n (Xn−1)],
u2 = [a
(2)
1 , a
(2)
2 (X1), . . . , a
(2)
n (Xn−1)],
...
un = [a
(n)
1 , a
(n)
2 (X1), . . . , a
(n)
n (Xn−1)]
,
where ℎ(a
(k)
i ) = pk−1 (i, k = 1, 2, . . . , n). If Û is the orbit of U under
the action Aut(Pn) on Σn, then ∣Û ∣ ≥ pn−1. It follows from the facts
described below.
Let us take the subset B = {[b1, b2, . . . , bn−1, 0] ; bi ∈ ℤ
∗
p} of Pn. Every
b ∈ B defines an inner automorphism 'b of Pn which acts as follows:
For any g = [g1, g2(X1), . . . , gn(Xn−1)] ∈ Pn we have
'b(g) = b−1gb = [g1, g2(x1 − b1), . . . , gn(x1 − b1, . . . , xn−1 − bn−1)] .
It is obvious that if b ∕= b′ (b, b′ ∈ B) and there exists i such that [g]i is
not a constant polynomial, then ['b(g)]i ∕= ['b′(g)]i. Since for the basis
U of Pn (n > 1) there exists i such that ℎ([ui]n) = pn−1, then we have
∣Û ∣ ≥ ∣{'b(U) ; b ∈ B}∣ = pn−1.
3. In general, the equality of types of two bases U and V does not
follow the existence of isomorphism between Cayley graphs Cay(Pn, U)
and Cay(Pn, V ). Let us consider the following two bases of P2 (p ∕= 2):
U : V :
u1 = [1, 0], v1 = [1, 0],
u2 = [0, xp−1
1 ], v2 = [0, 1− xp−1
1 ] .
We have t(U) = t(V ) = (1, 1). We will show that there is no possibility to
find automorphism � ∈ Aut0(P2) such that �(ui) = vi for i = 1, 2. Note
that, any inner automorphisms do not change the first coordinate of any
tableau and cannot change the coefficient of the monomial of maximal
height on the second coordinate of this tableau. Let us take an arbitrary
automorphism ' ∈ A. Since '(u1) = v1 = u1, then �1 = 1. This
automorphism should also change the coefficient of monomial of maximal
height so �2 = p−1. Then '(u2) = [0,−xp−1
1 ]. Now we consider an inner
automorphism a, where a = [a1, a2(x1)]. Then a(u1) = a−1 ⋅ u1 ⋅ a =
[1,−a2(x1−a1)+a2(x1−a1+1)]. So a2(x) = c from some c ∈ ℤp because
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.A. J. Slupik, V. I. Sushchansky 183
second coordinate must be equal 0. Then a('(u2)) = a−1[0,−xp−1
1 ]a =
[0,−(x1−a)
p−1]. The function −(x1−a)
p−1 is equal 0 for x1 = a and 1 for
the other x1, so it cannot be equal to the function 1− xp−1
1 . Hence there
is no possibility to have automorphism � = ' such that �(u2) = v2.
Because p ∕= 2 the group P2 is a MPI-group. It follows that Cay(P2, U)
and Cay(P2, V ) are not isomorphic.
4. Finally, we present the example of two bases U and V of P3:
u1 = [1, x21, x
2
1x
2
2] v1 = [2, x21, x
2
1x
2
2]
U: u2 = [1, 2x21, x
2
1x
2
2] V: v2 = [1, 2x21, x
2
1x
2
2]
u3 = [1, x21, 2x
2
1x
2
2] v3 = [1, x21, 2x
2
1x
2
2]
such that both of them have the type equals (3, 3, 3) and Cayley graphs
Cay(P3, U) and Cay(P3, V ) are not isomorphic. Those graphs are not
isomorphic because their diameters (i.e. the longest distance between
vertices of a graph in the standard graph metric) are equal to 12 and
11 respectively. Such diameters were obtained by computer calculations.
Note that, in this example the inequality n+ 1 ≤ p does not hold.
References
[1] Babai L. Automorphism Groups, Isomorphism, Recostruction. In: Handbook of
combinatorics, v. 2, Elsevier, 1995, 1447-1540.
[2] Bodnarchuk Y.V. Structure of the group of automorphisms of Sylow p-subgroup
of the symmetric group Spn (p ∕= 2), Ukr. Math. Zhurn., v. 36, 1984, 688-694 (in
ukrainian).
[3] Dixon J.D., Mortimer B., Permutation Groups, Springer-Verlag, 1996.
[4] Kaloujnine L. A. Sur les p-group de Sylow du groupe symetrique du degre pm, C.
R. Acad. Sci. Paris 221, 1945, 222-224.
[5] Kaloujnine L. A. La structure des p-groupes de Sylow des groupes symйtriques
finis, Annales scientifiques de l’Йcole Normale Supйrieure, Sйr. 3 , 65 1948, 239-
276,
[6] Konstantinova E. Some problems on Cayley graphs, Linear Algebra and its Appl.
429 (2008) 2754-2769.
[7] Lentoudis P. Le groupe des automorphismes du p-groupe de Sylow du groupe
symétrique de degré pm, C. R. Math. Rep. Acad. Sci. Canada, 7(2):133-136, 1985.
[8] Lentoudis P., Tits J. Sur le groupe des automorphismes de certains produits en
couronne, C. R. Acad. Sci. Paris 305, ser. I, 1987, 847-852.
[9] Li C.H., On isomorphisms of finite Cayley graphs - a survey, Discrete Mathemat-
ics, 256, 2002, 301-334.
[10] Li C.H., On isomorphisms of connected Cayley graphs, Discrete Mathematics ,
178, 1998, 109-122.
[11] Shalev A. Finite p-groups, In: Seitz G., Borowik A.V., Bryant R.M. (ed) Finite
and locally finite groups, Kluwer Acad. Publ., 1995, 401-450.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.184 Minimal generating sets and Cayley graphs
Contact information
A. J. Slupik Institute of Mathematics
Silesian University of Technology
Gliwice
E-Mail: anna.slupik@polsl.pl
V. I. Sushchansky Institute of Mathematics
Silesian University of Technology
Gliwice
E-Mail: vitaliy.sushchanskyy@polsl.pl
Received by the editors: 07.10.2009
and in final form 07.10.2009.
|