Bounds for cyclotomic polynomials

Dr Sardonicus · 2023-07-20, 14:13

Using the standard formula

$\Phi_{n}(x)\;=\;\prod_{d\mid n}(x^{d} \; - \; 1)^{\mu(\frac{n}{d})}$

it is easy to show that for integer a > 1 we have

$K\cdot a^{\varphi(n)} \; \le \; \Phi_{n}(a) \; \le \frac{1}{K}\cdot a^{\varphi(n)}\text{ where}$

$K \; = \; \prod_{i=1}^{\infty}(1 \; - \; a^{-i})$

(Note that for n > 1 we have the algebraic identity

$\Phi_{n}(x)\;=\;x^{\varphi(n)}\Phi(\frac{1}{x})$

The factors (1 - a^-d) are all less than 1, so K is obviously a lower bound for $\Phi_{n}(\frac{1}{a})$ 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

$\Phi_{p\cdot n}(x)\;=\;\Phi_{n}(x^{p})\text{ if p divides n}$

and

$\Phi_{p\cdot n}(x)\;=\;\frac{\Phi_{n}(x^{p})}{\Phi_{n}(x)}\text{ if p does not divide n.}$

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

$\Phi_{p}(x)\;=\;\frac{(1 - x^{-p})}{(1 - \frac{1}{x})}x^{\varphi(p)}$

so in this case we have, for integer a > 1,

$a^{\varphi(p)}\;\le\;\Phi_{p}(a)\;\le\;\frac{1}{(1 - \frac{1}{a})}a^{\varphi(p)}$

Similarly, for n = pq, the product of two distinct primes, it is not hard to show that for integer a > 1

$(1\;-\;\frac{1}{a})a^{\varphi(pq)}\;\le\;\Phi_{pq}(a)\;\le\;a^{\varphi(pq)}$

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.

charybdis · 2023-07-20, 17:16

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.

Dr Sardonicus · 2023-07-20, 20:21

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...

charybdis · 2023-07-20, 21:02

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.

Dr Sardonicus · 2023-07-21, 12:36

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.

Dr Sardonicus · 2023-07-23, 17:33

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

$\Phi_{n}(x)\;=\;\prod_{d\mid n}(x^{d} \; - \; 1)^{\mu(\frac{n}{d})}\text{. Substituting }x\;=\;e^{i\theta}\text{ we obtain for n > 1}$

$\Phi_{n}(e^{i\theta})\;=\;e^{\frac{i\theta\varphi(n)}{2}}\prod_{d\mid n}\sin(\frac{d\theta}{2})^{\mu(\frac{n}{d})}\text{ so that}$

$\|\Phi_{n}(e^{i\theta})\|\;=\;\prod_{d\mid n}\|\sin(\frac{d\theta}{2})\|^{\mu(\frac{n}{d})}$

$\text{Now, take n to be the product of primes }p\;\equiv\;\pm2\;\pmod{5}\text{ and }\theta\;=\;\frac{2k\pi}{5}\text{ where } k\;=\;1\text{ or }2\text{.}$

$\text{If the divisor d has evenly many prime factors, then }d\;\equiv\;\pm\;1\;\pmod{5}\text{ and if d has oddly many prime factors, then }d\;\equiv\;\pm\;2\;\pmod{5}\text{.}$

$\text{Taking } k \;=\;1\text{ if }n\tex{ has oddly many prime factors and }k\;=\;2\text{ if }n\text{ has evenly many prime factors, we obtain }$

$\|\Phi_{n}(e^{\frac{2k\pi i}{5}})\|\;=\;$\frac{\sin(\frac{2\pi}{5})}{sin(\frac{\pi}{5})}$^{2^{r-1}}\text{ where }r\text{ is the number of prime factors of n.}$

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

$p\;\equiv\;\pm3\;\pmod{10}\text{, } k\;=\;1\text{ or }3\text{ (instead of 1 or 2 ), and }\theta\;=\;\frac{k\pi }{5}\text{ instead of }\frac{2k\p}{5}\text{, we obtain}$

$\|\Phi_{n}(e^{\frac{k\pi i}{5}})\|\;=\;$\frac{\sin(\frac{3\pi}{10})}{sin(\frac{\pi}{10})}$^{2^{r-1}}\;=\;$\frac{\sin(\frac{2\pi}{5})}{sin(\frac{\pi}{5})}$^{2^{r}}$

2023-07-20, 14:13	#1
Dr Sardonicus Feb 2017 Nowhere 23×283 Posts	Bounds for cyclotomic polynomials Using the standard formula $\Phi_{n}(x)\;=\;\prod_{d\mid n}(x^{d} \; - \; 1)^{\mu(\frac{n}{d})}$ it is easy to show that for integer a > 1 we have $K\cdot a^{\varphi(n)} \; \le \; \Phi_{n}(a) \; \le \frac{1}{K}\cdot a^{\varphi(n)}\text{ where}$ $K \; = \; \prod_{i=1}^{\infty}(1 \; - \; a^{-i})$ (Note that for n > 1 we have the algebraic identity $\Phi_{n}(x)\;=\;x^{\varphi(n)}\Phi(\frac{1}{x})$ The factors (1 - a^-d) are all less than 1, so K is obviously a lower bound for $\Phi_{n}(\frac{1}{a})$ 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 $\Phi_{p\cdot n}(x)\;=\;\Phi_{n}(x^{p})\text{ if p divides n}$ and $\Phi_{p\cdot n}(x)\;=\;\frac{\Phi_{n}(x^{p})}{\Phi_{n}(x)}\text{ if p does not divide n.}$ 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 $\Phi_{p}(x)\;=\;\frac{(1 - x^{-p})}{(1 - \frac{1}{x})}x^{\varphi(p)}$ so in this case we have, for integer a > 1, $a^{\varphi(p)}\;\le\;\Phi_{p}(a)\;\le\;\frac{1}{(1 - \frac{1}{a})}a^{\varphi(p)}$ Similarly, for n = pq, the product of two distinct primes, it is not hard to show that for integer a > 1 $(1\;-\;\frac{1}{a})a^{\varphi(pq)}\;\le\;\Phi_{pq}(a)\;\le\;a^{\varphi(pq)}$ 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 2²·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-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 $\Phi_{n}(x)\;=\;\prod_{d\mid n}(x^{d} \; - \; 1)^{\mu(\frac{n}{d})}\text{. Substituting }x\;=\;e^{i\theta}\text{ we obtain for n > 1}$ $\Phi_{n}(e^{i\theta})\;=\;e^{\frac{i\theta\varphi(n)}{2}}\prod_{d\mid n}\sin(\frac{d\theta}{2})^{\mu(\frac{n}{d})}\text{ so that}$ $\\|\Phi_{n}(e^{i\theta})\\|\;=\;\prod_{d\mid n}\\|\sin(\frac{d\theta}{2})\\|^{\mu(\frac{n}{d})}$ $\text{Now, take n to be the product of primes }p\;\equiv\;\pm2\;\pmod{5}\text{ and }\theta\;=\;\frac{2k\pi}{5}\text{ where } k\;=\;1\text{ or }2\text{.}$ $\text{If the divisor d has evenly many prime factors, then }d\;\equiv\;\pm\;1\;\pmod{5}\text{ and if d has oddly many prime factors, then }d\;\equiv\;\pm\;2\;\pmod{5}\text{.}$ $\text{Taking } k \;=\;1\text{ if }n\tex{ has oddly many prime factors and }k\;=\;2\text{ if }n\text{ has evenly many prime factors, we obtain }$ $\\|\Phi_{n}(e^{\frac{2k\pi i}{5}})\\|\;=\;\(\frac{\sin(\frac{2\pi}{5})}{sin(\frac{\pi}{5})}\)^{2^{r-1}}\text{ where }r\text{ is the number of prime factors of n.}$ 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 $p\;\equiv\;\pm3\;\pmod{10}\text{, } k\;=\;1\text{ or }3\text{ (instead of 1 or 2 ), and }\theta\;=\;\frac{k\pi }{5}\text{ instead of }\frac{2k\p}{5}\text{, we obtain}$ $\\|\Phi_{n}(e^{\frac{k\pi i}{5}})\\|\;=\;\(\frac{\sin(\frac{3\pi}{10})}{sin(\frac{\pi}{10})}\)^{2^{r-1}}\;=\;\(\frac{\sin(\frac{2\pi}{5})}{sin(\frac{\pi}{5})}\)^{2^{r}}$ Last fiddled with by Dr Sardonicus on 2023-07-23 at 17:44 Reason: Fix botched formatting

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
New cyclotomic factorisations?	Andrew Usher	Number Theory Discussion Group	11	2023-05-26 12:05
Prime numbers norms of modulo cyclotomic polynomials	carpetpool	carpetpool	24	2017-10-29 23:47
Polynomials defining the same field as cyclotomic polynomial order 5	carpetpool	carpetpool	0	2017-04-19 20:33
What Bounds to choose, and what are Bounds	144	Information & Answers	5	2017-03-15 13:36
Cyclotomic Phi	plandon	Math	22	2009-07-29 18:59