Solutions to Putnam Group Theory Problems

Random number: 27

1968-B-2. $A$ is a subset of a finite group $G$, and $A$ contains more than half of the elements of $G$. Prove that each element of $G$ is the product of two elements in $A$.

Suppose that $\exists x \in G$ such that it cannot be written as the product of $2$ elements from the subset $A$. We can write $x$ in $|G|$ different ways as the product of $2$ elements from $G$ as follows: $$\forall y \in G : y \cdot (y^{-1} x) = x$$ We can write this out as: $$ y_1 \cdot (y_1^{-1} x) = x$$ $$ y_2 \cdot (y_2^{-1} x) = x$$ $$...$$ $$ y_{|G|} \cdot (y_{|G|}^{-1} x) = x$$ where $\{y_i\}$ is the set of all elements of $G$, with $y_i = y_j$ iff $i = j$. By assumption, $x$ can't be written as the product of two elements of $A$. Let's only consider the $y \in A$ then, and discard the rest because they are uninteresting. We can reindex $y$ such that: $$ y_1 \cdot (y_1^{-1} x) = x$$ $$ y_2 \cdot (y_2^{-1} x) = x$$ $$...$$ $$ y_{|A|} \cdot (y_{|A|}^{-1} x) = x$$ for all $y \in A$ now. The set of "right-multiples" (I don't know what else to call them) $\{(y_1^{-1} x),(y_2^{-1} x),...,(y_{|A|}^{-1} x)\}$ is "unique" in the sense that no two elements from this set are equal. If there were two elements equal, we would have for some $i,j$: $$ y_i \cdot (y_i^{-1} x) = y_j \cdot (y_j^{-1} x)$$ $$ y_i = y_j$$ But this is a contradiction. Hence the "right-multiples" are unique. There are $|A|$ right multiples, and because $|A| > \frac{|G|}{2}$, there must be some "right-multiple" in $A$. Hence there must be some $i$ such that both $y_i$ and $(y_i^{-1} x)$ are in $A$, completing our proof.

1969-B-2. Show that a finite group can not be the union of two of its proper subgroups. Does the statement remain true if “two” is replaced by “three”?

Suppose we have a finite group $G$, and two proper subgroups $A,B$. Suppose also that $A \cup B = G$. We know from Lagrange's theorem that $|A|, |B|$ both divide $|G|$. But we also know that $$A\cup B = G$$ $$|A| + |B| \geq |G|$$ Every subgroup must contain the identity element however, because subgroups are closed w.r.t inverses (so for $x \in S$ we must have $x^{-1} \in S$) but they are also closed w.r.t multiplication (so $x \cdot x^{-1} = e \in S$). Hence we have: $$|A| + |B| \geq |G| + 1$$ Because of Lagrange's theorem, we have $$|A| = \frac{|G|}{a} \text{ , } |B| = \frac{|G|}{b}$$ for some $a,b \in \mathbb{N}, a,b > 1$. Hence we have the inequality $$|G|(\frac{1}{a} + \frac{1}{b}) \geq |G| + 1$$ $$(\frac{1}{a} + \frac{1}{b}) > 1$$ which is impossible. Hence we have proven that it is impossible for $A \cup B = G$.

The statement is not true if you replace "two" with "three"; we can see this for the Klein four-group (that I somehow managed to guess, nice), which is the group $\mathbb{Z}_2 \times \mathbb{Z}_2$. You can take the three proper subgroups $\{e,a\},\{e,b\},\{e,c\}$ where $a,b,c$ are the elements of the group.

1972-B-3. Let $A$ and $B$ be two elements in a group such that $ABA = BA^2B$, $A^3 = 1$ and $B^{2n−1} = 1$ for some positive integer $n$. Prove $B = 1$.

Answer taken from here because I couldn't figure it out $$AB^2 = ABA^3B = (ABA)(A^2B) = (BAAB)(A^2B)$$ $$ = BA^2BA^2B = (BA^2)(BA^2B) = (BA^2)(ABA) = B^2A$$ So $A$ and $B^2$ commute. $$AB^{2m}A^2 = B^{2m}$$ Because you can drag the $A^2$ on the right through all the $B's$ to the left, because we know that $A$ commutes with $B^2$. We are given that $B$ has a finite odd order, so that means there must exist some $m$ such that $B^{2m} = B$. So we have: $$ABA^2 = B$$ $$AB = BA$$ So $A$ commutes with $B$. But then we have: $$(ABA = BA^2B) \implies (A^2B = A^2B^2) \implies (B = B^2) \implies (B = e)$$

1975-B-1. In the additive group of ordered pairs of integers $(m, n)$ (with addition defined componentwise), consider the subgroup $H$ generated by the three elements $$(3,8) \qquad (4,-1) \qquad (5,4)$$ Then $H$ has another set of generators of the form $$(1,b) \qquad (0,a)$$ for some integers $a,b$ with $a > 0$. Find $a$.

I claim that the set of three generators $$(3,8) \qquad (4,-1) \qquad (5,4)$$ are equivalent to the set of two generators $$(1,-2) \qquad (0,7)$$ An arbitrary element generated by the first set of three generators is given by $(3a + 4b + 5c, 8a - b + 4c)$, where $a,b,c \in \mathbb{Z}$ (This is due to the fact that addition over integers is not only commutative). Let $(3a + 4b + 5c) = n$. Then we have the following relations in modulo 7: $$-2n \equiv -6a - 8b - 10c \equiv a -b + 4c$$ $$8a - b + 4c \equiv a - b + 4c \equiv -2n$$ So every element generated by the first set of generators is of the form $(n,-2n)$ modulo 7. But this is exactly the set of elements described by the second set of generators! So we have that $a = 7$.

1976-B-2. Suppose that $G$ is a group generated by elements $A$ and $B$, that is, every element of $G$ can be written as a finite "word" $A^{n_1}B^{n_2}A^{n_3}...B^{n_k}$, where $n_1,n_2,...n_k$ are any integers, and $A^0 = B^0 = 1$, as usual. Also, suppose that $$A^4 = B^7 = ABA^{-1}B = 1, \qquad A^2 \neq 1, \qquad \text{and} \qquad B \neq 1$$ (a) How many elements of $G$ are of the form $C^2$ with $C$ in $G$? (b) Write each square as a word in $A$ and $B$.

$$ABA^{-1}B = 1$$ $$AB = B^{-1}A$$ This implies that if we have any word constructed of $A$ and $B$, we can 'shuffle' the $A$ parts of the word to the very right, so they pile up at the end. Since $G$ is generated by $A$ and $B$, this implies that every element of $G$ can be expressed as $B^nA^m$ for some integral $n,m$. Now consider what happens when we square this element: $$(B^nA^m)^2 = B^nA^mB^nA^m$$ We want to now shuffle the first group of $A$s past the second group of $B$s. The power of the $A$s doesn't change as they get shuffled, so we will end up with $2m$ copies of $A$ at the right. Each element of $B$ gets inversed as it passed by a single $A$. But we know that $B^7 = 1$, so $B^{-1} = B^6$. Knowing this, we have that: $$(B^nA^m)^2 = B^{n + n6^m}A^{2m}$$ We now want to utilise the fact that $A^4 = B^7 = 1$. For $m$ even, we have that $(B^nA^m)^2 = B^{2n}A^0$. For $m$ odd, we have that $(B^nA^m)^2 = B^0 A^2$. So we can enumerate all the squares (of which there are 8): $$A^2, 1, B, B^2, B^3, B^4, B^5, B^6$$