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