NDTypesAndRC(G,S) |
|---|
Calculates the nondegenerate types of the action of G on S up to permutation of the
coordinates and the relational complexity.
G: a permutation group
S: the set being acted upon, given as a set
Return: a record with entries ndtypesreps and rc, or fail if S is not a
set.
ndtypesreps: a list such that for each n ndtypesreps[n] is a list of
representatives from
each of the nondegenerate n-types up to permutation of the coordinates
rc: the relational complexity
Options:
verbose: if set to true, the function will output a variety of information as it runs.
|
Examples:
- Investigate the primitive action of $M_{23}$ on 23 points
<gap> Read("./RComp.g");
<gap> # Create M_23 in its primitive action on 23 points
<gap> G:=PrimitiveGroup(23,5);
M(23)
<gap> NDTypesAndRC(G,[1..23]);
rec(
ndtypesreps := [ [ [ 1 ] ], [ [ 1, 2 ] ], [ [ 1, 2, 3 ] ],
[ [ 1, 2, 3, 4 ] ], [ [ 1, 2, 3, 4, 5 ], [ 1, 2, 3, 4, 6 ] ],
[ [ 1, 2, 3, 4, 5, 6 ], [ 1, 2, 3, 4, 5, 7 ], [ 1, 2, 3, 4, 5, 8 ],
[ 1, 2, 3, 4, 5, 9 ], [ 1, 2, 3, 4, 5, 12 ], [ 1, 2, 3, 4, 5, 14 ]
] ], rc := 7 )
- Investigate the action of $\operatorname{GL}_4(3)$ on $2$-dimensional subspaces of
$\operatorname{GF}(3)^4$
<gap> # Create the action of GL(4,3) on 2-dimensional subspaces of GF(3)^4
<gap> G := GL(4,3);;
<gap> subspaces := Subspaces(FullRowSpace(GF(3),4),2);;
<gap> G_as_perm_grp := Action(G,subspaces,OnRight);;
<gap> rc_data := NDTypesAndRC(G_as_perm_grp,[1..Size(subspaces)]:verbose);;
2->3 ... num. non-deg. 2-type classes: 2 ... rc lower bound: 2 ...
3->4 ... num. non-deg. 3-type classes: 9 ... rc lower bound: 3 ...
4->5 ... num. non-deg. 4-type classes: 86 ... rc lower bound: 4 ...
5->6 ... num. non-deg. 5-type classes: 2074 ... rc lower bound: 5 ...
6->7 ... num. non-deg. 6-type classes: 1056 ... rc lower bound: 6 ...
7->8 ... num. non-deg. 7-type classes: 33 ... rc lower bound: 6 ...
<gap> rc_data.rc;
8
|
HeightAndRC(G,S) |
|---|
Calculates the height, i.e. the maximum size of an independent set, and relational
complexity of the action of G on S.
G: a permutation group
S: the set being acted upon, given as a set
Return: a record with entries height and rc, or fail if S is not a
set.
height: the height
rc: the relational complexity
Options:
verbose: if set to true, the function will output a variety of information as it runs.
|
Examples:
- Investigate the primitive action of $M_{23}$ on 23 points
<gap> # Create M_23 in its primitive action on 23 points
<gap> G:=PrimitiveGroup(23,5);;
<gap> HeightAndRC(G,[1..23]);
rec( height := 6, rc := 7 )
- Investigate the action of $\operatorname{GL}_4(3)$ on $2$-dimensional subspaces of
$\operatorname{GF}(3)^4$
(see the example for
HeightAndRCMatrixGroupOnSubspaces as well)
<gap> # Create the action of GL(4,3) on 2-dimensional subspaces of GF(3)^4
<gap> G := GL(4,3);;
<gap> subspaces := Subspaces(FullRowSpace(GF(3),4),2);;
<gap> G_as_perm_grp := Action(G,subspaces,OnRight);;
<gap> rc_data := HeightAndRC(G_as_perm_grp,[1..Size(subspaces)]);;
2->3 ... num. non-deg. 2-type classes: 2 ... rc lower bound: 2 ...
3->4 ... num. non-deg. 3-type classes: 9 ... rc lower bound: 3 ...
4->5 ... num. non-deg. 4-type classes: 86 ... rc lower bound: 4 ...
5->6 ... num. non-deg. 5-type classes: 2074 ... rc lower bound: 5 ...
6->7 ... num. non-deg. 6-type classes: 1056 ... rc lower bound: 6 ...
7->8 ... num. non-deg. 7-type classes: 33 ... rc lower bound: 6 ...
<gap> rc_data.rc;
8
<gap> rc_data.height;
7
- Investigate action of $\operatorname{Sym}(8)$ on the set of partitions of $\{1,\ldots,8\}$ into 2 blocks of
size 4
(see the example for
HeightAndRCSymOnPartitions as well)
<gap> # Create the action of Sym(8) on partitions of [1..8] into 2 blocks of size 4
<gap> G := SymmetricGroup(8);;
<gap> O := Orbit(G,[[1,2,3,4],[5,6,7,8]],OnSetsSets);;
<gap> G_as_perm_grp:=Action(G,O,OnSetsSets);;
<gap> HeightAndRC(G_as_perm_grp,[1..Length(O)]);
rec( height := 5, rc := 5 )
|
HeightAndRCMatrixGroupOnVectors(G,dim_of_vs,size_of_field) |
|---|
Calculates the height, i.e. the maximum size of an independent set, and relational
complexity of the action of the matrix group G on the vector space of dimension dim over the
field with size_of_field many elements.
G: a dim$\times$dim matrix group over the field with
size_of_field many elements
dim: dimension of the vector space
size_of_field: size of the field for the vector space
Return: a record with entries height and rc, or fail if S is not a
set.
height: the height
rc: the relational complexity
Options:
verbose: if set to true, the function will output a variety of information as it runs.
|
Examples:
- Investigate the actions of $\operatorname{GL}_4(3)$ and $\operatorname{SL}_4(3)$ on the vector space
$\operatorname{GF}(3)^4$
<gap> G := GL(4,3);;
<gap> HeightAndRCMatrixGroupOnVectors(G,4,3);
rec( height := 4, rc := 5 )
<gap> H := SL(4,3);;
<gap> HeightAndRCMatrixGroupOnVectors(H,4,3);
rec( height := 4, rc := 4 )
|
HeightAndRCMatrixGroupOnSubspaces(G,dim_of_vs,size_of_field,dim_of_sub) |
|---|
Calculates the height, i.e. the maximum size of an independent set, and relational
complexity of the action of the matrix group G on the set of subspaces of dimension dim_of_sub
of the vector space of dimension dim over the
field with size_of_field many elements.
G: a dim$\times$dim matrix group over the field with
size_of_field many elements
dim: dimension of the vector space
size_of_field: size of the field for the vector space
dim_of_sub: dimension of the subspaces on which to act
Return: a record with entries height and rc, or fail if S is not a
set.
height: the height
rc: the relational complexity
Options:
verbose: if set to true, the function will output a variety of information as it runs.
|
Examples:
-
Investigate the actions of $\operatorname{GL}_4(3)$ on $1$-dimensional subspaces of
$\operatorname{GF}(3)^4$
<gap> G := GL(4,3);;
<gap> HeightAndRCMatrixGroupOnSubspaces(G,4,3,1);
rec( height := 6, rc := 4 )
|
HeightAndRCSymOnPartitions(num_blocks, block_size) |
|---|
Calculates the height, i.e. the maximum size of an independent set, and relational
complexity of the action of $\operatorname{Sym}(n)$, for n = num_blocks*block_size, on the
set of partitions of $\{1\ldots n\} into num_blocks of blocks of size block_size.
num_blocks: number of blocks in the shape of the partition
block_size: the block size in the shape of the partition
Return: a record with entries height and rc, or fail if S is not a
set.
height: the height
rc: the relational complexity
Options:
verbose: if set to true, the function will output a variety of information as it runs.
|
Examples:
-
Investigate action of $\operatorname{Sym}(6)$ on the set of partitions of $\{1,\ldots,6\}$ into 2 blocks of
size 3
<gap> HeightAndRCSymOnPartitions(2,3);
rec( height := 4, rc := 3 )
|
RandomSearchNDTypesAndRC(G,S,growth_factor) |
|---|
Calculates the some of the nondegenerate types of the action of G on S up to
permutation of the
coordinates and finds a lower bound for the relational complexity. The function begins by
computing *all* nondegenerate 1 and 2-types (up to permutation of the coordinates). Then, for
each nondegenerate 2-type, 'growth_factor' many extensions to 3-types are computed by randomly
choosing growth_factor many orbits of the stabilizer of the 2-type. Each extension is then
tested against *all* other extensions to see if the relational complexity goes up. Finally, the
randomly chosen extensions are tested for nondegeneracy, and if there are any, the function
repeats the process for the nondegenerate 3-types, and so on.
G: a permutation group
S: the set being acted upon, given as a set
growth_factor: number of extensions to compute for each nondegenerate n-type
Return: a record with entries ndtypesreps and rclowerbound, or
fail if S is not a set.
ndtypesreps: a list such that for each n ndtypesreps[n] is a list of
representatives from each of the nondegenerate n-types that the function found (up to
permutation of the coordinates
rclowerbound: a lower bound for the relational complexity
Options:
verbose: if set to true, the function will output a variety of information as it runs.
|
Examples:
- Investigate action of $\operatorname{Sym}(16)$ on the set of partitions of $\{1,\ldots,16\}$
into 2 blocks of size 8
<gap> # Create the action of Sym(16) on partitions of [1..16] into 2 blocks of size 8
<gap> G := SymmetricGroup(16);;
<gap> O := Orbit(G,[[1..8],[9..16]],OnSetsSets);;
<gap> G_as_perm_grp:=Action(G,O,OnSetsSets);;
<gap> Length(O)
6435
<gap> rc_data := RandomSearchNDTypesAndRC(G_as_perm_grp,[1..Length(O)],2:verbose);;
2->3 ... num. non-deg. 2-type classes: 4 ... rc lower bound: 2 ...
3->4 ... num. non-deg. 3-type classes: 7 ... rc lower bound: 3 ...
4->5 ... num. non-deg. 4-type classes: 12 ... rc lower bound: 4 ...
5->6 ... num. non-deg. 5-type classes: 17 ... rc lower bound: 5 ...
6->7 ... num. non-deg. 6-type classes: 9 ... rc lower bound: 5 ...
<gap> rc_data.rclowerbound;
5
<gap> # run again - the results will almost surely be different
<gap> rc_data := RandomSearchNDTypesAndRC(G_as_perm_grp,[1..Length(O)],2:verbose);;
2->3 ... num. non-deg. 2-type classes: 4 ... rc lower bound: 2 ...
3->4 ... num. non-deg. 3-type classes: 6 ... rc lower bound: 3 ...
4->5 ... num. non-deg. 4-type classes: 12 ... rc lower bound: 4 ...
5->6 ... num. non-deg. 5-type classes: 19 ... rc lower bound: 4 ...
6->7 ... num. non-deg. 6-type classes: 5 ... rc lower bound: 4 ...
7->8 ... num. non-deg. 7-type classes: 1 ... rc lower bound: 4 ...
<gap> rc_data.rclowerbound;
4
|
HeightAndRCLB(G,S,growth_factor) |
|---|
Calculates a lower bound for the height, i.e. the maximum size of an independent set, and
a lower bound for the relational complexity of the action of G on S
(using the function RandomSearchNDTypesAndRC).
G: a permutation group
S: the set being acted upon, given as a set
growth_factor: number of extensions to compute for each nondegenerate n-type
Return: a record with entries heightlowerbound and rclowerbound,
or fail if S is not a set.
heightlowerbound: a lower bound for the height
rclowerbound: a lower bound for the relational complexity
Options:
verbose: if set to true, the function will output a variety of information as it runs.
|
Examples:
- Investigate the primitive action of $Co_{3}$ on 276 points
<gap> G:=PrimitiveGroup(276,3);
Co_3
<gap> # run with growth factor of 2
<gap> HeightAndRCLB(G,[1..276],2);
rec( heightlowerbound := 4, rclowerbound := 3 )
<gap> # run with growth factor of 5
<gap> HeightAndRCLB(G,[1..276],5);
rec( heightlowerbound := 2, rclowerbound := 2 )
<gap> # run again with growth factor of 5
<gap> HeightAndRCLB(G,[1..276],5);
rec( heightlowerbound := 7, rclowerbound := 7 )
- Investigate action of $\operatorname{Sym}(12)$ on the set of partitions of
$\{1,\ldots,14\}$ into 3 blocks of size 4
(see the example for
HeightAndRCLBSymOnPartitions as well)
<gap> # Create the action of Sym(12) on partitions of [1..12] into 3 blocks of size 4
<gap> G := SymmetricGroup(12);;
<gap> O := Orbit(G,[[1..4],[5..8],[9..12]],OnSetsSets);;
<gap> G_as_perm_grp:=Action(G,O,OnSetsSets);;
<gap> # run HeightAndRCLB a few times with a growth factor of 2
<gap> HeightAndRCLB(G_as_perm_grp,[1..Length(O)],2);
rec( heightlowerbound := 4, rclowerbound := 4 )
<gap> HeightAndRCLB(G_as_perm_grp,[1..Length(O)],2);
rec( heightlowerbound := 4, rclowerbound :=3 )
<gap> HeightAndRCLB(G_as_perm_grp,[1..Length(O)],2);
rec( heightlowerbound := 4, rclowerbound := 4 )
|
HeightAndRCLBSymOnPartitions(num_blocks, block_size, growth_factor) |
|---|
Calculates a lower bound for the height, i.e. the maximum size of an independent set, and
a lower bound for the relational complexity of the action of $\operatorname{Sym}(n)$, for
n = num_blocks*block_size, on the set of partitions of $\{1\ldots n\} into
num_blocks of blocks of size block_size (using the function
RandomSearchNDTypesAndRC).
num_blocks: number of blocks in the shape of the partition
block_size: the block size in the shape of the partition
growth_factor: number of extensions to compute for each nondegenerate n-type
Return: a record with entries heightlowerbound and rclowerbound,
or fail if S is not a set.
heightlowerbound: a lower bound for the height
rclowerbound: a lower bound for the relational complexity
Options:
verbose: if set to true, the function will output a variety of information as it runs.
|
Examples:
-
Investigate action of $\operatorname{Sym}(9)$ on the set of partitions of $\{1,\ldots,18\}$ into 2 blocks of
size 9
<gap> # using a growth factor of 1
<gap> HeightAndRCLBSymOnPartitions(2,9,1:verbose);
Num. Partitions: 24310
2->3 ... num. non-deg. 2-type classes: 4 ... rc lower bound: 2 ...
3->4 ... num. non-deg. 3-type classes: 3 ... rc lower bound: 3 ...
4->5 ... num. non-deg. 4-type classes: 3 ... rc lower bound: 3 ...
5->6 ... num. non-deg. 5-type classes: 1 ... rc lower bound: 3 ...
rec( heightlowerbound := 5, rclowerbound := 3 )
<gap> # using a growth factor of 2
<gap> HeightAndRCLBSymOnPartitions(2,9,2:verbose);
Num. Partitions: 24310
2->3 ... num. non-deg. 2-type classes: 4 ... rc lower bound: 2 ...
3->4 ... num. non-deg. 3-type classes: 6 ... rc lower bound: 3 ...
4->5 ... num. non-deg. 4-type classes: 12 ... rc lower bound: 4 ...
5->6 ... num. non-deg. 5-type classes: 13 ... rc lower bound: 4 ...
6->7 ... num. non-deg. 6-type classes: 8 ... rc lower bound: 4 ...
7->8 ... num. non-deg. 7-type classes: 1 ... rc lower bound: 4 ...
rec( heightlowerbound := 7, rclowerbound := 4 )
|