|
| Figure 1: Lattice Diagram for Group of Symmetries of the Square |
"I shall now mention something I obviously do not understand." - Ian Hacking (2014, p. 18)
1.0 Introduction
This has nothing to do with economics. It is my attempt to get my mind around a place where I can get a glimmer of some exciting mathematics being done in my lifetime.
Mathematicians have stated a theorem for classifying finite simple groups. Whether they have proven this theorem is an intriguing question in the philosophy of mathematics.
A finite simple group is a group with a finite number of elements and no proper normal subgroup. This definition contains several technical terms. In this post, I try to explain these terms and the setting of the theorem for classifying simple groups. This preamble raises several questions:
- What is a group? A proper subgroup? A normal subgroup?
- How can a finite, non-simple group be factored into a composition of simple groups?
I try to clarify the answers to these questions by means of a lengthy example. You can probably find this better expressed elsewhere. In working this out, I relied heavily on Fraleigh's textbook, which is the only book in the references that I have read, albeit mostly in the second edition.
2.0 The Group of Symmetries of the Square
A group is a generalization, in some sense, of a multiplication table. Formally, it is a set with a binary operation, in which the binary operation satisfies three axioms. A finite group is a group in which the set contains a finite number of elements.
To illustrate, I consider the set of symmetries of the square (Figure 2). These eight elements of the set are like the numbers along the top and left side of a multiplication table. Each element is an operation that can be performed on a square, leaving the square superimposed on itself. Each operation is described in the right column of Figure 2. The third column provides a picture of the operation. The four vertices of the square are numbered so that one can see the result of the operation. The second column specifies each operation as a permutation of the numbered vertices. The first row in each permutation lists the vertices, while the second row shows which of the original vertices ends up in the place of each vertex. The first column introduces a notation for naming each operation. The remainder of this post is expressed in this notation.
|
| Figure 2: Elements of a Group |
The group operation, *, is function composition. Let a and b be elements of the set {ρ0, ρ1, ρ2, ρ0, μ0, μ1, σ0, σ1}. The product a*b is defined to be the single operation that is equivalent to first performing the operation a on the square and then performing the operation b on the result. (Many textbooks define functional composition from right-to-left, instead.) Table 1 is the multiplication table for this group, under these definitions. For example, rotating a square 90 degrees clockwise twice is equivalent to rotating the square clockwise through 180 degrees. Thus:
ρ1 * ρ1 = ρ2
Table 1: The Group D4
| * | ρ0 | ρ1 | ρ2 | ρ3 | μ0 | μ1 | σ0 | σ1 |
| ρ0 | ρ0 | ρ1 | ρ2 | ρ3 | μ0 | μ1 | σ0 | σ1 |
| ρ1 | ρ1 | ρ2 | ρ3 | ρ0 | σ0 | σ1 | μ1 | μ0 |
| ρ2 | ρ2 | ρ3 | ρ0 | ρ1 | μ1 | μ0 | σ1 | σ0 |
| ρ3 | ρ3 | ρ0 | ρ1 | ρ2 | σ1 | σ0 | μ0 | μ1 |
| μ0 | μ0 | σ1 | μ1 | σ0 | ρ0 | ρ2 | ρ3 | ρ1 |
| μ1 | μ1 | σ0 | μ0 | σ1 | ρ2 | ρ0 | ρ1 | ρ3 |
| σ0 | σ0 | μ0 | σ1 | μ1 | ρ1 | ρ3 | ρ0 | ρ2 |
| σ1 | σ1 | μ1 | σ0 | μ0 | ρ3 | ρ1 | ρ2 | ρ0 |
A group is defined by the following three axioms:
- The binary operation in the group is associative. That is, for all a, b, and c in the group:
(a * b) * c = a * (b * c)
- The group contains an identity element. There exists an element e in the group such that for all a in the group:
e * a = a * e = a
- Every element of the group has an inverse. For all a in the group, there exists an element a-1 in the group such that:
a * a-1 = a-1 * a = e
Associativity is tedious to check for D4. Associativity implies that one can drop parenthesis below. ρ0 is the identity element. Every row and column in the multiplication table for D4 contains ρ0; thus, every element has an inverse.
An Abelian group is one in which the binary operation is commutative. The group of symmetries of the square is not Abelian. For an Abelian group, the multiplication table is symmetric across the principal diagonal; it does not matter to the result in which order one performs the operation for two arguments. The following two equations illustrates that D4 is not Abelian:
μ0*ρ1 = σ1
ρ1*μ0 = σ0
In words, flipping a square around its horizontal axis of symmetry and then rotating it ninety degrees clockwise is not equivalent to rotating it ninety degrees clockwise and then then reflecting it across that axis. The result of the first composition of operations is equivalent to reflecting the square across the diagonal axis of symmetry running from the south west to the north east. The second composition of operations is equivalent to flipping the square across the other diagonal.
One can also set up equations in a group, for example:
ρ1*ρ2*x = μ0
Then x must be σ0. Solving a Rubik's cube is analogous to solving such an equation.
3.0 Proper and Improper Subgroups
Some rows and columns in Table 1 can stand alone as a group. The entries in these restricted row and columns all appear as headings in the rows and columns. These entries form a subgroup of the original group. One-fourth of the table in the upper left of Table 1 provides an example. {ρ0, ρ1, ρ2, ρ3} is a subgroup of D4 (Table 2).
Table 2: A Subgroup of D4 with Four Elements
| * | ρ0 | ρ1 | ρ2 | ρ3 |
| ρ0 | ρ0 | ρ1 | ρ2 | ρ3 |
| ρ1 | ρ1 | ρ2 | ρ3 | ρ0 |
| ρ2 | ρ2 | ρ3 | ρ0 | ρ1 |
| ρ3 | ρ3 | ρ0 | ρ1 | ρ2 |
The group D4 has ten subgroups, as shown in the Lattice Diagram in Figure 1 above.
Subgroups have been defined such that, for any group G, the group G is a subgroup of itself. Another trivial case, the one-element group consisting of the identity element, also provides a subgroup of G. These two subgroups are known as improper subgroups. All other subgroups are proper subgroups.
One can make a couple of observations about subgroups. The binary operation in the group is the same as the binary operation in the subgroup. The property of associativity carries over from the group to the subgroup. Since a subgroup is a group, it must contain an identity element. And that identity element must also be the identity element for the group containing the subgroup. Thus, every subgroup of D4 contains ρ0. Likewise, for every element of a subgroup, the subgroup must also contain its inverse. Finally, the number of elements in a subgroup must evenly divide the number of elements in the group.
I have shown above how the eight elements of D4 can be defined in terms of permutations. As a matter of fact, the set of permutations of (1, 2, ..., n) form a group under the operation of function composition. This permutation group is designated as Sn, and it contains n! elements. Thus, S4 contains 24 (= 4x3x2x1) elements. Not only can one find all the subgroups of D4, one can extend the group such that D4 is a subgroup of that extended group.
4.0 Isomorphic Groups
In a group, the order of rows and columns in the multiplication table are of no matter. Likewise, the names of the elements are irrelevant to the structure of the group. Two groups are isomorphic if the multiplication table for one group can be mapped into the multiplication table for another group by reordering and renaming the elements of, say, the first group. As an example, consider the groups {ρ0, ρ2, μ0, μ1} and {ρ0, ρ2, σ0, σ1}. They each have the same number of elements, which is necessary for an isomorphism. Table 3 defines the group operation for the first group. Suppose that, in Table 3, μ0 is renamed σ0, and μ1 is renamed σ1 throughout. The resulting table will match the operation for the second group. Thus, the two groups are isomorphic.
Table 3: The Group {ρ0, ρ2, μ0, μ1}
| * | ρ0 | ρ2 | μ0 | μ1 |
| ρ0 | ρ0 | ρ2 | μ0 | μ1 |
| ρ2 | ρ2 | ρ0 | μ1 | μ0 |
| μ0 | μ0 | μ1 | ρ0 | ρ2 |
| μ1 | μ1 | μ0 | ρ2 | ρ0 |
The groups in Tables 2 and 3 are NOT isomorphic. They each contain four elements. Each element, however, in the group in Table 3 is its own inverse. This is an algebraic property, preserved no matter how the elements of the group are renamed. And the group in Table 2 does not have this property. As a matter of fact, only two groups containing four elements exist, up to an isomorphism. In other words, any group with four elements is isomorphic to either the group in Table 2 or to the group in Table 3.
Furthermore, only one group, up to isomorphism, contains two elements. Its operation is defined by Table 4. All the subgroups of D4 containing two elements are isomorphic to this group and, ipso facto, to each other. The text colors of the subgroups in the lattice diagram (Figure 1) express these isomorphisms.
Table 4: The Unique Group (Up To Isomorphism) With Two Elements
| * | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 0 |
5.0 Normal Subgroups, Factor Groups, and Homomorphisms
Certain additional patterns are apparent in Table 1. I have already pointed out that the first four rows and columns constitute the subgroup with the operation shown in Table 2. Notice that none of the entries in the last four columns for the first four rows are in this subgroup. Likewise, none of the entries in the first four columns for the last four rows are in this subgroup. On the other hand, the entries in the remaining rows and columns in the lower right are all in this subgroup. Can you see that these observations reveal the pattern expressed in Table 4? Mathematicians express this by saying that the factor group D4/{ρ0, ρ1, ρ2, ρ3} is isomorphic to the group with two elements.
A subgroup is normal if it can be used to divide up the rows and columns in the multiplication table for the group like this. For another example, consider the subgroup {ρ0, ρ2}. Table 5 shows a reordering of the rows and columns in Table 1 to facilitate the calculation of the factor group for this subgroup. Consider dividing this grid up into 16 blocks of two rows and two columns each. Each block will contain two elements of the group D4, and which element is paired with each element does not vary among these blocks.
Table 5: The Group D4 Reordered
| * | ρ0 | ρ2 | ρ1 | ρ3 | μ0 | μ1 | σ0 | σ1 |
| ρ0 | ρ0 | ρ2 | ρ1 | ρ3 | μ0 | μ1 | σ0 | σ1 |
| ρ2 | ρ2 | ρ0 | ρ3 | ρ1 | μ1 | μ0 | σ1 | σ0 |
| ρ1 | ρ1 | ρ3 | ρ2 | ρ0 | σ0 | σ1 | μ1 | μ0 |
| ρ3 | ρ3 | ρ1 | ρ0 | ρ2 | σ1 | σ0 | μ0 | μ1 |
| μ0 | μ0 | μ1 | σ1 | σ0 | ρ0 | ρ2 | ρ3 | ρ1 |
| μ1 | μ1 | μ0 | σ0 | σ1 | ρ2 | ρ0 | ρ1 | ρ3 |
| σ0 | σ0 | σ1 | μ0 | μ1 | ρ1 | ρ3 | ρ0 | ρ2 |
| σ1 | σ1 | σ0 | μ1 | μ0 | ρ3 | ρ1 | ρ2 | ρ0 |
These observations can be formalized by the function defined in Table 6. For an element a of D4, let f(a) denote the map defined in Table 6. To find the value of this function, locate a in the first column. Whether this value is 0, 1, 2, or 3 is determined by the corresponding entry in the second column. For all a and b in D4:
f(a * b) = f(a) o f(b)
A map from one group to another with this property is a homomorphism. An isomorphism is a homomorphism, but a homomorphism is a more general concept. Homomorphisms do not need to leave the number of elements in the group invariant.
Table 6: A Homomorphism from D4 to {0, 1, 2, 3}
| Elements of D4 | Image |
| ρ0, ρ2 | 0 |
| ρ1, ρ3 | 1 |
| μ0, μ1 | 2 |
| σ0, σ1 | 3 |
The factor group D4/{ρ0, ρ2} is easily calculated. Replace each element of D4 in Table 5 by its image under the homomorphism in Table 6. Collapse each pair of rows and columns. One ends up with Table 7, where I have renamed the group operation, as above. The factor group D4/{ρ0, ρ2} is isomorphic to the group with four elements with the operation shown in Table 3 above. The number of elements in a factor group is the quotient of the number of elements in the original group and the number of elements in the subgroup used to form the factor group.
Table 7: The Factor Group D4/{ρ0, ρ2}
| o | 0 | 1 | 2 | 3 |
| 0 | 0 | 1 | 2 | 3 |
| 1 | 1 | 0 | 3 | 2 |
| 2 | 2 | 3 | 0 | 1 |
| 3 | 3 | 2 | 1 | 0 |
The two improper subgroups for any group are normal and yield trivial factor groups. The factor group D4/D4 is isomorphic to the one-element group whose only member is the identity element. The factor group D4/{ρ0} is isomorphic to D4. The factor groups for improper subgroups provide no information about the structure of a group.
6.0 A Subgroup that is Not Normal
Not all subgroups are normal. The subgroup {ρ0, μ0}, for example, is not a normal subgroup of D4. Table 8 proposes a map from the elements of the group to the first four natural numbers. And Table 9 illustrates another reordering of the rows and columns in Table 1, with the entries replaced by the natural numbers to which they map. If one confines oneself to the first two columns, each pair of rows could be collapsed into one, with the label from the row taken from the map. But this process breaks down for the next two and the last two columns.
Table 8: A Map from D4 to {0, 1, 2, 3} that is Not a Homomorphism
| Elements of D4 | Image |
| ρ0, μ0 | 0 |
| ρ1, σ0 | 1 |
| ρ2, μ1 | 2 |
| ρ3, σ1 | 3 |
Table 9: Another Reodering of The Group D4
| * | ρ0 | μ0 | ρ1 | σ0 | ρ2 | μ1 | ρ3 | σ1 |
| ρ0 | 0 | 0 | 1 | 1 | 2 | 2 | 3 | 3 |
| μ0 | 0 | 0 | 3 | 3 | 2 | 2 | 1 | 1 |
| ρ1 | 1 | 1 | 2 | 2 | 3 | 3 | 0 | 0 |
| σ0 | 1 | 1 | 0 | 0 | 3 | 3 | 2 | 2 |
| ρ2 | 2 | 2 | 3 | 3 | 0 | 0 | 1 | 1 |
| μ1 | 2 | 2 | 1 | 1 | 0 | 0 | 3 | 3 |
| ρ3 | 3 | 3 | 0 | 0 | 1 | 1 | 2 | 2 |
| σ1 | 3 | 3 | 2 | 2 | 1 | 1 | 0 | 0 |
Suppose a subgroup contains n elements. To determine if the subgroup is normal, it is sufficient to examine the first n rows and the first n columns in the reordered table. This capability follows from a theorem about what are known as left and right cosets for a subgroup.
The permuation group S4 provides another example of a subgroup that is not normal.
By my calculations, D4 is NOT a normal subgroup of S4.
7.0 The Composition Series of a Group
At this point, I have completed my explanation of the lattice diagram at the top of this post, including circles, text colors, and boxes. I draw from these results to illustrate how a non-simple group, namely D4, can be expressed as a composition of factor groups.
Table 10 lists twelve series of subgroups of the group of symmetries of the square. Each series has the following properties:
- The leftmost group in the series is the one-element group containing the identity element.
- The rightmost group is D4.
- Each group in the series (except D4) is a proper normal subgroup of the group immediately to the right of it in the series.
A series with these properties is known as a subnormal series of the group D4. If every group in the series is also a normal subgroup of D4, the series is a normal series of the group D4. By the last property in the bulleted list, one can calculate a factor group for each pair of immediately successive groups in the series.
Table 10: Twelve Normal and Subnormal Series for D4
Number
Factor Groups | Series | Normal
Series |
| 1 | {ρ0} < D4 | Yes |
| 2 | {ρ0} < {ρ0, ρ1, ρ2, ρ3} < D4 | Yes |
| 2 | {ρ0} < {ρ0, ρ2, μ0, μ1} < D4 | Yes |
| {ρ0} < {ρ0, ρ2, σ0, σ1} < D4 | Yes |
| {ρ0} < {ρ0, ρ2} < D4 | Yes |
| 3 | {ρ0} < {ρ0, ρ2} < {ρ0, ρ1, ρ2, ρ3} < D4 | Yes |
| {ρ0} < {ρ0, ρ2} < {ρ0, ρ2, μ0, μ1} < D4 | Yes |
| {ρ0} < {ρ0, ρ2} < {ρ0, ρ2, σ0, σ1} < D4 | Yes |
| {ρ0} < {ρ0, μ0} < {ρ0, ρ2, μ0, μ1} < D4 | No |
| {ρ0} < {ρ0, μ1} < {ρ0, ρ2, μ0, μ1} < D4 | No |
| {ρ0} < {ρ0, σ0} < {ρ0, ρ2, σ0, σ1} < D4 | No |
| {ρ0} < {ρ0, σ1} < {ρ0, ρ2, σ0, σ1} < D4 | No |
The definition of an isomorphism for a subnormal series builds on the definition of isomorphism for groups. Consider the factor groups arising in each series from successive pairs of subgroups in each series. Two series are isomorphic if they contain the same of number of factor groups, in this sense, and these factor groups are isomorphic. The order in which the factor groups arise can vary among isomorphic subnormal series.
I have collected isomorphic series together, in Table 10, by means of horizontal lines in the first column. The series with one factor group is not isomorphic to any other series. The first series shown with two factor groups is not isomorphic to the other three series with two factor groups. And those three series are isomorphic to one another. All of the series with three factor groups are isomorphic to one another.
The series with three factor groups have another property. All factor groups in these series with three factor groups are simple groups. That is, they contain no proper normal subgroups. A subnormal series of a group in which all factor groups formed by the series are simple is known as a composition series. By the Jordan-Hölder Theorem, all compositions series for a group are isomorphic series. This theorem justifies one in speaking of THE composition series for a group. Finding the factor groups in a the composition series for a group is somewhat analogous to factoring a natural number. Note that D4 contains eight elements and each of the three factor groups in the composition series contain two elements. Furthermore,
8 = 23
For a natural number, the prime factors can be combined to yield the original number. Here the analogy apparently breaks down. The factor groups in a composition series for a group constrain the structure of the group, but two non-isomorphic groups can have the same composition series. But still, mathematicians have solved various problems in group theory for finite non-simple groups by use of the classification of finite simple groups.
Composition series apparently have an application in solving polynomial equations. The composition series for the permutation group S5 contains a factor group that is non-Abelian. This is connected with the insolvability of the quintic. There are formulas for zeros for cubic and fourth order polynomial, analogous to the quadratic formula. But there is no such formulas for poynomials of the fifth degree and higher.
8.0 Classification of Finite Simple Groups
At this point, I have explained how finite simple groups arise as factor groups for the composition series of any finite group. I hope that this gives some hint of why the following theorem is of interest.
Theorem: Each finite simple group is one of the following, up to an isomorphism:
- A group of prime order.
- An alternating group.
- A Lie group.
- One of 26 sporadic groups not otherwise classified.
I am aware that this this theorem uses technical terms I still have not explained, including one that I simply do not understand myself.
The sporadic groups are finite simple groups that do not fall into the other categories, although, I gather, some sporadic groups are related to one another.The sporadic group with the largest number of elements is called the Monster group. It has 808,017,424,794,512,875,886,459,904,961,710,757,005,754,368,000,000,000 elements.
9.0 History of the Theorem
In 1972, Daniel Gorenstein proposed that mathematicians could complete a classification of all simple groups. By the early 1980s, mathematicians had stated the theorem and those specialists who had pursued Gorenstein's program believed they had proven it. The proof, however, was scattered among (tens of?) thousands of pages in hundreds(?) of papers in many mathematics journals. No one person had probably ever understood the proof or read it in its entirety.
The proof, however, was discovered even then to be incomplete. Steve Smith and Michael Aschbacher worked on closing this gap, relating to quasithin groups. They succeeded by 2004.
Meanwhile, a number of mathematicians have been trying to simplify the proof and to restate it in one location. The ambition of these mathematicians is to produce a "second generation" proof of only a couple thousand pages.
Has a theorem been proven if only one or two mathematicians have read the proof in its entirety? How about if nobody has, which would have been the case in the 1980s if the proof had indeed been valid? Certainly, the proof of the classification theorem is not surveyable, in Wittgenstein's sense. Do mathematical results need to be established by a social process? If so, how can such social processes be characterized?
Appendix: Terms Defined or Illustrated Above
Abelian group, Associativity, Composition Series, Factor Group, Finite Group, Group, Homomorphism, Identity Element, Improper Subgroup, Inverse, Isomorphic Groups, Isomorphic Subnormal Series, Lattice Diagram, Normal Series, Normal Subgroup, Permutation Group, Proper Subgroup, Subgroup, Subnormal Series.
References
- Michael Aschbacher (2004). The Status of the Classification of the Finite Simple Groups, Notices of the AMS, V. 51, No. 7 (Aug.): pp. 736-740.
- Michael Aschbacher, Richard Lyons, Stephen D. Smith, and Ronald Solomon (2011). The Classification of Finite Simple Groups: Groups of Characteristic 2 Type, American Mathematical Society.
- Nicolas Bourbaki (1943). Elements of Mathematics: Algebra I: Chapters 1-3.
- J. H. Conway and S. P. Norton (1979). Monstrous Moonshine, Bulletin of the London Mathematical Society, V. 11, no. 3: pp. 308-339.
- John B. Fraleigh (2002). A First Course in Abstract Algebra, 7th Edition, Pearson.
- Daniel Gorenstein, Richard Lyons, and Ronald Solomon (1994). The Classification of the Finite Simple Groups, American Mathematical Society.
- Ian Hacking (2014). Why is there Philosophy of Mathematics at all?, Cambridge University Press.
- Daniel Kunkle and Gene Cooperman (2007). Twenty-Six Moves Suffice for Rubik's Cube, ISSAC'07, 29 Jul. - 1 Aug., Waterloo, Canada.
- Tomas Rokicki (2008). Twenty Five Moves Suffice for Rubik's Cube.
Posts
