 mersenneforum.org Bounds for cyclotomic polynomials
 Register FAQ Search Today's Posts Mark Forums Read 2023-07-20, 14:13 #1 Dr Sardonicus   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.   2023-07-20, 17:16 #2 charybdis   Apr 2020 22·3·5·19 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 2023-07-20 at 17:52   2023-07-20, 20:21   #3
Dr Sardonicus

Feb 2017
Nowhere

23·283 Posts Quote:
 Originally Posted by charybdis 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.
Unfortunately, this is false when n is prime, which I showed in the OP.

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...   2023-07-20, 21:02   #4
charybdis

Apr 2020

22×3×5×19 Posts Quote:
 Originally Posted by Dr Sardonicus Unfortunately, this is false when n is prime, which I showed in the OP.
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.   2023-07-21, 12:36   #5
Dr Sardonicus

Feb 2017
Nowhere

23·283 Posts Quote:
 Originally Posted by charybdis 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.
Yup. I saw what I expected to see.

I'm still a little surprised I haven't yet been able to find at least the result stated anywhere.   2023-07-23, 17:33 #6 Dr Sardonicus   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 2023-07-23 at 17:44 Reason: Fix botched formatting  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Andrew Usher Number Theory Discussion Group 11 2023-05-26 12:05 carpetpool carpetpool 24 2017-10-29 23:47 carpetpool carpetpool 0 2017-04-19 20:33 144 Information & Answers 5 2017-03-15 13:36 plandon Math 22 2009-07-29 18:59

All times are UTC. The time now is 10:03.

Sun Sep 24 10:03:58 UTC 2023 up 11 days, 7:46, 0 users, load averages: 0.79, 0.77, 0.76