Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose every prime $n$ could "explode" once. An explosion results in $\lfloor \alpha \ln n \rfloor$ particles being uniformly distributed over the integers in a range $n \pm \lfloor \beta \ln n \rfloor$. If a particle hits a composite or a previously exploded prime, nothing happens. If a particle hits a new prime $p$, then $p$ explodes under the same rules. Here is a little simulation starting at $n=23$, with $\alpha=10$ and $\beta=5$:
           Animation
So, on the first step, $n=23$ explodes into $\lfloor 10 \ln 23 \rfloor = 31$ particles, uniformly spreading over $23 \pm 15$. In the run depicted, these particles hit four primes:$11, 13, 29, 31$. Then each of those explodes; and so on. In the last frame, $199$ is hit.

Q1. For which $\alpha$ and $\beta$, if any, will this process almost surely explode an infinite number of primes?

I am hoping the answer is independent of the starting $n$.

Being largely ignorant of number theory, I am wondering if current knowledge of the distribution of the primes is sufficient to answer this question. Thanks for insights or even speculations!

Q1 Answered. quid shows that a ballistic range of $\pm \beta \log n$ is not enough to bridge the prime gaps: $\pm \beta \log^2 n$ conjecturally suffices, but a range of more than $\pm \beta \sqrt{n}$ is all that current technology can prove.

Addendum. Both quid and joro confirm that even assuming RH (the Riemann Hypothesis), the range needed for my simulation to provably explode all primes is at least $\pm \beta \sqrt n \log n$. May I add this question:

Q2. What is the minimum ballistic $\pm$-range that would suffice to provably (under "current technology") explode (with sufficent $\alpha$) all primes without any RH or otherwise conjectural assumptions?

share|improve this question
6  
+1 for the great movie –  Lee Mosher May 11 '12 at 1:38
1  
Thank you, Lee! :-) –  Joseph O'Rourke May 11 '12 at 11:34
    
Are you sure current technology can prove (unconditionally)? $\beta \sqrt{n}$? Appears to me the best bound on prime gaps under RH is $O(\sqrt{n}\log{n})$ –  joro May 11 '12 at 13:33
    
@joro: No, which is why I said "more than." Your comment accords with quid's, and adds more detail. Thanks! A remarkable gap between what is known and what is conjectured. –  Joseph O'Rourke May 11 '12 at 13:36
1  
A remark and a question: it seems, according to Guy, Unsolved Problems in NT, the best knwon unconditional upper bound on prime gaps is x^(d+eps) with d = 6/11 [where x corresponds to the size of the prime not the number of the gap]. So that would be a lower bound for the necessary range. I assume but am now not sure, is your Q2 also meant as 'almost surely'? –  quid May 12 '12 at 2:41

1 Answer 1

up vote 34 down vote accepted

This process will never explode an infinite number of primes (independent of $n$, $\alpha$, $\beta$).

Let $g_n$ denote the gap between the $n+1$-th and the $n$-th prime. It is known that $g_n/\log n$ is unbounded; indeed by a result of Rankin there is an infinitude such that this is larger than $$\frac{c \log \log n \log \log \log \log n }{ \log \log \log n}$$ for an explicty $c$; see the wikipedia page on prime gaps for additional details.

Yet the largest number one can reach from the $n$-th prime (or any prime before) with the given rules is $p_n + \beta \log p_n$. Since $p_n$ is asymptotically $n \log n$ its logarithm is of order $\log n$. So the largest number one can reach is bounded above by $p_n + \gamma \log n$ for some $\gamma$ independent of $n$.

Yet, by the above mentioned result on prime gaps there are primes for which the next largest prime will be graeter than $p_n + \delta \log n$ for any $\delta$. Since one can never bridge a gap with a $\delta$ greater than the $\gamma$; the process can at most explode all the primes before such a gap, appearing after the starting value. That is, at most finitely many.

Addition for added Q2: First a partial summary of comments, in view of the above a minimal requirement for such a process to have the potential to go on indefinitely is that the range will exceed the maximal (relative) size of prime gaps. While conjecturally their size should (only) be of order $(\log x)^2$ (for numbers of size $x$), the best known upper bounds are much weaker, namely asymptotically $x^{6/11 + \epsilon}$ for every positive $\epsilon$.

Now, for the actual Q2, I am not completely sure what is asked regarding 'probabilty', and I am not well placed to comment on this 'probabilty' aspect either. If the range is large enough to bridge all the gaps and the number of newly created explosions is not too small (but even more than one seems sufficient) it is possible that some instance of the process explodes all primes; always explode just the next largest prime (and also the next smallest if one started in the middle) but nothing else. Yet no matter the choices at each step there is a positive probabilty that the process stops at that step. Yet, perhaps, the question when there is a positive porobability that everything explodes is intended. As said I am not well placed to say something on this.

share|improve this answer
    
I will change this later, but at the end I should that by 'such a gap' I mean one for a delta greater than that gamma (depending on beta, but not n) –  quid May 10 '12 at 19:48
2  
Beautifully clear answer! –  Joseph O'Rourke May 10 '12 at 19:50
    
@Joseph O'Rourke: thanks, you are welcome! @General: Sorry for yet another comment on mysellf: in case one should want to modify the process, two points to keep in mind: the true max size of gaps should be about c (log n)^2 (Cramér's conjecture), so one would need to be able to bridge this at least. Yet, the known upper bounds on the size of gaps, even conditional on RH, are much worse, bigger than sqrt(n). –  quid May 10 '12 at 19:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.