Cyclotomic polynomials: $\Phi_n(p)$ is like $p^{\phi(n)}$ for big enough $p$, right?

Question

Apologies in advance if this turns out to be simple. So far I haven't found a proof or a reference.

Although I like $p$ to be a prime, I can ask the following for positive integers $n$ and $p$, using what should be clear notations for the $n$th cyclotomic polynomial and Euler's totient function: Given $p \gt 1$, is

$$ \mid \Phi_n(p)/p^{\phi(n)} \mid \lt p/(p-1)$$ for every $n$?

Indeed, if $n$ is a power of a prime $q$, we have the left hand quantity bounded by $p^{n/q}/(p^{n/q} -1)$, and the lim sup over all primes $n$ achieves $p/(p-1)$. The case for composite $n$ is not clear to me, thus the question, but I would hope for a tighter bound (perhaps involving the smallest prime power factor of $n$) than $p/(p-1)$.

An equivalent question asks to verify the bound on $\Phi_n(1/p)$. Of course the product of such quantities (to an appropriate power as $n$ runs over divisors of some $m$) will satisfy the bound, but this does not seem to help. If there is a reference offered that says (something like) the coefficients of cyclotomic polynomials grow slowly enough to exhibit the bound, I will read that. I am hoping for a simpler proof than that.

I am looking at (the moral equivalent of) prime factors of $\Phi_n(p)$ and wanted to make sure these values aren't much bigger than I think they are. I would be satisfied with a coarse bound (replace $p/(p-1)$ by $2$, say), but I think much more can be said.

UPDATE 2015.10.23 More now has been said, with my revised take on Jameson's presentation posted as a separate answer. For me, the key parts will be that $p \geq 2 $ prime and $p/(p-1)$ can be replaced by real $x \gt (2 - \epsilon)^{r/n}$ and $x^{n/r}/(x^{n/r} - 1)$, where $r=$rad$(n)$. Thanks again all, and special thanks to Peter Mueller. END UPDATE 2015.10.23

UPDATE 2015.10.21: Thanks to Peter Mueller, I read from notes of G.J.O. Jameson at http://www.maths.lancs.ac.uk/~jameson/cyp.pdf on cyclotomic polynomials of a sharper result, which indeed is simpler but also more challenging. I remove some of the challenge by interpreting some highlights here (hopefully without errors), but I recommend following the development of the notes as it proceeds in small but useful steps, with a certain degree of economy that takes ones breath away.

First, Jameson notes in 1.3 an inversion relation involving $\Phi_n(1/x)$ and real,nonzero $x$ that appears below. Jameson also prepares in 1.12 to work with squarefree indices through using $n_0=$rad$(n)$ and the identity $\Phi_n(x) = \Phi_{n_0}(x^{n/n_0})$. I modify and sketch a strict inequality (Lemma 1.19) which is used: For $0 \lt x \lt 1, m, a,\ldots,b$ positive integers (so also $0 \lt x^{powers} \leq x$),

\begin{eqnarray*} (1 -x^m)(1-x^{m+a})\ldots(1-x^{m+b}) & \geq & (1 - x^m - x^{m+a} - \ldots - x^{m+b}) \\ & \gt & 1 - ( x^m + x^{m+1} + \ldots ) = 1 - x^m/(1-x) \\ \end{eqnarray*}

Then Jameson has 1.20, which I rewrite and restrict to squarefree integers $n$, as one actually gets better bounds/ranges for when $n$ is not squarefree.

1.20 (rewritten) Let $n>1$ be squarefree with $j=1$ if the number $k$ of distinct prime factors of $n$ is an even number, and $j=-1$ if $k$ is odd. Let $0 \lt x \leq 1/2$. Then

$$1-x \lt \Phi_n(x)^j \lt 1.$$

Note when $n$ is 1, one has $\Phi_1(x)= x-1$ which is negative on the domain considered.

Using the inversion $\Phi_n(x)/x^{\phi(n)} = \Phi_n(1/x)$ when $n \gt 1$, this gives for $2 \leq x$ \begin{eqnarray*} (x-1)/x && \lt \Phi_n(x)/x^{\phi(n)} \lt 1, && k=2m \\ 1 && \lt \Phi_n(x)/x^{\phi(n)} \lt x/(x-1), && k=2m+1 . \\ \end{eqnarray*}

Using the relation for general non-squarefree indices, one can improve the $x$ in $1-x$ to $x$ to a fractional power, as well as extend the range a little. I am still working this part out. Even working out the statement using the inversion requires care. I think the results are both simple and challenging, and I am glad to share this on MathOverflow.

Jameson uses the tools carefully, working out the squarefree case in about half a page of elementary reasoning which I am still perusing. I am joyed. I'm also willing to buy Jameson two hot beverages. Peter Mueller can drop by and ask me for a toasted bagel. END UPDATE 2015.10.21

Gerhard "Wants To Stop Spinning Head" Paseman, 2015.10.19

Answer 1

Using the Mobius inversion formula, one may write

$$\Phi _n(X)= \prod _{d\mid n} (X^d-1)^{\mu (n/d)}.$$ We then get $$\frac{\Phi _n(p)}{p^{\phi (n)}}=\prod _{d \mid n} (1-\frac{1}{p^d})^{\mu (n/d)} . $$

[Edit] I did not think this would give a complete proof, but Fedja's comments below give the estimate in all cases. I give his proof: taking logs on both sides of the last equation we get $$\log \big (\frac{\Phi _n(p)}{p^{\phi (n)}}\big )= \sum _{d\mid n} \mu (\frac{n}{d})\log (1-\frac{1}{p^d})=- \sum _{d\mid n} \mu (\frac{n}{d}) \sum _{k\geq 1} \frac{1}{kp^{kd}}.$$ Now, for $0\leq x\leq 1/2$, it is proved in Fedja's comment below that the estimate $$0\leq \mid \sum _{d\mid n}\mu (\frac{n}{d})x^d \mid \leq x$$ holds. Taking $x=\frac{1}{p^k}$ and using this estimate in the above equality, we get the estimate
$$\mid \log \big( \frac{\Phi _n(p)}{p^{\phi (n)}}) \mid \leq \sum _{k\geq 1} \frac{1}{kp^k}=\log \big ( \frac{1}{1-\frac{1}{p} }\big ). $$ (We may assume that $\Phi _n(p)/p^{\phi (n)}\geq 1$; otherwise, the desired estimate is trivially true). Then the last inequality immediately implies $$\frac{\Phi _n(p)}{p^{\phi (n)}}\leq \frac{p}{p-1},$$ which is what was needed.

Answer 2

Let $d = \phi(n)$ and assume $n>2$.Then the primitive $n$-th roots of unity occur in $d/2$ complex conjugate pairs, and the GM-AM inequality applied to the (positive) contributions from each pair gives $\Phi_n(p)/p^d \leq (1 + \frac{1}{p^2}+ \frac{2}{dp})^{d/2}$, since the sum of the primitive $n$-th roots of unity has absolute value at most $1$. This is less than $e^{1/p}(1+ \frac{1}{p^{2}})^{d/2}$.Second term in product is at most $ e^{d/2p^{2}}$,so the quotient you are interested in is at most $e^{1/p + d/2p^{2}}$, as compared with $\sum_{j=0}^{\infty} 1/p^{j}$. This only helps when $p$ is fairly large compared to $n$ though.

Answer 3

I've decided to simplify the argument found in notes of Jameson, and at the same time improve the bounds and ranges of applicability. I'm rewriting for the purpose of understanding and the specific goal of improving the answer; for other applications I still recommend the notes.

For $n=1$, and $x$ a positive real, we have the desired quantity $\Phi_n(x)/x^{\phi(n)} = (x-1)/x$ which we take as understood, and will focus on $n \gt 1$. By inclusion-exclusion or some other means of summing over positive divisors of $n$, we have $\phi(n) = \sum_{d \mid n} d\mu(n/d)$, where I use the Moebius function $\mu(m)$, and rewrite the quantity as done in the answer of Venkataramana: $$\frac{\Phi_n(x)}{x^{\phi(n)}}= \frac{\prod_{d\mid n} (x^d -1)^{\mu(n/d)}}{\prod_{d \mid n} x^{d\mu(n/d)}}= \prod_{d \mid n}(1 - x^{-d})^{\mu(n/d)}= \left( \frac{P(x)}{Q(x)} \right)^j,$$ where I explain the last term below.

In the general case, $n$ is not always squarefree, so for some divisors $d$ of $n$ $\mu(n/d)$ is $0$ and the associated base $1 - x^{-d}$ "drops out". We collect the terms that don't drop out and arrange for the term with the largest value of $-d$ (smallest $d$) to be on the top. As a result, $j$ will be $1$ when the number of distinct prime factors of $n$ is even, and $-1$ when this number is odd. Letting $n_0=$rad$(n)$ and $n_1= n/n_0$, $P(x)$ will contain those factors of the form $(1 - x^{-an_1})$, where $a$ runs over the divisors of $n_0$ with $\mu(a)=1$ (so $1-x^{-n_1}$ is a factor of $P(x)$), and $Q(x)$ will contain the rest (factors $1 - x^{-an_1}$ where $a\mid n_0$ and $\mu(a)=-1$). However, even when $n$ is squarefree, $n_1$ will be $1$ and the argument will apply in this case also. By using $-n_1$, I avoid at some notational cost the inversion and squarefree reductions used in the argument of Jameson.

As a quick check, let us take $n= q^k$, a prime power with $k \geq 1$. Then $j=-1, n_1=n/q,$ $P(x)=(1-x^{-n_1}),$ and $Q(x)=(1-x^{-n})$, and
$$1 < \frac{\Phi_n(x)}{x^{\phi(n)}} = \frac{x^n - 1}{x^n - x^{n-n_1}} \lt \frac{x^{n_1}}{x^{n_1} - 1}= \frac{x^{n/q}}{x^{n/q} - 1},$$ and this last is bounded by $x/(x-1)$, and gets better when $k$ gets larger. Note however for $k=1$ that as $n$ runs through larger primes, $\Phi_n(x)/x^{\phi(n)}$ approaches $x/(x-1)$: we can't expect significant improvement for those $n$.

We continue now assuming $n$ is not a prime power. I use a simple estimate to bound both $P(x)$ and $Q(x)$. Actually, a key feature of Jameson's argument which I emphasize here is that we bound $P(x)/(1-x^{-n_1}) = (1- x^{-pqn_1})R(x)$ where $R(x)$ is the rest of the product (and could be 1), which is needed for the inequality in my question. $p$ and $q$ are the smallest and second smallest prime factors of $n$.

I introduce a familiar-looking inequality which I dub Lemma 91.1. For $1 \lt x$ a real, $m \lt 0$ an integer, and integers $0 \lt a \lt b$ and perhaps other distinct integer exponents coming from $[a,b]$ \begin{eqnarray*} (1-x^{am}) & \gt & (1- x^{am})\ldots(1-x^{bm}) \gt 1 - x^{am} - \ldots - x^{bm} \\ & \geq & 1 - x^{am} - x^{(a+1)m} - \ldots - x^{bm} = 1 - \frac{x^{am} (1- x^{m(1+b-a)})}{1- x^m} \\ \end{eqnarray*} Note that if $a=b$ in the above, then we have just $(1- x^{am})$ to bound, and we get equalities in this case.

This Lemma is the algebraic replacement of fedja's idea which is the heart of the accepted answer. It gives $1- x^{-n_1} \gt P(x) \geq (1 - x^{-n_1})(1 - x^{-pqn_1}(1- x^{-{\beta}n_1})/(1 - x^{-n_1}))$, for some integer $1 \leq \beta \leq n_0 - pq$ sufficiently large, and picking $\gamma \leq n_0 - p$ similarly to $\beta$ $1 - x^{-pn_1} \gt Q(x) \gt 1 - x^{-pn_1}(1-x^{-{\gamma}n_1})/(1-x^{-n_1})$. (If $1 \gt n_0 - pq$, pick $\beta=1$ anyway. One can always choose larger $\beta$ and $\gamma$ to weaken the inequality.)

To get $P(x) \lt Q(x)$, we look at when $1-Q(x) \lt 1 -P(x)$, or the sufficient condition $1- Q(x) \lt x^{-pn_1}(1-x^{-{\gamma}n_1})/(1-x^{-n_1}) \leq x^{-n_1} \lt 1 -P(x)$. For readability we substitute $y=x^{-n_1}$ and ask for this $y$ to satisfy $y^p(1 - y^{\gamma}) \leq y- y^2$, or $ y + y^{p-1}(1- y^{\gamma}) \leq 1$. $p$ is at least $2$, so this holds when $x^{-n_1} = y \leq 1/2$, however it can hold for slightly larger $y$. So for $x^{-n_1} \leq 1/2 + \epsilon(p,\gamma)$, we have $P(x) \lt Q(x)$. We can't expect a large $\epsilon(2,\gamma)$ (for we need $y \lt (2 - y^{\gamma})^{-1}$), but already $0.1 \lt \epsilon(p, \gamma)$ for primes $p \gt 2$.

We use the other inequalities to get immediately

$$\frac{P(x)}{Q(x)} \gt \frac{(1 - x^{-n_1})(1 - x^{-pqn_1}(1- x^{-{\beta}n_1})/(1 - x^{-n_1}))}{1 - x^{-pn_1}},$$ and we reuse $y$ to write this last as $$(1-y)\frac{1 - y^{pq}(1 - y^{\beta})/(1-y)}{1-y^p}= (1-y)\frac{1- y - y^{pq}(1-y^{\beta})}{1 - y - y^p + y^{p+1}}.$$

As $q\geq 3$, $y^{p(q-1)} ( 1- y^{\beta}) \lt 1 - y$ whenever $y^4 + y \lt 1$, and one can use $\beta$ to tweak the range further, so for such $y$ we have $-y^{pq}(1- y^{\beta}) \gt - y^p(1-y)$ so the last displayed term is $(1-y)$ times something larger than $1$. Thus $P(x)/Q(x) \gt 1-y = 1- x^{-n_1}$ for these $x$, which include $x^{n_1} \geq 2$.

Thus we have $\Phi_n(x)/x^{\phi(n)}$ sandwiched between $1 - x^{-n/\textrm{rad}(n)}$ and $1$, or between $1$ and $(1 - x^{-n/\textrm{rad}(n)})^{-1}$ for $x^{n_1} \gt 2 - \epsilon$, where we can tune epsilon based on $n$.

Gerhard "Apologies For The Simple Parts" Paseman, 2015.10.23