valuation(2, prime(n)-1)

[Pieter Moree]

Dear Benoit,

>
> Many thanks for this instructive answer and providing references.
>
>>> Letting S(n)=sum(i=2, n, valuation(2, prime(i)-1) )
>>>
>>> I suppose limit n-->infty S(n)/n = 2
>> This is true and is not too difficult to prove:
>>
>> The primes (*) p=1(mod 2^m) that are not =1(mod 2^{m+1})
>>
>> have
>> density 2^{-m} and contribute m/2^m to the density.
>> Summing this for m is 1 to infty then yields the result.
>> (This is the idea, in the proof one ought be a bit more careful.)
>
>
> More genrally, letting S(n,p)= sum(i=2, n, valuation(p, prime(i)-1) )
>
> If I'm not totally wrong, similar arguments should give :
>
> limit S(n,p)/n = sum(m>=1,m/p^m)=p/(p-1)^2
>
> limit S(n,2)/n=2
> limit S(n,3)/n=3/4
> limit S(n,5)/n=5/16
> limit S(n,7)/n=7/36

You are absolutely right. The density of primes q satisfying
valuation(p, prime(i)-1)=m equals m/q^m.
Summing this over m entails substituting x=1/q in x/(1-x)^2.
Et voila....


>>> I asked myself if (2n-S(n))/sqrt(n) is bounded with S(n)<2n
>> In my opinion this is rather too optimistic. If one assumes
>> the Generalized Riemann Hypothesis then one can show there
>> is a constant c such that if one replaces aqrt(n) by
>> sqrt(n)(log n)^c, then the quotient is bounded.
>>> and if limit n-->infty (2n-S(n))/sqrt(n) exist ?
>> I am convinced the answer is: NO. S(n) is quite irregular.
>> The analog to think of is: (pi(x)-Li(x))/sqrt{x}.
>> It can be proved that this does not have a limit.
>
> It's clear from Littlewood.
Indeed.

>I wonder what is the first n for which
> S(n)>2n ?

S(n)>2n ought to be a rare phenomenon. This is a consequence
of Chebyshev's bias. Chebyshev's bias entails that mod small moduli
there is a preference for a prime to have remainder a non-square
mod d over a square mod d. As d increases, this effect washes out.
Asymptotically there is equidistribution, though.

In our situation (going back to your original S(n)), there is a preference
for primes p to be 3(mod 4) over 1(mod 4). This means S(n) is going
to be lower than 2n (we are scoring too many 1's for the valuations...).
Since there is a preference over 5(mod 8) over 1(mod 8) again the
C bias is favoring the lower valuation, etc..
Again I expect that the techniques used to study Chebyshev's bias
can be used to prove something here.

The heuristics for divisors of a^k+b^k I propose, although asymptotically
exact also suffer (for small a and b) from Chebyshev bias effects.
This was observed by some second year students who numerically checked
my heuristics. This means that instead of fluctuations around the
mean one sees that there is a one-sided convergence to the mean.

> Following your analogy : why not conjecture c=1 and :
>
> S(n)=2n+O(n^(1/2)*log(x))

Could be true, but not something I doubt you can prove on GRH.
Remember, you get contributions here from error terms of lot of
zeta functions (I cannot rule out there is a lot of cancellation of course)
You get something like O(\sum_{2^m\le x}m sqrt{x}log x),
where I sum over the primes <=x. In your notation set x=n * log n.
i.e. O(n^{1/2}\log^{7/2}n)

(If you press me for a c, here it is c=7/2... ;-) ).

> making the full parallel with :
>
> pi(n)=Li(n)+O(n^(1/2)*log(n)) if RH is true.
>
> Or for any p :
>
> S(n,p)=p/(p-1)^2*n+O(n^(1/2)*log(x))
>
>

Bests,
Pieter