Recent searches
Search options
HARDCORE MATH POST
The McGee graph, shown here by Mamuka Jibladze, is the unique graph where each vertex has 3 neighbors and the shortest cycles have length 7. As it moves in this animation, each vertex comes back to its original position after two turns, so this illustrates an 8-fold symmetry of the McGee graph.
The symmetry group of the McGee graph has order 32, and Greg Egan and I figured out a bunch of what's going on here:
https://blogs.ams.org/visualinsight/2015/09/15/mcgee-graph/
though I'd still like a simpler construction of the McGee graph based on this group.
This group, let's call it the 'McGree group', is the semidirect product of ℤ/8 with its automorphism group. Alternatively, it's the group of affine transformations of ℤ/8, i.e. transformations
x ↦ a x + b
where a,b ∈ ℤ/8 and a is invertible, so a = 1,3,5,7. That gives 32 elements.
I gave a talk about this today and someone instantly pointed out that the McGee group is the smallest group G with an outer automorphism f: G → G that maps each element of G to an element in the same conjugacy class! So for each g∈G we have
f(g) = hgh⁻¹
for some h∈G, but we can't use the same h for all g! You could call f a 'pseudo-inner automorphism'.
𝐏𝐮𝐳𝐳𝐥𝐞: Explicitly describe a pseudo-inner automorphism of the McGee group.
There should be a nice description in terms of ℤ/8, and there should also be a visually nice description of how to turn any symmetry of the McGee graph into a new symmetry that is conjugate to g, but not always via the same element h!
I tried to solve the puzzle, but I must be confused about something.
If you conjugate (a,b) with (c,d) I think you get (a, b c + d - a d), but most importantly the first element, a, is unchanged. So any automorphism of the kind the puzzle is describing must leave the a in x ↦ a x + b unchanged.
Suppose we try to find such an automorphism by brute force, and start by looking at what it does to the subgroup consisting of elements of the form x ↦ x + b (which it must preserve). All it can do is change b by permuting the elements of ℤ/8.
When I checked all 8! permutations of ℤ/8, the only nontrivial ones for which this is an automorphism are those that correspond to multiplication of b by 3, 5 or 7. But these are inner automorphisms, corresponding to conjugation by (3,0), (5,0) or (7,0).
I must be doing something wrong! Can you give me a hint as to where I’ve messed up?
@gregeganSF @johncarlosbaez The partial automorphisms you found are inner on the a=1 subgroup, but they might be non inner once you extend them to the whole group.
@oantolin @gregeganSF - I'm afraid this is one of those nasty puzzles where I don't know the answer. Worst case: the guy who confidently told me SmallGroup(32,43) has this surprising property was wrong, or it's not the group of affine transformations we think it is. [EDIT: I ruled out these possibilities in later comments.]
It's true that in a semidirect product A ⋉ B with both A and B abelian, conjugation by any element leaves the first component in (a,b) ∈ A ⋉ B unchanged. (Another fun example: the rotation/translation group of the plane.)
The only way out I see is what @oantolin suggests: there's an automorphism f that multiplies b by 1, 3, 5, or 7 in a way that depends nontrivially on a:
f(a,b) = (a, n(a)b)
where n(a) = 1, 3, 5, or 7 and n is not a constant function.
Thanks for tackling this!
@oantolin @gregeganSF - SmallGroup(32,43) is indeed the group we're talking about here:
https://groupprops.subwiki.org/wiki/Holomorph_of_Z8
It's called the "holomorph" of ℤ/8 because it's the semidirect product of ℤ/8 and its automorphism group (which as Greg checked is the multiplicative group of ℤ/8).
Unfortunately this pages doesn't mention automorphisms of SmallGroup(32,43).
So, we should check which functions
n: {1,3,5,7} → {1,3,5,7}
give
f(a,b) = (a, n(a)b)
with
f((a,b),(a',b')) = f(a,b) f(a',b')
I checked all 4^4 possibilities, but I can’t find any functions where this is true other than the constant functions.
So either my calculations are flawed, or something trickier is happening to b that can't be achieved with multiplication.
Checking all (8!)^4 choices of four independent permutations of ℤ/8 isn’t practical ... and though I *think* the a=1 case must correspond to multiplication by 3, 5 or 7, even 3 * (8!)^3 is too big.
I think I’ve found four class-preserving outer automorphisms of Aff(ℤ/8)!
You map:
x ↦ a x + b
to:
x ↦ a x + (b + D(a))
where the values of D on 1, 3, 5, 7 must be one of these choices:
0, 0, 4, 4
0, 2, 0, 2
0, 4, 4, 0
0, 6, 0, 6
I don’t think these are the only possibilities. But I’m still searching through the (4!)^8 choices of permutations of the odd and even parts of ℤ/8, for each value of a.
Conjugation preserves the parity of b, so rather than there being 8! choices of permutations of ℤ/8 for each value of a, there are (4!)^2.
* Edited to add: You can get even more outer automorphisms like these by multiplying b, as well as adding to it:
x ↦ a x + (q b + D(a))
where q is chosen from {1, 3, 5, 7}.
Here q is independent of a, and if you didn’t add D(a) you would get an inner automorphism.
I’m fairly sure these 16 cases are the only class-preserving outer automorphisms.
The crucial properties that D(a) needs to satisfy in order to get an automorphism are:
D(a c) = a D(c) + D(a) = c D(a) + D(c)
D(1) = 0
while D(a) = 0 for all a is ruled out, because then the automorphism is inner.
@gregeganSF @johncarlosbaez @oantolin those equations are exactly the definition of crossed homomorphism in this context (they all follow from the first equation, using the fact that the group doing the acting is commutative, and the action is faithful).
@joshuagrochow @gregeganSF @oantolin - super-cool! I was trying to recognize these equations but I didn't. I wrote a post explaining crossed homomorphisms when I was first trying to understand them:
https://golem.ph.utexas.edu/category/2020/04/crossed_homomorphisms.html
@johncarlosbaez @gregeganSF @oantolin the gif in the first post looks very Mobius-y. Looks like you can view the graph in terms of a 3-cover of the 8-cycle, where you then connect the 3 vertices in each fiber in a path (blue-red-blue) and then add in the red edges after. Definitely feels like something cohomology-y going on.
(But I should be doing other things now - maybe I'll give a shot at making this more precise in a day or two.)
@johncarlosbaez @joshuagrochow @oantolin
I should just add that, while the equation:
D(a c) = a D(c) + D(a)
makes the map:
x ↦ a x + b
↓
x ↦ a x + (b q + D(a))
into an automorphism (where q is any invertible element), when you *also* need it to be class-preserving and outer, if you compare this with what happens to
x ↦ a x + b
conjugated by:
x ↦ c x + d
Namely:
x ↦ a x + (b c + d (1-a))
you have the additional constraint that:
D(a) = δ(a) (1-a)
where δ(a) is not a constant function.
@gregeganSF @johncarlosbaez @oantolin I mean, sure, but I feel like that fits in the following analogy
cohomology class : automorphism coming from a crossed hom
::
nontrivial coho class : non-inner automorphism coming from a crossed hom
And then the thing about class-preserving is a subgroup of automorphisms coming from crossed homs
I wasn’t arguing against anything you’re saying, I was just trying to spell out all the requirements on D(a) for the sake of performing concrete calculations.
@gregeganSF @johncarlosbaez @oantolin Oh, I don't think you were arguing against what I was saying at all - sorry if I phrased something that way. Just trying to figure out where the cohomology is here!
@gregeganSF @johncarlosbaez @oantolin This totally nerd-sniped me.
For the role of derivations in automorphisms of group extensions, check out the Wells exact sequence (and more recent work on it e.g. Buckley, Malfait, Jin-Liu), nicely exposited (w/ refs) by Jill Dietz in https://doi.org/10.1017/CBO9781316227343.013.
I had some thoughts about building the McGee graph from covering graphs (or etale covers, at least), but I think maybe they are too complicated to be worth writing down.
@joshuagrochow @oantolin - I'll definitely check this out. Do you think the Wells exact sequence helps explain what @gregeganSF found?
Greg found a way to construct the McGee graph from the McGee group, but I'm hoping the description of the two kinds of edges can be simplified.
@johncarlosbaez @oantolin @gregeganSF oh, uh, maybe not. Just explains why derivations appeared when computing automorphism of GA(1,Z/8).
But the three types of edges I do have some sort of an explanation for.
Think of B=Z/8=red vertices as the base. The blue vertices and edges between them are something like a global section of a certain 6-fold etale cover of the graph B w edges=odd differences.
Between red verts (in B) there are 3 natural choices for edge set (these are the orbitals of GA(1,Z/8)): nearby, opposite, and distant in @gregeganSF's terminology. Since the edges btwn blue verts cover the distant edges, we should really include nearby edges in B with one color and opposite with another. To make McGee 3-regular, choose to make opposite pairs edges and nearby pairs non-edges in B.
The edges between blue and red vertices are then just the 2-fold "covering map" (it's not quite a cover, because it's 2-to-1 but over each odd edge that would be present in the base there's only one blue edge instead of 2).
@johncarlosbaez @oantolin @gregeganSF realized that maybe wasn't so clear. Think of the base B as an edge-colored graph. Odd edges are colored gold, opposite edges colored black, and nearby edges colored clear. (Clear and gold edges will get deleted in the McGee graph.) The edges between blue vertices cover (in some sense) the gold edges.
The 6-fold sort-of-cover of the gold edges I have in mind has vertices (p, {q, r}) where q-p and r-p are odd and distinct. And edges when p is in q'r' and p' is in qr. Over each gold edge there is a K_{3,3}.