Inverse problem to Frobenius’ theorem

10/03/2013

Denote by L_n(G) the number of elements in G satisfying x^n = 1. Frobenius’ theorem states that if n is a divisor of |G|, then L_n(G) is a multiple of n.

In the article On an inverse Problem to Frobenius’ theorem (2011, Springerlink) Wei Meng and Jiangtao Shi propose the following problem.

Let k be a positive integer. Classify all groups G with the property that L_n(G) \leq kn for every divisor n of |G|.

Denote by k(G) the largest positive integer k such that L_n(G) \leq kn for all divisors n of |G|. It is a standard result that k(G) = 1 if and only if G is cyclic. Wei Meng and Jiangtao Shi have classified groups with k(G) = 2 and those with k(G) = 3 (with Kelin Chen).

Here are some of my thoughts about the general problem. Let G be a group and suppose that L_e(G) \leq ke for all e | |G|. Let p be a prime divisor of |G| and let P be a Sylow p-subgroup of G (of order p^n). Then

1) If k < p, then P is normal and cyclic.
2) If k < p^2, then P is normal or P is cyclic.
3) If k < p^t for t > 1, then P is normal or exp(P) \geq p^{n-t+2}
4) If k < 2p-1, then P is normal or else P is cyclic and n_p(G) = p+1.

Denote by n_p(G) the number of Sylow p-subgroups of G. The facts above follow from a theorem of G. A. Miller which states that if n_p(G) = p+1, then L_{p^n}(G) = p^{n+1} and if n_p(G) > p+1, then L_{p^n}(G) \geq (2p-1)p^n.

Applying this we see that when L_e(G) \leq 3e for all e | |G|, every Sylow subgroup of G is cyclic or normal. Furthermore, any Sylow p-subgroup P is central if p > 5. To see this, note that P is centralized by q-sylows for q \geq 5 since they are normal. The subgroup P is also centralized by q-sylows for q = 2, 3 since n_q(G) < p and the automorphism group of cyclic group of order q^k has order coprime to p. Hence by Burnside's normal complement theorem G = T \times M, where M is cyclic and coprime to 2, 3 and 5, reducing the classification of such G to groups with order of the form 2^a 3^b 5^c.

A good starting point for classifying groups with L_e(G) \leq 4e for all e | |G| might be to show that G = T \times M, where M is cyclic and coprime to primes that are small enough. However, it seems difficult to find a good upper bound for the number of Sylow 2-subgroups in this case. Applying 1), 2), 3), 4) or Miller's theorem no longer works here, so improving Miller's result is one possibility. It might be true that n_2(G) \leq 9. This is just a guess I made by looking at groups of order \leq 1000 and values of L_{2^n}(G) when n_2(G) \geq 11.

We would also need an upper bound for the size of primes dividing the order of the automorphism group of a 2-sylow Q. By 3), this Q would be a 2-group of order 2^n with a cyclic subgroup of order 2^{n-1}. I believe these are classified, so it would be a matter of computing the automorphism groups and thus giving an upper bound for the size of primes dividing |Aut(Q)|. Then 2-sylows would centralize any p-sylow for p greater than any prime divisor of [G : C_G(Q)] = [G : N_G(Q)][N_G(Q) : C_G(Q)] = n_2(G) [N_G(Q) : C_G(Q)].

Intersections of Sylow subgroups

07/11/2012

It would be easy to count the number of elements in p-Sylow subgroups if they would always intersect trivially. However, this is not usually the case. For example, in S_4 you can find two different Sylow subgroups that have nontrivial intersection. The intersections don’t always have the same size either, as the group S_3 \times S_3 illustrates. Given a group G with Sylow p-subgroups of order p^n, can we say anything about the intersections? The question is vague, but we can answer “nope, not without more information” as follows:

Let p be a prime and n \geq 1 integer. Then there exists a group G with p-Sylow subgroups of size p^n such that: for any 0 \leq i \leq n, we can find a pair (P, Q) of p-Sylow subgroups of G with |P \cap Q| = p^i.

We construct the group as a generalization of the example S_3 \times S_3 as follows. First, let p < q be primes such that q > n and q \equiv 1 \mod{p}. The existence of such q is guaranteed by Dirichlet’s theorem. Unfortunately, this is a very non-trivial result from number theory. Some special cases such as p = 2 and p = 3 have elementary proofs though (you can adapt Euclid’s proof of the fact that there are infinitely many primes).

Now let T be the nonabelian group of order pq, which exists since q \equiv 1 \mod{p}. Define the group G as the direct product G = T \times T \times \ldots \times T, where T appears n times in the product. A Sylow subgroup of G then has order p^n. Now there are q different p-Sylow subgroups in T, so let P_1, P_2, \ldots, P_n, P be distinct Sylow subgroups of T. Define

Q_0 = P \times P \times P \times \ldots \times P
Q_1 = P_1 \times P \times P \times \ldots \times P
Q_2 = P_1 \times P_2 \times P \times \ldots \times P
Q_3 = P_1 \times P_2 \times P_3 \times P \times \ldots \times P

\ldots

Q_{n-1} = P_1 \times P_2 \times P_3 \times \ldots \times P_{n-1} \times P_{n-1}
Q_n = P_1 \times P_2 \times P_3 \times \ldots P_n

Then the Q_i are p-Sylow subgroups of G, and |Q_n \cap Q_i| = p^i for all 0 \leq i \leq n.

Hence in G pairs of p-Sylow subgroups can have all possible orders.

There is something we can say about the number of elements in Sylow p-subgroups if we know the number of subgroups. First, if there is only only p-Sylow subgroup, say of order p^n, then obviously there are only p^{n} elements. If there are several p-Sylow subgroups, by Sylow’s theorem there are at least p+1. It can be shown that if there are p+1 different p-Sylow subgroups, then there are exactly p^{n+1} elements in the subgroups. Furthermore, if there are more than p+1 different p-Sylow subgroups, then there are more than p^{n+1} elements in the subgroups. I think this result is due to G. A. Miller.

Finite groups of order p^n q are solvable

31/10/2012

Suppose p and q are primes. Then according to Burnside’s theorem every group of order p^n q^m is solvable. We prove the special case m = 1 here. The proof is very old, going back at least to the 1916 book Theory and Applications of Finite Groups by G. A. Miller, H. F. Blichfeldt and L. E. Dickson (Chapter VIII, §73, pg. 185).

Theorem: Every group of order p^n q is solvable.

We argue by induction. The case n = 0 holds because groups of prime order are cyclic. Suppose then that the claim has been established for < n, and let G be a group of order p^n q. It is enough to show that G has a normal subgroup N with N and G/N solvable, and hence by induction it suffices to find a nontrivial proper normal subgroup of G. If G has only one p-Sylow subgroup, the subgroup is normal. Otherwise G has exactly q different p-Sylow subgroups. Let D = P_1 \cap P_2 be the intersection of two different p-Sylow subgroups P_1 and P_2 such that D has the largest possible order. Then since p-groups satisfy the normalizer condition (ie. for proper subgroups, "normalizers grow") we get that

D < N_{P_1}(D) \leq N_G(D)
D < N_{P_2}(D) \leq N_G(D)

Next we show that N_G(D) cannot be a p-group. If this were the case, then it would be contained in some p-Sylow subgroup P_3. Thus P_3 \cap P_1 \geq N_{P_1}(D) > D and by the maximality of D this implies P_3 = P_1. Similarly P_3 \cap P_2 \geq N_{P_2}(D) > D so again by the maximality of D we get P_3 = P_2, giving us the contradiction P_1 = P_2.

Thus by Cauchy’s theorem, there is an element x of order q in N_G(D). Let P be any p-Sylow subgroup of G. Since N_G(P) = P, the element x does not normalize P. Hence the subgroups P, xPx^{-1}, \ldots, x^{q-1}Px^{-(q-1)} are all distinct, and thus they are exactly all Sylow p-subgroups of G. Since x normalizes D, the subgroup D is then contained in every Sylow p-subgroup of G. The intersection

\bigcap\limits_{g \in G}gPg^{-1}

of all p-Sylow subgroups is always normal (the normal core of P). By induction, we may assume that it is trivial, so in particular we can assume that D is trivial. Since we chose D so that it has the largest possible order, the intersections of different p-Sylow subgroups are trivial. Thus we get a total of p^n q - q nonidentity elements from the p-Sylow subgroups. Therefore there can be only one q-Sylow subgroup, which is thus a nontrivial proper normal subgroup.

Subgroup of index p is normal in a finite p-group

29/10/2012

Let p be a prime. Then in any finite group G of order p^n a subgroup H of index p (in other words, a subgroup of order p^{n-1} is normal. This is a pretty simple fact, and I will give outlines for four different proofs here. The first two are standard and the other two are not so common. Proof 3 I figured out myself and it is the most elementary one, requiring almost nothing besides the formula for the order of a product of two subgroups. Proof 4 I saw in an old paper (1895) by Frobenius (*).

Proof 1: In finite p-groups (more generally in nilpotent groups) it is true that for any proper subgroup H, the normalizer N_G(H) is strictly larger than H. Hence for a subgroup H of order p^{n-1} the normalizer must equal all of G, implying that H is normal.

Proof 2: For any finite group G it is true that if a subgroup has index equal the smallest prime divisor of |G|, the subgroup is normal. This can be seen by considering the permutation representation given by the coset action. Since p is the smallest prime divisor of p^n, the claim follows.

Proof 3: Let H be a subgroup of index p. Suppose that H is not normal. Then there exists g \in G such that g^{-1}Hg \neq H. Thus G is equal to the product Hg^{-1}Hg, but this is in contradiction with the following fact.

If M is a subgroup of G and g \in G such that G = Mg^{-1}Mg, then M = G.

Proof of fact: Since g \in Mg^{-1}Mg, we get g \in M and thus G = MM = M.

Proof 4: We proceed by induction. The case n=1 is clear. Since p-groups have nontrivial center, there exists x \in Z(G) of order p. If x \in H, then H/\langle x\rangle \trianglelefteq G/\langle x\rangle by induction and thus H \trianglelefteq G. If x \not\in H, then G = H\langle x \rangle and H \trianglelefteq G since x is central.

(*) F. G. Frobenius, Verallgemeinerung des Sylow’schen Satzes, Sitzungsberichte der Königl. Preuß. Akad. der Wissenschaften (Berlin) (1895), 981-993

False proof of the Pythagorean theorem

26/07/2012

Reference: The American Mathematical Monthly, vol. 3, No. 6/7 (1896), pg. 170.

Suppose the theorem true.. something something.. it’s true, so it’s true! QED

A_5 is simple

12/03/2012

The following proof that A_5 is simple is a slight improvement on the proof presented by Gallian in his Monthly article Another proof that A_5 is simple (1984). Before the proof we will need a few elementary lemmas.

Lemma 1. A_5 has 24 elements of order 5, 20 elements of order 3, and 15 elements of order 2.

The elements of order 5 are the 5-cycles, elements of order 3 are 3-cycles, and elements of order 2 are product of two transpositions.

Lemma 2. Let N be a normal subgroup of a finite group G. If x \in G and \gcd(|x|, |G/N|) = 1, then x \in N.

Proof: The order of x{}N divides both |x| and |G/N|, so |xN| = 1. Thus xN = N which implies x \in N.

An immediate corollary of this result is that a normal subgroup contains every element with order coprime to its index.

Lemma 3.The group A_n has trivial center when n \geq 4.

Proof: Let \sigma \in Z(A_n), n \geq 4. Let i,j,k,l be different elements from \{1, 2, 3, \ldots, n \}. Now (i j k)\sigma = \sigma (i j k), so (i j k)\sigma(i) = \sigma(j). Therefore \sigma(i) is in \{i, j, k\}, as otherwise \sigma(i) = \sigma(j). Since \sigma also commutes with (i j l) and (i k l), we see that \sigma(i) is in \{i, j, l\} and \{i, k, l\} by the same argument. Thus \sigma(i) = i, because the intersection of these three sets is \{i\}. Therefore \sigma(i) = i for any i, and \sigma = (1).

Lemma 4. A normal subgroup of order 2 is central.

Proof: Suppose N = \{1, x\} is a normal subgroup of order 2 in G. Then for any g \in G, we have g^{-1}xg \in N. We cannot have g^{-1}xg = 1 because this would imply x = 1. Therefore g^{-1}xg = x, and gx = xg.

Theorem: A_5 is simple.

Suppose that N is a normal subgroup of A_5. Now A_5 has order 60, so N has order 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 or 60 by Lagrange’s theorem. If N has order 4, then N would contain 15 elements of order 2 since 2 is coprime to |G/N|. If N has order 3, 6, 12 or 15, then N would contain all 20 elements of order 3. If N has order 5, 10 or 20, then N would contain all 24 elements of order 5. If N has order 30, then N would contain 20 elements of order 3 and 24 elements of order 5. If N has order 2, then N is central since any normal subgroup of order 2 is, but this isn’t actually possible since A_5 has trivial center. Therefore the only possibilities are that N has order 1 or order 60, ie. N = \{(1)\} or N = A_5.

Cyclic numbers

23/02/2012

Using Lagrange’s theorem, it is not difficult to show that every group of prime order is cyclic. If G is a group of prime order, then each subgroup has order 1 or |G|. Thus G is generated by any non-identity element.

Prime numbers are not the only numbers with this property. For example, any group of order 15 is cyclic. To generalize this fact a bit, for p and q prime, p > q and p \not\equiv 1 \mod q, a group of order pq is always cyclic. What about in general? Is there a simple arithmetic characterization for all cyclic numbers? This turns out to be true, and we have the following theorem, which we will prove next:

Theorem. Every group of order n is cyclic if and only if \gcd(n, \varphi(n)) = 1.

Here \varphi denotes Euler’s totient function. The solution given here is a combination of the proof by Szele (1947) and another one given by Gallian and Moulton (1993). We will first need a lemma.

Lemma. If a finite group G is not cyclic and every proper subgroup of G is abelian, then G has a nontrivial proper normal subgroup.

Proof. See the paper by Gallian and Moulton.

Since the lemma also holds for finite cyclic groups of non-prime order, we have the following corollary:

Corollary. If G is a finite group of non-prime order with every proper subgroup abelian, then G has a nontrivial proper normal subgroup.

Proof of theorem. We will first show by induction that \gcd(n, \varphi(n)) = 1 forces any group of order n to be cyclic. For the case n = 1 the statement is clearly true. Suppose then that the claim is true for any integer less than n and that \gcd(n, \varphi(n)) = 1. Let G be a group of order n. If n is prime we are done, so we can assume that n is not prime. Now n has a prime factorization

n = p_1^{a_1}\ldots p_k^{a_k}

and thus

\varphi(n) = (p_1 - 1)p_1^{a_1 - 1}\ldots(p_k - 1)p_k^{a_k - 1}

This shows that a_1 = a_2 = \ldots = a_k = 1, for a_i being greater than one would imply that p_i is a common divisor of n and \varphi(n). Thus n and \varphi(n) are of the form

\begin{aligned}&n = p_1p_2 \ldots p_k \\ &\varphi(n) = (p_1 - 1)(p_2 - 1)\ldots(p_k - 1)\end{aligned}

Therefore for any divisor m of n, we have \gcd(m, \varphi(m)) = 1. This shows that any proper subgroup of G is cyclic, and thus G has a nontrivial proper normal subgroup H by the lemma. Since the order of G/H also divides n, the quotient group G/H is also cyclic. Since H and G/H are abelian, they are solvable and thus G is also solvable.

Let N be a minimal normal subgroup of G. Since G is solvable, the normal subgroup N has order p for some prime p. Then G/N has order n/p, and thus both N and G/N are cyclic. Now N = \langle a \rangle and G/N = \langle bN \rangle for some elements a and b from G. Notice that the order of bN must divide the order of b, so b has order n/p or n. If b has order n we are done, so suppose that b has order n/p.

Since N is a normal subgroup, b^{-1}ab = a^i for some 1 \leq i < p. Since b has order n/p, we notice that a = b^{-n/p}ab^{n/p} = a^{i^{n/p}} and thus i^{n/p} \equiv 1 \mod p. On the other hand, i^{p-1} \equiv 1 \mod by Fermat’s little theorem. Since \gcd(n/p, p-1) = 1, we have i \equiv 1 \mod p. Thus b^{-1}ab = a and ab = ba.

There is also another way to show that a and b commute. When N is normal, there is a homomorphism \psi: G \rightarrow Aut(N) with Ker(\psi) = C_G(N) by mapping each element of g to the corresponding conjugation map. Then \frac{n}{|C_G(N)|} divides p-1, since a cyclic group of order m has a exactly \varphi(m) automorphisms. Thus |C_G(N)| = n since \frac{n}{|C_G(N)|} also divides n. Therefore C_G(N) = G, which shows that N is central.

Since a and b commute and have coprime order, the element ab has order p \cdot n/p = n. Therefore G = \langle ab \rangle.

Proving the statement in the other direction is a bit easier. Suppose that \gcd(n, \varphi(n)) > 1. If n is not squarefree, then n has a prime divisor p such that p^2 divides n. Then C_p \times C_p \times C_{\frac{n}{p^2}} is a noncyclic group of order n. If n is squarefree, then there exist prime divisors p and q of n such that q divides p-1. But then a nonabelian group H of order pq exists, and H \times C_{\frac{n}{pq}} is a noncyclic group of order n.

For a different proof, see for example the outline given by Dieter Jungnickel (1992).

After thinking about cyclic numbers, it is natural to generalize and wonder about other orders which force some property on a group. For a nice exposition of cyclic, abelian and nilpotent numbers, see “Nilpotent numbers” by Pakianathan and Shankar (2000).

Split. Multiply. Sum.

15/01/2012

The following is extremely useless but cool.

36 = 3 * 6 + 3 * 6

655 = 65 * 5 + 6 * 55

1258 = 125 * 8 + 1 * 258
1352 = 13 * 52 + 13 * 52
2464 = 24 * 64 + 2 * 464
3382 = 338 * 2 + 33 * 82
3835 = 38 * 35 + 3 * 835
4738 = 47 * 38 + 4 * 738
4925 = 49 * 25 + 4 * 925
5275 = 52 * 75 + 5 * 275
8291 = 829 * 1 + 82 * 91
9274 = 92 * 74 + 9 * 274

11548 = 115 * 48 + 11 * 548
12915 = 129 * 15 + 12 * 915
16625 = 16 * 625 + 1 * 6625
39826 = 398 * 26 + 3 * 9826
43364 = 433 * 64 + 43 * 364
45715 = 4571 * 5 + 4 * 5715
47455 = 474 * 55 + 47 * 455
58825 = 588 * 25 + 5 * 8825
65455 = 6545 * 5 + 6 * 5455
74575 = 74 * 575 + 7 * 4575
75385 = 7538 * 5 + 7 * 5385
79417 = 794 * 17 + 7 * 9417

128917 = 1289 * 17 + 12 * 8917
147925 = 1479 * 25 + 14 * 7925
183645 = 183 * 645 + 18 * 3645
229124 = 229 * 124 + 22 * 9124
235297 = 23529 * 7 + 2 * 35297
257626 = 2576 * 26 + 25 * 7626
318825 = 318 * 825 + 3 * 18825
336375 = 336 * 375 + 33 * 6375
456372 = 456 * 372 + 45 * 6372
497218 = 497 * 218 + 4 * 97218
529672 = 5296 * 72 + 5 * 29672
589624 = 5896 * 24 + 5 * 89624
746956 = 7469 * 56 + 7 * 46956
992164 = 992 * 164 + 9 * 92164

1562564 = 15625 * 64 + 1 * 562564
1586185 = 1586 * 185 + 15 * 86185
1592728 = 1592 * 728 + 159 * 2728
1728472 = 17284 * 72 + 17 * 28472
1982212 = 1982 * 212 + 19 * 82212
2147275 = 2147 * 275 + 214 * 7275
2267525 = 22675 * 25 + 226 * 7525
2291125 = 2291 * 125 + 22 * 91125
2593361 = 259336 * 1 + 25 * 93361
2857144 = 285714 * 4 + 2 * 857144
3214288 = 321428 * 8 + 3 * 214288
3591112 = 3591 * 112 + 35 * 91112
3654625 = 365 * 4625 + 36 * 54625
3962386 = 3962 * 386 + 39 * 62386
3998251 = 3998 * 251 + 3 * 998251
4428416 = 44284 * 16 + 442 * 8416
4889125 = 4889 * 125 + 48 * 89125
6245764 = 6245 * 764 + 6 * 245764
6365455 = 6365 * 455 + 636 * 5455
6437626 = 6437 * 626 + 64 * 37626
6545455 = 654545 * 5 + 6 * 545455
6792453 = 679245 * 3 + 6 * 792453
7922773 = 7922 * 773 + 79 * 22773

11176524 = 111765 * 24 + 111 * 76524
11381872 = 1138 * 1872 + 113 * 81872
11637625 = 11637 * 625 + 116 * 37625
12396168 = 1239 * 6168 + 12 * 396168
12878125 = 128 * 78125 + 1 * 2878125
13776424 = 137764 * 24 + 137 * 76424
13836375 = 1383 * 6375 + 138 * 36375
15878617 = 158786 * 17 + 15 * 878617
17584435 = 17584 * 435 + 17 * 584435
22624768 = 22624 * 768 + 2 * 2624768
22745464 = 2274 * 5464 + 227 * 45464
22857175 = 228571 * 75 + 2 * 2857175
24615625 = 24615 * 625 + 2 * 4615625
24772516 = 2477 * 2516 + 24 * 772516
27624448 = 27624 * 448 + 2 * 7624448
29273125 = 292 * 73125 + 29 * 273125
32495125 = 3249 * 5125 + 32 * 495125
33638182 = 33638 * 182 + 3363 * 8182
34615386 = 3461538 * 6 + 3 * 4615386
36381835 = 3638 * 1835 + 363 * 81835
43726592 = 4372 * 6592 + 4 * 3726592
45472738 = 4547 * 2738 + 454 * 72738
61749583 = 617495 * 83 + 6 * 1749583
67188125 = 6718 * 8125 + 67 * 188125
67328713 = 67328 * 713 + 673 * 28713
73546625 = 7354 * 6625 + 7 * 3546625
79941295 = 7994 * 1295 + 7 * 9941295
87671233 = 8767123 * 3 + 8 * 7671233
91447525 = 91447 * 525 + 914 * 47525
98492224 = 98492 * 224 + 9 * 8492224

113654548 = 11365 * 4548 + 1136 * 54548
116346154 = 11634615 * 4 + 11 * 6346154
118234375 = 118 * 234375 + 11 * 8234375
129263914 = 1292639 * 14 + 12 * 9263914
145636625 = 1456 * 36625 + 145 * 636625
147745456 = 14774 * 5456 + 1477 * 45456
177518428 = 1775184 * 28 + 17 * 7518428
212498824 = 21249 * 8824 + 2 * 12498824
214358416 = 214358 * 416 + 2143 * 58416
226375625 = 226375 * 625 + 226 * 375625
232527475 = 2325274 * 75 + 23 * 2527475
259995385 = 25999 * 5385 + 2 * 59995385
284272768 = 2842 * 72768 + 284 * 272768
312388128 = 3123 * 88128 + 3 * 12388128
319881375 = 3198 * 81375 + 3 * 19881375
413784625 = 413784 * 625 + 41 * 3784625
431836364 = 43183 * 6364 + 4318 * 36364
472745455 = 47274 * 5455 + 4727 * 45455
487831417 = 4878314 * 17 + 487 * 831417
498237625 = 49823 * 7625 + 498 * 237625
527871736 = 527871 * 736 + 5 * 27871736
532814872 = 5328148 * 72 + 53 * 2814872
568363664 = 5683 * 63664 + 568 * 363664
591428575 = 59142 * 8575 + 59 * 1428575
591996223 = 591996 * 223 + 5 * 91996223
598192192 = 598192 * 192 + 59 * 8192192
633861625 = 6338 * 61625 + 63 * 3861625
654545455 = 65454545 * 5 + 6 * 54545455
662495434 = 662495 * 434 + 6 * 62495434
688995225 = 688995 * 225 + 6 * 88995225
726762933 = 7267629 * 33 + 72 * 6762933
727454575 = 7274 * 54575 + 727 * 454575
928515625 = 9285 * 15625 + 92 * 8515625

1138138192 = 1138138 * 192 + 113 * 8138192
1237822272 = 12378 * 22272 + 123 * 7822272
1248952968 = 12489 * 52968 + 12 * 48952968
1514546875 = 1514 * 546875 + 151 * 4546875
1614123586 = 16141235 * 86 + 16 * 14123586
1678688525 = 16786885 * 25 + 16 * 78688525
1686985175 = 1686985 * 175 + 16 * 86985175
1743484576 = 1743484 * 576 + 17 * 43484576
1818363645 = 18183 * 63645 + 1818 * 363645
1953125512 = 1953125 * 512 + 1 * 953125512
2345546875 = 234 * 5546875 + 23 * 45546875
2475445664 = 24754 * 45664 + 247 * 5445664
2542717658 = 25427176 * 58 + 25 * 42717658

These are all the examples I have found so far for numbers with no zero digit. We get more examples by taking any number with this property and multiplying it by a power of ten. For example, 36 = 3 * 6 + 3 * 6 and thus 360 = 3 * 60 + 3 * 60. This shows that there is an infinity of numbers with this property.

More families of these numbers are given by

12500...08 = 1 * 2500...08 + 12500...0 * 8
1600...0625 = 1600...0 * 625 + 1 * 600...0625
65454...5455 = 6 * 5454...5455 + 65454...545 * 5

These facts are not too difficult to prove. We will prove the third equality here which is the most interesting one, as it has no zero in its decimal expansion. Numbers with zero are a bit more common, although there are not too many of either.

First, let’s express 5454\ldots54 in form that is easier to manipulate. This way we easily find similar representations for 65454\ldots, 5454\ldots5455 and 65454\ldots545.

Let k be the amount of 5{}4‘s in this number. Now if x = 0.545454\ldots, then 10^{2k}x = 5454\ldots54.5454\ldots, implying (10^{2k}-1)x = 5454\ldots54. What is x as a fraction? Since 100x = 54.5454\ldots, we get 99x = 54 and so x = \frac{54}{99} = \frac{6}{11}.

Thus 5454\ldots54 = (10^{2k}-1)\frac{6}{11}. Then by multiplying by 100 (which adds two zeros at the end) and adding 55 (changing those zeros to 55), we get 5454\ldots55. Therefore

\begin{aligned}6 \cdot 5454\ldots5455 &= 6 \cdot (100 \cdot (10^{2k} - 1)\frac{6}{11} + 55) \\ &= 600 \cdot (10^{2k}-1)\frac{6}{11} + 5\cdot55 + 55\\ & \end{aligned}

And with the same method we find that

\begin{aligned}65454\ldots545 \cdot 5 &= 5 \cdot (6\cdot10^{2k+1} + 10\cdot(10^{2k}-1)\frac{6}{11} + 5) \\ &= 50 \cdot(10^{2k+1}-1)\frac{6}{11} + 5 \cdot 5 + 3 \cdot 10^{2k+2}\end{aligned}

Summing these two together gives our result after a few simple manipulations:

\begin{aligned}\  &= 100 \cdot (10^{2k}-1)\frac{6}{11} + 550 \cdot(10^{2k}-1)\frac{6}{11} + 300 + 55 + 3 \cdot 10^{2k+2} \\ &= 100 \cdot (10^{2k}-1)\frac{6}{11} + 300 \cdot(10^{2k} - 1) + 300 + 55 \\ &= 100 \cdot (10^{2k}-1)\frac{6}{11} + 3 \cdot 10^{2k+2} - 300 + 300 + 55 \\ &= 6 \cdot 10^{2k+2} + 100 \cdot (10^{2k}-1)\frac{6}{11} + 55 \\ &= 65454\ldots5455 \end{aligned}

as desired.

Are 36 = 3 * 6 + 3 * 6 and 1352 = 13 * 52 + 13 * 52 the only numbers that can be split this way from the middle?

A_5 is the only simple group of order 60

28/12/2011

Let G be a simple group of order 60.

Let N be a proper subgroup of G with index k. We will show that k \geq 5. Left coset action gives us the homomorphism \phi: G \rightarrow S_k, where Ker(\phi) \leq N. Since N is a proper subgroup and G is simple, Ker(\phi) = \{1\}. By the first isomorphism theorem, G \cong Im(\phi) \leq S_k. Therefore 60 divides k!, implying that k \geq 5.

Next we will show that G has a subgroup of index 5.

The amount of Sylow 2-subgroups must divide 15. Thus there are 1, 3, 5 or 15 Sylow 2-subgroups. If there is only one Sylow 2-subgroup, it is normal. Thus there has to be more than one Sylow 2-subgroup, since G is simple. The amount of Sylow 2-subgroups is equal to the index of the normalizer of a Sylow 2-subgroup, so 3 is not a possibility as shown before. If there are 5 Sylow 2-subgroups, then the normalizer of a Sylow 2-subgroup is of index 5.

Suppose then that there are 15 Sylow 2-subgroups in G. It is not difficult to show that there are 6 Sylow 5-subgroups in total, giving us 24 different elements. Thus there exist two different Sylow 2-subgroups P_1 and P_2 with nontrivial intersection. Otherwise we would find 24 + 45 = 69 different elements, which is not possible. Since P_1 and P_2 are Abelian, the intersection P_1 \cap P_2 is normal in them both. Thus it is also normal in the subgroup \langle P_1, P_2 \rangle generated by P_1 and P_2. Since G is simple, this subgroup is proper. As shown in the first paragraph, [G : \langle P_1, P_2 \rangle] \geq 5, and thus |\langle P_1, P_2 \rangle| \leq 12. By Lagrange’s theorem, 4 divides the order of \langle P_1, P_2 \rangle. Thus |\langle P_1, P_2 \rangle| = 12, because we also have |\langle P_1, P_2 \rangle| > 4. Then \langle P_1, P_2 \rangle is a subgroup of index 5.

We have now shown that there exists some H < G with [G:H] = 5. The left coset action gives us a homomorphism \phi: G \rightarrow S_5 with Ker(\phi) \leq H. By the same argument as before, Ker(\phi) = \{1\}. Denote N = Im(\phi). Then G \cong N \leq S_5. Now N is normal in S_5, because it has order 60 and therefore index 2. Then N \cap A_5 is normal in A_5. We know that A_5 is simple. Furthermore, any subgroup of S_n with more than two elements always contains an even element other than the identity. These two facts imply that N \cap A_5 = A_5, and so A_5 \leq N. Since A_5 and N both have the same order, N = A_5.

Thus G \cong A_5.

Automorphisms of the symmetric group

20/12/2011

Here n \geq 3.

Lemma 1. S_n has trivial center.

Proof: Let \sigma \in Z(G). Let i, j, k \in \{1, 2, \cdots, n\} be different. Then (ij)\sigma = \sigma(ij), so (ij)\sigma(i) = \sigma(j). Thus \sigma(i) \in \{i, j\}, as otherwise \sigma(i) = \sigma(j). Similarly (ik)\sigma = \sigma(ik), so \sigma(i) \in \{i, k\}. Thus \sigma(i) = i, and therefore \sigma = (1).

Lemma 2. S_n = \langle (12), (12 \cdots n) \rangle.

Proof:

\begin{aligned}S_n &= \langle (ab)\ |\ a,b \in \{1, 2, \cdots, n\} \rangle \\ &= \langle (12),\ (13),\ \cdots,\ (1n) \rangle \\ &= \langle (12),\ (23),\ \cdots,\ (n-1\ n) \rangle \\ &= \langle (12), (12 \cdots n) \rangle\end{aligned}

Lemma 3. If G is a group and \phi is an automorphism of G, then for every a \in G of finite order we have |\phi(a)| = |a|.

Proof: Follows from the fact that \phi(a)^k = 1 if and only if a^k = 1.

Lemma 4. Any automorphism \phi: S_n \rightarrow S_n preserves the parity of permutations.

Proof: Since the commutator subgroup of S_n is A_n, we have that A_n is a characteristic subgroup of S_n. Thus \phi(A_n) = A_n, and so g \text{ even} \Leftrightarrow \phi(g) \text{ even}.

Aut(S_n) \cong S_n for n = 3, n = 4 and n = 5.

Proof: In general, this result is true for every S_n with n \neq 2 and n \neq 6.

Because S_3 is generated by the elements (12) and (123), we have that any automorphism \phi is completely determined by \phi((12)) and \phi((123)). By lemma 3, there are 3 choices for \phi((12)) and 2 choices for \phi((123)), so there can be at most 6 different automorphisms. Since S_3 \cong S_3 / Z(S_3) \cong Inn(S_3) \leq Aut(S_3), we have that Aut(S_3) = Inn(S_3) and so Aut(S_3) \cong S_3.

Similarly S_4 is generated by (12) and (1234). By lemma 3 and lemma 4, we have 6 choices for \phi((12)) and 6 choices for \phi((1234)). Thus there are at most 36 automorphisms of S_4. On the other hand, S_4 \cong S_4 / Z(S_4) \cong Inn(S_4) \leq Aut(S_4), so |Aut(S_4)| is a multiple of 24 by Lagrange’s theorem. Thus there are 24 automorphisms, and Inn(S_4) = Aut(S_4). Therefore Aut(S_4) \cong S_4.

The case of S_5 is similar. Now S_5 is generated by (12) and (12345) and there are 10 choices for \phi((12)) and 24 choices for \phi((12345)). As before, S_5 \cong S_5 / Z(S_5) \cong Inn(S_5) \leq Aut(S_5), so |Aut(S_5)| is a multiple of 120. Thus there are 120 or 240 automorphisms. We will show that one of the choices for \phi((12)) and \phi((12345)) is not possible, which then shows that there are 120 automorphisms, and thus Inn(S_5) = Aut(S_5) and Aut(S_5) \cong S_5 as before. Suppose \phi is an automorphism with \phi((12)) = (12) and \phi((12345)) = (14523). Then

\begin{aligned}\phi((2345)) &= \phi((12)(12345)) \\ &= \phi((12))\phi((12345)) \\ &= (12)(14523) \\ &= (145)(23)\end{aligned}

But this is not possible, as (2345) has order 4 and (145)(23) order 6. Thus there are less than 240 automorphisms, and so Aut(S_5) \cong S_5.

This approach does not work with larger symmetric groups. The next symmetric group for which the claim is true is S_7. In S_7, we would have 126 choices for \phi((12)) and 720 choices for \phi((1234567)). This gives us a total of 90720 = 18 \cdot |S_7| possibilities, so a different method is required.

Upper bound for the index of intersection of two subgroups

13/12/2011

Let G be a group and let H and K be subgroups of finite index in G. Then [G : H \cap K] \leq [G:H][G:K]

First we notice that for every a \in G, we have a(H \cap K) = aH \cap aK. Because aH can be chosen in [G : H] different ways and aK in [G : K] different ways, there can be at most [G : H][G : K] cosets of H \cap K.

Cosets and partitions in a group

03/11/2011

Let G be a group. For a nonempty subset H of G and element a \in G, define the coset aH by:

aH = \{ah\ |\ h \in H\}

We know from Lagrange’s theorem that if H is a subgroup, then the cosets partition G into disjoint subsets. The question is: are there any other subsets which partition G with cosets? The following result answers the question completely, and we will prove it here.

The cosets of H partition G if and only if H is a coset of a subgroup of G.

Suppose first that the cosets of H partition G. Let M be the coset that contains the neutral element 1. Then if a \in M, we also have a = a1 \in aM. Thus aM = M, as we assumed that the cosets induce a disjoint partition of G. Now 1 \in aM, so am = 1 for some m \in M. This means that m = a^{-1} \in M. Finally, for all a, b \in M, we get ab \in aM = M. This shows that M, a coset of H, is a subgroup of G. Since M = gH, we get H = g^{-1}M, and thus H is a coset of the subgroup M.

For the converse, suppose H = aM, where M is a subgroup of G. Then gM = (ga^{-1})aM = ga^{-1}H, so the cosets of H and M are the same. Since M is a subgroup, the cosets partition G by Lagrange’s theorem.

Exercise from Topics in Algebra

01/11/2011

The following exercise can be found in I.N. Herstein’s book Topics in Algebra (second edition, pg. 53):

Give an example of a group G, subgroup H and an element a \in G such that aHa^{-1} \subseteq H but aHa^{-1} \neq H.

First we notice that H cannot be normal in G. This means that G cannot be Abelian. Secondly, H must be infinite. Otherwise aHa^{-1} \subseteq H would imply aHa^{-1} = H, since aHa^{-1} and H always have the same order. This shows that we should be looking for an infinite, nonabelian group with an infinite subgroup that has the desired property. Here is my example:

Let G = S_{\mathbb{R}}, the set of bijections from \mathbb{R} to \mathbb{R}. Let H = \{ f \in G\ |\ f(x) = x \text{ when } x \notin \mathbb{N} \}. Here \mathbb{N} does not include zero. Now H is a subgroup of G. Define the map \sigma : \mathbb{R} \rightarrow \mathbb{R} by \sigma(x) = x+1 for all x \in \mathbb{R}.

Let f \in H. Then \sigma f \sigma^{-1}(x) = \sigma f(x-1) = f(x-1) + 1. If x \notin \mathbb{N}, then \sigma f \sigma^{-1} (x) = f(x-1) + 1 = x. Thus \sigma f \sigma^{-1} \in H, and we have shown that \sigma H \sigma^{-1} \subseteq H.

Now \sigma f \sigma^{-1} (1) = f(0) + 1 = 1. Since \sigma H \sigma^{-1} only contains mappings of H that fix 1, \sigma H \sigma^{-1} \neq H.

The commutator subgroup of S_n

20/10/2011

We will prove that for all n \geq 3, the commutator subgroup of S_n (denoted S_{n}^{'}) is equal to A_n, the the alternating group of degree n.

First we will show that any 3-cycle must be in the commutator subgroup. Let (a\ b\ c) be a 3-cycle from S_n. Now

\begin{aligned}(a\ b\ c) &= (a\ c\ b)^2 \\ &= ((a\ b)(a\ c))^2 \\ &= (a\ b)(a\ c)(a\ b)(a\ c) \\ &= (a\ b)^{-1}(a\ c)^{-1}(a\ b)(a\ c) \\ &= [(a\ b),\ (a\ c)]\end{aligned}

Therefore (a\ b\ c) is a commutator, and thus is in the commutator subgroup. Since A_n is generated by 3-cycles when n \geq 3, the commutator subgroup contains all of A_n.

Next, note that any commutator \sigma^{-1}\tau^{-1}\sigma\tau, with \sigma and \tau permutations from S_n, must be an even permutation. It is known that \sigma has the same parity as \sigma^{-1} and \tau has the same parity as \tau^{-1}, and thus \sigma^{-1}\tau^{-1} has the same parity as \sigma\tau. This shows that their product \sigma^{-1}\tau^{-1}\sigma\tau must be even.

Thus every permutation in the commutator subgroup is even. Since the commutator subgroup contains A_n, the group of even permutations, it must be equal to A_n.

When n \geq 5, the alternating group A_n is simple. From this fact and what we just proved it follows that S_n is not solvable when n \geq 5.

There’s also another way to see that S_{n}^{'} \subseteq A_n using the following result:

Let G be a group. Then G^{'} \leq N if and only if N is normal in G and G/N is Abelian.

Now A_n is a normal subgroup of S_n and S_n/A_n is Abelian since [S_n:A_n] = 2. Thus S_n^{'} \subseteq A_n.

Subgroup criterions

03/10/2011

Let G be a group, and H a nonempty subset of G. The following statements are equivalent:

  1. H is a subgroup of G
  2. For all a, b \in H: ab \in H and a^{-1} \in H
  3. For all a, b \in H: ab^{-1} \in H
  4. For all a, b \in H: a^{-1}b \in H
  5. aH = H if and only if a \in H
  6. If a \in H, then aH = H
  7. If a \in H and b \not\in H, then ab \not\in H

We will equivalence of H being a subgroup and statement 2 for granted and use it to prove statement 6 and 7 equivalent to H being a subgroup.

Proof of statement 6: Suppose first that H is a subgroup of G. Let a \in H. Now ah \in H for all h \in H, so aH \subseteq H. Let h \in H. Then h = a(a^{-1}h) \in aH, so H \subseteq aH. Thus aH = H.

For the other direction, suppose that a \in H always implies aH = H. For any a \in H we get H = aH so a = ax for x \in H. Then x = 1, so 1 \in H. Similarly, 1 \in aH so ah = 1 for some h \in H. Now h = a^{-1}, so a^{-1} \in H. Finally, for all a, b \in H, we have ab \in aH = H. Thus H is a subgroup of G.

Proof of statement 7: If H is a subgroup, then when a \in H and b \not\in H, we cannot have ab \in H. If this would happen, then a^{-1}ab = b \in H since a^{-1} \in H.

Suppose then that a \in H and b \not\in H implies ab \not\in H in the nonempty subset H. First we will show that 1 \in H. Let a be some element of H. If we had 1 \not\in H, then a \cdot 1 = a \not\in H, which is a contradiction. Therefore 1 \in H. If we had a^{-1} \not\in H, then aa^{-1} = 1 \not\in H, again a contradiction. Thus H is closed under inverses. Suppose a \in H and b \in H. Then a^{-1} \in H. Thus if we had ab \not\in H, we would have a^{-1}ab = b \not\in H, a contradiction. Therefore ab \in H.

based permutation

24/05/2011

103462 (base 10) = 610432 (base 7) = 312046 (base 8)

245183 (base 10) = 413285 (base 9) = 158234 (base 11)

Notice that 245183 is prime.


Follow

Get every new post delivered to your Inbox.