This is a postscript to the previous blog post which was concerned with obtaining heuristic asymptotic predictions for the correlation
for the divisor function , in particular recovering the calculation of Ingham that obtained the asymptotic
when was fixed and non-zero and
went to infinity. It is natural to consider the more general correlations
for fixed and non-zero
, where
is the order divisor function. The sum (1) then corresponds to the case
. For
,
, and a routine application of the Dirichlet hyperbola method (or Perron’s formula) gives the asymptotic
or more accurately
where is a certain explicit polynomial of degree
with leading coefficient
; see e.g. Exercise 31 of this previous post for a discussion of the
case (which is already typical). Similarly if
. For more general
, there is a conjecture of Conrey and Gonek which predicts that
for some polynomial of degree
which is explicit but whose form is rather complicated (one has to compute residues of a various complicated products of zeta functions and local factors). This conjecture has been verified when
or
, by the work of Linnik, Motohashi, Fouvry-Tenenbaum, and others, but all the remaining cases when
are currently open.
In principle, the calculations of the previous post should recover the predictions of Conrey and Gonek. In this post I would like to record this for the top order term:
Conjecture 1 If
and
are fixed, then
as
, where the product is over all primes
, and the local factors
are given by the formula
where
is the degree
polynomial
where
and one adopts the conventions that
and
for
.
For instance, if then
and hence
and the above conjecture recovers the Ingham formula (2). For , we have
and so we predict
where
Similarly, if we have
and so we predict
where
and so forth.
As in the previous blog, the idea is to factorise
where the local factors are given by
(where means that
divides
precisely
times), or in terms of the valuation
of
at
,
We then have the following exact local asymptotics:
Proposition 2 (Local correlations) Let
be a profinite integer chosen uniformly at random, let
be a profinite integer, and let
. Then
(For profinite integers it is possible that and hence
are infinite, but this is a probability zero event and so can be ignored.)
Conjecture 1 can then be heuristically justified from the local calculations (2) by various pseudorandomness heuristics, as discussed in the previous post.
I’ll give a short proof of the above proposition below, basically using the recursive methods of the previous post. This short proof actually took be quite a while to find; I spent several hours and a fair bit of scratch paper working out the cases laboriously by hand (with some assistance and cross-checking from Maple). Here is an unorganised sample of some of this scratch, just to show how the sausage is actually made:
It was only after expending all this effort that I realised that it would be much more efficient to compute the correlations for all values of simultaneously by using generating functions. After performing this computation, it then became apparent that there would be a direct combinatorial proof of (6) that was shorter than even the generating function proof. (I will not supply the full generating function calculations here, but will at least show them for the easier correlation (5).)
I am confident that Conjecture 1 is consistent with the explicit asymptotic in the Conrey-Gonek conjecture, but have not yet rigorously established that the leading order term in the latter is indeed identical to the expression provided above.
We now prove (5). Here we will use the generating function method. From the binomial formula we have the formal expansion
for any . By the geometric series formula, it thus suffices to show that
in the ring of formal power series in .
With probability ,
is coprime to
and thus
. In the remaining probability
event,
for some
with the same distribution as the original random variable
, and
. This leads to the identity
and the claim then follows from a brief amount of high-school algebra.
Now we prove (6). By (3), our task is to show that
The above generating function method will establish this (and, as I said above, this was how I originally discovered the formula), but we give here a combinatorial proof. We first deal with the case when is not divisible by
. In this case, at least one of
and
must equal
; we can phrase this fact algebraically as the identity
By linearity (and translation invariance) of expectation and (5) we thus have
which gives (7) in this case.
Now suppose that for some (profinite) integer
. With probability
,
is coprime to
, so that
; in particular (8) holds here. In the remaining probability
event, we can write
. From (4) and Pascal triangle identities, we have
and similarly
and hence on subtracting from both equations, multiplying, and rearranging we have a variant of (8):
Putting this together, we see that
and hence by (5) as before
The claim is now easily verified from an induction on , as well as many applications of Pascal triangle identities.
23 comments
Comments feed for this article
31 August, 2016 at 12:31 pm
sylvainjulien
In conjecture 1, I get a message ‘formula doesn’t parse’ after ‘local factors’.
[Corrected now – T.]
31 August, 2016 at 5:17 pm
Dejan Kovacevic
It’s interesting to see how the sausage is actually made ;-)
Not sure about the others, but I am not using paper at all, although there are no fully appropriate software tools on the market for what Terry showed. Maple and Mathematica are useful just for small subset for all that work (and one to follow)…Here is my ‘meatball shop’:
http://ateravis.com/owncloud/index.php/s/jG3A3WvFA7dw4RV
31 August, 2016 at 5:43 pm
Anonymous
Is it possible to get similar conjectures for
instead of (or perhaps in addition to)
?
31 August, 2016 at 6:05 pm
Terence Tao
Certainly! Actually the two types of functions are related to each other by various linear identites such as
, so it is fairly easy to pass from one to the other.
1 September, 2016 at 1:52 am
Anonymous
Since
is meromorphic on
for
, while for the more general generating function
, it was proved (see Ramanujan’s collected papers, p. 339) by Estermann (probably in his paper “On certain functions represented by Dirichlet series” Proc. London Math. Soc.(2) 27 (1928) 435-448) that for
, the function
is meromorphic in the right half plane
and, except the cases
or
, has the line
as its natural boundary!
Therefore it is not clear how such linear identities representing
for
(whose generating function has the imaginary axis as its natural boundary) as linear combinations of
(whose generating function is a polynomial in
and therefore meromorphic on
) can possibly exist?
1 September, 2016 at 7:46 am
Terence Tao
Oops, you’re right; the identities I had in mind were only true locally, for instance
. So the local factors for
correlations can be derived from those of
correlations, which can then be multiplied together to establish the global prediction. But a proof of the global correlation estimates for
do not directly imply those for
or vice versa. Nevertheless, the theory of both functions ought to be very similar. For instance
agrees with
on squarefree numbers.
1 September, 2016 at 4:56 am
Sam
I’m so happy to see your work.We’re gonna meet one day.
1 September, 2016 at 2:11 pm
Anonymous
I’d be interested in a higher res picture of the scratch paper, to get a look at the actual calculations.
2 September, 2016 at 5:55 am
arch1
Is there a j^2 missing from the 3rd term in the numerator of the expression for
?
6 September, 2016 at 10:17 pm
Heuristic computation of correlations of higher order divisor functions — What’s new – hakoblog
[…] via Heuristic computation of correlations of higher order divisor functions — What’s new […]
10 September, 2016 at 12:41 am
Dejan Kovacevic
Question: I noticed that some sheets of paper on shared image contains either special characters or, more likely, some symbolic/graphic notation. I wonder if that is something formal/established or it is a mechanism which you use to simplify analysis?
10 September, 2016 at 11:04 pm
Ken
It is already published before, isn’t? http://vixra.org/abs/1609.0030
18 September, 2016 at 9:27 am
Anon
Is there a nice form known for the ordinary generating function of $\tau_k(n)$, i.e. $\sum_{n=1}^{\infty} \tau_k(n) x^n$? Or a nice way to estimate this for a fixed value of $x$ with $|x|<1$?
This came up recently in the course of some calculations I was making, and I can only seem to find info about the Dirichlet generating function of $\tau_k(n)$.
18 September, 2016 at 9:37 am
Terence Tao
I doubt there is a closed form expression for
. One can use the geometric series formula to remove one of the summations, e.g.
, but after that there isn’t much else one can do. (The divisor functions
have multiplicative structure but not much additive structure, which is the main reason why they have a nice Dirichlet series but not such a nice generating function.)
On the other hand, one can use summation by parts to estimate an expression such as
in terms of partial sums
. Roughly speaking, for
of the form
, a sum of the form
should behave like (a smoothed version) of
, since the range
is roughly where the weight
is large.
18 September, 2016 at 9:41 am
Anon
Thank you for your prompt and helpful comment!
18 September, 2016 at 1:24 pm
Anonymous
Your example for the generating function for
is a particular Lambert series, and indeed the Wikipedia article on Lambert series gives the generating function for
(for any complex
) as a simple Lambert series.
11 October, 2016 at 10:40 pm
Anonymous
Very enlightening!
11 October, 2016 at 10:42 pm
Anonymous
The conclusion of this paper is true?
The Distribution of Prime Numbers in an Interval
American Journal of Mathematics and Statistics, 2015 5(6), pp. 325-328
10.5923/j.ajms.20150506.01
http://article.sapub.org/10.5923.j.ajms.20150506.01.html
26 December, 2016 at 10:45 am
heverson01
“The first mathematical fact that amazed me was the Pythagorean theorem,” said mathematician Daina Taimina of Cornell University (USA). “I was a child and it seemed so incredible that it worked in geometry and worked with numbers!
https://johanneshaertel.wordpress.com/2016/12/24/8-os-beneficios-do-abacate/
23 February, 2017 at 1:42 pm
Kevin Smith
Hello Terry, I am wondering if the asymptotic correlations will remain the same here when $k$, $l$ are positive real numbers and not necessarily integer. What is your opinion on this?
25 February, 2017 at 10:45 am
Terence Tao
The top order term in the asymptotics should be basically the same (replacing factorials with Gamma functions as appropriate, of course). The lower order terms are more subtle, I think one should get an infinite asymptotic series in powers of
now, rather than just a polynomial. (One already sees this behavior just for the 1-point correlations
when
is non-integer.)
27 December, 2017 at 9:55 am
Correlations of the von Mangoldt and higher divisor functions II. Divisor correlations in short ranges | What's new
[…] discussed in this previous post, one heuristically expects an asymptotic of the […]
22 February, 2020 at 1:46 am
James Moriarty
Apparently you were unhappy with Windows Phone 8/8.1. What’s the feature you missed? What’s what you didn’t like?