Saturday, 19 November 2011

Symmetry of the prime patterns

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, 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.


(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.

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...

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.

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.

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.

Thursday, 13 January 2011

The "last prime" (aka why the twin prime proof didn't work)

It was axn from Mersenneforum who explained to me why my proof failed. He said "This is where your proof breaks down. Why "must" there be such a "last prime"?" He was quite right (I was relying on the idea that it was impossible for anyb "last prime" to cast out all remaining twin prime candidate pairs.)

Euclid's proof of the infinity of primes basically works because the symmetrical pattern built up by the primes must leave a gap for any finite set. This gap must be filled by a higher prime than the set we were considering (or a multiple of such a prime).

This works because it means that we need a higher prime to fill the gap.

In the case of twin primes, the existence of the gap in the pattern simply means that we need a higher prime, not a higher pair of twin primes.

So the proof would additionally need to show that you can't close all the gaps without moving up through the sieve to ever higher twin primes - otherwise it doesn't work.

I was grateful to him for spotting the problem and explaining it patiently.

So a failure, but I learnt something along the way, if only how difficult this problem is.

Tuesday, 11 January 2011

11# Twin Prime Symmetry

When I started looking at twin primes I got fascinated by the primorial length symmetrical patterns formed by composite numbers that are multiples of a limited set of factors (eg the pattern for multiples of 5 and 7 is symmetrical over a primorial length pattern of 210 numbers, and so is the pattern for twin prime candidates, pairs of 6N+/-1 numbers for which neither is a multiple of 5 and 7).

It can be hard to picture the symmetries I am talking about due to the length of series involved. Here is an image of the start, finish and centre of the 5/7/11 twin prime symmetry. You can see that the pairs struck out at 11 and 2299, 2101 and 209, and 2057 and 253 are the only pairs cast out by adding 11 to the sieve in this section, and that they are symmetrically arranged (as are all the other pairs cast out by 5 and 7).

Similarly you can see the pairs containing 1067 and 1243, and 1199 and 1111 are cast out by 11 and are symmetrical around the central point between 1151/1153 and 1157/1159.

Note that there is a gap of 2 spaces at the centre of the symmetry. Adding 11 to the symmetry has led to 30 pairs being cast out - 15 above the centre and 15 below.
These include the pair 11 and 13 which is of course a twin prime even though it is included in this symmetry.

135 of 385 twin pair candidates remain in this pattern from start to finish and the pattern will repeat from 2310 to 4620.

Fractal Primorial Patterns - a few basics

Lots of people have noticed primorial patterns in the primes. Just a quick note on one way of thinking about these:

Each time we go up through the sieve of Eratosthenes we get a primorial length symmetrical pattern of multiples. This pattern is endlessly repeated.

So, at a very basic level, after we have put 2 and 3 in the sieve we have the pattern

1 2 3  4   5   6
7 8 9 10 11 12

This is symmetrical (with 3 as a centre of symmetry of the first row) and will endlessly repeat.

The same is true after we sieve 5. This leaves a symmetrical pattern of 1, 7, 11, 13, 17, 19, 23, 29, which repeats in each group of 30 numbers.

If we make a sieve of 210 columns for the sieve up to 7, or 2310 columns for the sieve up to 11 we see the same kind of pattern - a symmetry of gaps which repeat on each subsequent iteration.

This process creates a fractal pattern, a overlaid pattern of self-similar elements. But it is not strictly a fractal pattern of primes or composites, because some primes fall within the pattern. It is a fractal pattern in which the gaps indicate "numbers that are not multiples of the primes {2....p}" (including 1 x 2, 1 x 3, 1 x 5 .... 1 x p).

Each time a primorial length pattern is reiterated it is also important to note what happens to each repeating gap (for instance 29, 59, 89, 119, 149, 179, 209). Within the prime pattern, the next prime p in the sieve will only remove 1/p of each particular gap (above you can see that 7 sieves out 119 from this particular set of gaps).

The overall pattern of gaps sieved out by the next prime is also symmetrical. Each pattern is symmetrical around a multiple of the previous primorial (so at the stage 7 is added, the symmetry is around multiples of 30, when 11 is added, the symmetry is around multiples of 210 etc). So numbers sieved in the first half of each iteration of the pattern are also sieved in a mirror pattern in the second half.

My failed twin prime proof relied on showing that we get the same kind of symmetrical pattern of gaps in the layout of twin prime pairs, and that the next prime only removes 2/p of the pairs in each line of gaps. This is correct but it only proves that when we sieve with any finite set of primes, there is an infinite, repeating pattern of "numbers that are not multiples of those primes".

Monday, 10 January 2011

Fractal Patterns in N-Factor Numbers

This is irrelevant to twin primes but it is interesting to observe another way in which the distribution of primes creates a fractal pattern.

The pattern of primes eg 1 x 5, 1 x 7, 1 x 11 etc is also fractally replicated in n-factor numbers. For 2-factor numbers a new pattern (congruent to the overall pattern of primes) starts at each prime  eg 5 x 5, 5 x 7, 5 x 11…  7 x 5, 7 x 7, 7 x 11…. and so on. For 3-factor numbers we have a new repeat of the prime pattern starting from each 2-factor number and so on.

Each iteration of this pattern produces a set of numbers. A set of composite numbers with up to n factors where n is finite cannot define every possible composite number. So the pattern is replicated endlessly, in another fractal pattern, creating composites of n+1, n+2 etc factors.