# Brun-Titchmarsh Theorem

## Primes in Arithmetic Progressions

One of the central problems of analytic number theory is understanding how primes distribute among residue classes.

For integers $a$ and $q$ with

$$
(a,q)=1,
$$

define

$$
\pi(x;q,a) =
\#\{p\leq x : p\equiv a\pmod q\}.
$$

The Prime Number Theorem for arithmetic progressions states that

$$
\pi(x;q,a)
\sim
\frac{\operatorname{li}(x)}{\varphi(q)}.
$$

However, this asymptotic theorem becomes difficult to use when $q$ grows with $x$.

The Brun-Titchmarsh theorem gives a strong unconditional upper bound valid uniformly over large ranges of moduli.

## Statement of the Theorem

Let

$$
1\leq q < x,
\qquad
(a,q)=1.
$$

Then

$$
\pi(x;q,a)
\leq
\frac{2x}{\varphi(q)\log(x/q)}
$$

for sufficiently large $x$.

More generally, for intervals,

$$
\pi(x+y;q,a)-\pi(x;q,a)
\leq
\frac{2y}{\varphi(q)\log(y/q)}
$$

under suitable conditions.

This theorem gives an upper bound for the number of primes in a residue class without requiring unproved hypotheses such as GRH.

## Interpretation

Heuristically, primes should distribute evenly among the

$$
\varphi(q)
$$

invertible residue classes modulo $q$.

Thus one expects approximately

$$
\frac{x}{\varphi(q)\log x}
$$

primes in each class.

The Brun-Titchmarsh theorem confirms that no residue class contains dramatically more primes than expected.

Although the constant $2$ is not believed optimal, the theorem is remarkably strong because it holds uniformly for large $q$.

## Comparison with the Prime Number Theorem

The Prime Number Theorem for progressions gives asymptotic equality:

$$
\pi(x;q,a)
\sim
\frac{x}{\varphi(q)\log x}.
$$

However, this statement is reliable only when $q$ is relatively small compared with $x$.

The Brun-Titchmarsh theorem provides only an upper bound, but it remains effective even when

$$
q
$$

is close to

$$
x.
$$

Thus the theorem complements asymptotic distribution results.

## Sieve-Theoretic Origin

The theorem arises naturally from sieve methods.

To count primes in the progression

$$
a \pmod q,
$$

one studies integers of the form

$$
nq+a.
$$

Applying upper-bound sieves estimates how many such integers avoid small prime factors.

The Selberg sieve gives especially clean proofs of the theorem.

Thus Brun-Titchmarsh is fundamentally a sieve estimate rather than a zero-free-region result.

## Why the Logarithm Changes

The denominator involves

$$
\log(x/q)
$$

instead of

$$
\log x.
$$

This reflects the fact that integers in the progression

$$
a \pmod q
$$

have effective density about

$$
1/q.
$$

The available interval length after fixing the progression is therefore reduced.

The logarithmic term adjusts for this restricted search space.

## Short Interval Version

A stronger formulation concerns primes in short intervals:

$$
\pi(x+y;q,a)-\pi(x;q,a).
$$

The theorem states roughly that the number of such primes is at most

$$
\frac{2y}{\varphi(q)\log(y/q)}.
$$

This is important when $y$ is much smaller than $x$.

Short-interval forms play a major role in modern prime gap problems.

## Relation with GRH

Under the Generalized Riemann Hypothesis, much stronger estimates are expected:

$$
\pi(x;q,a) =
\frac{\operatorname{li}(x)}{\varphi(q)}
+
O(\sqrt{x}\log x).
$$

The Brun-Titchmarsh theorem is weaker asymptotically, but it is unconditional and uniform in ranges where GRH-type estimates remain inaccessible.

Thus it remains extremely useful.

## Improvements and Refinements

Many mathematicians improved and refined the theorem.

Important developments include:

- sharper constants,
- stronger short-interval forms,
- weighted prime sums,
- averaged progression estimates.

Connections with the large sieve and zero-density methods produced deeper distribution results.

## Connection with Prime Gaps

The theorem constrains how concentrated primes can become in arithmetic progressions.

This indirectly affects prime gap theory because residue-class concentration influences local clustering behavior.

Modern bounded-gap arguments often combine sieve estimates with distribution theorems related to Brun-Titchmarsh-type bounds.

## Density Philosophy

The theorem reflects a general principle:

primes cannot cluster too heavily inside structured arithmetic sets.

Even without exact asymptotics, sieve methods impose strong upper limits on concentration.

This philosophy appears throughout analytic number theory and additive combinatorics.

## Importance

The Brun-Titchmarsh theorem is one of the most important upper-bound results in prime distribution theory.

It combines:

- sieve methods,
- arithmetic progressions,
- uniform distribution estimates,
- short-interval analysis.

The theorem remains a fundamental tool in modern analytic number theory, especially in situations where asymptotic formulas are unavailable or ineffective.