Just a quick note on the implications of the K numbers I talked about in my last post. (Edit - since deleted since there were a few issues with the approach - will try to come back and clarify this post at some point...)
In each primorial 0-30, 0-210, 0-2310 etc, there is a limited symmetrical pattern. Up to P#, K numbers (numbers that are either prime or don't have any factors or P or below) on the "way up" are composite, but K numbers on the "way down" (eg the remainder when a K number is subtracted from P#) are prime if they are below P^2. (If these remainders are over P^2 then they are either prime or they have a different set of composite factors to the K number.)
Not a very satisfying symmetry, granted, but it does explain why the assymmetrical prime patterns have such a symmetrical "feel". What we are actually seeing is a fractal, assymmetrical pattern gradually develop. But for every region P^2 to Pn^2 where Pn is the next prime after P, there is a symmetry with the region (Pn# - Pn^2) to (Pn# - P^2) with primes in the former being mirrored by Kpn numbers (numbers that don't have factors of Pn or below) in the latter.
Saturday 19 November 2011
Saturday 5 November 2011
From Euclid to the infinitude of 6n+1 and 6n-1 primes.
I said I'd look at the logic of assuming that there is an infinite number of primes in each axis of the n-factor grid used in previous posts (eg primes in the form of 6n+1 and in the form 6n-1). I'm not sure how to prove this properly. Here's how far I got so far, if anyone can see how to fill in the last step I'd be pleased.
Euclid: Assume X is the highest prime number. Multiply all primes up to X together then add one to the resulting primorial. The result must be either a prime or the product of primes higher than X.
OK, so this number X#+1 is clearly of the form 6n+1 since the first two primes are 2*3. However we haven't yet proved that there is an infinite number of 6n+1 primes, since, if it is a product of primes higher than X, those primes could be 6n-1 numbers (since an even number of 6n-1 numbers multiplied will give us a 6n+1 number).
So let's do something slightly different to Euclid. Assume X is the highest prime number. Multiply all primes up to X together then subtract one from the resulting primorial. The result must be either a prime or the product of primes higher than X. If it is a prime it is a 6n-1 prime. If it is the product of primes higher than X, then at least one of them must be a 6n-1 number, since any number of 6n+1 numbers multiplied together will produce another 6n+1 number.
So that proves there is an infinite number of 6n-1 numbers, but still not that there is an infinite number of 6n+1 numbers.
Intuitively it seems there must be since each number in the Sieve of Eratosthenes will sieve out a fairly even selection of 6n+1 and 6n-1 numbers, but that's only a guess really.
Of course the proof above would also show that there is an infinite number of 6n+1 numbers (since you need a 6n+1 number and a 6n-1 number to multiply together to get a new 6n-1 number) - but only if we could assume that X#-1 wouldn't always be a new 6n-1 prime and would sometimes be a product of other primes instead. So it's not quite there. (Edit - on returning to this post somewhat later on I realise that this paragraph is gobbledygook since a 6n-1 number could always be the product of an odd number of 6n-1 primes, but it doesn't really matter as either way the inifinitude of 6n+1 primes isn't proven using this approach)
I'm probably being stupid and there is probably a proof out there somewhere. (Edit: I think it is implied by Dirichlet's Theorem, so has been proved - I just want to see a proof I can get my head around a bit more easily).
Edit: For the infinitude of 6n+1 primes I'm tempted to suggest using the fraction Euler used (below) when he proved its inverse was equivalent to the sum of the harmonic series and thus diverged. He did this over all prime numbers, but it is clear that within the 6n+1 axis, the same maths is at work, since 4/5 of the numbers are not multiples of 5, 6/7 aren't multiples of 7, 10/11 aren't multiples of 11 and so on. I don't know how to express that idea more rigorously though.
1*2*4*6*….(p-1)
2*3*5*7*……p
Euclid: Assume X is the highest prime number. Multiply all primes up to X together then add one to the resulting primorial. The result must be either a prime or the product of primes higher than X.
OK, so this number X#+1 is clearly of the form 6n+1 since the first two primes are 2*3. However we haven't yet proved that there is an infinite number of 6n+1 primes, since, if it is a product of primes higher than X, those primes could be 6n-1 numbers (since an even number of 6n-1 numbers multiplied will give us a 6n+1 number).
So let's do something slightly different to Euclid. Assume X is the highest prime number. Multiply all primes up to X together then subtract one from the resulting primorial. The result must be either a prime or the product of primes higher than X. If it is a prime it is a 6n-1 prime. If it is the product of primes higher than X, then at least one of them must be a 6n-1 number, since any number of 6n+1 numbers multiplied together will produce another 6n+1 number.
So that proves there is an infinite number of 6n-1 numbers, but still not that there is an infinite number of 6n+1 numbers.
Intuitively it seems there must be since each number in the Sieve of Eratosthenes will sieve out a fairly even selection of 6n+1 and 6n-1 numbers, but that's only a guess really.
Of course the proof above would also show that there is an infinite number of 6n+1 numbers (since you need a 6n+1 number and a 6n-1 number to multiply together to get a new 6n-1 number) - but only if we could assume that X#-1 wouldn't always be a new 6n-1 prime and would sometimes be a product of other primes instead. So it's not quite there. (Edit - on returning to this post somewhat later on I realise that this paragraph is gobbledygook since a 6n-1 number could always be the product of an odd number of 6n-1 primes, but it doesn't really matter as either way the inifinitude of 6n+1 primes isn't proven using this approach)
I'm probably being stupid and there is probably a proof out there somewhere. (Edit: I think it is implied by Dirichlet's Theorem, so has been proved - I just want to see a proof I can get my head around a bit more easily).
Edit: For the infinitude of 6n+1 primes I'm tempted to suggest using the fraction Euler used (below) when he proved its inverse was equivalent to the sum of the harmonic series and thus diverged. He did this over all prime numbers, but it is clear that within the 6n+1 axis, the same maths is at work, since 4/5 of the numbers are not multiples of 5, 6/7 aren't multiples of 7, 10/11 aren't multiples of 11 and so on. I don't know how to express that idea more rigorously though.
1*2*4*6*….(p-1)
2*3*5*7*……p
(Edit: What I was getting at here was something like this bit from Wikipedia: "Stronger forms of Dirichlet's theorem state that, for any arithmetic progression, the sum of the reciprocals the prime numbers in the progression diverges, and that different
arithmetic progressions with the same modulus have approximately the
same proportions of primes." - that seems intuitively correct to me and would answer the question posed above, I'll see if I can find any proofs that are easy enough for me to follow).
Semi-prime distribution on the n-factor grid
Finally, I want to take a look at what we can know about the distribution of semi-primes on this grid. Here it is again as a reminder, with the primes coloured pink and the semi-primes yellow (other colours indicate numbers with more than 2 prime factors).
So what do we know about the primes and semi-primes on this grid.
1. There is an infinite number of primes in the central axes. I think Euclid's proof of the infinitude of primes might also suggest that there is an infinite number in each of these axes but I'm not 100% sure of that - I'll assume it is true for now and try running through the logic in another post.
2. Either way there is an infinite number of semi-primes on the grid. (This is obvious anyway, since each prime number will generate an infinite chain of semi-primes when multiplied by each of the infinite chain of primes.
3. Each prime on the central axes will generate an infinite, intermittent horizontal or vertical line of semi-primes stretching across the grid. This will hit an infinite number of diagonals.
What we don't know:
1. Is there an infinite number of semi-primes on the twin prime diagonal? If so the twin prime conjecture is true. The observations above suggest why this might be true, but they aren't proof of it.
2. Is there an infinite number of semi-primes on every infinite diagonal on the grid? If so, Polignac's conjecture is true (this refers to the larger grid as seen in the second and third image on this page).
3. Is it impossible to take a diagonal from one axis to the other (or from an axis to the diagonal NW-SE boundary - see previous post for a clearer explanation) without hitting a semi-prime. If so the Goldbach conjecture is true.
So what do we know about the primes and semi-primes on this grid.
1. There is an infinite number of primes in the central axes. I think Euclid's proof of the infinitude of primes might also suggest that there is an infinite number in each of these axes but I'm not 100% sure of that - I'll assume it is true for now and try running through the logic in another post.
2. Either way there is an infinite number of semi-primes on the grid. (This is obvious anyway, since each prime number will generate an infinite chain of semi-primes when multiplied by each of the infinite chain of primes.
3. Each prime on the central axes will generate an infinite, intermittent horizontal or vertical line of semi-primes stretching across the grid. This will hit an infinite number of diagonals.
What we don't know:
1. Is there an infinite number of semi-primes on the twin prime diagonal? If so the twin prime conjecture is true. The observations above suggest why this might be true, but they aren't proof of it.
2. Is there an infinite number of semi-primes on every infinite diagonal on the grid? If so, Polignac's conjecture is true (this refers to the larger grid as seen in the second and third image on this page).
3. Is it impossible to take a diagonal from one axis to the other (or from an axis to the diagonal NW-SE boundary - see previous post for a clearer explanation) without hitting a semi-prime. If so the Goldbach conjecture is true.
The n-factor grid: twin primes, Polignac primes and the Goldbach conjecture.
So, having introduced the grid of n-factor composite numbers in the previous post, how does this help us visualise prime problems?
First, let's look at twin primes. If we are looking for twin primes, we need to look at the pairs of numbers 6k-1 and 6k+1. In this image, the highlighted boxes contain the products of possible twin prime candidates (5*7, 11*13 etc). This diagonal, continued to infinity would contain all such products.
The reason for looking at the products of these numbers is this: where the numbers along this diagonal are semi-prime (yellow), the two factors on the horizontal axes must be twin primes. This is kind of obvious, since only the prime numbers on the central axes will produce a semi-prime when multiplied together. But it does provide some visual explanation of why you are likely to get a proportion of primes along a diagonal of this grid. Put in basic terms, it is obviously going to be pretty hard (especially at low numbers) to draw a diagonal that doesn't hit one of the vertical or horizontal stripes of semi-primes. It also doesn't suffer from the same problem as the original grid I was using as it does continue to distinguish primes from semi-primes and other composites.
Next, we can clearly see on this grid why, as we go up through the Sieve of Eratosthenes, the prime N will remove a maximum of 2/N of remaining twin prime candidates: Since the diagonal will pass through 1/N multiples of N on the horizonal axis and 1/N on the vertical axis, it will encounter up to 2/N multiples of N altogether*.
The twin prime conjecture is true if there is an infinite number of semi-primes on this diagonal, continued to infinity. (I'll talk about this a bit more on the next post).
Incidentally, the other diagonals on the grid all relate to other prime problems. In this diagram, the diagonals highlighted show the products of prime pairs with larger gaps, cousin primes (N, N+4), sexy primes (N, N+6) and some larger examples. If Polignac's conjecture that "for any positive even number n , there are infinitely many prime gaps of size n" is true, then any diagonal on this grid (continued to infinity) contains an infinite number of semi-primes. (Only top right is coloured).
On the grid below, the highlighted diagonals relate to the Goldbach conjecture. In this case the chains are finite - each chain contains all the pairs of 6n+/-1 numbers that could be added together to get a particular sum, for instance for 78 the potential pairs are 73+5, 67+11, 61+17....65+13, 71+7. If each diagonal that stretches from one axis to the other (or from an axis to the diagonal boundary of square numbers to the bottom left) contains at least one semi-prime then the Goldbach conjecture is true.
Edit: I later realise that while this is true, it would demonstrate a slightly stronger conjecture than Goldbach, since Goldbach would allow pairs of primes where one of the pair is 3 and the grid above ignores products of 3.
* 2/N is a maximum because, as previously noted, the first instance of N is not a composite so may be part of a twin prime pair. Also, for higher gaps between the primes, the maths changes slightly - for instance for primes separated by a gap of 30, the number 5 will only remove 1/5 of candidate pairs, since the diagonal will hit the 5-multiples on the horizontal and vertical axis on the same square.
Incidentally this post is a bit wrong - I should have been clearer that the prime N will remove a maximum of 2/N of remaining twin prime candidates in any infinitely repeating chain of numbers separated by the same interval - so for instance after we have sieved to 11, we know that the pair 101/103 is a twin prime. Within any higher primorial length pattern, there will be repetitions of this "twin prime candidate" gap, for instance in 13#, the gap repeats at 2310+101/3, 4620+101/3, 6930+101/3 and on to infinity. Some of these candidates will be eliminated by higher primes, but the prime P will only eliminate 2/P of all instances. All a bit more complicated then...
First, let's look at twin primes. If we are looking for twin primes, we need to look at the pairs of numbers 6k-1 and 6k+1. In this image, the highlighted boxes contain the products of possible twin prime candidates (5*7, 11*13 etc). This diagonal, continued to infinity would contain all such products.
The reason for looking at the products of these numbers is this: where the numbers along this diagonal are semi-prime (yellow), the two factors on the horizontal axes must be twin primes. This is kind of obvious, since only the prime numbers on the central axes will produce a semi-prime when multiplied together. But it does provide some visual explanation of why you are likely to get a proportion of primes along a diagonal of this grid. Put in basic terms, it is obviously going to be pretty hard (especially at low numbers) to draw a diagonal that doesn't hit one of the vertical or horizontal stripes of semi-primes. It also doesn't suffer from the same problem as the original grid I was using as it does continue to distinguish primes from semi-primes and other composites.
Next, we can clearly see on this grid why, as we go up through the Sieve of Eratosthenes, the prime N will remove a maximum of 2/N of remaining twin prime candidates: Since the diagonal will pass through 1/N multiples of N on the horizonal axis and 1/N on the vertical axis, it will encounter up to 2/N multiples of N altogether*.
The twin prime conjecture is true if there is an infinite number of semi-primes on this diagonal, continued to infinity. (I'll talk about this a bit more on the next post).
Incidentally, the other diagonals on the grid all relate to other prime problems. In this diagram, the diagonals highlighted show the products of prime pairs with larger gaps, cousin primes (N, N+4), sexy primes (N, N+6) and some larger examples. If Polignac's conjecture that "for any positive even number n , there are infinitely many prime gaps of size n" is true, then any diagonal on this grid (continued to infinity) contains an infinite number of semi-primes. (Only top right is coloured).
Edit: I later realise that while this is true, it would demonstrate a slightly stronger conjecture than Goldbach, since Goldbach would allow pairs of primes where one of the pair is 3 and the grid above ignores products of 3.
* 2/N is a maximum because, as previously noted, the first instance of N is not a composite so may be part of a twin prime pair. Also, for higher gaps between the primes, the maths changes slightly - for instance for primes separated by a gap of 30, the number 5 will only remove 1/5 of candidate pairs, since the diagonal will hit the 5-multiples on the horizontal and vertical axis on the same square.
Incidentally this post is a bit wrong - I should have been clearer that the prime N will remove a maximum of 2/N of remaining twin prime candidates in any infinitely repeating chain of numbers separated by the same interval - so for instance after we have sieved to 11, we know that the pair 101/103 is a twin prime. Within any higher primorial length pattern, there will be repetitions of this "twin prime candidate" gap, for instance in 13#, the gap repeats at 2310+101/3, 4620+101/3, 6930+101/3 and on to infinity. Some of these candidates will be eliminated by higher primes, but the prime P will only eliminate 2/P of all instances. All a bit more complicated then...
The grid of n-factor numbers
So in the previous post I showed a grid of composite numbers of the form 6n+/-1, and also looked at the problem of using it to look at prime patterns.
What I tried next isn't a complete solution to this problem, but I think it brings a bit more clarity to the grid and makes it more visually useful. Instead of the slightly confusing overlaying of rectangles of n-multiples, I used a different colour scheme, and graded the numbers according to how many factors they have. In this image, prime numbers are pink, semi-primes (numbers with 2 factors such as 25, 35, 49, 55 etc) are yellow, 3-factor numbers are green, 4-factor numbers are blue, 5-factor numbers are red, and the one 6-factor number (21875) is purple. (I've only shown the (6n+1)(6n-1) region, but this pattern would extend over the whole grid.)
We still see a similarly fractal pattern starting to emerge. In the next post I will talk about the distribution of semi-primes on this grid, and what we can know about how it will develop.
What I tried next isn't a complete solution to this problem, but I think it brings a bit more clarity to the grid and makes it more visually useful. Instead of the slightly confusing overlaying of rectangles of n-multiples, I used a different colour scheme, and graded the numbers according to how many factors they have. In this image, prime numbers are pink, semi-primes (numbers with 2 factors such as 25, 35, 49, 55 etc) are yellow, 3-factor numbers are green, 4-factor numbers are blue, 5-factor numbers are red, and the one 6-factor number (21875) is purple. (I've only shown the (6n+1)(6n-1) region, but this pattern would extend over the whole grid.)
We still see a similarly fractal pattern starting to emerge. In the next post I will talk about the distribution of semi-primes on this grid, and what we can know about how it will develop.
The composite 6n+1/6m-1 grid
To help look at prime patterns, I used a spreadsheet to create a grid of multiples of numbers in the form (6n+1) and (6n-1). The reason for this is that all numbers of this form are either prime numbers or multiples of smaller primes of the same form. So for instance, the first few composite numbers of this form are 25 (5*5), 35 (5*7), 49 (7*7), 55 (5*11) and so on. At it's most basic the grid looks like this.
If you imagine this continuing to the right and upwards, it is a small part of the grid of all numbers generated by multiplying together 6n+1 numbers (on the axis to the South and East) and 6n-1 numbers (on the axis to the North and West). The North-East quadrant contains numbers that are of the form (6n+1)(6m-1), the North-West contains (6n-1)(6m-1), the South-East contains those of the form (6n+1)(6m+1). (The whole pattern would mirror across the bottom diagonal row, which contains all the square numbers of this form, thus I leave it blank for clarity).
Next I coloured in stripes of composites with factors of n. So, for instance, I coloured in multiples of 5 yellow.
Overlaying multiples of 7 (brown), 11 (pink) and 13 (blue), you start to see the rather obvious fractal style pattern, a bit like a Sierpinski carpet (except we are eliminating squares of growing size within an infinite plain), but with the centre of the squares off-centre:
(You'll see that where a later prime is on the same line, I've overlayed the colour, so the 55 line is coloured pink for 11, not yellow for 5).
Here is a view of a larger section, also completed up to the multiples of 13.
And one more long shot, to show how the grid extends.
Note that all numbers that appear in the composite area (eg not the central axes) will also appear later on in those central axes as they are higher numbers in the form (6n+/-1). Also numbers with 3 or more factors will appear several times in the composite area, for instance 245 appears as 7*35 as well as 5*49. An infinitely extended version of the grid would (in theory) contain all composite numbers of the form (6n+/-1) as well as all prime numbers of this form (restricted to the central axes).
The problem with the composite 6n+/-1 grid
This grid gives an interesting visual way to observe the build up of symmetrical primorial patterns - basically you go up through the Sieve of Eratosthenes and gradually colour in the map and the patterns that build up are the same patterns I (and others) have observed in the distribution of composite numbers (and, consequently, the remaining numbers that are still "prime candidates", in other words numbers that are either prime or multiples of higher primes).
However there is a problem, which is that the grid of "composite numbers", as it expands, will also include the prime numbers in the central axes. So, when we go on to colour in multiples of 17, the 17 square will be coloured in as though it is a composite. This is one of the basic problems of sieve theory (as I understand it) as this sieve fails to clearly distinguish primes. Extended to infinity, the entire grid would be coloured in as "composite", even though there are an infinite number of primes.
(This is a serious problem for any attempt to understand twin primes and other related problems using these primorial patterns. It is clear that any set of prime numbers up to Pn will leave an infinitely repeating symmetrical pattern of "prime candidates" in subsequent Pn# length primorials. But we aren't actually looking for "prime candidates". We are looking those candidates that get sieved out as "composite" even though they are actually one of a pair of twin primes).
In the next post I will look at a slightly different grid.
If you imagine this continuing to the right and upwards, it is a small part of the grid of all numbers generated by multiplying together 6n+1 numbers (on the axis to the South and East) and 6n-1 numbers (on the axis to the North and West). The North-East quadrant contains numbers that are of the form (6n+1)(6m-1), the North-West contains (6n-1)(6m-1), the South-East contains those of the form (6n+1)(6m+1). (The whole pattern would mirror across the bottom diagonal row, which contains all the square numbers of this form, thus I leave it blank for clarity).
Next I coloured in stripes of composites with factors of n. So, for instance, I coloured in multiples of 5 yellow.
Here is a view of a larger section, also completed up to the multiples of 13.
And one more long shot, to show how the grid extends.
Note that all numbers that appear in the composite area (eg not the central axes) will also appear later on in those central axes as they are higher numbers in the form (6n+/-1). Also numbers with 3 or more factors will appear several times in the composite area, for instance 245 appears as 7*35 as well as 5*49. An infinitely extended version of the grid would (in theory) contain all composite numbers of the form (6n+/-1) as well as all prime numbers of this form (restricted to the central axes).
The problem with the composite 6n+/-1 grid
This grid gives an interesting visual way to observe the build up of symmetrical primorial patterns - basically you go up through the Sieve of Eratosthenes and gradually colour in the map and the patterns that build up are the same patterns I (and others) have observed in the distribution of composite numbers (and, consequently, the remaining numbers that are still "prime candidates", in other words numbers that are either prime or multiples of higher primes).
However there is a problem, which is that the grid of "composite numbers", as it expands, will also include the prime numbers in the central axes. So, when we go on to colour in multiples of 17, the 17 square will be coloured in as though it is a composite. This is one of the basic problems of sieve theory (as I understand it) as this sieve fails to clearly distinguish primes. Extended to infinity, the entire grid would be coloured in as "composite", even though there are an infinite number of primes.
(This is a serious problem for any attempt to understand twin primes and other related problems using these primorial patterns. It is clear that any set of prime numbers up to Pn will leave an infinitely repeating symmetrical pattern of "prime candidates" in subsequent Pn# length primorials. But we aren't actually looking for "prime candidates". We are looking those candidates that get sieved out as "composite" even though they are actually one of a pair of twin primes).
In the next post I will look at a slightly different grid.
Mea Culpa
I had a bit of a messianic moment in January when I thought I had proved the twin prime conjecture. Very silly of me, and someone from the Mersenne forum patiently told me where I was wrong. On further searching I also see plenty of other people have noticed the primorial patterns that underlied the attempt.
So now, in a more humble frame of mind I've returned to thinking about this problem and the way it relates to a few other issues, so I will be making a few posts to make observations, without any claim to be doing anything more than keeping a record of my thoughts.
I'll leave the earlier posts up as a useful reminder of my own hubris.
So now, in a more humble frame of mind I've returned to thinking about this problem and the way it relates to a few other issues, so I will be making a few posts to make observations, without any claim to be doing anything more than keeping a record of my thoughts.
I'll leave the earlier posts up as a useful reminder of my own hubris.