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.