Primes sum ratio
Let
$$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?
Solution 1:
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):
- $$\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} $$
- $$\sum_{n\ge2}\;\sum_{p\text{ prime}} \frac{\chi(p)^n}{np^{ns}}\le 2\zeta(2)$$
- $$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)$$
- $$\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.
Solution 2:
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}$$