WorksMathematics
The totient bound and extremal gaps in cyclotomic polynomials
Abstract
Let be odd and squarefree, and let be prime. If , every gap in has length strictly less than . If , the maximum gap has length and occurs exactly times. We determine its positions and endpoint coefficients. These results prove the equality criterion of Ambrosino, Hong and Lee and the multiplicity formula of Zhang. We also treat repeated prime factors, even cofactors and extremal zero runs in periodic coefficient blocks.
Introduction
A primitive th root of unity is a complex number of multiplicative order . The th cyclotomic polynomial is , where the product runs over all such roots. Its degree is Euler’s totient . For , write . A gap is a pair of consecutive elements of . Its length is , so it contains intermediate zero coefficients. Write for the greatest gap length and for the number of gaps of that length.
For odd primes , Hong, Lee, Lee and Park [1] proved that . For example, with and ,
The consecutive exponent differences are , so . Camburu, Ciolan, Luca, Moree and Shparlinski [2] and Zhang [3] independently showed that the length occurs times. In the two occurrences are and , in agreement with .
Two conjectures extend these results to products of distinct odd primes. In both, write such a product as , where is its largest prime factor.
Conjecture 1.1 (Ambrosino, Hong and Lee [4 Conjecture 7]). The maximum gap of has length if and only if .
Conjecture 1.2 (Zhang [5 Conjecture 0.1]). If and , then
Al-Kateeb, Ambrosino, Hong and Lee [6 Theorem 1] proved the length formula for . Theorem 1.1(i) completes Conjecture 1.1 by proving strict inequality for . Part (ii) proves the count in Conjecture 1.2 for any number of prime factors and gives the positions and endpoint coefficients of all maximum gaps.
Theorem 1.1. Let be odd and squarefree, let be a prime with , and put .
(i) . The maximum gap length satisfies .
(ii) . The maximum gap length is . Put and . There are exactly gaps of length , whose pairs of endpoints are
In the first pair, the coefficient of is and that of is . In the second, the coefficient of is and that of is . Every coefficient strictly between the two endpoints of either pair is zero.
Example. Take , so . For , the maximum in is and occurs four times [5 Theorem 0.1]. For , we have and . The two gaps of length in run from to and from to .
2020 Mathematics Subject Classification. 11C08.
Key words and phrases. Cyclotomic polynomial, maximum gap, Euler totient function, roots of unity.
When , Conjecture 1.1 follows directly from and . For , Theorem 1.1 allows any prime . Sanna [7, §6] records the proposed upper bound for . Zhang [5, Theorem 0.1] determined the maximum and its multiplicity for . Benoist and Perucca [8] proved the predicted count for , with prime, and .
The proof of Theorem 1.1 uses the product , which also occurs in Kaplan’s binary argument in [2 §2.1]. Truncating it at the right endpoint of a gap reduces the equality case to a question about a partial sum of .
Corollary 1.2 (Odd cofactors). Let be odd and let be prime. Put , and . Then
The gaps of length are exactly
Their endpoint coefficients are and $(1,-1) gaps of length $d.
Proof. For , put and . In the Möbius product for , a divisor contributes precisely when , that is, when with . This gives the classical radical reduction [1 §2]
Set . Since , we have and hence . Every gap of corresponds to the gap with the same endpoint coefficients. Theorem 1.1 applied to now gives the claim, since and .
For example, take and . In the gaps and of become and . Both have length , as .
Section 4 treats every even cofactor by the radical and sign identities of [1 §2]. For squarefree even and , the threshold is . The final section describes the cyclic runs of zeros for both parities.
Truncation and complementary partial sums
Fix . Write , where , and put for . We have .
Proposition 2.1. For every prime one has . Suppose that is a gap of length , and let . Then for every primitive th root ,
Proof. Set . A root of unity of order has th power of order . Since , this order equals precisely when or . The roots of are simple because this polynomial divides . Both factors on the left below are monic, so comparison of roots and then degrees gives
For any gap , let be the sum of the terms of of degree less than . Since is the last support exponent before , we have and . On the right of (2.2), the term survives truncation modulo precisely if . The indices in this range are exactly . Moreover, , since is an exponent of . Thus , which gives . Consequently
If , the left side has degree , and the right side has degree at most . Their difference is divisible by , hence is zero. Evaluation at a primitive th root gives . But is again primitive of order , so its minimal polynomial over has degree . This contradicts and . The gap bound follows.
Now suppose . By (5), there is a polynomial such that . The difference has degree exactly , since . Its leading coefficient is , since is monic. The quotient therefore has degree zero. Comparing the coefficients of gives , so
At the left side vanishes, giving (3).
Lemma 2.2. Suppose is odd and squarefree. For a primitive th root and , one has .
Proof. Inversion permutes the primitive th roots, so is reciprocal and . Put . Reversing the terms after index in gives
Here and the coefficients of are real. Let and . Both and are positive, and . The product formula , with the Möbius function, gives , since only the factor with contributes a linear term and is squarefree. Thus satisfies , and because is the largest index for which .
Suppose that belongs to . By the equality of moduli above, for either choice of . Set
The exponents in range from to , so and . Since and has real coefficients, . Hence
The coefficient of in is . Since , it is also the constant coefficient of , and it is nonzero. Thus is a nonzero polynomial over of degree less than vanishing at , contrary to the minimality of .
The extremal gaps
Proof of Theorem 1.1. Set , , and . Proposition 2.1 gives . For a gap of length , take as in (3). Since , Lemma 2.2 applied to gives or .
If , then and . The only rational root of unity of odd order is . Thus and . Writing gives the first family in (1.1).
If , then , so and . The inequalities give . Write . Since , we obtain , as in the second family.
In both cases is a positive integer with , hence .
(i) Suppose . Then , so neither case can yield a gap of length . By Proposition 2.1, all gaps therefore have length less than .
(ii) Suppose . Then . To realize the candidates in (1.1), put . This polynomial has degree , constant coefficient , and leading coefficient . In we have
By (4), and agree in all degrees less than . For we have , since and . The st translate in (6) ends at exponent , and the th starts at . This gives the first family with endpoint coefficients . The reciprocity of gives the second family and reverses the endpoint coefficients. The right endpoints in the two families are congruent to 0 and modulo , respectively. These classes are distinct since and . Each family therefore contributes distinct gaps, giving maximum gaps in total.
Example 3.1. Take and . Then , , and . In increasing order the four maximum gaps are .
Even values of the cofactor
For an even integer , let be the product of its distinct odd prime divisors, with the empty product equal to 1. Write
Throughout this section is a prime with , so is odd. Put .
Theorem 4.1. Let be even and let be a prime. Then
If , the gaps of length and the coefficients at their endpoints, in increasing order of exponent, are given by
| gap of length | endpoint coefficients |
Table 1.
There are exactly such gaps. If , all gaps have length . They are with coefficients , for $0\le k\le p-2.
Proof. We combine the radical reduction (2) with the sign identity of [1 §2]. For odd , negation bijects primitive th roots with primitive th roots. Since is even, this gives
Now and , whence
Thus a nonzero coefficient at degree in gives the coefficient at degree in . The ordered supports correspond bijectively, so every gap is scaled by with its multiplicity preserved.
If , apply Theorem 1.1 with cofactor . For , part (i) gives strict inequality. For , part (ii) gives the maximum gaps of . Writing , the two exponents of the first gap both have the parity of , since is odd and is even. Multiplication of both coefficients by gives the first row. Reflection in degree reverses the coefficients and gives the second row. Distinctness and the range of follow from the support bijection. If , the same identity gives .
For squarefree even , one has and . Thus equality already holds for , and the count is . For , all gaps are multiples of , hence . In that range the actual maximum is still given by the reduction (4.1). For example, if is prime, apply Theorem 1.1(ii) with the smaller of as cofactor. The actual maximum is then and occurs times.
Example 4.2. For , , we have , , and . The extreme pairs are and , with coefficients and , respectively. For and the same prime, is unchanged and . The extreme pairs become and with the same coefficients. For , , the reduction to instead gives four maximum gaps of length 6 discussed after Theorem 1.1.
Zero runs in the periodic blocks
The partial-sum argument also identifies the blocks in the coefficient decomposition of [6] that can contain an extremal run of zeros. Continue with the notation and hypotheses of Theorem 1.1, and put . Work in and put
For , let denote the coefficient at the residue of modulo in the representative of degree less than . Multiplication by rotates this list of coefficients. For , the coefficients in a short interval ending at satisfy
Indeed, (2.2) and (3.1) give the formula with . Passing from to adds terms with . Each vanishes because and . Thus (5.1) also holds when the interval crosses several multiples of .
Proposition 5.1. No contains cyclically consecutive zeros. A run of cyclically consecutive zeros occurs precisely for and , once per period in each case. In it ends at residue , and in it ends at residue .
Proof. Since , cancellation in gives
In particular , because for a primitive th root . The polynomial representative of every rotation of is divisible by . Rotate a run of zeros to the final positions. The representative then has degree at most . Since , this excludes . For the representative must equal for some . Undoing the rotation yields in . By (5.2), . Lemma 2.2 forces or .
The last entries of are zero. If a rotation also has these final zeros, it equals by the same degree bound. Equation (5.2) then gives , so . Thus the run in is unique. Finally, (2.2) and (5.2) give in . Its unique run is therefore shifted by residues.
Blocks for an even cofactor
Let be even and prime, and use the notation of Section 4. Define , , with this even by the same formulas as above, and use the representative modulo to read each block.
Proposition 5.2. Let be even. No contains cyclically consecutive zeros. A run of length occurs precisely for the indices
In each such block there are exactly two runs of length per period of . In the first range they end at residues , , and in the second at , , all taken modulo . For a power of two the two ranges coincide.
Proof. The degree and cancellation argument in Proposition 5.1 applies to every . It excludes consecutive zeros, and a run of length forces with . Hence at any primitive th root .
Suppose . As in (4.1) we have . Thus the prefix is the prefix of through index , evaluated at , a primitive th root. Its squared modulus is . Lemma 2.2 forces to be or , which gives the asserted ranges. In the first range and . In the second , whence by (5.2) and .
The last positions of vanish. A rotation with the same final zeros must equal a rational multiple of , by the degree argument. Cancellation implies for its shift , so (mod ). The second shift occurs because gives modulo . This gives the two listed end residues for and their translates for .
Finally, if , then , , and every . The two runs end immediately before and . As , both lists of end residues agree.
:::
For the only block is ; both cyclic positions are nonzero.
Declaration
This paper was written by the author in collaboration with GPT 6 Astra.
References
- [1]H. Hong, E. Lee, H.-S. Lee and C.-M. Park, Maximum gap in (inverse) cyclotomic polynomial, J. Number Theory 132 (2012), 2297–2315.arxiv.org/abs/1101.4255
- [2]O.-M. Camburu, E.-A. Ciolan, F. Luca, P. Moree and I. E. Shparlinski, Cyclotomic coefficients: gaps and jumps, J. Number Theory 163 (2016), 211–237.arxiv.org/abs/1507.07098
- [3]B. Zhang, Remarks on maximum gap in binary cyclotomic polynomials, Bull. Math. Soc. Sci. Math. Roumanie 59(107) (2016), no. 1, 109–115.
- [4]M. Ambrosino, H. Hong and E. Lee, Lower bounds for maximum gap in (inverse) cyclotomic polynomials, arXiv:1702.07650 (2017).arxiv.org/abs/1702.07650
- [5]B. Zhang, Maximum gaps in a class of ternary cyclotomic polynomials, Adv. Math. (China) 48 (2019), 419–429.DOI
- [6]A. Al-Kateeb, M. Ambrosino, H. Hong and E. Lee, Maximum gap in cyclotomic polynomials, J. Number Theory 229 (2021), 1–15.arxiv.org/abs/1911.11667
- [8]A. Benoist and A. Perucca, The ternary cyclotomic polynomials Φ₃pq, Involve 19 (2026), no. 1, 51–72.DOI