4
$\begingroup$

Is anything known asymptotically about the binary "primes mod 3" sequence besides Dirichlet's result that 1 and 2 occur half of the time? For example, can you prove that it does not eventually cycle forever with a simple "12" repetition?

(I would guess that this sequence is asymptotically random with no correlations, but it really wouldn't be that surprising if, for example, there were some tendency to switch back and forth in consecutive terms. If anyone has an argument, or data, indicating that this sequence is not so random, I'd like to hear about it.)

$\endgroup$
12
  • $\begingroup$ See the discussion in the comments of mathoverflow.net/questions/153656/… . It addresses essentially questions of your flavor. Not too much is probably known about the complexity of this sequence, but recent progress on primes would say something as Terry Tao indicates in these comments. $\endgroup$
    – Lucia
    Jan 16, 2014 at 16:41
  • 1
    $\begingroup$ One more comment: Work of Daniel Shiu shows that arbitrarily long strings of consecutive $1$'s (or consecutive $2$'s) will appear in this sequence. In particular this rules out the $12$ cycling forever. See also the recent preprint of Banks et al: arxiv.org/pdf/1311.7003v2.pdf . $\endgroup$
    – Lucia
    Jan 16, 2014 at 17:15
  • $\begingroup$ Is Shiu's result based on hypothesis or pure theory? I can't find the reference from Google and want to try to understand if this is proven with no assumptions. $\endgroup$
    – bobuhito
    Jan 16, 2014 at 17:29
  • $\begingroup$ Shiu's result is an unconditional theorem. The preprint of Banks et al linked above gives the reference (and also a different proof of Shiu's result based on Maynard's recent work). $\endgroup$
    – Lucia
    Jan 16, 2014 at 17:35
  • 1
    $\begingroup$ There is a very nice overview paper about these types of problems by Granville and Martin arxiv.org/abs/math/0408319 A quite simlar question got ask for mod 4 istead of mod 3 mathoverflow.net/questions/128079/a-bit-of-primes $\endgroup$
    – user9072
    Jan 16, 2014 at 18:24

1 Answer 1

2
$\begingroup$

I recommend the paper Chebyshev's Bias by Rubinstein and Sarnak, see also

http://en.wikipedia.org/wiki/Chebyshev%27s_bias

They show that in the sense of logarithmic density

http://en.wikipedia.org/wiki/Natural_density#Other_density_functions

primes congruent to 2 modulo 3 predominate. Specifically, and under certain hypotheses, $$ \lim_{x\to\infty}\frac{1}{\log x}\sum_{n<x,\pi(1,3,n)<\pi(2,3,n)}\frac{1}{n}\sim 0.9990\ldots, $$ where $\pi(a,b,x)$ counts the number of primes less that $x$ congruent to $a$ modulo $b$

$\endgroup$
6
  • $\begingroup$ Interesting. Let's say the sequence is "1212222121221111122..." from which I naturally calculate a "predomination sequence", P, as "1111222222222222112...". I can't use your summation (since the starting prime is considered secret), but I suppose that I could calculate the average P and see that it is greater than, for example, 1.501, even as my starting secret prime goes to infinity. Of course, this is all based on hypotheses, so I wonder if someone has tried to measure this limit. $\endgroup$
    – bobuhito
    Jan 16, 2014 at 17:19
  • $\begingroup$ @bobuhito Apparently a new discovery is that $p_{n+1}$ modulo 3 is strongly correlated to $p_n$ modulo 3. The same goes for other small moduli. See Mathematicians Discover Prime Conspiracy. $\endgroup$ Mar 14, 2016 at 22:26
  • $\begingroup$ @Jeppe I think this discovery is the "slight" effect already mentioned in comments. $\endgroup$
    – bobuhito
    Mar 23, 2016 at 15:43
  • $\begingroup$ @bobuhito You are right. Now I included it in a comment to the question as well (hopefully I am not being too redundant). $\endgroup$ Mar 23, 2016 at 16:00
  • $\begingroup$ @JeppeStigNielsen does this hold only modulo 3? What about other primes? $\endgroup$
    – Alephnull
    Aug 7, 2016 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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