# Small primes in arithmetic sequences

Fix an integer $a>1$. For $n \geq 1$ an integer, let $\pi_{n,1}(an)$ the number of primes $p \leq an$ such that $p \equiv 1 \pmod{n}$, and $\pi(an)$ the number of all primes $p \leq an$. Let $$Q_a(n) = \frac{\pi_{n,1}(an)}{\pi(an)} \phi(n),$$ where $\phi(n)$ is Euler's phi function.

If instead of fixing $a$ we fix $n$ and let $a$ goes to infinity, then by Dirichlet's theorem that $\lim_{a \rightarrow \infty} Q_a(n) = 1$. If we don't fix $n$ but let it goes to infinity fast enough relatively to $a$, for example $n=a^{1+\epsilon}$ with $\epsilon>0$ under (GRH), then one can prove that the limit is still 1 by some effective version of Dirichlet. But I am interested here in the case where $a$ is fixed. In this case, it is clear that $Q_a(n)$ varies to widely to have a limit when $n \rightarrow \infty$.

Hence let us tame $Q_a(n)$ by considering, following Cesaro, $C_a(n) = \frac{Q_a(1)+\dots+Q_a(n)}{n}$.

Does $C_a(n)$ have a limit when $a$ is fixed and $n$ goes to infinity ? If so what is this limit ?

I have made some sage computations for different values of $a$ ($a=2$ to $10$) and $C_a(n)$ seems to have a tendency to grow very slowly, though it is not clear if it is toward a finite limit or $+\infty$ -- or if the whole thing is just an artefact.

My motivation is trying to understand (if only conjecturally), in the simplest case I can think of, what happens to the effective Chebotarev density theorem beyond the version I can find in the literature. I'll appreciate any answer, be it unconditional, based on a conjecture like GRH, or even purely heuristic.

Comments (added on October 16th): I am interested in the question above for any integer $a$ but in my research a similar question arose with $a=8$. Actually I don't think the answer will really change of nature with $a$, so we can focus on the case $a=2$. In this case, the only number congruent to $1$ modulo $n$ between $1$ and $2n$ which is susceptible to be prime is $n+1$, hence $Q_2(n)=0$ if $n+1$ is not prime, while when $n+1$ is a prime $p$, $$Q_2(n)=\frac{\phi(p-1)}{\pi(2 (p-1))}.$$ By the way, this illustrates the fact that $Q_2(n)$ does not have a limit when $n \rightarrow \infty$: $0$ is obviously the inf.lim., but $+\infty$ is the sup.lim. : think on $n=p-1$ being for example the higher prime I'm a Sophie Germain's pair of prime, so that $\phi(n)=(p-1)/2-1$ and $Q_2(p-1) \sim \log p / 4$ which goes to inanity if one choses an infinite sequence of Germain's primes (which is widely expected to exist -- at this stage, I am perfectly happy to use any conjecture even if one can do otherwise).

Back to the question, one has: $$C_2(n) = \frac{1}{n} \sum_{1 < p \leq n,\ p \ \rm prime} \frac{\phi(p-1)}{\pi(2p-2)}.$$ Note that since $Q_2(n)$ is non-negative, one can replace it by an equivalent, so $$C_2(n) \sim D_2(n) := \frac{1}{n} \sum_{1 < p \leq n,\ p \ \rm prime} \frac{\phi(p-1) \log(p)}{2p},$$ and the question begins to look like a complicated version of a question already asked several times on mathoverflow about the Cesaro average of Euler's $\phi(n)$, which behaves much more smoothly than $\phi(n)$ itself. Experimentally, here is what I get for $C_2(n)$ for $n=2^k$, $k$ running from $1$ to $23$:

0.750000000000000 0.500000000000000 0.300000000000000 0.254482323232323 0.204751427085986 0.182394996041895 0.174044947095252 0.177096489596196 0.177412757367371 0.175004984083009 0.175280949354989 0.176774240882088 0.177008402332853 0.178414103595542 0.178516411591865 0.179091173423042 0.179809089385918 0.180252447106263 0.180775697751659 0.181112338150868 0.181529153981739 0.181858564625316 0.182136158910456

To me it looks like $C_2(n)$ has a limit or perhaps goes to infinity a little bit slower than $\log n$, but I am really not well-trained in the difficult art of divination of limits of sequences from their first terms... What do you think?

-
Wait, is it really known that $n=a$ is fast enough? That would imply in particular a Linnik constant of at most 2. –  Noam D. Elkies Oct 15 '12 at 1:05
Noam, you're right, my mistake. I should have say "under (GRH)". Even so, I am not sure that n=a is fast enough, but if I am not mistaken again, $n=a^{1+\epsilon}$ for any positive $\epsilon$ is. Indeed, by effective Chebotarev, one has $|\pi_{n,1}(an) - \frac{1}{\phi(n)} Li(an)| < c \frac{1}{\phi(n)} (an)^{1/2} (\phi(n) \log n + \phi(n) \log an)$, hence for $a=n^{1+\epsilon}$, $|Q_a(n)-1|< c' n^{-1-\epsilon/2} \phi(n) \log n$ which goes to $0$ when $n \rightarrow\infty$. –  Joël Oct 15 '12 at 5:22
I am editing the question to remove this mistake. –  Joël Oct 15 '12 at 5:23
I prefer "too widely". Also, are you interested in small a , large a, all a, or any a? I suspect that a=7 makes things a little more tame than a=1. Gerhard "Ask Me About System Design" Paseman, 2012.10.15 –  Gerhard Paseman Oct 15 '12 at 15:37
It seems to me that expanding $\phi(p-1) = \sum_{d,m:dm=p-1} \mu(d) m$ and working out the asymptotics for $\sum_{p: p=1 \hbox{ mod } d} \frac{(p-1)/d}{2p} \log p$ should do the job, as this sum decays roughly like $1/d^2$ (using Brun-Titchmarsh for the large d case) and so should be convergent in $d$. –  Terry Tao Oct 16 '12 at 15:10
show 1 more comment

When $a=2$, the sum you want the asymptotics of is basically $$\frac12 \frac{\log n}n \sum_{p\le n} \frac{\phi(p-1)}{p-1} \sim \frac12 \frac1{\pi(n)} \sum_{p\le n} \frac{\phi(p-1)}{p-1},$$ which is half the average value of the multiplicative function $\phi(n)/n$ on shifted primes $p-1$. The heuristic for evaluating this constant is as follows: recall that $$\frac{\phi(p-1)}{p-1} = \prod_{q\mid(p-1)} \bigg( 1-\frac1q \bigg).$$ For every fixed prime $q$, a proportion $1/(q-1)$ of primes $p$, namely those congruent to $1$ (mod $p$), will have $\phi(p-1)/(p-1)$ containing a factor of $1-1/q$; the others, a proportion $(q-2)/(q-1)$ of the primes, simply have the factor 1 instead. Heuristically, all these contributions are independent, and so the average value of $\phi(p-1)/(p-1)$ should be the product of the averages for each $q$, which are $$\frac1{q-1} \bigg( 1-\frac1q \bigg) + \frac{q-2}{q-1}1 = 1-\frac1{q(q-1)}.$$ Therefore we predict that $$\frac12 \frac1{\pi(n)} \sum_{p\le n} \frac{\phi(p-1)}{p-1} \to \frac12 \prod_q \bigg( 1-\frac1{q(q-1)} \bigg) \approx 0.186978.$$ This can be proved without much difficulty, using the method outlined in Terry's comment. EDITED TO ADD: $$\sum_{p\le n} \frac{\phi(p-1)}{p-1} = \sum_{p\le n} \sum_{d\mid(p-1)} \frac{\mu(d)}d = \sum_{d\le n} \frac{\mu(d)}d \sum_{p\le n, p\equiv1\pmod d}1 = \sum_{d\le n} \frac{\mu(d)}d \pi(n;d,1),$$ where $\pi(x;q,a)$ is the number of primes $p\le x$ with $p\equiv a\pmod q$. Now one can use the prime number theorem in arithmetic progressions to get an asymptotic formula for $\pi(n;d,1)$ when $d$ is small and the Brun-Titchmarsh theorem to get an upper bound for $\pi(n;d,1)$ when $d$ is large. The result will be the same, in the limit, as what you get if you simply plug in $\pi(x)/\phi(d)$ for $\pi(x;d,1)$: $$\frac12 \frac1{\pi(n)} \sum_{p\le n} \frac{\phi(p-1)}{p-1} \sim \frac12 \sum_{d\le n} \frac{\mu(d)}{d\phi(d)} \sim \frac12 \sum_{d=1}^\infty \frac{\mu(d)}{d\phi(d)} = \frac12 \prod_p \bigg( 1 + \frac{-1}{p\phi(p)} + \frac0{p^2\phi(p^2)} + \cdots \bigg).$$
Beautiful! The heuristic is certainly correct, as your numerical value is very pleasingly the limit of my sequence $C_2(n)$. As for the proof, however, my problem is that I don't understand Terry's comment. Could you explain a little bit more ? –  Joël Oct 24 '12 at 19:28