OpenMath

OpenMath is an extensible standard for representing the semantics of mathematical objects.

https://openmath.org

OpenMath Content Dictionary: permgp1

Canonical URL:
http://www.openmath.org/cd/permgp1.ocd
CD Base:
http://www.openmath.org/cd
CD File:
permgp1.ocd
CD as XML Encoded OpenMath:
permgp1.omcd
Defines:
base, generators, group, is_in, is_primitive, is_subgroup, is_transitive, orbit, orbits, order, schreier_tree, stabilizer, stabilizer_chain, support
Date:
2004-06-01
Version:
2 (Revision 1)
Review Date:
Status:
experimental

A CD of functions for permutation groups 

     First version written by A. Solomon 1998-11-19.
     Modified by David Carlisle 1999-04-28.
     Rebuilt by Arjeh M. Cohen 2002-12-16.

group

Description:

This symbol represents an n-ary function. The first argument is a group operation (usually, left_compose or right_compose), the other n-1 arguments represent permutations. When evaluated on such arguments, the function represents the permutation group generated by the last n-1 arguments.

Example:
The permutation group generated by (1,5,4)(2,6) and (1,4,5)(3,6)
group ⁡ ( right_compose , permutation ⁡ ( cycle ⁡ ( 1 , 5 , 4 ) , cycle ⁡ ( 2 , 6 ) ) , permutation ⁡ ( cycle ⁡ ( 3 , 6 ) , cycle ⁡ ( 1 , 4 , 5 ) ) )
Signatures:
sts

[Next: support] [Last: stabilizer_chain] [Top]

support

Description:

This represents a unary function whose argument should be a permutation group. When evaluated at a permutation group G, it is the set of points which are moved a member of G.

Example:
The following expression evaluates to the set {1,2,3,4,5,6}.
support ⁡ ( group ⁡ ( right_compose , permutation ⁡ ( cycle ⁡ ( 1 , 5 , 4 ) , cycle ⁡ ( 2 , 6 ) ) , permutation ⁡ ( cycle ⁡ ( 3 , 6 ) , cycle ⁡ ( 1 , 4 , 5 ) ) ) )
Signatures:
sts

[Next: generators] [Previous: group] [Top]

generators

Description:

This is a function with one argument, which should be a permutation group. When evaluated with argument G it returns the list of permutations which occur in the definition of G.

Example:
The following expression evaluates to the list of permutations [(1,5,4)(2,6),(3,6)(1,4,5)].
generators ⁡ ( group ⁡ ( right_compose , permutation ⁡ ( cycle ⁡ ( 1 , 5 , 4 ) , cycle ⁡ ( 2 , 6 ) ) , permutation ⁡ ( cycle ⁡ ( 3 , 6 ) , cycle ⁡ ( 1 , 4 , 5 ) ) ) , 2 )
Signatures:
sts

[Next: orbit] [Previous: support] [Top]

orbit

Description:

The binary function whose first argument should be a permutation group G. If the second argument is an element of the support of G, the value is the orbit of the second argument under the action of G. Otherwise, it is the singleton consisting of the second argument.

Example:
The following expression evaluates to the set {2,3,6}.
orbit ⁡ ( group ⁡ ( right_compose , permutation ⁡ ( cycle ⁡ ( 1 , 5 , 4 ) , cycle ⁡ ( 2 , 6 ) ) , permutation ⁡ ( cycle ⁡ ( 3 , 6 ) , cycle ⁡ ( 1 , 4 , 5 ) ) ) , 2 )
Signatures:
sts

[Next: stabilizer] [Previous: generators] [Top]

stabilizer

Description:

This is an n-ary function with n at least 2. The first argument is a permutation group G, the other arguments are elements x_2,x_3,...,x_n upon which G acts. The value is the subgroup of G consisting of all permutations which stabilize each of x_2,x_3,...,x_n.

Example:
The following expression stands for the stabilizer of 1 and 2 in the permutation group generated by the permutations (1,5,4)(2,6) and (3,6)(1,4,5).
stabilizer ⁡ ( group ⁡ ( right_compose , permutation ⁡ ( cycle ⁡ ( 1 , 5 , 4 ) , cycle ⁡ ( 2 , 6 ) ) , permutation ⁡ ( cycle ⁡ ( 3 , 6 ) , cycle ⁡ ( 1 , 4 , 5 ) ) ) , 1 , 2 )
Signatures:
sts

[Next: is_transitive] [Previous: orbit] [Top]

is_transitive

Description:

This is a Boolean function with one argument, which should be a permutation group. When evaluated at a permutation group G, it returns the value true if and only if the permutation group argument acts transitively on the support of G.

Example:
The following boolean value is false.
is_transitive ⁡ ( group ⁡ ( right_compose , permutation ⁡ ( cycle ⁡ ( 1 , 5 , 4 ) , cycle ⁡ ( 2 , 6 ) ) , permutation ⁡ ( cycle ⁡ ( 3 , 6 ) , cycle ⁡ ( 1 , 4 , 5 ) ) ) )
Signatures:
sts

[Next: orbits] [Previous: stabilizer] [Top]

orbits

Description:

This is a function with one argument, which should be a permutation group. When evaluated at a permutation group G, it returns the set of all orbits of G on elements from the support of G.

Example:
The following expression evaluates to the list of sets [{2,3,6},{1,4,5}].
orbits ⁡ ( group ⁡ ( right_compose , permutation ⁡ ( cycle ⁡ ( 1 , 5 , 4 ) , cycle ⁡ ( 2 , 6 ) ) , permutation ⁡ ( cycle ⁡ ( 3 , 6 ) , cycle ⁡ ( 1 , 4 , 5 ) ) ) )
Signatures:
sts

[Next: is_primitive] [Previous: is_transitive] [Top]

is_primitive

Description:

The unary function with one argument, which should be a permutation group. Its value is true if and only if G acts primitively on the support of G. This means that there is no proper subset B of the support of G with more than one element such that the image of B under an element of G meets B in a proper nonempty subset of B.

Example:
The following expression evaluates to the boolean true.
is_primitive ⁡ ( group ⁡ ( right_compose , permutation ⁡ ( cycle ⁡ ( 1 , 5 , 4 , 3 ) , cycle ⁡ ( 2 , 6 ) ) , permutation ⁡ ( cycle ⁡ ( 3 , 6 ) , cycle ⁡ ( 1 , 4 , 5 , 2 ) ) ) )
Signatures:
sts

[Next: schreier_tree] [Previous: orbits] [Top]

schreier_tree

Description:

This is a function with two arguments. The first argument should be a permutation group G, the second argument a point x permuted by G. When evaluated at G and x, it returns a list of three lists X,V,B. The first list, X, enumerates the points of the G-orbit of x. The second list and the third list both have the same length as X, say n. The second list represents a map V from [1,...,n] to {-m,...,-1,0,1,...,m}, where m is the number of generators of G, and the third list represents a map B from [1,...,n] to X. These maps satisfy the following properties: X(1) = B(1) = x. Moreover, V(i) = 0 if and only if i = 1. For each index i distinct from 1, the value B(i) is equal to X(j) for some index j smaller than i. If V(i) is positive, then X(i) is the image of B(i) under the V(i)-th generator of G. If V(i) is negative, then B(i) is the image of X(i) under the (-V(i))-th generator of G.

Example:
The following expression represents a Schreier tree.
schreier_tree ⁡ ( group ⁡ ( right_compose , permutation ⁡ ( cycle ⁡ ( 1 , 5 , 4 , 3 ) , cycle ⁡ ( 2 , 6 ) ) , permutation ⁡ ( cycle ⁡ ( 3 , 6 ) , cycle ⁡ ( 1 , 4 , 5 , 2 ) ) ) , 4 )
Signatures:
sts

[Next: base] [Previous: is_primitive] [Top]

base

Description:

This is a function with one argument, which should be a permutation group. When evaluated with argument G it returns a list of points permuted by G such that the stabilizer of all elements of the list in G is trivial. Besides, the list is minimal with respect to the latter property (in the sense that the stabilizer in G of the elements of no proper subset is trivial).

Example:
The following expression represents a base.
base ⁡ ( group ⁡ ( right_compose , permutation ⁡ ( cycle ⁡ ( 1 , 5 , 4 ) , cycle ⁡ ( 2 , 6 ) ) , permutation ⁡ ( cycle ⁡ ( 3 , 6 ) , cycle ⁡ ( 1 , 4 , 5 ) ) ) )
Signatures:
sts

[Next: order] [Previous: schreier_tree] [Top]

order

Description:

This is a function with one argument, which should be a permutation group. When evaluated with argument G it returns the size of the group G.

Example:
The following expression evaluates to 18.
order ⁡ ( group ⁡ ( right_compose , permutation ⁡ ( cycle ⁡ ( 1 , 5 , 4 ) , cycle ⁡ ( 2 , 6 ) ) , permutation ⁡ ( cycle ⁡ ( 3 , 6 ) , cycle ⁡ ( 1 , 4 , 5 ) ) ) )
Signatures:
sts

[Next: is_in] [Previous: base] [Top]

is_in

Description:

This is a Boolean function with two arguments. The first argument should be a permutation, the second a permutation group. When evaluated with first argument x and second argument G, it returns true if and only if x belongs to G.

Example:
The following expression evaluates to the boolean false.
is_in ⁡ ( permutation ⁡ ( cycle ⁡ ( 1 , 2 ) ) , group ⁡ ( right_compose , permutation ⁡ ( cycle ⁡ ( 1 , 5 , 4 ) , cycle ⁡ ( 2 , 6 ) ) , permutation ⁡ ( cycle ⁡ ( 3 , 6 ) , cycle ⁡ ( 1 , 4 , 5 ) ) ) )
Signatures:
sts

[Next: is_subgroup] [Previous: order] [Top]

is_subgroup

Description:

This is a Boolean function with two arguments, both of which are permutation groups. When evaluated with first argument H and second argument G it returns true if and only if H is a subgroup of G.

Example:
The following expression evaluates to the boolean false.
is_subgroup ⁡ ( group ⁡ ( right_compose , permutation ⁡ ( cycle ⁡ ( 1 , 5 , 4 ) , cycle ⁡ ( 2 , 6 ) ) , permutation ⁡ ( cycle ⁡ ( 3 , 6 ) , cycle ⁡ ( 1 , 4 , 5 ) ) ) , group ⁡ ( right_compose , permutation ⁡ ( cycle ⁡ ( 1 , 5 , 4 , 3 ) , cycle ⁡ ( 2 , 6 ) ) , permutation ⁡ ( cycle ⁡ ( 3 , 6 , 2 ) , cycle ⁡ ( 1 , 4 , 5 ) ) ) )
Signatures:
sts

[Next: stabilizer_chain] [Previous: is_in] [Top]

stabilizer_chain

Description:

This function takes one argument which should be a permutation group. When applied to the permutation group G, its value is a list consisting of two lists B, H of equal length. The first list B is a base for G, whereas the i-th entry H[i] of the second list is the stabilizer in G of the elements B[1], ..., B[i].

Example:
The following expression represents a stabilizer chain.
stabilizer_chain ⁡ ( group ⁡ ( right_compose , permutation ⁡ ( cycle ⁡ ( 1 , 5 , 4 ) , cycle ⁡ ( 2 , 6 ) ) , permutation ⁡ ( cycle ⁡ ( 3 , 6 ) , cycle ⁡ ( 1 , 4 , 5 ) ) ) )
Signatures:
sts

[First: group] [Previous: is_subgroup] [Top]