Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am interested in bounds for

$$S_m = \frac{1}{m-1} \sum_{t | m-1} t \varphi(t)$$

as $m$ gets large.

share|cite|improve this question
up vote 2 down vote accepted

If you let $n = m-1$, and $f(n) = S_{m} / n$, then $f(n)$ is a multiplicative function, with Euler product $$\frac1{n^2}\prod_{p^r \mathop{\mid\mid}n} \sum_{k=0}^r p^k\phi(p^k) = \prod_{p^r \mathop{\mid\mid}n} p^{-2r}\left(1+p(p-1)+p^3(p-1)+\cdots+p^{2r-1}(p-1)\right).$$

This simplifies down to $$f(n) = \prod_{p^r \mathop{\mid\mid}n} \left(\frac{p+p^{-2r}}{p+1}\right) \le \prod_{p \mid n} \left(\frac{p+1/4}{p+1}\right).$$

Since $\sum_p 1/p$ diverges, this product can be made arbitrarily close to $0$ by choosing $n$ to be divisible by many many small primes. So no, $S_m$ cannot be bounded below by a linear function of $m$.

On the other hand, since $f(n) \ge n/\sigma(n)$ (where $\sigma$ is the sum of divisors function), it is possible to bound $S_m$ from below by $m / (2\log \log m)$ for large enough $m$. The slow growth of $\log \log m$ explains your empirical observations.

share|cite|improve this answer
@felipa No, it's a good question. Dirichlet's theorem shows that for any $k$ we can find a prime of the form $m = k!q + 1$. Thus we can choose $m-1$ to have all the factors we wish, even when restricting $m$ to be prime. – Erick Wong Feb 6 '13 at 17:12
@felipa It's an old theorem of Grönwall (wikipedia) that $\sigma(n) \le (e^{\gamma} + o(1)) n \log \log n$, although our bound can be deduced directly from Mertens' theorems without reference to $\sigma(n)$. The factor of $2$ just comes from rounding $e^{\gamma}$ up to the next integer. – Erick Wong Feb 8 '13 at 20:25

Proceeding as in the answer above let $T(n) = S(n+1)$ and we'll examine $T(n)$ in more detail. Write it as follows: $$ T(n) = \frac{1}{n} \sum_{t|n} t \varphi(t) = \sum_{t|n} \varphi(t) \left( \frac{n}{t} \right)^{-1}.$$ It now follows from basic properties of the Euler totient that $$ L(s) = \sum_{n\ge 1} \frac{T(n)}{n^s} = \frac{\zeta(s-1)}{\zeta(s)}\zeta(s+1).$$ For certain Dirichlet series of which this is an instance, we have for $c$ chosen correctly that $$ T(n) = \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} L(s) n^{s-1} ds.$$ Now taking the residues at $s=2$ and $s=0$, we obtain $$ T(n) \sim 1/6\,{n}^{-1}+6\,{\frac {\zeta \left( 3 \right) n}{{\pi }^{2}}} $$ which confirms your hypothesis that on average $n$, $T(n)$ is linear. This expansion could be continued and that is where the necessary fluctuation will appear.

We can also apply the Wiener-Ikehara theorem to study the average order of the sum of $T(n)$, which is much more smooth. We have $$\frac{1}{n} \sum_{k=1}^n T(n) = \frac{1}{2n} T(n)+ \frac{1}{n}\frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} L(s) n^s/s ds,$$ which gives $$\frac{1}{n} \sum_{k=1}^n T(n) \sim \frac{1}{2n} T(n)+\frac{1}{n} \left( 1/6\,\ln \left( n \right) +1/6\,\gamma-2\,\zeta \left( 1,-1 \right) -1/6\,\ln \left( 2\,\pi \right) +3\,{\frac {\zeta \left( 3 \right) {n}^{2}}{{\pi }^{2}}}\right).$$ This last approximation is of truly stunning accuracy, which is why I include it here even if doesn't directly answer the OP's question.

share|cite|improve this answer

We can certainly bound it from above since $$\frac{1}{m-1}\sum_{t|m-1}t\varphi(t) \leq \frac{m-1}{m-1}\sum_{t|m-1}\varphi(t) = m-1$$

share|cite|improve this answer
@felipa yes, a lower bound is definitely more tricky, as can be seen from how much more complicated Erick's answer is. – Tobias Kildetoft Feb 6 '13 at 17:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.