3
$\begingroup$

I don't know much (anything) about sieves, but as I read the section on the Selberg upper bound sieve from Greaves's Sieves in Number Theory, there is a theorem 4 which says that If $Y\ge X \ge 2$, then

\begin{equation} \pi(Y)-\pi(Y-X) \leq \frac{2X}{\log X} + O\left(\frac{X}{\log^2 X}\right). \end{equation}

  1. I would be interested in knowing what the best available bound is.
  2. Also, I notice that this bound holds irrespective of the value of $Y$. Are there ways to improve it for say $Y = 2X$ or $X= \sqrt{Y}$?

Thank you in advance!

Here, $\pi(X) = \sum_{p\leq x} 1$.

$\endgroup$
6
  • 2
    $\begingroup$ For your first question, it might be worth looking at Montgomery and Vaughn's 1973 paper "The large sieve". One of their main results is making this explicit. They show that (equation 1.12) $\pi(Y)-\pi(Y-X)\leq 2X/\log X$. It does appear possible to improve these results a bit further (see for instance, equation 1.11 in their paper) but this neat result of theirs is what is still used in most modern papers $\endgroup$ Commented Oct 30, 2022 at 22:25
  • 3
    $\begingroup$ In terms of the constant 2, improving this is known to be essentially equivalent to ruling out the existence of Seigel zeros (at least in the case when you also consider the primes in an arithmetic progression). $\endgroup$ Commented Oct 30, 2022 at 23:52
  • $\begingroup$ For Y=2X -- or indeed Y=O(X) -- we get an asymptotic formula from the Prime Number Theorem, which is X / log(X) without the factor of 2. $\endgroup$ Commented Oct 31, 2022 at 0:13
  • 1
    $\begingroup$ I think you don't really mean $Y=\sqrt X$. Maybe $X=\sqrt Y$? $\endgroup$ Commented Oct 31, 2022 at 1:14
  • $\begingroup$ @GerryMyerson, thanks! I have edited it now. $\endgroup$
    – user859588
    Commented Oct 31, 2022 at 8:21

1 Answer 1

6
$\begingroup$

If $Y\geq X\geq 2$, then as Daniel Johnston wrote, Montgomery and Vaughan proved that

$$\pi(Y)-\pi(Y-X)\leq \frac{2X}{\log X}.$$

Whether this constitutes a "best bound" requires a definition of what you consider to be "best". Expounding on Noam Elkies' comment, it follows from work of Heath-Brown (building on Hoheisel, Tchudakov, Heath-Brown and Iwaniec, Huxley, and many others) that if $Y^{7/12}\leq X\leq Y$, then

$$\pi(Y)-\pi(Y-X)\sim\frac{X}{\log Y}.$$

Therefore, for all $\epsilon>0$ there exists $Y_0(\epsilon)>0$ such that if $Y\geq Y_0(\epsilon)$ and $Y^{7/12}\leq X\leq Y$, then

$$\Big|\pi(Y)-\pi(Y-X)-\frac{X}{\log Y}\Big|\leq \epsilon \frac{X}{\log Y}.$$

(This can be made more precise using known error terms in the prime number theorem for short intervals.) The notion of "best" depends on context.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the references! $\endgroup$
    – user859588
    Commented Oct 31, 2022 at 19:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .