<![CDATA[Resource Convertibility (Part 2)]]>

<![CDATA[Resource Convertibility (Part 2)]]>guest post by Tobias Fritz

In Part 1, I introduced ordered commutative monoids as a mathematical formalization of resources and their convertibility. Today I’m going to say something about what to do with this formalization. Let’s start with a quick recap!

Definition: An ordered commutative monoid is a set $A$ equipped with a binary relation $\geq,$ a binary operation $+,$ and a distinguished element $0$ such that the following hold:

• $+$ and $0$ equip $A$ with the structure of a commutative monoid;

• $\geq$ equips $A$ with the structure of a partially ordered set;

• addition is monotone: if $x\geq y,$ then also $x + z \geq y + z.$

Recall also that we think of the $x,y\in A$ as resource objects such that $x+y$ represents the object consisting of $x$ and $y$ together, and $x\geq y$ means that the resource object $x$ can be converted into $y.$

When confronted with an abstract definition like this, many people ask: so what is it useful for? The answer to this is twofold: first, it provides a language which we can use to guide our thoughts in any application context. Second, the definition itself is just the very start: we can now also prove theorems about ordered commutative monoids, which can be instantiated in any particular application context. So the theory of ordered commutative monoids will provide a useful toolbox for talking about concrete resource theories and studying them. In the remainder of this post, I’d like to say a bit about what this toolbox contains. For more, you’ll have to read the paper!

To start, let’s consider catalysis as one of the resource-theoretic phenomena neatly captured by ordered commutative monoids. Catalysis is the phenomenon that certain conversions become possible only due to the presence of a catalyst, which is an additional resource object which does not get consumed in the process of the conversion. For example, we have

$\text{timber + nails}\not\geq \text{table},$

$\text{timber + nails + saw + hammer} \geq \text{table + saw + hammer}$

because making a table from timber and nails requires a saw and a hammer as tools. So in this example, ‘saw $+$ hammer’ is a catalyst for the conversion of ‘timber $+$ nails’ into ‘table’. In mathematical language, catalysis occurs precisely when the ordered commutative monoid is not cancellative, which means that $x + z\geq y + z$ sometimes holds even though $x\geq y$ does not. So, the notion of catalysis perfectly matches up with a very natural and familiar notion from algebra.

One can continue along these lines and study those ordered commutative monoids which are cancellative. It turns out that every ordered commutative monoid can be made cancellative in a universal way; in the resource-theoretic interpretation, this boils down to replacing the convertibility relation by catalytic convertibility, in which $x$ is declared to be convertible into $y$ as soon as there exists a catalyst which achieves this conversion. Making an ordered commutative monoid cancellative like this is a kind of ‘regularization’: it leads to a mathematically more well-behaved structure. As it turns out, there are several additional steps of regularization that can be performed, and all of these are both mathematically natural and have an appealing resource-theoretic interpretation. These regularizations successively take us from the world of ordered commutative monoids to the realm of linear algebra and functional analysis, where powerful theorems are available. For now, let me not go into the details, but only try to summarize one of the consequences of this development. This requires a bit of preparation.

In many situations, it is not just of interest to convert a single copy of some resource object $x$ into a single copy of some $y;$ instead, one may be interested in converting many copies of $x$ into many copies of $y$ all together, and thereby maximizing (or minimizing) the ratio of the resulting number of $y$ ‘s compared to the number of $x$ ‘s that get consumed. This ratio is measured by the maximal rate:

$\displaystyle{ R_{\mathrm{max}}(x\to y) = \sup \left\{ \frac{m}{n} \:|\: nx \geq my \right\} }$

Here, $m$ and $n$ are natural numbers, and $nx$ stands for the $n$ -fold sum $x+\cdots+x,$ and similarly for $my.$ So this maximal rate quantifies how many $y$ ’ s we can get out of one copy of $x,$ when working in a ‘mass production’ setting. There is also a notion of regularized rate, which has a slightly more complicated definition that I don’t want to spell out here, but is similar in spirit. The toolbox of ordered commutative monoids now provides the following result:

Rate Theorem: If $x\geq 0$ and $y\geq 0$ in an ordered commutative monoid $A$ which satisfies a mild technical assumption, then the maximal regularized rate from $x$ to $y$ can be computed like this:

$\displaystyle{ R_{\mathrm{max}}^{\mathrm{reg}}(x\to y) = \inf_f \frac{f(y)}{f(x)} }$

where $f$ ranges over all functionals on $A$ with $f(y)\neq 0.$

Wait a minute, what’s a ‘functional’? It’s defined to be a map $f:A\to\mathbb{R}$ which is monotone,

$x\geq y \:\Rightarrow\: f(x)\geq f(y)$

and additive,

$f(x+y) = f(x) + f(y)$

In economic terms, we can think of a functional as a consistent assignment of prices to all resource objects. If $x$ is at least as useful as $y,$ then the price of $x$ should be at least as high as the price of $y$ ; and the price of two objects together should be the sum of their individual prices. So the $f$ in the rate formula above ranges over all ‘markets’ on which resource objects can be ‘traded’ at consistent prices. The term ‘functional’ is supposed to hint at a relation to functional analysis. In fact, the proof of the theorem crucially relies on the Hahn–Banach Theorem.

The mild technical mentioned in the Rate Theorem is that the ordered commutative monoid needs to have a generating pair. This turns out to hold in the applications that I have considered so far, and I hope that it will turn out to hold in most others as well. For the full gory details, see the paper.

So this provides some idea of what kinds of gadgets one can find in the toolbox of ordered commutative monoids. Next time, I’ll show some applications to graph theory and zero-error communication and say a bit about where this project might be going next.

• Resource convertibility: part 3.

]]>