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 equipped with a binary relation a binary operation and a distinguished element such that the following hold:
• and equip with the structure of a commutative monoid;
• equips with the structure of a partially ordered set;
• addition is monotone: if then also
Recall also that we think of the as resource objects such that represents the object consisting of and together, and means that the resource object can be converted into
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
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 sometimes holds even though 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 is declared to be convertible into 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 into a single copy of some instead, one may be interested in converting many copies of into many copies of all together, and thereby maximizing (or minimizing) the ratio of the resulting number of ‘s compared to the number of ‘s that get consumed. This ratio is measured by the maximal rate:
Here, and are natural numbers, and stands for the -fold sum and similarly for So this maximal rate quantifies how many ’ s we can get out of one copy of 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 and in an ordered commutative monoid which satisfies a mild technical assumption, then the maximal regularized rate from to can be computed like this:
where ranges over all functionals on with
Wait a minute, what’s a ‘functional’? It’s defined to be a map which is monotone,
In economic terms, we can think of a functional as a consistent assignment of prices to all resource objects. If is at least as useful as then the price of should be at least as high as the price of ; and the price of two objects together should be the sum of their individual prices. So the 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.