search

SupposeNot / RAMP

Research Assistant for Maps and Polytopes
4 stars 0 forks source link

Add Algorithm for Classifying ARP for a fixed group #178

Open Mixer2021 opened 1 year ago

SupposeNot commented 1 year ago

What's the scope on this? Is the idea "Let $G$ be a group, identify all abstract regular polytopes with automorphism group $G$."?

CunningGabe commented 1 year ago

I believe that was the idea, yes. I think the thought here (for starters) was less "come up with a novel algorithm" but rather "use the obvious technique without worrying about efficiency". (In other words, identify all involutions, and then find all "stringy" sequences of involutions that generate the group.)

Mark: I might be able to use some tight polytope stuff to help optimize this - e.g. to help know how high of a rank we need to look in.

SupposeNot commented 1 year ago

Do we want to find ALL... or do we want to find all UP TO ISOMORPHISM?

Hartley has some nice code/writeups of stuff we can borrow/adapt. Happy to poke at that.

CunningGabe commented 1 year ago

Ah good point - I guess just up to isomorphism.

Mixer2021 commented 1 year ago

I think find ALL should mean up to isomorphism here. We could also include up to duality if we prefer, but that sometimes is annoying (see Marston's data).

If we want to consider isomorphic things as different, then I have no clue what ALL even means.

CunningGabe commented 1 year ago

I think the point is that if we fix a concrete representation of a group, then several different generating sets might yield isomorphic string C-groups (not just abstractly, but in the generators-to-generators way).

For example, if G = <x, y | x^2 = y^2 = (xy)^5 = 1>, then a naive algorithm is:

  1. Look for all involutions in G.
  2. For each rank r, pick a sequence of r involutions g_1, ..., g_r such that the result is a string C group. But that actually duplicates a lot - we could have g_1 = x and g_2 = y, or we could have g_1 = xyx and g_2 = y, and these actually yield isomorphic string C-groups.

Some people are interested in things like "how many ways are there to pick a set of generators", but I think that's not our goal at the moment.

SupposeNot commented 1 year ago

The good news is that the "up to isomorphism" approach is the one that Hartley documented nicely, and from who's code I can probably adapt a number of good ideas and labor saving steps.