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?

  • 2
    $\begingroup$ Wait, is it really known that $n=a$ is fast enough? That would imply in particular a Linnik constant of at most 2. $\endgroup$ Oct 15, 2012 at 1:05
  • $\begingroup$ 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$. $\endgroup$
    – Joël
    Oct 15, 2012 at 5:22
  • $\begingroup$ I am editing the question to remove this mistake. $\endgroup$
    – Joël
    Oct 15, 2012 at 5:23
  • $\begingroup$ 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 $\endgroup$ Oct 15, 2012 at 15:37
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Terry Tao
    Oct 16, 2012 at 15:10

1 Answer 1


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). $$

  • $\begingroup$ 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 ? $\endgroup$
    – Joël
    Oct 24, 2012 at 19:28
  • $\begingroup$ In the preceding comment, I meant "very plausibly" not "pleasingly" which was a delirium tremens of my spelling corrector. By the way, no one wants to explain to me Terry's comment (I think I just need a little more details)? $\endgroup$
    – Joël
    Oct 25, 2012 at 13:06
  • $\begingroup$ Great! thank you. $\endgroup$
    – Joël
    Oct 26, 2012 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.