As mentioned in Terry Tao's comment to this question, it is constructively known
that there are primes between sufficiently large cubes. $\:$ According to wikipedia,
"there exists a constant $\: \theta < 1 \:$ such that $\;\;\; \pi \hspace{-0.03 in}\left(x\hspace{-0.04 in}+\hspace{-0.04 in}x^{\hspace{.02 in}\theta}\right)-\pi \hspace{.03 in}(x) \: \sim \: \dfrac{x^{\hspace{.02 in}\theta}}{\log(x)} \;\;\;$ as $x$ tends to infinity".

Is there any somewhat-similar corresponding effective result for the density of primes in short intervals?

Such a result could yield an effective randomized reduction from subset sum to this variant of factoring.

  • 1
    $\begingroup$ what is an effective randomized reduction? $\endgroup$
    – Turbo
    May 1, 2017 at 11:07

1 Answer 1


One can read off such an effective result from the work of Dudek. Indeed, examining his Section 3.3, we can get the following explicit lower bound for $x>\exp(8\times 10^{14})$ and $h=3x^{2/3}$: $$ \sum_{x<p\leq x+h}\log p>h-\tfrac{1}{2}(1-10^{-3})h-\tfrac{1}{2}(1-10^{-3})h-0.0008h. $$ (Note that Dudek's definition of $E(x,h,k)$ should be multiplied by $-1$.) That is, $$ \sum_{x<p\leq x+3x^{2/3}}\log p>0.0006x^{2/3},\qquad x>\exp(8\times 10^{14}).$$

Under the Riemann Hypothesis, much better explicit bounds are known, see e.g. Theorem 1.1 in the recent preprint of Dudek-Grenié-Molteni.


You must log in to answer this question.