请输入您要查询的字词:

 

单词 FindingTheOrderOfAGroup
释义

finding the order of a group


1 Group order and Membership

Problem 1 (Find Group Order). Given a finite groupMathworldPlanetmath G, and a subset S of G, determinethe order of the subgroupMathworldPlanetmathPlanetmath H=S.

Problem 2 (Membership Test). Given a finite group G, and a subset S of G and an element gG, determine if gH=S.

Of course both problems have a simple solution: list all the elements of H by repeated multiplicationPlanetmathPlanetmath. However, if G=S100, S is some arbitrary subset, it is possible for S to have order up to 100!, far in excess of any reasonable computation. So the problems are actually feasiblity questions.

At first glance the two problems seem unrelated, but indeed, often they are two versions of the same problem. For example, if we can determine the order of the group S for any subset S, then given any gG, compute the order of S and S,g. If they are equal then gS, otherwise gS.

If instead we are able to test membership, then we may sometimes build up to the group H by locating a subgroup of H, testing if the elements of S lie in this subgroup, if not, extend to a larger group building a transversal for the resulting cosets as we go. In the end we have a list of subgroups

H=Hk>Hk-1>>H0=1

and a set of transversals Ti for Hi/Hi-1 (as cosets not as quotient groupsMathworldPlanetmath as Hi-1 need not be normal). The size of each Ti is the index[Hi:Hi-1] and so we can compute the order of H as

|H|=[Hk:Hk-1][H1:H0].

Notice this required we build |T0|+|T1|++|Tk| many elements of H.To make this process efficient requires |Ti| and k be small enough. Part of this is handled in the next basic, yet powerful, result.

Proposition 1.

For every finite group G and every set of generatorsPlanetmathPlanetmathPlanetmath S of G, thereexists a subset of T of S of size no more than log2|G| whichalso generates G. Furthermore, every chain of subgroups has length nomore than log2|G|.

Proof.

Given S={s1,,sk} build the subgroup chain Gi=s1,,si. Notice then that

G=GkGk-1G0=1.

We create T as the subset of sirS such that GirGir-1, that is, we remove elements the generate the same subgroups in the chain. So now

G=Gij>>G0=1.

Hence

|G|=[Gij:Gij-1][Gi1:G0]

and 2[Gir:Gir-1] so jlog2|G|.∎

We now outline the known state of these problems in various computational domains.

2 Permutation Groups

Given G=Sn, then both finding the group order and the membership test problem have polynomial timesMathworldPlanetmath solutions, polynomial in n. The first algorithmsMathworldPlanetmath of this sort where developed by Charles C. Sims and the computational complexity established by Frust Hopcroft and Luks. These are now known collectively as the Schreier-Sims algorithms because their principle theoretical tool is Schreier’s lemma.

To solve use G(i)={gG:1g=1,,ig=i} which gives a chain of subgroups

G=G(0)>G(1)>>G(n-1)=1.

Applying a careful use of Schreier’s lemma to establish transversals of each sectionPlanetmathPlanetmath of the chain produce the order of G. Moreover, this also implicitly factors every gG uniquely into g1g2gn-1 where giG(i-1) but giG(i). If some gSn cannot be factored through the algorithm (a process usually called sifting) then gG. Thus memberhsip is also solved.

3 Polycyclic Presentations

A polycyclic presentationMathworldPlanetmath by its very design exhibits a chain of subgroups of known prime indices. The order of the group is therefore a produce of the primes. Membership testing can be handled in various ways including sifting the element of the generators of the presentation.

4 Matrix groups

Here the process of computing orders and testing membership collapses to basic problems in number theoryMathworldPlanetmath: discrete logarithmsMathworldPlanetmath, and large integer factorization. Unfortunately, these problems have unknown computational complexity and their complexity is the backbone of many cryptographic systems.

For example, given a subgroup H of GL(2,q) for some q=pi, i sufficiently large, it may be that H is a cyclic groupMathworldPlanetmath, for example a subgroup of the multiplication of the field GF(q)×. For instance

H[1011].

It is a well known hard problem to factor q-1 for q=pi a large power of a prime. Thus it is often the case that we cannot determine subgroups of H as there may be none of small order. Indeed H may be isomorphicPlanetmathPlanetmathPlanetmath to r for r a very large prime. For example, is 2127-1 a prime?To determine for a given gGL(2,2127) what |g|=|g| is can require a test of this sort in general.

For membership testing the same number theoretic problems arrise.To test if gH=h=GF(q)× would require we find out ifg=hi in GF(q). This is a problem known as the discrete logarithm.

5 General presentations of groups

Given an arbitrary presentation of a group, Boone demonstrates it is impossible even to know if the group is the trivial group. Thus the problem of knowning if the order is non-zero is impossible. Membership testing is therefore also impossible.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 19:06:47