7
$\begingroup$

Let $x$ and $y$ be positive reals in $(0,1)$ with $x < y$ and $y-x =\epsilon$. I seek smallest primes $p$ and $q$ such that $$x \le \frac{p}{q} \le (x+\epsilon) = y \;.$$

Q. What upper bound $u(\epsilon)$ can be placed on $\max\{p,q\}=\max(q)$ as a function of $\epsilon$?

Examples.

$x=\sqrt{2}/2 \approx 0.707107$, $\epsilon=10^{-4}$, $y=(x+\epsilon)$, then $$ x = \sqrt{2}/2 \approx 0.\color{blue}{707}{\color{red}{1}}07 < \frac{p}{q}=\frac{1217}{1721}\approx 0.\color{blue}{707}147 < 0.\color{blue}{707}{\color{red}{2}}07 \approx (\sqrt{2}/2 + \epsilon) = y \;. $$ For $\epsilon=10^{-5}$, $$ x = \sqrt{2}/2 \approx 0.\color{blue}{7071}\color{red}{0}7 < \frac{p}{q}=\frac{3491}{4937}\approx 0.\color{blue}{7071}096 < 0.\color{blue}{7071}{\color{red}{1}}7 \approx (\sqrt{2}/2 + \epsilon) = y \;. $$ I believe those are optimal prime ratios for those $x$ & $y$. If so, $u(10^{-4}) \ge 1721$ and $u(10^{-5}) \ge 4973$; and $u(10^{-6}) \ge 8597$ and $u(10^{-7}) \ge 38287$ (data not presented): $$ \begin{array}{cccc} \epsilon=10^{-4} & \epsilon=10^{-5} & \epsilon=10^{-6} & \epsilon=10^{-7}\\ u(\epsilon) \ge 1721 & u(\epsilon)\ge 4937 & u(\epsilon)\ge 8597 & u(\epsilon)\ge 38287 \end{array} $$

(The above question is tangentially related to the earlier question, "Visibility in a prime orchard.")

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ This is essentially a prime gap conjecture: For what primes q can we guarantee a prime p with xq < p < (x+e)q? Granted we don't know that there is a prime greater than xq and within log(xq)loglog(xq), but I would say it is likely once xq gets above 100. So pick q large enough so that (log(xq)^2)/q smaller than epsilon. Gerhard "I'd Say You're Probabilistically Safe" Paseman, 2015.07.11 $\endgroup$
    – Gerhard Paseman
    Commented Jul 11, 2015 at 23:48

1 Answer 1

Reset to default
2
$\begingroup$

Here is an idea which might help show that the smallest prime is not much larger than the smallest integer needed.

One of the processes I like to use is the mediant $\frac{a+c}{b+d}$ of two positive fractions $\frac ab$ and $\frac cd$ to approximate a real with a fraction of small denominator. Suppose we use the process to approximate $x +\epsilon/2$, say. At some point we will end with two ratios of integers of, say, $k$ decimal digits each, call them $\frac ab$ and $\frac cd$, with $$x \lt \frac ab \lt x + \frac{\epsilon}{2} \lt \frac cd \lt x + \epsilon$$.

Then the mediant $\frac{a+c}{b+d}$ will have at most $k+1$ digits in numerator and denominator, and this can be tweaked to adjust the numerator and denominator to be primes without moving the ratio out of the interval of interest. Probably one can tweak $\frac ab$ or $\frac cd$ similarly, but the point is that the prime representation won't need many more digits than the pure integer representation, and if $\epsilon$ is measured in negative powers of 10, I predict fewer decimal digits than that will be needed for the prime representation.

Gerhard "Caution: Much Vigorous Handwaving Nearby" Paseman, 2015.07.11

Improve this answer
$\endgroup$
3
  • $\begingroup$ I am happy to encounter the "mediant" outside of music. $\endgroup$
    – Joseph O'Rourke
    Commented Jul 12, 2015 at 0:43
  • 1
    $\begingroup$ @JosephO'Rourke, the term mediant is used in simple continued fractions, it is exactly how two consecutive "convergents" are combined to make the next one when the "digit" $a_i$ is $1.$ When the digit is larger than $1,$ the actual combination can be repeated by repeated mediant with the second convergent. This is in Khinchin's little book; he gives no name to my digits $a_i,$ some authors say "partial quotients" $\endgroup$
    – Will Jagy
    Commented Jul 12, 2015 at 19:41
  • $\begingroup$ Although I do not have a proof, there should be something (Stern-Brocot tree?) that says using the mediant iteratively to approximate a real by a rational gives at each stage the fraction with smallest denominator closest to the real: you don't miss any fractions with smaller denominator in doing so. I feel pretty confident about my prediction as a result. Once you have a/b comfortably in the interval with b not much smaller than $1/\epsilon$, tweaking top and bottom to get nearest primes should work. Gerhard "Look! I'm About To Fly!" Paseman, 2015.07.13 $\endgroup$
    – Gerhard Paseman
    Commented Jul 13, 2015 at 18:50

You must log in to answer this question.

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