19 Brun-Titchmarsh type theorems

Definition 19.1 Prime counting function on arithmetic progressions

Suppose \(a,q\in \mathbb Z\) with \(\gcd (a,q)=1\). For each \(x\geq 0\), define

\[ \pi (x;q,a)=\sum _{\substack {p\leq x\\ p\text{ prime}\\ q\mid (p-a)}}1. \]

The ordinary prime counting function can be recovered by \(\pi (x)=\pi (x;1,1)\).

The Prime Number Theorem (PNT) shows that \(\pi (x)\sim \frac x{\log x}\) as \(x\to \infty \). On the other hand, known results on the asymptotic behavior of \(\pi (x;q,a)\) depend greatly on how \(q\) and \(x\) are sent to \(\infty \). Heuristically, it is expected that for “most” sequences \(q_n,x_n\to \infty \) with \(q_n{\lt}x_n\), \(\pi (x_n;q_n,a)\sim \frac{x_n}{\varphi (q_n)\log (x_n)}\) as \(n\to \infty \). Brun-Titchmarsh type theorems make this precise by provide asymptotic upper or lower bounds on \(\pi (x;q,a)\) in terms of \(\frac x{\varphi (q)\log x}\) or related quantities, presupposing constraints between \(q\) and \(x\).

Definition 19.2 Logarithmic integral function

Define the offset logarithmic integral function for \(x\geq 2\) by \(\operatorname {Li}(x)=\int _2^x\frac{\mathrm du}{\log u}\). Note that \(\operatorname {Li}(x)\sim \frac x{\log x}\).

We first record two early results which recover the correct asymptotic under stringent assumptions.

Theorem 19.3 Brun-Titchmarsh theorem under GRH (1929) [ 272 ]

Under the Generalized Riemann Hypothesis (GRH), if \(q{\lt}x\), then

\[ \pi (x;q,a)=\frac{\operatorname {Li}(x)}{\varphi (q)}+O(x^{1/2}\log x). \]

Theorem 19.4 Walfisz (1936) [ 290 ]

Fix \(B\geq 0\) and suppose \(q\leq (\log x)^B\). Then there exists \(A=A(B){\gt}0\) such that

\[ \pi (x;q,a)=\frac{\operatorname {Li}(x)}{\varphi (q)}+O(x\exp (-A\sqrt{\log x})). \]

19.1 Upper bounds

Titchmarsh’s original theorem establishes a coarse asymptotic upper bound.

Theorem 19.5 Brun-Titchmarsh theorem (1929) [ 272 ]

If \(0{\lt}\theta {\lt}1\) and \(q\leq x^\theta \), then

\[ \pi (x;q,a)=O\left(\frac x{\varphi (q)\log x}\right)+O(x^{6(1-\theta )/7}). \]

Later bounds more generally bound the number of prime numbers equivalent to \(a\pmod q\) in the interval \([x,x+y]\). Observe that setting \(x=0\) indeed yields an improvement on previous results.

Theorem 19.6 Lint, Richert (1965) [ 283 ]

If \(y{\gt}q\), then

\[ \pi (x+y;q,a)-\pi (x;q,a){\lt}\frac{2y}{\varphi (q)\log (y/q)}\min \left(\frac32,1+\frac6{\log (y/q)}\right). \]

Theorem 19.7 Montgomery, Vaughan (1973) [ 219 ]

If \(y{\gt}q\), then

\[ \pi (x+y;q,a)-\pi (x;q,a){\lt}\frac{2y}{\varphi (q)\log (y/q)}. \]

On the other hand, various bounds improve on this result under polynomial relationships of the form \(q\leq x^\theta \). To state these, we need the following definition.

Definition 19.8 \(\theta \) and \(C_\theta \)

Suppose \(x{\gt}0\) and \(q\in \mathbb Z\). Define \(\theta :=\frac{\log q}{\log x}\), and let \(C_\theta {\gt}0\) be the smallest constant such that

\[ \max _{a:\gcd (a,q)=1}\pi (x;q,a)\leq \frac{(C_\theta +o(1))x}{\varphi (q)\log (x)} \]

as \(x\to \infty \).

Here is the historical progression of bounds on \(C_\theta \), where

\begin{align} \nonumber C_1(\theta ) =& \ - \frac{66}{33 - 16 \theta } \int _{2}^{4} \frac{\log (t-1)}{t} d t \\ \nonumber & + \frac{8}{4 - \left(3 + \frac{7}{64} \right) \theta } \int _{\frac{8 - \left(7 + \frac{7}{32} \right) \theta }{4 \theta }}^{\frac{165\left(4-\left(3+\frac{7}{64} \right) \theta \right)}{4(33 - 16 \theta )} - \frac{1}{4}} \frac{\log (t-1)}{t} d t \\ \nonumber & + \frac{8}{4 - \left(1 + \frac{7}{64} \right) \theta } \int _{\max \left(\frac{4- \left(1+ \frac{7}{64} \right) \theta }{2 (2-3 \theta )} - \frac{5}{4}, 2 \right)}^{\frac{8 - \left(7 + \frac{7}{32} \right) \theta }{4 \theta }} \frac{\log (t-1)}{t} d t \end{align}

and

\begin{align} \nonumber C_2(\theta ) =& \ - \frac{66}{33 - 16 \theta } \int _{2}^{4} \frac{\log (t-1)}{t} d t \\ \nonumber & + \frac{16}{8 - 7 \theta } \int _{\frac{8 - 7 \theta }{4 \theta }}^{\frac{165(8-7 \theta )}{8(33 - 16 \theta )} } \frac{\log (t-1)}{t} d t \\ \nonumber & + \frac{16}{8 - 3 \theta } \int _{\max \left(\frac{9 \theta }{4(2 - 3 \theta )}, 2 \right)}^{\frac{8 - 7 \theta }{4 \theta }} \frac{\log (t-1)}{t} d t. \end{align}

Table 19.1 Historical bounds on \(C_\theta \)

Reference

Range of \(\theta \)

Upper bound on \(C_\theta \)

Titchmarsh (1930)

\((0,1)\)

Finite

van Lint & Richert (1965) [ 283 ]

Montgomery & Vaughan (1973) [ 219 ]

Selberg (1991) [ 265 ]

\((0,1)\)

\(2/(1-\theta )\)

Motohashi (1973) [ 220 ]

\((0,1/3)\)

\(16/(8-3\theta )\)

Motohashi (1974) [ 221 ]

\((0,1/3]\)

\(2\) (on LH)

Motohashi (1973) [ 220 ]

\((2/5,1/2]\)

\(2/(2-3\theta )\)

Motohashi (1974) [ 221 ]

\([1/3,2/5]\)

\(4/(2-\theta )\)

Motohashi (1974) [ 221 ]

\([1/3,2/5]\)

\(2/(2-3\theta )\) (on LH)

Goldfeld (1975) [ 81 ]

\((0,24/71)\)

\(16/(8-3\theta )\)

Iwaniec (1982) [ 147 ]

\((0,9/20)\)

\(16/(8-3\theta )\)

Iwaniec (1982) [ 147 ]

\((0,9/20)\)

\(8/(4-2\theta )\) (if \(q\) cube-free)

Iwaniec (1982) [ 147 ]

\([9/20,2/3]\)

\(8/(6-7\theta )\)

Baker (1996) [ 3 ]

\((9/20,1/2)\)

\(4/(2-\theta )\)

Friedlander & Iwaniec (1997) [ 75 ]

\([6/11,1)\)

\((2-((1-\theta )/4)^6)/(1-\theta )\)

Maynard (2013) [ 208 ]

\((0,1/8]\)

\(2\)

Bourgain & Garaev (2014) [ 25 ]

\([1-\delta ,1)\)

\((2-c_0(1-\theta )^2)/(1-\theta )\)

Xi & Zheng (2024) [ 301 ]

\((9/20,1/2)\)

\(16/(8-(3+7/32)\theta )\)

Xi & Zheng (2024) [ 301 ]

\((9/20,1/2)\)

\(16/(8-3\theta )\) (if \(q\) prime)

Xi & Zheng (2024) [ 301 ]

\([1/2,12/23)\)

\(8/(5-5\theta )\) (if \(q\) prime)

Xi & Zheng (2024) [ 301 ]

\([12/23,32/61)\)

\(32/(32-43\theta )\) (if \(q\) prime)

Xi & Zheng (2024) [ 301 ]

\([32/61,8/15)\)

\(24/(16-17\theta )\) (if \(q\) prime)

Xi & Zheng (2024) [ 301 ]

\([8/15,7/13)\)

\(48/(40-49\theta )\) (if \(q\) prime)

Xi & Zheng (2024) [ 301 ]

\([7/13,6/11)\)

\(16/(11-12\theta )\) (if \(q\) prime)

Xi & Zheng (2024) [ 301 ]

\([6/11,4/7)\)

\(32/(28-35\theta )\) (if \(q\) prime)

Xi & Zheng (2024) [ 301 ]

\([9/51,9/11]\)

\(160/(89-91\theta )\) (if \(q\) smooth square-free)

Xi & Zheng (2024) [ 301 ]

\([1/8,5/12)\)

\(2\) (if \(q\) smooth square-free)

Xi & Zheng (2024) [ 301 ]

\([5/12,9/20)\)

\(5/(5-6\theta )\) (if \(q\) smooth square-free)

Xi & Zheng (2025) [ 302 ]

\([9/20,1/2)\)

\(66/(33-16\theta ) - C_1(\theta )\)

Xi & Zheng (2025) [ 302 ]

\([9/20,1/2)\)

\(66/(33-16\theta ) - C_2(\theta )\) (if \(q\) prime)

Xi & Zheng (2025) [ 302 ]

\([3/10,3/4]\)

\(24/(15-16\theta )\) (if \(q\) smooth square-free)

Xi & Zheng (2025) [ 303 ]

\([1/2,34/67]\)

\(240/(184-217\theta )\) (if \(q\) prime)

Xi & Zheng (2025) [ 303 ]

\([1/2,(\nu (2 \nu +1))/(4 \nu ^2 + \nu + 4)]\)

\(\frac{8}{6 - 7 \theta + \frac{2 \nu - (3 \nu + 4) \theta }{\nu (2 \nu - 1)}}\) for every integer \(\nu \geq 5\) (if \(q\) prime)

Let \(\theta _{\mathrm{char}}\) be the least constant such that for every \(\varepsilon {\gt}0\) there exists \(\delta {\gt}0\) such that one has a character sum bound of the form

\[ \sum _{l \leq L} \chi (l) \ll L q^{-\delta } \]

whenever \(\chi \) is a non-principal character mod \(q\) and \(L \geq q^{\theta _{\mathrm{char}}}+\varepsilon \). The Burgess bound [ 27 , 28 ] shows that \(\theta _{\mathrm{char}} \leq 3/8\), which can be improved to \(\theta _{\mathrm{char}} \leq 1/4\) for cube-free \(q\). The extended Lindelöf hypothesis implies that \(\theta _{\mathrm{char}}=0\).

In [ 147 , Theorem 3 ] it was shown that

\[ C_\theta \leq \max ( \frac{2}{1 - \theta \theta _{\mathrm{char}}}, \frac{2}{2-12\theta /5}). \]

This was improved in [ 198 ] to

\[ C_\theta \leq \max ( \frac{2}{1 - \theta \theta _{\mathrm{char}}}, \frac{2}{8/7-24\theta /35}). \]

A further (complicated) bound on \(C_\theta \) in the range \(3/7 \leq \theta {\lt} 9/20\) may be found in [ 3 , Theorem 2 ] .

In [ 301 ] , the bound \(C_\theta \leq 16/(8-(3+2\theta _{\mathrm{RP}})\theta )\) for \(9/20 {\lt} \theta {\lt} 1/2\) was established, where \(\theta _{\mathrm{RP}}\) is the exponent for the Ramanujan–Petersson conjecture for \(GL_2(\mathbf{Q})\). By the work of Kim and Sarnak [ 167 ] one has \(\theta _{\mathrm{RP}} \leq 7/64\). One can also convert exponent pairs to bounds on \(C_\theta \):

Theorem 19.9 From exponent pairs to Brun–Titchmarsh

[ 301 , Theorem 1.4 ] If \((k,\ell )\) is an exponent pair, then

\[ C_\theta \leq \frac{4}{(3+k-\ell ) - (3+3k-\ell )\theta } \]

whenever

\[ \frac{1+k-\ell }{2+2k-2\ell } \leq \theta \leq \frac{1+k-\ell }{1+2k-\ell }. \]

Averaged versions of the Brun–Titchmarsh inequality were proven in [ 119 ] , [ 120 ] , [ 147 ] , [ 59 ] , [ 72 ] , [ 73 ] [ 215 ] , [ 4 ] , [ 6 ] , [ 74 ] and [ 182 ] .

For any \(\theta \), let \(C'_\theta \) denote the best constant for which one has an upper bound

\[ \pi (x+x^\theta ) - \pi (x) \leq (C'_\theta +o(1)) \frac{x^\theta }{\log x} \]

for unbounded \(x\). The following bounds on \(C'_\theta \) are known:

Table 19.2 Historical bounds on \(C'_\theta \)

Reference

Range of \(\theta \)

Upper bound on \(C'_\theta \)

Montgomery & Vaughan (1973) [ 219 ]

\((0,1)\)

\(2/\theta \)

Iwaniec (1982) [ 147 ]

\((1/3,1)\)

\(18/(15\theta -2)\)

Iwaniec (1982) [ 147 ]

\((1/2,1)\)

\(4/(1+\theta )\)

Lou & Yao (1989) [ 199 ]

\((6/11,11/20]\)

\(22/(100\theta -45)\)

Lou & Yao (1992) [ 200 ]

\((6/11,1]\)

\(1.031\)

Baker, Harman, & Pintz (1997) [ 7 ]

\((0.55,1)\)

\(1.0001\)

R. Li (2025) [ 183 ]

\((0.52,0.521]\)

\((0.521,0.522]\)

\((0.522,0.523]\)

\((0.523,0.524]\)

\((0.524,0.525]\)

\((0.525,0.535]\)

\(2.874\)

\(2.700\)

\(2.583\)

\(2.536\)

\(2.437\)

\(2.347\)

19.2 Lower bounds

The most basic lower bound is Dirichlet’s theorem, stating that \(\lim _{x\to \infty }\pi (x;q,a)=\infty \); we shall not record it here. Until relatively recently, good lower bounds were not known on \(\pi (x;q,a)\) other than Theorem 19.4 for small \(q\), but there are many known estimates for the smallest value of \(x\) for which \(\pi (x;q,a){\gt}0\).

Definition 19.10 Linnik’s constant \(L\)

Define \(L\) to be the infimum over all \(L'{\gt}0\) where there exists \(q_0(L'){\gt}0\) such that for all \(q\geq q_0(L')\) and \(x{\gt}q^{L'}\), \(\min _{\gcd (a,q)=1}\pi (x;q,a){\gt}0\).

Here is the historical progression of \(L\).

Table 19.3 Historical bounds on \(L\)

Reference

Upper bound on \(L\)

Linnik (1994) [ 190 ]

\({\lt}\infty \)

Pan (1957) [ 228 ]

\(10000\)

Pan (1958) [ 229 ]

\(5448\)

Chen (1965) [ 34 ]

\(777\)

Jutila (1970) [ 158 ]

\(630\)

Jutila (1970) [ 157 ]

\(550\)

Chen (1977) [ 35 ]

\(168\)

Jutila (1977) [ 159 ]

\(80\)

Graham (1977) [ 84 ]

\(36\)

Graham (1981) [ 86 ]

\(20\)

Chen (1979) [ 36 ]

\(17\)

Wang (1986) [ 291 ]

\(16\)

Chen & Liu (1989) [ 37 ]

\(13.5\)

Chen & Liu (1990) [ 38 ]

\(11.5\)

Wang (1991) [ 292 ]

\(8\)

Heath-Brown (1992) [ 112 ]

\(5.5\)

Meng (2000) [ 211 ]

\(4.5\) (if \(q\) prime)

Meng (2001, 2010) [ 212 ] [ 213 ]

\(4.5\) (if \(q\) has bounded cubic part)

Xylouris (2009) [ 304 ]

\(5.2\)

Xylouris (2011) [ 305 ]

\(5.18\)

Xylouris (2011, 2018) [ 306 ] [ 307 ]

\(5\)

Montgomery (1971) [ 218 ]

\(\frac{5}{2} = 2.5\) (if \(q\) is a power of a fixed prime)

Forti & Viola (1973) [ 70 ]

\(\frac{45}{20 - \sqrt{3}} = 2.4633 \dots \) (if \(q\) is a power of a fixed prime)

Jutila (1972) [ 162 ]

\(\frac{3 (9 + \sqrt{17})}{16} = 2.4606 \dots \) (if \(q\) is a power of a fixed prime)

Huxley (1975) [ 125 ]

\(\frac{12}{5} = 2.4\) (if \(q\) is a power of a fixed prime)

B. Chen (2025) [ 31 ]

\(\frac{7}{3} = 2.3333 \dots \) (if \(q\) is a power of a fixed prime)

Banks & Shparlinski (2019) [ 10 ]

\(\frac{1}{0.4736} = 2.1115 \dots \) (if \(q\) is a power of a fixed prime)

R. Li (2025) [ 183 ]

\(\frac{1}{0.4752} = 2.1044 \dots \) (if \(q\) is a power of a fixed prime)

Heath-Brown (1990) [ 111 ]

\(3 + \varepsilon \) (under the existence and some conditions of the exceptional character, effective)

\(2 + \varepsilon \) (under the existence and some conditions of the exceptional character, ineffective)

Friedlander & Iwaniec (2003) [ 76 ]

\(\frac{117}{59} = 1.983 \dots \) (under the existence and some conditions of the exceptional character)

Recent work by Maynard [ 208 ] establishes asymptotic lower bounds for \(\pi (x;q,a)\).

Theorem 19.11 Maynard (2013) [ 208 ]

For sufficiently large \(q\) and \(x{\gt}q^8\), we have

\[ \frac{\log q}{q^{1/2}}\left(\frac x{\varphi (q)\log x}\right)\ll \pi (x;q,a). \]

Theorem 19.12 Maynard (2013) [ 208 ]

Let \(\epsilon {\gt}0\). There exists \(q_0(\epsilon ){\gt}0\) such that for all \(q\geq q_0(\epsilon )\),

\[ \frac{q^{-\epsilon }x}{\varphi (q)\log x}\ll \pi (x;q,a). \]