Wednesday, 21 November 2012

Twin primes, fractals and frequencies

Following on from the previous post, here are a few thoughts about twin primes and frequencies.

I was picturing primes in terms of frequencies between 0 and 1. We can also reduce each set of twin primes to a single frequency, by looking at their product.

If we start by dividing the line into sixths, this gives us the product of 2 and 3 (which obviously can't overlap with any twin primes other than the pair 3/5, and nor can any shorter frequency reached by dividing by 2 or 3).

Now we know that neither of the frequencies for 1/5 and 1/7 will intersect the frequency for 1/6. We also know that the largest frequency which will intersect with both 1/5 and 1/7 is 1/35.

So we find the frequency 1/35 that hits both 1/5 and 1/7 (badly drawn above).

This frequency is symmetrical within the space, never intersects with the frequency 1/6 (or for 1/36).

To sieve for twin primes, we could go up through each pair of 6n+1/6n-1 numbers 11 and 13, 17 and 19, 23 and 25, and add the frequency for their product - 143, 323, 575 etc. When any part of this frequency coincides with an existing frequency, this is not a twin prime. For instance 115/575 coincides with 7/35 (both = 1/5), so we know 23 and 25 cannot be a pair of twin primes.

I like this idea in theory because it reduces the problem of twin primes to a symmetrical problem in which we are looking at a single number each time, the semi-prime product of two potential twin primes, rather than the overlapping patterns of two different patterns. We know there is an infinitude of semi-primes, though this need not mean that there is an infinitude of twin prime pairs.

You can also visualise the sieve I used on the previous post working for twin primes - that worked by dividing each number by the square of each of its factors. If we go through each 6n+1/6n-1 product, then we need to divide by the square of any two of its factors - so we get the series 1/35, 1/143, 1/323 - but for 575 we only get 575/25 = 1/23.

Each time we get a number that is smaller than the fractions/frequencies we have got before, we have reached a new pair of twin primes - because 575 only gives us 1/23 we know if can't be a twin prime pair product. Similarly 1295 (35x37) gives us 1295/37^2/49 = 25/37 and 49/37, neither of which are smaller than previous twin prime frequencies.

So there are things to like about this way of exploring twin primes - however I'm not sure it is actually much use in practise - the sieve outlined above is really laborious as it depends on factorisation, so it is only interesting as a mental representation. And I can't see any way of applying the frequency model that gives us anything we didn't already know about twin prime distribution.

The one thing that does interest me is that both the prime sieve in the previous post and the twin sieve in this post can be described in terms of a repetition of the same transform over and over. For primes you simply test the next integer by shrinking it into the space between 0 and 1. For twin primes you test the next semi-prime product of two n and n+2 numbers by shrinking into the space between 0 and 1. (I only bothered with the 6n+1 and 6n-1 numbers but a more basic algorithm would be to test every instance of n(n+2) where n is an integer and n=n+2.

I'm a bit boring about the fractal nature of prime number patterns but this brings out that fractal nature for me - as I said in the previous set this way of depicting the number line makes it look a lot more like the construction of a Cantor set.

Saturday, 10 November 2012

Prime numbers, fractals and frequencies

Prime numbers, fractals and frequencies

I’ve been thinking about numbers in terms of frequencies. This is partly inspired by Terence Tao talking abut primes in terms of frequencies, and partly because I was pondering whether there is a similarity between the Cantor Set and the pattern of primes.

To explain this, I’m going to start with a really basic look at integers, then move quickly on to primes (for which we can give a Euclid-derived proof based on frequencies) and then twin primes (for which this approach gives an interesting model to think about).

Integers as frequencies.

I will mostly be looking at the number space between 0 and 1.

If we think about frequencies that can intersect both 0 and 1, the first wave below represents a frequency of 1 (blue) then 2 (red), 3 (green), then 4 (purple). Any frequency which intersects 0 and 1 and divides the space in between into equal segments represents an integer.

(The image is a bit like a badly drawn Fourier transform – I need to read a bit more about them as they may relate more closely than I realise to what I’m talking about here).

If we didn’t know that there is a infinitude of integers, we could “prove it” thus.

Take the highest frequency you have already found (in this case 4), then extend it by one cycle. Then scale the resulting pattern down to fit the space between 0 and 1.

Yellow represents the frequency for the number 5.

You can always do this, so there is an infinitude of integers (big surprise…)

Primes as unique frequencies

Looking at the images above we can see that the wave pattern for 4 coincides with the pattern for 2 at one point – this indicates that 4 is not a prime number. Any multiple of 2 will coincide with the frequency for the number 2, any multiple of 3 will coincide with the frequency for 3 and so on.

A frequency represents a prime number if it doesn’t coincide with the frequencies for any smaller integers at any point along the central axis.

There is a useful sieve we can now use to isolate prime numbers. (I think this is loosely related to the Von Mangoldt function in the way that it treats square factors differently from unique factors….)

This process can be described in terms of pure frequencies, but to make it quicker to understand I’ll assume we can work out the factors of any integer.

Here’s the sieve:

Take each integer N > 1 and divide by the square of each of its unique factors. For instance, for 30 = 2 x 3 x 5 we end up with 30/4, 30/9, 30/25. For 20 we end up with 20/4 and 20/25. For 36 we end up with 36/36 = 1. For 31 we end up with 1/31.

Then map the results onto a line representing the number line.

2/4 = 1/2
3/9 = 1/3
4/4 = 1
5/25 = 1/5
6/4 = 3/2
6/9 = 2/3
7/49 = 1/7
8/4 = 2
9/9 = 1
10/4 = 5/2
10/25 = 2/5
11/121 = 1/11
12/9 = 4/3
12/4 = 3

This means all primes have been turned into their reciprocals. (I have a feeling that as with the Von Mangoldt function, this is related to natural logarithms, since powers of primes are reduced by this method to one less than the power of their prime factor – eg 4 becomes 1, but 8 becomes 2 – this doesn’t really matter though - the main issue is that the sieve isn't mixing up primes with powers of primes even though both have only one factor).

OK, now we are going to look at how the prime reciprocals fall between 0 and 1.

Look at these sequences
0, ½, 1
0, 1/3 2/3 1
0, 1/5, 2/5, 3/5, 4/5, 5

The furthest number to the left (the smallest fraction) is a prime reciprocal. This process gradually accumulates all the prime reciprocals in the space between 0 and ½. As we sieve upwards through the integers, the smallest fraction on the number line will always be a prime reciprocal.

Each represents a unique frequency which can start on 0 and finish on 1.

So this gives us a way to recast Euclid’s poof of the infinitude of primes.

A. Assume there is a finite number of primes.

If this is the case then above the highest prime x, all future whole numbers will create frequencies that land on points of this line which are already occupied. For instance if we add a frequency of ¼ it will land on 1/2, if we add a frequency of 1/6 it will land on 1/3, ½ and 2/3. This is because 4 is a multiple of 2 and 6 is a multiple of 2 and 3.

So given A. there must be a finite number of primes which generate the frequencies for all higher numbers.

B. It’s easy to show that for any x, there are infinitely many numbers y that have no prime factors smaller than x.

This also means that for any set of prime reciprocals up to x, there are infinitely many frequencies which don’t coincide with any of the reciprocals of multiples of the numbers up to x. The first interval on each of these frequencies will be a prime reciprocal.

So the statement B is all we need to prove that statement A is false, since the first frequency > x that doesn’t coincide with the prime frequencies up to x must be a prime frequency.

The thing I really like about this method is that it is a perfect sieve for prime numbers and it also brings out the “fractal” nature of primes, which I have mentioned before – we are basically partitioning the space between 0 and 1 over and over using the same method (given above for integers), overlaying an infinite number of frequencies into the same space - and the pattern we end up with has an infinitude of prime frequencies, each of shorter period – so thinking in terms of reciprocals gets us much closer to a Cantor Set than is obvious from considering the number line from 1 upwards.

Next I’m going to use a similar method to look at twinprimes.