$$G(n)=\begin{cases}1 &\text{if }n \text{ is a prime }\equiv 3\bmod17\\0&\text{otherwise}\end{cases}$$

And let

$$P(n)=\begin{cases}1 &\text{if }n \text{ is a prime }\\0&\text{otherwise.}\end{cases}$$

How to prove that

$$\lim_{N\to\infty}\frac{\sum\limits_{n=1}^N G(n)}{\sum\limits_{n=1}^N P(n)}=\frac1{16}$$

And what is $$\lim_{N\to\infty} \frac{\sum\limits_{n=1}^N n\,G(n)}{\sum\limits_{n=1}^N n\,P(n)}?$$

And what is $O(f(n))$ of the fastest growing function $f(n)$ such that the following limit exists: $$\lim_{N\to\infty} \frac{\sum\limits_{n=1}^N f(n)\,G(n)}{\sum\limits_{n=1}^N f(n)\,P(n)}$$

And does this all follow directly from the asymptotic equidistribution of primes modulo most thing, if such a thing were known? And is it known?

  • 1
    $\begingroup$ As for your question about asymptotic equidistribution: what are the residues, modulo 17, which have properties which might single them out as being more or less likely to occur as the residue of a prime? (For 12, for instance, there is exactly one prime which has a residue of 3, out of infinitely many; and exactly zero primes have a residue of 8.) If the remaining residues were equidistributed asymptotically, what would this mean for the residue 3 modulo 17? $\endgroup$ – Niel de Beaudrap Oct 1 '11 at 11:20
  • $\begingroup$ The first question was answered by de la Vallée-Poussin shortly after the Prime Number Theorem was proved. For any $a$ relatively prime to $b$, the long-term proportion of primes of the form $a+kb$ is $1/\varphi(b)$, where $\varphi$ is the Euler $\varphi$-function. Thus the answer in your case is indeed $1/16$. The general result is deep, and there is no reason to think that there is a substantially easier argument in your special case. For the second "weighted" question, I do not know the answer. $\endgroup$ – André Nicolas Oct 1 '11 at 16:00
  • 1
    $\begingroup$ I've corrected the "\mbox"s, changing them to "\text". The essay at this URL does not only apply to Wikipedia. This can seriously confuse people who try to take the practice from $\LaTeX$ used on websites to $\LaTeX$ used in the normal way. $\endgroup$ – Michael Hardy Oct 1 '11 at 17:27
  • 4
    $\begingroup$ You will likely also be interested in the following paper: arxiv.org/abs/math/0408319v1 $\endgroup$ – Craig Oct 3 '11 at 15:05

The first part is a special case of a density result that spiritually follows Dirichlet's theorem. First:

Theorem. Let $A$ be a set of prime numbers. If the natural density $$\lim_{n\to\infty}\frac{\#\{ a\le n,\;a\in A\}}{\#\{p\le n,\; p \text{ prime}\}}$$ exists, then the Dirichlet density given by $$\lim_{s\to1^+}\frac{1}{-\log (s-1)}\sum_{a\in A} \frac{1}{a^s}$$ also exists and is equal to the first.

Note: Wikipedia cites J.P. Serre's "A Course in Arithmetic," but I haven't checked this. After the results below, this leaves just proving that the natural density exists in the first place (but I am presently having trouble locating a source covering this caveat). Second:

Theorem. If $a,n$ are coprime, then the asymptotic proportion of primes congruent to $a$ modulo $n$ is equal to $1/\varphi(n)$, where $\varphi$ is the totient function.

Informally this means that prime residues are proportionally "equidistributed" under any modulus (ignoring trivial residues sharing divisors with the modulus), though there are higher-order correction terms which show there is some imbalance (see e.g. Chebyshev's bias). The proof isn't too much more work after Dirichlet's theorem, and for that I refer you to Pete L. Clark's notes or Steven J. Miller's notes on the subject. DT itself does, however, take some real analytic machinery.

In my opinion, the four key highlights are (first see Dirichlet characters and $L$-functions):

  1. $$\frac{1}{\phi(n)}\sum_{\chi\mod n}\chi(a^{-1}m)=\begin{cases}1&m\equiv a\mod n\\0&\text{otherwise}\end{cases} $$
  2. $$\sum_{n\ge2}\;\sum_{p\text{ prime}} \frac{\chi(p)^n}{np^{ns}}\le 2\zeta(2)$$
  3. $$P_a(s)=\sum_{p\equiv a\mod n}\frac{1}{p^s}=\frac{1}{\varphi(n)}\sum_{\chi\mod n}\chi(a^{-1})\log L(s,\chi)+O(1)$$
  4. $$\zeta_N(s)=\prod_{\chi\ne\chi_0}L(s,\chi)\ge \sum_{\gcd(k,n)=1}\frac{1}{k^{\phi(n)s}} $$

After using (4), one can purge all $O(1)$ terms from equation (3) to obtain

$$P_a(s)\sim \frac{1}{\phi(n)}\sum_{p\text{ prime}}\frac{1}{p^s}.$$

Since $\sum p^{-s}\sim \log(\frac{1}{s-1})$ as $s\to1^+$, this proves the density theorem. This is just a partial skeleton of the full argument, but I think all of the relevant details and background information can be found in all of the links I've provided.

I don't have much to say about the rest. For the second listed question, it's plausible a calculation can be devised from loosely combining the $L$-function approach described above with some clever Riemann Stieltjes integration akin to Eric Naslund's answer in an M.SE question of mine, "How does $\sum_{p<x}p^{-s} $ grow asymptotically for $\mathrm{Re}(s)<1$?" (which would apply here with $s=-1$). The third and last question is a bit ill-defined, as I'm sure there are an infinite number of distinct growth classes which make the limit exist, with no clear maximum among them, but you can certainly discuss the possibility in reference to elementary functions e.g. polynomials and logarithms.

| cite | improve this answer | |
  • $\begingroup$ @kermit: If it's okay with you, I'd rather wait out the 4 days; maybe someone can answer the next two questions even if I can't. (Also, FWIW, I've tried combining RS integrals with Dirichlet L functions to evaluate the second problem and I just ended up going in circles; it appears the lower order terms 'cancel' and the higher order terms - which I don't have - get amplified into significance.) If you still want to give away the bounty I think you can press the 'flag' button on either my answer, this comment, or your original post with an explanation. $\endgroup$ – anon Oct 6 '11 at 18:55
  • 1
    $\begingroup$ @kermit - you have reported receiving an error when trying to award your bounty; what is the exact error message you see, please? $\endgroup$ – Jarrod Dixon Oct 6 '11 at 22:16

The first sum follows from Siegel-Walfisz_theorem

Summation by parts on the second sum should yield for large $N$:

$$\frac{\sum\limits_{n=1}^N n\,G(n)}{\sum\limits_{n=1}^N n\,P(n)}=\frac{(N\sum\limits_{n=1}^N G(n))-\sum\limits_{n=1}^{N-1}\sum\limits_{k=0}^{n} G(k)}{\sum\limits_{n=1}^N n\,P(n)}=\frac{(N\sum\limits_{n=1}^N P(n)/16)-\sum\limits_{n=1}^{N-1}\sum\limits_{k=0}^{n} P(k)/16}{\sum\limits_{n=1}^N n\,P(n)}=\frac1{16}$$

| cite | improve this answer | |
  • $\begingroup$ I've basically derived the same thing in another guise, but what I was unable to do is figure out why dropping off the error $\pi_{3,17}(N)-\pi(N)/16$ is justified (i.e. why $G$ can be replaced by $P/16$). Can you elaborate on that part? $\endgroup$ – anon Oct 7 '11 at 6:53
  • $\begingroup$ Also, an easier way than summation by parts is possible; one can "add and subtract" in the numerator and obtain $$(*)=\frac{\sum_{n\le N} n(G(n)-\frac{1}{16}P(n))}{\sum_{n\le N} nP(n)}+16.$$ There might be an easy way to see the non-16 term vanishes in the limit, but I can't figure it right now. $\endgroup$ – anon Oct 7 '11 at 7:04

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.