ROOTS ON A CIRCLE - PDF Document

Presentation Transcript

  1. ROOTS ON A CIRCLE KEITH CONRAD 1. Introduction The nth roots of unity obviously all lie on the unit circle (see Figure 1 with n = 7). Algebraic integers that are not roots of unity can also appear there. The quartic polynomial z4−2z3−2z +1 has two roots on the unit circle (see Figure 2). To explain this, we use the symmetry in the coefficients of z4−2z3−2z +1, which tells us that if α is a root then so is 1/α. Write the two real roots as α1and 1/α1. If α2is a non-real root then so are 1/α2and α2, neither of which is real or equal to α2, so they must be equal. The condition 1/α2= α2 is the same as |α2| = 1. 1 Figure 1. The 7th roots of unity. 1 Figure 2. The roots of z4− 2z3− 2z + 1. 1

  2. 2 KEITH CONRAD A famous polynomial with many, but not all, roots on the unit circle is Lehmer’s poly- nomial [3, p. 477] z10+ z9− z7− z6− z5− z4− z3+ z + 1, whose roots are plotted in Figure 3. There are 2 real roots (approximately .850 and 1.176) and 8 roots on the unit circle. How do you prove those non-real roots are really on the unit circle? From the symmetry in the coefficients, the roots come in reciprocal pairs, and since the coefficients are real the non-real roots come in complex conjugate pairs. If α is one of the non-real roots, then 1/α and α are also roots, but it is not immediately clear how to show 1/α = α, so |α| = 1. The argument we gave for the quartic does not apply in this case since there are too many non-real roots. 1 Figure 3. The roots of z10+ z9− z7− z6− z5− z4− z3+ z + 1. Generally, we want to explain how to count the number of roots of a polynomial that lie on the unit circle. For an irreducible polynomial in Q[z], having a root on the unit circle imposes a symmetry property on the polynomial and a constraint on its degree, as follows. Theorem 1.1. Let f(z) ∈ Q[z] be irreducible with degree n > 1. If f(z) has a root on the unit circle then n is even and znf(1/z) = f(z). Proof. Let α be a root of f(z) with |α| = 1. Since f has real coefficients, α = 1/α is also a root of f(z). The product znf(1/z) is a polynomial in Q[z] of degree n (its leading coefficient is f(0)) with root α, so by irreducibility of f(z), znf(1/z) = cf(z) for some nonzero rational number c. Setting z = 1, f(1) = cf(1). Since f(1) 6= 0 by our hypotheses, c = 1, so f(z) = znf(1/z). Setting z = −1, we get f(−1) = (−1)nf(−1). Since f(−1) 6= 0, (−1)n= 1, so n is even. In Section 2 we will describe a method of root counting on the unit circle that applies to all polynomials satisfying the conclusion of Theorem 1.1, whether or not they are irreducible in Q[z]. In Section 3 we will describe two further methods that apply to more general polynomials. (A result needing polynomials with all roots on the unit circle is in [4].) Finally, Section 4 extends the ideas to circles of radius other than 1. ? 2. The Palindromic Case It turns out that the conclusions in Theorem 1.1 essentially say f(z) can be expressed in terms of z + 1/z, whether or not the coefficients are rational.

  3. ROOTS ON A CIRCLE 3 Theorem 2.1. For a polynomial f(z) = cnzn+ cn−1zn−1+ ··· + c1z + c0with coefficients in C and degree n, the following conditions are equivalent: (1) the polynomial has palindromic coefficients: ck= cn−kfor all k, (2) znf(1/z) = f(z), (3) (if n is even) f(z) = zn/2g(z + 1/z) for a polynomial g with coefficients in C and degree n/2. Proof. It is simple to check that (1) and (2) are equivalent and that (3) ⇒ (2). To prove (2) ⇒ (3), set n = 2m and rewrite the equation znf(1/z) = f(z) as zmf(1/z) = (1/z)mf(z). Since f(z) has degree 2m, ?1 which is a polynomial in z and 1/z with degree m (this means the highest power of z and 1/z occurring is the mth power). The condition (1), which is equivalent to (2), tells us that the right side of (2.1) is has symmetric coefficients: ziand z−ihave equal coefficients for all i ≤ m. These properties are also true for c2m(z+1/z)m, which when expanded into a polynomial in z and 1/z has initial and final terms matching those in (2.1), so (1/z)mf(z)−c2m(z+1/z)m is a polynomial in z and 1/z of degree less than m with symmetric coefficients. Therefore by induction on the degree, we can write (1/z)mf(z) − c2m(z + 1/z)m= h(z + 1/z) where h(z) ∈ C[z] and either h = 0 or degh < m. Now add c2m(z + 1/z)mto both sides. We will call a polynomial of degree n “palindromic” when its coefficients satisfy (1), and hence also (2) and (if n is even) (3). ?m zm−1+c0 c1 f(z) = c2mzm+ c2m−1zm−1+ ··· + cm+ ··· + (2.1) zm, z ? Remark 2.2. If f(z) is palindromic of odd degree n then z2nf(1/z2) = f(z2), so f(z2) is palindromic of even degree 2n. Also the condition znf(1/z) = f(z) forces f(−1) = 0, so f(z) = (z+1)f1(z), where zn−1f1(1/z) = f1(z), so f1(z) is palindromic of even degree n−1 and thus f(z) = (z + 1)z(n−1)/2g(z + 1/z) where degg = (n − 1)/2. Example 2.3. The polynomial z4− 2z3− 2z + 1 is palindromic of degree 4. Divide by z2 to get z2− 2z − 2/z + 1/z2. Subtract (z + 1/z)2: ? This is −2(z + 1/z) − 2, so add (z + 1/z)2to both sides and multiply by z2: ? Example 2.4. The polynomial z6− z4− 2z3− z2+ 1 is palindromic of degree 6. Divide by z3to get z3− z − 2 − 1/z + 1/z3. Now subtract (z + 1/z)3: ? Next add 4(z + 1/z): ? ? ? ?2 z2− 2z −2 z+1 z +1 = −2z − 2 −2 − z. z2 z ! ?2 ? ? z +1 z +1 z4− 2z3− 2z + 1 = z2 − 2 − 2 . z z ? ? ?3 z3− z − 2 −1 z+1 z +1 = −4z − 2 −4 − z. z3 z ? ? ?3 ? ? z3− z − 2 −1 z+1 z +1 z +1 − = −2. + 4 z3 z z

  4. 4 KEITH CONRAD Bringing the powers of z + 1/z to the right side and multiplying through by z3, we get ? Example 2.5. The polynomial z8−z5−z4−z3+1 is palindromic of degree 8. Divide by z4to get z4− z − 1 − 1/z + 1/z4. Now subtract (z + 1/z)4: ? Next add 4(z + 1/z)2: ? Add z + 1/z: ? Bringing all the powers of z +1/z to the right side and multiplying through by z4, we have ? In Theorem 2.1, we made no assumptions about irreducibility or that the coefficients are rational. (The theorem was, however, inspired by the situation of Theorem 1.1 where f(z) is irreducible in Q[z].) Theorem 2.1 provides a bijection between the polynomials g(z) in C[z] of degree m and the palindromic polynomials f(z) in C[z] of degree 2m. Obviously f is monic if and only if g is monic, and the nature of the recursive process to obtain g from f, as shown in Examples 2.3, 2.4, and 2.5, shows f has integral coefficients if and only if g has integral coefficients. If f(z) is irreducible in Q[z] then g(z) is also irreducible in Q[z] because the equation f(z) = zmg(z+1/z) forces f to factor nontrivially if g does. However, if g(z) is irreducible in Q[z] then it does not follow that f(z) is irreducible. For example, if g(z) = z2− 5 then z2g(z + 1/z) = (z2− z − 1)(z2+ z − 1). Here is a link between roots on the unit circle and real roots. Theorem 2.6. Let f(z) = cnzn+ cn−1zn−1+ ··· + c1z + c0have even degree n = 2m and satisfy ck= cn−kfor all k. Write f(z) = zmg(z +1/z) where degg = m. The roots of f on the unit circle, considered as pairs of reciprocals, correspond to the roots of g in the interval [−2,2] by {α,1/α} ↔ α + 1/α. Proof. We have f(z) = 0 if and only if g(z + 1/z) = 0. (Note f(0) = c0= cn6= 0.) If |z| = 1, so z = cosθ + isinθ, then z + 1/z = 2cosθ lies in the interval [−2,2]. Conversely, if −2 ≤ t ≤ 2, so t = 2cosθ for some angle θ, then t = z + 1/z for the two numbers z = cosθ ± isinθ (which are really one number when t = ±2, namely z = 1 for t = 2 and z = −1 for t = −2). Setting z = ±1 in the equation f(z) = zmg(z + 1/z), we get f(±1) = ±g(±2). Since we are usually interested in polynomials f(z) that are irreducible over Q with degree greater than 1, f(±1) will not be 0, so g(z) will not vanish at ±2. Therefore the endpoints of [−2,2] will not really matter when we talk about roots, although we should specify that a root of g(z) is in (−2,2), not just [−2,2], to be sure it has the form z + 1/z for two values of z. ! ?3 ? ? z +1 z +1 z6− z4− 2z3− z2+ 1 = z3 − 4 + 2 . z z ? ? ?4 z4− z − 1 −1 z+1 z +1 = −4z2− z − 7 −1 z−4 − z2. z4 z ? ? ?4 ? ?2 z4− z − 1 −1 z+1 z +1 z +1 = −z + 1 −1 − + 4 z. z4 z z ? ? ?4 ? ?2 ? ? z4− z − 1 −1 z+1 z +1 z +1 z +1 − + 4 + = 1. z4 z z z ! ?4 ? ?2 ? ? z +1 z +1 z +1 z8− z5− z4− z3+ 1 = z4 − 4 − + 1 . z z z ?

  5. ROOTS ON A CIRCLE 5 Remark 2.7. The multiplicity of a root of g in (−2,2) equals the multiplicity of the corresponding root of f on the unit circle, and if 2 or −2 is a root of g with multiplicity k then 1 or −1 is a root of f with multiplicity 2k. Example 2.8. The polynomial z4−2z3−2z+1 from Figure 2 is palindromic. By Example 2.3, ? so the roots of z4−2z3−2z+1 on the unit circle are related to the real roots of w2−2w−2 in [−2,2]. This quadratic has roots ≈ −.732 and 2.732. One of them is in (−2,2), so there are two roots of the quartic on the unit circle. ! ?2 ? ? z +1 z +1 z4− 2z3− 2z + 1 = z2 − 2 − 2 , z z Example 2.9. The palindromic polynomial z6− z4− 2z3− z2+ 1 can be written as ? ! ?3 ? ? z +1 z +1 z6− z4− 2z3− z2+ 1 = z3 − 4 − 2 z z by Example 2.4, so the roots of z6− z4− 2z3− z2+ 1 on the unit circle (see Figure 4) are related to the roots of w3− 4w − 2 in [−2,2]. This cubic has roots ≈ −1.675, −.539, and 2.214. Two of the roots of w3−4w−2 are in (−2,2) so z6−z4−2z3−z2+1 has four roots on the unit circle. 1 Figure 4. The roots of z6− z4− 2z3− z2+ 1. Example 2.10. The palindromic polynomial z8− z5− z4− z3+ 1 can be written as ? by Example 2.5, so roots of z8−z5−z4−z3+1 on the unit circle (see Figure 5) are related to the roots of w4− 4w2− w + 1 in [−2,2]. This quartic has roots ≈ −1.764, −.693, .396, 2.061. Three of the roots of w4−4w2−w +1 are in (−2,2) so z8−z5−z4−z3+1 has six roots on the unit circle. ! ?4 ? ?2 ? ? z +1 z +1 z +1 z8− z5− z4− z3+ 1 = z4 − 4 − + 1 z z z Example 2.11. To prove Lehmer’s polynomial z10+ z9− z7− z6− z5− z4− z3+ z + 1 has 8 roots on the unit circle, we express this polynomial in terms of z +1/z. Carrying out

  6. 6 KEITH CONRAD 1 Figure 5. The roots of z8− z5− z4− z3+ 1. the method of Examples 2.3, 2.4, and 2.5 on Lehmer’s polynomial, it is equal to ? The polynomial w5+ w4− 5w3− 5w2+ 4w + 3 has all real roots, which are approximately −1.886, −1.468, −.584, .913, 2.026. Since 4 of the roots are in (−2,2), there are 8 roots of Lehmer’s polynomial on the unit circle. Lehmer does not say in [3] how he determined that his polynomial has all but two roots on the unit circle, but I suspect it was by the method we just used. This method appears in [1, p. 297] and [2, Prop. 8]. ! ?5 ? ?4 ? ?3 ? ?2 ? ? z +1 z +1 z +1 z +1 z +1 z5 − 5 − 5 + + 4 + 3 . z z z z z A real number α is called a Salem number if α > 1, α is the root of a monic polynomial in Z[x] whose other roots include 1/α, and all further roots are on the unit circle. The root of Lehmer’s polynomial that is greater than 1 is a Salem number and it is conjectured to be the smallest Salem number. The paper [1] discusses many places where Salem numbers occur in mathematics and [5, Sect. 3.4] puts Lehmer’s polynomial into the general setting of arithmetic dynamics. So far our examples have had all but two roots on the unit circle and the remaining two roots are real. Is there an example where f(z) is irreducible in Q[z] and all but two of its roots are on the unit circle and these other two roots are not real? No. Such a situation requires g(z) to have all but one root in [−2,2] and therefore its remaining root must be real since g(z) has real coefficients. When t is real and outside [−2,2], the solutions to z + 1/z = t are both real (and reciprocals of each other). Let’s try to get an example with roots on the unit circle where all but four roots are on the unit circle and those other four roots are not real. A minimal example would be f(z) = z3g(z + 1/z) where degg = 3 with g having one root in [−2,2] and its other two roots not being real. Example 2.12. The polynomial g(z) = z3−z−1 has one real root, which is approximately 1.32 and is in (−2,2). Define ? ? z +1 f(z) = z3g = z6+ 2z4− z3+ 2z2+ 1, z

  7. ROOTS ON A CIRCLE 7 which happens to be irreducible in Q[z]. Since g has 1 root in (−2,2) and 2 non-real roots, f has 2 roots that are on the unit circle and 4 roots that are off the unit circle and are not real. See Figure 6. 1 Figure 6. The roots of z6+ 2z4− z3+ 2z2+ 1. Theorem 2.6 is easy to apply to a specific palindromic polynomial of even degree, but not to a family of palindromic polynomials (or a palindromic polynomial of odd degree). An example of such a family isPn a-family-of-polynomials-whose-zeros-all-lie-on-the-unit-circle/. ?n ?λk(n−k)zkfor n ∈ Z+, which has all of its roots k=0 k on the unit circle when λ ∈ [0,1]. See https://mathoverflow.net/questions/299304/ 3. The General Case Since Theorem 2.6 only works on palindromic polynomials, we need new ideas to count roots on the unit circle of nonpalindromic polynomials. Example 3.1. The polynomial f(z) = z10+5z8+z7+12z6+2z5+13z4+z3+8z2−z+2, which is not palindromic, appears to have 4 roots on the unit circle in Figure 7. How can we verify there are 4 roots of f(z) on the unit circle? One method is to factor f(z) in Q[z]. If it really has roots on the unit circle then it must be reducible in Q[z] since it is not palindromic. We can apply Theorem 2.6 to the irreducible factors of f(z) in Q[z]; the factors with roots on the unit circle must be palindromic of even degree. Using a computer algebra package, f(z) factors in Q[z] as (z2+ z + 2)(z8− z7+ 4z6− z5+ 5z4− z3+ 4z2− z + 1), where the first factor has no roots on the unit circle by the quadratic formula and the second factor is palindromic with even degree. We could apply the recursive method in the proof of Theorem 2.1 to write the second factor as z4g(z + 1/z) for some g(z) and then count roots of g(z) in [−2,2] in order to count the roots of f(z) on the unit circle by Theorem 2.6. However, rather than show further details, let’s admit that it would be good to have a method that can be applied to general polynomials without having to factor them. We will describe two methods, one told to me by Fran¸ cois Brunault and the other by Fernando Rodriguez-Villegas. (3.1)

  8. 8 KEITH CONRAD 1 Figure 7. The roots of z10+ 5z8+ z7+ 12z6+ 2z5+ 13z4+ z3+ 8z2− z + 2. Brunault’s observation is that if f(z) of degree n > 0 in R[z] does not have 0, 1, or −1 as roots (dividing f(z) by enough powers of z, z−1, and z+1 can put us in that situation) then the (monic) polynomial F(z) := gcd(f(z),znf(1/z)) fits the hypotheses of Theorem 2.6 and roots of f(z) on the unit circle are the same as roots of F(z) on the unit circle (although not necessarily with the same multiplicity), so we can use Theorem 2.6 to count roots of F(z) on the unit circle in order to make that count for f(z). Theorem 3.2. Let f(z) ∈ R[z] be nonconstant of degree n without 0, 1, or −1 as roots. The polynomial F(z) := gcd(f(z),znf(1/z)) has even degree and is palindromic, and a number on the unit circle is a root of f(z) if and only if it is a root of F(z). Proof. Since F(z) is a factor of f(z) and 0, 1, and −1 are not roots of f(z), they are not roots of F(z) either. For nonzero α in C we have F(α) = 0 if and only if f(α) = 0 and f(1/α) = 0, so F(α) = 0 if and only if F(1/α) = 0: the roots of F(z) always come in reciprocal pairs {α,1/α}, where α 6= 1/α since F(z) does not have 0, 1, or −1 as roots. When α is on the unit circle, 1/α = α. Since f(z) has real coefficients, f(α) = f(α). Therefore when α is on the unit circle, f(1/α) = 0 ⇔ f(α) = 0 ⇔ f(α) = 0, so F(α) = 0 if and only if f(α) = 0. To prove F(z) has even degree and is palindromic, suppose α is a root of F(z), so 1/α is a root and α 6= 1/α. Factor the biggest powers of α and 1/α out of f(z): f(z) = (z − α)i(z − 1/α)jh(z) where i ≥ 1 and j ≥ 1 and h(z) does not have α or 1/α as roots. (Possibly i 6= j.) Computing degrees tells us n = i + j + degh, so znf(1/z) = zi+j+degh(1/z − α)i(1/z − 1/α)jh(z) = zi(1/z − α)izj(1/z − 1/α)jzdeghh(1/z) = (1 − αz)i(1 − z/α)jzdeghh(1/z) = (−α)i(z − 1/α)i(−1/α)j(z − α)jzdeghh(1/z) = (z − α)j(z − 1/α)i((−α)i(−1/α)j)zdeghh(1/z), where the polynomial zdeghh(1/z) does not have α or 1/α as roots. Therefore in C[z], z−α and z − 1/α are factors of F(z) with the same multiplicity min(i,j). Thus F(z) = (z − α)min(i,j)(z − 1/α)min(i,j)gcd(h(z),zdeghh(1/z)).

  9. ROOTS ON A CIRCLE 9 So each root pair {α,1/α} of F(z) contributes the factor (z − α)min(i,j)(z − 1/α)min(i,j)to F(z). For a ≥ 1 in Z and α 6∈ {0,1,−1} the product p(z) = (z − α)a(z − 1/α)aof degree 2a satisfies z2ap(1/z) = p(z). Since F(z) is a product of such (pairwise relatively prime) factors, degF is even and zdegFF(1/z) = F(z), so F(z) is palindromic by Theorem 2.1. ? We can calculate F(z) by Euclid’s algorithm in R[z], so if f(z) ∈ Q[z] then F(z) ∈ Q[z]. Example 3.3. Let f(z) = z10+ 5z8+ z7+ 12z6+ 2z5+ 13z4+ z3+ 8z2− z + 2 from Example 3.1. From Figure 7 it seems to have 4 roots on the unit circle. To verify this, first note 0, 1, and −1 are not roots (f(0) = 2, f(1) = 44 and f(−1) = 38). We have z10f(1/z) = 2z10− z9+ 8z8+ z7+ 13z6+ 2z5+ 12z4+ z3+ 5z2+ 1, and using Euclid’s algorithm we get F(z) = gcd(f(z),z10f(1/z)) = z8− z7+ 4z6− z5+ 5z4− z3+ 4z2− z + 1, which has even degree and is palindromic.1By the proof of Theorem 2.1 we have F(z) = z4g(z+1/z) for g(z) = z4−z3+2z−1. The polynomial g(z) has two real roots, approximately −1.153 and .535, which are both in the interval (−2,2), so F(z) has four roots on the unit circle by Theorem 2.6 and thus f(z) does as well by Theorem 3.2. Example 3.4. The polynomial f(z) = z10−z6+4z4−3z2+2 is not palindromic and does not have 0, 1, or −1 as roots. To count the roots of f(z) on the unit circle, we compute F(z) = gcd(f(z),z10f(1/z)) = z8− 2z6+ 3z4− 2z2+ 1. This is palindromic of degree 8, so F(z) = z4g(z + 1/z) where it turns out that g(z) = z4−6z2+9. The polynomial g has two double roots, approximately ±1.732 (exactly, these are ±√3). Both roots are in (−2,2), so each one leads to two double roots of F(z) on the unit circle by solving z + 1/z = w for z where w is a root of g. Example 3.4 is the first time that we have met an example where g(z) has a repeated root. Example 3.5. Let f(z) = z6+ iz5+ (3 + i)z4+ (1 + i)z3+ (1 + 3i)z2+ z + i. Here the coefficients are complex. The roots are plotted in Figure 8 and there appear to be two roots on the unit circle. Although f(z) 6= 0 at z = 0,1, and −1, we are not justified in applying Theorem 3.2 since f(z) does not have real coefficients. Even though gcd(f(z),z6f(1/z)) makes sense, it is 1 and therefore its (empty set of) roots do not help us count roots of f(z) on the unit circle. And gcd(f(z),z6f(1/z)) does not help either since, in this case, z6f(1/z) = −if(z).2 But f(z)f(z) has real coefficients and is palindromic: f(z)f(z) = z12+ 7z10+ 4z9+ 14z8+ 16z7+ 14z6+ 16z5+ 14z4+ 4z3+ 7z2+ 1 This is z6g(z + 1/z) where g(z) = z6+ z4+ 4z3− 5z2+ 4z − 2. There are two real roots of g(z) in [−2,2], approximately −1.850 and .684, so f(z)f(z) has four roots on the unit circle. The roots of f(z) and f(z) are complex conjugate to each other and f(z)f(z) has no repeated roots, so f(z) has two roots on the unit circle. 1We have now rediscovered the second factor of f(z) in (3.1), but without having to factor f(z). 2The “double conjugate” f(z) is the polynomial with coefficients conjugate to f(z) while f(z) and f(z) are not polynoimals in z.

  10. 10 KEITH CONRAD 1 Figure 8. The roots of z6+ iz5+ (3 + i)z4+ (1 + i)z3+ (1 + 3i)z2+ z + i. Rodrigues-Villegas’s suggestion for how to find roots of a polynomial on the unit circle is to apply a M¨ obius transformation to pass between the unit circle and the real line. The M¨ obius transformation M(z) =z − i z + i, which is illustrated in Figure 9, sends the upper half-plane onto the open unit disc and the real line onto the unit circle without the point 1 (although you could say ∞ is sent to 1). Its inverse is M−1(z) =i(1 + z) 1 − z which sends the unit circle without 1 onto the real line. z + 1 i(z − 1), = M(z) =z−i z+i 1 Figure 9. The M¨ obius transformation M(z) = (z − i)/(z + i). For a polynomial f(z) of degree n > 0 (where f(z) need not be palindromic and n need not be even), compose f(z) with M(z) and then multiply by (z + i)nto clear out the

  11. ROOTS ON A CIRCLE 11 denominator: define ?z − i ? f∗(z) = (z + i)nf(M(z)) = (z + i)nf (3.2) . z + i A real root of f∗(z) is transformed by M(z) into a root of f(z) on the unit circle. Conversely, every root of f on the unit circle other than 1 has the form (z − i)/(z + i) for some real number z that is a root of f∗. Therefore counting roots of f on the unit circle is the same as counting real roots of f∗as long as we remember to check separately whether or not 1 is a root of f (which is easy). There is no special role for the interval [−2,2], we don’t have to double the count when passing from real roots of the auxiliary polynomial to roots of f on the unit circle, and it doesn’t matter whether or not f itself has real coefficients. Writing f∗(z) = a(z)+ib(z) where a(z) and b(z) have real coefficients, a real root of f∗(z) is the same thing as a common real root of a(z) and b(z), that is, a root of the polynomial gcd(a(z),b(z)). Thus counting roots of f(z) on the unit circle is the same as checking if f(1) = 0 and counting real roots of gcd(a(z),b(z)). Example 3.6. Let f(z) = z4− 2z3− 2z + 1, from Example 2.8, so f(1) 6= 0. We have f∗(z) = (z + i)4f z + i Here b(z) = 0. There are 2 real roots of a(z) = f∗(z) (approximately ±.6812; this isn’t related to the Golden ratio, which is 1.61803...), so f(z) has 2 roots on the unit circle. ?z − i ? = −2z4− 12z2+ 6 = −2(z4+ 6z2− 3). Example 3.7. Let f(z) = z6− z4− 2z3− z2+ 1, from Example 2.9, so f(1) 6= 0. Since f∗(z) = (z + i)6f z + i again b(z) = 0 and a(z) = f∗(z). The polynomial a(z) has 4 real roots, so f(z) has 4 roots on the unit circle. ?z − i ? = −2z6− 38z4+ 26z2− 2 = −2(z6+ 19z4− 13z2− 1), Example 3.8. For the polynomial f(z) = z6+ 2z4− z3+ 2z2+ 1 from Example 2.12, f(1) 6= 0 and f∗(z) = 5z6− 29z4+ 23z2− 7. Once again b(z) = 0. The polynomial a(z) = f∗(z) has 2 real roots, so f(z) has 2 roots on the unit circle. Example 3.9. For the polynomial f(z) = z8−z5−z4−z3+1 from Example 2.10, f(1) 6= 0 and f∗(z) = −z8− 64z6+ 134z4− 56z2+ 3. Once more b(z) = 0. The polynomial a(z) = f∗(z) has 6 real roots, so f(z) has 6 roots on the unit circle. Example 3.10. For Lehmer’s polynomial L(z) = z10+z9−z7−z6−z5−z4−z3+z +1, L(1) 6= 0 and L∗(z) = (z + i)10f z + i Yet again, b(z) = 0. There are 8 real roots of a(z) = L∗(z), so L(z) has 8 roots on the unit circle. ?z − i ? = −z10− 149z8+ 518z6− 314z4+ 43z2− 1.

  12. 12 KEITH CONRAD Example 3.11. We now turn to f(z) = z10+5z8+z7+12z6+2z5+13z4+z3+8z2−z+2, from Example 3.1. It is non-palindromic and seems to have 4 roots on the unit circle, with f(1) 6= 0. We counted its roots on the unit circle in Example 3.3 by using Theorem 3.2. To carry out this count using a M¨ obius transformation instead, f∗(z) = (44z10−198z8+448z6−548z4+260z2−38)+i(22z9−88z7+180z5−184z3+38z) where b(z) is (finally) not 0. Since gcd(a(z),b(z)) = 22z8−88z6+180z4−184z2+38 = b(z)/z, which has 4 real roots, f(z) has 4 roots on the unit circle. Example 3.12. Let f(z) = zn− 1, so f(1) = 0 and f∗(z) = (z + i)n− (z − i)n. Since the roots of f(z) are all on the unit circle, f∗(z) must have all real roots. Examples of the decomposition of f∗(z) as a(z) + ib(z) are given in Table 1. Unlike before, now it is a(z) that is always 0. The roots of b(z) are all real. In fact its roots are the numbers cot(πk/n) for 1 ≤ k ≤ n − 1. n a(z) 1 0 2 0 3 0 4 0 −8z3+ 8z 5 0 −10z4+ 20z2− 2 6 0 −12z5+ 40z3− 12z Table 1. Polynomials a(z) and b(z) for zn− 1. b(z) −2 −4z −6z2+ 2 Example 3.13. Let f(z) = z10−z6+4z4−3z2+2 which is not palindromic and f(1) 6= 0. In Example 3.4 we showed f(z) has four (double) roots on the unit circle. To show this using a M¨ obius transformation, f∗(z) = (3z10− 87z8+ 678z6− 678z4+ 87z2− 3) + i(2z9− 56z7+ 396z5− 56z3+ 2z). We have gcd(a(z),b(z)) = z8−28z6+198z4−28z2+1 = b(z)/(2z). Since 1 is not a root of f(z), the roots of f(z) on the unit circle are in bijection with the real roots of gcd(a(z),b(z)). The polynomial gcd(a(z),b(z)) has degree 8 and 4 real roots that are each double roots, so f(z) has 4 roots on the unit circle and they are each a double root. Example 3.14. Let f(z) = z6+ iz5+ (3 + i)z4+ (1 + i)z3+ (1 + 3i)z2+ z + i, a non- palindromic polynomial with f(1) 6= 0. We saw in Example 3.5 that f(z) has two roots on the unit circle by looking at f(z)f(z). This can be done with a M¨ obius transformation, as follows. Since f∗(z) = (1 + i)(7z6− 6z5− 13z4+ 12z3+ 9z2− 14z − 3), a(z) and b(z) both equal 7z6−6z5−13z4+12z3+9z2−14z −3, which has two real roots. Therefore f(z) has two roots on the unit circle. Since we often saw in the examples that b(z) = 0, it is natural to ask what makes that happen (or what makes a(z) = 0). Theorem 3.15. For f(z) =Pn k=0ckzkof degree n, write f∗(z) = a(z) + ib(z), where a(z) and b(z) have real coefficients.

  13. ROOTS ON A CIRCLE 13 (1) f(z) has real coefficients if and only if f∗(−z) = (−1)nf∗(z). Concretely: when n is even, f(z) is real if and only if a(z) is even and b(z) is odd, and when n is odd, f(z) is real if and only if a(z) is odd and b(z) is even. (2) a(z) = 0 if and only if f(z) = −znf(1/z), while b(z) = 0 if and only if f(z) = znf(1/z). Concretely, a(z) = 0 if and only if ck= −cn−kfor all k, while b(z) = 0 if and only if ck= cn−kfor all k. (3) If 1 is a root of f with multiplicity m then deg(f∗) = n − m. In particular, f∗has degree n if and only if f(1) 6= 0. (4) The leading coefficient of f is f∗(−i)/(−2i)n. (5) f has coefficients in Q(i) if and only if f∗has coefficients in Q(i). (6) f has coefficients in Z[1/2,i] if and only if f∗has coefficients in Z[1/2,i]. Part 3 explains why b(z) for zn− 1 in Table 1 has degree n − 1 rather than n. Proof. This will involve a bit of careful computations with complex conjugation. (1): To say f(z) has real coefficients is equivalent to f(z) = f(z). This is equivalent to f(M(z)) = f(M(z)). Since M(z) = M(−z) by a direct calculation, ? so f(z) has real coefficients if and only if f∗(−z) = (−1)n(z + i)nf(M(z)) = (−1)nf∗(z). In terms of a(z) and b(z), f∗(−z) = a(−z)−ib(−z), so f(z) has real coefficients if and only if a(−z) = (−1)na(z) and b(−z) = (−1)n−1b(z). (2): The equations f∗(z) = a(z) + ib(z) and f∗(z) = a(z) − ib(z) let us solve for a(z) and b(z): a(z) =f∗(z) + f∗(z) 2 Therefore a(z) = 0 if and only if f∗(z) = −f∗(z) and b(z) = 0 if and only if f∗(z) = f∗(z). For ε = ±1, the equation f∗(z) = εf∗(z) is equivalent to (3.3) (z + i)nf(M(z)) = ε(z + i)nf(M(z)). ? (−z − i)n=(−1)nf∗(−z) f∗(−z) (−z + i)n f∗(−z) f(M(z)) = f(M(−z)) = = , (z + i)n b(z) =f∗(z) − f∗(z) and . 2i Since M(z) = M(−z) = 1/M(z), (3.3) is the same as f(1/M(z)) = ε(z + i)n (3.4) (z − i)nf(M(z)). Replacing z with M−1(z) = (z + 1)/(i(z − 1)) in (3.4), it becomes znf(1/z) = εf(z). For ε = 1 we get the condition for when b(z) = 0 and for ε = −1 we get the condition for when a(z) = 0. (3): Write f(z) = (z −1)mq(z), where q(1) 6= 0. The operation ff∗is multiplicative, so f∗(z) = ((z − 1)∗)mq∗(z) = (−2i)mq∗(z). By an explicit calculation with polynomials, if q(z) has degree d then the coefficient of zdin q∗(z) is q(1) 6= 0, so q∗(z) has the same degree as q. (4), (5), (6): These are explained by the formulas connecting f(z) and f∗(z): ?z − i ? ?i(z − 1) ?n ? ? z + 1 i(z − 1) f∗(z) = (z + i)nf f∗ (3.5) and f(z) = . z + i 2

  14. 14 KEITH CONRAD The second formula is derived by replacing z with M−1(z) = (z + i)/(i(z − 1)) in the definition f∗(z) = (z + i)nf(M(z)). ? Is every polynomial F(z) of the form f∗(z) for some f? There is one constraint F has to satisfy, by the leading coefficient formula in the previous theorem: F(−i) 6= 0. This is the only obstruction. Corollary 3.16. For a polynomial F(z) with degree N that satisfies F(−i) 6= 0, the poly- nomials f(z) that satisfy f∗(z) = F(z) are ?i(z − 1) for m ≥ 0. In particular, there is a unique f(z) of the same degree as F(z) such that f∗(z) = F(z). ?N+m ? ? z + 1 i(z − 1) F 2 Proof. Since deg(f∗) ≤ degf, f needs to have degree at least N. If f∗ and f2(z) have the same degree then f1(z) = f2(z). Since (i(z − 1)/2)∗= 1, it suffices to show the polynomial ?i(z − 1) has degree N and satisfies f∗= F. Its degree is certainly at most N and the coefficient of zNis (i/2)NF(−i) 6= 0, so the degree is N. The reader can check this polynomial satisfies f∗(z) = F(z). 1(z) = f∗ 2(z) and f1(z) ?N ? ? z + 1 i(z − 1) F 2 ? On polynomials of a fixed degree, f(z)f∗(z) is a bijection. While it’s true that if f(z) has coefficients in Z[i] then f∗(z) has coefficients in Z[i], the converse is false in general. Example 3.17. When F(z) = z4− 4z2+ 2, the solution to f∗(z) = F(z) with degree 4 is ?i(z − 1) In general, if F(z) =PN ?i(z − 1) ?4 k=0akzkthen ?N ? ? z + 1 i(z − 1) 7 16z4−1 4z3+5 8z2−1 4z +7 F = 2 16 ? ? N X =iN z + 1 i(z − 1) ak(−i)k(z + 1)k(z − 1)N−k, F 2N 2 k=0 and asking for this to have z-coefficients in Z[i] amounts to some 2-power congruence con- ditions on linear combinations of the ak’s. (It’s best to expand this polynomial in powers of z − 1 rather than z, which doesn’t affect whether or not coefficients are in Z[i].) To make sure the coefficients are in Z and not just Z[i], make sure the real and imaginary parts of F(z) satisfy the even/odd conditions from Theorem 3.15, depending on the parity of N. We can invert the process f(z)f∗(z) to generate examples of polynomials f(z) in Q[z] with a specified number of roots on the unit circle starting with a polynomial in Q[z] having a specified number of real roots, but there is a lot more we have to keep track of compare to directly computing zmg(z+1/z) when g(z) has enough roots in (−2,2), especially if you want f(z) to be monic with integral coefficients.

  15. ROOTS ON A CIRCLE 15 4. Beyond the Unit Circle In number theory and algebraic geometry there are certain problems over finite fields that give rise to polynomials whose roots all have the same absolute value equal to a number other than 1, and this phenomenon has practical applications in coding theory (google “Hasse–Weil bound” and “coding theory”). An example of such a polynomial is 9z4+ 9z3+ 7z2+ 3z + 1, whose roots all lie on the circle |z| = 1/√3 (see Figure 10).3To verify this, we want to generalize the earlier theorems to roots on a circle r where r 6= 1. 1/√3 Figure 10. The roots of 9z4+ 9z3+ 7z2+ 3z + 1. Theorem 4.1. Let f(z) ∈ Q[z] be irreducible with degree n > 1. If f(z) has a root with absolute value r, where r2∈ Q, then n is even and (z/r)nf(r2/z) = f(z). Proof. Let α be a root of f(z) with absolute value r, so α is also a root and α = r2/α. The product znf(r2/z) is in Q[z] with degree n (the coefficient of znis f(0)/rn6= 0) and α is a root, so znf(r2/z) = cf(z) for some nonzero rational number c. Evaluating this equation at z = r and then at z = −r, we see that c = rnand then that n is even. Theorem 4.2. For f(z) = cnzn+cn−1zn−1+···+c1z+c0with coefficients in C and degree n, and r > 0, the following conditions are equivalent: (1) ck= rn−2kcn−kfor all k, (2) (z/r)nf(r2/z) = f(z), (3) (if n is even) f(z) = (z/r)n/2g(z/r + r/z) for a polynomial g with coefficients in C and degree n/2. ? ? Proof. Apply Theorem 2.1 to f(rz). A polynomial f(z) fitting the first two properties in Theorem 4.2 is called “r-palindromic”. Thus 1-palindromic means palindromic and f(z) is r-palindromic if and only if f(rz) is palin- dromic. Replacing f(z) with f(z/r), if f(z) is palindromic then f(z/r) is r-palindromic. Remark 4.3. Generalizing Remark 2.2, if f(z) is r-palindromic of odd degree n then f(z2) is√r-palindromic of even degree 2n and f(z) = (z + r)fr(z) where fr(z) is r-palindromic of even degree n − 1. 3This polynomial is the L-function of the quadratic character of the finite field F3[t]/(t5−t−1). Setting z = 1/3s, the condition |z| = 1/√3 is equivalent to Re(s) = 1/2, which resembles the classical Riemann hypothesis.

  16. 16 KEITH CONRAD For a polynomial f(z) fitting the conditions in Theorem 4.2, 0 is not a root and f(α) = 0 ⇐⇒ f(r2/α) = 0, so roots of f(z) come in pairs {α,r2/α} (a singleton only for α = ±r). Theorem 4.4. For f(z) = cnzn+cn−1zn−1+···+c1z +c0with coefficients in C that has even degree n = 2m and is r-palindromic for an r > 0, write f(z) = (z/r)mg(z/r + r/z). Roots of f on the circle of radius r, considered as pairs {α,r2/α} (a singleton for α = ±r), are in bijection with the roots of g in the interval [−2,2] by {α,r2/α} ↔ α/r + r/α. Proof. Apply Theorem 2.6 to f(rz). ? Example 4.5. We will show f(z) = 9z4+9z3+7z2+3z+1 has all of its roots on the circle |z| = 1/√3 (see Figure 10). We first check f(z) satisfies the first condition in Theorem 4.2 when r = 1/√3: ck= (1/3)2−kc4−kfor 0 ≤ k ≤ 4. The reader should confirm this for each k. Then Theorem 4.2 tells us f(z) must satisfy the third condition, and explicitly f(z) = (√3z)2g(√3z+1/(√3z)) for g(w) = w2+√3w+1/3.4The polynomial g has two real roots (approximately −1.51 and −.22) and they are both in the interval (−2,2). Therefore f(z) has all 4 roots on the circle of radius 1/√3. Example 4.6. We will show z6− 4z5+ 9z4− 15z3+ 18z2− 16z + 8 has all of its roots on the circle |z| =√2 (see Figure 11). √2 Figure 11. The roots of z6− 4z5+ 9z4− 15z3+ 18z2− 16z + 8. The polynomial satisfies the first condition of Theorem 4.2 for r =√2, so by the third condition f(z) = (z/√2)3g(z/√2 +√2/z) for a polynomial g(z). Explicitly, g(w) = 8w3− 16√2w2+ 12w + 2√2 and this has all real roots (approximately −.174,1.021, and 1.981) and they are all in (−2,2). Thus all the roots of f(z) have absolute value√2. For a polynomial that may not be r-palindromic, where r > 0, we can count its roots of absolute value r by generalizing the ideas of Brunault and Rodrigues-Villegas from Section 3. 4The second condition of Theorem 4.2 says f(z) = (√3z)4f(1/(3z)), which is called the functional equation for f(z). When z = 1/3sas in the previous footnote and F(s) = f(1/3s), the functional equation for f(z) is the same as F(s) = 32(1−2s)F(1 − s).

  17. ROOTS ON A CIRCLE 17 Theorem 4.7. For r > 0, let f(z) ∈ R[z] have degree n > 0 without 0, r, or −r as roots. The polynomial Fr(z) := gcd(f(z),(z/r)nf(r2/z)) has even degree and is r-palindromic, and a complex number α of absolute value r is a root of f(z) if and only if it is a root of Fr(z). Proof. We can apply Theorem 3.2 to f(rz), which does not have 0, 1, or −1 as roots: the polynomial Gr(z) := gcd(f(rz),znf(r/z)) has even degree, is palindromic, and has the same roots of absolute value 1 as f(rz). The change of variables z 7→ z/r in polynomials does not change degrees and turns roots of absolute value 1 into roots of absolute value r (if you think this is wrong, consider r = 2 and the polynomial z2+ 1). Therefore Fr(z) := Gr(z/r) = gcd(f(z),(z/r)nf(r2/z)) has even degree, is r-palindromic, and has the same roots of absolute value r as f(r(z/r)), which is f(z). Example 4.8. Let f(z) = z6−4z4+6z3−16z2−60z +25. We will show 4 out of 6 roots have absolute value r =√5 without factoring f(z). We have (z/r)6f(r2/z) = (z6/53)f(5/z) = (1/5)z6−(12/5)z5−(16/5)z4+6z3−20z2+125, and its greatest common divisor with f(z) is Fr(z) = z4+ 3z3+ 4z2+ 15z + 25. (This is r-palindromic, i.e., ck= r4−2kc4−k= 52−kc4−kfor 0 ≤ k ≤ 4, as Theorem 4.7 says it must be.) By Theorem 4.7, f(z) has as many roots of absolute value r as Fr(z) does, which by scaling is the same as the number of roots of absolute value 1 of Fr(rz) = 25z4+ 15√5z3+ 20z2+ 15√5z + 25. This palindromic polynomial of degree 4 is z2g(z + 1/z) for g(z) = 25z2+ 15√5z − 30 and g(z) has 2 real roots that are approximately −1.955 and .613. Both are in (−2,2), so Fr(z) has 4 roots on the unit circle and thus f(z) has 4 roots on the circle |z| = r =√5. We can also count roots on the circle of radius r using the M¨ obius transformation Mr(z) = rz − i ? z + i, which sends the real line onto the circle of radius r, excluding the number r. Therefore the number of roots of f(z) with absolute value r other than r itself equals the number of real roots of ? where n = degf. Example 4.9. Let f(z) = 9z4+ 9z3+ 7z2+ 3z + 1 as in Example 4.5. For r = 1/√3, f(r) ≈ 7.79 6= 0 and (z + i)4f z + i This polynomial has 4 real roots, approximately ±.89 and ±.37, and degf = 4, so all the roots of f have absolute value r = 1/√3. Example 4.10. We show f(z) = z6−4z5+9z4−15z3+18z2−16z +8 from Example 4.6 has all roots with absolute value r =√2 by looking at real roots of (4.1): r is not a root of f(z) since f(r) ≈ .318 6= 0, and (z +i)6f z + i ? rz − i z + i (z + i)nf (4.1) , ? ? ?13 ? ?13 ? 3+ 2√3 3− 2√3 rz − i z4−22 3z2+ = . ? ? = (88−62√2)z6+(−168+70√2)z4+(168+70√2)z2+(−88−62√2). rz − i

  18. 18 This polynomial has 6 real roots and degf = 6, so all roots of f have absolute value r =√2. KEITH CONRAD Example 4.11. To count roots of f(z) = z6− 4z4+ 6z3− 16z2− 60z + 25 with absolute value r =√5, we have f(r) ≈ −97.082 6= 0 and (z + i)6f z + i where (−30 − 30√5)z6+ (−2430 + 390√5)z4+ (2430 + 390√5)z2+ (30 − 30√5) (−30 − 30√5) 2 ? ? rz − i = a(z) + b(z)i a(z) = ! z6+73 − 47√5 z4+ (4 − 17√5)z2+3 −√5 = 2 and (−560 − 240√5)z5+ 2080z3+ (−560 + 240√5)z (−560 − 240√5)z b(z) = ! z4+−91 + 39√5 z2+47 − 21√5 = . 2 2 The real roots of a(z)+b(z)i are the real roots of gcd(a(z),b(z)), and this greatest common divisor is b(z)/z since a(z) =−96+48√5 128 roots, so f(z) has 4 roots with absolute value r = Example 4.9. (z2+ (2 +√5)2)(b(z)/z). Check b(z)/z has 4 real √5, as we found by another way in Appendix A. The Geometry of z + 1/z The function z + 1/z, particularly how it relates the unit circle and [−2,2], was used in Section 2 to count roots of a polynomial on the unit circle. We take a closer look here at the geometric effect of this function on the complex plane. On C, inversion z 7→ 1/z exchanges the interior and exterior of the unit circle (ignoring the origin) and also the upper and lower half-planes. See Figure 12, where, for instance, the regions marked A and 1/A are exchanged. and try to get a feel for how the different parts of the plane get moved around (e.g., regions A and B share a border and so do their inverse regions 1/A and 1/B). This process is quite simple on the unit circle, where inversion is just reflection across the x-axis. D A C B 1/D 1/A 1/C 1/B Figure 12. The function 1/z.

  19. ROOTS ON A CIRCLE 19 If we look instead at the function z 7→ z+1/z on the complex plane (ignoring the origin) then something quite different occurs. This function is 2-to-1 rather than 1-to-1: z and 1/z both go to the same place under z + 1/z, so the regions A and 1/A have the same values, and likewise for other pairs of inverse regions. What happens to the upper half-plane under z 7→ z + 1/z is illustrated in Figure 13: the regions B and C are spread out to the two quadrants in the lower half-plane and the regions A and D each fill up a whole quadrant in the upper half-plane. So z + 1/z sends the upper half-plane onto the whole complex plane except for (−∞,−2] and [2,∞), which are doubly covered by the real line without 0. In the same way z + 1/z on the lower half-plane fills up the complex plane. D A D + 1/D A + 1/A z 7→ z +1 C B z −1 1 1/D 1/A C + 1/C B + 1/B 1/C 1/B Figure 13. The function z + 1/z. The circular arc from i to 1, which separates A and B, turns into the segment [0,2] on the real line. However, the boundary separating A+1/A and B+1/B is the whole positive x-axis, not just [0,2]. Where did the part of the boundary [2,∞) between A + 1/A and B + 1/B come from? The explanation is that we should not forget the 2-to-1 nature of z + 1/z: we should look at where A has a common boundary with both B and 1/B, not just 1/B. That means not only the arc from i to 1 between A and B but also the interval [1,∞) between A and 1/B. Under z 7→ z + 1/z the interval [1,∞) becomes [2,∞). References [1] E. Ghate and E. Hironaka, The arithmetic and geometry of Salem numbers, Bull. Amer. Math. Soc. 38 (2001), 293–314. [2] G. Kuba, Several types of algebraic numbers on the unit circle, Arch. Math. 85 (2005), 70–78. [3] D. H. Lehmer, Factorization of certain cyclotomic functions, Ann. of Math. 34 (1933), 461–479. [4] F. Rodriguez-Villegas, On the zeros of certain polynomials, Proc. Amer. Math. Soc. 130 (2002), 2251– 2254. [5] J. H. Silverman, “The Arithmetic of Dynamical Systems,” Springer-Verlag, NY, 2007.