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
