3
$\begingroup$

What is the smallest known $c$ so that for any $n\geq 2$ there are at least $n/\log_2{n}$ primes between $n$ and $cn$ (inclusive)?

The prime number theorem seems to give an asymptotic result so I am not sure how to get a particular constant from it.

I am interested in answers that depend on well known conjectures as well as answers that are known to be correct.

Following a comment, the notation $\log_2{n}$ refers to taking the logarithm base $2$.

[Cross-posted from math.se where $c=13/6$ was suggested as a possibility.]

Improve this question
$\endgroup$
7
  • $\begingroup$ I can think of three interpretations for $\log_2 n$. Which one do you have in mind? Gerhard "Perhaps You Mean Base Two?" Paseman, 2015.05.15 $\endgroup$
    – Gerhard Paseman
    Commented May 15, 2015 at 16:05
  • $\begingroup$ @GerhardPaseman I mean log base two. For example $\log_2{8} = 3$. Does that reduce the number of options? (What were your three interpretations?) $\endgroup$
    – Simd
    Commented May 15, 2015 at 16:07
  • $\begingroup$ Iterated log and a messed up version of $(\log n)^2$. It would be nice for you to edit the question not only to clarify but to include some motivation. Gerhard "If You Would, Pretty Please" Paseman, 2015.05.15 $\endgroup$
    – Gerhard Paseman
    Commented May 15, 2015 at 16:12
  • $\begingroup$ @GerhardPaseman Thank you. I am not sure if I should be embarrassed but my motivation is mathematical curiosity. $\endgroup$
    – Simd
    Commented May 15, 2015 at 16:15
  • 2
    $\begingroup$ projecteuclid.org/euclid.ijm/1255631807 $\endgroup$
    – user41593
    Commented May 15, 2015 at 17:07

2 Answers 2

Reset to default
11
$\begingroup$

Assuming I made no mistake, $c=11/5$ is the smallest such value.

Let $c=11/5$. Using Theorem 1 of Rosser-Schoenfeld, we see easily that $$\pi(cn)-\pi(n-1)\geq(\log 2)\frac{n}{\log n},\qquad n\geq 74,$$ where $\log$ is the natural logarithm as usual in analytic number theory. We can verify the same inequality for $2\leq n\leq 73$ by computer. Finally, for $n=5$ the above inequality means that there are at least $3$ primes in $[5,5c]$, whence $c\geq 11/5$ is necessary.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ @eleanora: Actually, Rosser-Schoenfeld is the standard reference for such things. They wrote further papers, but this one is cited the most. $\endgroup$
    – GH from MO
    Commented May 15, 2015 at 17:56
  • 2
    $\begingroup$ That is good to know. As you can tell, this is not my usual academic field. $\endgroup$
    – Simd
    Commented May 15, 2015 at 17:56
2
$\begingroup$

Indeed, the suggestion given in the other thread is quite appropriate. Use a lower bound from Dusart for $\pi(cn)$, and an upper bound for $\pi(n)$, and you want the difference between these bounds to be at least $n/\log_2 n$. Using results from Dusart which apply for $n \gt $ three billion (primarily that $\pi(n) \leq (n/ \ln n)[1 + 1/ \ln n + 2.334 / (\ln n)^2]$ ), rewriting $1/ \ln n$ as $\epsilon$ and $1/ \ln cn$ as $\epsilon/(1 + \epsilon \ln c)$, after the dust settles one wants $c$ that satisfies

$$c \frac{1}{1 + \epsilon \ln c} [1 + \frac{\epsilon}{1 + \epsilon \ln c} + \frac{2\epsilon^2}{(1+ \epsilon \ln c)^2}] > \ln 2 + 1 + \epsilon + 2.334 \epsilon^2,$$ where we have $\epsilon \lt 1/20$. Thus, look for a $c$ that works for the first three billion $n$ (I haven't checked, but $c=13/6$ seems like a good candidate), and make sure that the above equation is satisfied for this $c$ and $\epsilon$ not too large (which it is for $c=13/6$, since the left hand side is at least 2 and the right hand side is less than 2.

Gerhard "Just A Matter Of Computation" Paseman, 2015.05.15

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ You can probably use older inequalities from Rosser/Schoenfeld which apply for all $n \gt 286$ to do a proof by hand. Just check that $\epsilon$ is small enough to pull the result through. Gerhard "Rewriting Terms Really Helps Here" Paseman, 2015.05.15 $\endgroup$
    – Gerhard Paseman
    Commented May 15, 2015 at 17:26
  • 1
    $\begingroup$ Indeed, such a computation has been outlined by GH from MO, who has even checked smaller values and found that $c=13/6$ does not quite cut it. Gerhard "Missed It By That Much" Paseman, 2015.05.15 $\endgroup$
    – Gerhard Paseman
    Commented May 15, 2015 at 17:38

You must log in to answer this question.

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