2
$\begingroup$

I'm a programmer and only vaguely familiar with category theory, but I ran into something where I have the gut feeling that category theory could have helped me.

I wrote a program to generate anagrams. Mathematically, this can be expressed as follows:

  1. Treat each word or sentence as a multiset of letters. For example, the word banana corresponds to the multiset $\{\textrm{a}^3, \textrm{b}^1, \textrm{n}^2\}$.
  2. Two words (or sentences) are anagrams of each other exactly when they correspond to the same multiset.
  3. To list $N$-word anagrams of a sentence, start by computing the multisets of all words in a word list. Now, the anagrams are the sums of $N$ of these multisets $w_1 + w_2 + \cdots + w_N$ which are equal to to sentence's multiset.

At some point when working at this, I had the intuition that we could also express this problem using natural numbers as follows:

  1. Map each distinct letter in our query (the sentence to find an anagram for) to a small prime. To keep the numbers as small as possible, map the most common letter to 2, the next most common to 3, then 5, and so on. So, if our query is banana, we get $p(\textrm{a}) = 2$, $p(\textrm{n}) = 3$, and $p(\textrm{b}) = 5$.
  2. Map the multiset of each word or sentence to the product $\prod_c p(c)^{m(c)}$, where $m(c)$ is the multiplicity of the character.
  3. Now, the sum of two multisets corresponds to their product; multiset subtraction corresponds to division; and, if I needed those operations for my algorithm, intersection would correspond to the greatest common divisor and union to the lowest common multiple.

Now, it turns out that CPUs are quite good at manipulating numbers; good enough that we gain some extra speed for anagrams of reasonable lengths by using the natural number encoding instead of lists of multiplicities.

However, I believe the only reason I was able to come up with this mapping is that it was familiar territory: I have probably seen something very similar elsewhere, and I think even with multisets occasionally the terminology of greatest common divisor and lowest common multiple is used. Suppose I wouldn't have been aware of this correspondence. Would knowing category theory have helped me spot it and other similarly interesting correspondences?

$\endgroup$
2
  • 5
    $\begingroup$ I don't think category theory specifically would have helped you. $\endgroup$
    – Qi Zhu
    Commented Sep 18, 2020 at 13:04
  • 1
    $\begingroup$ From checking the wikipedia page to multisets, it seems that the terminology from gcd and lcm here stems from the intuition that by choosing the correct poset, these notions would be the meet and join of the poset - which would be gcd and lcm in the poset of $(\mathbb{N}, \leq)$. (Those would be product and coproduct from a categorical perspective.) $\endgroup$
    – Qi Zhu
    Commented Sep 18, 2020 at 13:05

1 Answer 1

3
$\begingroup$

It's certainly possible! One way to get there is to note that for any set $S$, the set of multisets with elements from $S$ can be identified with the free commutative monoid on $S$, a very well-known categorical construction. It is also well-known in number theory, and is essentially a way of phrasing the fundamental theorem of arithmetic, that the commutative monoid of natural numbers under multiplication is freely generated by the set of primes.

In particular, the monoid of natural numbers expressible as a product of the $26$ smallest primes, under multiplication, is thus isomorphic to the monoid of multisets with elements from the English alphabet, and multiset addition, which tells you how to turn a multiset into a natural number and how to compute the sum of multisets by multiplying natural numbers. One still has to prove the results about intersection and gcd, etc, but thinking about free commutative monoids could be enough to give the idea.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .