September 30, 2018. With a little experimental mathematics, you too can arrive at the insights of Ramanujan! A simple program in Haskell for discovering partition identities.

### Introduction

Prerequisites: basic number theory, some exposure to Haskell.

The Rogers-Ramanujan identities relate different ways of splitting natural numbers into smaller parts. I will state a precise version below, but before that, I’ll introduce some basic notions. The purpose of this post will not be to prove these identities, but rather, to arrive at them experimentally using Haskell. The associated GitHub page is here.

A partition of a natural number $n \in \mathbb{N}$ is a way of writing $n$ as a sum of smaller natural numbers, or blocks, ignoring the order in which we add the blocks. For instance, there are $5$ ways to partition the number $4$:

$4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1.$

A partition $\sigma$ can be thought of a multiset of natural numbers $\sigma = [\sigma_1, \ldots, \sigma_k] = [\sigma_i]$, where $\sigma_i \in \mathbb{N}$. The variable $k$ will stand for the number of blocks in a partition, and we typically order the blocks in increasing size, so that $\sigma_1 \leq \sigma_2 \leq \cdots \ldots \sigma_k$. This means we can talk about blocks being next to each other, or adjacent, in a partition.

We can consider partitions where the blocks have certain properties, conveniently encoded by a test which takes a partition and spits out “true” or “false” according to whether the partition has the property. Let’s denote the number of partitions of $n$ satisfying a predicate $Q$ by $p_Q(n)$. This is a modification of the usual notation $p(n)$ for the number of partitions without any constraints. Note that $p_Q(n) \leq p(n)$. Predicates can be combined using propositional connectives like “not” ($\neg$), “and” ($\wedge$), and “or” ($\vee$).

Here are some specific predicates:

• Adjacent elements of $\sigma$ differ by at least $2$, or $\sigma_{i+1}-\sigma_i \geq 2$ for all $0 \leq i \leq k$. We call this predicate $A$.
• The smallest element of $\sigma$ is at least $2$, or $\sigma_1 \geq 2$. Label this predicate $B$.
• Elements of $\sigma$ are congruent to $1$ or $4$ modulo $5$. Call this $C$.
• Elements of $\sigma$ are congruent to $2$ or $3$ modulo $5$. Call this $D$.

We can now state the Rogers-Ramanujan identities. For all $n \in \mathbb{N}$,

$p_A(n) = p_C(n), \qquad p_{A\wedge B}(n) = p_D(n).$

We’re going to build some Haskell code for experimentally seeing this result, and other similar partition identities. To follow along, you will need to have Haskell installed on your system, and understand the basics of the language. (For an introduction, I recommend Learn You a Haskell for Great Good.) This little project is, in part, a rather belated tribute to the surprisingly good Ramanujan biopic, The Man who Knew Infinity (2015).

### Generating partitions

To begin with, we’re going to be manipulating some lists, so we will import Data.List:

import Data.List


We now need some way to generate ordinary partitions (with the trivial predicate). Let’s do it recursively! Basically, to get partitions of $n$, we take the partitions of $n-1$ and either (a) add an extra block $1$, or (b) increase one of the blocks by $1$:

indexedAdd :: ([Int], Int) -> [Int]

where numCopies = length ls
copyLs    = replicate numCopies ls
zipped    = zip copyLs [1..numCopies]

partitions :: Int -> [[Int]]
partitions 0 = [[]]
partitions n = nub $biggerParts ++ newParts where recurParts = partitions (n-1) newParts = [ [1] ++ part | part <- recurParts ] biggerParts = map sort$ concat $map addOne recurParts  This automatically produces partitions with blocks in ascending size. This method is highly inefficient, so in the future, I hope to optimise this. ### Predicate builders To find$p_Q(n)$, we need to filter the partitions of$n$using the predicate$Q$. Before showing how to do this, let’s build up a stock of predicates. Even better, using currying, we can build objects which build predicates! Examples of flexible predicate builders are supersets, forbidden numbers and given remainders. I’ll go through these in turn. A superset predicate just checks if all the blocks lie in some set$N \subseteq \mathbb{N}$of natural numbers: supersetOf :: [Int] -> [Int] -> Bool supersetOf sup = foldl (\t x -> and [x elem sup, t]) True  Forbidden numbers are actually the same as supersets, but it’s easier sometimes to specify the complement of$N$than$N$itself: forbiddenNums :: [Int] -> [Int] -> Bool forbiddenNums forbidList = foldl (\t x -> and [not$ x elem forbidList, t]) True


An alternative way to forbid numbers is to negate the superset predicate, which I’ll discuss below. Finally, we have remainders, e.g. $\equiv 1 \pmod 4$:

remainders :: Int -> [Int] -> [Int]
remainders b [] = [1..]
remainders b rs = filter correctRem [1..]
where correctRem num = (rem num b) elem rs


These will obviously be important for the Rogers-Ramanujan identities. I’ll list a few more predicate builders that I decided would be useful:

differsBy :: Int -> [Int] -> Bool
differsBy _ []   = True
differsBy n ls = all (>=n) diffs
where diffs  = zipWith (-) (tail ls) ls

biggerThan :: Int -> [Int] -> Bool
biggerThan n = all (>n)

lessThan :: Int -> [Int] -> Bool
lessThan n = all (<n)

limitReps :: Int -> [Int] -> Bool
limitReps n ls = all (<=n) repLengths
where repLengths = map length $group ls noConsecMult :: Int -> Int -> [Int] -> Bool noConsecMult b rs ls = all test pairDiffs where diffs = zipWith (-) (tail ls) ls pairDiffs = zip diffs$ tail ls
test      = \(x, y) -> or [ x /= b, not $(rem y b) elem rs] predGaps :: Int -> Int -> Int -> [Int] -> Bool predGaps b rs gap ls = all test pairDiffs where diffs = zipWith (-) (tail ls) ls pairDiffs = zip diffs$ tail ls

### References

Written on September 30, 2018