7
$\begingroup$

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?

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy