Some Properties of the Coefficients of Cyclotomic Polynomials Citation Lu, Kau-un (1968) Some Properties of the Coefficients of Cyclotomic Polynomials. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/py5s-v205. https://resolver.caltech.edu/CaltechTHESIS:12182015-163230212 Abstract An explicit formula is obtained for the coefficients of the cyclotomic polynomial F n (x), where n is the product of two distinct odd primes. A recursion formula and a lower bound and an improvement of Bang’s upper bound for the coefficients of F n (x) are also obtained, where n is the product of three distinct primes. The cyclotomic coefficients are also studied when n is the product of four distinct odd primes. A recursion formula and upper bounds for its coefficients are obtained. The last chapter includes a different approach to the cyclotomic coefficients. A connection is obtained between a certain partition function and the cyclotomic coefficients when n is the product of an arbitrary number of distinct odd primes. Finally, an upper bound for the coefficients is derived when n is the product of an arbitrary number of distinct and odd primes. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Mathematics) Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Apostol, Tom M. Thesis Committee: Unknown, Unknown Defense Date: 5 April 1968 Record Number: CaltechTHESIS:12182015-163230212 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:12182015-163230212 DOI: 10.7907/py5s-v205 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 9331 Collection: CaltechTHESIS Deposited By: INVALID USER Deposited On: 21 Dec 2015 17:41 Last Modified: 03 Apr 2024 20:43 Thesis Files Preview PDF - Final Version See Usage Policy. 8MB Repository Staff Only: item control page

Copyright KAU-UN 1968 0 LU - by SOME PROPER TIES OF THE COEFFICIENTS OF CYCLOTOMIC POLYNOMIALS Thesis by Kau-un Lu In Partial Fulfillment of the Requirements For the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1968 (Submitted April 5 , 1968) ii ACKNOWLEDGMENTS The author wishes to acknowledge his indebtedness to his advisor, Dr. T. M. Apostol, for suggesting the subject matter of this research, and for his guidance and inspiration throughout the course of the research, and for his patient reading and revision of the presentation of this thesis. During his graduate studies the author has been the recipient of Teaching Assistantships, and summer fellowships. wishes to express his appreciation for these gifts. The author iii ABSTRACT An explicit formula is obtained for the coefficients of the cyclotomic polynomial F odd primes. n (x), where n is the product of two distinct A recursion formula and a lower bound and an improve- ment of Bang 1 s upper bound for the coefficients of F n (x) are also obtained, where n is the product of three distinct primes, The cyclo- tomic coefficients are also studied when n is the product of four distinct odd primes. A recursion formula and upper bounds for its coefficients are obtained. The last chapter includes a different approach to the cyclotomic coefficients. A connection is obtained between a certain partition function and the cyclotomic coefficients when n is the product of an arbitrary number of distinct odd primes, Finally, an upper bound for the coefficients is derived when n is the product of an arbitrary number of distinct odd primes, iv TABLE OF CONTENTS Pag e ACKNOWLEDGMENTS ii ABSTRACT iii INTRODUCTION 1 1. 1 Historical Background 1 1. 2 Some Basic Properties of Cyclotomic Polynomials 2 Previous Work on the Cyclotomic Coefficients 6 CHAPTER I 1. 3 CHAPTER II THE CYCLOTOMIC POLYNOMIAL F (x) n WHERE n IS A PRODUCT OF TWO DISTINCT ODD PRIMES 8 2. 1 Explicit Formulas for the Coefficients 8 2. 2 An Example 9 2. 3 Proof of The or e m 1 10 CHAPTER III THE CYCLOTOMIC POLYNOMIAL F (x) n WHERE n rs A PRODUCT OF THREE DISTINCT ODD PRIMES 22 3. 1 R e cursion Formulas for the Coefficients 22 3. 2 Lower Bounds for the L a rg e st Coefficie nts 22 3. 3 Uppe r Bounds for the Coe fficie nts 35 CHAPTER 'N 4. 1 THE CYCLOTOMIC POLYNOMIAL F (x) n WHERE n rs A PRODUCT OF FOUR DISTINCT ODD PRIMES 42 A Recursion Formula for the Coefficie nts 42 v 4. 2 CHAPTER V Upper Bounds for the Coefficients THE CYCLOTOMIC POLYNOMIAL F 48 n (x) WHERE n IS A PRODUCT OF AN ARBITRARY NUMBER OF DISTINCT 5. 1 5. 2 5. 3 REFERENCES ODD PRIMES 52 A Partition Function and Its Generating Function 52 Connection Between p(k, rn, n) and the Cyclotornic Coefficients 53 An Upper Bound for the Coefficients 56 62 1 CHAPTER I INTRODUCTION 1. 1 Historical Background The cyclotomic polynomial F (x) of order n is defined by n the equation F n (x) = ¢(n) II (x - () J j= 1 ( 1) where t;; , t;; 2 , ••. , '¢(n) are the primitive nth roots of unity. 1 Here ¢(n) is Euler's function which enumerates the number of positive integers :::: n which are relatively prime to n. F n We can also write ¢{n) k (x) = ~ ck x k=O where the coefficients c , c , ... , c¢(n) are integers which we call 1 0 cyclotomic coefficie nts. This thesis is a study of some of the proper- ties of these coefficients. The cyclotomic polynomials appeared first in Gauss's Disquisitiones Arithmeticae ( 1801) in a study of equations which determine the divisions of the circle. They appeared later in Cauchy's proof of the existence of primitive roots of a prime p (Exercises de math., 1829, 231). In 1854 Kronecker (Journal de math., XIX) and in 1859 V. Lebesgue (Ann. Mat. 2) studied the irreducibility of cyclotomic polynomials. Bang (Tidsskrift for math. , (5), 4, 1886) and r. 2 Sylvester (Comptes Rendus Paris, 106, 1888) proved the existence of infinitely many primes of the form m z + l for given m by use of cyclotomic polynomials. 1. 2 Some Basic Properties of Cyclotomic Polynomials This section lists some basic properties of cyclotomic poly- nomials in the form of six lemmas. F n The first three lemmas show that (x) is a monic polynomial of degree ¢(n) with integer coefficients. Lemma 4 shows that symmetrically located coefficients are equal. Hence to study the coefficients of the cyclotomic polynomial it suffices to study only half of them. Lemmas 5 and 6 reduce the study to cyclotomic polynomials of an order which is a product of distinct odd primes. Lemma 1. Proof: x n - l = II din ( 2) F d(x) This follows from the fact that any nth root of unity is a primitive dth root of unity for some unique divisor d of n. d Lemma 2. F (x) n Proof: = II (x - 1) µ,(n/d) ( 3) djn This follows from Lemma 1 by applying the Mobius inversion formula. Lemma 3. The cyclotomic polynomial F n (x) of order n is a monic polynomial of degree ¢(n) with integral coefficients. Proof: This is easily proved by mathematical induction. theorem is true for n = 1. The Now suppose it is true for all F k(x), where 3 k < n. From ( 2) we have x n - 1 = F n (x) din IT Fd(x) = F (x) G (x) . n n d<n G (x) = where n IT F d(x) djn d<n Since d< n, each factor F d(x) is a monic polynomial with integral Hence G (x) is also a monic n coefficients by the induction hypothesis. polynomial with integral coefficients . F (x) n Now write xn - 1 = G (x} n Since G (x) has leading coefficient 1, the long division produces only n integral coefficients, so F n (x) is also a monic polynomial with integral coefficients. To conclude the induction we need to prove that the degree of F n (x) is ¢(n). Let the degree of F (x) be v. n From the induction hypothesis the degree of F d(x) is ¢(d) for each d< n. Hence by (3) we have n =v + ~ ¢{d) djn d<n since 6 ¢(d) = n. = v - ¢ {n) + ~ ¢ ( d) = v - ¢ {n) + n din Hence v = ¢{n) and the lemma is proved. din Lemma 4. are equal for n > 1. Symmetrically located cyclotomic coefficients 4 Proof: Since the degree of F (x) is ¢(n), proving the lemma n is equivalent to proving that x¢(n) F n (1 /x) = F (x). n use of the two well-known formulas (a) (b) ~ dµ(n/d) = ¢(n). din This proof makes ~ µ.(d) = 0forn>1, and din From (3) we have x¢(n) F n(~) = x¢(n) d ln( (~) =x ¢(n) 1) µ(n/d) d - II 1- x din ( x d)µ(n/d) d ¢(n) d µ(n/d) II (1 - x ) = -----:B dµ.(n/ d) din x din x = by (b). d µ(n/d) II (1 - x ) din If we change the sign of each factor the product does not change sign since by (a) we have ~ µ(n/d) din = O. Therefore d µ(n/d) II (x - 1) ' din ak pk , where the ai are pos- Lemma 5. itive integers, let q = F n (x) = p 1 ... pk. Then 5 = F q (xn/q} F (x} n Proof: First rewrite (3) as F n Now µ.{d} = 0 unless F (x} n = II n/d = II (x} din Hence di q. (xn I d - 1} µ.( d} = II <liq dlq Lemma 6. Proof: µ.(d} - 1} (x If n is odd, { (x n/q q/d } - 1 } µ.(d} n ~ 3, we have F 2n = (x) = F n (- x) • By Lemma Z we have F Zn(x) = d µ.( Zn/d) II (x - 1) di Zn Since n is odd, the divisors d of Zn are equal to the divisors d' and Zd', where d' In. Hence we have d1 II (x d'I n = d1 II (x d'I n Since µ(Zn/d ') we have µ.( 2n/ d') Zd' II (x d'I n - 1) µ.(Zn Id') - 1} and µ.(n/d') µ.(Zn/Zd ') - 1) dI II (x d'I n µ.(n/d') - 1) d' µ.(n/d') II (x + 1) d'I n have opposite signs for odd n > 1 and d' In, 6 F 2n(x) = II (x d'I n d' + 1) µ.(n/d') for n > 1 . , for I Since n is odd and d' n , we have F 2n(x) = II d'I n ( - ( - x) d' )µ.(n/d') +1 = a•\ n [(<-x>d' - 1) µ(n/d') (- l)~(n/d'>] II d'I n ~ Since ~ =[ (- x) d'I n d1 - 1 µ.( n / d ) ] :B µ.(n/d') <- 1>d'I n n>l. µ.(n/ d ') = 0 , we obtain F 2n(x) 1. 3 1 ) = F n (- x ) , for n>l. Previous Work on the Cyclotomic Coefficients In 1883, Migotti [ 12] proved that the coefficients of F are ± 1 or 0, where p 1 and Pz are two odd primes. (x) P1Pz In 1895 Bang [ 4] proved that no coefficient of F p <p <p are odd primes. 2 3 1 (x ) exceeds p - 1, where 1 P1P2P3 In 1931, I.Schur proved that there exist cyclotomic polynomials with coefficients arbitrarily large in absolute value. The proof has not been published, but it was given by Emma Lehmer in one of her papers [11]. In 19 36 Emma Lehmer [11] proved that as n runs over all products of three distinct primes, the cyclotomic polynomials F n (x) contain arbitrarily large coefficients. Paul Erdos [8] proved there are infinitely many n such that the In 1945 7 greatest coefficient of F n(x) in absolute value exceeds n k for every k. In 1960 Marion Beiter [5] proved that if we let c where p 1 n where a n x < Pz are odd primes, then if = { (- 1) 0 c n 0 n = ap 1 + \3p 2 + o in exactly one way , otherwise , and [3 are nonnegativ e integers and o = 0 or 1. In 1964 Helen Habermehl, Sharon Richardson, and Mary Ann Szwajkos [9] proved that if we let ¢(3· Pz) F 3 . Pz (x ) = 6 n=O c n x n where Pz is a prime greater than 3, then for n s: p - l, 2 1 c n = -1 0 if n = 0 if n (mod 3) = 1 (mod 3} if n = 2 (mod 3) For n > p -l, we have en= er:, where n' = 2(p -l) - n. 2 2 8 CHAPTER II THE CYCLOTOMIC POLYNOMIAL F (x) WHERE n IS n A PRODUCT OF TWO DISTINCT ODD PRIMES Theorem 1 gives a formula for the coefficients of F where p 1 and p 2 (x ) P1P2 are two distinct odd primes greater than 3. In corollary 1 we show that the coefficients are ± 1 or 0 by means of the formula in Theorem 1. 2. 1 It agrees with the known results. Explicit Formulas for the Coefficients Theorem 1: Let p 1 and p 2 be two primes with p 2 > p 1 Let c n x n and let For each k= 0,1,2, ••. ,N, let 0 if 0 .:S, n < kp 1 if kp < n < 2 -1 if kp < n < 2 0 otherwise c (k) = n Then we have - - - - . 2 ¢(P1Pz) 2 ' n =kp 2 (mod p 1) ' n =kp2+l (mod p 1) ¢(p 1 P2) 2 > 3. 9 (A) c c {B) 2. 2 ¢(p 1P2) c (0) + c ( 1) + ..• + c (N) n n n = n if 0 < n < = c ¢{pl P2> -n n 2 ¢(P1P2) if < n :::_¢{pl P2) 2 An Example Before we prove the theorem 1, we consider the example F 35 (x). Here p 1 = 5, p 2 = 7. From the formula (3) of Lemma 2 we have d µ.(35/d) IT (x - 1) dl35 (x - 1) (x = (x 5 35 - 1) (x 7 - 1) - 1) Dividing out we have F 35 (x) = 1-x+x5 -x 6 +x 7 -x 8 +x 10 -x 11 +x 12 - ••. + x 24 To compute the coefficients byTheorem 1 we first determine N = [( 5 - 1) ( 7 - 1)] = l 2· 7 ¢(5· 7) 2 and ' = 12 The calculations forTheorem 1 can be arranged in tabular form as follows: n 0 1 2 3 4 5 6 7 8 9 10 11 12 c (O) n c ( 1) n c n 1 -1 0 0 0 1 -1 0 0 0 1 -1 0 0 0 0 0 0 0 0 1 -1 0 0 0 1 1 -1 0 0 0 1 -1 1 -1 0 1 -1 1 10 2, 3 Proof of Theorem 1 From Lemma 1 we have Now we multiply out and make an appropriate change of the indices to obtain c c n x n = l+x ( n- P1 - n Z)x+ .. <P1- 1>Pz Pz + ••• +x (4) We shall prove (A) by equating the coefficients of like powers of x in ( 4). Part (B) then follows from the symmetry property of lemma 4. We will prove (A) by mathematical induction on t where 11 1) We consider the case t = 0, which means 0.::;, n < p 2 . Since for each k = 1, 2, ... ,N we have c (k) = 0 for 0 < n < kp , 2 n prove that (A) is true for 0 < n < Pz is equivalent to proving c for 0.::;, n < p 2 n to = c n (O) . Equating . the coefficients of like powers of x in (6) we find: x x x x 0 c ( 0) = 1 = c 0 ( 0) . 1 c 2 c i 1 2 +c + c 0 1 =0; hence + c 0 c 1 =-c = 0 ; hence c 2 = - l = c (0). 1 0 = 0 = c ( 0) • 2 Ci + Ci-1 + • • • + C 1 + CO = 0 hence = c.]. ( 0) where hence hence This proves that c n = c (0) for 0 < n < p n N ext we show that cm+ cm= cm(O} where p 1 .::;, m < p 2 . - 1 - 1 . = cm+ (0) on the assumption that 1 This will prove that c n = c (0) for n 0 .::;, n < Pz. Equating the coefficients of x m+l in (4) we find: c m + 1 + c m + . . . + c m+ 1 - ( p - 1) 1 =0 12 Hence Now we shall prove, by induction on n, that we have c {O} + c i {O} + • • • + c { l} ( O} = .0 n nn- p . 1 { 6} we have c Pi- i(O} + c Hence (6) is true for n Pi- 2 (0} + ••• + c i(O) + c (0) 0 = Pi- i. and show it is true for n = m+ 1. =0 • Next we suppose it is true for n =m We have cm+i(O) + cm(O} + ••• + Cm+i -(pi-i}(O} = cm+i(O)+(cm(O}+cm-1(0)+ •.• +cm-{pi-i}(O))-cm-{pi-1}(0}. (7) By the assumption that (6} is true for n = m the right member of (7} simplifies to By the definition of the c {O} 's, n this difference is 0. proved (6}. By (6), equation (5) becomes Hence we have 13 Hence c m+ 1 = c m+ 1(0) Hence we have shown that en= cn{O) for 0 :::_ n < Pz. 2} tp 2 Now we assume (A} is true for all n in the interval .:S. n < (t+ l)p 2 and try to show it is true for all n in the interval ( t+ 1) p .:S. n < ( t+ 2) p 2 and n .:S. 2 ¢(P1Pz) 2 Equating the coefficients of like powers of x in (4) we find =1 By the induction hypothesis we have c(t+l)pz + (c(t+l)pz-1(0) + c(t+l)pz-1(1) + .•• + c(t+l)pz-l(N)) + ••• + (c(t+ l)pz - (pl -1) {O} + c(t+l)pz-(Pl-1)(1} + •.• + c(t+l)pz-(Pcl)(N~ = 1. Hence we have + (c(t+l)pz-1(1) + ••• + c(t+l)pz-(Pl-1)(1~ + .. + (c(t+l)pz-l(N) + ••• + c(t+l)pz-<P1-l)(N)) = 1 Adding and subtracting c(t+l)p (0) + ••• + c(t+l)p (N) on the left we 2 2 obtain 14 c (t+l)p2 - + (c(t+l)p2(0) + c(t+l)p2-l(O) + •.• + c(t+l)p2-CP1-l)(O~+ .. Now we shall prove, by induction on n, ( 8) = 1 + (c(t+l)p2(N) + ••• + c(t+l)p2 - (pl -l)(N)) that for each k = 1, 2, •.• , N we have (9) c n ( k) + c n _ 1 ( k) + • • . + c n _ ( p _ 1) ( k) = 0 1 where n is such that (k+ l)p :S. n 2, 2 ¢ (P1P2) 2 1 and c ( k+ 1) p 2 - ( p 1 - 1) = - 1 , we p.ave This proves (9) for n = (k+ l)p • Now we suppose (9) is true for n = m, 2 ¢ (pl P2) where (k+l)p < m < and show it is also true for n = m+l. We 22 have cm+ 1( k) + cm (k) + • • . + cm+ 1 - ( p - 1) ( k) 1 = cm+l(k) + (cm(k) + ••• + cm-(pl-l)(k))- cm-(pl-l)(k) By the hypothesis that (9) is true for n (10) = m, the right member of ( 10) simplifies to c m+ l(k) - c m- ( p - 1) (k) = 0 1 This proves (9). . 15 Now w e return to {8}. Since by {6} w e have {8) simplifies to c{t+l}p2 -(c{t+l}p2{0} + ••• + c{t+l}p2{N)) + (c{t+l)p 2{1) + c{t+l)p2-l{l) + ••• + c{t+l)p2-<P1-l){l~ + .. + (c{t+l)p2{N) + ••• + c{t+l}p2-<P1-l){N)J Sinc e we hav e c {i} = 0 for 0 < n < ip n - 2 = 1 {11} , { 11) simplifies to c{t+l}p2 -(c{t+l}p2{0) + ••• + c{t+l)p2{N}J + ( c (t+l)p2{1} + ••• + + c{t+l}pz-<P1-l}{l~ + .. ~(t+l}p2{t) + . .. + c{t+l)p2{t)) + c{t+1)p2{t+l) = 1 • {12) Since we have whe r e 1 :::_ j :::_ t, b y {9}, equa tion { 1 2) simp lifie s to c(t+l)p2 - ( c {t+l)p2{0) + ••• + c{t+l)p2{N~ + c {t+ 1) p 2 ( t+ 1) = 1 Since c{ t+ l)p {t+ l) = 1, equ ation {13} be come s 2 ( 13) 16 ( 14} Equating coefficients of x (t+ l)pz+ 1 we also have c{t+l) Pz+l + c(t+l) Pz + • • • + c(t+l) Pz - P1 = O By an argument similar to that used in the derivation of (8), we have + (c(t+l)pz+l(O) + ••• + c(t+l)p -p (0)) 2 1 + (c(t+l)pz+l(N)+ ••• + c ( t+ l) p _ p ( N)l 2 1 ) + .. =0 Similarly, by ( 6) and (9) and the definition of the c (k) 's we have n c(t+l)p -l - (c(t+l)p +1< 0 > + • • • + c(t+l)p +1{N)) 2 2 2 + c(t+l)Pz+l(t+l) + c(t+l)p}t+l) - 1' Similar 1y we have = O ( 15) 17 This proves (A) is true for n in the interval (t+l)Pz.S. n.S. (t+l)p +(p -l). 2 1 To finish the remaining cases we can assume that for all 0 .S. k .S. s , we have ¢(pl Pz) where s is such that p -1.::: s < p 2 -l and (t+l)p +s < - -- 2 1 2 and show that Equating the coefficients of x (t+l)p 2+s+l we find By an argument similar to the derivation of (8) we obtain c(t+l)p +s+l - (c(t+l)p +s+l(O) + • · • + 2 2 c(t+l)p 2+s+l(N~ + (c(t+l)p +s+l(O) + · · · + c(t+l}p +s+l-(p -l}(Oj + 2 2 1 + (c(t+l}p +s+l(N) + .•• + c(t+l}p +s+l-(p -l}(N}) 2 2 1 =0 Since c (i) = 0 for 0 < n < ip 2 , we simplify the above equations to n - 18 c(t+l)p +s+l -(c(t+l)p +s+l(O) + • • · + 2 2 +(c(t+l)p +s+l(O) + ••• + 2 c(t+l)p 2+s+l(N~ c(t+l)p 2+s+l-{p 1 -l)(O~+ •• + (c(t+l)pz+s+l(t+l) + ••• + c(t+l)pz+s+l-{pl-l)(t+l~ = o. By the definition of c (i) 's again, we have n c(t+l)p +s+l - (c(t+l)p +s+l(O) + • • • + 2 2 c(t+l)p 2+s+l(N~ + (c(t+l)p +s+l(O) + ••• + c(t+l)p +s+l(O)J 2 2 + ·• + (c(t+l)p +s+l(t) + • • • + c(t+l)p +s+l(t)) 2 2 = O By ( 6) and (9), we find that Hence we have This completes the proof of Theorem 1. Corollary 1: Pz > pl > 3. Let p 1 and Pz be two primes such that Let c n x n 19 Then c n is ± 1 or O. Proof: c From Theorem 1 we have n = c n (O} + c n ( 1) + •.. + c n (N) where c (k} is ± 1 or 0, for each k = 0, 1, ... , N. n c n ( 16} Hence to prove is ± 1 or 0 it is suf£icient to prove the following two statements: (a) If one of the c (k) in ( 16) is 1 then none of the other n c (k} in ( 16} can be 1. n {b} If one of the c {k) in ( 16) is - 1 then none of the other n c (k) in (16) can be - 1. n We prove (a} by assuming the contrary. exist two distinct integers k 1 and k 2 between 0 and N such that According to Theorem 1, we have and Hence we can write and This means there 20 where m N' - l 1 and m ¢(P1Pz)J Zpl • Since p 1 are two distinct integers between 0 and 2 Subtracting the last two equations we have and Pz are two distinct primes, we have But 0 :S. m 1 , Pz-1 m2 < -Z , so we must have Pz-1 <-2 Hence we conclude that This also implies This contradiction proves (a). Now assume the contrary to {b). integers k 1 and k 2 such that According to Theorem 1, we have n - kzPz+ 1 There exist two distinct 21 Hence we can write n = k p 2 +m p +1 1 1 1 n = kzPz + m2pl + 1 where m 1 and m 2 are two integers between 0 and N'. Subtracting the last two equations we have Again as in the proof of {a), this leads to a contradiction. pletes the proof of the corollary. This com- 22 CHAPTER Ill THE CYCLOTOMIC POLYNOMIAL F (x) WHERE n IS THE n PRODUCT OF THREE DISTINCT ODD PRIMES 3. 1 Upper and Lower Bounds for the Largest Coefficient The coefficients of a cyclotomic polynomial whose order is a product of three distinct odd primes are no longer ± 1 or 0. the coefficient of '.?' 7 in F . . (x) is - 2. 3 5 7 In fact, In 1895 Bang proved that no (x) exceeds p - l if p < p < p are odd primes. 2 1 1 3 P1P2P3 In 1936 Emma Lehmer proved that for a given odd prime p if we con1 coefficient of F = kp 1 + 2 and p 3 = (m p 1 p 2 - l) /2, then the coefficient of x11 is (p -l)/2, where h = {p -3) (p p +1)/2. 1 2 3 1 struct primes p 2 and p 3 such that p 2 Theorem 3 shows that for a given odd prime p 1 if we construct primes = kp 1 + 2 and p 3 = (m p 1p 2 -l)/2, then the coefficient of xh is (p +1) /2, where h = {p - l){p p + 1) /2. Hence 1 1 2 3 p 2 and p 3 such that p 2 {p -1)I2 is not an upper bound for the coefficients of F {x) . 1 P1P2P3 Theorem 4 shows that under certain conditions Bang's upper bound {p - l) for the coefficients of F (x) can be improved. 1 P1P2P3 Fir st we obtain a recursion formula for the coefficients of 3. 2 A Recursion Formula for the Cyclotomic Coefficients Theorem 2: Let c n x n 23 where p 1 < p2 < p 3 +¢(p p ) +(p -l), 1 3 1 are three distinct odd primes. and define e 0 , e 1 , ... , eT/ e (a) x = ¢(p 1 p 2 ) by the relation n For each s = 0 , 1 , . . • , ( p - 2) , 1 fn (b) f n = e n-sp f n 2 + e n- ( s- l) p 2 + ••. + e n 2 1 = fT -n 1 2 (p - l)p _::: n _::: T /2 , 2 1 if T /2 < n < T • Then we have (A) For 0 < n < T (B) For T _::: n < ¢(p p p ) /2 , 1 2 3 , £Oen+ flcn-1 +. • • + fTcn-T = {: Proof: , if sp 2 < n < (s+ l)p 2 = e n- ( p - l) P + e n- ( P - 2) P + ••• + e n if (c) n 2 Let T By Lemma 1 we have 24 = (x-1) F (x) F P1 = {<x-1) F = (xPzP 3 - Pz (x) F Pz (x) F i) P3 F (x) F P3 {x) F PzP3 (x) F P1 (x) F P1P2 (x)} F P1P3 P1 {x) F P1P2 Dividing by GPzP 3 - {x) F P1P2 (x) F {x) F P1P3 0 {x) F {x) F {x) . PzP3 P1PzP3 P1P3 {x) F P1PzP3 {x) P1PzP3 we find We obtain the conclusion of this theorem by equating coefficients of like powers of x in { 17). Let's consider If we let F {x) = {x) F P1 P1P2 a n x n then we have if n:::: kp 2 , otherwise where k=O, l, ••• ,{p -l) 1 {x) 25 If we let then we have Substituting the value for a b b b into the above equation, we obtain n =en n = e n-p + e n n = e n-sp + e n-(s- l)p + ••• + e n-p + e n n if 0 .:::_ n < Pz if Pz .:::_ n < 2p 2 2 2 2 and 0 .:::_ s < p b n 1 - 1 1 sp if T (pl-l)pz.:::_n.:::,7 2 .:::_n< (s+l)p 2 . = e n-(p -l)p + e n-(pl -2}p2 + •• • + e n . if 2 2 Since the symmetrically located coefficients of F (x) F P1 . (x} F P1Pz (x) P1P3 are equal, we have if T ""Z' < n.:::_ T Hence we see that f n = bn if 0 < n< T Then ( 14) becomes +x (pl -1) PzP3 26 Equating the coefficients of like powers of x we find: 0 < n < T, For if f c n + f c n- 1 + .•. + f no c 1 0 if if if by the symmetry of the coefficients of F (x) • P1P2P3 Hence we complete the proof of this theorem. Theorem 3: · There exist integers n, the product of three distinct odd primes greater than 3, such that the cyclotomic polynomial F n(x) contains a coefficient which is equal to (p +1) /2, where 1 p 1 is the smallest prime factor of n. Proof: Given a prime p 1 > 3, by Dirichlet's theorem on primes in arithmetic progressions there is an integ er k such that p 2 = kp 1 + 2 is prime. Since p p and (p p - l) /2 are relatively prime, 1 2 1 2 there is aninteger m' such that p Let m = 2m' + 1. ~hen p 3 3 = m'p p + (p p -l)/2 is prime. 1 2 1 2 = (mp 1 p 2 - l)/2. From the definition of p ,p we obtain the following lemma. 2 3 27 m p p 1 2 3 = - 1 (mod p 1) 2 = 2 (mod p 1) Lemma 7: p 2p = 1 (mod p 3 ) p that is, 2p 3 =- 1 k? 1 p p 3 3 = 1 (mod p 2) =-1/2 (mod p 1 p 2) (mod p 1 P 2 ) Proof of Lemma 7: 1 (mod p ) . 2 mp p 1 2 = 2p3 + 1 - 1 (mod p ) 3 P2 = kpl + 2 = 2 (mod p 1) p3 = (m P1 P2- l) - 1 =- 2 2 (mod p p ) 1 2 This completes the proof of Lemma 7. Now let h = We will show that the coefficient of xh is (p + 1) /2 1 By lemma 2 we h ave F (x ) P1P2P3 28 Consider the diophantine equation =h ' ( 18} subject to the restrictions The coefficient of xh is the number of solutions of ( 18} with e = f, minus the number of solutions of ( 18} with e ~ f. Now we reduce equation (18} modulo p , p , p respectively, 2 1 3 using the lemma. This gives us since p p - - 1 (mod p ) . 2 3 1 ( p 1- l} izP1P3 + j + fp3 - i3P1Pz + j + ep2 - 2 {mod p ) 2 {pl -1) 2 {mod p ) 3 Multiplying the last two congruences by k and m, respectively, and using L e mma "? again, we obtain 29 f j - il - 2e + z (mod p ) 1 ( 20) i2 -l f) - k(pl -2--j+2 (mod p ) 2 ( 21) ep2J (mod p ) 3 ( 22) for e = f = 0, (18) has (p 1+1) /2 solu- (p 1 -1 . i3 = m - 2 - - J Now we will show that: tions; for tion. c = f = 1, (18) has no solution; for e ~ f, (18) has no solu- This will prove that the coefficient of xh is (p +1) /2. 1 Assume e = f = 0. j.::, (p -l) and i < p , 1 1 1 Then ( 20) gives we obtain j = i 1 . j = i 1 (mod p ). 1 Substituting j = i 1 Since into the equations (21) and (22), we have i2 -1 ) - k (p +-il i3 -1 - m (p +-i1 Since i l p 2 p J 3 (mod p ) 2 ( 23) (mod p ) 3 (24) .::, h, we have 1 -) l+( P2P3 Sinc e i 1 is an integer, we obtain i have k(p -1)/2 < p . 2 1 i (pl-1) 2 2p2p3 :::_ (p -1)/ 2. 1 Since p p i :::_ h, we have 1 3 2 < (<P1-1)12) (P2P3+ 1) = 2 - 1 p -1 = _1_ + P1P3 = Since p 2 = kp 1+2, we 30 Therefore we conclude that (23) is an equality, (23 1) Since p = 3 mp p -l m(p -l) 1 2 1 , we have < p . 3 2 2 Since p p i .:::, h, we have 1 2 3 Hence we conclude that ( 24) is an equality, (24') Since values for i 1 . . 0 < i (pl-1) , there are (p +1)/2 choices of 1 2 If we can show that for each choice of i we have 1 1 .:::, i p p .:::, h and i p p .:::, h, 2 1 3 3 1 2 solutions in the case e then we can conclude that (18) has (p +1) /2 1 = f = 0. By ( 23 ') we have . i < 2 k(p 1 -1) - 2 . Hence we have m(p -l) Since we have i < 3 - 1 2 Next assume e = 1, f = 0: by (21'}, we have (20) becomes j = i 1 - 2 (mod p ). 1 31 Hence we obtain j = i if i 1 = 0. - 2 if i 1 1 ~ 0 , 1; j = p 1 - 1 if i 1 = 1 For the last two cases we can use (21} to get (pl-1) - k 2 (mod p 2 ) ; if j = p 1 - 1 Hence we have p 2 k(pl -1) ---- 2 k(pl -1) > P2 - - - 2 - P2 Hence we have kpl P3(P1- l} i2P1P3 > P1P2P3 - 2 P1-l = p 1 P2P3 - P2P3 2 (p2-2)p3(P1 -1) = P1P2P3 - 2 P1+l + p (p -1} = P2P3 - 2 - + P3(P1 -1) > h 3 1 P1-l pl-5 Since i 1 .:S, - , we have j .:S, - 1 2 2 still in the case e = 1, f = 0. Hence (22) becomes For the case j = i Hence we obtain -2: . We are 32 pl-1 . ) i3 = P3 + m ( - 2 - - J - P2 + -+ p -1 > P3 + m ( p -5 ) P2 = P3 + m( 2 - P2) Hence, since m p Pz = 2p + 1, we have 1 3 i3P1P2 = P1P2P3 + mplp2( 2 -Pz) = P1P2P3+(2p3+1)(2-p2) = (P2P3 + l)(pl - 2) + (4p3 - P2+ P1+4) > (p 2 p 3 + l)(p 1 - 2) > h Hence for e = 1, f = 0, (19) is violated. Hence we conclude that (18) = l, f = 0. . (pl+l) Assume e = 0, f = 1. Then from (20) we have j = 1 + 1 has no solution for e 2 Substituting this value of j into (22), we have Hence we obtain i 3 = p 3 - m(l+i 1) > P3 - m(l + P1;l) m· (p +1) 1 2 33 Hence we have (pl-1) = P1P2P3 - mplp2 i3pl P2 2 (pl+l) = P1P2P3 - (2p3 + 1) = 2 2 P1P2P3 - 2 P1P3 - 2p3 - P1 - 1 2 Assume Then we have Hence we obtain or Since p 2 > 2 and p 2 p - 2p 2 - 2p 1 > p 2 p - 4p 2 = p 2 (p -4) > 0 we have 3 3 3 proved that the ine quality ( >~) is not true. Hence we conclude that Hence for e = 1 , f = 0 , Hence (18) has no solution for (19) is violated. e = l, f = O. Assume e = f = 1. = i 1 - ~ (mod p 1). Then from (20) we have j = i Hence we have j = i (21) and (22), we have 1 + (p -3)/2. 1 1 - 2- i Substituting i nto 34 (p 1 -1 i3 . - m - 2 - - 11 - -+p -3 J m((l - i 1} - p 2 ) P2 (mod p } 3 (mod p } 3 Hence we have Assume Then we have Hence we obtain But P2P3<P1-3} - 4p3 - 2p2 - P1 - 1 > P2P3<P1 - 3} - 8p3 = p3 Hence ( ~:<>~} is not true. (Pz(P 1 - 3) - s) > 0 sinc e pl> 3 Hence = f = 1, (15} has no solution. This proves that the coefficient of xh is (p +1)/2, where h = (p -1} (p p + l} /2. 1 2 3 1 Hence for e 35 3. 3 Improvement of Bang's Upper Bound Theorem 4: Let c n x n where p , p , p are three dis tine t odd primes. 2 1 3 If there exists an P1 -1 such that for each integer k satisfying 1 < k < m < _ _ + 1 , 4 the diophantine inequality integer m I kPzP3 + s2P1P3 + s3P1P2 I < P1 - 1 Pz-1 has no solution in the domain I s 2 I .:s.-2- - 1 and Is 3 I < P3-l - 1 , 2 then - (p -1)1 I en I .:S. - 2 G 2(m ~ l):J Note: The upper bound for I en I does not exceed p 1 -1. The upper bound is equal to p -1 when m=O. 1 by Bang. Proof: = x By Lemma 1 we have P1PzP3 x PzP3 - 1 -1 1 This is the case proved 36 n~(p.~0 x ~· ( 1-xP2 -xP3 +xP2+P3J 1 = ( """' L..Ja x n LJ J= If we let then we obtain = ( """' LJb x n~ ( 1-xP2 -xP3 +x P2+P3j n where b n = a n + a n- 1 + ••• + a n-p ( - l) ' 1 Since a that n and b n a. = 0 1 :6 c n x n if i < 0 • are nonne gative, from (>:(>~>:() we can see Ic n I -< 2 max Ib n I . Hence we need to find a bound for max I b n I. n n Since we need only to consider those c p -1 1 O<i < - - - 1, - 12 Assertion 1 : p -1 2 - 1 , 2 o< i2<- 1 n s such that n< p -1 0 < i3 < _ 3_ 2 - 1 . (25) For a given n .s_ ¢ (p p 2 p ) /2 we have an= 1, 1 3 if n = i p p + i p p + i p p has solution; 2 1 3 1 2 3 3 1 2 a n = 0, + i 2 P 1P 3 +i 3 p 1 p 2 has no solution. Proof: From its definition, a n is the number of solutions of (26) 37 Hence to prove the assertion we need to prove that for a given n (26} has at most one solution. Suppose (26} has two solutions (i ,i ,i ) and (i ',iz',i 1) . 1 2 3 1 3 Then we have (27) Hence we obtain Since p , p , p are three distinct primes, we have 1 2 3 I Since 0 :S, i , i :S, 1 1 (p1- 1> 2 - 1, we also have 1 i1- i 1 =0 or Substituting into (27), we have Hence we obtain . ' (p2-1> - 1, we conclude that Since O :::_ i 2 , i 2 :::_ 2 Hence we also have 38 This completes the proof of the assertion. From b n = a n +an- 1 + ••• +an- ( p- l) and assertion 1 we con- clude that for a given n.:::, ¢(p p 2 p ) /2 the coefficient bn is the number 1 3 of the following equations which have a solution: (28) where the equations with left-hand side negative are omitted. Assertion 2: values for i 1 If two equations in (28) have solutions, their must be differ e nt. Proof: Suppose not. Then we have where i f j and 0 < i, j.:::, p -l. 1 H e nce we obtain Hence we have Since 0 < i, j.:::, p 1 -1, this implies i =j 39 a contradiction. This proves assertion 2. . th e inequa . l"ities . 0 < i. < p 1- l - 1 an d assertion . 2 , we U sing 12 conclude that in (28) there are at most (p -1) /2 equations which have 1 solutions and their values for i 1 are distinct. according to increasing values of i n-j 0 1 We can rearrange them a~ follows: = = n-j(p -1) 1 ---- 1 2 where ( 29) = is a subset of 0,1, •.. ,(pl-l). 0 1 ~ ·i ·····i+-J The coefficient b have a solution. n is the number of equations in (29) which I I .: : , (p 1 -1)/2 and I en I .: : , p 1 -1, Hence we have max bn which is Bang's bound. Notice that if p 1 > 3 , the system (29) contains more than one equation. If we subtract each equation from its predecessor in (29), we have or (30) where and 40 Hence if (30) does not have a solution, then the maximal number of solvable equations in system (29) is reduced to: p -1 1 P1 -1 ~ when ' p -1 _1_+ 2. 2 1' when 2 p -1 1 2 is even is odd . Putting this into one formula, we find that the maximal number of solvable equations in system (29) is reduced to -[-~] 2 . 2 If we subtract each equation from its second predecessor in ( 29) , we have (31) where P2-l I s2 I < - 2 - - 1 and Hence if (30) and (31) do not have a solution, then the maximal number of solvable equations in system (29) is reduced to - [- (pl -1)] 2. 3 This process continues. Since there are only(p -1)/2 equa1 tions in (29), we will reach a largest integer m.:::,(p -l)/4 + 1 such that 1 for each k satisfying equality 1.:::, k.:::, m < (p -l)/4 + 1 the diophantine in1 41 has no solution in the domain P2-l I s2 I < - 2 - - 1 and Then the maximal number of solv a ble equations in (29) is reduced to This completes the proof of this theorem. 42 CHAPTER IV THE CYCLOTOMIC POLYNOMIAL F (x) WHERE n IS THE n PRODUCT OF FOUR DISTINCT ODD PRIMES This chapter develops p 1 < Pz < p 3 < p 4 properties of F p p p p (x) , where 1 2 3 4 are odd primes. Theorem 5 gives recursion for- mulas for the cyclotomic coefficients. Theorems 6 and 7 give upper bounds for the coefficients d e rived from Theorem 5. 4. 1 A Recursion Formula for the Coefficients From Lemma 2 we have P1PzP3P4 1-x = PzP3P4 1-x PzP3 1-x Pz 1-x 1 P1P3P4 1-x P1P3 1-x P3 1-x 1 P1PzP4 1-x P1P4 1-x P4 1-x 1 P1PzP3 1-x P1Pz 1-x .. pl 1-x 0 ( 1-xPzP4) ( 1-xP3P4) ( 1-x 43 Let =~ a x n n Then an is equal to the number of solutions of n = i p p p 1 2 3 4 + i 2 P 1P 3 P 4 + i 3 P 1P 2 P 4 + i 4 p 1 p 2 p 3 . Now we will prove that: has a solution in the range 0 .:::_ i a n = 0 otherwise. It is sufficient to prov e that if a n +0 then a n = 1. Suppose not. That is, assum e there are two solutions for some n, where .:::_ p -1 , 1 1 (i ,i ,i ,i ) 1 2 3 4 specified intervals. say f (i 1',i 2 ,i 3 ,i~) with i.J and i J. lying in the 1 1 Then we obtain I 44 (il -i1'> PzP3P4 + (iz-i2'> P1P3P4 + (i3 -i3') P1PzP4 + (i4 -i~) P1PzP3 = 0 . (34) Hence Since Ii 1 - i 1' I :S, p 1 -1, we conclude that Then (34) becomes (35) Hence Since I i 2 - iz' I :S. p 2 - l , we conclude that Then (35) becomes Hence Since I i 3 - i 3 I :S, p 3 -1 , we conclude that 1 Hence we also have 45 (33). Let If we consider that b 1 n s are obtained by multiplying each term in with we have where b n =0 (36) 0 .:::_ k.:::_ p -l 2 otherwise . Let Then we obtain, as above, (3 7) d n =0 otherwise . Let N = ( p 2 - l) p 1 + ( p 1 - l) p 3 + (p 3 - l) p 2 + (p 1 - l)" p4 Nl = (pz-1) P1 + (pl-1) P3 ; N2 = (p3-l) Pz + (pl-1) P4· Write 46 e n x n Then we have .f 0 _< n < N d b d b en = b n d 0 + n-1. 1 + • · · • 0 n e l = bN ldn-N 1 + ... + b n -N 2 dN 2 n if N 2 :s_ n :s_ N Let Then we have if Hence we obtain ¢ (pl PzP3P 4) :0 c n=O n x n Equating coefficients of like powers we find co = fo = 1 c n = f -f 1 n n- 1 O<n<N 47 c c n = f n -fn-1 -f 0 if n = f -f +f -f -f n n-1 n-(p 2 p + 1) n-p 2 p 0 4 4 if if if Hence we have the following theorem: Theorem 5 : polynomial. b n = Let: t if n = kp 1 where (mod p ) 3 and kp 1 .:S. n .:S. kp 1 + ( p 1 - 1) p 3 0 .:s_ k .:s_ p -l 2 otherwise if n =kp 2 (mod p 4 ) and kp 2 .:S. n .:S. kp 2 + (p 1 -1)p 4 where otherwise • 0 .:s_ k .:S. p 2 - l 48 = an en = has a positive integral solution 0 otherwise . N = {pz-1) P1 + {pl-1) P3 + {P3-l) Pz + {pl-1) P4 Nl = {pz-1) P1 + {pl-1) P3 Nz = {p3-l) Pz+ {pl-1) P4 bN d n- N + ••• + b 0 d n 1 1 1 if bN d -N + ••• + b -N dN 1 n 1 n 2 2 if 0 < n< N if Then c n = f n - f n-1 +f n-{PzP + 1) - fn-p p where 4. 2 4 2 4 £. = 0 if i < 0 . 1 +f n-{p p + 1) 3 4 Upper Bounds for the Coefficients Theorem 6: Adopt the same notations as in Theorem 5. a. be the maximum number of nonzero a . 1 s for n in the range n k .::_ n .::_ k + N .::_ ~ ¢{p p p p ) 1 2 3 4 for any integer k > 0 ; l et Let 49 13 = max I e - en- 1 1 • O<n<N n Then I c n I -< 4 as Proof: From Theorem 5 we have I c n I < 4 max If n - f n- 1 I .< 4 max (an- N + .•• + a n } max I e n - e n- 1 I = 4 a (3 FromTheorem 6 we see that the differences between successive f 1 n s keep the values of c 's small. n itive part, we obtain an upper bound for Theorem 7: polynomial, where p Proof: 1 If we consider only the pos- Ic n I . Let Fp p p p (x} = ~ c xn be the cyclotomic 1 2 3 4 n < Pz < p 3 < p 4 are distinct odd primes. Then In equation ( 38} we proved the formula wher e ~ LJf nx n '"' i1PzP3P4+izP1P3P4+i3P1PzP4+i4P1PzP3+j1P1+jzPz+j3P3+j4P4 =Lix . 50 W e need only consider thos e n in the interval 0 _:: n _:: For these n, f n z1 ¢{p 1 p 2 p 3 p 4 ). is the number of solutions of with p -1 p -1 p -1 2 1 3 0 < i 1 < - - ; 0 < i2 < - - ; 0 < i < _ _ . 2 2 - 3 2 ' <+; p -1 O_::i 4 O_::j 1 _::p 2 -l; O_::j To show that 3 _::p -l; O_::j _::p - l . 4 3 1 Ifn I _:: ~ p 12 {p 2 - l){p 3 - l) it suffices to prove that for fixed {i , i , j , j ) the diophantine equation {40) has at most one 2 3 3 4 solution {i , i , j , j ), because the number of possible choices for 1 4 1 2 {i 2' i 3' j 3' j 4) is ~ p 12 {p 2 - 1){p3 - 1) . Suppose { 40) has more than one solution, say where Then we obtain 51 Reducing this modulo p p , we obtain 2 3 ( 42) But ( 42) is equivalent to the sys tern 1 (j 1-j1 ) p 1 - 0 1 (j 1-j1 ) p 1 + (j 2 -j Since ( 43) z') P2 - O I j 1 -j 1' I :S, p 2 - l , the first congruence relation in (43) is an equality, i.e. , {j -j ') p = 0. 1 1 1 Hence the second congruence in ( 43) becomes Since I j 2 -j z' I < p 3 -1 , the above congruence is an equality. Hence we conclude that j 2 = j 1 2 , and ( 41) becomes Hence we also have i one solution. Since 4 = i~. Thus, for fixed (i ,i ,j ,j ), 2 3 3 4 (40) has at most Therefore we obtain the inequality I c n I < 4 max If n I , this gives us the upper bound 52 CHAPTER V THE CYCLOTOMIC POLYNOMIAL F m (x) WHERE m IS A PRODUCT OF AN ARBITRARY NUMBER OF DISTINCT ODD PRIMES If m is a product of more than four distinct odd primes, the formula for F m (x} in Lemma 2 and the method depending on this lem- ma are no longer applicable. ferent type for F m This chapter contains results of a dif- (x ) , where m is a product of an arbitrary number of odd primes. 5. 1 A Partition Function and Its Generating Function Let S s 1 .::, s 2 .::, s 3 m denote the reduced residue system modulo m. Let .::, ..• .::, s ¢ (m} be its e l ements , chosen to lie in the interval l<s.<m. - 1- We define p{k, m, n} to be the number of ways that an integer k can be partitioned into sum of n distinct members of S m . A generating function for p{k, m, n} is given in the following theorem. n Theorem 8 : Proof: 6 sm II .l= 1 x k.t k = 6 p{k, m, n}x k Consider the coefficient of x. • (44) From the l e ft-hand side of {44) we see that the coe fficient of xk is equal to the number of 53 ways that k can be partitioned into sum of n distinct members of S which is exactly p(k, m, n). 5. 2 m , Hence (44) is an identity. Connection Between p(k, m, n) and the Cyclotomic Coefficients Theorem 9: Conside r the cyclotomic polynomial ¢(m) F where m m (x) = ~ (-1) n c x¢(m) -n n n=O is a product of t distinct odd primes. K For any n .:S, ¢(m) let n = s¢(m) + s¢(m)-1 + · · · + s¢(m)-(n-l) where s¢(m), s¢(m)- l' ..• , s¢(m)-(n- l) are the largest n elements of the reduced residue system modulo m. Then we have en= dfm [~~d}~: m)p(d,m,n~ Proof: µ(:;)] We shall use the following well- known formula: :6 k mod.m (m, k) =l = µ.(m) exp(2nik) m From the definition of the cyclotomic polynomial we have F m (x) = II ( x - exp (J,, m) 1 J, mod m = znu,~"'\ (--mJJ From the hypothesis of the theorem , this is equal to ¢(m) :6 n=O (-l)n c n x¢(m)-n 54 Hence we have c n = {45) where the s. are the elements of S i m . Since e 2ni.l /m is periodic with period m, we can write 2nik m-1 c n = 6 a{k) e m { 46) k=O Collecting the terms e Zni.l /m with .l = k {mod m) and .l < K - 2ni1./m . is p{.l, m, n) , that the coefficient of e 6 a{k) = we see n so we have p{.l, m, n) { 4 7) .l=k {mod m) 1.< K n From { 46) we see that = 6 c 1 b(d, m, n, k 1 ) 2nik') e -:rnr<f { 48) dim k mod m/d 1 {k , m/d)=l n where ~ 6 I I b{d, m, n, k ) = a{k d) . · I I We will prove that b(d, m, n, k ) is independent of k . It can be seen that if we replace e Zni /in by e Znik/m with (k,m) = 1 we get the same set of primitive mth roots of unity S Since c n is a symmetric function of the elements of S . no c h ange in . c th ere is {k, m) = 1. n m . from (45), m i.f we rep1ace e 2rri/m b y e 2nik/m w1.th We can also prove that the set 55 m} 1 2nik m/d . , {e (k I , r;;) : 1 , k modd I is invariant under the replaceme nt of e 2ni/m by e 2nik/m with (k,m) = 1. For d = 1; if. we replace e 2ni/m by e 2nik/m b{ l, m, n, 1) plays the role of b{ 1, m, n, k) . b(l,m,n, 1) then Hence we have = b(l,m,n,k) If we let k go from 2 to m with {m, k) = 1 , then we obtain b( 1, m, n, 1) where (k,m) = 1, k mod m. = = b( 1, m, n, k) Let us write b(l,m,n, 1) = b(l,m,n). Then we have 2nik' ~ b(l,m,n,k ) e k mod m 1 (k , m) = 1 1 1 = b ( 1, m, n) m ~ e k' mod m 1 (k ,m)=l 2nik m 1 For d > 1; if we replace e 2ni/m b y e 2nik/m with (m, k) = 1, then b(d, m, n, 1) plays the role of b(d, m, n, k). b{d, m, n, 1) = b(d, m, n, k) If we let k go from 2 to m/d with (k, m/d) = 1 , b{d, m, n, 1) wher e (k, m/d) = 1, k mod m/d. we have Hence we have = then we obtain = b(d, m, n, k) Write b(d, m, n, 1) = b(d, m, n). Then 56 "'\"' I b(d, m, n, k ) e LJ 2nik m/d 1 1 = b(d ,m,n) k mod m/d 1 (k , m/d)=l """' LJ · k mod m/d 1 (k , m/d)= 1 2nik em/d Hence (48) b e comes :0 en= ~ 1 b{d,m,n) aim ( k 1 :0 2nik em/d )j modm/d 1 {k , m/d)= 1 By the formula 2nik :0 1 e k mod m/d 1 (k , m/d)=l 1 mrcr = µ. (r:) we obtain c n = 6 b{d, m, n) aim But b{d, m, n) = a(d) by {48), so we have c n = 6 aim a(d) µ.(r:;) By ( 46) we have c 5. 3 n = An Upper Bound for the Coefficients Theorem 10: Consider the cyclotomic polynomial r. 57 F m (x) = ¢{m) 6 c n=O x n n where m is a product of t distinct odd primes. Then we have ¢ {m) - i ) -m 2n) I c n I < z<ti <m> ( cos 22n)( ill cos 24n) ill . . . ( cos 2( -z Proof: Since F m (x ) is analytic, we have f n! F(n) (0) = m 2ni F {z) m dz n+l z lzl=l Therefore we obtain f n! n! c n = 2ni I zl =l F (z) m dz n+l z Hence we have I cnl ~;TT F f I zl =l < (z) m dz n+l z 2~ max IFm(z)I 2n I zl =l max I zl =l IFm {z)I To complete the proof we will show that . ( 49) 58 (50) From the definition of F F m (x) = m (x) we see that 2nki) ( x-em II (k, m)=l Therefore we obtain IFm (z) I = II (k, m)=l z - e 2:d I Hence we have max Iz I=1 IF (z)I = m We therefore see that max I zj =l max II I z = 1 (k , m) = 1 I IF z - e 2nki m (51) (z) I is equal to the maximum of the m product of the lengths of the segments between z on the unit circle and e 2nki/m with (k, m) = 1. A We consider a half unit circle 0 Figure 1 B 59 Wri t e C k as the point e 2nik / m ¢ (m ) for k = 1, 2, . .• •-z- - 1. W ri te ¢ (m ) 1 - 2- p where =2 ( 52) IT k =l I A C k l is the le ngt~ of ACk • S i n ce the a n g l e L BAC k = 2nk/ m, we h ave = 2 cos 211 k m Hence ¢ (m ) 2 p = 2- ( co s ~) (c os !:) .. . (cos (¢ (~) - i) ~) We therefore h ave T he probl em now re d uces to showin g that max I1 = i (k, m )=l I zl z- e 2nik m < p 2 ( 53) Co n sid er TI ( k,m)=l It is a c ontinuou s function of z. Iz - e 2:k 1 Let z 0 b e t he point suc h that 2nik II (k,m) = l z0 - e m 2nik = max I1 z i ( k, m ) i I I= = z - e m (5 4) 60 C1 Z O-+-------------+B Figure 2 We draw a diameter z B . 0 Tl = number of L et 2nik e m with (k, m}=l and l .S: k,::::m, which are on the"upper half closed circle. T2 = number of e 2nik m with (k, m)=l and l .S: k.S: m, which are on the lower open half circle. Then we have T + T 2 = ¢ (m) . 1 Let B = e c 1. I c 1. iSO = e = e Write 2ni.l + m e -2n i1. + m 0 e 0 for m 1. = 1, 2, ... '4 for £, m = 1,2, ... ,4 Then we have 2nik I1 (k, m )=l Z 0 - em (55) 61 where z 0 c ~ • I z 0 c ..e,I is the length of z 0 c ..e,' and I z 0 C~I is the length of Say T 1 ,:::. T 2 , then we have T 2 .::::_ zocT l+T 2 T1 + T2 2 Izoc~ < Thus we see that 21 2 ZOCT +T 1 2 +l 2 IZOCTl-11 -< Izoc~2+1I z -< 0 c' T 1+T 2 2 -1 Hence we have (56) But by (52) we see that Combining this with {54), (55), and (56) we have max II z 1 Ck, m> I I= I = z - e 2~kl < p 2 1 This proves (53) and also completes the proof of Theorem 10. 62 REFERENCES 1. T. M. Apostol, Mathematical Analysis, Addison-Wesley, Reading, Mass., 1957. 2. T. M. Aposto l and Herbert S. Zuckerman, On the functional equation F(mn) F( (m, n)) = F(m) F(n) f( {m, n)), Pacific Journal of Mathematics, vol. 14, (1964) pp. 377-384. 3. Douglas R. Anderson and T. M. Apostol, The evaluation of. Ramanujan's sum and generalizations, Duke Mathematical Journal,vol. 20, (1953) pp. 141-338. 4. A. S. Bang, Om Ligningen ¢n(x) = 0, Nyt Tidsskrift for Mathematik (B), vol. 6 (1895) PP.· 6-12. 5. Marion Beiter, The midterm coefficient of the cyclotomic polynomial F pq(x), American Mathematical Monthly, vol. 7 l ( 19 64) pp. 769-70. 6. L. Garlitz, The number of terms in the cyclotomic polynomial F pq(x), American Mathematical Monthly, vol. 73 (1 964) pp. 979-88. 7. L. E. Dickson, History of the The ory of Numbers, Institution of Washington, Washington, 1919. 8. Paul Erdos, On the coe fficients of the cyclotomic polynomial, Bulletin American Mathematical Society,vol. 52 (1946) pp. 179-84. 9. Hele n Habermehl, Sharon R ichardson, and Mary Ann Szwajkos, A note on coe fficients of cyclotomic polynomials, Mathematics Magazine, vol, 37 (1964) pp. 183 - 85. 10. D. H. Lehmer, Some prope rties of the cyclotomic polynomial, Journal of Mathematical Analysis and Applications, vol. 15, (1 966) pp. 105-17. 11. Emma Lehmer, On the magnitude of the coefficients of the cyclotomic polynomial, Bulletin American Mathematical Society, vol. 42 ( 1936) pp. 389-92. 1 2. A. Migotti, Zur Theorie d er Kreistheilungsgleichung, S. -B. der Math. -Naturwiss lasse der Kaiserlichen Akademie der Wissenschaften, Wien, (2) 87 (1883) pp. 7-14. Carnegie 63 13. I. Nive n and H. S. Zuckerman, An Introduction to the The ory of Numbers, John Wile y and Sons, New York, 2nd e d., 1966. 14. H. Rade macher, Lectur es on Elementary Number Theory, Blaisdell, Waltham, Mass., 1964. 15. I. J. Schoenberg, A note on the cyclotomic polynomial, Mathematika, vol. 11 (1964) pp. 131-36.