Let $\pi(x;q,a)$ count the number of primes $\leq x$ congruent to $a$ mod $q$. The Brun-Titchmarsh Theorem states that for all $q< x$, $(a,q)=1$, we have $$ \tag{1} \pi(x;q,a) \leq \frac{2x}{\varphi(q)\log(x/q)}. $$ Let $f(n) = 1$ if $n$ is prime and $0$ otherwise. Then we can rephrase $(1)$ as (almost) saying that $$ \tag{2} \sum_{\substack{n\leq x\\ n\equiv a (q)}} f(n) \leq \frac{2}{\varphi(q)} \sum_{\substack{n\leq x\\ (n,q)=1}} f(n). $$ I'm curious if inequalities like these have been studied for other arithmetic functions $f$. There is a vast literature proving asymptotic formulas, i.e. things like $$ \tag{3} \sum_{\substack{n\leq x\\ n\equiv a (q)}} f(n) \sim \frac{1}{\varphi(q)} \sum_{\substack{n\leq x\\ (n,q)=1}} f(n), $$ for various specific arithmetic functions (e.g. the divisor function or the indicator function of squarefree numbers or smooth numbers). However, I have not found much literature on inequalities like $(2)$. Thus my question:

Are there any results that prove inequalities like $(2)$ for arithmetic functions other than the prime-indicator function?

Any references and comments are most appreciated. Some thoughts and remarks about this general kind of problem:

  • The fact that $(1)$ has $x/q$ instead of $x$ inside the $\log$ is not a mere technicality; it represents a deep barrier to improving the inequality. By analogy, inequalities like $(2)$ might only be provable in a slightly weaker form.
  • Typically, one is more concerned with the range of validity and amount of uniformity of formulas of the type $(3)$, rather than the quality of the error terms (though these are certainly important as well). Given that the full conjectured range of validity and uniformity for formulas like $(3)$ are seldom known, inequalities like $(2)$ seem like an interesting avenue of research, as such inequalities (by analogy with $(1)$) may hold in wider ranges.
  • My original motivation for this was thinking about smooth numbers in arithmetic progressions. In that case, the constant $2$ arises from thinking about what might happen if Vinogradov's conjecture on the least quadratic non-residue modulo a prime was false (basically, if $y$ is small enough, every $y$-smooth number is a quadratic residue, and these would (conjecturally) equidistribute in the $\varphi(p)/2$ available residue classes).
  • Equidistribution results like $(3)$ often require complex/harmonic-analytic tools, such as the distribution of zeros of $L$-functions or estimates for Kloosterman sums (e.g. in the case of the divisor function). However, the Brun-Titchmarsh theorem (in its original form) uses only elementary sieve theory. If inequalities like $(2)$ can be proved without the use of such "heavy machinery," this would be another reason why they are interesting to study.

1 Answer 1


Yes, there are several results answering the question you ask about, in great generality.

  1. Linnik, in his monograph on the dispersion method, proved an analogue of (2) for the $k$-th divisor function. Concretely, $$\sum_{\substack{n \le x \\ n \equiv a \bmod q}} d_k(n) \ll \frac{x}{q} \left(\frac{\phi^{r-1}(q)}{q^{r-1}}\log x \right)$$ uniformly for $q \le x^{1-\varepsilon}$.

  2. This was generalized by Peter Shiu (a student of Halberstam) in his Crelle paper ''A Brun-Titchmarsh theorem for multiplicative functions'' (J. Reine Angew. Math. 313 (1980), 161–170) to a wide class of multiplicative functions. Here the bound takes the form $$\sum_{\substack{n \le x \\ n \equiv a \bmod q}} f(n) \ll \frac{x}{q} \frac{1}{\log x}\exp\left( \sum_{\substack{p \le x \\ p \nmid q}} f(p) \right)$$ uniformly for $q\le x^{1-\varepsilon}$, with an implied constant depending only on $f$ and $\varepsilon$. In fact, Shiu's result also allows you to add the additional restriction $n \in [x-y,x]$. Here $\frac{1}{\log x}\exp\left( \sum_{\substack{p \le x \\ p \nmid q}} f(p) \right)$ arises as the mean value of $\alpha$ over integers coprime to $q$ (up to a multiplicative constant bounded away from $0$ and $\infty$), by e.g. applying Wirsing's theorem to $f(n) \cdot 1_{(n,q)=1}$.

  3. A further generalization was given by M. Nair and G. Tenenbaum in ''Short sums of certain arithmetic functions'' (Acta Math. 180 (1998), no. 1, 119–144), building on earlier work of Nair. In particular, they show that 'multiplicative' can be replaced by (a weak notion of) 'submultiplicaitve', dependence of the constant on $f$ can be made more specific, and the growth condition imposed by Shiu (which I did not mention) can be considerably weakened. Moreover, one can obtain similar bounds for (sub)multiplicative functions in several variables evaluated on polynomial arguments. This generalization leads to new results. A. Hildebrand, in his MathSciNet review calls this generalization 'far-reaching' and 'definitive'.

  4. As far as I know, no author has tried to optimize the constant in the estimate (2) in the multiplicative setting.

  • 1
    $\begingroup$ Thanks for the detailed answer. I was aware of Shiu's paper, but wasn't sure if the constant had been optimized. $\endgroup$ Apr 10, 2022 at 16:50
  • 1
    $\begingroup$ I see. Then I am not aware of a single work dealing with the constant (although Nair and Tenenbaum specify on what 'invariants' the constant depends on). Shiu's paper is quite self-contained and I am sure for a given $f$ a constant can be given. I would start with simple functions: a function $f$ supported on squarefrees (e.g. $\mu^2$ or $\mu^2 \cdot d_2$), as the argument might be a bit simpler then. Optimizing the constant is tricky: even for the constant function $\mathbf{1}$, it is clear the argument is lossy (with constant >2), while one should get the constant $1$ essentially... $\endgroup$ Apr 10, 2022 at 18:33

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.