Transcript The least known

The least known length
of ordered basis of
symmetric group
S. A. Kalinchuk,
Yu. L. Sagalovich
Institute for Information Transmission
Problems, Russian Academy of Sciences
ACCT 2008
Introduction



ACCT 2006 paper “The problem of minimal ordered basis of
symmetric group”
Set of all transpositions as a basis of symmetric group Sn
Questions



Is it possible to use less number of transpositions for
obtaining all n! permutations?
Is it possible to fix the sequence of transpositions by
the only way for all products?
(2,4) (2,3) (1,4) (1,2) (1,3)
ACCT 2008
Ordered basis definition

symmetric group with degree
an ordered system of transpositions of


on the set of numbers
Definition:
The system
is called ordered basis of symmetric group
any permutation
can be represented as
,
if
where
ACCT 2008
Preliminaries

There exist the ordered bases with the transpositions’ number
of order
. For example,

The obtained result is based on that the degree
symmetric group
is chosen to be equal to
of
ACCT 2008
Main results



Let
,
Partition
Proposition 1:
Any permutation
where
groups

of group
can be factored as
and
are some permutations belonging to symmetric
and
correspondingly, and a permutation
of group
has the form as
Example:
ACCT 2008
Main results

Proposition 2:
Let
and
be ordered bases of groups
correspondingly.
and
Let
be an ordered system of transpositions of group
and let this system generate permutations of the form
,
.
Then the system
is the ordered basis of group
ACCT 2008
Main results

Partition

Let


Let
and
be some permutations defined on the set
Consider an ordered system of transpositions

Example:
and
ACCT 2008
Main results

Proposition 3:
Let
and
be some ordered systems of transpositions
generating permutations of the forms
and
correspondingly.
Then the system
generates permutations of the form
at any
and
.
ACCT 2008
Ordered basis construction


Symmetric group
on
Partition recurrently the set
The system

is the order basis of
Let


where
ACCT 2008
Ordered basis construction


Symmetric group
on
Partition recurrently the set
The system

is the order basis of
Let


where
ACCT 2008
Ordered basis construction


Symmetric group
on
Partition recurrently the set
The system

is the order basis of
Let


where
ACCT 2008
Ordered basis construction example
Since
apply
ACCT 2008
Ordered basis construction example
Since
apply
ACCT 2008
Ordered basis construction example
ACCT 2008
Ordered basis construction example
ACCT 2008
Ordered basis construction example

The constructed ordered basis consists of
76 transpositions

Total number of all transpositions in S16 is 120
ACCT 2008
Ordered basis length

Differs from lower bound
only in factor
ACCT 2008