[math-fun] Still not about primes
Victor Miller <victorsmiller@gmail.com> wrote:
This phenomenon was dubbed "Chebyshev's bias" by Sarnak et. al. : https://en.wikipedia.org/wiki/Chebyshev%27s_bias
Granville and Martin have an entertaining article in the Monthly about it: https://dms.umontreal.ca/~andrew/PDF/PrimeRace.pdf
Thanks. That's a very interesting paper. But it's not at all what I was talking about. I was looking, not at whether there are more primes congruent to 3 mod 4 than to 1 mod 4, but at whether there are more primes for which a 3 mod 4 prime follows a 1 mod 4 prime or vice versa than there are for which a 3 mod 4 prime follows another 3 mod 4 prime or a 1 mod 4 prime follows another 1 mod 4 prime. Similarly with 1 mod 3 vs. 2 mod 3 primes. The bias toward prime types changing appears to be much larger than the Chebyshev bias. Of the first million primes (other than 2 and 3) there are 499799 and 500201 primes congruent to 1 mod 4 and 3 mod 4 respectively, a difference indistinguishable from noise, but there are 562576 primes for which a 3 mod 4 prime follows a 1 mod 4 prime or vice versa, and 437423 primes for which a 3 mod 4 prime follows another 3 mod 4 prime or a 1 mod 4 prime follows another 1 mod 4 prime. But, as I said right in the subject line, that wasn't what my post was about either. It was about the fact that there's a similar bias, in the same direction, in whether 3 mod 4 prime follows a prime that follows 1 mod 4 prime or vice versa (i.e. two spaces apart). Intuitively, the bias ought to be in the *opposite* direction. Not because of anything to do with primes, but because of binary sequences in general. If f(n) is usually different from f(n+1), and there are only two possible values for f, then surely f(n) must usually be the same as f(n+2). That's what my post was about. I checked my code several times, and counted the numbers by a completely different method (using search and replace in Emacs) before I trusted my results. My idea that the Thue-Morse sequence (A010060) might be a good one to test was productive. (That binary sequence starts with 0, then in each step the complement of the sequence is appended to the sequence: 0, 01, 0110, 01101001, 0110100110010110, etc.) Adjacent terms (f(n) vs. f(n+1)) differ 2/3 of the time. Terms two steps apart (f(n) vs. f(n+2)) *also* differ 2/3 of the time! (So much for my intuition.) I also checked differences up to 20 apart (f(n) vs. f(n+20)). Here's a table of what (asymptotic) proportion of the time the terms differed: 1 2/3 2 2/3 3 1/3 4 2/3 5 1/2 6 1/3 7 1/2 8 2/3 9 5/12 10 1/2 11 7/12 12 1/3 13 7/12 14 1/2 15 5/12 16 2/3 17 11/24 18 5/12 19 13/24 20 1/2 For powers-of-two spaces apart, they always differ 2/3 of the time (e.g. f(n) vs. f(n+64)). For any even number of spaces apart, they differ the same proportion of the time as they do half that many spaces apart (e.g. f(n) vs. f(n+6) is the same as f(n) vs. f(n+3)). I don't see any other obvious patterns in the above table, except that the numerators are never more than 1 away from half the denominator, and the denominators are always either 2, or 3 times a (possibly zero) power of 2. Neither the numerators nor the denominators are in OEIS. If I convert all of the above numbers into 24ths, I get: 16 16 8 16 12 8 12 16 10 12 14 8 14 12 10 16 12 10 13 12 Again, no obvious pattern. Is it possible to contrive a sequence for which the first two rows (f(n) vs. f(n+1) and f(n) vs. f(n+2)) both exceed 2/3? If not, what is the limit, and why?
If a binary sequence has f(n) != f(n+1) with frequency phi > 1/2, then the frequency of f(n) != f(n+2) has to be less than 2*(1 - phi); so it is not possible for both to exceed 2/3. But it is a lot easier to reason this out from the other direction: If we have f(n) != f(n+2) with frequency B, then the frequency of f(n) != f(n+1) has to be in the range [B/2, 1-B/2]. More specifically this frequency is B/2 + A*(1 - B), where A is the frequency with which the pattern f(n) == f(n+2) is filled in with the other value at f(n). A=0 is a sequence with no runs of length 1, A=1 is a sequence with no runs of length 3 or longer. All this generalizes Jim Propp's example; reasoning about these frequencies is the same as reasoning about three correlated binary variables. On Sat, Jan 4, 2020 at 3:08 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
Victor Miller <victorsmiller@gmail.com> wrote:
This phenomenon was dubbed "Chebyshev's bias" by Sarnak et. al. : https://en.wikipedia.org/wiki/Chebyshev%27s_bias
Granville and Martin have an entertaining article in the Monthly about it: https://dms.umontreal.ca/~andrew/PDF/PrimeRace.pdf
Thanks. That's a very interesting paper. But it's not at all what I was talking about. I was looking, not at whether there are more primes congruent to 3 mod 4 than to 1 mod 4, but at whether there are more primes for which a 3 mod 4 prime follows a 1 mod 4 prime or vice versa than there are for which a 3 mod 4 prime follows another 3 mod 4 prime or a 1 mod 4 prime follows another 1 mod 4 prime. Similarly with 1 mod 3 vs. 2 mod 3 primes.
The bias toward prime types changing appears to be much larger than the Chebyshev bias. Of the first million primes (other than 2 and 3) there are 499799 and 500201 primes congruent to 1 mod 4 and 3 mod 4 respectively, a difference indistinguishable from noise, but there are 562576 primes for which a 3 mod 4 prime follows a 1 mod 4 prime or vice versa, and 437423 primes for which a 3 mod 4 prime follows another 3 mod 4 prime or a 1 mod 4 prime follows another 1 mod 4 prime.
But, as I said right in the subject line, that wasn't what my post was about either. It was about the fact that there's a similar bias, in the same direction, in whether 3 mod 4 prime follows a prime that follows 1 mod 4 prime or vice versa (i.e. two spaces apart). Intuitively, the bias ought to be in the *opposite* direction. Not because of anything to do with primes, but because of binary sequences in general. If f(n) is usually different from f(n+1), and there are only two possible values for f, then surely f(n) must usually be the same as f(n+2). That's what my post was about.
I checked my code several times, and counted the numbers by a completely different method (using search and replace in Emacs) before I trusted my results.
My idea that the Thue-Morse sequence (A010060) might be a good one to test was productive. (That binary sequence starts with 0, then in each step the complement of the sequence is appended to the sequence: 0, 01, 0110, 01101001, 0110100110010110, etc.)
Adjacent terms (f(n) vs. f(n+1)) differ 2/3 of the time. Terms two steps apart (f(n) vs. f(n+2)) *also* differ 2/3 of the time! (So much for my intuition.) I also checked differences up to 20 apart (f(n) vs. f(n+20)). Here's a table of what (asymptotic) proportion of the time the terms differed:
1 2/3 2 2/3 3 1/3 4 2/3 5 1/2 6 1/3 7 1/2 8 2/3 9 5/12 10 1/2 11 7/12 12 1/3 13 7/12 14 1/2 15 5/12 16 2/3 17 11/24 18 5/12 19 13/24 20 1/2
For powers-of-two spaces apart, they always differ 2/3 of the time (e.g. f(n) vs. f(n+64)). For any even number of spaces apart, they differ the same proportion of the time as they do half that many spaces apart (e.g. f(n) vs. f(n+6) is the same as f(n) vs. f(n+3)). I don't see any other obvious patterns in the above table, except that the numerators are never more than 1 away from half the denominator, and the denominators are always either 2, or 3 times a (possibly zero) power of 2. Neither the numerators nor the denominators are in OEIS.
If I convert all of the above numbers into 24ths, I get: 16 16 8 16 12 8 12 16 10 12 14 8 14 12 10 16 12 10 13 12 Again, no obvious pattern.
Is it possible to contrive a sequence for which the first two rows (f(n) vs. f(n+1) and f(n) vs. f(n+2)) both exceed 2/3? If not, what is the limit, and why?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Keith F. Lynch -
Michael Collins