WHY SHOULD ONE EXPECT TO FIND LONG RUNS OF (NON)-RAMANUJAN PRIMES ? PETERHEGARTY 2 1 ABSTRACT. Sondow et al have studied Ramanujan primes (RPs) and observed nu- 0 merically that, while half of all primes are RPs asymptotically, one obtains runs of 2 consecutivesRPs(resp. non-RPs)whicharestatisticallysignificantlylongerthanone n wouldexpectifonewastossinganunbiasedcoin. Inthisdiscussionpaperweattempt a a heuristicexplanationof thisphenomenon. Our heuristicfollowsnaturallyfromthe J PrimeNumberTheorem,butseemstobeonlypartlysatisfactory.Itmotivateswhyone 8 should obtain long runs of both RPs and non-RPs, and also longer runs of non-RPs 1 thanofRPs. However,italsosuggeststhatoneshouldobtainlongerrunsofRPsthan havesofarbeenobservedinthedata,andthisissueremainspuzzling. ] T N . h 1. THE MODEL t a m Consider the following random process : you have an infinite supply of identical [ biased coins, which return heads with probability p (1,1], and tails with probability ∈ 2 1 p. NowtossN ofthesecoins. Foreach i = 1,...,N, leth ,t denotethenumberof 1 i i − v heads (resp. tails)amongthefirst itosses. Thush +t = i. Alsodenote i i 7 4 ∆ := h t . (1.1) i i i 8 − 3 The coins that come up as heads will each be colored red or blue, according to the 1. following rule : Suppose the i:th toss is a head. Then color this coin red if and only if 0 thefollowingtwoconditionssare satisfied: 2 1 ∆ ∆ , for allj = i+1,...,N (1.2) j i : ≥ v and i X If1 k < iand ∆ ∆ , thenthereexistsl (k,i) suchthat ∆ < ∆ . (1.3) r ≤ k ≥ i ∈ l i a Otherwise, color the coin blue. The definition requires some thought, so here is an exampleto illustratehowtheschemeworks: toss 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 result H T H H T H H H T H T H H T H H ∆ 1 0 1 2 1 2 3 4 3 4 3 4 5 4 5 6 color B R B R R B B R B R R − − − − − Now what do we expect to observe, when N is large ? Well, with high probabil- ity (w.h.p.), we will observe close to pN heads and close to (1 p)N tails. Hence − Date:January19,2012. 2000MathematicsSubjectClassification. 11A41(primary). 1 2 PETERHEGARTY ∆ (2p 1)N w.h.p. Now at most one coin is colored red for each positive value N ≈ − attainedbythefunction∆. Ontheotherhand,foranyǫ > 0,w.h.p. thefunction∆will eventuallyexceed(2p 1 ǫ)N forgood. Hence,w.h.p. about(2p 1)N coinswillbe − − − colored red, and theremaining heads, about (1 p)N in number, will be colored blue. − So, as N , the fraction of redheads, amongst all heads, will almost surely (a.s.) → ∞ approach 2p 1 andthefractionofblueheadswilla.s. approach 1 p. Inparticular, when − − p p p = 2/3,abouthalfthehead-coins willbecoloredred andhalfcolored blue. I claim that, with p = 2/3, this is a good basic model to have in mind when one considers Ramanujan primes (RPs) : the red coins corresponding to RPs and the blue ones tonon-RPs. Iwillexplaintwothings: 1. Whythismodelisreasonable. 2. Why one expects to get longer runs of blue coins than if the red-blue coloring was donebytossinganother,fair coin. I will deal with the second issue first. However, the analysis will show that, in this model, one also expects longer runs of red coins than if the coloring was done fairly at random, though not as long as the blue runs. This may seem to contradict the data in [SNN]. AfterexplainingwhyIneverthelessconsiderthemodelto bereasonable, Iwill discussthisissue. 2. WHY DO WE GET LONG MONOCHROMATIC RUNS ? If a biased coin with probability p of heads is tossed N times, then it is well-known thattheexpectedlengthofthelongestrunofconsecutiveheadsisapproximately logN = log(1/p) log N. Another way of looking at this is that, for any k N, one expects to have 1/p ∈ to toss the coin on the order of (1/p)k times to have a reasonable probability of seeing at least one run of k consecutive heads. This is easy to see intuitively: the probability of any k consecutive coin tosses all resulting in heads is pk and thus, by linearity of expectation, the expected number of such runs amongst N tosses is (N k + 1)pk, − which (foranyfixed k)willbeΘ(1)when N = Θ[(1/p)k]. In particular, when p = 1/2, we expect to have to make on the order of 2k tosses to haveareasonableprobabilityofwitnessingarun ofk heads. Thefollowingfacts aboutbiased coin-tossingarealso well-known: Proposition 2.1 Suppose we toss a sequence of identical biased coins with probabil- ityp > 1/2ofheads. WithnotationasinSection1,foreachN N, letc denotethe N,p ∈ probabilitythat ∆ 0 for all i = 1,...,N. Then the numbers c are non-increasing i N,p ≥ in N and ifwelet c := lim c , then p N N,p →∞ 2p 1 c = − > 0. (2.1) p p PROOF : That cN,p cN+1,p is trivial. Let E,F and F′ denote the following three ≥ events: WHYSHOULDONEEXPECTTOFINDLONGRUNSOF(NON)-RAMANUJANPRIMES? 3 E : theeventthat∆ > 0foralli > 0,whenwemakeaninfinitesequenceoftosses. i F : theeventthat∆ 0 foralli > 0 whenwemakean infinitesequenceoftosses. i ≥ F : theeventthat∆ ∆ foralli > 1whenwemakeaninfinitesequenceoftosses. ′ i 1 ≥ Since thecoin tossesareindependent,onehas P(F) = P(F ). (2.2) ′ Secondly, itisclear that c = P(F). (2.3) p Thirdly,theeventE occursifandonlyifthefirsttossyieldsaheadandthereafterevent F occurs. Hence, ′ P(E) = p P(F ). (2.4) ′ · In Example1.13, Chapter3 of[D], itisshownthat P(E) = 2p 1. (2.5) − Eqs. (2.2)-(2.5)togetherimply(2.1), and theproofiscomplete. Remark2.2Itisnoaccidentthatc equalsthefractionofredheadsinthehead-coloring p modelofSection 1. Indeed, thisobservationisthebasisfortherigorousproofof(2.1). Fix p > 1/2 and consider the head-coloring model of Section 1. Fix k N and let ∈ denote the expected number of runs of k redheads, when N coins are tossed. I k,N E claim that,as N , → ∞ (2p 1)2 − pk−1 . Ek,N pk−1. (2.6) (cid:20) p (cid:21)· N ≤ To seetheright-handinequality,justobservethatifk consecutiveheads areall colored red, thenat thevery leastthek 1 headsfromthe2ndtothelast musthavebeen arun − ofk 1 heads,withnotailsinbetween. Thishappenswithprobabilitypk 1. Thus,the − − probabilityofarunofk redheadswithafixedstartingpointisatmostpk 1. Sincethere − are N k +1 possiblestartingpointsfortherun,linearityofexpectationimpliesthat − (N k +1)pk 1, (2.7) k,N − E ≤ − which gives the right-hand inequality in (2.6). For the lower bound, we again consider a fixed starting point. A sufficient condition to get a run of k redheads with a given startingpointisthat thefollowingthreeeventsalloccur: A: thestartingpointisaredhead, B : itisfollowedbya runofk 1 heads,withno tailsinbetween − C : thevalueof∆neveragaingoesbelowitsvalueat theend ofthisrun ofk heads. It is clear that each of B and C positively correlates with A, while B and C are in- dependent ofoneanother. Hence P(A B C) P(A) P(B) P(C). (2.8) ∧ ∧ ≥ × × As shown in Section 1, we know that P(A) 2p 1 as N . As above, the → − → ∞ event B occurs with probability pk 1. Thirdly, it is immediatethat P(C) c = 2p 1. − ≥ p p− Plugging everything into (2.8), we find that the probability of a run of k redheads with 4 PETERHEGARTY agivenstartingpointisatleast (2p−p1)2 ·pk−1. Linearityofexpectationthenyieldsthe h i left-hand inequalityin (2.6). Thisbringsusto ourfirst result: Proposition 2.3 In the model of Section 1, the expected length of the longest run of consecutive reds among a total of N heads, is on the order of logN . In other words, log(1/p) for any k N, we expect to have to make on the order of pk tosses in order to have a ∈ reasonableprobabilityofobservinga runofk redheads. In particular, when p = 2/3, the expected length of the longest run of consecutive reds among a total of N heads, is on the order of logN . In other words, for any log(3/2) k N,weexpecttohavetomakeontheorderof 3 k tossesinordertohaveareason- ∈ 2 ableprobabilityof observinga runof k redheads(cid:0). (cid:1) Remark 2.4 The proposition says that, for any fixed p > 1/2 and very large N, we expect to see runs of redheads amongst the heads of similar length to runs of heads amongstallthecoins. So what about blues ? Here, for simplicity, I only consider the case p = 2/3 for the moment1. Let k N and let denote the expected number of runs of 2k con- 2k,N ∈ F secutive blue heads somewhere amongst the first N coins. Suppose, for example, that in a run of 3k consecutive tosses one observes at least 2k tails2. This means that the function ∆ will have decreased by at least k over this run. All succeeding heads will definitely becolored blueat least untilthefunction ∆has risenby k again. Thenit isa tedious,butstandard,calculationtoshowthatthereisafixedu > 03suchthat,inorder for the function ∆ to increase by k, at least 2k heads will need to be revealed. Hence, as N , → ∞ F2k,N & u q , (2.9) 2k N · where q is the probability of a run of 3k tosses yielding at least 2k tails. Explicitly, 2k onehas 3k l 3k l 3k 1 2 − q = . (2.10) 2k (cid:18) l (cid:19)(cid:18)3(cid:19) (cid:18)3(cid:19) X l=2k A lowerboundfor thisis gotby simplytakingthel = 2k term,hence 2k k 3k 1 2 q . (2.11) 2k ≥ (cid:18) 2k (cid:19)(cid:18)3(cid:19) (cid:18)3(cid:19) 1Iwillgeneralisetoarbitraryp >1/2whenIgetthetime. Iwillindicatebelowwherechangesneed tobemade. 2More generally,one willneed to replace2 and3 by somenumbersdependingon p, andchosenin suchawaythatthefinalexponentin(2.13)willbelessthanp. 3Thisnumberwillalsodependonpinageneralanalysis. WHYSHOULDONEEXPECTTOFINDLONGRUNSOF(NON)-RAMANUJANPRIMES? 5 Now let k also. Put v := 3 . Applying Stirling’s estimate to (2.11), one → ∞ k 4πk q easily computesthat 3k 33 k 27 k v = v , (2.12) (cid:18) 2k (cid:19) ∼ k(cid:18)22(cid:19) k(cid:18) 4 (cid:19) and hencethat k 2k 1 1 q & v = v . (2.13) 2k k k (cid:18)2(cid:19) (cid:18)√2(cid:19) Putting all this together, and using the fact that u in (2.9) is a constant, plus that the functionv decreases subexponentiallyink, wehaveoursecond result: k Proposition 2.5 In the model of Section 1, with p = 2/3, the expected length of the longestrunofconsecutivebluesamongatotalofN heads,isatleast logN = 2log N. log(√2) 2 Inotherwords,forlargebutfixedk N,weexpecttohavetomakeatmostontheorder ∈ of (√2)k = 2k/2 tosses in order to have a reasonableprobabilityof observing a run of k blueheads. RemarkNotetheuseofthewords‘atleast’and‘atmost’inProposition2.5,asagainst ‘approximately’ in Proposition 2.3. This reflects the fact that we only have a lower bound in (2.9), whereas in (2.6) we haveboth upper and lowerbounds. Whileit seems difficult to compute F2k,N exactly, it is quite easy to see, with the help of Proposition N 2.1, that there will be some upper bound of the form c2k, for some c < 1. Hence, 1 1 in order to have a reasonable probability of observing a run of k blueheads, one does expect tohavetomakeanumberoftosseswhichis exponentialink. From Propositions 2.3 and 2.5 it follows that one expects to see longer runs, both of reds and blues, than if the coloring was done fairly at random, but that one expects to see even longer runs of blueheads than of redheads. Or, to put it another way, for any fixed,andlargeenoughk N,oneexpectstoseearunofkblueheadssomewhatearlier ∈ than a run of k redheads, and one expects to see both in turn much earlier than if the coloringwas donefairlyat random. 3. WHY IS THIS A REASONABLE MODEL FOR RPS ? First of all, we just focus on the ‘ordinary’RPs discussed in [SNN]4, which wewish to compare with the p = 2/3 model above. The obvious extension to the so-called Generalised RPs of[ABMRS] willbementionedat theend. So consider p = 2/3 as fixed for now. Let me describe, in somewhat informal terms, another random model which I claim is asymptotically equivalent to that in Section 1. Suppose we have two different radioactivesubstances, H (head) and T (tail). H decays twice as fast as T (i.e.: T has double the half-life of H). At some time t = 0, I start observing both substances and record each individual decay of a H- or a T-atom. For eachi N,leth ,t denotethenumberofH-(resp. T-)atomsamongstthefirstiwhich i i ∈ 4Table1ofthispapercontainssomeerrors,butthesehavebeencorrectedinarXiv:1105.2249(v2) 6 PETERHEGARTY decay. Then color a decayed H-atom red if conditions (1.2) and (1.3) hold, otherwise blue. If one wants to be more formal, one can phrase this in terms of two independent, parallel Poisson processes, one of which has double the intensity of the other. But the point is that thismodel is equivalent,as t , with that of Section 1. I leaveit to the → ∞ reader to convincehimselfofthis. From here, we can see the relevance to Ramanujan primes. First of all, the prime number theorem says that, for large x, there are approximately x primes up to x. logx Equivalently, it says that, for large n, the n:th prime satsifies p nlogn. Now sup- n ∼ pose that we start from some p and begin searching to the right of it for the next n prime p . There is, of course, nothing random about this search process. But in a n+1 well-known ‘random model’ for prime gaps, one imagines that this search is a Poisson process withintensity 1 1 . In thisrandommodel,thereisalsononeed tostart logn ∼ logpn thesearchataprime: thestartingpointcanalsobechosenatrandomwithoutaffecting themodel. Nowsupposeonechoosesalargerandomnumberxandstartstwoprimesearchesin parallel, one at x and the other at x/2, where the former search proceeds twice as fast as the latter. By this I mean that, when in the former process we have searched from x up to x + t, then in the latter we have searched from x/2 up to (x + t)/2. Since log(x/2) logx,oneseesthattheformerPoissonprocesshasapproximatelytwicethe ∼ intensity of the latter. Clearly, the method of determining whether a prime is Ramanu- jan or not is basically the same as that of deciding how to color the primes ‘revealed’ intheformerofthesetwoPoissonprocesses. Hence, wehaveshownhowourmodelin Section 1 isareasonablemodelfortheRamanujan primes. Finally,weturntoGeneralisedRPs. Tomodelc-Ramanujanprimes,oneshouldchoose p = 1 5. 1+c 4. DISCUSSION Everythingaboveis,ofcourse,heuristics. Thereisnothing‘random’abouttheprime numbers. More importantly, the Prime Number Theorem is a very precise statement about the density of the primes. This suggests that a main problem with our heuristic model is its Markovian nature. In other words, if I start a search for a prime from some point x, and don’t find any prime up to x + t, say, then the PNT implies that I am now, in some sense, ‘more likely’ to find a prime between x + t and x + 2t. The furtheronesearchesthemorerestrictivethePNTbecomes. Since, inordertoobservea monochromaticrun (equivalently,a run of (non)-RPs) of length k, one expects to have tosearchinarangeexponentialink (Props. 2.3and2.5),thePNTwill,indeed,impose severerestrictionson whatcan happen. In [SNN], the authors fix an upper bound x, and find the length of the longest run of (non)-RPs in [1,x]. Our models suggest that a better way of collecting the data would be to fix an integerk, and determinethe first timea run of k (non)-RPs appears. Thisisbecause,‘locally’,themodeloftwoparallelPoissonprocessesseemstobeokay. 5Iwillleaveallfurthercalculationsforgeneralctoanotherforum. WHYSHOULDONEEXPECTTOFINDLONGRUNSOF(NON)-RAMANUJANPRIMES? 7 Despitetheproblemsdiscussedabove,IdonotseeclearlywhyPropositions2.1and2.2 should not be a reasonable guidewhat should be observed, as k . In otherwords, → ∞ I conjecture that, once the numbers get big enough, one will also observe considerably longerrunsofRamanujanprimesthanafaircoin-tossingmodelwouldsuggest,though never as long as the runs of non-Ramanujan primes. If this is not the case, if the data in [SNN] is a reasonable guide to what happens asymptotically, then our model must contain aseriousflaw. ACKNOWLEDGEMENTS IthankJonathanSondowand Johan Tykessonforhelpful discussions. REFERENCES [ABMRS] A. Amersi, O. Beckwith, S.J. Miller, R. Ronan and J. Sondow, Generalised Ramanujan primes.PreprintatarXiv:1108.0475 [D] R.Durrett,Probability:TheoryandExamples(SecondEdition),DuxburyPress(1996). [SNN] J. Sondow, J.W. Nicholson and T.D. Noe, Ramanujan Primes: Bounds, Runs, Twins and Gaps,J.IntegerSeq.14(2011),Article11.6.2. DEPARTMENT OF MATHEMATICAL SCIENCES, CHALMERS UNIVERSITY OF TECHNOLOGY AND UNIVERSITY OFGOTHENBURG, 41296GOTHENBURG, SWEDEN E-mailaddress:[email protected]