Let $B$ be a set of positive integers such that $\sum_{b \in B} 1 / \varphi(b) < +\infty$, where $\varphi(\cdot)$ is the Euler's totient function. For any $y > 0$ put $$\delta_y := \limsup_{x \to +\infty} \frac{\#\{p \leq x : \exists b \in B,\; b > y,\; p \equiv 1 \pmod b\}}{x / \log x} ,$$ where $p$ runs over the prime numbers and $\pi(\cdot)$ is the prime counting function. By the Dirichlet theorem on prime in arithmetic progressions, the primes $p \leq x$ such that $p \equiv 1 \pmod b$ are $$\sim \frac1{\varphi(b)} \frac{x}{\log x}$$ therefore I guess that it should be $$\delta_y \ll \sum_{\substack{b \in B \\ b > y}} \frac1{\varphi(b)} ,$$ and in particular $\delta_y \to 0$ for $y \to +\infty$.

My questions are: (1) Is it true that $\lim_{y \to +\infty} \delta_y = 0$ ? (2) If so, can we give an upper bound like $\delta_y \ll f(y)$, for some function $f(y)$ ? (3) If not, what other hypotheses on $B$ are required in order to have $\lim_{y \to +\infty} \delta_y = 0$?

I tried to estimate from above $\delta_y$ with the Brun–Titchmarsh theorem, but the problem is that $b$ could be of the order of $x$.

Thanks for any help.

  • $\begingroup$ First of all, nice job on a very well-asked question, that really pointed to the key issues directly. To demonstrate a possible idea to explore: if every element of $B$ were prime, and if you had the further assumption that $\#\{b\in B,\, b\le x\} = o(x/\log x)$, then that would suffice: for the possible $b\le\sqrt x$ you use exactly your Brun–Titchmarsh argument; and for $\sqrt b< x\le b$, there can only be one $b$ dividing any given $p-1$ (since otherwise $b_1b_2$ would divide $p-1$, but it's too big). This could be relaxed to the elements of $b$ having only large prime factors. $\endgroup$ Mar 18, 2017 at 21:52
  • 1
    $\begingroup$ I'm not sure (1) is true for all possible choices of $B$. Here's a construction to try out to possibly falsify (1): given an extremely rapidly sequence of real numbers $x_1,x_2,\dots$, let $B$ be the union of infinitely many intervals of the form $[x_j, x_j(1+1/j^2)]$. The growth is irregular enough that our intuitions about how thick these sets must be might not be correct. $\endgroup$ Mar 18, 2017 at 21:53

1 Answer 1


No, $\delta_y$ need not tend to 0. Take a rapidly increasing sequence of integers $y_n$. Then define the set $B$ as $\{p-1|\exists n: y_n\leq p\leq 2y_n\}$. Then we have \begin{eqnarray*} \delta_{y_n} & \geq & \limsup_{m>n}\frac{\log (2y_m)}{2y_m}\#\{p\leq 2y_n: \exists b>y_m, p\equiv 1\pmod{b}\}\\ & = & \limsup_{m>n}\frac{\log (2y_m)}{2y_m}(\pi(2y_m)-\pi(y_m))\\ & = & \frac{1}{2}. \end{eqnarray*} On the other hand $\varphi(n)\gg\frac{n}{\log\log n}$, thus $\sum_{y\leq p\leq 2y}\frac{1}{\varphi(p-1)}\ll\frac{\log\log y}{\log y}$, thus, if we take $y_n=2^{n^2}$, we get $$ \sum_{b\in B}\frac{1}{\varphi(p-1)} \ll \sum_{n=1}^\infty \frac{\log\log y_n}{\log y_n} \ll \sum_{n=1}^\infty\frac{\log n}{n^2}<\infty. $$

In general it is a bad idea to use pointwise estimates for multiplicative function, however, here it works because we have enough freedom in choosing the sequence $y_n$.

  • $\begingroup$ Thanks for this nice counterexample. However, I don't understand why you wrote "In general it is a bad idea to use pointwise estimates for multiplicative function, however, here it works...". Did'nt you actually show that pointwise estimates don't work for your choice of $B$? $\endgroup$
    – user40023
    Mar 19, 2017 at 12:18

You must log in to answer this question.