[math-fun] Asimov's group-metric puzzle
From: Dan Asimov <asimov@msri.org> Let (G, *) be a finite group. 1. Then (say by left multiplication) G acts as a group LG of permutations on itself: LG := {L_g | g in G} is a subgroup of S(G), where L_g(x) := gx for all x in G and all g in G, and S(G) is the group of all permutations of the set G. 2. Definition: A left-invariant metric D on G is one such that for every g in G, the permutation L_g: G -> G is an isometry. 3. There is always a left-invariant metric D on G. For, pick any metric d on G, and average it over the action of LG... D(x,y) := (1/|G|) Sum_{g in G} d(L_g(x), L_g(y))
--WDS COMMENT: this proof has a gap: you implicitly assumed such a metric d existed to start with. If we allow trivial metrics e.g. all distances are 1 except dist(x,x)=0, then ok, but it is not immediately obvious a nontrivial metric exists? Oh, I see: if a,b unequal then dist(a,b)=1+epsilon*random should work as "d".
4. Question: Which finite groups G have some left-invariant metric D whose full group of isometries is precisely the left multiplications Isom((G,D)) = {L_g | g in G} ??? 5. Example: Let G be the alternating group A_3. Every left-invariant metric D makes G into an equilateral triangle. But every equilateral triangle has a 6-element isometry group, S_3.
--WDS: The reason the A3 example fails is that A3 has an "outer automorphism" consisting of conjugation by an element of S3 that is not a member of A3. For any group, if g is a member, any conjugation map x --> g^(-1) x g is an automorphism. An automorphism not of this form, is "outer." So one might make the tentative conjecture, that the answer to Dan's question is "every group that has no outer automorphisms." Here is a list of the sporadic simple groups without Outer auts: M11, M23, M24, Co1, Co2, Co3, Th, Fi23, B, M, J1, Ru, J3, Ly (source: http://brauer.maths.qmul.ac.uk/Atlas/v3/spor/) Here is a list of nonsporadic simple groups without outer auts: S_a(2) apparently for all even a>=6, G2(5), E7(p), E8(p), E8(p) apparently for all primes p, Here is a list of nonsporadic simple groups with outer auts: A_n for each n>=3, L_a(b) apparently for all a>=2 and b>=2, S_a(b) apparently for all b>=3, U_a(b) apparently for all a,b, O_a(b), O+_a(b), O-_a(b) apparently for all a,b Here is a list of the sporadic simple groups with outer auts: M12, M22, HS, J2, McL, Suz, He, HN, Fi22, Fi24', O'N, J3, T As a positive example: There are some well known metrics on S_n, the group of n! permutations, including the number of inversions, and the euclidean and L1 distance metrics in n-space. In general: all we need to know is the distances(x,Id) where Id is the identity element. What if we consider the multiplicative group of nonsingular kXk matrices over some field F? Well, for Lie groups, see John Milnor: Curvatures of left invariant metrics on lie groups, Advances in Mathematics 21,3 (September 1976) 293-329 which begins with the claim "each n-dimensional Lie group possesses a (n-1)n/2-dimensional family of distinct left invariant metrics." If F is the complex numbers, using dist(Id,M) is some suitable function of the eigenvalues of M, such as dist=SUM |log(eigenvalue)|, perhaps works? But if F is (say) a finite field, then what? For any finite group G, the full set of left invariant metrics is describable as the solution of a linear program, i.e. is a polytope. One might ask whether and when the symmetries of this polytope are G. So... interesting puzzle, possibly with rich connections to a lot of stuff; sorry I have not solved it. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
="Warren D Smith" <warren.wds@gmail.com>
From: Dan Asimov <asimov@msri.org> Let (G, *) be a finite group. 1. Then (say by left multiplication) G acts as a group LG of permutations on itself: LG := {L_g | g in G} is a subgroup of S(G), where L_g(x) := gx for all x in G and all g in G, and S(G) is the group of all permutations of the set G. 2. Definition: A left-invariant metric D on G is one such that for every g in G, the permutation L_g: G -> G is an isometry. 3. There is always a left-invariant metric D on G. For, pick any metric d on G, and average it over the action of LG... D(x,y) := (1/|G|) Sum_{g in G} d(L_g(x), L_g(y))
--WDS COMMENT: this proof has a gap: you implicitly assumed such a metric d existed to start with. If we allow trivial metrics e.g. all distances are 1 except dist(x,x)=0, then ok, but it is not immediately obvious a nontrivial metric exists? Oh, I see: if a,b unequal then dist(a,b)=1+epsilon*random should work as "d".
4. Question: Which finite groups G have some left-invariant metric D whose full group of isometries is precisely the left multiplications Isom((G,D)) = {L_g | g in G} ??? 5. Example: Let G be the alternating group A_3. Every left-invariant metric D makes G into an equilateral triangle. But every equilateral triangle has a 6-element isometry group, S_3.
--WDS: The reason the A3 example fails is that A3 has an "outer automorphism" consisting of conjugation by an element of S3 that is not a member of A3.
For any group, if g is a member, any conjugation map x --> g^(-1) x g is an automorphism. An automorphism not of this form, is "outer."
So one might make the tentative conjecture, that the answer to Dan's question is "every group that has no outer automorphisms."
Here is a list of the sporadic simple groups without Outer auts: M11, M23, M24, Co1, Co2, Co3, Th, Fi23, B, M, J1, Ru, J3, Ly (source: http://brauer.maths.qmul.ac.uk/Atlas/v3/spor/)
Here is a list of nonsporadic simple groups without outer auts: S_a(2) apparently for all even a>=6, G2(5), E7(p), E8(p), E8(p) apparently for all primes p,
Here is a list of nonsporadic simple groups with outer auts: A_n for each n>=3, L_a(b) apparently for all a>=2 and b>=2, S_a(b) apparently for all b>=3, U_a(b) apparently for all a,b, O_a(b), O+_a(b), O-_a(b) apparently for all a,b
Here is a list of the sporadic simple groups with outer auts: M12, M22, HS, J2, McL, Suz, He, HN, Fi22, Fi24', O'N, J3, T
As a positive example: There are some well known metrics on S_n, the group of n! permutations, including the number of inversions, and the euclidean and L1 distance metrics in n-space.
In general: all we need to know is the distances(x,Id) where Id is the identity element.
What if we consider the multiplicative group of nonsingular kXk matrices over some field F? Well, for Lie groups, see John Milnor: Curvatures of left invariant metrics on lie groups, Advances in Mathematics 21,3 (September 1976) 293-329 which begins with the claim "each n-dimensional Lie group possesses a (n-1)n/2-dimensional family of distinct left invariant metrics." If F is the complex numbers, using dist(Id,M) is some suitable function of the eigenvalues of M, such as dist=SUM |log(eigenvalue)|, perhaps works?
But if F is (say) a finite field, then what?
For any finite group G, the full set of left invariant metrics is describable as the solution of a linear program, i.e. is a polytope. One might ask whether and when the symmetries of this polytope are G.
So... interesting puzzle, possibly with rich connections to a lot of stuff; sorry I have not solved it.
[sorry for the previous spam]
="Warren D Smith" <warren.wds@gmail.com>
Here is a list of the sporadic simple groups without Outer auts: M11, M23, M24, Co1, Co2, Co3, Th, Fi23, B, M, J1, Ru, J3, Ly (source: http://brauer.maths.qmul.ac.uk/Atlas/v3/spor/)
Here is a list of the sporadic simple groups with outer auts: M12, M22, HS, J2, McL, Suz, He, HN, Fi22, Fi24', O'N, J3, T
J3 appears in both lists, but J4 in neither?
It depends on whether one considers Jacques' group to be a sporadic group (in which case 27) or a group of Lie type (in which case 26).
Sent: Thursday, September 17, 2015 at 10:09 PM From: "Dan Asimov" <asimov@msri.org> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Asimov's group-metric puzzle
Even with one of the J3's changed into a J4, it appears there are now 27 sporadic simple groups.
-Dan
On Sep 17, 2015, at 12:03 PM, Marc LeBrun <mlb@well.com> wrote:
J3 appears in both lists, but J4 in neither?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Huh? Ah --- THAT Jacques! WFL On 9/17/15, Adam P. Goucher <apgoucher@gmx.com> wrote:
It depends on whether one considers Jacques' group to be a sporadic group (in which case 27) or a group of Lie type (in which case 26).
Sent: Thursday, September 17, 2015 at 10:09 PM From: "Dan Asimov" <asimov@msri.org> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Asimov's group-metric puzzle
Even with one of the J3's changed into a J4, it appears there are now 27 sporadic simple groups.
-Dan
On Sep 17, 2015, at 12:03 PM, Marc LeBrun <mlb@well.com> wrote:
J3 appears in both lists, but J4 in neither?
_______________________________________________ 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
Here's a cute question, which may be trivial: Hex is of course a win for the first player. Let's give the second player a small advantage: every million moves (starting with the millionth) the 2nd player can place two stones instead of one. I conjecture that for all sufficiently large boards, the second player now has a winning strategy. Is this obvious? I know that the second player wins if we provide her with some other kinds of advantage, like removing one row of the board, but I don't see any obvious way to reduce this to that case. - Cris p.s. Is there anyone out there who sells a nice wooden Hex board?
="Dan Asimov" <asimov@msri.org>
Even with one of the J3's changed into a J4, it appears there are now 27 sporadic simple groups.
-Dan
On Sep 17, 2015, at 12:03 PM, Marc LeBrun <mlb@well.com> wrote:
J3 appears in both lists, but J4 in neither?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Sep 17, 2015, at 4:27 PM, Marc LeBrun <mlb@well.com> wrote:
[sheesh, sorry again for premature spamsm]
="Dan Asimov" <asimov@msri.org>
Even with one of the J3's changed into a J4, it appears there are now 27 sporadic simple groups.
-Dan
I think the Tits group T is being considered an honorary sporadic here?
It could be. I don't even know why it isn't considered a regular sporadic group (pardon the oxymoron). Alternatively, there is also: ----- Jacques Leplat Company Owner, Developer at J3 LIMITED ----- —Dan
P.S. The Subject line is incorrect. This was not posted as a puzzle; I don't know the answer. -Dan
On Sep 17, 2015, at 4:27 PM, Marc LeBrun <mlb@well.com> wrote:
="Dan Asimov" <asimov@msri.org>
Even with one of the J3's changed into a J4, it appears there are now 27 sporadic simple groups.
-Dan
I think the Tits group T is being considered an honorary sporadic here?
participants (7)
-
Adam P. Goucher -
Cris Moore -
Dan Asimov -
Dan Asimov -
Fred Lunnon -
Marc LeBrun -
Warren D Smith