The
-orbit theory and polycirculant conjecture
Aleksandr Golubchik Osnabrueck, Germany,
15.03.2005
Abstract
The paper contains a proof of the conjecture of M. Klin and D. Maru
i
that an automorphism group of a transitive graph contains a permutation, decomposed in cycles of the same length. The proof is based on the
-orbit theory developed by author. Key words:
-orbits, partitions, permutations, symmetry, groups
1 Introduction
A permutation group
is called
-closed if it is an automorphism group of a graph, another if it is an automorphism group of an ordered partition
of a set
. If
and
, then one says that
is a
-closure for
. A permutation is called regular if it is decomposed in cycles of the same length.
In [1] P. Cameron described the conjecture of M. Klin and D. Maru
i
(Polycirculant conjecture) that was announced on the British Combinatorial Conference (Problem BCC15.12 (DM282)) in July 1995:
Theorem 1
Every
-closed transitive group contains a regular element.
Below we give a proof of this statement, based on the
-orbit theory developed by author.
The first attempt to describe this theory was launched in [3] .
2
-Orbit theory
Let
be a permutation group of a degree
and
(
) be a non-diagonal part of
(i.e. all
values of coordinates of a
-tuple
are different), then the action of
on
forms a partition
of
on
-invariant classes. This partition is called a system of
-orbits of
and we denote it as
.
The
-orbit theory studies symmetry properties of
-orbits that cannot be obtained from permutation group theory, studying a permutation group
as a permutation algebra and therefore being not able to see the inside structure of a
-orbit of
and relations between
-orbits of subgroups of
. Also the graph representation of permutation groups that considers an action of a permutation group on
is not able to see all relations in
for
.
The
-orbit theory gives a new view on abstract finite groups and finite permutation groups and shows a way to simple solutions of some problems which either are not solved or have a complicated solution. These problems are: the polynomial solution of graphs isomorphism problem; the problem of a full invariant of finite groups, admitting a primitive (isomorphic) permutation representation; a simple proof of the Feit-Thompson theorem: the solvability of finite groups of odd order (that lies in the foundation of the Classification of finite simple groups [6] ); The simple proof of the Fein-Kantor-Schacher theorem: any transitive permutation group contains a fixed-point-free prime-power element [5] ; and the problem that we consider in this paper.
The specificity of the
-orbit representation of a group
is a possibility to do a group visible. In order to go to this visibility one makes a partition of a matrix of a
-orbit on cells of
-orbits of subgroups of an investigated permutation group
and studies symmetry properties of cells and the whole partition. Below we consider some facts from the
-orbit theory which are necessary for the proof of theorem 1 .
The
-orbit theory considers different actions of permutations on
-sets and symmetries that follows from those actions. Let
be a
-tuple, then the left action of a permutation
on
is defined as
and the right action of
on
is given as
(here
). From that we obtain the left and right action of a permutation on
-tuples and
-sets.
The left action of a permutation is (on definition) an isomorphism (
), the right action is not an isomorphism (
). If the right action is an isomorphism, then it is an indicium for existing of a subgroup with non-trivial normalizer, whose
-orbit contains (right-)isomorphic
-subsets connected with considered right action.
Let
be a
-orbit of
. One of
-tuples from
we choose as an initial
-tuple and consider all permutations from
relatively to this
-tuple. If
is an initial
-tuple, then
. The specificity of an initial
-tuple is the equality of number and order values of its coordinates (that we take from the same ordered set
). We call the initial
-tuple as
-space and its ordered subsets as subspaces. A
-orbit
of
is a projection of
on some subspace
. We write this projection as
. So we consider subspaces as ordered sets of coordinates and
-orbits as non-ordered sets of
-tuples. The different orderings of
-tuples (lines) in a matrix of a
-orbit shows different symmetry properties of
-orbit, related with corresponding properties of the investigated permutation group.
We say that two
-sets
and
are
-isomorphic if they are isomorphic and connected with a permutation
:
. If we study a group
and
are isomorphic, but not
-isomorphic, then we say that they are
-isomorphic (where
is the symmetric group).
We define the left action
of a group
on a
-subset
as
. The left action
of a subgroup
on a
-orbit
of
is given as
.
Correspondingly the right action
and
. The left action of
on a
-set
and
on a
-orbit
of
for
is the same as for
, because
. By the right action the equality
has senseonly if
is the initial
-tuple. Hence the right action on
-sets has not a direct reduction from the right action on
sets. If
is a
-orbit of
,
and
is a
-orbit of
, then
and
are partitions of
on
-orbits of left and right cosets of
in
, at that
-orbits of left cosets are
-orbits of conjugate with
subgroups of
and
-orbits of right cosets are
-orbits of
. Projections of
,
and
on a subspace
gives a covering
and a partition
of the
-orbit
on
-orbits of left and right cosets of
in
. If
, then
and
. Below under action of permutations we understand the left action.
Let
be a divisor of
. We call
as an automorphic number if there exists a
-element suborbit of
(a
-element orbit of a subgroup of
).
Let
be a set of coordinates of a
-tuple
, then for a
-set
we define
as
.
If
is a suborbit of
, then we say that
is an automorphic
-tuple and
is an automorphic subset of
. Let
be a
-set we say that
is an automorphic
-set, if
acts on
transitive. Let
be a
-orbit (an automorphic
-set) and
be an automorphic
-tuple, then a
-orbit
we call as right-automorphic
-orbit or
-rorbit.
Let
be a set and
be a set of subsets of
, then
. Under
we understand a set of unions of intersected on
classes of
. So
is a partition of
(possibly trivial). A union and intersection of partitions
and
of
we write as
and
. Let
be a subpartition of
, then we write
.
Let
and
be a maximal subset of
with
, then we call
as a
-block of
.
Let
and
be a non-trivial partition of
, then we say that
is incoherent. If
is a non-trivial covering of
, then we say that
is coherent. Any coherent
-orbit consists of intersected on
-blocks. Classes of a partition of an incoherent
-orbit are coherent
-suborbits or
-blocks. A coherent
-orbit
is defined on a set
. Its coherent or incoherent
-suborbit
is defined on a set
.
In order to show this we say that
is
-coherent (
-incoherent). If a (
-) coherent
-orbit contains no
-coherent and no
-incoherent
-suborbit for any
, then we call it as elementary coherent.
Let
be a
-suborbit of
. The maximal transitive on
subgroup of
we call a stabilizer of
in
and write it as
or simply
.
Let
be a
-orbit of
and
be a
-block, then evidently
is a partition of
and
is a
-orbit of
.
Let a group
be imprimitive, then
contains a non-trivial (
) incoherent
-orbit.
If
is primitive, then any (non-trivial)
-orbit of
is coherent. From here follows that it is convenient to consider primitive Abelian groups as trivial imprimitive or trivial primitive, because, as distinct from non-Abelian primitive groups, such a group
contains no non-trivial suborbit
that forms a covering
of
. So further under a primitive group we understand a non-Abelian primitive group. Let a group
be imprimitive and
be a
-invariant partition of
(
), then we say that classes of
are imprimitivity blocks.
We say that a transitive group
is a minimal degree group or md-group if it cannot be represented isomorphically on a partition
of
, otherwise we say that
is a non-minimal degree group or nmd-group. It follows that primitive groups are md-groups. Let
be a finite group,
and a representation
be a md-group isomorphic to
, then we say that
is a md-stabilizer of
. So
is a maximal by including subgroup of
containing no normal subgroup of
.
Let
and
, then a
-tuple
we call a concatenation of
and
and write this as
.
Proposition 2
Let
be an automorphic
-tuple,
,
and
, then
is a normal subgroup of
and a factor group
is isomorphic to
.
Proof: If
is not trivial, then
is an intransitive group. Let
be a
-orbit of
, then there exists only one partition
of
on
classes with projection
.
Hence
. The group
is isomorphic to the factor group
, because
and it acts on cosets of
in
transitive.
Proposition 3
Let
,
be a
-suborbit of
,
,
and
. Let
, then
is a normal subgroup of
.
Proof: There exists only one partition
of
on
classes so that
.
Hence
.
Proposition 4
Let
be an imprimitive group,
be a partition of
on imprimitivity blocks and
be ordered set
, then
is a normal subgroup of
.
Proof: Subgroups
form a class of conjugate subgroups and
. If
is a nmd-group and
is an isomorphism, then
is trivial.
Proposition 5
Let
,
be
-suborbits of
,
and
, then
and
are also partitions of
on isomorphic
-suborbits of
. If
be not trivial and
contains
and
, then
,
,
and
.
Proof: Let
, then equalities follows from corresponding properties of sets of left cosets of subgroups of
. For
equalities are projections of corresponding equalities for
.
Lemma 6
Let for every
-suborbit
of a
-orbit
a set
be a partition of
, then
.
Proof: Let
,
be a set of partitions of
on isomorphic
-suborbits of
and
, then
and
are partitions from
. Let
be a partition of
on
-blocks, then there exists a partition
so that
is not trivial, i.e.
. By repeating we obtain that there exist partitions
so that
.
For each partition
in the union process there exists a subgroup
so that a class
is a
-orbit of
and
, because we can begin from a subgroup that is isomorphic to the automorphism group of a
-block, and with a subgroup of a prime order that permutes
-blocks. Thus
contains a subgroup
of order
that acts transitive on
.
Let
be any permutation from
and
, then
, because any class
of
generates a partition
. It follows that the action of
and
on
are isomorphic and hence
.
Proposition 7
Let
be an incoherent automorphic
-set, then
.
Proof: If
is incoherent, then
has evidently a permutation that fixes a
-tuple from
.
Lemma 8
Let
be an elementary coherent
-orbit, then
.
Proof: Let
be a
-block and
be a
-suborbit of
that has non-trivial intersection with
. Let
, then
-orbit of
in
is
, because the elementary coherent
-orbit
is the unique super-
-suborbit for any
-block.
Hence
is a partition of
. Then the statement follows from lemma 6 .
Lemma 9
Let
be a transitive group, a
-tuple
,
,
and
be automorphic and
-isomorphic, and
contains no
-tuple
-isomorphic to
, then
-
∙
the
-tuple
is automorphic,
-
∙
the group
is not trivial,
-
∙
the group
has a normalizer
that acts imprimitive on
with imprimitivity blocks
and
.
Proof: Let
,
,
and
. Let
be
-blocks with coordinates
and
. Consider a maximal
-subset
, whose projection on
is
and a maximal
-subset
, whose projection on
is
. The
-subset
can be partition on
-orbits of
and the
-subset
can be partition on
-orbits of
. Take in opinion that
and
have on condition non-trivial intersection with any
-tuple from
and that the intersection
contains
, we obtain that
is a
-orbit of the non-trivial subgroup
.
Let now
be maximal
-subsets with projection
on
and
correspondingly, then
is a
-orbit of the imprimitive on
normalizer
of
with imprimitivity blocks
and
.
For the greater than two automorphic
-isomorphic subsets we have more possibilities for permutations of subsets and therefore find more possible properties.
Lemma 10
Let
,
,
, all
are automorphic and
-isomorphic and no class of
belongs to
, then
-tuple
is automorphic, a subgroup
can be trivial and has a normalizer
that acts imprimitive on
with imprimitivity blocks
.
Proof: Let
and
. If
maps
on
, then
can be mapped on any
-tuple with coordinates
. So in this case
can be trivial, but
is not trivial, because subsets
are non-intersected in pairs and, on condition, they are intersected with any
-tuple from
, where
are
-blocks with
.
Theorem 11
Let
be a primitive group and
be a maximal automorphic divisor of
, then there exists a partition
of
on automorphic
-isomorphic
-subsets or on automorphic
-isomorphic
-subsets.
Proof: Let the statement be not correct, then there exists a subset
of
that can be partition on automorphic
-isomorphic
-tuples
( where
), and the subset
contains no automorphic
-tuple
-isomorphic to
, then from lemma 10 immediately follows that
is an automorphic subset. If
divides
, then
is not the maximal divisor of
. Contradiction. So
does not divide
and
is a covering of
.
Let
, then
and
are
-invariant and therefore an intersection of any two classes of
contains whole number of
-tuples from
. Hence
must contain some class from
. Contradiction.
Lemma 12
A nmd-group is
-closed.
Proof: Let
be not
-closed a nmd-group and
be a
-closure of
, then
and
have the same set of imprimitivity blocks
and hence
is a md-group.
Let
be a md-reduction of
and
be a md-reduction of
. Since
is not
-closed, then
is not
-closed too and hence
. It follows that
is isomorphic to
, i.e.
is a nmd-group. Contradiction.
Lemma 13
Let
be a set of imprimitivity blocks of a nmd-group
and
, then
is trivial.
Proof: Let
,
,
and
, then from lemma 12 it follows that
. Let
,then there exists a partition
of
so that
. It follows that
and hence
contain a subgroup
of order
. Then there exists only one partition
of
on
automorphic classes so that
, hence
is a normal subgroup of
. Let a representation
be a md-group, then
is a md-stabilizer of
. But
has non-trivial intersection with
and hence it cannot be a md-stabilizer of
. Contradiction.
Lemma 14
Let
be a nmd-group, then there exists an isomorphic representation
of
on imprimitivity blocks of a prime power.
Proof: Let
be not prime and
be a prime divisor of
. Let
, then
contains an automorphic
-tuple
, so that
. Hence
has an imprimitive representation on classes of
. If
is a homomorphism, then
is a homomorphism too. Contradiction. Thus
is an isomorphism.
This statement can be generalized:
Lemma 15
Let
be a partition of
and
be a homomorphism of
, then there exists a partition
on subsets of
of a prime power so that
is also a homomorphism, at that if
is an isomorphism, then
is an isomorphism too.
3 The proof of theorem 1
3.1 Imprimitive nmd-groups
From lemma 14 it follows that any nmd-group contains a regular element.
3.2 Primitive groups
Let
be a primitive group. If
contains a nmd-subgroup, then it contains a regular element.
Let
contains no nmd-subgroup, but an imprimitive md-subgroup
.
Lemma 16
Let
be a maximal imprimitive md-subgroup of
, then
is
-closed if and only if
is
-closed.
Proof: Let
be a set of imprimitivity blocks of
, then
and all classes of
(partitions of
) are different. Let
,
and
. Let
be not
-closed, then any class
is not
-closed and hence
is not
-closed. Let
be not
-closed and
be a
-closure of
, then
contains an imprimitive on
-suborbit
that is a
-closure of
.
Thus a consideration of a primitive group
can be reduced to a consideration of its imprimitive md-subgroup. So we have to consider a primitive group that contains no imprimitive subgroup.
Lemma 17
Let
contains no imprimitive subgroup, then it is not
-closed.
Proof: If
contains no imprimitive subgroup, then (lemma 10 and theorem 11 ) there exists a partition
of
on automorphic
-isomorphic
-subsets and no partition of
on automorphic
-isomorphic
-subsets. Let
,
,
and
, then any two
-blocks from a
-orbit
are intersected on
. Hence a non-trivial normalizer
of
is a
-closure of
.
So we can reduce the consideration of theorem 1 to imprimitive md-groups.
3.3 Imprimitive md-groups
Let
be an imprimitive md-group and
be a partition of
on imprimitivity blocks, then a group
is not trivial. Let
,
,
and
be
-closed, then
is also
-closed and hence
, where
is an extension of
on
. Accordingly to lemma 15 we can assume that
is prime, then
(for any
) is a direct product and contains a regular element of order
. Hence
contains a regular element of order
.
Conclusion The main inference from the investigation of
-orbits symmetry properties is that a finite group
is not closed by its algebraic properties, because the group algebra
is equivalent to the action of
on
, but this algebra generates also the action of
on
. Properties of that action not always can be interpreted with group algebra or with traditional permutation group theory. Namely such properties are the subject of investigation of the
-orbit theory. Some investigations related with an application of
-orbit representation to problems announced above are described in [2] - [4] The
-orbit theory gives a new view on finite many-dimensional symmetries and can bring new ideas and applications to other sciences studying symmetrical objects.
References
-
Peter J. Cameron, Elusive groups and the polycirculant conjecture, Queen Mary, University of London, Barcelona, February 2001
-
Aleksandr Golubchik, The polynomial algorithm for graphs' isomorphism testing,
, February 2002.
☻ open access ✓
-
Aleksandr Golubchik, On the Polycirculant conjecture,
, April 2002.
☻ open access ✓
-
Aleksandr Golubchik, On the nature of finite groups,
, September 2004.
☻ open access ✓
-
Aleksandr Golubchik, The
-orbit theory and Fein-Kantor-Schacher Theorem,
, February 2005.
☻ open access ✓
-
Daniel Gorenstein, Finite simple groups, Plenum Press, New York and London, 1982