Tikalon Header Blog Logo

Partitioning

February 21, 2011

When I was a schoolboy, one way that teachers would keep students busy when they needed a break was to write a long word or a phrase on the blackboard and have the class try to make as many words as possible from the available letters.[1] There's an inverse problem in mathematics that considers how many different ways you can create a natural number by summing other natural numbers. This process, called partitioning, generates quite a few more pages of numbers than factoring, which is the process of finding what prime numbers multiply together to give you your composite number.

For example, the number six is the product of two prime numbers, 2 and 3, multiplied together; that is, 2 x 3 = 6. The number of ways you can build six by adding natural numbers takes quite a bit more page space:
6 = 6
6 = 5 + 1
6 = 4 + 2
6 = 4 + 1 + 1
6 = 3 + 3
6 = 3 + 2 + 1
6 = 3 + 1 + 1 + 1
6 = 2 + 2 + 2
6 = 2 + 2 + 1 + 1
6 = 2 + 1 + 1 + 1 + 1
6 = 1 + 1 + 1 + 1 + 1 + 1

So, there are eleven ways to sum natural numbers to get six. The number of ways to generate the natural numbers this way, starting with zero, is called the partition function and is symbolized as p(n), where n is the natural number. The partition function is the integer sequence, 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, etc.. This is sequence A000041 of the The On-Line Encyclopedia of Integer Sequences, and its low accession number underscores its fundamental nature. The graph below shows how the number of partitions grows as the natural numbers become larger. The partition of 1000 is given as
p(1000) = 24,061,467,864,032,622,473,692,149,727,991,
or about 2.4 x 1031.

Partitions for the natural numbers up to 45.

Partitions for the natural numbers up to 45. Not exactly an exponential, but quite close for large n. Rendered via Gnumeric with data from my C program.


Until recently, there was no function available for calculating values of p(n). Not surprisingly, Leonhard Euler attempted a formula, and he was successful in finding a recursion relation instead. The recursion relation gives accurate values, but it's too complicated for use on very large numbers. I've translated into C a published Basic program[2] that uses Euler's method to calculate the number of partitions for natural numbers up to 121, the limit of a long integer in C. You can view the source code here.

In 1918, the famous number theorists, G. H. Hardy and Srinivasa Ramanujan, showed that the partition function was quite closely approximated by an exponential. At the time, Ramanujan, who had a head for numbers, to say the least, noticed patterns in the partition number sequence involving the prime numbers 5, 7 and 11. These are known as Ramanujan's congruences. Robert Kanigel, a professor of science writing at MIT, has written a biography of Ramanujan, readable by non-mathematicians, that sits on my bookshelf.[3]

Hans Rademacher found an exact formula for p(n) in 1937; but it was still complicated; and, as they say, it lacked elegance, since it used a construct called a modified Bessel function of the first kind. Finally, it was announced at the end of January that Ken Ono, in collaboration with many other mathematicians, had discovered a finite formula determining the value of p(n) for positive n.[4-8] Ono is a chaired professor at the University of Wisconsin-Madison and at Emory University, and the partition team included Jan Bruinier (Technical University of Darmstadt, Germany), Amanda Folsom (Yale) and Zach Kent (Emory).[4]

This partition formula had a strange genesis in Fry's Electronics, a US West Coast electronics retailer that helped to fuel the later silicon valley hacker culture responsible for many of our computer gizmos. John Fry, the company CEO, founded and funded the American Institute of Mathematics (Palo Alto, California) in 1994. The American Institute of Mathematics became a National Science Foundation mathematical institute, one of seven, in 2002. The Institute encourages collaboration on major mathematics problems by hosting workshops on current topics, and that's how the partitioning team was started.[4]

I've written often how many discoveries have happened by accident, or by a flash of insight. A flash of insight is what led to the partition formula. As recounted in an Emory University press release, Ken Ono and Zach Kent were hiking in northern Georgia, about an hour and a half drive northeast of Emory. They started to imagine what it would be like to hike through partition numbers and realized that partition numbers had a fractal nature; that is, they had an infinitely-repeating structure.[4]. This self-similarity of fractals, as applied to partitioning, removed the problems with Rademacher's approach of nearly a hundred years ago.

The insight also confirmed Ramanujan's idea of congruences. Says Ono, "The sequences are all eventually periodic, and they repeat themselves over and over at precise intervals."[4] Another mathematician, Frank Calegari of Northwestern University, has developed a shorter proof.[7]

References:

  1. Despite persistent rumors, I'm not as old as to have been a classmate of Irving Langmuir. A more challenging word game is Euler's Day Off, for which the goal is placement of twenty-five random letters in a five-by-five grid to yield as many vertical and horizontal words as possible. Only words with three or more letters count, and the game is scored by assigning one point for each word letter.
  2. Abdulkadir Hassen and Thomas J. Osler, "Playing With Partitions On The Computer."
  3. Robert Kanigel, "The Man Who Knew Infinity: A Life of the Genius Ramanujan," (Washington Square Press, New York), 1991, 464 pages (Paperback via Amazon).
  4. Carol Clark, "New theories reveal the nature of numbers," Emory University Press Release, January 20, 2011 .
  5. Jan Hendrik Bruinier And Ken Ono, "An Algebraic Formula For The Partition Function," AIM Web Site.
  6. Amanda Folsom, Zachary A. Kent and Ken Ono, "l-Adic Properties Of The Partition Function," AIM Web Site.
  7. Frank Calegari, "A Remark On A Theorem Of Folsom, Kent, And Ono," Northeastern University.
  8. American Institute of Mathematics, What is the partition function?

Permanent Link to this article

Linked Keywords: Schoolboy; blackboard; inverse problem; mathematics; natural number; partitioning; factoring; prime numbers; composite number; Integer Sequence A000041; The On-Line Encyclopedia of Integer Sequences; Gnumeric; function; Leonhard Euler; recursion relation; G. H. Hardy; Srinivasa Ramanujan; exponential; prime number; Ramanujan's congruences; Robert Kanigel; Massachusetts Institute of Technology; MIT; Hans Rademacher; elegance; Bessel function; Ken Ono; University of Wisconsin-Madison; Emory University; Technical University of Darmstadt, Germany; Yale; Fry's Electronics; US West Coast; silicon valley; hacker culture; John Fry; CEO; American Institute of Mathematics; Palo Alto, California; National Science Foundation; Georgia; fractal; self-similarity; Frank Calegari; Northwestern University; Irving Langmuir; Euler's Day Off.

RSS Feed

Google Search


Latest Books by Dev Gualtieri

LGM by Dev Gualtieri
LGM by Dev Gualtieri, paperback LGM by Dev Gualtieri, Kindle

Thanks to Cory Doctorow of BoingBoing for his favorable review of Secret Codes!

Secret Codes & Number Games by Dev Gualtieri
Secret Codes & Number Games by Dev Gualtieri, paperback

Other Books

Other Books by Dev Gualtieri