[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. The odd get even

Let G be a subgroup of Sn. Show that if G contains an odd permutation, then |G| is even.

1.1. Solution

Let x∈G be odd, let H be the set { y ∈ G | y is even }, and let Hx be the coset { yx | x ∈ H }. Then there is a one-to-one correspondence between H and Hx, so |H| = |Hx|. Note that every permutation in Hx is odd. The converse also holds: if z is an odd permutation in G, then zx-1 is even and thus in H, and so zx-1x = z is in Hx. It follows that every permutation in G is in exactly one of H and Hx, so |G| = |H| + |Hx| = 2|H| is even.

2. Damaging a group

Let G be a group. Consider the algebra G* obtained by replacing the multiplication operation in G with x*y = xy-1 and G** obtained by replacing the multiplication operator in G with x**y = x-1y-1 (where in each case multiplication and inverses are done using the original operation in G).

  1. Prove or disprove: For any group G, G* is a semigroup.

  2. Prove or disprove: For any group G, G** is a semigroup.

2.1. Solution

Neither is a semigroup, because neither satisfies associativity:

  1. (x*y)*z = (x*y)z-1 = xy-1z-1 but x*(y*z) = x*(yz-1) = x(yz-1)-1 = xzy-1.

  2. (x**y)**z = (x**y)-1z-1 = (x-1y-1)-1z-1 = yxz-1 but x**(y**z) = x-1(y**z)-1 = x-1(y-1z-1)-1 = x-1zy.

3. Whirling polygons

Show that Dn has a subgroup of size m if and only if m divides 2n.

3.1. Solution

The only if part is just Lagrange's theorem.

For the if part, first recall that Dn is generated by a flip f and a rotation r, with rn = f2 = e and fr = r-1f. So in particular the subgroup generated by r is isomorphic to ℤn. It follows that Dn has a subgroup (generated by rn/m) for each m that divides n.

Suppose now that m does not divide n but does divide 2n. Then m = 2k where k∣n (we can only fit one extra 2 in 2n). Consider the subgroup of Dn generated by f and rn/k; this has exactly k elements of the form ran/k and k of the form ran/kf, for a total of 2k=m elements.

4. Cocosets

Given a group G with subgroups H and K, define HK = { hk | h ∈ H, k ∈ K }. Show that HK is a subgroup of G if and only if HK = KH.

4.1. Solution

Let's do the if direction first. Let hk ∈ HK and consider (hk)-1 = k-1h-1 ∈ KH = HK. Now consider rs ∈ HK; we wish to show hkrs is also in HK. But since kr ∈ KH = HK there exists some uv ∈ HK such that kr = uv. Rewrite hkrs = huvs = (hu)(vs) ∈ HK.

For only if, observe that if HK is a subgroup, then for each x ∈ G we have x ∈ HK if and only if x-1 ∈ HK (the only if part is just closure of H under inverses applied to (x-1)-1 = x). But then HK = { hk | h ∈ H, k ∈ K } = { (hk)-1 | h ∈ H, k ∈ K } = { k-1h-1 | h ∈ H, k ∈ K } = { kh | k ∈ K, h ∈ H } = KH.

5. Rational quotients

Let ℚ be the additive group of the rationals, i.e. the group whose elements are numbers of the form n/m for integers n and m ≠ 0 and whose operation is the usual addition operation for fractions, and let ℤ be the additive group of the integers, which we will treat as equal to the subgroup of the rationals generated by 1 = 1/1. Prove or disprove: ℤ is isomorphic to a subgroup of ℚ/ℤ.

5.1. Solution

Let f:ℤ→ℚ/ℤ be a homomorphism. We will show that f is not injective: there exist n and m in ℤ such that f(n) = f(m). Since any isomorphism between ℤ and a subgroup of ℚ/ℤ would give an injective f, this will show that no such isomorphism exists.

Let f(1) = a/b. Then f(b+1) = (b+1) f(1) = (b+1)(a/b) = a/b + a. But a ∈ ℤ, so a/b + a is in the same coset of ℤ as a/b. It follows that f(1) = f(b+1) and f is not injective.

Comment: The quotient group ℚ/ℤ is generally known as the rationals mod 1, since a natural choice of representatives for the various cosets is the rationals x with 0 ≤ x < 1, and addition yields the remainder after subtracting out any ones. This is similar to the construction of ℤm ≈ ℤ/mℤ.

2014-06-17 11:57