16
$\begingroup$

Summary

The base-$\beta$ logarithm gives an isomorphism of topological spaces $$ \log_\beta\colon\mathbb{R}_{\geq0}\xrightarrow{\cong}[-\infty,\infty). $$ This continuous map preserves some algebraic structure, e.g. sending multiplication to addition. As is well-known in tropical geometry, it also approximately sends the binary operation addition to the binary operation $\max$, $$\log_\beta(a+b)\approx\max\left(\log_\beta(a),\log_\beta(b)\right),$$ and this approximation gets better as the base $\beta\in(1,\infty)$ increases.


Question: Is there a category-theoretic way to tell this story?

Background

A commutative rig ("ring without negatives") is a tuple $(S, 0, +, 1, *)$, where $(S,0,+)$ and $(S,1,*)$ are both commutative monoids, and where multiplication distributes over addition, $a*(b+c)=(a*b)+(a*c)$. Both $$ \big(\mathbb{R}_{\geq0},0,+,1,*\big)\quad\text{and}\quad\big([-\infty,\infty), -\infty, \max, 0, +\big) $$ are rigs; in fact, they are topological rigs. That is, each of the sets $\mathbb{R}_{\geq0}$ and $[-\infty,\infty)$ has a well-known topology (e.g. in $[-\infty,\infty)$, the open sets containing $-\infty$ are generated under union by those of the form $[-\infty,x)$ for $x\in \mathbb{R}$), and in each case the two binary operations, namely $+,*$ and $\max,+$, are continuous with respect to that topology.

As mentioned above, the $\log_\beta$ function is an isomorphism of topological spaces, but it is not a homomorphism of rigs. It preserves almost all of the structure ($0\mapsto-\infty, 1\mapsto 0, *\mapsto +$), the one exception being that the addition operation is not preserved.

However, we do have simple bounds on the difference between $\log_\beta(a+b)$ and $\max(\log_\beta a,\log_\beta b)$ for all $a,b\in\mathbb{R}_{\geq0}$. One checks easily (using the two exhaustive cases $a\leq b$ and $b\leq a$) that $$ 0\leq \log_\beta(a+b)-\max\big(\log_\beta(a),~\log_\beta(b)\big)\leq\log_\beta 2. $$ Thus as $\beta$ gets bigger—one might think of $\beta$ physically as "coldness", so "as the system gets colder"—the approximation gets better: $\log_\beta$ becomes closer and closer to an isomorphism of topological rigs.

Motivation

Tropical geometry is widely studied field, and I imagine that nothing in this section is particularly novel in that context. But let me just say what motivates me.

Having an almost-isomorphism (asking precisely what that should mean is the goal of this post) between these two topological rigs is interesting because, for one thing, $\max,+$ matrix multiplication is much easier for humans and faster to compute than $+,*$ matrix multiplication. Moreover, lots of ideas port over.

For example, one can discuss what I might call "log-stochastic matrices" where the max of each column is 0. These form a category that is similar in certain ways to the usual category Stoch of finite sets and stochastic maps, but of course having key differences. Working a bit in this category, I could imagine it being relevant in behavioral economics, where there may be multiple "best choices" in a given situation (multiple 0's in a given column), and calculations need to be easy (again max, + being easier than +,*).

Categorical issues

My goal is to be able to say, category-theoretically, both that $\log_\beta$ is an approximate rig map for each $\beta\in(1,\infty)$, and also that these approximations get better as $\beta$ increases. To tell this story categorically, one needs to define what "better approximation" means.

One attempt could be to give something like a distance between $\log(a+b)$ and $\max(\log a, \log b)$, and for this we would need something like a metric. The usual category of metric spaces has short maps (distance non-decreasing functions) as its morphisms. This doesn't work too well for us, because $(\mathbb{R},0,+,1,*)$ is not an internal rig in that category; in particular, the multiplication operation $*\colon\mathbb{R}_{\geq0}\times\mathbb{R}_{\geq0}\to\mathbb{R}_{\geq 0}$ is not a short map. In fact, it is not even Lipschitz. But once one moves to the category of topological spaces or sets—where our two structures do become internal rigs—how will one measure the distances between their distance addition operations?

The goal is not to necessarily stick with the viewpoint of the previous paragraph, but to come up with a categorical viewpoint in which the successive approximations story is most at home.

$\endgroup$
2
$\begingroup$

Summary

While it could certainly be prettied up, it seems that the basic idea is actually fairly straightforward: use each $\log_\beta$ to transport the rig structure from $\mathbb{R}_{\geq0}$ to the space $[-\infty,\infty)$ and use the metric structure there.

Transporting the rig structure

For any $\beta$, consider the operation $P_\beta\colon[-\infty,\infty)\times[-\infty,\infty)\to[-\infty,\infty)$ given by $$P_\beta(a,b):=\log_\beta\left(\beta^a+\beta^b\right).$$ This is obtained by transporting $+$ along the $\log_\beta$ bijection. As such, it is easy to see that $P_\beta$ is unital with respect to $-\infty$ and associative, and that $+$ distributes over $P_\beta$. We can also see this directly, e.g.: \begin{align*} a+P_\beta(b,c)&= \log_\beta(\beta^a)+\log_\beta(\beta^b+\beta^c)\\&= \log_\beta(\beta^{a+b}+\beta^{a+c})\\&= P_\beta(a+b,a+c). \end{align*} The limit of these operations $P_\beta$ as $\beta$ increases is $$ \lim_{\beta\to\infty}P_\beta(a,b)= \lim_{\beta\to\infty}\log_\beta\left(\beta^a+\beta^b\right)= \max(a,b). $$ As an aside, a similar phenomenon occurs for the family of $\ell_p$ norms, and there seems to be a relationship. Namely, the variables in the exponential terms have switched roles ($\beta\leftrightarrow p$ and $\ell_p\leftrightarrow P_\beta$). Writing $\ell$ for $\ell_p$ and $P$ for $P_\beta$, one sees the resemblance immediately: $$ \ell(a,b)^p=a^p+b^p \qquad\text{vs.}\qquad \beta^{P(a,b)} = \beta^a + \beta^b. $$ We'll save this curiosity for another time.

A family of metric rigs

Going back to the main story, for any $\beta\in(1,\infty)$ we have a rig $$ R_\beta:=\big([-\infty,\infty),-\infty,~P_\beta~,0,+\big). $$ Each of these is of course isomorphic to the original rig $(\mathbb{R}_{\geq0},0,+,1,*)$, but the point is to show that these are rig objects in the category of (Lawvere) metric spaces. That is, we need to show that both operations are short with respect to the usual metric on $[-\infty,\infty)$.

Checking shortness for the "multiplication" operation $+$, we choose $a,b_1,b_2$ and see immediately that we have $d(a+b_1,a+b_2)=d(b_1,b_2)$ and hence the necessary inequality holds $$d(a+b_1,a+b_2)\leq d(b_1,b_2).$$ Checking shortness for the "addition"operation $P_\beta$ is slightly more involved. It uses the fact that for nonnegative reals $0\leq x$ and $0<y_2\leq y_1$ we have $\frac{x+y_1}{x+y_2}\leq\frac{y_1}{y_2}$. For any $a,b_1,b_2\in[-\infty,\infty)$, if either $b_1=-\infty$ or $b_2=-\infty$ it is easy to show that $d(P_\beta(a,b_1),P_\beta(a,b_2))\leq d(b_1,b_2)$. So we assume without loss of generality that $-\infty<b_2\leq b_1$, i.e. $0<\beta^{b_2}\leq\beta^{b_1}$, and compute \begin{align*} d\big(P_\beta(a,b_1),P_\beta(a,b_2)\big)&= \log_\beta(\beta^a+\beta^{b_1})-\log_\beta(\beta^a+\beta^{b_2})\\&= \log_\beta\left(\frac{\beta^a+\beta^{b_1}}{\beta^a+\beta^{b_2}}\right)\\&\leq \log_\beta\left(\frac{\beta^{b_1}}{\beta^{b_2}}\right)\\&= b_1-b_2=d(b_1,b_2). \end{align*} We have thus shown that $R_\beta$ is an internal rig in the category of Lawvere metric spaces. Indeed, in the case of both operations, we implicitly used the fact that the category of (Lawvere) metric spaces is monoidal closed, so a function $P\colon X_1\times X_2\to Y$ is short iff for each $a\in X_1$ the function $P_a\colon X_2\to Y$ given by $P_a(b):=P(a,b)$ is short.

Thus we have a whole family of operations $P_\beta$, one for each $\beta\in(1,\infty]$. Each of these fulfills the role of addition in the metric rig $R_\beta=([-\infty,\infty),-\infty,P_\beta,0,+)$. where we put $P_\infty:=\max$. And thus we also have a whole family of rig structures, all on the same space and all with the same units and the same multiplication.

There may be more to say, e.g. perhaps the $P_\beta$ satisfy certain laws for varying $\beta$, but I won't pursue anything further for now.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.