Re: [math-fun] Simple finite group problem
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
4 14 16 26
Note that that's isomorphic to the other one of the two abstract groups of order 4, the one that isn't a cyclic group. Inspired by that, here's an absurdly bold conjecture with remarkably little evidence: *Every* finite abelian group is isomorphic to some multiplicative group mod N. Someone prove me wrong. After I get my program to find all such groups through at least N=1000 working, I'll check and see if it appears to be true. Of course whatever I find will constitute neither a proof or a disproof, but it may inspire insight. In support of that, is there any online database of small abstract abelian groups? I see little point in reinventing that wheel. Thanks.
On Sun, Apr 24, 2016 at 11:06 PM, Keith F. Lynch <kfl@keithlynch.net> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
4 14 16 26
Note that that's isomorphic to the other one of the two abstract groups of order 4, the one that isn't a cyclic group.
Inspired by that, here's an absurdly bold conjecture with remarkably little evidence: *Every* finite abelian group is isomorphic to some multiplicative group mod N. Someone prove me wrong.
Your conjecture is not hard to prove, if you know the fundamental theorem of Abelian groups (every abelian group is the direct product of cyclic groups) and Dirichlet's theorem on primes in arithmetic progressions (if a and b are relatively prime, there are infinitely many primes of the form an + b). Let's say we're looking for the subsemigroups of Z/N* that are groups. Let the prime factorization of N be N = Prod_{i=1}^n p_i^{e_i}. Let's first solve this for n = 1, that is, for N a prime power. The only possible identity elements are 0 and 1, since those are the only solutions of X^2 = X mod p^n. The only possible group with identity 0 is the 1-element group, since if 0 is the multiplicative identity and a is in the group, a = a * 0 = 0. If the identity is 1, then any element of it must be relatively prime to p. The set of all p^n - p^{n-1} of these form a cyclic group. This has one subgroup for every divisor of its order. For the general case, The identity element has to be either 0 or 1 mod p_i^{e_i} for each i. So there are 2^N possible identity elements, one for each subset of {1, 2, ... n}. So let's fix a subset S of {1, 2, ... n}, call the complement of S in {1, 2, ... n} S', and let's find all the groups with an identity element that is 1 mod p_i^{n_i} for i in S, and 0 mod p_i^{n_i} for i in S'. Such a group is still a group mod p_i^{n_i} for i in S', which must be the 1-element group, so all its elements are multiples of p_i^{n_i}. So for the chosen identity element, we can divide all the group elements by Prod_{i in S'} p_i^n_i, and we are left with the multiplicative group of Z mod M, where M = Prod_{i in S} p_i^{e_i}, which is the product of the cyclic groups of order phi(p_i^{e_i}) for i in S. The original problem asked us to count these groups. While there is a formula, it's fairly involved; see for example http://math.ubbcluj.ro/~calu/nrsubgroup.pdf But the new question of whether every abelian group arises in this way is much easier. If we want to find the cyclic group of order M, we need to find a prime power p^n such that M divides phi(p^n). But this is easy, by Dirichlet's theorem. We can even require n = 1. We're then looking for a prime p such that M divides p-1, that is p must be of the form k * M +1. There are infinitely many such primes, so we can find as many cyclic groups of any desired order as we like, Since any finite abelian group is the direct product of cyclic groups, we can obtain any abelian group in this way. Andy
I wrote: ----- Just to mention that, although the classification of finite abelian groups really isn't that hard, Dirichlet's theorem on primes in arithmetic progressions, on the other hand, is a pioneering and deep theorem that introduces several new ideas and was probably the first proof in analytic number theory. So I wonder if the existence of any finite group up to isomorphism as a multiplicative subsemigroup of at least one ring Z/N (N in Z+) can be proved by more elementary methods than an appeal to Dirichlet. ----- after Andy wrote:
On Apr 24, 2016, at 9:54 PM, Andy Latto <andy.latto@pobox.com> wrote:
But the new question of whether every abelian group arises in this way is much easier. If we want to find the cyclic group of order M, we need to find a prime power p^n such that M divides phi(p^n). But this is easy, by Dirichlet's theorem. We can even require n = 1. We're then looking for a prime p such that M divides p-1, that is p must be of the form k * M +1. There are infinitely many such primes, so we can find as many cyclic groups of any desired order as we like, Since any finite abelian group is the direct product of cyclic groups, we can obtain any abelian group in this way.
But a colleague kindly pointed out that Andy's proof uses only the case of an arithmetic sequence = 1 mod M, which is among a number of cases of Dirichlet's theorem that can be proved without recourse to the advanced techniques of characters and analytic number theory, but instead by generalizing Euclid's proof of the infinitude of primes: This is proved in some generality in this lovely paper, Prime numbers in certain arithmetic progressions by M. Ram Murty and Nithum Thain: http://projecteuclid.org/download/pdf_1/euclid.facm/1229442627 <http://projecteuclid.org/download/pdf_1/euclid.facm/1229442627> in Theorem 6, or more specifically see the remark after the Corollary to Theorem 5. —Dan
In fact I think that it is true that every finite abelian group is isomorphic to a subgroup of the group of units of Z/(n) for n a product of distinct primes. To see this note that if n is a product of distinct primes p_1,...,p_k then the group of units is a product C_{p_1-1}xC_{p_2-1} x...xC_{p_k-1} where C_{p-1} is a cyclic group of order p - 1. Then it suffices to show that for any sequence q_1,...,q_s of prime powers there are distinct prime p_1,...,p_s such that q_i divides p_i -1 for all i. Then then C_{p_i-1} will have a subgroup of order q_i , etc.. This follows from Dirichlet's theorem_on_arithmetic_progressions <https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions> , Namely since for any one of the q's, gcd(q,1) = 1, there are infinitely many primes p of the form p =q * k +1 Hence q divides p -1. And since there are infinitely many such primes we can chose a different prime p_i for each q_i. Of course here I use the fact that every finite abelian group is the product of cyclic groups of prime power order. If I recall correctly this is a trick that Everett Dade told me about over half century ago. On Sun, Apr 24, 2016 at 11:06 PM, Keith F. Lynch <kfl@keithlynch.net> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
4 14 16 26
Note that that's isomorphic to the other one of the two abstract groups of order 4, the one that isn't a cyclic group.
Inspired by that, here's an absurdly bold conjecture with remarkably little evidence: *Every* finite abelian group is isomorphic to some multiplicative group mod N. Someone prove me wrong.
After I get my program to find all such groups through at least N=1000 working, I'll check and see if it appears to be true. Of course whatever I find will constitute neither a proof or a disproof, but it may inspire insight. In support of that, is there any online database of small abstract abelian groups? I see little point in reinventing that wheel. Thanks.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Just to mention that, although the classification of finite abelian groups really isn't that hard, Dirichlet's theorem on primes in arithmetic progressions, on the other hand, is a pioneering and deep theorem that introduces several new ideas and was probably the first proof in analytic number theory. So I wonder if the existence of any finite group up to isomorphism as a multiplicative subsemigroup of at least one ring Z/N (N in Z+) can be proved by more elementary methods than an appeal to Dirichlet. —Dan On Apr 24, 2016, at 9:59 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote: In fact I think that it is true that every finite abelian group is isomorphic to a subgroup of the group of units of Z/(n) for n a product of distinct primes. . . . . . . This follows from Dirichlet's theorem_on_arithmetic_progressions <https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressio... <https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions>> On Apr 24, 2016, at 9:54 PM, Andy Latto <andy.latto@pobox.com> wrote: Your conjecture is not hard to prove, if you know the fundamental theorem of Abelian groups (every abelian group is the direct product of cyclic groups) and Dirichlet's theorem on primes in arithmetic progressions (if a and b are relatively prime, there are infinitely many primes of the form an + b).
Inspired by that, here's an absurdly bold conjecture with remarkably little evidence: *Every* finite abelian group is isomorphic to some multiplicative group mod N. Someone prove me wrong.
Interesting suggestion.
After I get my program to find all such groups through at least N=1000 working, I'll check and see if it appears to be true. Of course whatever I find will constitute neither a proof or a disproof, but it may inspire insight. In support of that, is there any online database of small abstract abelian groups? I see little point in reinventing that wheel. Thanks.
There's a simple decomposition theorem for finite abelian groups. Consider any choice E: {2, 3, 5, 7,...} —> {0, 1, 2, 3, ...} of a nonnegative integer e(p) for each prime p, *such that* e(p) > 0 *for only finitely many primes* p. Then such e are in one-to-one correspondence with finite abelian groups, up to group isomorphism. Namely, E <—> Z/2^e(2) + Z/3^e(3) + Z/5^e(5) + Z/7^e(7) + ... where + denotes direct sum. For more see https://en.wikipedia.org/wiki/Finitely_generated_abelian_group#Classificatio... (and ignore the Z^k direct summands, since that article more generally addresses the classification of finitely *generated* abelian groups, which is only infinitesimally more complicated). —Dan
Never mind, I think I managed to screw even this up. arrgh^(arrgh^arrgh) by forgetting that a prime's power can occur more than once. (The link is still valid, though.) —Dan
On Apr 24, 2016, at 10:03 PM, Dan Asimov <asimov@msri.org> wrote:
Inspired by that, here's an absurdly bold conjecture with remarkably little evidence: *Every* finite abelian group is isomorphic to some multiplicative group mod N. Someone prove me wrong.
Interesting suggestion.
After I get my program to find all such groups through at least N=1000 working, I'll check and see if it appears to be true. Of course whatever I find will constitute neither a proof or a disproof, but it may inspire insight. In support of that, is there any online database of small abstract abelian groups? I see little point in reinventing that wheel. Thanks.
There's a simple decomposition theorem for finite abelian groups.
Consider any choice
E: {2, 3, 5, 7,...} —> {0, 1, 2, 3, ...}
of a nonnegative integer e(p) for each prime p, *such that*
e(p) > 0
*for only finitely many primes* p.
Then such e are in one-to-one correspondence with finite abelian groups, up to group isomorphism.
Namely,
E <—> Z/2^e(2) + Z/3^e(3) + Z/5^e(5) + Z/7^e(7) + ...
where + denotes direct sum.
For more see
https://en.wikipedia.org/wiki/Finitely_generated_abelian_group#Classificatio...
(and ignore the Z^k direct summands, since that article more generally addresses the classification of finitely *generated* abelian groups, which is only infinitesimally more complicated).
—Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Andy Latto -
Dan Asimov -
Dan Asimov -
Keith F. Lynch -
W. Edwin Clark