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}\frac{1}{p}).$$ 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 ?


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$.

  • $\begingroup$ Is it then possible that, letting $$\omega_0(n):=\sum_{p|n,p\leq \log n}1,$$ then $$\lim_{\omega_0(n)\to+\infty}s(n)=+\infty ?$$ $\endgroup$ – Captain Darling May 7 '17 at 14:12

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.

  • $\begingroup$ (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))$ ? $\endgroup$ – 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(\operatorname{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 \equiv 1(\operatorname{mod} d)}\frac{1}{p^2}.$$ That seems to suggest that if $n$ is such that $s(n)$ is large, then for many divisors $d|n$ there might be many primes $p \equiv 1 (\operatorname{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 remind you of anything I could look up?


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.