# Operations on the Set of Elements ## Order and Index Functions ### `Order(G): GrpFin -> RngIntElt` ### `# G: GrpFin -> RngIntElt` The order of the group $G$ as an integer. If the order is not currently known, it will be computed. Computing the order may fail for groups in the category `GrpFP`; cf. Chapter [Introduction to Fp-Groups](../../FinitelyPresentedGroups/IntroductionToFPGroups/index-introduction-to-fpgroups.md#chapgrpfpint). ### `FactoredOrder(G): GrpFin -> [ ]` The order of the finite group $G$ returned as a factored integer. The factorization is returned in the form of a sequence $Q$ which is defined as follows: If $\#G = p_1^{e_1}\ldots p_n^{e_n}, \quad e_i>0$, then $Q$ will be the integer sequence $[ \langle p_1, e_1\rangle, \ldots, \langle p_n, e_n\rangle ]$. If the orders of $G$ is not known, it will be computed. Computing the order may fail for groups in the category `GrpFP`; cf. Chapter [Introduction to Fp-Groups](../../FinitelyPresentedGroups/IntroductionToFPGroups/index-introduction-to-fpgroups.md#chapgrpfpint). ### `Index(G, H): GrpFin, GrpFin -> RngIntElt` The index of the subgroup $H$ in the group $G$. The index is returned as an integer. Computing the index may fail for groups in the category `GrpFP`; cf. Chapter [Introduction to Fp-Groups](../../FinitelyPresentedGroups/IntroductionToFPGroups/index-introduction-to-fpgroups.md#chapgrpfpint). ### `FactoredIndex(G, H): GrpFin, GrpFin -> [ ]` The index of the subgroup $H$ in the group $G$. The subgroup $H$ must have finite index in $G$. The index is returned as a factored integer. The format is the same as for `FactoredOrder`. Computing the index may fail for groups in the category `GrpFP`; cf. Chapter [Introduction to Fp-Groups](../../FinitelyPresentedGroups/IntroductionToFPGroups/index-introduction-to-fpgroups.md#chapgrpfpint). ### `Example: Order (ex-fd70fc)` Exploration of the order and index functions for a finitely presented group and its subgroup: ```magma > Q, h := Group< s, t, u | > t^2, u^17, s^2 = t^s = t, u^s = u^16, u^t = u >; > Order(Q); 68 > FactoredOrder(Q); [ <2, 2>, <17, 1> ] > S := sub< Q | t*s^2, u^4 >; > Index(Q, S); 4 > #S; 17 ``` ## Membership and Equality ### `g in G: GrpFinElt, GrpFin -> BoolElt` Given a group element $g$ and a group $G$, return `true` if $g$ is an element of $G$, `false` otherwise. ### `g notin G: GrpFinElt, GrpFin -> BoolElt` Given a group element $g$ and a group $G$, return `true` if $g$ is not an element of $G$, `false` otherwise. ### `S subset G: { GrpFinElt }, GrpFin -> BoolElt` Given a group $G$ and a set $S$ of group elements belonging to a group $H$, where $G$ and $H$ belong the same generic group, return `true` if $S$ is a subset of $G$, `false` otherwise. ### `S notsubset G: { GrpFinElt }, GrpFin -> BoolElt` Given a group $G$ and a set $S$ of group elements belonging to a group $H$, where $G$ and $H$ belong the same generic group, return `true` if $S$ is not a subset of $G$, `false` otherwise. ### `H subset G: GrpFin, GrpFin -> BoolElt` ### `IsSubgroup(H, G): GrpFin, GrpFin -> BoolElt` Given groups $G$ and $H$ belonging to the same generic group, return `true` if $H$ is a subgroup of $G$, `false` otherwise. ### `H notsubset G: GrpFin, GrpFin -> BoolElt` Given groups $G$ and $H$ belonging to the same generic group, return `true` if $H$ is not a subgroup of $G$, `false` otherwise. ### `H eq G: GrpFin, GrpFin -> BoolElt` Given groups $G$ and $H$ belonging to the same generic group, return `true` if $G$ and $H$ are the same group, `false` otherwise. ### `H ne G: GrpFin, GrpFin -> BoolElt` Given groups $G$ and $H$ belonging to the same generic group, return `true` if $G$ and $H$ are distinct groups, `false` otherwise. ## Set Operations ### `NumberingMap(G): GrpFin -> Map` Given a finite group $G$ in the category `GrpPerm`, `GrpMat`, `GrpPC` or `GrpAb`, return a bijective mapping from the group $G$ onto the set of integers $\{ 1 \ldots |G| \rbrace$. The actual mapping depends upon the particular representation of $G$. ### `Representative(G): GrpFin -> GrpFinElt` ### `Rep(G): GrpFin -> GrpFinElt` An element chosen from the group $G$. ### `Example: Set Operations (ex-f73fa4)` We use the function `NumberingMap` to construct the multiplication table for the dihedral group of order $12$. ```magma > G := DihedralGroup(6); > f := NumberingMap(G); > [ [ f(x*y) : y in G ] : x in G ]; [ [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ], [ 2, 3, 4, 5, 6, 1, 12, 7, 8, 9, 10, 11 ], [ 3, 4, 5, 6, 1, 2, 11, 12, 7, 8, 9, 10 ], [ 4, 5, 6, 1, 2, 3, 10, 11, 12, 7, 8, 9 ], [ 5, 6, 1, 2, 3, 4, 9, 10, 11, 12, 7, 8 ], [ 6, 1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 7 ], [ 7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6 ], [ 8, 9, 10, 11, 12, 7, 6, 1, 2, 3, 4, 5 ], [ 9, 10, 11, 12, 7, 8, 5, 6, 1, 2, 3, 4 ], [ 10, 11, 12, 7, 8, 9, 4, 5, 6, 1, 2, 3 ], [ 11, 12, 7, 8, 9, 10, 3, 4, 5, 6, 1, 2 ], [ 12, 7, 8, 9, 10, 11, 2, 3, 4, 5, 6, 1 ] ] ``` ## Random Elements ### `Random(G: parameters): GrpFin -> GrpFinElt` ```magma Short: BoolElt Default: false ``` A randomly chosen element for the group $G$. If a representation of the carrier set of $G$ has already been created, then the element chosen will be genuinely random. If such a representation has not yet been created, then the *random* element is chosen by multiplying out a *random* word in the generators. Since it is not usually practical to choose words long enough to properly sample the elements of $G$, the element returned will usually be biased. The boolean-valued parameter `Short` is used in this situation to indicate that a short word will suffice. Thus, if `Random` is invoked with `Short` assigned the value `true` then the element is constructed using a short word. ### `Example: Random Operations (ex-79c950)` We illustrate the use of the function `Random` using the wreath product of the symmetric group of degree $4$ and the cyclic group of order $6$. ```magma > G := WreathProduct(Sym(4), CyclicGroup(6)); > G; Permutation group G acting on a set of cardinality 24 (1, 5, 9, 13, 17, 21)(2, 6, 10, 14, 18, 22) (3, 7, 11, 15, 19, 23) (4, 8, 12, 16, 20, 24) (1, 2, 3, 4) (1, 2) > Order(G); 1146617856 > Random(G); (1, 17, 12, 4, 18, 10, 3, 20, 9, 2, 19, 11)(5, 22, 13, 6, 21, 15) (7, 24, 16)(8, 23, 14) // We display the cycle structures of 10 random elements of G > R := [ CycleStructure(Random(G)) : i in [1..10] ]; > R; [ [ <6, 1>, <3, 6> ], [ <9, 1>, <6, 2>, <3, 1> ], [ <9, 2>, <3, 2> ], [ <12, 1>, <9, 1>, <3, 1> ], [ <18, 1>, <6, 1> ], [ <18, 1>, <6, 1> ], [ <12, 1>, <6, 2> ], [ <6, 3>, <2, 3> ], [ <6, 1>, <4, 3>, <2, 3> ], [ <6, 3>, <3, 2> ] ] ``` ### `RandomProcess(G): GrpFin -> Process` ### `RandomProcessWithWords(G): GrpFin -> Process` ### `RandomProcessWithValues(G, Q): GrpFin, SeqEnum -> Process` ### `RandomProcessWithWordsAndValues(G, Q): GrpFin, SeqEnum -> Process` ```magma Slots : RngIntElt Default: 10 Scramble : RngIntElt Default: 50 WordGroup: GrpSLP Default: ``` Create a process to generate randomly chosen elements from the group $G$. The process uses a variant of the product-replacement method similar to the *Rattle* method of [[Leedham-Green and Murray, 2002](../../references.md#cite-randomelementsvariants)]. The generating set stored in the process has $N$ elements, where $N$ is the maximum of the specified value for `Slots` and `Ngens`$(G) + 1$. Initially they are the generators of $G$ repeated as necessary and the accumulator is the identity. Random elements are now produced by successive calls to `Random(P)`, where $P$ is the process created by this function. Each such call returns the current value of the accumulator, modifying the generating set as for product-replacement, and modifying the accumulator by multiplying by the new member of the generating set. Setting `Scramble := m` causes $m$ such operations to be performed before the process is returned. The functions with words and values create a process that returns extra group elements for each call. A process created with words returns, as second return value for each call to `Random(P)`, the `GrpSLPElt` describing the random element returned as a straight-line program in the group generators. The parameter `WordGroup` may be used to specify a particular group for the words to be elements of. A process created with values takes as input a sequence of group elements $Q$ giving the values assigned to each generator of $G$. The second value returned is the result of computing in parallel with these values as with the generators of $G$. In particular, if the elements of $Q$ are homomorphic images of the generators of $G$, then the second return value from `Random(P)` will be the image of the first under this homomorphism. A process created with words and values does all of the above, with the three return values of `Random(P)` being a random element of $G$, the straight-line program and the value. The use of this function on a finitely-presented group $G$ is not recommended. Since there is no reduction of words, the random elements generated may be extremely long. ### `Random(P): Process -> GrpFinElt` Given a random element process $P$ created by the function `RandomProcess(G)` for the finite group $G$, construct a random element of $G$ by forming a random product over the expanded generating set constructed when the process was created. For large permutation or matrix groups for which a BSGS is not known, this function should be used in preference to `Random(G)`. If the process was created with words or values then there will be second and third return values as described under `RandomProcess` above. ### `Random(P): Process -> GrpFinElt` Given a random element process $P$ created by the function `RandomProcess(G)` for the finite group $G$, return $G$. ### `InitialiseProspector(G:parameters): GrpMat` ### `InitialiseProspector(G:parameters): GrpPerm` Initialise a product-replacement prospector for the given group. This is an extension of the product-replacement algorithm that searches for an element $x\in G$ such that some predicate is true for this element. The prospector aims to find elements $x$ so that the corresponding straight-line program for $x$ is short. Statistical tests and various heuristics are used to achieve this. Generally, output from product-replacement with short straight-line programs is not very random. Prospector aims to run product-replacement until the output looks random, then start a search for the element wanted. At all times, if the output starts to look non-random, or word lengths grow too far without finding an element, the prospector may return to a previous state of product replacement and try again, searching in a different direction. The statistical tests are used to make concrete the notion of “looks random”. For permutation groups the test used is based on number of cycles of the element. For matrix groups the test statistic is the number of factors of the characteristic polynomial. ### `Prospector(G, f:parameters): Grp, UserProgram -> BoolElt, GrpElt, GrpSLPElt` Run an initialised prospector for group $G$ to find $x\in G$ such that $f(x)$ is true. The first return value gives the success or failure of the search. If this value is true, then the second and third return values are $x$ and a straight-line program giving $x$ in terms of the group generators. The parameter `MaxTries` may be set to limit the number of random selections made by the prospector when attempting to find $x$. ### `Example: Random Prospector (ex-f1996a)` We find a random pair of generators for the symmetric group of degree 300 and use a random process to find an element which is a 300-cycle as a straight-line program in the generators. The proportion of such elements is 1 in 300, so we expect the program to have length 600. ```magma > SetSeed(1); > S := Sym(300); > repeat G := sub; > until IsSymmetric(G); > P := RandomProcessWithWords(G); > repeat x,w := Random(P); > until CycleStructure(x) eq [<300,1>]; > #w; 936 ``` Note that the group $S$, known to be a symmetric group, has an efficient uniform random element generator available as above. The word length was somewhat longer than the expected value. Now we set up a prospector and use it to search for an element of the same cycle structure. The defining word for the new element should be shorter than the expected 600. ```magma > InitialiseProspector(G); true > test := func]>; > repeat a,x,w := Prospector(G, test); until a; > #w; 206 > Evaluate(w, [G.1,G.2]) eq x; true ``` ## Action on a Coset Space ### `CosetTable(G, H): GrpFin, GrpFin -> Map` The (right) coset table for $G$ over subgroup $H$ relative to its defining generators. ### `CosetTable(G, f): GrpFin, Hom(GrpFin) -> Hom(GrpFin)` The coset table for $G$ corresponding to the permutation representation $f$ of $G$, where $f$ is a homomorphism of $G$ onto a transitive permutation group. ### `Transversal(G, H): Grp, Grp -> { @ GrpElt @}, Map` ### `RightTransversal(G, H): Grp, Grp -> { @ GrpElt @}, Map` Given a group $G$ and a subgroup $H$ of $G$, this function returns **(a)** An indexed set of elements $T$ of $G$ forming a right transversal for $G$ over $H$; **(b)** The corresponding transversal mapping $\phi: G \rightarrow T$. If $T = [t_1, \ldots, t_r]$ and $g \in G$, $\phi$ is defined by $\phi(g) = t_i$, where $g\in Ht_i$. ### `CosetAction(G, H): Grp, Grp -> Hom(Grp), GrpPerm, Grp` Given a subgroup $H$ of the group $G$, construct the permutation representation of $G$ given by the action of $G$ on the set of (right) cosets of $H$ in $G$. The function returns: **(a)** The natural homomorphism $f: G \rightarrow L$; **(b)** The induced group $L$; **(c)** The kernel $K$ of the action (a subgroup of $G$). Note that $G$ may be any type of group. If $G$ is a finitely presented group, then $K$ may be returned undefined. ### `CosetImage(G, H): Grp, Grp -> GrpPerm` Given a subgroup $H$ of the group $G$, construct the image $L$ of $G$ given by the action of $G$ on the set of (right) cosets of $H$ in $G$. ### `CosetKernel(G, H): Grp, Grp -> Grp` Given a subgroup $H$ of the group $G$, construct the kernel of the action of $G$ on the set of (right) cosets of $H$ in $G$.