Re: [math-fun] Simple finite group problem
This is a reply to three people, so don't don't skip this unless you're skipping the whole topic. Dan Asimov <asimov@msri.org> wrote:
Argh. Maybe this has fewer mistakes.
Tricky, that 5.
---------------------------- {0}, {1}, {5}, {6} {-1, 1}, {-4, 4} {-3, -1, 1, 3}, {-4, -2, 2, 4} {-4, -3, -2, -1, 1, 2, 3, 4} ---------------------------- The last one is not a group. The way I found them was, for every subset of {0,1,2,3,4,5,6,7,8,9}, to create a multiplication table and check every row to make sure each number in the maybe-group appeared once and only once. For a small number of small groups, it's practical to do this by hand. I also made sure that in at least one row the column headers weren't permuted, i.e. that there's an identity element. I didn't need to make sure that it's associative, since of course multiplication is associative. I didn't need to make sure each element had an inverse, since the Jth row contains the identity element for all J; the column that's in says what its inverse is. I plan to rewrite it to be much faster. For each number I, 2 through N-1, check to see if it equals its square mod N. If so, add it to the identity element table. (0 and 1 are put in the table without checking.) 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. Of course, as with the first program, I will precompute the whole mod N table. There's no point in doing the same calculations multiple times. Tom Karzes <karzes@sonic.net> wrote:
Are you counting groups as distinct that are identical to each other, but happen to use different numbers for the elements? For example, {1, 3, 7, 9} is really the same group as {6, 2, 8, 4} (the elements correspond in the order listed). Does it makes sense to count it twice?
I'm not sure what you're saying. Are you pointing out that those groups are isomorphic? Yes. In that sense there are only two groups of order 4, and only one group of order N whenever N is prime. In that same sense, the group of addition of reals is the same as the group of multiplication of positive reals; we've just relabeled all the elements. But nobody would suggest that means that multiplication isn't worthy of study because it's just addition with funny names and we already understand addition.
If so, then we're really identifying subsets of integers that generate these groups, rather than the groups themselves.
Well, yes. There's very little to be said about small groups themselves. They're useful tools for studying other things. Joerg Arndt <arndt@jjj.de> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
Mod N, the identity elements are those numbers I such that I^2 = I mod N. For N=10, those are 0, 1, 5, and 6. The numbers of identity elements mod N appear to be given by A034444. Mod 30, there are 8 of them, and 28 groups.
A group G has one neutral ("identity") element e by definition: a * e = a = e * a for all a \in G
*A* group, yes. But as I said, mod 30 there are 28 groups: Identity element 0: {0} Identity element 1: {1} {1,11} {1,19} {1,7,13,19} {1,17,19,23} {1,29} {1,11,19,29} {1,7,11,13,17,19,23,29} Identity element 6: {6} {6,24} {6,12,18,24} Identity element 10: {10} {10,20} Identity element 15: {15} Identity element 16: {16} {4,16} {2,4,8,16} {14,16} {16,26} {4,14,16,26} {4,16,22,28} {2,4,8,14,16,22,26,28} Identity element 21: {21} {9,21} {3,9,21,27} Identity element 25: {25} {5,25}
Usually the multiplicative group mod n consists of all u, 1<=u<n, such that gcd(u,n)=1 (the "units"). ...
You seem to have something different in mind. I'd like to warn about using existing terminology with non-standard meanings.
What would you call what I'm doing?
I think the order of any of these groups always divides phi(N).
The order of any subgroup of G is a divisor of the order of G. As the order of the multiplicative group mod N is phi(N), so your statement follows.
But that applies only to the groups with an identity element of 1. The groups with different identity elements are obviously not subgroups of a group with an identity element of 1. So it's not obvious to me that they all must have orders that divide phi(N), but they do all appear to.
First step: define everything.
I was hoping this already has a name. "Multiplicative groups mod N" is the obvious name, but if that's already taken for a subset of what I'm talking about, I'll have to use something else. Something short, so it will fit in a title of an OEIS entry.
It seems that the function f(n) = number of subsemigroups of Z/(n) which are groups is a multiplicative function <https://en.wikipedia.org/wiki/Multiplicative_function>, that is, f(1) = 1 and if n = ab where gcd(a,b) = 1 then f(n) = f(a)f(b). Thus it suffices to find f(p^n) for all primes p and positive integers n. In particular, if n is a product of k distinct primes then f(n) = 3^k since Z/(p) has 3 subsemigroups which are groups, {0}, {1} and {1,2,...p-1}. Perhaps there is a nice formula for f(p^n), n>1. Maybe someone has already mentioned this and I missed it. Too much stuff to read through. On Thu, Apr 21, 2016 at 10:04 PM, Keith F. Lynch <kfl@keithlynch.net> wrote:
This is a reply to three people, so don't don't skip this unless you're skipping the whole topic.
Dan Asimov <asimov@msri.org> wrote:
Argh. Maybe this has fewer mistakes.
Tricky, that 5.
---------------------------- {0}, {1}, {5}, {6}
{-1, 1}, {-4, 4}
{-3, -1, 1, 3}, {-4, -2, 2, 4}
{-4, -3, -2, -1, 1, 2, 3, 4} ----------------------------
The last one is not a group.
The way I found them was, for every subset of {0,1,2,3,4,5,6,7,8,9}, to create a multiplication table and check every row to make sure each number in the maybe-group appeared once and only once. For a small number of small groups, it's practical to do this by hand.
I also made sure that in at least one row the column headers weren't permuted, i.e. that there's an identity element.
I didn't need to make sure that it's associative, since of course multiplication is associative. I didn't need to make sure each element had an inverse, since the Jth row contains the identity element for all J; the column that's in says what its inverse is.
I plan to rewrite it to be much faster. For each number I, 2 through N-1, check to see if it equals its square mod N. If so, add it to the identity element table. (0 and 1 are put in the table without checking.)
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.
Of course, as with the first program, I will precompute the whole mod N table. There's no point in doing the same calculations multiple times.
Tom Karzes <karzes@sonic.net> wrote:
Are you counting groups as distinct that are identical to each other, but happen to use different numbers for the elements? For example, {1, 3, 7, 9} is really the same group as {6, 2, 8, 4} (the elements correspond in the order listed). Does it makes sense to count it twice?
I'm not sure what you're saying. Are you pointing out that those groups are isomorphic? Yes. In that sense there are only two groups of order 4, and only one group of order N whenever N is prime.
In that same sense, the group of addition of reals is the same as the group of multiplication of positive reals; we've just relabeled all the elements. But nobody would suggest that means that multiplication isn't worthy of study because it's just addition with funny names and we already understand addition.
If so, then we're really identifying subsets of integers that generate these groups, rather than the groups themselves.
Well, yes. There's very little to be said about small groups themselves. They're useful tools for studying other things.
Joerg Arndt <arndt@jjj.de> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
Mod N, the identity elements are those numbers I such that I^2 = I mod N. For N=10, those are 0, 1, 5, and 6. The numbers of identity elements mod N appear to be given by A034444. Mod 30, there are 8 of them, and 28 groups.
A group G has one neutral ("identity") element e by definition: a * e = a = e * a for all a \in G
*A* group, yes. But as I said, mod 30 there are 28 groups:
Identity element 0: {0} Identity element 1: {1} {1,11} {1,19} {1,7,13,19} {1,17,19,23} {1,29} {1,11,19,29} {1,7,11,13,17,19,23,29} Identity element 6: {6} {6,24} {6,12,18,24} Identity element 10: {10} {10,20} Identity element 15: {15} Identity element 16: {16} {4,16} {2,4,8,16} {14,16} {16,26} {4,14,16,26} {4,16,22,28} {2,4,8,14,16,22,26,28} Identity element 21: {21} {9,21} {3,9,21,27} Identity element 25: {25} {5,25}
Usually the multiplicative group mod n consists of all u, 1<=u<n, such that gcd(u,n)=1 (the "units"). ...
You seem to have something different in mind. I'd like to warn about using existing terminology with non-standard meanings.
What would you call what I'm doing?
I think the order of any of these groups always divides phi(N).
The order of any subgroup of G is a divisor of the order of G. As the order of the multiplicative group mod N is phi(N), so your statement follows.
But that applies only to the groups with an identity element of 1. The groups with different identity elements are obviously not subgroups of a group with an identity element of 1. So it's not obvious to me that they all must have orders that divide phi(N), but they do all appear to.
First step: define everything.
I was hoping this already has a name. "Multiplicative groups mod N" is the obvious name, but if that's already taken for a subset of what I'm talking about, I'll have to use something else. Something short, so it will fit in a title of an OEIS entry.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Oops. For the prime 2, f(2) = 2, and if p is an odd prime then I think f(p) = 1 + tau(p-1). Since Z/(p) has subgroups {0} and the tau(p-1) subgroups of the cyclic group of order p-1 generated by any primitive root of p. ---where tau(n) is the number of divisors of n. In particular f(10) = f(2)f(5) = 2*(1+tau(4)) = 2*4 = 8. Since there is a nice formula for tau(n) this beats brute force when n is a product of distinct primes. Perhaps some number theorists can find a nice formula for f(p^n) where p is prime and n is a positive integer. On Thu, Apr 21, 2016 at 11:04 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
It seems that the function f(n) = number of subsemigroups of Z/(n) which are groups is a multiplicative function <https://en.wikipedia.org/wiki/Multiplicative_function>, that is, f(1) = 1 and if n = ab where gcd(a,b) = 1 then f(n) = f(a)f(b). Thus it suffices to find f(p^n) for all primes p and positive integers n. In particular, if n is a product of k distinct primes then f(n) = 3^k since Z/(p) has 3 subsemigroups which are groups, {0}, {1} and {1,2,...p-1}. Perhaps there is a nice formula for f(p^n), n>1. Maybe someone has already mentioned this and I missed it. Too much stuff to read through.
On Thu, Apr 21, 2016 at 10:04 PM, Keith F. Lynch <kfl@keithlynch.net> wrote:
This is a reply to three people, so don't don't skip this unless you're skipping the whole topic.
Dan Asimov <asimov@msri.org> wrote:
Argh. Maybe this has fewer mistakes.
Tricky, that 5.
---------------------------- {0}, {1}, {5}, {6}
{-1, 1}, {-4, 4}
{-3, -1, 1, 3}, {-4, -2, 2, 4}
{-4, -3, -2, -1, 1, 2, 3, 4} ----------------------------
The last one is not a group.
The way I found them was, for every subset of {0,1,2,3,4,5,6,7,8,9}, to create a multiplication table and check every row to make sure each number in the maybe-group appeared once and only once. For a small number of small groups, it's practical to do this by hand.
I also made sure that in at least one row the column headers weren't permuted, i.e. that there's an identity element.
I didn't need to make sure that it's associative, since of course multiplication is associative. I didn't need to make sure each element had an inverse, since the Jth row contains the identity element for all J; the column that's in says what its inverse is.
I plan to rewrite it to be much faster. For each number I, 2 through N-1, check to see if it equals its square mod N. If so, add it to the identity element table. (0 and 1 are put in the table without checking.)
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.
Of course, as with the first program, I will precompute the whole mod N table. There's no point in doing the same calculations multiple times.
Tom Karzes <karzes@sonic.net> wrote:
Are you counting groups as distinct that are identical to each other, but happen to use different numbers for the elements? For example, {1, 3, 7, 9} is really the same group as {6, 2, 8, 4} (the elements correspond in the order listed). Does it makes sense to count it twice?
I'm not sure what you're saying. Are you pointing out that those groups are isomorphic? Yes. In that sense there are only two groups of order 4, and only one group of order N whenever N is prime.
In that same sense, the group of addition of reals is the same as the group of multiplication of positive reals; we've just relabeled all the elements. But nobody would suggest that means that multiplication isn't worthy of study because it's just addition with funny names and we already understand addition.
If so, then we're really identifying subsets of integers that generate these groups, rather than the groups themselves.
Well, yes. There's very little to be said about small groups themselves. They're useful tools for studying other things.
Joerg Arndt <arndt@jjj.de> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
Mod N, the identity elements are those numbers I such that I^2 = I mod N. For N=10, those are 0, 1, 5, and 6. The numbers of identity elements mod N appear to be given by A034444. Mod 30, there are 8 of them, and 28 groups.
A group G has one neutral ("identity") element e by definition: a * e = a = e * a for all a \in G
*A* group, yes. But as I said, mod 30 there are 28 groups:
Identity element 0: {0} Identity element 1: {1} {1,11} {1,19} {1,7,13,19} {1,17,19,23} {1,29} {1,11,19,29} {1,7,11,13,17,19,23,29} Identity element 6: {6} {6,24} {6,12,18,24} Identity element 10: {10} {10,20} Identity element 15: {15} Identity element 16: {16} {4,16} {2,4,8,16} {14,16} {16,26} {4,14,16,26} {4,16,22,28} {2,4,8,14,16,22,26,28} Identity element 21: {21} {9,21} {3,9,21,27} Identity element 25: {25} {5,25}
Usually the multiplicative group mod n consists of all u, 1<=u<n, such that gcd(u,n)=1 (the "units"). ...
You seem to have something different in mind. I'd like to warn about using existing terminology with non-standard meanings.
What would you call what I'm doing?
I think the order of any of these groups always divides phi(N).
The order of any subgroup of G is a divisor of the order of G. As the order of the multiplicative group mod N is phi(N), so your statement follows.
But that applies only to the groups with an identity element of 1. The groups with different identity elements are obviously not subgroups of a group with an identity element of 1. So it's not obvious to me that they all must have orders that divide phi(N), but they do all appear to.
First step: define everything.
I was hoping this already has a name. "Multiplicative groups mod N" is the obvious name, but if that's already taken for a subset of what I'm talking about, I'll have to use something else. Something short, so it will fit in a title of an OEIS entry.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Thu, Apr 21, 2016 at 11:04 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
It seems that the function f(n) = number of subsemigroups of Z/(n) which are groups is a multiplicative function
I don't think this is true. Given a subsemigroup of Za and a subsemigroup of Zb, we can generate a subsemigroup of Z(a*b) via the chinese remainder theorem. But I think that in general, not all subsemgroups of Z(a*b) arise in this way. For example, restricting ourselves for the moment just to those subsemigroups with identity element 1, suppose that for A we have a cyclic group of order 4 and its 2 subgroups, and for B we also have a cyclic group of order 4 and its two subgroups. The product of these two 4-element groups is a 16-element group that has the 9 subgroups that arise from crossing a subgroup of one with a subgroup of another, but there are other subgroups, such as the "diagonal" subgroup generated by an element that projects down to a generator of each of the Z4's. Andy
<https://en.wikipedia.org/wiki/Multiplicative_function>, that is, f(1) = 1 and if n = ab where gcd(a,b) = 1 then f(n) = f(a)f(b). Thus it suffices to find f(p^n) for all primes p and positive integers n. In particular, if n is a product of k distinct primes then f(n) = 3^k since Z/(p) has 3 subsemigroups which are groups, {0}, {1} and {1,2,...p-1}. Perhaps there is a nice formula for f(p^n), n>1. Maybe someone has already mentioned this and I missed it. Too much stuff to read through.
On Thu, Apr 21, 2016 at 10:04 PM, Keith F. Lynch <kfl@keithlynch.net> wrote:
This is a reply to three people, so don't don't skip this unless you're skipping the whole topic.
Dan Asimov <asimov@msri.org> wrote:
Argh. Maybe this has fewer mistakes.
Tricky, that 5.
---------------------------- {0}, {1}, {5}, {6}
{-1, 1}, {-4, 4}
{-3, -1, 1, 3}, {-4, -2, 2, 4}
{-4, -3, -2, -1, 1, 2, 3, 4} ----------------------------
The last one is not a group.
The way I found them was, for every subset of {0,1,2,3,4,5,6,7,8,9}, to create a multiplication table and check every row to make sure each number in the maybe-group appeared once and only once. For a small number of small groups, it's practical to do this by hand.
I also made sure that in at least one row the column headers weren't permuted, i.e. that there's an identity element.
I didn't need to make sure that it's associative, since of course multiplication is associative. I didn't need to make sure each element had an inverse, since the Jth row contains the identity element for all J; the column that's in says what its inverse is.
I plan to rewrite it to be much faster. For each number I, 2 through N-1, check to see if it equals its square mod N. If so, add it to the identity element table. (0 and 1 are put in the table without checking.)
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.
Of course, as with the first program, I will precompute the whole mod N table. There's no point in doing the same calculations multiple times.
Tom Karzes <karzes@sonic.net> wrote:
Are you counting groups as distinct that are identical to each other, but happen to use different numbers for the elements? For example, {1, 3, 7, 9} is really the same group as {6, 2, 8, 4} (the elements correspond in the order listed). Does it makes sense to count it twice?
I'm not sure what you're saying. Are you pointing out that those groups are isomorphic? Yes. In that sense there are only two groups of order 4, and only one group of order N whenever N is prime.
In that same sense, the group of addition of reals is the same as the group of multiplication of positive reals; we've just relabeled all the elements. But nobody would suggest that means that multiplication isn't worthy of study because it's just addition with funny names and we already understand addition.
If so, then we're really identifying subsets of integers that generate these groups, rather than the groups themselves.
Well, yes. There's very little to be said about small groups themselves. They're useful tools for studying other things.
Joerg Arndt <arndt@jjj.de> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
Mod N, the identity elements are those numbers I such that I^2 = I mod N. For N=10, those are 0, 1, 5, and 6. The numbers of identity elements mod N appear to be given by A034444. Mod 30, there are 8 of them, and 28 groups.
A group G has one neutral ("identity") element e by definition: a * e = a = e * a for all a \in G
*A* group, yes. But as I said, mod 30 there are 28 groups:
Identity element 0: {0} Identity element 1: {1} {1,11} {1,19} {1,7,13,19} {1,17,19,23} {1,29} {1,11,19,29} {1,7,11,13,17,19,23,29} Identity element 6: {6} {6,24} {6,12,18,24} Identity element 10: {10} {10,20} Identity element 15: {15} Identity element 16: {16} {4,16} {2,4,8,16} {14,16} {16,26} {4,14,16,26} {4,16,22,28} {2,4,8,14,16,22,26,28} Identity element 21: {21} {9,21} {3,9,21,27} Identity element 25: {25} {5,25}
Usually the multiplicative group mod n consists of all u, 1<=u<n, such that gcd(u,n)=1 (the "units"). ...
You seem to have something different in mind. I'd like to warn about using existing terminology with non-standard meanings.
What would you call what I'm doing?
I think the order of any of these groups always divides phi(N).
The order of any subgroup of G is a divisor of the order of G. As the order of the multiplicative group mod N is phi(N), so your statement follows.
But that applies only to the groups with an identity element of 1. The groups with different identity elements are obviously not subgroups of a group with an identity element of 1. So it's not obvious to me that they all must have orders that divide phi(N), but they do all appear to.
First step: define everything.
I was hoping this already has a name. "Multiplicative groups mod N" is the obvious name, but if that's already taken for a subset of what I'm talking about, I'll have to use something else. Something short, so it will fit in a title of an OEIS entry.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
There's multiplicative, meaning that if GCD(a,b) = 1 then f(ab) = f(a)f(b). And there's completely multiplicative, meaning just that f(ab) = f(a)f(b) no matter what. —Dan
On Apr 22, 2016, at 9:17 AM, Andy Latto <andy.latto@pobox.com> wrote:
On Thu, Apr 21, 2016 at 11:04 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
It seems that the function f(n) = number of subsemigroups of Z/(n) which are groups is a multiplicative function
I don't think this is true. Given a subsemigroup of Za and a subsemigroup of Zb, we can generate a subsemigroup of Z(a*b) via the chinese remainder theorem. But I think that in general, not all subsemgroups of Z(a*b) arise in this way. For example, restricting ourselves for the moment just to those subsemigroups with identity element 1, suppose that for A we have a cyclic group of order 4 and its 2 subgroups, and for B we also have a cyclic group of order 4 and its two subgroups. The product of these two 4-element groups is a 16-element group that has the 9 subgroups that arise from crossing a subgroup of one with a subgroup of another, but there are other subgroups, such as the "diagonal" subgroup generated by an element that projects down to a generator of each of the Z4's.
Andy
<https://en.wikipedia.org/wiki/Multiplicative_function>, that is, f(1) = 1 and if n = ab where gcd(a,b) = 1 then f(n) = f(a)f(b). Thus it suffices to find f(p^n) for all primes p and positive integers n. In particular, if n is a product of k distinct primes then f(n) = 3^k since Z/(p) has 3 subsemigroups which are groups, {0}, {1} and {1,2,...p-1}. Perhaps there is a nice formula for f(p^n), n>1. Maybe someone has already mentioned this and I missed it. Too much stuff to read through.
On Thu, Apr 21, 2016 at 10:04 PM, Keith F. Lynch <kfl@keithlynch.net> wrote:
This is a reply to three people, so don't don't skip this unless you're skipping the whole topic.
Dan Asimov <asimov@msri.org> wrote:
Argh. Maybe this has fewer mistakes.
Tricky, that 5.
---------------------------- {0}, {1}, {5}, {6}
{-1, 1}, {-4, 4}
{-3, -1, 1, 3}, {-4, -2, 2, 4}
{-4, -3, -2, -1, 1, 2, 3, 4} ----------------------------
The last one is not a group.
The way I found them was, for every subset of {0,1,2,3,4,5,6,7,8,9}, to create a multiplication table and check every row to make sure each number in the maybe-group appeared once and only once. For a small number of small groups, it's practical to do this by hand.
I also made sure that in at least one row the column headers weren't permuted, i.e. that there's an identity element.
I didn't need to make sure that it's associative, since of course multiplication is associative. I didn't need to make sure each element had an inverse, since the Jth row contains the identity element for all J; the column that's in says what its inverse is.
I plan to rewrite it to be much faster. For each number I, 2 through N-1, check to see if it equals its square mod N. If so, add it to the identity element table. (0 and 1 are put in the table without checking.)
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.
Of course, as with the first program, I will precompute the whole mod N table. There's no point in doing the same calculations multiple times.
Tom Karzes <karzes@sonic.net> wrote:
Are you counting groups as distinct that are identical to each other, but happen to use different numbers for the elements? For example, {1, 3, 7, 9} is really the same group as {6, 2, 8, 4} (the elements correspond in the order listed). Does it makes sense to count it twice?
I'm not sure what you're saying. Are you pointing out that those groups are isomorphic? Yes. In that sense there are only two groups of order 4, and only one group of order N whenever N is prime.
In that same sense, the group of addition of reals is the same as the group of multiplication of positive reals; we've just relabeled all the elements. But nobody would suggest that means that multiplication isn't worthy of study because it's just addition with funny names and we already understand addition.
If so, then we're really identifying subsets of integers that generate these groups, rather than the groups themselves.
Well, yes. There's very little to be said about small groups themselves. They're useful tools for studying other things.
Joerg Arndt <arndt@jjj.de> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
Mod N, the identity elements are those numbers I such that I^2 = I mod N. For N=10, those are 0, 1, 5, and 6. The numbers of identity elements mod N appear to be given by A034444. Mod 30, there are 8 of them, and 28 groups.
A group G has one neutral ("identity") element e by definition: a * e = a = e * a for all a \in G
*A* group, yes. But as I said, mod 30 there are 28 groups:
Identity element 0: {0} Identity element 1: {1} {1,11} {1,19} {1,7,13,19} {1,17,19,23} {1,29} {1,11,19,29} {1,7,11,13,17,19,23,29} Identity element 6: {6} {6,24} {6,12,18,24} Identity element 10: {10} {10,20} Identity element 15: {15} Identity element 16: {16} {4,16} {2,4,8,16} {14,16} {16,26} {4,14,16,26} {4,16,22,28} {2,4,8,14,16,22,26,28} Identity element 21: {21} {9,21} {3,9,21,27} Identity element 25: {25} {5,25}
Usually the multiplicative group mod n consists of all u, 1<=u<n, such that gcd(u,n)=1 (the "units"). ...
You seem to have something different in mind. I'd like to warn about using existing terminology with non-standard meanings.
What would you call what I'm doing?
I think the order of any of these groups always divides phi(N).
The order of any subgroup of G is a divisor of the order of G. As the order of the multiplicative group mod N is phi(N), so your statement follows.
But that applies only to the groups with an identity element of 1. The groups with different identity elements are obviously not subgroups of a group with an identity element of 1. So it's not obvious to me that they all must have orders that divide phi(N), but they do all appear to.
First step: define everything.
I was hoping this already has a name. "Multiplicative groups mod N" is the obvious name, but if that's already taken for a subset of what I'm talking about, I'll have to use something else. Something short, so it will fit in a title of an OEIS entry.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Fri, Apr 22, 2016 at 1:01 PM, Dan Asimov <asimov@msri.org> wrote:
There's multiplicative, meaning that if GCD(a,b) = 1 then f(ab) = f(a)f(b).
And there's completely multiplicative, meaning just that f(ab) = f(a)f(b) no matter what.
True, but this doesn't change the fact that this function is not even multiplicative. Even if a and b are relatively prime, phi(a) and phi(b) can have a common factor, which is what leads to the additional "diagonal" groups. Andy
—Dan
On Apr 22, 2016, at 9:17 AM, Andy Latto <andy.latto@pobox.com> wrote:
On Thu, Apr 21, 2016 at 11:04 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
It seems that the function f(n) = number of subsemigroups of Z/(n) which are groups is a multiplicative function
I don't think this is true. Given a subsemigroup of Za and a subsemigroup of Zb, we can generate a subsemigroup of Z(a*b) via the chinese remainder theorem. But I think that in general, not all subsemgroups of Z(a*b) arise in this way. For example, restricting ourselves for the moment just to those subsemigroups with identity element 1, suppose that for A we have a cyclic group of order 4 and its 2 subgroups, and for B we also have a cyclic group of order 4 and its two subgroups. The product of these two 4-element groups is a 16-element group that has the 9 subgroups that arise from crossing a subgroup of one with a subgroup of another, but there are other subgroups, such as the "diagonal" subgroup generated by an element that projects down to a generator of each of the Z4's.
Andy
<https://en.wikipedia.org/wiki/Multiplicative_function>, that is, f(1) = 1 and if n = ab where gcd(a,b) = 1 then f(n) = f(a)f(b). Thus it suffices to find f(p^n) for all primes p and positive integers n. In particular, if n is a product of k distinct primes then f(n) = 3^k since Z/(p) has 3 subsemigroups which are groups, {0}, {1} and {1,2,...p-1}. Perhaps there is a nice formula for f(p^n), n>1. Maybe someone has already mentioned this and I missed it. Too much stuff to read through.
On Thu, Apr 21, 2016 at 10:04 PM, Keith F. Lynch <kfl@keithlynch.net> wrote:
This is a reply to three people, so don't don't skip this unless you're skipping the whole topic.
Dan Asimov <asimov@msri.org> wrote:
Argh. Maybe this has fewer mistakes.
Tricky, that 5.
---------------------------- {0}, {1}, {5}, {6}
{-1, 1}, {-4, 4}
{-3, -1, 1, 3}, {-4, -2, 2, 4}
{-4, -3, -2, -1, 1, 2, 3, 4} ----------------------------
The last one is not a group.
The way I found them was, for every subset of {0,1,2,3,4,5,6,7,8,9}, to create a multiplication table and check every row to make sure each number in the maybe-group appeared once and only once. For a small number of small groups, it's practical to do this by hand.
I also made sure that in at least one row the column headers weren't permuted, i.e. that there's an identity element.
I didn't need to make sure that it's associative, since of course multiplication is associative. I didn't need to make sure each element had an inverse, since the Jth row contains the identity element for all J; the column that's in says what its inverse is.
I plan to rewrite it to be much faster. For each number I, 2 through N-1, check to see if it equals its square mod N. If so, add it to the identity element table. (0 and 1 are put in the table without checking.)
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.
Of course, as with the first program, I will precompute the whole mod N table. There's no point in doing the same calculations multiple times.
Tom Karzes <karzes@sonic.net> wrote:
Are you counting groups as distinct that are identical to each other, but happen to use different numbers for the elements? For example, {1, 3, 7, 9} is really the same group as {6, 2, 8, 4} (the elements correspond in the order listed). Does it makes sense to count it twice?
I'm not sure what you're saying. Are you pointing out that those groups are isomorphic? Yes. In that sense there are only two groups of order 4, and only one group of order N whenever N is prime.
In that same sense, the group of addition of reals is the same as the group of multiplication of positive reals; we've just relabeled all the elements. But nobody would suggest that means that multiplication isn't worthy of study because it's just addition with funny names and we already understand addition.
If so, then we're really identifying subsets of integers that generate these groups, rather than the groups themselves.
Well, yes. There's very little to be said about small groups themselves. They're useful tools for studying other things.
Joerg Arndt <arndt@jjj.de> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
Mod N, the identity elements are those numbers I such that I^2 = I mod N. For N=10, those are 0, 1, 5, and 6. The numbers of identity elements mod N appear to be given by A034444. Mod 30, there are 8 of them, and 28 groups.
A group G has one neutral ("identity") element e by definition: a * e = a = e * a for all a \in G
*A* group, yes. But as I said, mod 30 there are 28 groups:
Identity element 0: {0} Identity element 1: {1} {1,11} {1,19} {1,7,13,19} {1,17,19,23} {1,29} {1,11,19,29} {1,7,11,13,17,19,23,29} Identity element 6: {6} {6,24} {6,12,18,24} Identity element 10: {10} {10,20} Identity element 15: {15} Identity element 16: {16} {4,16} {2,4,8,16} {14,16} {16,26} {4,14,16,26} {4,16,22,28} {2,4,8,14,16,22,26,28} Identity element 21: {21} {9,21} {3,9,21,27} Identity element 25: {25} {5,25}
Usually the multiplicative group mod n consists of all u, 1<=u<n, such that gcd(u,n)=1 (the "units"). ...
You seem to have something different in mind. I'd like to warn about using existing terminology with non-standard meanings.
What would you call what I'm doing?
I think the order of any of these groups always divides phi(N).
The order of any subgroup of G is a divisor of the order of G. As the order of the multiplicative group mod N is phi(N), so your statement follows.
But that applies only to the groups with an identity element of 1. The groups with different identity elements are obviously not subgroups of a group with an identity element of 1. So it's not obvious to me that they all must have orders that divide phi(N), but they do all appear to.
First step: define everything.
I was hoping this already has a name. "Multiplicative groups mod N" is the obvious name, but if that's already taken for a subset of what I'm talking about, I'll have to use something else. Something short, so it will fit in a title of an OEIS entry.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
Okay. Here's a variation of the problem. Let g(n) be the number of distinct subsemigroups of the multiplicative semigroup of the ring Z/(n). Brute force get this sequence (starting with n=1) also not in the OEIS: 1, 3, 5, 8, 7, 26, 9, 29, 20, 42, 9, 168, 13, 58, 106 Add 1 to these if you consider the empty set a semigroup. For Maple fans here's a Maple program using the Magma package to compute g(n) g:=proc(n) local A,i,j,S,c,x; A:=Matrix(n): for i from 1 to n do for j from 1 to n do A[i,j]:=(i-1)*(j-1) mod n +1; od: od: S:=combinat:-powerset(n): c:=0; for x in S do if nops(x) = 0 then next; fi; if Magma:-IsSubMagma(x,A) then c:=c+1; fi; od; return c; end proc: On Fri, Apr 22, 2016 at 1:26 PM, Andy Latto <andy.latto@pobox.com> wrote:
On Fri, Apr 22, 2016 at 1:01 PM, Dan Asimov <asimov@msri.org> wrote:
There's multiplicative, meaning that if GCD(a,b) = 1 then f(ab) = f(a)f(b).
And there's completely multiplicative, meaning just that f(ab) = f(a)f(b) no matter what.
True, but this doesn't change the fact that this function is not even multiplicative. Even if a and b are relatively prime, phi(a) and phi(b) can have a common factor, which is what leads to the additional "diagonal" groups.
Andy
—Dan
On Apr 22, 2016, at 9:17 AM, Andy Latto <andy.latto@pobox.com> wrote:
On Thu, Apr 21, 2016 at 11:04 PM, W. Edwin Clark <wclark@mail.usf.edu>
wrote:
It seems that the function f(n) = number of subsemigroups of Z/(n) which are groups is a multiplicative function
I don't think this is true. Given a subsemigroup of Za and a subsemigroup of Zb, we can generate a subsemigroup of Z(a*b) via the chinese remainder theorem. But I think that in general, not all subsemgroups of Z(a*b) arise in this way. For example, restricting ourselves for the moment just to those subsemigroups with identity element 1, suppose that for A we have a cyclic group of order 4 and its 2 subgroups, and for B we also have a cyclic group of order 4 and its two subgroups. The product of these two 4-element groups is a 16-element group that has the 9 subgroups that arise from crossing a subgroup of one with a subgroup of another, but there are other subgroups, such as the "diagonal" subgroup generated by an element that projects down to a generator of each of the Z4's.
Andy
<https://en.wikipedia.org/wiki/Multiplicative_function>, that is, f(1) = 1 and if n = ab where gcd(a,b) = 1 then f(n) = f(a)f(b). Thus it suffices to find f(p^n) for all primes p and positive integers n. In particular, if n is a product of k distinct primes then f(n) = 3^k since Z/(p) has 3 subsemigroups which are groups, {0}, {1} and {1,2,...p-1}. Perhaps there is a nice formula for f(p^n), n>1. Maybe someone has already mentioned this and I missed it. Too much stuff to read through.
On Thu, Apr 21, 2016 at 10:04 PM, Keith F. Lynch <kfl@keithlynch.net> wrote:
This is a reply to three people, so don't don't skip this unless you're skipping the whole topic.
Dan Asimov <asimov@msri.org> wrote:
Argh. Maybe this has fewer mistakes.
Tricky, that 5.
---------------------------- {0}, {1}, {5}, {6}
{-1, 1}, {-4, 4}
{-3, -1, 1, 3}, {-4, -2, 2, 4}
{-4, -3, -2, -1, 1, 2, 3, 4} ----------------------------
The last one is not a group.
The way I found them was, for every subset of {0,1,2,3,4,5,6,7,8,9}, to create a multiplication table and check every row to make sure each number in the maybe-group appeared once and only once. For a small number of small groups, it's practical to do this by hand.
I also made sure that in at least one row the column headers weren't permuted, i.e. that there's an identity element.
I didn't need to make sure that it's associative, since of course multiplication is associative. I didn't need to make sure each element had an inverse, since the Jth row contains the identity element for all J; the column that's in says what its inverse is.
I plan to rewrite it to be much faster. For each number I, 2 through N-1, check to see if it equals its square mod N. If so, add it to the identity element table. (0 and 1 are put in the table without checking.)
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.
Of course, as with the first program, I will precompute the whole mod N table. There's no point in doing the same calculations multiple times.
Tom Karzes <karzes@sonic.net> wrote:
Are you counting groups as distinct that are identical to each other, but happen to use different numbers for the elements? For example, {1, 3, 7, 9} is really the same group as {6, 2, 8, 4} (the elements correspond in the order listed). Does it makes sense to count it twice?
I'm not sure what you're saying. Are you pointing out that those groups are isomorphic? Yes. In that sense there are only two groups of order 4, and only one group of order N whenever N is prime.
In that same sense, the group of addition of reals is the same as the group of multiplication of positive reals; we've just relabeled all the elements. But nobody would suggest that means that multiplication isn't worthy of study because it's just addition with funny names and we already understand addition.
If so, then we're really identifying subsets of integers that generate these groups, rather than the groups themselves.
Well, yes. There's very little to be said about small groups themselves. They're useful tools for studying other things.
Joerg Arndt <arndt@jjj.de> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote: > Mod N, the identity elements are those numbers I such that I^2 > = I mod N. For N=10, those are 0, 1, 5, and 6. The numbers of > identity elements mod N appear to be given by A034444. Mod 30, > there are 8 of them, and 28 groups.
A group G has one neutral ("identity") element e by definition: a * e = a = e * a for all a \in G
*A* group, yes. But as I said, mod 30 there are 28 groups:
Identity element 0: {0} Identity element 1: {1} {1,11} {1,19} {1,7,13,19} {1,17,19,23} {1,29} {1,11,19,29} {1,7,11,13,17,19,23,29} Identity element 6: {6} {6,24} {6,12,18,24} Identity element 10: {10} {10,20} Identity element 15: {15} Identity element 16: {16} {4,16} {2,4,8,16} {14,16} {16,26} {4,14,16,26} {4,16,22,28} {2,4,8,14,16,22,26,28} Identity element 21: {21} {9,21} {3,9,21,27} Identity element 25: {25} {5,25}
Usually the multiplicative group mod n consists of all u, 1<=u<n, such that gcd(u,n)=1 (the "units"). ...
You seem to have something different in mind. I'd like to warn about using existing terminology with non-standard meanings.
What would you call what I'm doing?
> I think the order of any of these groups always divides phi(N).
The order of any subgroup of G is a divisor of the order of G. As the order of the multiplicative group mod N is phi(N), so your statement follows.
But that applies only to the groups with an identity element of 1. The groups with different identity elements are obviously not subgroups of a group with an identity element of 1. So it's not obvious to me that they all must have orders that divide phi(N), but they do all appear to.
First step: define everything.
I was hoping this already has a name. "Multiplicative groups mod N" is the obvious name, but if that's already taken for a subset of what I'm talking about, I'll have to use something else. Something short, so it will fit in a title of an OEIS entry.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yes, I goofed. Sorry. I tested my formula for products of primes up to 14. If I had gone to 15 I would have found my error. My formula gives 12 for n = 15 but brute force gives 14. I missed those "diagonal" cases. Anyhow I think for primes f(p) = 1 + tau(p-1). That saves a little work. On Fri, Apr 22, 2016 at 12:17 PM, Andy Latto <andy.latto@pobox.com> wrote:
On Thu, Apr 21, 2016 at 11:04 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
It seems that the function f(n) = number of subsemigroups of Z/(n) which are groups is a multiplicative function
I don't think this is true. Given a subsemigroup of Za and a subsemigroup of Zb, we can generate a subsemigroup of Z(a*b) via the chinese remainder theorem. But I think that in general, not all subsemgroups of Z(a*b) arise in this way. For example, restricting ourselves for the moment just to those subsemigroups with identity element 1, suppose that for A we have a cyclic group of order 4 and its 2 subgroups, and for B we also have a cyclic group of order 4 and its two subgroups. The product of these two 4-element groups is a 16-element group that has the 9 subgroups that arise from crossing a subgroup of one with a subgroup of another, but there are other subgroups, such as the "diagonal" subgroup generated by an element that projects down to a generator of each of the Z4's.
Andy
<https://en.wikipedia.org/wiki/Multiplicative_function>, that is, f(1) = 1 and if n = ab where gcd(a,b) = 1 then f(n) = f(a)f(b). Thus it suffices to find f(p^n) for all primes p and positive integers n. In particular, if n is a product of k distinct primes then f(n) = 3^k since Z/(p) has 3 subsemigroups which are groups, {0}, {1} and {1,2,...p-1}. Perhaps there is a nice formula for f(p^n), n>1. Maybe someone has already mentioned this and I missed it. Too much stuff to read through.
On Thu, Apr 21, 2016 at 10:04 PM, Keith F. Lynch <kfl@keithlynch.net> wrote:
This is a reply to three people, so don't don't skip this unless you're skipping the whole topic.
Dan Asimov <asimov@msri.org> wrote:
Argh. Maybe this has fewer mistakes.
Tricky, that 5.
---------------------------- {0}, {1}, {5}, {6}
{-1, 1}, {-4, 4}
{-3, -1, 1, 3}, {-4, -2, 2, 4}
{-4, -3, -2, -1, 1, 2, 3, 4} ----------------------------
The last one is not a group.
The way I found them was, for every subset of {0,1,2,3,4,5,6,7,8,9}, to create a multiplication table and check every row to make sure each number in the maybe-group appeared once and only once. For a small number of small groups, it's practical to do this by hand.
I also made sure that in at least one row the column headers weren't permuted, i.e. that there's an identity element.
I didn't need to make sure that it's associative, since of course multiplication is associative. I didn't need to make sure each element had an inverse, since the Jth row contains the identity element for all J; the column that's in says what its inverse is.
I plan to rewrite it to be much faster. For each number I, 2 through N-1, check to see if it equals its square mod N. If so, add it to the identity element table. (0 and 1 are put in the table without checking.)
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.
Of course, as with the first program, I will precompute the whole mod N table. There's no point in doing the same calculations multiple times.
Tom Karzes <karzes@sonic.net> wrote:
Are you counting groups as distinct that are identical to each other, but happen to use different numbers for the elements? For example, {1, 3, 7, 9} is really the same group as {6, 2, 8, 4} (the elements correspond in the order listed). Does it makes sense to count it twice?
I'm not sure what you're saying. Are you pointing out that those groups are isomorphic? Yes. In that sense there are only two groups of order 4, and only one group of order N whenever N is prime.
In that same sense, the group of addition of reals is the same as the group of multiplication of positive reals; we've just relabeled all the elements. But nobody would suggest that means that multiplication isn't worthy of study because it's just addition with funny names and we already understand addition.
If so, then we're really identifying subsets of integers that generate these groups, rather than the groups themselves.
Well, yes. There's very little to be said about small groups themselves. They're useful tools for studying other things.
Joerg Arndt <arndt@jjj.de> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
Mod N, the identity elements are those numbers I such that I^2 = I mod N. For N=10, those are 0, 1, 5, and 6. The numbers of identity elements mod N appear to be given by A034444. Mod 30, there are 8 of them, and 28 groups.
A group G has one neutral ("identity") element e by definition: a * e = a = e * a for all a \in G
*A* group, yes. But as I said, mod 30 there are 28 groups:
Identity element 0: {0} Identity element 1: {1} {1,11} {1,19} {1,7,13,19} {1,17,19,23} {1,29} {1,11,19,29} {1,7,11,13,17,19,23,29} Identity element 6: {6} {6,24} {6,12,18,24} Identity element 10: {10} {10,20} Identity element 15: {15} Identity element 16: {16} {4,16} {2,4,8,16} {14,16} {16,26} {4,14,16,26} {4,16,22,28} {2,4,8,14,16,22,26,28} Identity element 21: {21} {9,21} {3,9,21,27} Identity element 25: {25} {5,25}
Usually the multiplicative group mod n consists of all u, 1<=u<n, such that gcd(u,n)=1 (the "units"). ...
You seem to have something different in mind. I'd like to warn about using existing terminology with non-standard meanings.
What would you call what I'm doing?
I think the order of any of these groups always divides phi(N).
The order of any subgroup of G is a divisor of the order of G. As the order of the multiplicative group mod N is phi(N), so your statement follows.
But that applies only to the groups with an identity element of 1. The groups with different identity elements are obviously not subgroups of a group with an identity element of 1. So it's not obvious to me that they all must have orders that divide phi(N), but they do all appear to.
First step: define everything.
I was hoping this already has a name. "Multiplicative groups mod N" is the obvious name, but if that's already taken for a subset of what I'm talking about, I'll have to use something else. Something short, so it will fit in a title of an OEIS entry.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
On Thu, Apr 21, 2016 at 10:04 PM, 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?
*A* group, yes. But as I said, mod 30 there are 28 groups:
Identity element 0: {0} Identity element 1: {1} {1,11} {1,19} {1,7,13,19} {1,17,19,23} {1,29} {1,11,19,29} {1,7,11,13,17,19,23,29}
{1, 7, 13, 19} is not a group; 7 * 13 = 11.I haven't checked the rest of your list. 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. Andy
{1, 7, 13, 19} is not a group; 7 * 13 = 11.I haven't checked the rest of your list.
My wetware says (7*13)%30 = (91 % 30) = 1.
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.
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
I haven't been reading all these messages, but here goes anyway.... In every finite commutative monoid M, you get its maximal subgroups by.... (1) Computing first its set of idempotents X (ie those elements x such that x^2 =x). (2) Then, for each x in X, compute the subset S(x) of y's such that x divides y and y divides x. Each set S(x) is a maximal subgroup of M with identity the idempotent x. For the particular case of the integers modulo 30, I got these idempotents and maximal subgroups In[1164]:= idempotents = Select[elements, mult[#, #] == # &] Out[1164]= {0, 1, 6, 10, 15, 16, 21, 25} 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}} Listing all the subgroups is more work, but they're easily found via this divide and conquer technique. On Fri, Apr 22, 2016 at 10:34 AM, Tom Rokicki <rokicki@gmail.com> wrote:
{1, 7, 13, 19} is not a group; 7 * 13 = 11.I haven't checked the rest of your list.
My wetware says (7*13)%30 = (91 % 30) = 1.
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.
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/
I like this a lot, and am going to rewrite the maximal subgroups in my preferred form that includes negative numbers, for symmetry's sake: {0} {15} {-5, 5} {-10, 10} {-9, -3, 3, 9} {-12, -6, 6, 12} {-13, -11, -7, -1, 1, 7, 11, 13} {-14, -8, -4, -2, 2, 4, 8}, —Dan 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.
On Apr 22, 2016, at 12:41 PM, Thane Plambeck <tplambeck@gmail.com> wrote:
I haven't been reading all these messages, but here goes anyway....
In every finite commutative monoid M, you get its maximal subgroups by....
(1) Computing first its set of idempotents X (ie those elements x such that x^2 =x). (2) Then, for each x in X, compute the subset S(x) of y's such that x divides y and y divides x.
Each set S(x) is a maximal subgroup of M with identity the idempotent x.
For the particular case of the integers modulo 30, I got these idempotents and maximal subgroups
In[1164]:= idempotents = Select[elements, mult[#, #] == # &] Out[1164]= {0, 1, 6, 10, 15, 16, 21, 25}
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}}
Listing all the subgroups is more work, but they're easily found via this divide and conquer technique.
Arrgh^arrgh. That last one should have been {-14, -8, -4, -2, 2, 4, 8, 14} , of course. (In case it helps to know, I'm wearing an out-of-date pair of glasses while I wait for the new ones.) —Dan
On Apr 22, 2016, at 1:34 PM, Dan Asimov <dasimov@earthlink.net> wrote:
I like this a lot, and am going to rewrite the maximal subgroups in my preferred form that includes negative numbers, for symmetry's sake:
{0}
{15}
{-5, 5}
{-10, 10}
{-9, -3, 3, 9}
{-12, -6, 6, 12}
{-13, -11, -7, -1, 1, 7, 11, 13}
{-14, -8, -4, -2, 2, 4, 8},
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 On Fri, Apr 22, 2016 at 2:52 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Arrgh^arrgh.
That last one should have been
{-14, -8, -4, -2, 2, 4, 8, 14}
, of course.
(In case it helps to know, I'm wearing an out-of-date pair of glasses while I wait for the new ones.)
—Dan
On Apr 22, 2016, at 1:34 PM, Dan Asimov <dasimov@earthlink.net> wrote:
I like this a lot, and am going to rewrite the maximal subgroups in my preferred form that includes negative numbers, for symmetry's sake:
{0}
{15}
{-5, 5}
{-10, 10}
{-9, -3, 3, 9}
{-12, -6, 6, 12}
{-13, -11, -7, -1, 1, 7, 11, 13}
{-14, -8, -4, -2, 2, 4, 8},
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/
participants (7)
-
Andy Latto -
Dan Asimov -
Dan Asimov -
Keith F. Lynch -
Thane Plambeck -
Tom Rokicki -
W. Edwin Clark