Aha. I was intrigued (as I think John was) as to why you wanted to generate "a" non-Abelian group of given order n.
But thank you for the impetus to dust off my brain. ;-) On Sun, Dec 18, 2011 at 3:18 AM, Roger Hui <rogerhui.can...@gmail.com> wrote: > Thanks, I think :-). > >> Do you want me to find my dissertation and dust it off? > > That is not necessary. The procedure where I thought I could use a > non-abelian group turns out to not work. See: > http://www.jsoftware.com/jwiki/Essays/88_Hats . > > > > On Sat, Dec 17, 2011 at 6:57 PM, Ian Clark <earthspo...@gmail.com> wrote: > >> As John says, not every n permits the existence of a non-Abelian group >> of order n. If n is a prime, then there is precisely one abstract >> group of order n and it is cyclic, hence Abelian. >> >> Also as John says, the simplest example of a (barely) non-Abelian >> group is the dihedral group: the ways of fitting a cut-out regular >> polygon back in its hole, including flipping it over. Hence "dihedral" >> (=2-sided). >> >> I'd add that if n is odd, it enormously simplifies the possibilities. >> This is the notorious Feit-Thompson theorem, >> http://en.wikipedia.org/wiki/Feit%E2%80%93Thompson_theorem >> which in 1963 broke all records for the longest mathematical proof >> ever published. It states that all odd-order groups are solvable. >> "Solving" a group means breaking it down into its "composition >> series": >> http://en.wikipedia.org/wiki/Composition_series >> the components being called "simple" groups. The reverse process is >> called "group extension": >> http://en.wikipedia.org/wiki/Group_extension >> which offers the basis of a group-constructing algorithm. >> >> Simple groups include the cyclic groups of prime order, plus several >> series of groups whose structure is very far from simple. It's been a >> leading research problem for the past century to classify the finite >> simple groups, and in 2004 it was actually completed. >> http://en.wikipedia.org/wiki/List_of_finite_simple_groups >> In the 1960s it was one of the biggest international research programs >> in pure mathematics I knew of, drawing in some of the leading >> mathematical minds -- plus a few not-so-leading ones, like yours-truly >> :-) >> >> A finite group is called "solvable" only if its composition series >> contains none of these tough-nut non-cyclic, non-Abelian groups, but >> only prime-cyclics. >> >> I recommend this article, especially >> http://en.wikipedia.org/wiki/Group_extension#Extension_problem >> because it explains the problem deftly without plunging into the >> asphyxiating terminology of finite group theory. >> >> The title of my PhD dissertation was "the construction of finite >> factorisable groups" (1972) and for it I actually got free exclusive >> use of a large commercial mainframe (Burroughs B6500) to do a search >> for finite simple groups of a given order... or at least, a search for >> components called "elementary transcosets" which I needed to build up >> any finite group, even non-solvable ones, by a kind of generalized >> group extension called "transcoset theory". >> >> As with number theory, the difficulties only appear for astronomical >> values of n, the order of the target group G to be generated, far in >> excess of what even today's computers can handle. In 1972 Marshall >> Hall, jnr published a survey of all the simple groups up to >> n=1,000,000, and the number you'd have to consider in a short(ish) >> algorithm is manageable. >> >> http://en.wikipedia.org/wiki/List_of_finite_simple_groups#Non-cyclic_simple_groups_of_small_order >> >> If I was setting out today using J to find all possible G of given >> order n, I'd go right back to basics and work with the Cayley table of >> G (=multiplication table). Yes, really. Using heuristics of course to >> cut out the unwanted redundancy. Basically I'd choose an entry in >> Cayley(G) to be an integer, 0 to (n-1). But if A is a subgroup of G >> then the entries might become (<'A';p;q) where p and q are >> permutations of the rows and columns of Cayley(A) --this in effect >> builds Cayley(G) from the so-called right- and left-coset expansions >> of A in G. If you build G up by extending it by one prime-cyclic: Cp >> at a time, then Cayley(G) need only have (p^2) boxed entries. >> >> This is just my preferred approach. If you ask another group theorist, >> they'll more likely suggest representing the elements of G by the >> elements of Sym(n) (which contains as subgroups all possible groups G) >> -- ie as permutations, or as binary matrices (=permutation matrices) >> (as you say you've been trying) and working with so-called "group >> presentations". >> >> There's a conjecture that any (non-cyclic) simple group can be >> generated by [the right choice of] precisely two elements. I think it >> can be relied on for all practical values of n. If elements g and h >> generate G, then G can be represented as a set of equations in {g,h} >> -- this is called a "(group) presentation" of G. Deciding whether two >> given presentations are isomorphic, or even whether any given >> presentation is finite, are Turing-uncomputable problems (proven by >> Gregory Chaitin, if memory serves), so I've never thought of >> presentations as offering a viable computing technique. You may >> disagree, and discover they suit you well. Though once you've got your >> G, it's a neat way to define it. If I recall, all the new simple >> groups that have been discovered in the last 40 years have been >> published as group presentations. If you want a nice simple FAX to >> play around with theorem-proving techniques, then a (semi-)group >> presentation makes a splendid subject. I'd guess you'd need >> theorem-proving to generate the Cayley table of G from a presentation >> of it. >> >> Do you want me to find my dissertation and dust it off? >> >> IanClark >> >> On Fri, Dec 16, 2011 at 2:28 PM, Roger Hui <rogerhui.can...@gmail.com> >> wrote: >> > Does anyone know a way to generate a non-abelian group with order m? >> > >> > I can generate non-abelian groups, e.g. multiplication of non-singular >> > boolean matrices, or the group generated by a bunch of permutations, but >> I >> > need a group of size m when I am given the m. >> > ---------------------------------------------------------------------- >> > For information about J forums see http://www.jsoftware.com/forums.htm >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm >> > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
