Improving on the Brun-Titchmarsh Theorem

Technical Summary: Improving on the Brun-Titchmarsh Theorem

Problem Statement
The paper addresses the upper bound for the number of primes in an interval of length $N$, specifically the quantity $\pi(M+N) - \pi(M)$. The central goal is to refine the classical Brun-Titchmarsh Theorem, which asserts that for large $N$, this count is bounded by $2N / \log N$. While it is known that the constant 2 is optimal for sieve methods in a general context (the "parity principle"), the authors aim to quantify the $o(1)$ term more precisely. Specifically, they seek to establish a bound of the form:
$$\pi(M+N) - \pi(M) \le \frac{2N}{\log N + c}$$
for a specific, improved constant $c$. Previous works by Montgomery & Vaughan ($c=5/6$) and others had provided various values, but the authors aim to push this constant higher.

Methodology
The authors employ a hybrid sieving process that combines elements of the large sieve and the Selberg sieve, utilizing a framework they term "local models." The methodology proceeds through several distinct stages:

1. Hilbertian Inequalities and Almost Orthogonal Systems:
   The paper begins by establishing a generalized "almost orthogonal" system in a complex Hilbert space. This extends Selberg's lemma by introducing a bilinear error term involving coefficients $\omega_{i,j}$. This refinement allows for a more detailed handling of the remainder terms in the sieve. The authors derive a weighted inequality (Theorem 2.1) where weights $\xi_i$ are optimized to minimize the error, specifically addressing the problem of majorizing a step function by a polynomial.

2. Local Models for Primes:
   The sequence of primes in an interval is approximated using characteristic functions of integers coprime to a modulus $d$. To handle the redundancy inherent in the sequence of moduli (where knowing coprimality to $d$ implies coprimality to its factors), the authors define a "local system" using Ramanujan sums $c_q(n)$. They construct a basis of functions $\phi^*_q$ that are "almost orthogonal" with respect to a weighted inner product defined on the interval $[M+1, M+N]$.

3. Analysis of Remainder Terms:
   The core of the estimation involves bounding the remainder term $R$ arising from the bilinear form. This requires analyzing the distribution of integers coprime to a fixed modulus $f$ (chosen as $f=210$) within sub-intervals. The authors introduce functions $\theta^+_f(u)$ and $\theta^-_f(u)$ to bound the deviation of the count of such integers from their expected density. These functions are step functions that must be bounded from above by a polynomial.

4. Polynomial Approximation and Linear Programming:
   A significant technical hurdle is finding a polynomial $P(u)$ that strictly majorizes the step function $\theta^*_{210}(u)$ (derived from $\theta^+_f$ and $\theta^-_f$) while minimizing a specific linear functional $F(P)$. The authors note that standard approximation methods (like Bernstein polynomials) yielded poor numerical results. Instead, they utilize linear programming (specifically the lpsolve package) to find a polynomial of degree 25.

   • The polynomial is constrained to be greater than $\theta^*_{210}$ at 300 specific points.
   • Coefficients are restricted to a lower bound ($-1000$) to manage the non-compactness of the domain.
   • The authors acknowledge numerical instabilities and the fact that many coefficients hit the artificial boundary, preventing a fully rigorous analytic proof of the polynomial's global validity without numerical verification.

5. Final Optimization:
   The optimized polynomial is used to bound the error term in the sieve inequality. By sending the auxiliary parameters to infinity and optimizing the ratio $S^2/N$, the authors derive a lower bound for the quantity $N/Z - \frac{1}{2}\log N$, which translates directly into the constant $c$ in the final theorem.

Key Contributions and Results

• Main Theorem: The authors prove that there exists an $N_0$ such that for all $N \ge N_0$ and $M \ge 1$:
  $$\pi(M+N) - \pi(M) \le \frac{2N}{\log N + 3.53}$$
  (The calculation in the text yields $3.5372$, rounded to $3.53$ in the abstract).
• Hybrid Sieve Technique: The paper introduces a specific formulation of the sieve that blends the large sieve and Selberg sieve, utilizing "local models" to handle the remainder terms with greater precision than previous applications of these methods.
• Numerical Optimization in Sieve Theory: The work demonstrates the necessity of numerical methods (linear programming) to solve the optimization problems inherent in modern sieve theory, specifically the majorization of step functions by polynomials.

Significance and Limitations
The paper claims that the constant $3.53$ represents an improvement over previous bounds (such as $c=2.81$ found in "lectures on sieves"). However, the authors are explicit about the limitations of their result:

• Numerical Dependency: The result relies heavily on numerical computations, particularly the linear programming step. The authors note that they could not find a closed-form expression for the majorant polynomial and that the solution involved coefficients hitting artificial boundaries, which introduces numerical instability.
• Optimality: The authors state they are "not in a position to assert that our result is best possible," even within the confines of their own method. The improvement is achieved through a specific choice of weights and a numerical optimization of the polynomial, rather than a fundamental theoretical breakthrough in the parity principle itself.
• Scope: The improvement is specific to the constant in the denominator of the Brun-Titchmarsh bound for large $N$. The method does not claim to resolve the parity problem or provide asymptotic formulas, but rather tightens the upper bound for the count of primes in short intervals.

In summary, the paper provides a rigorous, albeit numerically assisted, improvement to the Brun-Titchmarsh constant by refining the error analysis in a hybrid sieve framework, acknowledging that the precision of the result is bounded by the numerical stability of the polynomial approximation used.