This is a reply to four people, so don't don't skip this unless you're skipping the whole topic. Please don't quote this whole message if you reply to it. Quoting is intended only to establish context. Would you soak a textbook in highlighter ink? I miss the days when mail programs would reject any message containing more quoted text than new text. A good rule of thumb is to only quote what you would manually retype if your mail program didn't support automatic quoting. Andy Latto <andy.latto@pobox.com> wrote:

Keith F. Lynch <kfl@keithlynch.net> wrote:

...

Then, for each identity element I, multiply it by all other numbers 2 through N. If I*J is not J, it's not the right identity element for J. Otherwise, keep multiplying J by itself until I either get I back (win) or I get 0 (fail). If I didn't fail, add the group to the list. At the end, eliminate duplicates and list them all.

aren't you only finding the cyclic subgroups with this algorithm?

Oops, yes. One reason it took me a few days to reply was because I've been trying to figure out how to fix this. (Another mistake in that paragraph is that if it fails, it wouldn't necessarily ever hit 0. But that's easy to fix. Most simply, if it finds more than N elements, fail, as there must be duplicates.) One way would be to add to my list every union of every subset of the cyclic multiplicative groups mod N with a common identity element, while eliminating any duplicates. The problem with this is that it would soon become very slow, like my first program, especially since I'd have to check every new group to make sure it was a group, and if not, add elements until it was. (The union of two groups isn't necessarily a group.) I ran my first program through N=36. That meant checking 2^36 subsets. It took more than a day to run. N=50 would have taken decades, and N=70 would have taken geological ages. The new program would be better, but the practical limit would be N=194. (For N=195, I=1, there are 40 cyclic groups, hence 2^40 subsets to check. That's more than a trillion.) I'm hoping to get to at least N=1000. My second program gets to N=1000 in about 2 minutes. But, as you point out, it only finds cyclic groups. For the record, the largest set of cyclic groups it's found (for N<1000) is 168 for N=819, I=1. That's probably because phi(819) is 2^4 * 3^3, i.e. it has lots of factors. Another approach would be to find just the generating set, i.e. the cyclic groups containing elements not in any other cyclic groups for the same N and same I. I've just written a program to find all of them. Again, it takes about a minute to get to N=1000. Again, N=819, I=1 holds the record, with a generating set of 130. The practical limit is probably N=272, as N=273, I=1 has a generating set of 40, so 2^40 subsets to check. (The values of N for which there's an I for which there's a generating set with more than one element, i.e. for which there's a group that's not cyclic, appears to be given by A033949. Also, it appears that if it's true for any I, it's true for I=1.) Okay, I think I've got it now. For every *pair* of cyclic groups containing an element not in any other cyclic group, i.e. single- generator groups, I'll generate a new group by taking their union and completing it. That will get me every group with 2 generators. Then I'll take the pairwise union of every single-generator group with every 2-generator group, and that will give me every 3-generator group, etc. I'd continue like that until a step found no more. Let me try it by hand, for N=30, I=16: Here are all the single-generator groups: A: 2 4 8 16 B: 14 16 C: 4 16 22 28 D: 16 26 Now let me take the pairwise unions of them, then complete them: A U B: 2 4 8 14 16 compl: 2 4 8 14 16 22 26 28 A U C: 2 4 8 16 22 28 compl: 2 4 8 14 16 22 26 28 -- duplicate A U D: 2 4 8 16 26 compl: 2 4 8 14 16 22 26 28 -- duplicate B U C: 4 14 16 22 28 compl: 2 4 8 14 16 22 26 28 -- duplicate B U D: 14 16 26 compl: 4 14 16 26 C U D: 4 16 22 26 28 compl: 2 4 8 14 16 22 26 28 -- duplicate That didn't quite work, as it missed two groups: {16} and {4,16}. Maybe if I also took the pairwise intersections? Sigh.

{1, 7, 13, 19} is not a group; 7 * 13 = 11.

As Tom Rokicki pointed out, it is. (10-3)(10+3) = 100-9 = 91 = 1 mod 30. That came from my first program, which I designed for extreme reliability at the expense of speed. I would be astonished if it made any mistakes. I use its results to check the results from my faster programs.

This is not a big deal if you're generating the groups by hand, but if you're doing it programatically, it means there's something wrong with your program.

I was generating them by a program. I'm not going to check 2^30 subsets by hand! That's more than a billion. Thane Plambeck <tplambeck@gmail.com> wrote:

Ie, there are 8 idempotents. So there will be 8 maximal subgroups. Here they are.

In[1173]:= Map[allMutuals, idempotents]

Out[1173]= {{0}, {1, 7, 11, 13, 17, 19, 23, 29}, {6, 12, 18, 24}, {10, 20}, {15}, {2, 4, 8, 14, 16, 22, 26, 28}, {3, 9, 21, 27}, {5, 25}}

Interesting.

Listing all the subgroups is more work, but they're easily found via this divide and conquer technique.

How would you divide and conquer? Testing each of the 2^(M-1) identity-element-containing subsets of the length-M maximal subgroups would be practical for N=30, where M is at most 8, but completely impractical for much larger N. For instance for N=997 you'd have 2^995 subsets. That would take incomparably more eons than there are nanoseconds in a trillion trillion eons. You could pair the identity element with each other element in the maximal subgroup to make a new group, but that would only get you back to my list of all cyclic groups, and you'd have to build from there. Dan Asimov <dasimov@earthlink.net> wrote:

I like this a lot,

I'm glad to hear it.

and am going to rewrite the maximal subgroups in my preferred form ... for symmetry's sake:

Don't be so negative. :-)

P.S. Now I'd like to know the same thing for the Gaussian integers Z[i] and the Eisenstein integers Z[w] where w = exp(2pi*i/3). These apparently have some complicated factor rings. See e.g. http://home.wlu.edu/~dresdeng/papers/factorrings.pdf.

Maybe I'll work on that after I finish this problem. Thane Plambeck <tplambeck@gmail.com> wrote:

possible theorem (?): the union of elements in the maximal subgroups exhaust all moduli (as they do for thirty) iff N (ie 30, here) is squarefree

I made the same conjecture here on the 20th: Mod N, the number of numbers that *don't* appear in any multiplicative group appears to be given by A055654. It appears to be always 0 for square-free N, and never 0 if N is not square free. Those groupless numbers are always divisors of N. Tom Karzes <karzes@sonic.net> wrote:

An additional property that holds when N is even but not a multiple of 4: Each maximal subgroup consists solely of either even numbers or odd numbers, never both.

You can take it a lot farther than that. That property holds for every group (not just maximal ones) for every even N (not just ones not divisible by 4). [Update: I see that in a later message you noticed the latter.]