Archive for the ‘Groups and Fields’ Category

Elements of a finite field as a sum of two squares or two cubes

Posted: February 6, 2019 in Elementary Algebra; Problems & Solutions, Groups and Fields
Tags: , ,
0

It is well-known that, in a finite field, every element is a sum of two squares (Problem 1). It is however not true that every element of a finite field is a sum of two cubes. For example, in \mathbb{Z}_7, we cannot write 3 or 4 as a sum of two cubes because \{a^3: \ a \in \mathbb{Z}_7\}=\{0,1,6\} and so the only elements of \mathbb{Z}_7 that are a sum of two cubes are 0,1,2,5,6.
But if, in a finite field, \alpha^3=2 for some non-zero element \alpha of the field, then we can show that every element of the field is a sum of two cubes (Problem 2).

Problem 1. Show that every element of a finite field is a sum of two squares.

Solution. Let F be a finite field. So we want to show that if x \in F, then x=a^2+b^2 for some a,b \in F. We can actually be more specific if we consider two cases. Let |F|=q.

Case 1: q=2n for some integer n. Then, since x^q=x for all x \in F, we get x=(x^n)^2. So in this case, every element of the field is a square.

Case 2: q=2n+1 for some integer n. Since F is finite, the multiplicative group F^{\times} is cyclic.
So F^{\times}=\langle c \rangle. Let x \in F and consider the sets

A:=\{a^2: \ \ a \in F\}, \ \ \ B:=\{x-a^2: \ \ a \in F\}.

Clearly \{0\} \cup \{c^{2m}: \ \ 1 \le m \le n\} \subseteq A and |A|=|B|. Thus |A| \ge n+1 and hence

|A|+|B| =2|A| \ge 2n+2 > |F|.

Therefore A \cap B \neq \emptyset, i.e. there exist a,b \in F such that a^2=x-b^2 and the result follows. \Box

Remark 1. Regarding the second case in the solution of Problem 1, notice that, in fact, we have

A= \{0\} \cup \{c^{2m}: \ \ 1 \le m \le n\}

and so |A|=n+1. The reason is that if c^k=c^{2m} for some integers k,m, then c^{k-2m}=1 and hence k-2m must be divisible by |F^{\times}|=2n implying that k is even.

Problem 2. Let F be a finite field and suppose that there exists 0 \ne \alpha \in F such that \alpha^3=2. Show that every element of F is a sum of two cubes.

Solution. So we want to show that if x \in F, then x=a^3+b^3 for some a,b \in F. Let |F|=q and let’s consider three cases.

Case 1: q=3n for some integer n. Then x=x^q=(x^{n})^3 for all x \in F.

Case 2: q=3n+2 for some integer n. Then x=x^{2-q}=(x^{-n})^3 for all 0 \ne a \in F and clearly 0=0^3.

So, in both cases 1 and 2, for every x \in F, there exists a \in F such that x=a^3.

Case 3: q=3n+1 for some integer n. Since F is finite, the multiplicative group F^{\times} is cyclic. So F^{\times}=\langle c \rangle. Let x \in F and consider the sets

A:=\{a^3: \ \ a \in F\}, \ \  B:=\{x-a^3: \ \ a \in F\}, \ \ \ C:=\{a^3-x: \ \ a \in F\}.

Clearly \{0\} \cup \{c^{3m}: \ \ 1 \le m \le n\} \subseteq A and |A|=|B|=|C|. So |A| \ge n+1 and

|A|+ |B|+ |C| =3|A| \ge 3n+3 > |F|.

So at least two of the sets A,B,C have non-empty intersection. If A \cap B \neq \emptyset or A \cap C \neq \emptyset, then x=a^3+b^3 for some a,b \in F and we are done.
Now suppose that B \cap C \ne \emptyset. So there exist a,b \in F such that x-a^3=b^3-x and so 2x=a^3+b^3. Since, as given in the problem, \alpha^3=2 for some \alpha \ne 0, we have 2 \ne 0 and 2^{-1}=\alpha^{-3}. Hence

x=\alpha^{-3}(a^3+b^3)=(\alpha^{-1}a)^3+(\alpha^{-1}b)^3. \ \Box

Remark 2. Regarding the third case in the solution of Problem 2, notice that, in fact, we have

A= \{0\} \cup \{c^{3m}: \ \ 1 \le m \le n\}

and so |A|=n+1. The reason is that if c^k=c^{3m} for some integers k,m, then c^{k-3m}=1 and hence k-3m must be divisible by |F^{\times}|=3n implying that k is divisible by 3.

Advertisements

Maximum number of elements of the union of two proper subgroups of a finite group

Posted: December 2, 2018 in Elementary Algebra; Problems & Solutions, Groups and Fields
Tags: ,
0

Problem 1. Let G be a group and suppose that H, K are two subgroups of G. Show that if G=H \cup K, then either H=G or K=G.

Solution. If H \subseteq K or K \subseteq H, then H \cup K=G gives K=G or H=G and we are done. Otherwise, there exist h \in H \setminus K and k \in K \setminus H. But then hk \in G \setminus H \cup K, contradiction! \Box

So, as a result, if G is a finite group and H,K are two subgroups of G with H \ne G and K \ne G, then |H \cup K| \ne |G|. That raises this question: how large could |H \cup K| get? The following problem answers this question.

Problem 2. Let G be a finite group and suppose that H, K are two subgroups of G such that H \ne G and K \ne G. Show that \displaystyle |H \cup K| \le \frac{3}{4}|G|.

Solution. Recall that \displaystyle |HK|=\frac{|H||K|}{|H \cap K|} and thus \displaystyle \frac{|H||K|}{|H \cap K|} \le |G|. Hence \displaystyle |H \cap K| \ge \frac{|H| |K|}{|G|} and so

\displaystyle \begin{aligned}|H \cup K|=|H|+|K|-|H \cap K| \le |H|+|K|-\frac{|H| |K|}{|G|} =(a+b-ab)|G|, \ \ \ \ \ \ \ \ \ (*)\end{aligned}

where \displaystyle a:=\frac{|H|}{|G|} and \displaystyle b:=\frac{|K|}{|G|}.
Now, since H \ne G and K \ne G, we have [G:H] \ge 2 and [G:K] \ge 2, i.e. \displaystyle a \le \frac{1}{2} and \displaystyle b \le \frac{1}{2}. So if we let a':=1-2a and b':=1-2b, then a' \ge 0, \ b' \ge 0 and thus

\displaystyle a+b-ab=\frac{3}{4}-\frac{a'+b'+a'b'}{4} \le \frac{3}{4}.

The result now follows from (*). \ \Box

Example 1. The upper bound \displaystyle \frac{3}{4}|G| in Problem 2 cannot be improved, i.e. there exists a group G and subgroups H, K of G such that \displaystyle |H \cup K|=\frac{3}{4}|G|. An example is the Klein-four group G=\mathbb{Z}_2 \times \mathbb{Z}_2 and the subgroups H:=\{(0,0), (1,0)\} and K:=\{(0,0),(0,1)\}. Then |G|=4 and \displaystyle |H \cup K|=3=\frac{3}{4}|G|.

Example 2. We showed in Problem 1 that a group can never be equal to the union of two of its proper subgroups. But there are groups that are equal to the union of three of their proper subgroups. The smallest example, again, is the Klein-four group

\mathbb{Z}_2 \times \mathbb{Z}_2= \{(0,0), (1,0)\} \cup \{(0,0), (0,1)\} \cup \{(0,0),(1,1)\}.

Two elements of the same order of a group are conjugate, in somewhere!

Posted: November 24, 2018 in Elementary Algebra; Problems & Solutions, Groups and Fields
Tags: , ,
0

In this post, we give a nice little application of Cayley’s theorem.

Let G be a group and let g,h \in G. If g,h are conjugate in G, i.e. g=xhx^{-1} for some x \in G, then clearly g^n=1 if and only if h^n=1. So g,h have the same order. The converse however is false, i.e. if g,h \in G have the same order, that does not imply g,h are conjugate. For example, in an abelian group, two elements are conjugate if and only if they are equal but you can obviously have distinct elements of the same order in the group, e.g. in \mathbb{Z}/3\mathbb{Z}, both non-zero elements have the same order 3.

We are now going to show that although two elements of the same order of a group might not be conjugate in the group, but they are certainly conjugate in some larger group.

Problem. Let G be a group and suppose that g,h \in G have the same order. Show that there exists a group S \supseteq G such that g,h are conjugate in S.

Solution. By Cayley’s theorem, we can embed G into the symmetric group S:=\text{Sym}(G) using the injective group homomorphism f : G \to S defined by f(x)=\sigma_x \in S, where \sigma_x: G \to G is the permutation defined by \sigma_x(y)=xy for all y \in G. So we only need to show that \sigma_g, \sigma_h are conjugate in S. Well, let |g|=|h|=n. Then the cycle decomposition of \sigma_g, \sigma_h are in the form 

\sigma_g=(y_1, gy_1, \cdots , g^{n-1}y_1)(y_2, gy_2, \cdots , g^{n-1}y_2) \cdots

and 

\sigma_h=(y_1, hy_1, \cdots , h^{n-1}y_1)(y_2, hy_2, \cdots , h^{n-1}y_2) \cdots

So \sigma_g, \sigma_h have the same cycle type and hence they are conjugate in S. \ \Box

Groups satisfying (xy)^n=x^ny^n

Posted: November 11, 2018 in Elementary Algebra; Problems & Solutions, Groups and Fields
Tags: , , ,
0

Definition 1. Let n be an integer. A group G is called n–abelian if (xy)^n=x^ny^n for all x,y \in G.
In other words, G is n-abelian if the map f : G \to G defined by f(x)=x^n is a group homomorphism.

Definition 2. If G is both n-abelian and m-abelian, for some integers m,n, then G is also mn-abelian because then for x,y \in G we will have

(xy)^{mn}=((xy)^m)^n=(x^my^m)^n=x^{mn}y^{mn}.

So the set

\text{E}(G)=\{n \in \mathbb{Z}: \ \ (xy)^n=x^ny^n, \ \ \forall x,y \in G\},

i.e., the set of those integers n for which G is n-abelian, is a multiplicative subset of \mathbb{Z}. Clearly 0,1 \in \text{E}(G). The set \text{E}(G) is called the exponent semigroup of G.

Remark 1. Since (xy)^n=x(yx)^{n-1}y, we have (xy)^n=x^ny^n if and only if (yx)^{n-1}=x^{n-1}y^{n-1}. So a group G is n-abelian if and only if (yx)^{n-1}=x^{n-1}y^{n-1} or, equivalently, (xy)^{1-n}=x^{1-n}y^{1-n} for all x,y \in G. So a group G is n-abelian if and only if it is (1-n)-abelian. In other words, n \in \text{E}(G) if and only if 1-n \in \text{E}(G).

Example 1. Every abelian group is obviously n-abelian for all n. It is also clear that 2-abelian groups are abelian because xyxy=(xy)^2=x^2y^2=xxyy gives yx=xy. As the next two examples show, there exists a non-abelian n-abelian group for any n > 2.

Example 2. Let n \ge 3 be an odd integer and consider the Heisenberg group G:=H(\mathbb{Z}/n\mathbb{Z}), which is a non-abelian group (why?). We show that n, n+1 \in \text{E}(G), i.e. G is both n-abelian and (n+1)-abelian. To see that, let

g= \displaystyle \begin{pmatrix} 1 & a & b \\ 0 & 1 & c \\ 0 & 0 & 1 \end{pmatrix} \in G.

An easy induction shows that

\displaystyle g^m= \begin{pmatrix}1 & ma & mb + \frac{m(m-1)}{2}ac \\ 0 & 1 & mc \\ 0 & 0 & 1 \end{pmatrix}

for all integers m \ge 1. Thus g^n=I, the identity matrix, and so g^{n+1}=g, for all g \in G.
Hence I=(xy)^n=x^ny^n and xy=(xy)^{n+1}=x^{n+1}y^{n+1} for all x,y \in G proving that G is both n-abelian and (n+1)-abelian.

Remark 2.  Notice that, in Example 2, if n is even, then \displaystyle \frac{n(n-1)}{2} \ne 0 (as elements of \mathbb{Z}/n\mathbb{Z}) and so g^n is not always the identity element in this case. However, there’s a way to fix this, as the next example shows. But first, notice that H(\mathbb{Z}/n\mathbb{Z}) can also be viewed as the group of  triples

G:=\{(a,b,c): \ \ a,b,c \in \mathbb{Z}/n\mathbb{Z}\}

with multiplication defined by

(a,b,c)(a',b',c')=(a+a',b+b'+ac',c+c').

In the next example, we modify the above multiplication such that we get g^n=1 for all g \in G.

Example 3. Let n \ge 3 be any integer and consider the set G:=\{(a,b,c): \ \ a,b,c \in \mathbb{Z}/n\mathbb{Z}\}. Define multiplication in G by

(a,b,c)*(a',b',c')=(a+a',b+b'+2ac',c+c').

It’s easy to see that (G,*) is a non-abelian group. We show that n, n+1 \in \text{E}(G). Let g=(a,b,c) \in G. A quick induction shows that

g^m=(ma, mb+m(m-1)ac, mc)

for all integers m \ge 1. So g^n=(0,0,0)=1_G for all g \in G and thus 1_G=(xy)^n=x^ny^n for all x,y \in G proving that G is n-abelian.
Also, since g^{n+1}=g for all g \in G, we have xy=(xy)^{n+1}=x^{n+1}y^{n+1} and so G is (n+1)-abelian.

Problem 1. Let G be a group. Show that

i) if n, n+1 \in \text{E}(G) for some integer n, then x^n \in Z(G) for all x \in G

ii) if n, n+1,n+2 \in \text{E}(G) for some integer n, then G is abelian.

Solution. i) Let x,y \in G. We have

xyx^ny^n=xy(xy)^n=(xy)^{n+1}=x^{n+1}y^{n+1}

and so yx^n=x^ny.

ii) Let x,y \in G. By i), we have yx^n=x^ny and yx^{n+1}=x^{n+1}y. Thus

x^{n+1}y=yx^{n+1}=yx^nx=x^nyx

and so xy=yx. \ \Box

Problem 2. Let G be an n-abelian group and let x,y \in G. Show that

i) x^{n-1}y^n=y^nx^{n-1}

ii) (xyx^{-1}y^{-1})^{n(n-1)}=1

Solution. i) By Remark 1, (ab)^{n-1}=b^{n-1}a^{n-1} for all a,b \in G. Thus

\begin{aligned} x^{n-1}y^{n-1}=(yx)^{n-1}=((yxy^{-1})y)^{n-1}=y^{n-1}(yxy^{-1})^{n-1}=y^{n-1}yx^{n-1}y^{-1}=y^nx^{n-1}y^{-1} \end{aligned}

and the result follows.

ii) Again, using the Remark 1, we have

\begin{aligned} (xyx^{-1}y^{-1})^{n(n-1)}=((x(yx^{-1}y^{-1}))^{n-1})^n=((yx^{-1}y^{-1})^{n-1}x^{n-1})^n=(yx^{-(n-1)}y^{-1}x^{n-1})^n \\ =y^n(x^{-(n-1)}y^{-1}x^{n-1})^n=y^nx^{-(n-1)}y^{-n}x^{n-1}=1, \ \ \ \text{by i)}.  \ \Box \end{aligned}

Remark 3. Let G be an n-abelian group for some integer n \ge 2. An immediate result of Problem 2, ii), is that if either G is torsion-free or G is finite and \text{gcd}(n(n-1), |G|)=1, then G is abelian.

A simple property of subfields of R

Posted: September 23, 2018 in Elementary Algebra; Problems & Solutions, Groups and Fields
0

Problem.  Show that if \displaystyle F \subseteq \mathbb{R} is a field and x_1, \cdots , x_n are positive real numbers such that \sum_{i=1}^n x_i \in F and x_i^2 \in F for all i, then x_i \in F for all i.

Solution. The proof is by induction over n. There’s nothing to prove for n=1. For n\ge 2, since \sum_{i=1}^n x_i \in F, we have

\displaystyle \sum_{i=2}^n x_i \in F(x_1)=F + Fx_1

and thus, by the induction hypothesis, x_i \in F+ Fx_1 for all i \ge 2. So x_2=a+bx_1 for some a,b \in F.

If b=0, then x_2 \in F and so \sum_{i \ne 2}x_i \in F. Hence, by the induction hypothesis, x_i \in F for all i.

If a=0, then x_2=bx_1 (so b > 0 because x_1,x_2 > 0). Thus

\displaystyle \sum_{i=1}^n x_i = (b+1)x_1 + \sum_{i \ge 3} x_i \in F

and so, by the induction hypothesis, x_i \in F for all i.

If a, b \ne 0, then x_2^2=a^2+b^2x_1^2+2abx_1 gives x_1 \in F and so \sum_{i \ge 2} x_i \in F implying, again by the induction hypothesis,that x_i \in F for all i. \ \Box

Example. Show that \mathbb{Q}(\sqrt{2}+ \sqrt{5}+ \cdots +\sqrt{n^2+1})=\mathbb{Q}(\sqrt{2}, \sqrt{5}, \cdots , \sqrt{n^2+1}). for all integers n \ge 1.

Solution. Let F:=\mathbb{Q}(x_1 + \cdots + x_n), where x_i=\sqrt{i^2+1} for all i. Since \sum_{i=1}^n x_i \in F and x_i^2 \in F for all i, we have, by the above problem, x_i \in F for all i. Thus \mathbb{Q}(x_1, \cdots , x_n) \subseteq F and we are done because obviously F \subseteq \mathbb{Q}(x_1, \cdots , x_n).

Maximum order of abelian subgroups in a symmetric group

Posted: April 21, 2012 in Elementary Algebra; Problems & Solutions, Groups and Fields
Tags: , ,
0

For any set X, we denote by {\rm{Sym}}(X) the group of bijective maps from X to X.

Problem. Let \alpha : \mathbb{N} \longrightarrow [1, \infty) be any map which satisfies the following two conditions: \alpha(p) \geq p and \alpha(p+q) \geq \alpha(p) \alpha(q) for all p,q \in \mathbb{N}. Let X be a set with |X|=n. Prove that if G is an abelian subgroup of {\rm{Sym}}(X), then |G| \leq \alpha(n).

Solution.  The proof is by induction on n. If n=1, then |G|=1 \leq \alpha(1). Let X be a set with |X|= n \geq 2 and suppose that the claim is true for any set of size < n. Let G be an abelian subgroup of {\rm{Sym}}(X). Clearly gx=g(x), \ g \in G, x \in X, defines an action of G on X. Let X_1, \ldots , X_k be the orbits corresponding to this action and consider two cases.

Case 1. k=1: Fix an element x_1 \in X. Then X=X_1=Gx_1. Suppose that g_1x_1=x_1 for some g_1 \in G and let x \in X. Then x=gx_1 for some g \in G. Thus, since G is abelian, we have

x=gx_1=gg_1x_1=g_1gx_1=g_1x.

Hence g_1x=x for all x \in X and thus g_1=1. So the stabilizer of x_1 is trivial and therefore, by the orbit-stabilizer theorem, |G|=|X|=n \leq \alpha(n).

Case 2.  k \geq 2: Let |X_i|=n_i, \ i=1,2, \ldots, k. Clearly \sum_{i=1}^k n_i=n and, since k \geq 2, we have n_i < n for all i. For every g \in G and 1 \leq i \leq k let g_i=g|_{X_i}, the restriction of g to X_i, and put

G_i=\{g_i: \ g \in G\}.

Then g_i \in {\rm{Sym}}(X_i) and G_i is an abelian subgroup of {\rm{Sym}}(X_i). Thus, by the induction hypothesis

|G_i| \leq \alpha(n_i),

for all i. Now, define \varphi : G \longrightarrow \bigoplus_{i=1}^k G_i by \varphi(g)=(g_1, g_2, \ldots , g_k) for all g \in G. It is obvious that \varphi is one-to-one and so

|G| \leq |\bigoplus_{i=1}^k G_i|=\prod_{i=1}^k |G_i| \leq \prod_{i=1}^k \alpha(n_i) \leq \alpha(\sum_{i=1}^k n_i)=\alpha(n). \ \Box

Remark. The map \alpha: \mathbb{N} \longrightarrow [1, \infty) defined by \alpha(p)=3^{p/3}, for all p \in \mathbb{N}, satisfies both conditions in the above Problem. So if |X|=n and if G is an abelian subgroup of {\rm{Sym}}(X), then |G| \leq 3^{n/3}.

Degree of an irreducible factor of composition of two polynomials

Posted: November 17, 2011 in Elementary Algebra; Problems & Solutions, Groups and Fields
Tags: ,
0

Problem. Let F be a field and suppose that f(x),g(x), p(x) are three polynomials in F[x]. Prove that if both f(x) and p(x) are irreducible and p(x) \mid f(g(x)), then \deg f(x) \mid \deg p(x).

Solution. Let \mathfrak{m} and \mathfrak{n} be the ideals of F[x] generated by f(x) and p(x), respectively. Let E=F[x]/\mathfrak{m} and L = F[x]/\mathfrak{n}. Since both f(x) and p(x) are irreducible, E and L are field extensions of F. Now, define the map \varphi : E \longrightarrow L by \varphi(h(x) + \mathfrak{m})=h(g(x)) + \mathfrak{n}, for all h(x) \in F[x]. We first show that \varphi is well-defined. To see this, suppose that h(x) \in \mathfrak{m}. Then h(x)=f(x)u(x) for some u(x) \in F[x] and hence h(g(x)) = f(g(x))u(g(x)) \in \mathfrak{n}, because p(x) \mid f(g(x)). So \varphi is well-defined. Now \varphi is clearly a ring homomorphism and, since E is a field and \ker \varphi is an ideal of E, we must have \ker \varphi = \{0\}.
Therefore we may assume that F \subseteq E \subseteq L and hence

\deg p(x) = [L : F] = [L: E][E:F]=(\deg f(x))[L : E]. \ \Box

Older Entries