19
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I think we need a "cyclotomic-polynomials" tag. Gerhard "Second Question On This Account" Paseman, 2015.10.19 $\endgroup$ – Gerhard Paseman Oct 20 '15 at 3:17
  • $\begingroup$ A search using the key word "cyclotomic" turns up three tags "cyclotomic-integers", "cyclotomic-fields" and "cyclotomic-integer". I'm suggesting a merger to something like "cyclotomy". Fan "Better Tags" Zheng $\endgroup$ – Fan Zheng Oct 20 '15 at 3:25
  • $\begingroup$ Indeed. Perhaps this has been discussed in meta already. Although I can see tag-fracturing as a danger, I can also see the use of wildcard searches for tag values. Gerhard "We Can Work Around This" Paseman, 2015.10.19 $\endgroup$ – Gerhard Paseman Oct 20 '15 at 3:28
  • 2
    $\begingroup$ Shouldn't this work for real p large enough? $\endgroup$ – joro Oct 20 '15 at 7:27
  • 1
    $\begingroup$ The set $\{\,\phi_n(2)/2^{\phi(n)}:n=1,2,\dots\,\}$ has some interesting structure. I almost wrote a paper about it once. $\endgroup$ – Gerry Myerson Oct 20 '15 at 12:14
17
$\begingroup$

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.

$\endgroup$
  • 15
    $\begingroup$ Actually it does give the desired bound if one notices that for $0<x\le \frac12$, we have $0\le \sum_{d|n} \mu(d)x^d\le x$. Indeed, the left inequality is obvious even if we subtract everything from $\mu(1)x^1=x$ and the right inequality follows from the fact that once $x^q$ is subtracted for some prime factor $q|n$, all divisors divisible by $q$ cannot bring us back even if taken with the plus sign. Now, to switch from the sums to the products, just take $\log$, decompose it into the Taylor series, and apply this observation to $x=\frac 1{p^k}$ for $k=1,2,\dots$. $\endgroup$ – fedja Oct 20 '15 at 11:12
  • $\begingroup$ @fedja: you seem to be right. That gives a clean proof. $\endgroup$ – Venkataramana Oct 20 '15 at 13:40
  • $\begingroup$ This is looking good: I will accept it after I finish scrutinizing it. If you are able to manage an argument of even more algebraic flavor, I would be joyed. In any case, thank you: the efforts are worth at least a moderately priced hot beverage to you (fedja as well as Venkataramana). Come by the S.F. Bay Area to claim your prizes and (optional) face-to-face. Gerhard "Sorry, Gift Cards Not Awarded" Paseman, 2015.10.20 $\endgroup$ – Gerhard Paseman Oct 20 '15 at 18:23
  • $\begingroup$ For $n \gt 1$ and positive real $x$, the inequalities obtained starting with the displayed estimate of fedja are strict (check me on this, especialy if you replace $k \geq 1$ by $k \gt 0$). I don't need the strict version, but I did ask for it. If you email me, maybe we can get this cold beverage thing worked out. Gerhard "Giving This My Seventh Upvote" Paseman, 2015.10.20 $\endgroup$ – Gerhard Paseman Oct 20 '15 at 18:40
  • 7
    $\begingroup$ A different (somewhat simpler) proof of the inequality is given in maths.lancs.ac.uk/~jameson/cyp.pdf (Prop. 1.20). $\endgroup$ – Peter Mueller Oct 20 '15 at 21:17
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ To my surprise, Jameson actually starts the notes using complex conjugate pairs. You might enjoy following the development for the first few pages. Gerhard "Maybe Complex Can Be Simpler" Paseman, 2015.10.21 $\endgroup$ – Gerhard Paseman Oct 21 '15 at 19:55
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I did, and it got reverted to Jamseon Thanks for the catch. Gerhard "Still Have Seoul Inside Me" Paseman, 2015.10.23 $\endgroup$ – Gerhard Paseman Oct 23 '15 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.