June 23, 2012 Leave a comment
First things first, for those of you actually reading on my blog, and not via an RSS feed, you probably noticed I changed the theme. I’m not sure if I’ll stick with it, but for now, I like it.
Now that summer has started, I’ve had time to work on the ever growing list of “Things to do if I had more time.” One project I started a while ago, was KnowMSG: Know More Simple Groups.
For anyone who has taken an introductory algebra course, you are intimately familiar with the problems of the form: “Prove there are no simple groups of order BLANK.” There are a few basic tricks, usually coming from the Sylow theorems, and you learn how to use them. This fall I was assigned to do this for all numbers below 200. Instead of hand-writing all of these proofs, I wrote KnowMSG.
The idea is, you input a number and it either returns a simple group of that order, or returns a proof that no such simple group can exist. Well, that’s overstating it. While it’s true that we have a classification theorem for all finite simple groups, it’s not something I pretend to understand, so I don’t think it’s fair to cite the classification theorem. Instead, KnowMSG tries to find an elementary proof. If it can’t then it cites the classification theorem, Burnside’s theorem, or the Feit-Thompson theorem. I consider any of those cases failures, as their proofs are not “elementary,” for any reasonable definition of the word.
That being said, KnowMSG doesn’t fail too frequently. The smallest number (at time of writing) that it fails on is 1008. The smallest odd number it fails on is 4455 (odd numbers are easier, it seems). It never fails on anything which is 2 modulo 4. On numbers less than 1,000,000, it only fails on 8493 cases. I set a goal, which is now accomplished, to solve every group less than 1000. The goal of solving all sizes via elementary means is surely unattainable; if I did, I would have an elementary proof of the classification theorem.
Here you can find a list of all the numbers below 1,000,000 which I do not have satisfactory proofs for. If you find a neat technique that can solve a few cases, let me know, and I’ll implement it.
People have been asking how KnowMSG works, so let me give you a basic overview. You can also find all the code hosted on github, but I can assure you it is messy, and not well-commented. If you’re feeling ambitious, have at it.
Say you plug in . First, it’s easiest to check if there is a simple group of that order. It literally has the classification theorem coded into it, so it can check relatively quickly if there is a simple group of that order.
If there aren’t any, the idea is to first write down, for each prime dividing , the possible number of Sylow -subgroups. By the Sylow theorems, these numbers must be 1 modulo , and must be a factor of . Sometimes, for some prime, 1 is the only option, and we can use this to deduce the existence of a normal subgroup. Otherwise, we proceed by contradiction.
If there were no normal subgroups, then 1 could not be an option for any prime. Moreover, we can knock out some of the smaller options, because if there are Sylow -subgroups, then our group acts on them by conjugation giving us a map
Since the kernel of this map is a normal subgroup, it must be trivial or injective. By construction, it isn’t trivial, so it must be injective. Sometimes this gives us a contradiction, say, if (the size of ) does not divide .
Now it gets complicated. There are approximately 10 tricks KnowMSG knows, and for each possibility for , for each prime , it tries to apply each of the tricks to arrive at a contradiction for that possibility. If it can get a contradiction for each for a given prime, it prints out a case-by-case proof. Otherwise it just dumps to the screen any information it could deduce, along with a notice that it doesn’t have a proof.
There are three numbers below 1000, that I needed to get to reach my goal, for which none of this worked. They are 720, 756, and 840. These cases are somehow harder than the rest. Here I feel like I cheated slightly. KnowMSG simply checks if you input one of those numbers, and spits out a memorized proof. It’s not really doing any thinking.
Anyway, that’s the basic idea. If you want to know more about how these tricks work, you can
- Look at the file technique.js on github,
- Try plugging in these numbers. I believe all of the cases are covered by these examples: 2, 27, 90, 180, 240, 252, 540, 576, 720, 756, 840, 1716, and 808017424794512875886459904961710757005754368000000000