Study on Application of Lagrange’S Theorem In Cosets

A coset is what we get when we take a subgroup and shift it (either on the left or on the right). The best way to think about cosets is that they are shifted subgroups, or translated subgroups. Note g lies in both gH and Hg, since g = ge = eg. Typically gH 6= Hg. When G is abelian, though, left and right cosets of a subgroup by a common element are the same thing. When an abelian group operation is written additively, an H-coset should be written as g + H, which is the same as H + g. Example 1.2. In the additive group Z, with subgroup mZ, the mZ-coset of a is a + mZ. This is just a congruence class modulo m. Example 1.3. In the group R_, with subgroup H = f_1g, the H-coset of x is xH = fx;�xg. This is \x up to sign." Example 1.4. When G = S3, and H = f(1); (12)g, the table below lists the left H-cosets and right H-cosets of every element of the group. Compute a few of them for non-identity elements to satisfy yourself that you understand how they are found. Notice first of all that cosets are usually not subgroups (some do not even contain the identity). Also, since (13)H 6= H(13), a particular element can have di_erent left and right H-cosets. Since (13)H = (123)H, di_erent elements can have the same left H-coset. (You have already seen this happen with congruences: 14 + 3Z = 2 + 3Z, since 14 _ 2 mod 3.)

We will generally focus our attention on left cosets of a subgroup. Proofs of the corresponding properties of right cosets will be completely analogous, and can be worked out by the interested reader. Since g = ge lies in gH, every element of G lies in some left H-coset, namely the left coset de_ned by the element itself. (Take a look at Example 1.4, where (13) lies in (13)H.) Similarly, g 2 Hg since g = eg. A subgroup is always a left and a right coset of itself: H = eH = He. (This is saying nothing other than the obvious fact that if we multiply all elements of a subgroup by the identity, on either the left or the right, we get nothing new.) What is more important to recognize is that we can have gH = H (or Hg = H) even when g is not the identity. For instance, in the additive group Z, 10 + 5Z = 5Z. All this is saying is that if we shift the multiples of 5 by 10, we get back the multiples of 5. Isn't that obvious? In fact, the only way we can have a + 5Z = 5Z is if a is a multiple of 5, i.e., if a 2 5Z. For a subgroup H of a group G, and g 2 G, when does gH equals H? Theorem 4.1. For g 2 G, gH = H if and only if g 2 H. Now we need to show that if g 2 H, then gH H. We prove gH = H by showing each is a subset of the other. Since g 2 H, gh 2 H for any h 2 H, so gH € H. To see H € gH, note h = g(g€ 1h) and that g €1h is in H (since g€1 2 H). Joseph-Louis Lagrange (1736{1813), born in Turin, Italy, was of French and Italian descent. His talent for mathematics became apparent at an early age. Leonhard Euler recognized Lagrange's abilities when Lagrange, who was only 19, communicated to Euler some work that he had done in the calculus of variations. That year he was also named a professor at the Royal Artillery School in Turin. At the age of 23 he joined the Berlin Academy. Frederick the Great had written to Lagrange proclaiming that the \greatest king in Europe" should have the \greatest mathematician in Europe" at his court. For 20 years Lagrange held the position vacated by his mentor, Euler. His works include contributions to number theory, group theory, physics and mechanics, the calculus of variations, the theory of equations, and deferential equations. Along with Laplace and Lavoisier, Lagrange was one of the people responsible for designing the metric system. During his life Lagrange profoundly incensed the development of mathematics, leaving much to the next generation of mathematicians in the form of examples and new problems to be solved.

In ancient Greece, three classic problems were posed. These problems are geometric in nature and involve straightedge-and-compass constructions from what is now high school geometry; that is, we are allowed to use only a straightedge and compass to solve them. The problems can be stated as follows. 1. Given an arbitrary angle, can one trisect the angle into three equal sub-angles using only a straightedge and compass? 2. Given an arbitrary circle, can one construct a square with the same area using only a straightedge and compass? 3. Given a cube, can one construct the edge of another cube having twice the volume of the original? Again, we are only allowed to use a straightedge and compass to do the construction. After puzzling mathematicians for over two thousand years, each of these constructions was finally shown to be impossible. We will use the theory of fields to provide a proof that the solutions do not exist. It is quite remarkable that the long-sought solution to each of these three geometric problems came from abstract algebra. nature of these problems in a bit more The index and Lagrange's theorem For any integer m 6= 0, the number of cosets of mZ in Z is ImI. This gives us an interesting way to think about the meaning of ImI, other than its definition as \m made positive." Passing from Z to other groups, counting the number of cosets of a subgroup gives a useful numerical invariant. De_nition 5.1. Let H be a subgroup of a group G. The index of H in G is the number of left cosets of H in G. This number, which is a positive integer or 1, is denoted [G : H]. Concretely, the index of a subgroup tells us how many times we have to translate the subgroup around (on the left) to cover the whole group. Example 5.2. Since H = {(1); (12)} has three left cosets in S3, by Example 4.4, [S3 : H] = 3. Example 5.3. The subgroup H = {1; s} of D4 has four left cosets: H; rH = {r; rs}; r2H = {r2; r2s}; r3H = {r3; r3s}: The index of H in D4 is 4. Example 5.4. For a positive integer m, [Z : mZ] = m, since 0; 1; : : : ;m 1 are a complete set of coset representatives of mZ in Z. Example 5.5. What is the index of 15Z inside 3Z? (Not inside Z, but 3Z.) Modulo 15, a multiple of 3 is congruent to 0; 3; 6; 9, or 12. That is, we have the disjoint union 3Z = 15Z [ (3 + 15Z) [ (6 + 15Z) [ (9 + 15Z) [ (12 + 15Z): Thus [3Z : 15Z] = 5.

Lagrange's Theorem, one of the most important results in finite group theory, states that the order of a subgroup must divide the order of the group. This theorem provides a powerful tool for analyzing finite groups; it gives us an idea of exactly what type of subgroups we might expect a finite group to possess. Central to understanding Lagrange’s Theorem is the notion of a coset.

Let G be a group and H a subgroup of G. De_ne a left coset of H with representative g 2 G to be the set gH = fgh : h 2 Hg: Right cosets can be defined similarly by Hg = fhg : h 2 Hg: If left and right cosets coincide or if it is clear from the context to which type of coset that we are referring, we will use the word coset without specifying left or right. Example 1. Let H be the subgroup of Z6 consisting of the elements 0 and 3. The cosets are

0 + H = 3 + H = {0; 3} 1 + H = 4 + H = {1; 4}

2 + H = 5 + H = {2; 5g} We will always write the cosets of subgroups of Z and Zn with the additive notation we have used for cosets here. In a commutative group, left and right cosets are always identical. Example 2. Let H be the subgroup of S3 defined by the permutations f(1); (123); (132)g. The left cosets of H are

(1)H = (123)H = (132)H = {(1); (123); (132)} (12)H = (13)H = (23)H = {(12); (13); (23)}

The right cosets of H are exactly the same as the left cosets:

H(1) = H(123) = H(132) = {(1); (123); (132)} H(12) = H(13) = H(23) = {(12); (13); (23)}

It is not always the case that a left coset is the same as a right coset. Let K be the subgroup of S3 defined by the permutations f(1); (12)g. Then the left cosets of K are

(1)K = (12)K = {(1); (12)} (13)K = (123)K = {(13); (123)}

however, the right cosets of K are

K(1) = K(12) = {(1); (12)} K(13) = K(132) = {(13); (132)} K(23) = K(123) = {(23); (123)}

The following lemma is quite useful when dealing with cosets. (We leave its proof as an exercise.) Lemma 6.1 Let H be a subgroup of a group G and suppose that g1; g2 2 G. The following conditions are equivalent. 1. g1H = g2H; 2. Hg-1 1 = Hg-1 2 ; 3. g1H € g2H; 4. g2 € g1H; 5. g € 1 1 g2 € H.

In all of our examples the cosets of a subgroup H partition the larger group G.

• Alon, Noga; Yuster, Raphael; Zwick, Uri (1995), "Color-coding", Journal of the Association for Computing Machinery 42 (4): 844–856, doi:10.1145/210332.210337, MR 1411787.

• Avann, S. P. (1961), "Metric ternary distributive semi-lattices", Proceedings of the American Mathematical Society (American Mathematical Society) 12 (3): 407–414, doi:10.2307/2034206, JSTOR 2034206, MR 0125807.

• Bandelt, Hans-Jürgen (1984), "Retracts of hypercubes", Journal of Graph Theory 8 (4): 501–510, doi:10.1002/jgt.3190080407, MR 0766499.

• Bandelt, Hans-Jürgen; Chepoi, V. (2008), "Metric graph theory and geometry: a survey", Contemporary Mathematics, to appear.

• Bandelt, Hans-Jürgen; Forster, P.; Sykes, B. C.; Richards, Martin B. (October 1, 1995), "Mitochondrial portraits of human populations using median networks", Genetics 141 (2): 743–753, PMC 1206770, PMID 8647407.

• Bandelt, Hans-Jürgen; Forster, P.; Rohl, Arne (January 1, 1999), "Median-joining networks for inferring intraspecific phylogenies", Molecular Biology and Evolution 16 (1): 37–48, PMID 10331250.

• Bandelt, Hans-Jürgen; Macaulay, Vincent; Richards, Martin B. (2000), "Median networks: speedy construction and greedy reduction, one simulation, and two case studies from human mtDNA", Molecular Phylogenetics and Evolution 16 (1): 8–28, doi:10.1006/mpev.2000.0792, PMID 10877936.

• Barthélémy, Jean-Pierre (1989), "From copair hypergraphs to median graphs with latent vertices", Discrete Mathematics 76 (1): 9–28, doi:10.1016/0012-365X(89)90283-5, MR 1002234.

• Birkhoff, Garrett; Kiss, S. A. (1947), "A ternary operation in distributive lattices", Bulletin of the American Mathematical Society 53 (1): 749–752, doi:10.1090/S0002-9904-1947-08864-9, MR 0021540.

• Buneman, P. (1971), "The recovery of trees from measures of dissimilarity", in Hodson, F. R.; Kendall, D. G.; Tautu, P. T., Mathematics in the Archaeological and Historical Sciences, Edinburgh University Press, pp. 387–395.

• Chepoi, V.; Dragan, F.; Vaxès, Y. (2002), "Center and diameter problems in planar quadrangulations and triangulations", Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 346–355.

• Chepoi, V.; Fanciullini, C.; Vaxès, Y. (2004), "Median problem in some plane triangulations and quadrangulations", Computational Geometry: Theory & Applications 27: 193–210.

• Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing 14: 210–223, doi:10.1137/0214017, MR 0774940.

• Chung, F. R. K.; Graham, R. L.; Saks, M. E. (1987), "Dynamic search in graphs", in Wilf, H., Discrete Algorithms and Complexity (Kyoto, 1986), Perspectives in Computing 15, New York: Academic Press, pp. 351–387, MR 0910939.

Combinatorica 9 (2): 111–132, doi:10.1007/BF02124674.  Day, William H. E.; McMorris, F. R. (2003), Axiomatic Concensus [sic] Theory in Group Choice and Bioinformatics, Society for Industrial and Applied Mathematics, pp. 91–94, ISBN 0-89871-551-2.