Skip to main content
1 of 3
Gerhard Paseman
  • 3.2k
  • 1
  • 18
  • 29

I've decided to simplify the argument found in notes of Jamseon, 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 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

Gerhard Paseman
  • 3.2k
  • 1
  • 18
  • 29