Recently I have been thinking a lot about pullbacks of graphs and it really is frustrating at times because they’re much harder to think about compared to colimits. It turns out that there is an obvious (in hindsight) reason for this and I thought it would be nice to tell you about it.

While thinking of limits of graphs, I’ve been progressively roping more and more people into joining me in this game. First I started with my undergraduate student Mansi Pai and then I got Will Turner into it too. Both of them (like every other person I play these games with) observe very quickly that, although it’s very visually simple to think of taking colimits of graphs, limits, the dual operation, are much harder to think about. It turns out that you can see why very easily once you know a fact and a vibe:

Fact. spans of finite sets are \(\mathbb{N}\)-valued matrices.

Vibe. prime factorization is “hard” to do.

Now I put “hard” in quotes above because, as you probably know, nobody really knows which complexity class PrimeFactorization really ought to be in (although we all suspect it to be NP-intermediate). Either way though, since we base lots of cryptography on the fact that prime factorization is difficult to do, I think it’s fair for me to say that it’s a “hard problem” for the purposes of this post.

Now what about the fact I mentioned? Well, as the nlab will tell you, Spans in FinSet are \(\mathbb{N}\)-valued matrices : a span \(X_1 \leftarrow M \rightarrow X_2\) of finite sets, is a matrix with \(|X_1|\) rows, \(|X_2|\) columns and where the \((x_1, x_2)\)-entry (for \((x_1, x_2) \in X_1 \times X_2\)) is given by the cardinality of the fiber over the two elements \(x_1\) and \(x_2\) (i.e. the cardinality of the set \(\{m \in M \mid f_i(m) = x_i \text{ for } i \in \{1,2\}\) where \(f_1\) and \(f_2\) are the legs of the span above).

In any category \(\mathsf{C}\) with pullbacks, you can define the category \(\mathsf{Span}(\mathsf{C})\) of spans in \(\mathsf{C}\). This has as objects those of \(\mathsf{C}\) and as arrows the spans in \(\mathsf{C}\). Composition is done by pullback as follows: given two composable morphisms \((M, m_1, m_2) \colon X_1 \to X_2\) and \((N, n_1, n_2) \colon X_2 \to X_3\) as drawn below,

we form their composite by taking the pullback of \(m_2\) and \(n_1\) yielding the red span shown below.

Now, given what I just told you about thinking of matrices as spans, it should be natural to wonder whether the category \(\mathsf{Span}(\mathsf{FinSet})\) represents. It turns out that it can be thought of as the category having natural numbers as objects and matrices as morphisms which compose via matrix multiplication.

But then, armed with this fact and the fact that integer factorization is hard, it should be obvious that writing a graph as a limit of prime factors (where I mean “prime” in terms of being written as pullbacks) should be hard: if you could do that, then you would also have a way of factorizing matrices; but then you could factorize \(1 \times 1\) matrices. In other words, limits of graphs are hard to think about because integers are hard to factorize.

Alla prossima,

Ben