Calculating cyclotomic polynomials
Authors:
Andrew Arnold and Michael Monagan
Journal:
Math. Comp. 80 (2011), 23592379
MSC (2010):
Primary 11Y16; Secondary 1204
Published electronically:
February 17, 2011
MathSciNet review:
2813365
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We present three algorithms to calculate , the cyclotomic polynomial. The first algorithm calculates by a series of polynomial divisions, which we perform using the fast Fourier transform. The second algorithm calculates as a quotient of products of sparse power series. These two algorithms, described in detail in the paper, were used to calculate cyclotomic polynomials of large height and length. In particular, we have found the least for which the height of is greater than , , , and , respectively. The third algorithm, the big prime algorithm, generates the terms of sequentially, in a manner which reduces the memory cost. We use the big prime algorithm to find the minimal known height of cyclotomic polynomials of order five. We include these results as well as other examples of cyclotomic polynomials of unusually large height, and bounds on the coefficient of the term of degree for all cyclotomic polynomials.
 1.
Gennady
Bachman, On the coefficients of cyclotomic polynomials, Mem.
Amer. Math. Soc. 106 (1993), no. 510, vi+80. MR 1172916
(94d:11068), 10.1090/memo/0510
 2.
Gennady
Bachman, Flat cyclotomic polynomials of order three, Bull.
London Math. Soc. 38 (2006), no. 1, 53–60. MR 2201603
(2006j:11032), 10.1112/S0024609305018096
 3.
A. S. Bang.
Om ligningen . Nyt Tidsskrift for Mathematik, (6):612, 1895.
 4.
P.
T. Bateman, C.
Pomerance, and R.
C. Vaughan, On the size of the coefficients of the cyclotomic
polynomial, Topics in classical number theory, Vol. I, II (Budapest,
1981) Colloq. Math. Soc. János Bolyai, vol. 34,
NorthHolland, Amsterdam, 1984, pp. 171–202. MR 781138
(86e:11089)
 5.
D.
M. Bloom, On the coefficients of the cyclotomic polynomials,
Amer. Math. Monthly 75 (1968), 372–377. MR 0227086
(37 #2671)
 6.
Wieb
Bosma, Computation of cyclotomic polynomials with Magma,
Computational algebra and number theory (Sydney, 1992) Math. Appl.,
vol. 325, Kluwer Acad. Publ., Dordrecht, 1995, pp. 213–225.
MR
1344932 (96j:11142)
 7.
Paul
Erdös, On the coefficients of the cyclotomic
polynomial, Bull. Amer. Math. Soc. 52 (1946), 179–184. MR 0014110
(7,242e), 10.1090/S000299041946085389
 8.
Y. Gallot, P. Moree, and H. Hommerson.
Value distribution of cyclotomic polynomial coefficients. Available at http://arxiv.org/abs/0803.2483.
 9.
K.
O. Geddes, S.
R. Czapor, and G.
Labahn, Algorithms for computer algebra, Kluwer Academic
Publishers, Boston, MA, 1992. MR 1256483
(96a:68049)
 10.
A.
Grytczuk and B.
Tropak, A numerical method for the determination of the cyclotomic
polynomial coefficients, Computational number theory (Debrecen, 1989)
de Gruyter, Berlin, 1991, pp. 15–19. MR 1151850
(93c:11116)
 11.
H.
W. Lenstra Jr., Vanishing sums of roots of unity, Proceedings,
Bicentennial Congress Wiskundig Genootschap (Vrije Univ., Amsterdam, 1978)
Math. Centre Tracts, vol. 101, Math. Centrum, Amsterdam, 1979,
pp. 249–268. MR 541398
(81c:10044)
 12.
N. Kaplan.
Personal correspondence.
 13.
Nathan
Kaplan, Flat cyclotomic polynomials of order four and higher,
Integers 10 (2010), A30, 357–363. MR 2684126
(2011k:11169), 10.1515/INTEG.2010.030
 14.
Nathan
Kaplan, Flat cyclotomic polynomials of order three, J. Number
Theory 127 (2007), no. 1, 118–126. MR 2351667
(2008k:11031), 10.1016/j.jnt.2007.01.008
 15.
Yôichi
Koshiba, On the calculations of the coefficients of the cyclotomic
polynomials, Rep. Fac. Sci. Kagoshima Univ. 31
(1998), 31–44. MR 1718402
(2000g:11126)
 16.
Yôichi
Koshiba, On the calculations of the coefficients of the cyclotomic
polynomials. II, Rep. Fac. Sci. Kagoshima Univ. 33
(2000), 55–59. MR 1833785
(2002i:11132)
 17.
Helmut
Maier, The size of the coefficients of cyclotomic polynomials,
Analytic number theory, Vol.\ 2 (Allerton Park, IL, 1995) Progr. Math.,
vol. 139, Birkhäuser Boston, Boston, MA, 1996,
pp. 633–639. MR 1409383
(97g:11106)
 18.
H.
L. Montgomery and R.
C. Vaughan, The order of magnitude of the 𝑚th coefficients
of cyclotomic polynomials, Glasgow Math. J. 27
(1985), 143–159. MR 819835
(87e:11026), 10.1017/S0017089500006145
 19.
Pieter
Moree, Inverse cyclotomic polynomials, J. Number Theory
129 (2009), no. 3, 667–680. MR 2488596
(2009k:11199), 10.1016/j.jnt.2008.10.004
 20.
T.D. Noe.
Least such that the coefficient of cyclotomic polynomial phi(k,x) has the largest possible magnitude. Sequence A138475 in N. J. A. Sloane (Ed.), The OnLine Encyclopedia of Integer Sequences (2008), http://www.research.att.com/~njas/sequences/A138475.
 21.
T.D. Noe.
Maximum possible magnitude of the coefficient of a cyclotomic polynomial. Sequence A138474 in N. J. A. Sloane (Ed.), The OnLine Encyclopedia of Integer Sequences (2008), published electronically at http://www.research.att.com/~njas/sequences/A138474.
 22.
T.D. Noe.
Numbers n such that phi(n,x) is a flat cyclotomic polynomial of order four. Sequence A117318 in N. J. A. Sloane (Ed.), The OnLine Encyclopedia of Integer Sequences (2008), http://www.research.att.com/~njas/sequences/A117318.
 23.
T.D. Noe.
Numbers n such that phi(n,x) is a flat cyclotomic polynomial of order three. Sequence A117223 in N. J. A. Sloane (Ed.), The OnLine Encyclopedia of Integer Sequences (2008), http://www.research.att.com/~njas/sequences/A117223.
 24.
T.D. Noe.
Odd squarefree numbers n such that the cyclotomic polynomial phi(n,x) is not coefficient convex. Sequence A146960 in N. J. A. Sloane (Ed.), The OnLine Encyclopedia of Integer Sequences (2008), http://www.research.att.com/~njas/sequences/A146960.
 25.
R.
Thangadurai, On the coefficients of cyclotomic polynomials,
Cyclotomic fields and related topics (Pune, 1999) Bhaskaracharya
Pratishthana, Pune, 2000, pp. 311–322. MR 1802391
(2001k:11213)
 26.
Joachim
von zur Gathen and Jürgen
Gerhard, Modern computer algebra, 2nd ed., Cambridge
University Press, Cambridge, 2003. MR 2001757
(2004g:68202)
 1.
 G. Bachman.
On the coefficients of cyclotomic polynomials. Mem. Amer. Math. Soc., 106(510):vi+80, 1993. MR 1172916 (94d:11068)
 2.
 G. Bachman.
Flat cyclotomic polynomials of order three. Bull. London Math. Soc., 38(1):5360, 2006. MR 2201603 (2006j:11032)
 3.
 A. S. Bang.
Om ligningen . Nyt Tidsskrift for Mathematik, (6):612, 1895.
 4.
 P.T. Bateman, C. Pomerance, and R.C. Vaughan.
On the size of the coefficients of the cyclotomic polynomial. In Topics in classical number theory, Vol. I, II (Budapest, 1981), volume 34 of Colloq. Math. Soc. János Bolyai, pages 171202. NorthHolland, Amsterdam, 1984. MR 781138 (86e:11089)
 5.
 D.M. Bloom.
On the coefficients of the cyclotomic polynomials. Amer. Math. Monthly, 75:372377, 1968. MR 0227086 (37:2671)
 6.
 W. Bosma.
Computation of cyclotomic polynomials with Magma. In Computational algebra and number theory (Sydney, 1992), volume 325 of Math. Appl., pages 213225. Kluwer Acad. Publ., Dordrecht, 1995. MR 1344932 (96j:11142)
 7.
 Paul Erdös.
On the coefficients of the cyclotomic polynomial. Bull. Amer. Math. Soc., 52:179184, 1946. MR 0014110 (7:242e)
 8.
 Y. Gallot, P. Moree, and H. Hommerson.
Value distribution of cyclotomic polynomial coefficients. Available at http://arxiv.org/abs/0803.2483.
 9.
 K.O. Geddes, S.R. Czapor, and G. Labahn.
Algorithms for Computer Algebra. Kluwer Academic Publishers, Boston, 1992. MR 1256483 (96a:68049)
 10.
 A. Grytczuk and B. Tropak.
A numerical method for the determination of the cyclotomic polynomial coefficients. In Computational number theory (Debrecen, 1989), pages 1519. de Gruyter, Berlin, 1991. MR 1151850 (93c:11116)
 11.
 Jr H.W. Lenstra.
Vanishing sums of roots of unity. In Proceedings, Bicentennial Congress Wiskundig Genootschap (Vrije Univ., Amsterdam, 1978), Part II, volume 101 of Math. Centre Tracts, pages 249268, Amsterdam, 1979. Math. Centrum. MR 541398 (81c:10044)
 12.
 N. Kaplan.
Personal correspondence.
 13.
 N. Kaplan.
Flat cyclotomic polynomials of order four or higher. Integers, 10:A30, 357363, 2010. MR 2684126
 14.
 N. Kaplan.
Flat cyclotomic polynomials of order three. J. Number Theory, 127(1):118126, 2007. MR 2351667 (2008k:11031)
 15.
 Y. Koshiba.
On the calculations of the coefficients of the cyclotomic polynomials. Rep. Fac. Sci. Kagoshima Univ., (31):3144, 1998. MR 1718402 (2000g:11126)
 16.
 Y. Koshiba.
On the calculations of the coefficients of the cyclotomic polynomials. II. Rep. Fac. Sci. Kagoshima Univ., (33):5559, 2000. MR 1833785 (2002i:11132)
 17.
 H. Maier.
The size of the coefficients of cyclotomic polynomials. In Analytic number theory, Vol. 2 (Allerton Park, IL, 1995), volume 139 of Progr. Math., pages 633639. Birkhäuser Boston, Boston, MA, 1996. MR 1409383 (97g:11106)
 18.
 H.L. Montgomery and R. C. Vaughan.
The order of magnitude of the th coefficients of cyclotomic polynomials. Glasgow Math. J., 27:143159, 1985. MR 819835 (87e:11026)
 19.
 P. Moree.
Inverse cyclotomic polynomials. J. Number Theory, 129(3):667680, 2009. MR 2488596 (2009k:11199)
 20.
 T.D. Noe.
Least such that the coefficient of cyclotomic polynomial phi(k,x) has the largest possible magnitude. Sequence A138475 in N. J. A. Sloane (Ed.), The OnLine Encyclopedia of Integer Sequences (2008), http://www.research.att.com/~njas/sequences/A138475.
 21.
 T.D. Noe.
Maximum possible magnitude of the coefficient of a cyclotomic polynomial. Sequence A138474 in N. J. A. Sloane (Ed.), The OnLine Encyclopedia of Integer Sequences (2008), published electronically at http://www.research.att.com/~njas/sequences/A138474.
 22.
 T.D. Noe.
Numbers n such that phi(n,x) is a flat cyclotomic polynomial of order four. Sequence A117318 in N. J. A. Sloane (Ed.), The OnLine Encyclopedia of Integer Sequences (2008), http://www.research.att.com/~njas/sequences/A117318.
 23.
 T.D. Noe.
Numbers n such that phi(n,x) is a flat cyclotomic polynomial of order three. Sequence A117223 in N. J. A. Sloane (Ed.), The OnLine Encyclopedia of Integer Sequences (2008), http://www.research.att.com/~njas/sequences/A117223.
 24.
 T.D. Noe.
Odd squarefree numbers n such that the cyclotomic polynomial phi(n,x) is not coefficient convex. Sequence A146960 in N. J. A. Sloane (Ed.), The OnLine Encyclopedia of Integer Sequences (2008), http://www.research.att.com/~njas/sequences/A146960.
 25.
 R. Thangadurai.
On the coefficients of cyclotomic polynomials. In Cyclotomic fields and related topics (Pune, 1999), pages 311322. Bhaskaracharya Pratishthana, Pune, 2000. MR 1802391 (2001k:11213)
 26.
 J. von zur Gathen and J. Gerhard.
Modern computer algebra. Cambridge University Press, Cambridge, second edition, 2003. MR 2001757 (2004g:68202)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2010):
11Y16,
1204
Retrieve articles in all journals
with MSC (2010):
11Y16,
1204
Additional Information
Andrew Arnold
Affiliation:
Centre for Experimental and Constructive Mathematics, Simon Fraser University, Burnaby, BC V5A 1S6, Canada
Email:
ada26@sfu.ca
Michael Monagan
Affiliation:
Centre for Experimental and Constructive Mathematics, Simon Fraser University, Burnaby, BC V5A 1S6, Canada
Email:
mmonagan@cecm.sfu.ca
DOI:
http://dx.doi.org/10.1090/S002557182011024671
Received by editor(s):
October 10, 2008
Received by editor(s) in revised form:
July 17, 2010
Published electronically:
February 17, 2011
Additional Notes:
This work was supported by NSERC of Canada and the MITACS NCE of Canada
Article copyright:
© Copyright 2011
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
