Primes

[naita]

@armstrongm

I have thought of that possibility as well. I am however, sure that it will in fact take place. I have written down how the absolute difference between the number of primes written as 6n+1 and 6n-1 changes. You are correct that is does swing.

The problem with saying that it might be skewed by a value is that the number of primes that can be written as 6n-1 appears to be increasing. Of course there are times where the difference narrows it fell from quite sharply at one point. But, for all the intervals I checked it never once fell below 6.

That is for the first 5154 primes.

What kind of intervals did you check? Among the first 1130 the difference is just 4. That is also the difference among the first 2134, but among the first 10 000 there does appear to be a bias in favour of 6n-1. The highest difference in the other direction is 49 for the first 6931.

[That_Don_Guy]

A brute force check shows that, in the first 102 million positive integers, 2,886,399 are primes of the form 6N-1, and 2,885,957 are primes of the form 6N+1.

[Exapno_Mapcase]

@armstrongm

Yes I agree the size of each data set will be infinitely large rather than both sets being equal to infinity.

This seems to be where you go off the rails. Although neither phrase is accurate - infinite means endless, and you can find endless examples of 6n +/- 1 - an infinite set can be sized only by whether it can be placed into a one-to-one correspondence with another infinite set. All those corresponding sets are definitionally equal in size.

Whether 6n+1 or 6n-1 is larger for any finite set is mathematically interesting, and the patterns can demonstrate some deep principles. But you can do this for many, many patterns. A well-known one is whether the cumulative total of heads or tails on a fair coin will be larger and whether and when they switch. (They do switch, and infinitely often.)

The same is true for your question. You keep saying that one form will have more primes than the other. This is not true, except for finite runs. As is true for the heads or tails question, you can have arbitrarily long runs of either one ahead, but they must end at some point, and the expected difference is always zero.

Chebyshev’s bias doesn’t apply here as it concerns a limit. Infinite sets are unlimited. In fact, over an unlimited set of numbers it behaves exactly the way the heads and tails do.

The English mathematician J.E. Littlewood proved in 1914 that any Chebyshev bias gets violated infinitely often, if you go far enough.

[That_Don_Guy]

@That_Don_Guy

A brute force check shows that, in the first 102 million positive integers, 2,886,399 are primes of the form 6N-1, and 2,885,957 are primes of the form 6N+1.

Correction: that’s the first 100.2 million positive integers, not the first 102 million.

For 102 million, there are 2,935,308 6N-1 primes, and 2,934,669 6N+1 primes.

Also, the largest gap between the number of 6N-1 primes and the number of 6N+1 primes up to that point is 1020, at 73,275,959. There does not appear to be any point where there are more 6N+1 primes than 6N-1 primes.

[Indistinguishable]

@Exapno_Mapcase

This seems to be where you go off the rails. Although neither phrase is accurate - infinite means endless, and you can find endless examples of 6n +/- 1 - an infinite set can be sized only by whether it can be placed into a one-to-one correspondence with another infinite set. All those corresponding sets are definitionally equal in size.

armstrongm seems to be asking a perfectly fine question in a basically fine way. Cardinality (i.e., isomorphism classes under arbitrarily pathological one-to-one correspondence) is not the only notion of size one might care about. After all, it is almost completely uncontroversial to say such things as, for example, “Doubling a disk’s radius changes its size”, which only make sense on other other accounts of size.

Asymptotic density is not the same thing as ordinary cardinality, but it is another perfectly good notion of size, and very often just the formal concept one is interested in. And yet another perfectly good notion of how to compare the sizes of sets A and B of integers is given by looking not simply at the asymptotic behavior of the ratio of their counts within increasing bounds, but instead, the difference of these counts. Why not?

Chebyshev’s bias doesn’t apply here as it concerns a limit.

Chebyshev’s bias is relevant to the question armstrongm is asking. It’s just about the most relevant thing imaginable! The only way it would not be relevant is if you ignored the question armstrongm was asking and substituted a different one in its place.

[That_Don_Guy]

In the first 500.1 million positive integers:

13,180,849 primes of the form 6N-1

13,179,993 primes of the form 6N+1

The largest gap is 2310, at 344,558,471

[Steve_MB]

@Dead_Cat

Anyway, with the exception of 2 or 3, this is simply a manifestation of the fact that primes cannot be a multiple of 2 or 3. All numbers not of the form 6n-1 or 6n+1 are multiples of at least one of 2 or 3 (I haven’t checked this rigorously, but 6n is clearly a multiple of 6 (and so not prime), 6n +/- 2 is clearly a multiple of 2 (and so not prime), and 6n +/- 3 is clearly a multiple of 3 (and so not prime) - no doubt a simple proof exists).

In terms of your original question, I’ve checked the primes up to 100 (which I know is next to useless in terms of a mathematical proof, I was just interested) and found they appear to be equal up to that point, so I suspect that holds forever - but I would like to see a proof of it.

You already provided a proof, albeit one that glides over the first step:

1. All integers higher than 3 are expressible as 6n-2, 6n-1, 6n, 6n+1, 6n+2, or 6n+3 where n is some positive integer, because 6n-3, 6n-4, etc or 6n+4, 6n+5, etc can be converted to one of these forms by adding or subtracting a multiple of 6).

2. Integers expressed as 6n or 6n+3 are not prime, because they are divisible by 3.

3. Integers expressed as 6n-2 or 6n+2 are not prime, because they are divisible by 2. (Actually, this also covers 6n, but that’s already taken care of.)

4. Ergo, all primes higher than 3 are in the form 6n-1 or 6n+1

[Indistinguishable]

@armstrongm

“In general, if 0 < a, b < q are integers, (a, q) = (b, q) = 1, a is a quadratic residue, b is a quadratic nonresidue mod q, then π(x; q, b) > π(x; q, a) occurs more often than not” if I understand it correctly that part of the equation has been proved through the Riemann Hypothesis and that in turn would make the statement that having more primes in the form 6n-1 than 6n+1 is to be expected then?

This is presumably a reference to the Rubinstein-Sarnak result. This is conditional on both the Riemann Hypothesis (which has not been proven, though any violation of it would be very unexpected!) and another unproven assumption of similar status.

But, yes, everyone basically expects that for “most” size limits, you should expect to find more primes of the form 6n - 1 than of the form 6n + 1 within those limits. More precisely, the Rubinstein-Sarnak results says, giving each size limit n a weight of 1/n, the weighted average of the size limits below m for which this is true tends to a constant as m grows large, and that constant is about 99.90%.

That having been said, there are also infinitely many size limits for which this is false (accounting for the other 0.10% of the time). The first example is at size limit 608981813029.

[Indistinguishable]

@Indistinguishable

But, yes, everyone basically expects that for “most” size limits, you should expect to find more primes of the form 6n - 1 than of the form 6n + 1 within those limits. More precisely, the Rubinstein-Sarnak results says, giving each size limit n a weight of 1/n, the weighted proportion of the size limits below m for which this is true tends to a constant as m grows large, and that constant is about 99.90%.

Wording clarified in bold.

Another way of putting it would be, supposing we increased the size limits uniformly in their number of digits (so the limits themselves grew exponentially); then 99.90% of the time, more primes below the limit are of the form 6n - 1 than of the form 6n + 1.

[That_Don_Guy]

I’ll stop at 1.0002 billion:

25,429,633 primes of the form 6N-1

25,427,503 primes of the form 6N+1

The largest gap is 2553 at 973,043,663

[ZenBeam]

@Indistinguishable

Another way of putting it would be, supposing we increased the size limits uniformly in their number of digits (so the limits themselves grew exponentially); then 99.90% of the time, more primes below the limit are of the form 6n - 1 than of the form 6n + 1.

That Don Guy’s calculations for primes up to 500 million or up to a billion found ratios of the two forms of 0.999935 and 0.999916 respectively. That’s a different calculation than what you have, but are the two numbers numerically related?

I’d expect that if one of them has a value < 1, the other one likely would as well, but your value is about ten times farther from 1 than That Don Guy’s. Is it just that 1 billion is too small, or will his value always be different?

[Exapno_Mapcase]

@Indistinguishable

armstrongm seems to be asking a perfectly fine question in a basically fine way. Cardinality (i.e., isomorphism classes under arbitrarily pathological one-to-one correspondence) is not the only notion of size one might care about. After all, it is almost completely uncontroversial to say such things as, for example, “Doubling a disk’s radius changes its size”, which only make sense on other other accounts of size.

Asymptotic density is not the same thing as ordinary cardinality, but it is another perfectly good notion of size, and very often just the formal concept one is interested in. And yet another perfectly good notion of how to compare the sizes of sets A and B of integers is given by looking not simply at the asymptotic behavior of the ratio of their counts within increasing bounds, but instead, the difference of these counts. Why not?
Chebyshev’s bias is relevant to the question armstrongm is asking. It’s just about the most relevant thing imaginable! The only way it would not be relevant is if you ignored the question armstrongm was asking and substituted a different one in its place.

I’m looking at the question in the OP. “But can more primes be expressed as 6n+1 than 6n-1 or is the number of primes that can be expressed as 6n+1 equal to the number of primes that can be expressed as 6n-1?”

I’m not saying that the differences at any point are not interesting. I’m saying that those are a different question from the one I’m reading. And also a different one than the OP who says that density is not his interest is asking. And one that Great Antibob seemed to answer, giving the same answer as mine with a reference to a proven theorem. (Yes, redundant technically but not in colloquial English.)

Could you please clarify? I’m seriously missing your point.

[armstrongm]

@Exapno_Mapcase

Since the two sets are countably infinite, they can be placed into one-to-one correspondence. So they are exactly equal.

The primes themselves can be placed into one-to-one correspondence with the integers, so they are also exactly equal. Yet common sense would tell us that the primes are fewer than the integers everywhere you can possibly look. That’s why common sense is a terrible tool to use with math.

You might like to think that they are equal at infinity wouldn’t you? I certainly would it creates a sense of order. Yet maths definitely does not always create order where there should be. Take this example. You might think that the number of primes that can be expressed as 4n+1 is the same as that that can be expressed as 4n-1. But that is an incorrect assumption. The data people have gathered tell us otherwise.

Two sets of infinity are not always equal. Some infinities are larger. In any event each, if I understand you correctly, should not be equal to infinity. They should equal infinity divided by two. So therefore to attack or defend your argument as I understand it is to answer the question, “What is infinity divided by two?”

[armstrongm]

@naita

What kind of intervals did you check? Among the first 1130 the difference is just 4. That is also the difference among the first 2134, but among the first 10 000 there does appear to be a bias in favour of 6n-1. The highest difference in the other direction is 49 for the first 6931.

My intervals are

0-300
0-400
0-500
0-600
. . .
Up until
5154

[Great_Antibob]

@armstrongm

Two sets of infinity are not always equal. Some infinities are larger. In any event each, if I understand you correctly, should not be equal to infinity. They should equal infinity divided by two. So therefore to attack or defend your argument as I understand it is to answer the question, “What is infinity divided by two?”

I’ll wade back into this one, though it’s a digression from the original question, which appears to be answered pretty thoroughly now.

It’s not as simple as “infinity divided by two”. It never really is when infinitely large sets are involved.

But in this particular case, both sets are actually infinite (the infinitude of the sets of primes of the form 6k-1 and 6k+1 were proven many, many years ago now) and have the same cardinality. In as conventional a sense as we have in math, that does make them the same “size”. Which is the same cardinality as the whole set of integers. So, both sets, though subsets of the integers, are the same “size” so to speak as all the integers and as each other. Infinitely large sets are funny like that.

ETA: Yes, when you stop at some finite N and examine all primes less than N, one set will be larger than another. And, as Indistinguishable showed, it tends to be the 6k-1 set that’s larger in this case. But that analysis goes out the window when you try to generalize to the set of ALL primes. You can no longer say one set is “larger” than the other when you take the entire set.

[armstrongm]

@Exapno_Mapcase

This seems to be where you go off the rails. Although neither phrase is accurate - infinite means endless, and you can find endless examples of 6n +/- 1 - an infinite set can be sized only by whether it can be placed into a one-to-one correspondence with another infinite set. All those corresponding sets are definitionally equal in size.

Whether 6n+1 or 6n-1 is larger for any finite set is mathematically interesting, and the patterns can demonstrate some deep principles. But you can do this for many, many patterns. A well-known one is whether the cumulative total of heads or tails on a fair coin will be larger and whether and when they switch. (They do switch, and infinitely often.)

The same is true for your question. You keep saying that one form will have more primes than the other. This is not true, except for finite runs. As is true for the heads or tails question, you can have arbitrarily long runs of either one ahead, but they must end at some point, and the expected difference is always zero.

Chebyshev’s bias doesn’t apply here as it concerns a limit. Infinite sets are unlimited. In fact, over an unlimited set of numbers it behaves exactly the way the heads and tails do.

You seem to be nit picking and arguing our definitions of different things rather than the data. I am not going to debate the difference between infinitely large and infinity with you.

But seeing as you brought it up perhaps you are the right man to answer this question for me. If you are saying that they are spread 50% each. Then for you to contemplate what the size of each data set is you need to tell me what infinity divided by two is.

Infinity is a limit it doesn’t exist in the real world. Yes, before you find the flaw in that statement, neither do irrational numbers technically maybe. But the point is that when I say infinity I am that is the limit that will be reached by certain sequences such as the sum of all natural numbers. So what is this limit over two? That division is significant. Therefore in order to get around this I say infinitely large. The use of that phrase is deliberate and wasn’t meant to be a problem.

Neither does the theorem of Dirchlet I don’t think I say think because to be honest I don’t know its an opinion.

Chebyschev’s bias is interesting though. It deals with primes of 4n+1 and 4n+3. This is interesting and shows they aren’t equal. In fact there is a an interesting link and I am fairly confident its proof through the Riemann hypothesis, assuming that is true, is valid and applies here. It is the most valid thing that I have come across and seems to validate that more primes will be written as 6n-1 than 6n+1.

[armstrongm]

@Indistinguishable

This is presumably a reference to the Rubinstein-Sarnak result. This is conditional on both the Riemann Hypothesis (which has not been proven, though any violation of it would be very unexpected!) and another unproven assumption of similar status.

But, yes, everyone basically expects that for “most” size limits, you should expect to find more primes of the form 6n - 1 than of the form 6n + 1 within those limits. More precisely, the Rubinstein-Sarnak results says, giving each size limit n a weight of 1/n, the weighted average of the size limits below m for which this is true tends to a constant as m grows large, and that constant is about 99.90%.

That having been said, there are also infinitely many size limits for which this is false (accounting for the other 0.10% of the time). The first example is at size limit 608981813029.

This is not your explanation rather my lack of understanding of everything that was said. Let me be clear there should be more 6n-1 than 6n+1 primes 99.9% of the time?

[Great_Antibob]

@armstrongm

Chebyschev’s bias is interesting though. It deals with primes of 4n+1 and 4n+3. This is interesting and shows they aren’t equal. In fact there is a an interesting link and I am fairly confident its proof through the Riemann hypothesis, assuming that is true, is valid and applies here. It is the most valid thing that I have come across and seems to validate that more primes will be written as 6n-1 than 6n+1.

Again, this is true with caveats. For any given N, primes less than N of the form 6n-1 will outnumber primes of the form 6n+1 for most choices of N. But not for all choices of N.

The populations do “flip” for certain values of N.

[armstrongm]

@Exapno_Mapcase

I’m looking at the question in the OP. “But can more primes be expressed as 6n+1 than 6n-1 or is the number of primes that can be expressed as 6n+1 equal to the number of primes that can be expressed as 6n-1?”

I’m not saying that the differences at any point are not interesting. I’m saying that those are a different question from the one I’m reading. And also a different one than the OP who says that density is not his interest is asking. And one that Great Antibob seemed to answer, giving the same answer as mine with a reference to a proven theorem. (Yes, redundant technically but not in colloquial English.)

Could you please clarify? I’m seriously missing your point.

Yes this is my fault I did my original data in a silly way. The data I had said that there were more 6n-1 primes than 6n+1 primes. I just misinterpreted it. I apologise for the confusion.

[armstrongm]

@Great_Antibob

I’ll wade back into this one, though it’s a digression from the original question, which appears to be answered pretty thoroughly now.

It’s not as simple as “infinity divided by two”. It never really is when infinitely large sets are involved.

But in this particular case, both sets are actually infinite (the infinitude of the sets of primes of the form 6k-1 and 6k+1 were proven many, many years ago now) and have the same cardinality. In as conventional a sense as we have in math, that does make them the same “size”. Which is the same cardinality as the whole set of integers. So, both sets, though subsets of the integers, are the same “size” so to speak as all the integers and as each other. Infinitely large sets are funny like that.

ETA: Yes, when you stop at some finite N and examine all primes less than N, one set will be larger than another. And, as Indistinguishable showed, it tends to be the 6k-1 set that’s larger in this case. But that analysis goes out the window when you try to generalize to the set of ALL primes. You can no longer say one set is “larger” than the other when you take the entire set.

The point is that I am thoroughly convinced that at infinity they will not be the same size. It is so unlikely. From what I understand there is a 0.1% chance of it happening. NASA got man to the moon on a 99.9% chance. Through chebyschev’s bias it must be the case that for values there are more primes that are written as 6n-1. You keep saying at infinity they will be equal. But that’s a bit like saying when we reach the each of the universe this happens. It’s so far beyond any number you can think of that it seems almost pointless.

I’m not attacking you at all its very interesting. But I cant see it happening I have yet to hear an argument that doesn’t support the idea that at infinity even or at the very least incredibly large values there aren’t primes more primes than can be written as 6n-1 than 6n+1.