[math-fun] Not about primes
I looked at the first million primes, excluding 2 and 3, to see how often a prime that's 1 mod 4 is followed by a prime that's 3 mod 4, and vice versa, as compared with the number of primes that are followed by another prime of the same 4-remainder. I noticed that there's a significant bias. A changed 4-remainder happens 281288 times in each direction. An unchanged four-remainder happens 218510 (1->3) and 218913 (3->1) times. So the total number of changes is 562576, which is well over the expected 499999.5. Next I checked how many changes there are between a prime and the prime *two* positions later, e.g. from 5 to 11, 7 to 13, or 11 to 17. Given that the changes between consecutive primes are unexpectedly high, I thought that changes between primes 2 positions apart would have to be low. The closer the sequence is to purely alternating, 1,3,1,3,1,3,..., the closer the second changes would have to be from unchanging, 1,1,1,1,1,... and 3,3,3,3,3,.... But that's not what I saw. The second changes are also well above half a million: 511084. Likewise with the third changes: 505466. And the fourth, fifth, etc. Not until the *29th* changes, i.e. whether a prime has the same 4-remainder as the prime 29 positions after it, is there a number of changes that is less than half a million, 499209. (Note that there are one-million-minus-n nth changes, e.g. 999971 29th changes, of which half, 499985.5 would by chance be different. Also note that if there's a bias, e.g. more primes 3 mod 4 than 1 mod 4, that ought to *reduce* the number of changes between primes n places different, for all n. In the limit, if all primes were 3 mod 4, there would be zero differences for every n.) I'm confused as to how this is possible. Given a long sequence containing just two numbers, e.g. the first million digits of pi in binary, if adjacent terms are less likely to be identical than chance would predict, how can the terms two apart also be less likely to be identical than chance? And just how large can these biases be? Is a million-term sequence possible in which there are 900000 differences between adjacent terms and 800000 differences between terms two places apart? If not, just how large can those numbers be, and how would one design a sequence to maximize them? Maybe it has something to do with Fourier transforms? Would the Thue-Morse sequence be an interesting example? As my subject line says, this is no longer about primes, but about changes in two-valued sequences in general.
This phenomenon was dubbed "Chebyshev's bias" by Sarnak et. al. : https://en.wikipedia.org/wiki/Chebyshev%27s_bias Victor On Fri, Jan 3, 2020 at 10:46 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
I looked at the first million primes, excluding 2 and 3, to see how often a prime that's 1 mod 4 is followed by a prime that's 3 mod 4, and vice versa, as compared with the number of primes that are followed by another prime of the same 4-remainder. I noticed that there's a significant bias. A changed 4-remainder happens 281288 times in each direction. An unchanged four-remainder happens 218510 (1->3) and 218913 (3->1) times. So the total number of changes is 562576, which is well over the expected 499999.5.
Next I checked how many changes there are between a prime and the prime *two* positions later, e.g. from 5 to 11, 7 to 13, or 11 to 17. Given that the changes between consecutive primes are unexpectedly high, I thought that changes between primes 2 positions apart would have to be low. The closer the sequence is to purely alternating, 1,3,1,3,1,3,..., the closer the second changes would have to be from unchanging, 1,1,1,1,1,... and 3,3,3,3,3,....
But that's not what I saw. The second changes are also well above half a million: 511084. Likewise with the third changes: 505466. And the fourth, fifth, etc. Not until the *29th* changes, i.e. whether a prime has the same 4-remainder as the prime 29 positions after it, is there a number of changes that is less than half a million, 499209.
(Note that there are one-million-minus-n nth changes, e.g. 999971 29th changes, of which half, 499985.5 would by chance be different. Also note that if there's a bias, e.g. more primes 3 mod 4 than 1 mod 4, that ought to *reduce* the number of changes between primes n places different, for all n. In the limit, if all primes were 3 mod 4, there would be zero differences for every n.)
I'm confused as to how this is possible. Given a long sequence containing just two numbers, e.g. the first million digits of pi in binary, if adjacent terms are less likely to be identical than chance would predict, how can the terms two apart also be less likely to be identical than chance? And just how large can these biases be? Is a million-term sequence possible in which there are 900000 differences between adjacent terms and 800000 differences between terms two places apart? If not, just how large can those numbers be, and how would one design a sequence to maximize them?
Maybe it has something to do with Fourier transforms?
Would the Thue-Morse sequence be an interesting example?
As my subject line says, this is no longer about primes, but about changes in two-valued sequences in general.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Granville and Martin have an entertaining article in the Monthly about it: https://dms.umontreal.ca/~andrew/PDF/PrimeRace.pdf On Fri, Jan 3, 2020 at 10:46 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
I looked at the first million primes, excluding 2 and 3, to see how often a prime that's 1 mod 4 is followed by a prime that's 3 mod 4, and vice versa, as compared with the number of primes that are followed by another prime of the same 4-remainder. I noticed that there's a significant bias. A changed 4-remainder happens 281288 times in each direction. An unchanged four-remainder happens 218510 (1->3) and 218913 (3->1) times. So the total number of changes is 562576, which is well over the expected 499999.5.
Next I checked how many changes there are between a prime and the prime *two* positions later, e.g. from 5 to 11, 7 to 13, or 11 to 17. Given that the changes between consecutive primes are unexpectedly high, I thought that changes between primes 2 positions apart would have to be low. The closer the sequence is to purely alternating, 1,3,1,3,1,3,..., the closer the second changes would have to be from unchanging, 1,1,1,1,1,... and 3,3,3,3,3,....
But that's not what I saw. The second changes are also well above half a million: 511084. Likewise with the third changes: 505466. And the fourth, fifth, etc. Not until the *29th* changes, i.e. whether a prime has the same 4-remainder as the prime 29 positions after it, is there a number of changes that is less than half a million, 499209.
(Note that there are one-million-minus-n nth changes, e.g. 999971 29th changes, of which half, 499985.5 would by chance be different. Also note that if there's a bias, e.g. more primes 3 mod 4 than 1 mod 4, that ought to *reduce* the number of changes between primes n places different, for all n. In the limit, if all primes were 3 mod 4, there would be zero differences for every n.)
I'm confused as to how this is possible. Given a long sequence containing just two numbers, e.g. the first million digits of pi in binary, if adjacent terms are less likely to be identical than chance would predict, how can the terms two apart also be less likely to be identical than chance? And just how large can these biases be? Is a million-term sequence possible in which there are 900000 differences between adjacent terms and 800000 differences between terms two places apart? If not, just how large can those numbers be, and how would one design a sequence to maximize them?
Maybe it has something to do with Fourier transforms?
Would the Thue-Morse sequence be an interesting example?
As my subject line says, this is no longer about primes, but about changes in two-valued sequences in general.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
In response to Keith’s question “if adjacent terms are less likely to be identical than chance would predict, how can the terms two apart also be less likely to be identical than chance?”: What Keith is asking (I think) is, if unbiased random bits x and y are negatively correlated, and unbiased random bits y and z are negatively correlated, how can x and z be negatively correlated? (Cf. “The enemy of my enemy is my friend”.) My favorite example of four pairwise negatively correlated unbiased random bits is four bits constrained so that exactly two of them are 0s and the other two are 1s, with each of the six possible joint outcomes having probability 1/6. Jim Propp On Fri, Jan 3, 2020 at 10:46 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
I looked at the first million primes, excluding 2 and 3, to see how often a prime that's 1 mod 4 is followed by a prime that's 3 mod 4, and vice versa, as compared with the number of primes that are followed by another prime of the same 4-remainder. I noticed that there's a significant bias. A changed 4-remainder happens 281288 times in each direction. An unchanged four-remainder happens 218510 (1->3) and 218913 (3->1) times. So the total number of changes is 562576, which is well over the expected 499999.5.
Next I checked how many changes there are between a prime and the prime *two* positions later, e.g. from 5 to 11, 7 to 13, or 11 to 17. Given that the changes between consecutive primes are unexpectedly high, I thought that changes between primes 2 positions apart would have to be low. The closer the sequence is to purely alternating, 1,3,1,3,1,3,..., the closer the second changes would have to be from unchanging, 1,1,1,1,1,... and 3,3,3,3,3,....
But that's not what I saw. The second changes are also well above half a million: 511084. Likewise with the third changes: 505466. And the fourth, fifth, etc. Not until the *29th* changes, i.e. whether a prime has the same 4-remainder as the prime 29 positions after it, is there a number of changes that is less than half a million, 499209.
(Note that there are one-million-minus-n nth changes, e.g. 999971 29th changes, of which half, 499985.5 would by chance be different. Also note that if there's a bias, e.g. more primes 3 mod 4 than 1 mod 4, that ought to *reduce* the number of changes between primes n places different, for all n. In the limit, if all primes were 3 mod 4, there would be zero differences for every n.)
I'm confused as to how this is possible. Given a long sequence containing just two numbers, e.g. the first million digits of pi in binary, if adjacent terms are less likely to be identical than chance would predict, how can the terms two apart also be less likely to be identical than chance? And just how large can these biases be? Is a million-term sequence possible in which there are 900000 differences between adjacent terms and 800000 differences between terms two places apart? If not, just how large can those numbers be, and how would one design a sequence to maximize them?
Maybe it has something to do with Fourier transforms?
Would the Thue-Morse sequence be an interesting example?
As my subject line says, this is no longer about primes, but about changes in two-valued sequences in general.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
James Propp -
Keith F. Lynch -
Victor Miller