MathOverflow is a question and answer site for professional mathematicians. 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

For each positive integer n we may define the convergent sum $$ s(n)=\sum_{p}\frac{(n,p-1)}{p^2} $$ where the summation is over primes p and $(a,b)$ denotes the greatest common divisor of a,b.

It is immediate to deduce that s(n) is bounded on average:

Using $\sum \limits_{d|a, d|b}\phi(d)=(a,b)$ and inverting the order of summation we get

$s(n)=\sum_{d|n}\phi(d) a_d$ where $a_d=\sum_{p \equiv 1 (mod \ d)}p^{-2} $

Ignoring the fact that we sum over primes we get the bound $a_d \ll \frac{1}{d^2}$ which leads to $$\sum_{n \leq x}s(n) \ll x \sum_{d \geq 1}\frac{\phi(d)a_d}{d}=O(x) $$ and $$s(n) \ll \exp(\sum_{p|n}1)$$ The last inequality means that $s(n)$ stays bounded if $\omega(n)$ is bounded. Towards the other direction, it seems fair to expect that $s(n)$ grows to infinity if $\omega(n)$ is large in some quantitative sense, say $\omega(n) \geq (1+\epsilon) \log \log n$. Taking into account that the contribution to the sum $s(n)$ of the primes $p$ that satisfy $(p-1,n) \leq \frac{p}{\log p}$ is bounded, since $\sum_{p}\frac{1}{p \log p}$ converges, we see that $ s(n)=s'(n)+O(1)$ where $s'(n)=\sum_{ (p-1,n)>\frac{p}{\log p}} \frac{(n,p-1)}{p^2}$ We are therefore led to the question as to whether a condition of the form $\frac{\omega(n)}{\log \log n}-1 \gg 1$ can guarantee that $s'(n) \to +\infty$ Are there any non-trivial techniques that can be used to answer this question ?

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

Your guess that $s(n)$ gets large if $\omega(n)$ is large is not correct.
It is possible for $n$ to have many primes, and for $s(n)$ still to be small.

This can be seen from some of the work in your question. As you note $s(n) =\sum_{d|n} \phi(d) a_d$ where $a_d =\sum_{p\equiv 1\pmod d} p^{-2} \ll 1/d^2$. Therefore $$ s(n) \ll \sum_{d|n} \frac{1}{d} \le \prod_{p|n} \Big(1-\frac 1p\Big)^{-1}. $$ If now every prime factor of $n$ exceeds $\log n$, then (since $\omega(n) \le \log n$ trivially) we have $$ s(n) \ll \Big(1-\frac{1}{\log n} \Big)^{-\log n} \ll 1. $$

Thus $n$ can have about $\log n/\log \log n$ prime factors, all larger than $\log n$ and still $s(n)$ would be $\ll 1$.

share|cite|improve this answer

Are you just trying to show $s(n)$ is unbounded? and do you insist on a non-trivial technique? Let $n=m!$; then $s(n)>\sum_{p\lt m}{p-1\over p^2}=\sum_{p\lt m}{1\over p}+O(1)$ and of course the sum diverges.

share|cite|improve this answer
(corrected the typo log log n, thanx !) your choice of n shows that $s(n) \gg \log \log \log n$ infinitely often. Choosing $n=\prod_{p \leq m}(p-1)$ we deduce that $s(n) \gg \log \log n$ infinitely often. But my question was of another nature : Is it true that $s(n) \to \infty$ for each sequence of integers n that have a large number of prime divisors (not for just a particular sequence of the form $m!$ or $\prod_{p \leq y}(p-1))$ ? – Captain Darling Sep 15 '10 at 12:13

A few more ideas: using the chebyshev upper bound, by partial summation we have $\sum_{p>y}p^{-2}=O(\frac{1}{y \log y})$ and therefore we see that $s(n)=\sum_{p \leq \frac{n}{\log n}}\frac{(p-1,n)}{p^2}+O(1).$ Furthermore by the equality $\sum_{p \leq x}p^{-1}=\log \log x +A +(\frac{1}{\log x})$ we get $$s(n)=\sum_{p \leq n^{1/3}}\frac{(p-1,n)}{p^2}+O(1)$$ and one can make this more accurate. There is something in the expression $s(n)=\sum_{d|n}\phi(d)a_d$ that is linked to Linnik's constant(or the Elliot-Halberstam Conjecture). In particular, using $a_d=\sum_{p=1(mod d), p>y} p^{-2} \leq d^{-2}\sum_{m>y/d}m^{-2}$ one can deduce that $$s(n)=\sum_{d|n}\phi(d) a'(d)+O(1)$$ where $$a'(d)=\sum_{p \leq d \log d {\log \log d}^2, p=1(mod d)}\frac{1}{p^2}$$ That seems to suggest that for each n for which $s(n)$ is quite large then for many divisors $d|n$ there might be many primes $p=1 (mod d)$ in the interval $[d,d \log d {\log \log d}^{2}]$ and conversely, but I haven't been able to establish a clear connection between these two facts. To this end we may compute the mean values $\sum_{n \leq x} s^{2k}(n), k \geq 0$ which is quite straightforward. Does all this set-up reminds you anything I could look up?

share|cite|improve this answer

Your Answer


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

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