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,8

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.

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.

Example

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

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}]

Crossrefs

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

Sequence in context: A093320 A082370 A005136 * A058761 A050119 A290253

Adjacent sequences: A138471 A138472 A138473 * A138475 A138476 A138477

Keyword

nonn

Author

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

Status

approved