20230720, 14:13  #1 
Feb 2017
Nowhere
23×283 Posts 
Bounds for cyclotomic polynomials
Using the standard formula
it is easy to show that for integer a > 1 we have (Note that for n > 1 we have the algebraic identity The factors (1  a^{d}) are all less than 1, so K is obviously a lower bound for for all n; likewise, 1/K is an upper bound. It occurred to me to wonder whether I could improve the value of K. After looking at limited numerical evidence, I was led to guess that K = 1  1/a was best possible. We also have the standard identities and The first identity allows us to restrict consideration to squarefree values of n. The second identity shows that for squarefree n, the factor 1  x appears in the numerator when n is the product of evenly many distinct primes, and in the denominator when n is the product of oddly many prime factors. This suggests considering these two cases separately. For n = p, a prime, we have so in this case we have, for integer a > 1, Similarly, for n = pq, the product of two distinct primes, it is not hard to show that for integer a > 1 I suspect that these inequalities persist for products of oddly many and evenly many distinct primes, respectively, but haven't figured out out to prove it. I also suspect these are either well known, or have been busted by counterexample, but so far my searching has failed to find them. If anyone knows a reference, or can devise a proof, please post it. 
20230720, 17:16  #2 
Apr 2020
2164_{8} Posts 
EDITED as original proof had an error
It's sufficient to show that \[1\frac{1}{a} \leq \prod_{d \vert n}\left(1\frac{1}{a^d}\right)^{\mu(d)} \leq 1\] holds for all a>1 and all squarefree n. This can be proved by induction on the number of prime factors of n. The base case is simple. Say n has k prime factors, n=qm with q prime. We assume *both* sides of the inequality hold for m and for all values of a. The lower bound now comes out quite quickly by induction: \[\prod_{d \vert n}\left(1\frac{1}{a^d}\right)^{\mu(d)} = \prod_{d \vert m}\left(1\frac{1}{a^d}\right)^{\mu(d)}\prod_{d \vert m}\left(1\frac{1}{a^{qd}}\right)^{\mu(qd)} \geq 1\frac{1}{a}\] where we bound the left bracket using the lower bound applied to m and a, and the right bracket using the upper bound applied to m and a^q. You can prove the upper bound by showing the stronger result \[\prod_{d \vert n}\left(1\frac{1}{a^d}\right)^{\mu(d)} \leq \left(1\frac{1}{a}\right)\prod_{p \vert n}\left(1\frac{1}{a^p}\right)^{1}.\] This holds by induction, using the lower bound applied to m and a^q to give an upper bound on \(\prod_{d \vert m}\left(1\frac{1}{a^{qd}}\right)^{\mu(qd)}\). It's not too hard to see that the RHS is less than 1. I feel like there must be a better way that I'm missing. It would be nice to prove the upper and lower bounds separately rather than inducting on both at once. This must be in the literature somewhere, but probably just as a lemma so pretty hard to find. Last fiddled with by charybdis on 20230720 at 17:52 
20230720, 20:21  #3  
Feb 2017
Nowhere
23·283 Posts 
Quote:
I believe the lower bound inequality holds when n is the product of evenly many prime factors, and the upper bound holds when n is the product of oddly many prime factors. I think induction on the number of prime factors is the right idea, but so far I haven't been able to make it work. I had also had the idea of adding two new prime factors, to keep the factor 1  1/a on the same side of the fraction bar... 

20230720, 21:02  #4 
Apr 2020
2^{2}×3×5×19 Posts 
You missed that I exchanged the \(\mu\left(\frac{n}{d}\right)\) for \(\mu(d)\), which keeps the expression the same when the number of prime factors is even but takes the reciprocal when it is odd. This reduces the two cases down to one.

20230721, 12:36  #5  
Feb 2017
Nowhere
6509_{10} Posts 
Quote:
I'm still a little surprised I haven't yet been able to find at least the result stated anywhere. 

20230723, 17:33  #6 
Feb 2017
Nowhere
23×283 Posts 
In my first semester as a grad student (fall 1977) I (along with a bunch of other math grad students) was carted off to a number theory conference at Illinois State University. One of the talks was an extraordinarily ingenious proof that certain cyclotomic polynomials have very large coefficients. I no longer remember whether Bahwan Saffari himself gave the talk, or if someone else did with the name Saffari being given in the topic.
The argument and result are given as Theorem 11 in this survey, and as problem 9 of Exercises 4.3.1 in Multiplicative Number Theory I: Classical Theory (which lists it as an unpublished result of Saffari). The basic idea is to produce evaluations of cyclotomic polynomials on the unit circle which have absolute values which are very large compared to their degree. I sketch the argument here. We have Now the quotient of sine values is the "golden ratio" 1.618... The log of the evaluation doubles with each new prime factor. Assuming the first primes == 2 or 3 (mod 5) are used, the log of n obviously increases much more slowly. I happened to notice a very slight improvement to the above result. If we take n to be the product of distinct primes Last fiddled with by Dr Sardonicus on 20230723 at 17:44 Reason: Fix botched formatting 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New cyclotomic factorisations?  Andrew Usher  Number Theory Discussion Group  11  20230526 12:05 
Prime numbers norms of modulo cyclotomic polynomials  carpetpool  carpetpool  24  20171029 23:47 
Polynomials defining the same field as cyclotomic polynomial order 5  carpetpool  carpetpool  0  20170419 20:33 
What Bounds to choose, and what are Bounds  144  Information & Answers  5  20170315 13:36 
Cyclotomic Phi  plandon  Math  22  20090729 18:59 