Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Does anyone know a proof of the Brun-Titchmarsh inequality in the following form starting from the large sieve inequality?

Brun-Titchmarsh inequality: Let $\pi(x;q,a) = |\{p \text{ prime}: p\equiv a \pmod q , p\le x\}|$, $(a,q) = 1$. Then $$\pi(x;q,a) \ll \frac{x}{\phi(q)} \frac{1}{\log(\frac xq)} \quad \text{for }q<x.$$ with an absolute implied constant.

By the large sieve inequality I mean

Large sieve inequality: Fix $M,N\ge 1$, $Q\ge 1$. For primes $p\le Q$, let $\Omega_p\subset \mathbb Z/p\mathbb Z$ be given. Let $\omega = |\Omega_p|$, and $S=\{M\le n\le M+N: n\pmod p\notin \Omega_p \text{ for }p\le Q\}$. Then $$|S|\le \frac{N+Q^2}{H},$$ where $H=\sum_{\substack{q\le Q, \\ q\text{ squarefree}}} \prod_{p\mid q} \frac{\omega_p}{p-\omega_p}$.

If you can prove it or know a reference, I'd be grateful. Thanks for your help!

share|cite|improve this question
up vote 3 down vote accepted

There is a set of notes on sieve methods by Denis Charles that provides a strengthening of the Brun-Titchmarsh Inequality using the Large Sieve Method. I have had it for some time, but I have not advanced very far yet. Please check the bottom of Page 88. :)

share|cite|improve this answer
Thanks for the link! – Sam Jan 28 '13 at 19:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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