You are currently browsing the monthly archive for août 2015.

When one considers the sequence of values $f(n)$ of some reasonable arithmetic function, like the divisor function $\tau$, or the function $\omega(n)$ the number of prime factors of $n$, one may notice that excluding a few abnormal values, the sequence looks very much like a neat, recognizable sequence. Or at least, smoothing the sequence by averaging it produces a sequence which looks neat.

Thus $\omega(n)$ has normal order $\log\log n$: almost all numbers $n$ have about $\log\log n$ ; this is the theorem of Hardy-Ramanujan. It’s even better than this : for almost all numbers, $\omega(n)$ is within $(\log\log n)^{1/2+\epsilon}$ of its model $\log\log n$. In fact the values of $\frac{\omega(n)-\log\log n}{\sqrt{\log\log n}}$ follow a Gaussian distribution, as the Erdös-Kac theorem reveals.

In contrary the divisor function $\tau$ doesn’t have any normal order, but it does have an average order which is quite good-looking, namely $\log n$ (while $\log\tau$ has a normal order which, surprisingly isn’t $\log\log n$ but a bit a less, namely $\log 2\log\log n$, showing that a few exceptionally highly divisble numbers are able to make the average deviate substantially).

Now of course on the primes $\tau$ and $\omega$ collapse violently, being stuck at respectively 2 and 1. The question is whether just after such a shocking value, at $n=p+1$, one recovers more normal arithmetic indices, whether there are traces of the past catastrophe (or signs of the coming castrophe just before it).

Of course $p+1$ isn’t absolutely any number, for instance it’s surely even; but then is $(p+1)/2$ just any number? It must also be said that it has higher chances to be mutiple of 3 than a generic number, in fact one in two chance instead of one in three, because $p+1\equiv 1\text{ or } 0\text{ mod }3$ whith equal probability.

From the point of view of $\omega$

There the answer is: yes, perfectly. Indeed, Heini Halberstam established that the Erdös-Kac theorem holds when $n$ is constrained to range in the shifted primes $p+1$. That is, $\omega(p+1)$ lies within $M\sqrt{\log\log p}$ of $\log\log p$ for a positive proportion $p(M)$ of primes, the density being again gaussian.

From the point of view of $\tau$

Not quite. For this consider the Titchmarsh divisor problem, consisting in estimating $\sum_{p\leq x} \tau(p+1)$. If $\tau(p+1)$ was replaceable by $\log(p+1)$ as we suppose, then this sum would be asymptotic to $\sum_{p\leq x}\log p\sim x$ by Mertens formula. It turns out that it is in fact asymptotic to $\frac{\zeta(2)\zeta(3)}{\zeta(6)}x$, the constant prefactor being well over 1,9, so that it can be said that $p+1$ has almost twice as many divisors as banal numbers of his size. Now remember it’s always even; now there are good heuristic reasons to believe that $\sum_{n\leq x,n\equiv [0] 2}\tau(n)\equiv 2/3x\log x$, so that in average $\tau(2n)$ is close to $4/3\log n$, but 1,9 is still much larger sensibly larger than 4/3. Here the higher chances of $p+1$ to be divisible by 3, 5 etc. in comparison to a banal number weigh enough to make the average deviate.

It would be interesting to determine whether $\log \tau(p+1)$ has a normal order, in the same vein as Halberstam’s result.

Another criterion of banality: the probability of being squarefree

As we know, the density of squarefree numbers is $1/\zeta(2)=\prod_{q \text{ prime}}(1-q^{-2})$. It is then reasonable to wonder if among numbers of the forme $n=p+1$, the proportion of square free is the same. It’s clear to see that it can’t quite be so: indeed, $p+1$ has one on two chance of being divisible by the square 4 (while a generic number has of course one on four chance), one on six chances of being divisible by 9, one on $q(q-1)$ chance of being divisibly by the prime $q$. So one guesses that $p+1$ is a little less likely to be squarefree than any number; indeed, it’s been proven by Mirsky that the proportion of squarefree numbers among numbers of the form $p+1$ is $\prod_q (1-1/(q(q-1))$, to compare with $\prod_{q \text{ prime}}(1-q^{-2})$.

The property of being squarefree can be replaced by the property of being $k$-free for instance, the density among shifted primes being then $\prod_q (1-1/(q^{k-1}(q-1))$, to compare with $\prod_{q \text{ prime}}(1-q^{-k})$.

Appendix: average of the divisor function on odd and even numbers

We know that

$\displaystyle{x\log x\sim\sum_{n\leq x}\tau(n)=\sum_{\substack{n\equiv 0\mod [2]\\n\leq x}}\tau(n)+\sum_{\substack{n\equiv 0\mod [2]\\n\leq x}}\tau(n)=S_0(x)+S_1(x)}$

And let us suppose that $\sum_{n\equiv 0\mod [2],n\leq x}\tau(n)\sim Ax\log x$ and $\sum_{n\equiv 1\mod [2],n\leq x}\tau(n)\sim Bx\log x$.

Now the sum on even numbers can be decomposed into a sum on numbers of 2-adic valuation 1,2,3… But numbers of 2-adic valuation k are numbers which are of the form 2^km with $m$ odd, so

$\displaystyle{\sum_{v_2(n)=k,n\leq x}\tau(n)=(k+1)\sum_{n\leq x/2^k,n\equiv 1[2]}\tau(n)\sim(k+1)Bx/2^k\log x}$ for fixed $k$. Pretending this asymptotic also holds when $k$ is allowed to grow with $x$, we infer from $S_0(x)=2S_1(x/2)+(3-2)S_1(x/4)+(4-3)S_1(x/8)\cdots$ that $C=D+D/2+D/4\cdots=2D$. Hence $S_0(x)\sim 2x/3\log x$ and $S_1(x)\sim x/3\log x$.

It might be that this intuition has been proven more rigorously, I’d like to see where!