I’ve often been a bit spooked by the “big O notation” f = O(g), even though the definition really isn’t so bad.
For for positive valued real functions f and g defined on some unbounded set of reals, we say:
f = O(g) when \limsup f/g < \infty.
Maybe it’s the name itself: f = O(g) has to be one of the worst ways to express the idea that f is below g in some ordering on functions. According to wikipedia, Hardy’s original notation for the concept was f \preccurlyeq g, which is much better. But more likely, it’s because I have a terminal case of categorical brain-worms, and I just couldn’t quite figure out what this definition really meant, in that peculiarly insulting sense of “really” used colloquially by category theorists.
So this post is a story of what f = O(g) really means, to a category theorist. First, we’ll focus in on the quantity at the heart of the proposition that f = O(g), namely \limsup f/g \in [0, \infty]. This quantity always exists if we extend the reals by \infty, so we’ll do that. The TL;DR of this post is that we can interpret this quantity as the colimit of the internal hom of modules enriched in [0, \infty] with the reverse order \geq and monoidal structure of multiplication. If we then take the function \mathrm{bdd} : [0, \infty] \to \{\mathrm{false}, \mathrm{true}\} which sends a number to \mathrm{true} if and only if it is bounded, which is to say < \infty, then this number \limsup f/g becomes the predicate f \in O(g).
Before we go crashing forth into enriched category theory, let’s set the stage. By the way, I’m going to assume you know enriched category theory.
Define \mathcal{M} to be the monoidal category [0, \infty] with the greater-than ordering \geq and the monoidal product of multiplication xy and unit 1. We define 0 \cdot \infty = \infty, so that multiplication will preserve colimits (infema) in both variables.
We note that \mathcal{M} has a limits (or suprema, remember the reverse ordering) and colimits (or infema). It is also closed, since
xy \geq z if and only if x \geq z/y
I encourage you to think about what should happen with z and y are either 0 or \infty (this was first worked out by Fujii in his Bachelor’s thesis, at least in an isomorphic situation). Since \mathcal{M} is very similar to Lawvere’s [0, \infty] with the same ordering and monoidal structure +, I’ll call a \mathcal{M} category a “multric space”.
A “multric space” is a category enriched in \mathcal{M}. Explicitly, a multric space X consists of a set of objects and for each two objects x and y a number X(x, y) \in [0, \infty] so that
- 1 \geq X(x, x), and
- X(x,y)X(y, z) \geq X(x, z)
Now, a multric space is not anything new, at least up to isomorphism. This is because the function \log : [0, \infty] \to [-\infty, \infty] is a monoidal isomorphism between \mathcal{M} and the latter category equipped with the \geq ordering and the monoidal structure of +. This is the enriching base at the heart of Simon Willerton’s wonderful analysis of the Legendre-Frenchel tranform. We’ll prefer to use \mathcal{M} however, because our key formula is multiplicative.
For any a \in [0, \infty], there is a functor i_a : \mathbb{B} \to \mathcal{M} where \mathbb{B} = \{\mathrm{false}, \mathrm{true}\} is the usual ordering and i_a(\mathrm{false}) = \infty and i_a(\mathrm{true}) = a. This map i_a always preserves colimits, since on the left a colimit is existential quantification and on the right it is the infemum. A function d : X \to \{a, \infty\} has infemum a if and only if \exists x \in X with d(x) = a, which is the statement of colimit preservation of i_a. It therefore has a right adjoint \mathrm{bdd}_a, which we can compute directly from the adjunction statement when applies to \mathrm{true}:
a \geq x if and only if \mathrm{true} \vdash \mathrm{bdd}_a(x)
That is, \mathrm{bdd}_a(x) is the predicate that a \geq x. For i_a to be a lax monoidal functor, we need that 1 \geq a and a^2 \geq a, which are luckily the same condition. Of these, there is a maximal inclusion i_0 (remember the reverse ordering) and a minimal inclusion i_1. Now, i_0 is a bit special since it also preserves all limits, and therefore has a left adjoint as well as a right adjoint. To compute its right adjoint \phi, we can test on \mathrm{false}:
x \geq \infty if and only if \phi(x) \vdash \mathrm{false}
In other words, \phi(x) is false if and only if x = \infty, so we conclude that \phi(x) must be true if and only if x < \infty. In other words, the left adjoint to i_0 is \mathrm{bdd}, as defined above. Since 1 is bounded and xy is bounded just when both x and y are, \mathrm{bdd} is a monoidal functor.
Now we turn our attention to modules of multric spaces.
A (right) module of a multric space X is a function f : X \to [0, \infty] so that f(x)X(x, y) \geq f(y). Right modules form a multric space with \mathrm{Mod}_X(f, g) := \sup_x g(x)/f(x).
We’ll define the point-wise monoidal product on modules: (fg)(x) := f(x)g(x). This is not well defined for all mutlric spaces, however, since it’s not always the case that X(x, y) \geq X(x, y)^2. We’ll say that a metric space which satisfies this equation is log-negative — though note that it means 1 \geq X(x, y) or X(x, y) = \infty. In particular, i_a P is log-negative for any order P and a \in [0, 1].
For a log-positive multric space X, its modules form a closed monoidal multric space, where
[f, g](x) := \sup_y g(y)/(X(x, y)f(y)) = \mathrm{Mod}_X(X(x, -)f, g)
Let’s check that this works using some end-fu:
\mathrm{Mod}_X(f, [g, h]) = \sup_x (\sup_y h(y)/(X(x,y)g(y))/f(y)
= \sup_x\sup_y ((h(y)/(X(x, y)g(y))/f(y)
= \sup_x\sup_y h(y)/(X(x, y)g(y)f(y))
= \sup_x h(x)/(f(x)g(x))
= \mathrm{Mod}_X(fg, h)
It looks better in abstract notation:
\mathrm{Mod}_X(f, [g, h]) = \prod_x [f(x), [\prod_y [X(x, y)\otimes g(y), h(y)]]
= \prod_x \prod_y [f(x), [X(x, y)\otimes g(y), h(y)]]
= \prod_x \prod_y [f(x) \otimes X(x, y) \otimes g(y), h(y)]
= \prod_x [f(y) \otimes g(y), h(y)]
= \mathrm{Mod}_X(f \otimes g, h)
Now, we can take the colimit of [f, g], which is
\mathrm{colim}[f, g] = \inf_x \sup_y g(y)/(X(x, y)f(y))
This is the quantity I want to relate to the predicate f = O(g) — or the way this will turn out, g = O(f). Let U be a subset of \mathbb{R} which is unbounded on the right, and consider U as an order with the usual ordering. Then i_1 U is a multric space, and a right module on i_1 U is an increasing function f : U \to [0, \infty]. Given two such modules, consider \mathrm{colim}[f, g]:
\mathrm{colim}[f, g] = \inf_x \sup_y g(y)/(i_1U(x, y)f(y)) = \inf_x \sup_{y \geq x} g(y)/f(y)
This is because if y < x if and only if i_1U(x, y) = \infty, and in this case g(y)/(i_1U(x, y) f(y)) = 0, so the supremum can be computed by only looking at those y \geq x in which case i_1U(x, y) = 1. This is precisely \limsup g/f!
This only worked for increasing functions. Can we get all functions? Well any function f : U \to [0, \infty] on a set X can be seen as a module on the discrete multric space \flat U on U. We can Kan extend along the inclusion \flat U \to i_1 U and then compare them there: does this give the right thing? I’ll leave it for now and come back later if I figure it out.
Cheers,
David