Exploding primes - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T19:44:09Z http://mathoverflow.net/feeds/question/96604 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/96604/exploding-primes Exploding primes Joseph O'Rourke 2012-05-10T19:04:42Z 2012-05-12T15:02:45Z <p>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$: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/ExplodingPrimes1.gif" alt="Animation" /> <br /> 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.</p> <blockquote> <p><b>Q1</b>. For which $\alpha$ and $\beta$, if any, will this process almost surely explode an infinite number of primes?</p> </blockquote> <p>I am hoping the answer is independent of the starting $n$.</p> <p>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!</p> <p><b>Q1 Answered</b>. 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.</p> <p><b>Addendum</b>. Both quid and joro confirm that even assuming RH (<a href="http://en.wikipedia.org/wiki/Riemann_hypothesis" rel="nofollow">the Riemann Hypothesis</a>), the range needed for my simulation to <em>provably</em> explode all primes is at least $\pm \beta \sqrt n \log n$. May I add this question: </p> <blockquote> <p><b>Q2</b>. What is the minimum ballistic $\pm$-range that would suffice to provably (under "current technology") explode (with sufficent $\alpha$) all primes <em>without any RH or otherwise conjectural assumptions</em>?</p> </blockquote> http://mathoverflow.net/questions/96604/exploding-primes/96608#96608 Answer by quid for Exploding primes quid 2012-05-10T19:40:50Z 2012-05-12T15:02:45Z <p>This process will <em>never</em> explode an infinite number of primes (independent of $n$, $\alpha$, $\beta$). </p> <p>Let $g_n$ denote the gap between the $n+1$-th and the $n$-th prime. It is known that <code>$g_n/\log n$</code> 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$; <a href="http://en.wikipedia.org/wiki/Prime_gap" rel="nofollow">see the wikipedia page on prime gaps for additional details</a>.</p> <p>Yet the largest number one can reach from the $n$-th prime (or any prime before) with the given rules is <code>$p_n + \beta \log p_n$</code>. Since <code>$p_n$</code> 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$. </p> <p>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. </p> <p><strong>Addition for added Q2:</strong> 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$. </p> <p>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. </p>