A138474 Maximum possible magnitude of the x^n coefficient of a cyclotomic polynomial.

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 3, 4, 4, 5, 4, 4, 4, 5, 5, 6, 5, 5, 6, 6, 6, 6, 7, 7, 7, 8, 9, 9, 7, 8, 8, 10, 13, 12, 10, 12, 9, 11, 15, 13, 13, 14, 15, 13, 16, 15, 15, 14, 16, 24, 17, 21, 21, 16, 22, 28, 26, 23

Offset: 0

Author

T. D. Noe, Mar 19 2008, Apr 14 2008, Feb 16 2009

Keywords

• nonn

Comments

Terms for n <= 30 come from Table 1 of the Gallot et al. paper, which quotes results from Moller. Sequence A138475 gives the minimum order of the cyclotomic polynomial that produces that maximal coefficient. A very fast method (due to Grytczuk and Tropak) for computing the coefficients up to x^k in the cyclotomic polynomial Phi(n,x) is given by the Mathematica function coef[k,n] below.

The first n for which a(n) > n is 118. The sequence appears to be monotonic for n > 143. Terms up to n=128 were found by exhaustive search; subsequent terms were found by a much faster hill-climbing method.

Examples

			a(7)=2 is attained for the cyclotomic polynomial Phi(105,x), which has the term -2x^7.
		

References

• A. Grytczuk and B. Tropak, A numerical method for the determination of the cyclotomic polynomial coefficients, Computational number theory (Debrecen, 1989), 15-19, de Gruyter, Berlin, 1991.

Links

• T. D. Noe, Table of n, a(n) for n = 0..1000
• John Abbott and Nico Mexis, Cyclotomic Factors and LRS-Degeneracy, arXiv:2403.08751 [math.AC], 2024. See pp. 8-10.
• Yves Gallot, Pieter Moree and Huib Hommersom, Value distribution of cyclotomic polynomial coefficients, arXiv:0803.2483 [math.NT], 2008.
• H. Möller, Über die i-ten Koeffizienten der Kreisteilungspolynome, Math. Ann. 188 (1970), 26-38.
• Carlo Sanna, A Survey on Coefficients of Cyclotomic Polynomials, arXiv:2111.04034 [math.NT], 2021.

Crossrefs

Cf. A013594 (smallest order of cyclotomic polynomial containing n or -n as a coefficient).

Programs

Mathematica

coef[k_,n_] := Module[{t, b=Table[0,{k+1}]}, t=-MoebiusMu[n]*Table[g=GCD[n,k-m]; MoebiusMu[g]*EulerPhi[g], {m,0,k-1}]; b[[1]]=1; Do[b[[j+1]] = Take[b,j].Take[t,-j]/j, {j,k}]; b]; Table[mx=1; r=PrimePi[k]+1; mnN=Prime[r]; ps=Reverse[Prime[Range[r]]]; Do[d=IntegerDigits[i,2,r]; n=Times@@Pick[ps,d,1]; c=Abs[coef[k,n][[ -1]]]; If[c==mx, mnN=Min[mnN,n], If[c>mx, mx=c; mnN=n]], {i,2^r-1}]; mx, {k,2,20}]