Solution Set 9: Part A

Benjamin Bakker Mathematics 25a Prof. Berger

November 26, 2003

A.1. Let (E, d) be a metric space, and let f : E → ℂ be a function. Write f(x) = a(x) + ib(x) where a, b are two functions from E to ℝ.

(1) prove that f is continuous if and only if a and b are continuous.

Solution. For any x, y ∈ ℂ, if |a(x) − a(y)| < ϵ and |b(x) − b(y)| < ϵ, then

|f(x) − f(y)| = \sqrt{|a(x) − a(y)|^{2} + |b(x) − b(y)|^{2}} < ϵ\sqrt{2}

and similarly, if |f(x) − f(y)| < ϵ, then by the above equality

|a(x) − a(y)| < ϵ and |b(x) − b(y)| < ϵ

It then follows that f is continuous if and only if a, b are. In one direction, for all ϵ > 0, if f is continuous, then for any x ∈ E there exists δ such that |f(x) − f(y)| < ϵ whenever d(x, y) < δ, in which case the above shows that |a(x) − a(y)| < ϵ and |b(x) − b(y)| < ϵ. The other direction is the same.

(2) prove that if f, g are two continuous functions from (E, d) to ℂ then f ± g and f · g are also continuous.

Solution. Let f(x) = a(x) + ib(x) and g(x) = c(x) + id(x). f ± g = (a ± c) + i(b ± d) is continuous if and only if a ± c and b ± d are. Similarly, fg = (ac − bd) + i(ad + bc) is continuous if and only if ac − bd and ad + bc are. Sums and products of continuous functions from a metric space into ℝ are continuous, so f ± g and fg are continuous.

A.2. If m ∈ ℤ_{≥1} let ϕ(m) = Card{1 ≤ x ≤ m, gcd(x, m) = 1}. If G is a group and if g ∈ G, the order of g is the smallest m ≥ 1 such that g^{m} = e. Don’t confuse this with the order of G which is Card(G).

(1) prove that the order of g is the order of the subgroup it generates in G (assume that G is finite).

Solution. The subgroup generated by g is H = {…, g^{−2}, g^{−1}, e, g, g^{2}, …}. g has finite order because G is finite; let n be the order of g. For any p ∈ ℤ, there exist q, r ∈ ℤ, 0 ≤ r ≤ n − 1 such that p = nq + r ⇒ g^{p} = g^{nq+r} = g^{r}, and H = {e, g, …, g^{n−1}}. The n elements e, g, …, g^{n−1} are distinct, for if g^{p} = g^{q} with 0 ≤ p, q ≤ n − 1 and p ≠ q, then g^{q−p} = e and 0 < |q − p| < n, so n is not the order of g. Thus, the order of H is n.

(2) prove that if G is any finite group and if g ∈ G then the order of g divides the order of G.

Solution. By the above, the order of the subgroup H generated by g is equal to the order of g. Since G is finite, we have by Lagrange’s thm that the order of g divides Card(G).

(3) prove that if n ≥ 1, then ∑_{d|n} ϕ(d) = n (here ∑_{d|n} means the sum over all divisors d of n).

Solution. Let S_{d} be the set of all integers from 1 to n whose greatest common divisor with n is d. Of course, for any 1 ≤ x ≤ n, gcd(x, n) divides n (and x), so ∑_{d|n} Card(S_{d}) = n. But gcd(x, n) = d if and only if gcd(x/d, n/d) = 1; x ∈ S_{d} can be anything from d (since d|x) to n, so 1 ≤ x/d ≤ n/d, and S_{d} = {1 ≤ y ≤ n/d| gcd(y, n/d) = 1} ⇒ Card(S_{d}) = ϕ(n/d). Factors of n always come in pairs, d and n/d, so n = ∑_{d|n} ϕ(n/d) = ∑_{d|n} ϕ(d).

(4) show that if G is a cyclic group of order n and d divides n, then there are ϕ(d) elements in g of order d.

Solution. Let G = (e, g, ⋯, g^{n−1}). If h = g^{k} satisfies x^{d} = e, then kd = mn for some m; since k ≤ n, we have m ≤ d. If p = gcd(m, d) ≠ 1, then d/p < d, and h^{d/p} = g^{(m/p)n} = e since m/p is an integer, and d is not the order of g. Conversely, if gcd(m, d) = 1, then gcd(k, n) = n/d; lcm(k, n) = kd, and therefore the order of h is d. It then follows that the number of elements of order d is equal to Card{1 ≤ m ≤ d| gcd(m, d) = 1} = ϕ(d).

(5) in (5)-(7) let K be a field and let G be a finite subgroup of (K^{∗}, ×) of order n. Prove that there are at most d elements g ∈ G such that g^{d} = 1.

Solution. An element g ∈ G satisfies g^{d} = 1 iff it is a root of x^{d} − 1. As shown in class, this polynomial has degree d and therefore has at most d roots in K.

(6) prove that there exists an element g ∈ G which is of order n.

Solution. We first want to show that the number of elements of degree d is no more than ϕ(d) for any d|n. If there is no element of order d, then this is trivial. If not, there exists an element g ∈ G of order d, and g generates a subgroup H of order d by (1), all of whose elements satisfy x^{d} = 1. By (5), these are the only elements that satisfy x^{d} = 1, so all elements of order d are contained in H, a cyclic group of order d, and the claim follows by (4). If there were no element of G of order n, then Card(G) ≤ ∑_{d|n} ϕ(d)−ϕ(n) = n−ϕ(n) by (3), and since ϕ(n) ≥ 1, we have a contradiction. Thus, G has an element of order n.

(7) prove that G is cyclic.

Solution. This follows immediately from (6).

(8) let G be the set of invertible elements in ℤ/24ℤ. Prove that G is not a cyclic group.

Solution. By inspection, the invertible elements are (\overline{1}, \overline{5}, \overline{7}, \overline{11}, \overline{13}, \overline{17}, \overline{19}, \overline{23})—actually, you can check by direct computation that the inverse of each invertible element is itself. There are then 7 elements of order 2, but ϕ(2) = 1, so G is not cyclic.

A.3. Let S^{1} be the set of complex numbers z such that |z| = 1 and let C_{n} be the set of complex numbers such that z^{n} = 1.

(1) prove that (S^{1}, ×) and (C_{n}, ×) are compact subgroups of ℂ^{∗}, ×.

Solution. We saw S^{1} on last week’s problem set, problem A.1.(3) (just identify (x, y) with x + iy). Note that the n distinct powers of e^{2πi/n}, 1, e^{2πi/n}, …, e^{2πi(n−1)/n}, all satisfy z^{n} = 1 and are therefore the only elements of C_{n}.

We know ℂ^{∗} = ℂ \ {0} is a group under multiplication, so we need only check that both S^{1} ⊂ ℂ^{∗} and C_{n} ⊂ ℂ^{∗} contain 1 and are closed under × and inversion; it is sufficient to show that both contain 1 and are closed under (x, y) ↦ xy^{−1}. Clearly 1 ∈ S^{1} and 1 ∈ C_{n}. If z, w ∈ S^{1}, then |zw^{−1}| = |z|/|w| = 1 so zw^{−1} ∈ S^{1}; if z, w ∈ C_{n}, then (zw^{−1})^{n} = z^{n}/w^{n} = 1 ⇒ zw^{−1} ∈ C_{n}. Finally, S^{1} is the image of the compact set [0, 1] ⊂ ℝ under the continuous homomorphism f : ℝ → ℂ given by f(t) = e^{2πit} and is therefore compact, while C_{n} is a finite union of points and therefore compact.

(2) are there any other ones?

Solution. No. Let G be a compact subgroup of (ℂ \ {0}, ×). If there is an element z ∈ G with |z| > 1, then z^{n} ∈ G for all n > 0, and since d(z^{n}, 0) = |z|^{n} ⟶ ∞, G is not compact (i.e., z^{n} contains no convergent subsequence); likewise, if |z| < 1, then z^{−1} ∈ G and |z^{−1}| > 1. Thus, G ⊂ S^{1}. Of course, we also have 1 ∈ G.

We showed in lecture that the only closed subgroups of ℝ are 0, αℤ, ℝ, where α ∈ ℝ. Since f is a continuous homomorphism and G ⊂ S^{1} is compact and therefore closed, f^{−1}(G) is a closed subgroup of ℝ—f^{−1}(G) is a subgroup since 1 ∈ G ⇒ 0 ∈ f^{−1}(G), and if x, y ∈ f^{−1}(G), f(xy^{−1}) = f(x)f(y)^{−1} ∈ G ⇒ xy^{−1} ∈ f^{−1}(G)). We know that f^{−1}(1) = ℤ ⊂ f^{−1}(G); either f^{−1}(G) = αℤ for some α ∈ ℝ, in which case 1 = αn for some n ∈ ℤ ⇒ f^{−1}(G) = \frac{1}{n}ℤ and G = C_{n}, or f^{−1}(G) = ℝ, in which case G = S^{1}.

A.3. If P (X) = X^{d} + a_{d−1}X^{d−1} + ⋯ + a_{0} ∈ ℂ[X], let R be the largest of the |z_{i}| where z_{1}, …, z_{d} are the roots of P in ℂ. Prove the following inequalities:

(1) if r > 0 satisfies r^{d} ≥ ∑_{i=0}^{d−1} |a_{i}|r^{i}, then R ≤ r.

Solution. If X is the root with largest norm |X| = R, then by the triangle inequality,

R^{d} = |P (X) − a_{d−1}X^{d−1} − ⋯ − a_{0}| ≤ |P (X)| + |a_{d−1}|R^{d−1} + ⋯ + |a_{0}| = |a_{d−1}|R^{d−1} + ⋯ + |a_{0}|

Suppose r > 0 satisfies r^{d} ≥ ∑_{i=0}^{d−1} |a_{i}|r^{i}. If r < R, then

\frac{|a_{d−1}|}{r} + ⋯ + \frac{|a_{0}|}{r^{d}} ≤ 1 and 1 ≤ \frac{|a_{d−1}|}{R} + ⋯ + \frac{|a_{0}|}{R^{d}}

⇒ \frac{|a_{d−1}|}{r} + ⋯ + \frac{|a_{0}|}{r^{d}} ≤ \frac{|a_{d−1}|}{R} + ⋯ + \frac{|a_{0}|}{R^{d}}

which is a contradiction since 1/r > 1/R. Thus, r ≥ R.

(2) R ≤ max(1, ∑_{i=0}^{d−1} |a_{i}|) (Montel)

Solution. If 1 ≥ ∑_{i=0}^{d−1} |a_{i}|, then by (1), R ≤ 1. If 1 < ∑_{i=0}^{d−1} |a_{i}|, then if R > ∑_{i=0}^{d−1} |a_{i}|, by the above

1 ≤ \frac{|a_{d−1}|}{R} + ⋯ + \frac{|a_{0}|}{R^{d}} < \frac{|a_{d−1}|}{R} + ⋯ + \frac{|a_{0}|}{R} < 1

which is a contradiction. Thus, R ≤ ∑_{i=0}^{d−1} |a_{i}| whenever 1 < ∑_{i=0}^{d−1} |a_{i}|, and

R ≤ max (1, ∑_{i=0}^{d−1} |a_{i}|)

(3) R ≤ 1 + max_{0≤k≤d} |a_{k}| (Cauchy)

Solution. If R > 1, let a = max_{1≤i≤d−1} |a_{i}|. From (2) we have

R ≤ |a_{d−1}| + \frac{|a_{d−2}|}{R} + ⋯ + \frac{|a_{0}|}{R^{d−1}} ≤ a ∑_{i=0}^{d−1} (\frac{1}{R})^{i} = a\frac{1 − R^{−d}}{1 − R^{−1}}

⇒ R − 1 ≤ a − aR^{−d} ≤ a ⇒ R ≤ 1 + a

If R ≤ 1, then the above inequality is satisfied trivially, so

R ≤ 1 + max_{0≤k≤d−1} |a_{k}|

(4) R ≤ |1 − a_{d−1}| + |a_{d−1} − a_{d−2}| + ⋯ + |a_{1} − a_{0}| + |a_{0}| (Montel)

Solution. Let Q(X) = (X − 1)P (X). The coefficients b_{i} of Q are

Q(X) = XP (X) − P (X) = X^{d+1} + (a_{d−1} − 1)X^{d} + ⋯ + (a_{0} − a_{1})X − a_{0}

The roots of Q just consist of the roots of P and 1. Thus, R ≥ 1, in which case we must have, by (2),

R ≤ ∑_{i=1}^{d} |b_{i}| = |1 − a_{d−1}| + |a_{d−1} − a_{d−2}| + ⋯ + |a_{1} − a_{0}| + |a_{0}|

(5) if a_{i} ∈ ℝ for all i and 1 ≥ a_{d−1} ≥ a_{d−2} ≥ ⋯ ≥ a_{0} ≥ 0 then R ≤ 1 (Kakeya)

Solution. We have |a_{i} − a_{i−1}| = a_{i} − a_{i−1} for all 0 ≤ i ≤ d, with a_{d} = 1. Thus, by (4),

R ≤ (1 − a_{d−1}) + (a_{d−1} − a_{d−2}) + ⋯ + (a_{1} − a_{0}) + a_{0} = 1

and all of the roots of P lie on the unit disc.