Wednesday, December 7, 2011

Partition Numbers

I recently came across the interesting fact that a new finite method for calculating partitions has been discovered by Ken Ono with some collaborators at Emory University.

This is a fascinating development with respect to an area of number theory that seems deceptively simple yet proves to be fiendishly difficult.

Partitions simply relate to the number of ways that a particular number can be broken down. It may help to initially think of this in concrete terms.

So for example the various partitions of 4 could be likened to the manner in which we could break up arrangements of - say - four pebbles.

At one extreme we could take the four together (i.e 4).
Then we could divide the four into a group of three one left over (i.e. 3 + 1).
We could also divide into two groups of two pebbles (i.e. 2 + 2).

Then we could split one group of 2 into two single pebbles while maintaining the other group intact (i.e. 2 + 1 + 1).

Finally we could break the 4 into 4 single pebbles (i.e. 1 + 1 + 1 + 1).

So the total number of partitions of 4 is thereby demonstrated to be 5.


However whereas it is relatively easy to work out the partitions in this manner for the lower numbers it quickly becomes increasingly more difficult so that for example the number of partitions of 100 is 190569292!

In arriving at the partitions in this manner we are considering various combinations without rearrangement. So for example 3 and 1 and 1 and 3 in this interpretation represent the same partition.

Now when we allow for rearrangement, the calculation of the number of partitions is surprisingly simple.

Thus taking once again the number 4 we can include here as additional partitions 1 + 3, 1 + 1 + 2 and 1 + 2 + 1 giving eight partitions in all.

In fact the general formula for sum of partitions (with rearrangement) is 2^(n - 1).

So the answer of 8 represents the case where n = 4.

Now this result of the number of partitions (with rearrangement allowed) can be expressed as the sum 1 + 2^0 + 2^1 + 2^2 + ... + 2^(n - 2).

Interestingly - dating from Euler - the number of unrestricted partitions (without rearrangement) can be expressed as a generating function entailing the partition numbers.


One fruitful exercise would be the exploration of the relationship as between unrestricted partitions (without rearrangement) and restricted partitions (with rearrangement).

Clearly the number of unrestricted is considerably less than restricted for large n.

It struck me that Mersenne primes can be seen to represent a unique relationship with 2^(n - 1).
Thus all Mersenne primes therefore are related to (appropriate) restricted partition numbers (through the subtraction of 1).

So using the restricted formula for partition numbers i.e. 2^(n - 1) where once again rearrangement is allowed, the first Mersenne prime when n = 3 is 2^2 - 1 = 3.

The second Mersenne prime for n = 4 is 2^3 - 1 = 7. The third Mersenne prime for n = 6 is 2^5 - 1 = 7 and the fourth for n = 8 is 2^7 - 1 = 127.


It also struck me that perhaps a more general relationship involving the relationship of the prime to natural numbers also pertains to the relationship as between the unrestricted (without arrangement) and restricted partitions (with arrangement).

For example the 100th restricted partition number = 2^99 and the 100th unrestricted partition number (190569292) lies between 2^29 and 2^30. Now as the number of primes contained in the first 99 natural numbers = 25, it is tempting to believe that perhaps there is some link here with the general distribution of the prime numbers.


However for much higher values of n this apparent relationship breaks down.

In other words when we express an unrestricted partition number n, as a power of 2, the power of this number ultimately bears very little relationship with the frequency of primes up to n - 1!

However it is still tempting to surmise that - even if less apparent - that an important relationship relating to the distribution of primes (among the natural numbers) underlies the relationship of unrestricted to restricted partition numbers.

In this context, Ono and his team demonstrated a pronounced recurrence pattern to partition numbers whereby - ultimately - all terms could in principle be shown to recur at regular intervals (as multiples of the original term) in the sequence of partition numbers.

Ramanujan had already demonstrated this recurrence pattern for 5, 7 and 11. However though much less obvious this can be extended to the other partition numbers!

For example the first 30 terms of the (unrestricted) partition number sequence are

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718 and 4565.

Now if we look at 5 in this sequence we can see that a multiple of this number recurs with every 5th succeeding number. So 30 is clearly a multiple as are 135, 490, 1575 and 4565.

If we now look at 7 we can see that a multiple of this occurs with every 7th succeeding number. So 77, 490 and 2436 are all multiples of 7!

Now finally if we look at 11, we can see that a multiple of this number occurs with every 11th succeeding number. So 297 and 3718 (in this sequence) are multiples of 11!

Not surprisingly these recurrence patterns lead to the notion of the partition numbers as very interesting examples of fractals. So partition numbers in their inherent structure give rise to fractals.

From a related piece of work that I am investigating at present, I have come to the conclusion that all algebraic irrational numbers are inherently dynamic in their very structure exhibiting unique fractal patterns.

The deeper significance of this finding is that all such numbers entail the relationship as between discrete and continuous notions (that in qualitative terms are linear and circular with respect to each other).

So ultimately the very nature of partition numbers entails this same relationship!

No comments:

Post a Comment