## Calculating cyclotomic polynomials

HTML articles powered by AMS MathViewer

- by Andrew Arnold and Michael Monagan PDF
- Math. Comp.
**80**(2011), 2359-2379 Request permission

## Abstract:

We present three algorithms to calculate $\Phi _n(z)$, the $n_{th}$ cyclotomic polynomial. The first algorithm calculates $\Phi _n(z)$ by a series of polynomial divisions, which we perform using the fast Fourier transform. The second algorithm calculates $\Phi _n(z)$ 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 $n$ for which the height of $\Phi _n(z)$ is greater than $n$, $n^2$, $n^3$, and $n^4$, respectively. The third algorithm, the big prime algorithm, generates the terms of $\Phi _n(z)$ 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 $k$ for all cyclotomic polynomials.## References

- Gennady Bachman,
*On the coefficients of cyclotomic polynomials*, Mem. Amer. Math. Soc.**106**(1993), no. 510, vi+80. MR**1172916**, DOI 10.1090/memo/0510 - Gennady Bachman,
*Flat cyclotomic polynomials of order three*, Bull. London Math. Soc.**38**(2006), no. 1, 53–60. MR**2201603**, DOI 10.1112/S0024609305018096 - A. S. Bang. Om ligningen $\phi _n(x)=0$.
*Nyt Tidsskrift for Mathematik*, (6):6–12, 1895. - 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, North-Holland, Amsterdam, 1984, pp. 171–202. MR**781138** - D. M. Bloom,
*On the coefficients of the cyclotomic polynomials*, Amer. Math. Monthly**75**(1968), 372–377. MR**227086**, DOI 10.2307/2313417 - 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** - Paul Erdös,
*On the coefficients of the cyclotomic polynomial*, Bull. Amer. Math. Soc.**52**(1946), 179–184. MR**14110**, DOI 10.1090/S0002-9904-1946-08538-9 - Y. Gallot, P. Moree, and H. Hommerson. Value distribution of cyclotomic polynomial coefficients. Available at http://arxiv.org/abs/0803.2483.
- K. O. Geddes, S. R. Czapor, and G. Labahn,
*Algorithms for computer algebra*, Kluwer Academic Publishers, Boston, MA, 1992. MR**1256483**, DOI 10.1007/b102438 - 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** - 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** - N. Kaplan. Personal correspondence.
- Nathan Kaplan,
*Flat cyclotomic polynomials of order four and higher*, Integers**10**(2010), A30, 357–363. MR**2684126**, DOI 10.1515/INTEG.2010.030 - Nathan Kaplan,
*Flat cyclotomic polynomials of order three*, J. Number Theory**127**(2007), no. 1, 118–126. MR**2351667**, DOI 10.1016/j.jnt.2007.01.008 - Yôichi Koshiba,
*On the calculations of the coefficients of the cyclotomic polynomials*, Rep. Fac. Sci. Kagoshima Univ.**31**(1998), 31–44. MR**1718402** - 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** - 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** - H. L. Montgomery and R. C. Vaughan,
*The order of magnitude of the $m$th coefficients of cyclotomic polynomials*, Glasgow Math. J.**27**(1985), 143–159. MR**819835**, DOI 10.1017/S0017089500006145 - Pieter Moree,
*Inverse cyclotomic polynomials*, J. Number Theory**129**(2009), no. 3, 667–680. MR**2488596**, DOI 10.1016/j.jnt.2008.10.004 - T.D. Noe. Least $k$ such that the $x^n$ coefficient of cyclotomic polynomial phi(k,x) has the largest possible magnitude. Sequence A138475 in N. J. A. Sloane (Ed.), The On-Line Encyclopedia of Integer Sequences (2008), http://www.research.att.com/~njas/sequences/A138475.
- T.D. Noe. Maximum possible magnitude of the $x^n$ coefficient of a cyclotomic polynomial. Sequence A138474 in N. J. A. Sloane (Ed.), The On-Line Encyclopedia of Integer Sequences (2008), published electronically at http://www.research.att.com/~njas/sequences/A138474.
- 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 On-Line Encyclopedia of Integer Sequences (2008), http://www.research.att.com/~njas/sequences/A117318.
- 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 On-Line Encyclopedia of Integer Sequences (2008), http://www.research.att.com/~njas/sequences/A117223.
- 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 On-Line Encyclopedia of Integer Sequences (2008), http://www.research.att.com/~njas/sequences/A146960.
- R. Thangadurai,
*On the coefficients of cyclotomic polynomials*, Cyclotomic fields and related topics (Pune, 1999) Bhaskaracharya Pratishthana, Pune, 2000, pp. 311–322. MR**1802391** - Joachim von zur Gathen and Jürgen Gerhard,
*Modern computer algebra*, 2nd ed., Cambridge University Press, Cambridge, 2003. MR**2001757**

## 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
- 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
- © Copyright 2011
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp.
**80**(2011), 2359-2379 - MSC (2010): Primary 11Y16; Secondary 12-04
- DOI: https://doi.org/10.1090/S0025-5718-2011-02467-1
- MathSciNet review: 2813365