• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

How much group theory do I need to know for twisty puzzles?

qwr

Member
Joined
Jul 24, 2019
Messages
3,371
YouTube
Visit Channel
Every so often I think about learning more group theory to understand the cube. I took one semester of undergrad algebra but I kinda failed it and forgot everything. So how much background do I need before I can understand enough to use GAP to prove things? I guess it's all finite group stuff and other algebra like rings and fields won't help. I tried reading some book I found online about group theory and rubik's cubes but it didn't go in depth enough to really teach me anything besides basic definitions.
 

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
I personally don't really know much group theory beyond whatever I learnt in my first class of undergrad algebra either… although I kinda struggled with that and that led me to wiki-walking the Groupprops wiki and ProofWiki a bit, and maybe I'm lumping whatever I learnt during the wikiwalks into the class itself.

Off the top of my head, these are the useful things for analysing twisty puzzles (and also some puzzles of the non-twisty kind):

- Fundamentals. You should be familiar with things like functions, subsets, equivalence relations, the notion of well-definedness.

- Combinatorics. Important, but thankfully you don't need anything advanced. Just think of those probability questions where you have to add or multiply a bunch of stuff together to get the answer. The most advanced thing that's still useful is the inclusion-exclusion principle, and even then, you mostly don't need to touch inclusion-exclusion if you're looking at the group theory side of things.

- Linear algebra, especially over number systems other than the real/complex numbers. Real linear algebra and complex linear algebra aren't that useful in a very discrete setting, but it's fairly common to have to deal with linear algebra mod 2 or mod 3 when it comes to twisty puzzles. Again, nothing advanced needed—knowing how to solve equations and multiply matrices is enough.

- Basic number theory. What prime numbers are, unique factorisation, that kind of stuff. Nothing more than what would be covered in an undergrad abstract algebra class or its prerequisites.

- Group theory itself. Definitions of group, subgroup, coset, normal subgroup, centre, homomorphism, isomorphism, quotient group, direct product, semidirect product, abelian group, cyclic group, symmetric/alternating groups, special/general linear groups (and projective, affine variants thereof), group action, types of group action (faithful, free, transitive, etc.), orbit, stabiliser, free group, word metric. How group actions induce subgroups of symmetric groups. Sylow theorems are good to know (Sylow subgroups always exist; all Sylow p-subgroups are conjugate; nobody can remember the others) but mostly not very important.

- Other objects studied in abstract algebra. Not so much to analyse with group theory, but more to know the terminology and also serve as examples of things that are not groups. For example, the sets of legal move sequences on bandaged puzzles (including jumbling ones) behave like groupoids.

Might extend this list later on if I think of anything else to add.
 

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
I hope that @cuBerBruce, @rokicki , @Ben Whitmore, @Lucas Garron, @ch_ts, and others will also add some pointers for using GAP.

I have heard of SageMath from the college textbook, Permutation Puzzles: A Mathematical Perspective. (The author has an appendix introducing you to SageMath with examples. He of course uses it throughout the text as well.)

Also, apparently you can convert models of groups constructed in GAP to SageMath. GAP may be the most commonly used because it's the fastest at these type of computations. But I honestly don't know (and have never cared) about Group theory that much to know if SageMath can offer what you are looking for. (So that's why I gave the above users a poke so that you get more informed answers! I have used Mathematica for a number of things, but most of the code I used was my own -- not built in functions -- and it wasn't your typical group theory software functions.)
________________
For all those viewing thread that just want to get started learning the basics (and a little intermediate things), check out the links I ("cmowla") provided in this Reddit topic. (Primarily videos, but some PDFs.)
 
  • Like
Reactions: qwr

qwr

Member
Joined
Jul 24, 2019
Messages
3,371
YouTube
Visit Channel
I personally don't really know much group theory beyond whatever I learnt in my first class of undergrad algebra either… although I kinda struggled with that and that led me to wiki-walking the Groupprops wiki and ProofWiki a bit, and maybe I'm lumping whatever I learnt during the wikiwalks into the class itself.

Off the top of my head, these are the useful things for analysing twisty puzzles (and also some puzzles of the non-twisty kind):

- Fundamentals. You should be familiar with things like functions, subsets, equivalence relations, the notion of well-definedness.

- Combinatorics. Important, but thankfully you don't need anything advanced. Just think of those probability questions where you have to add or multiply a bunch of stuff together to get the answer. The most advanced thing that's still useful is the inclusion-exclusion principle, and even then, you mostly don't need to touch inclusion-exclusion if you're looking at the group theory side of things.

- Linear algebra, especially over number systems other than the real/complex numbers. Real linear algebra and complex linear algebra aren't that useful in a very discrete setting, but it's fairly common to have to deal with linear algebra mod 2 or mod 3 when it comes to twisty puzzles. Again, nothing advanced needed—knowing how to solve equations and multiply matrices is enough.

- Basic number theory. What prime numbers are, unique factorisation, that kind of stuff. Nothing more than what would be covered in an undergrad abstract algebra class or its prerequisites.

- Group theory itself. Definitions of group, subgroup, coset, normal subgroup, centre, homomorphism, isomorphism, quotient group, direct product, semidirect product, abelian group, cyclic group, symmetric/alternating groups, special/general linear groups (and projective, affine variants thereof), group action, types of group action (faithful, free, transitive, etc.), orbit, stabiliser, free group, word metric. How group actions induce subgroups of symmetric groups. Sylow theorems are good to know (Sylow subgroups always exist; all Sylow p-subgroups are conjugate; nobody can remember the others) but mostly not very important.

- Other objects studied in abstract algebra. Not so much to analyse with group theory, but more to know the terminology and also serve as examples of things that are not groups. For example, the sets of legal move sequences on bandaged puzzles (including jumbling ones) behave like groupoids.

Might extend this list later on if I think of anything else to add.

I know pretty much everything here except the group action kind of stuff which I forgot. My class never got to different types of group action. I've done quite a few Project Euler problems which are more combinatorics/number theory heavy than any other area.


I hope that @cuBerBruce, @rokicki , @Ben Whitmore, @Lucas Garron, @ch_ts, and others will also add some pointers for using GAP.

I have heard of SageMath from the college textbook, Permutation Puzzles: A Mathematical Perspective. (The author has an appendix introducing you to SageMath with examples. He of course uses it throughout the text as well.)

Also, apparently you can convert models of groups constructed in GAP to SageMath. GAP may be the most commonly used because it's the fastest at these type of computations. But I honestly don't know (and have never cared) about Group theory that much to know if SageMath can offer what you are looking for. (So that's why I gave the above users a poke so that you get more informed answers! I have used Mathematica for a number of things, but most of the code I used was my own -- not built in functions -- and it wasn't your typical group theory software functions.)
________________
For all those viewing thread that just want to get started learning the basics (and a little intermediate things), check out the links I ("cmowla") provided in this Reddit topic. (Primarily videos, but some PDFs.)

I'll be sure to check out the textbook you linked. Iirc SageMath is in python and can do a lot more than just group theory, like dealing with computations mod p.
 
Top