guest post by Tobias Fritz
Hi! I am Tobias Fritz, a mathematician at the Perimeter Institute for Theoretical Physics in Waterloo, Canada. I like to work on all sorts of mathematical structures which pop up in probability theory, information theory, and other sorts of applied math. Today I would like to tell you about my latest paper:
• The mathematical structure of theories of resource convertibility, I.
It should be of interest to Azimuth readers as it forms part of what John likes to call ‘green mathematics’. So let’s get started!
Resources and their management are an essential part of our everyday life. We deal with the management of time or money pretty much every day. We also consume natural resources in order to afford food and amenities for (some of) the 7 billion people on our planet. Many of the objects that we deal with in science and engineering can be considered as resources. For example, a communication channel is a resource for sending information from one party to another. But for now, let’s stick with a toy example: timber and nails constitute a resource for making a table. In mathematical notation, this looks like so:
We interpret this inequality as saying that “given timber and nails, we can make a table”. I like to write it as an inequality like this, which I think of as stating that having timber and nails is at least as good as having a table, because the timber and nails can always be turned into a table whenever one needs a table.
To be more precise, we should also take into account that making the table requires some tools. These tools do not get consumed in the process, so we also get them back out:
Notice that this kind of equation is analogous to a chemical reaction equation like this:
So given a hydrogen molecules and an oxygen molecule, we can let them react such as to form a molecule of water. In chemistry, this kind of equation would usually be written with an arrow ‘
So what’s going on here, mathematically? In all of the above equations, we have a bunch of stuff on each side and an inequality ‘
Definition: An ordered commutative monoid is a set 
•
•
• addition is monotone: if 
Here, the third axiom is the most important, since it tells us how the additive structure interacts with the ordering structure.
Ordered commutative monoids are the mathematical formalization of resource convertibility and combinability as follows. The elements 
A mathematically minded reader might object that requiring 
We could now go back to the original examples and try to model carpentry and chemistry in terms of ordered commutative monoids. But as a mathematician, I needed to start out with something mathematically precise and rigorous as a testing ground for the formalism. This helps ensure that the mathematics is sensible and useful before diving into real-world applications. So, the main example in my paper is the ordered commutative monoid of graphs, which has a resource-theoretic interpretation in terms of zero-error information theory. As graph theory is a difficult and traditional subject, this application constitutes the perfect training camp for the mathematics of ordered commutative monoids. I will get to this in Part 3.
In Part 2, I will say something about what one can do with ordered commutative monoids. In the meantime, I’d be curious to know what you think about what I’ve said so far!
In timber + nails >= table, I think you are leaving out units for simplicity, i.e. your unit of timber is “just enough to make one table” and likewise for your unit of nails; I don’t think you mean “an infinite or unlimited amount of timber”. But (if I’m right about what you mean) I think leaving out the units makes it more confusing by making this aspect of your meaning ambiguous. It would be clearer if your example was something like 10 planks + 20 nails >= 1 table.
That’s a good point, thanks! You’re absolutely right in saying that what I mean is really something like this:
where ‘
‘ is shorthand for the 10-fold sum 
, and similarly for the nails.
But: it’s not necessary to formalize the example like this. I could also take ‘
‘ to stand for an infinite number of planks, resulting in
and likewise for the nails. In this way of formalizing the resource conversion, the original inequality of my post holds. And so does an even stronger one:
Does this clarify things?
Yes, thanks!
I want these blog posts to be focused on the main ideas rather than on listing references and explaining who did what. So for completeness, let me just briefly add here that not all of the ideas that I explain are due to the paper itself, but you can find proper references in there. For example, the idea of using ordered commutative monoids to formalize resource convertibility has been proposed a bit earlier in a paper that I wrote together with Bob Coecke and Rob Spekkens. It is very close in spirit to some quantum information theory stuff of Devetak, Harrow and Winter.
PS: there’s something wrong with one of the equations. The blog software doesn’t seem to know \rightarrow.
I fixed the equation. The actual problem was leaving out the $ at the end of a previous equation… and then, once that was fixed, the subscript in \text{H_2O} seemed to cause problems, so I dealt with that.
Nice article! I guess my main question is something like: what sort of ‘structure theorems’ are known for ordered commutative monoids? We won’t have a ‘classification’, but there might be nice general things to say, at least for some classes of them.
For example, there’s a nice theorem about commutative semigroups:
Theorem. Any commutative semigroup has a grading by a semilattice such that the homogeneous components are Archimedean semigroups.
I explained the definitions and sketched the proof here. The grading by a semilattice comes from the following preorder that any commutative semigroup has:
if you can get some multiple of 
by adding something to 
. That should have some nice interpretation in terms of resource theory!
Now, forget commutative semigroups and restrict attention to commutative monoids. Then what happens when our commutative monoid has its own ordering? How does this interact with the ordering in the semilattice… etcetera?
You may have answered these questions in your paper.
Yes, I’ve been thinking that there should exist a structure theorem like that, and the result that you mention gives me a better idea of what it may look like. It may already exist somewhere out there, but if it does, then I haven’t seen it yet.
In the unordered setting, I imagine that the equivalence between idempotent commutative monoids and semilattices (with bottom) is highly relevant. So the first step might be to ask, how does this equivalence generalize to the ordered setting?
Let’s say that an ordered commutative monoid
is idempotent if 
for all 
. Can we describe this kind of structure in purely order-theoretic terms? Do we need to equip 
with two ordering relations in order to do so?
To me this would eventually sound better if formulated as
I might have misunderstood something (in particular I didn’t look at the article) but even if one leaves away time and space considerations (in particular the optimization of assembly lines is often rather nontrivial) there is e.g- still the aspect of incompatibility, which might rather easily give you even a non-associative structure, which as I understood (?) is not a feature of a monoid (I might though eventually mix up some of the plentiful cathegoretic terms) . Like if work ressource A, called workA does not know how to use a hammer but a saw and workforce B the other way around then table
workA + timber + saw and table 
workB + +timber +hammer + nail but “nothing” 
workB+ timber + saw and “nothing” 
workA + timber+hammer + nail then
(timber + saw + workA)+(workB + timber+hammer + nail) but “nothing” \leq $ (timber + saw) +(workA+workB) + (timber+hammer + nail) as I would think.
table
?
Nad wrote:
I agree completely! Optimization of assembly lines is not a problem that I’m concerned with here, but it’s clearly very important and challenging. Nevertheless, ordered commutative monoids may also be a useful tool for studying the complexity of such a problem: if you have 1 hour of computation time on a supercomputer available, can you find the optimal solution to your assembly line problem? If you write it as an inequality like this,
1 hr computation time
solution to assembly line problem,
it becomes clearly analagous to the timber-and-table example from my post.
What kind of incompatibility do you have in mind here? Do you have a simple example?
You’re right in suspecting that monoids are always associative by definition. The reason is that when I group together a bunch of resource objects, like
, it should not matter how I put the brackets in this sum: with either bracketing, it’s just the same bunch of stuff! Likewise the order of the items in the sum should be irrelevant, which leads to commutativity.
Are you now also considering the worker who assembles the table as a resource object? That’s an interesting idea which goes beyond my original example. So if person ‘workA’ knows how to use the saw but not the hammer, then he will not be able to make the table,
Similarly for person ‘workB’, who can only operate the hammer, but not the saw. But if the two team up, they can successfully catalyze the conversion of the raw materials into a table,
Ugh, sorry, this should have been a reply to nad and the last inequality should not be negated…
sure workforce is a ressource. and as said not everybody is a MacGuyver type. There can be incompatibilities of workforce and tools and I also don’t see that
). That is instead of “nothing” \leq $ (timber + saw) +(workA+workB) + (timber+hammer + nail), where you might get the impression that (workA+workB) may “catalyze” I meant:
if two team up that this is necessarily catalyzing. There are human incompatibilities too.I am sorry you might have gotten this “catalyzing impression” maybe because I actually did the brackets not as I wanted to (and by the way also did not latex the
“nothing” \leq $ (timber + saw +workA)+(workB + timber+hammer + nail)
“nothing”
(timber + saw +workA)+(workB + timber+hammer + nail)
argh.
“nothing”
(timber + saw +workB)+(workA + timber+hammer + nail)
Nad wrote:
That’s true! But it’s independent of the question whether one should also model the workforce as a resource object living in an ordered commutative monoid. Often, one of the challenges in mathematical modelling is to figure out which things need to be taken into account and which things can be considered irrelevant to the model. The answer to this strongly depends on the application context, and also on the goals that the model is being designed for.
To give an example which is less politically loaded than the workforce, let’s consider the oxygen that we breathe. In most application contexts, we don’t need to consider it as a resource object, because it is just so abundant everywhere around us that we are guaranteed not to run short of it in most contexts. However, if our application context is scuba diving, then the oxygen is crucial and definitely needs to be considered as a resource object.
I have used the term ‘catalyze’ in the technical sense that
, but 
for elements 
of an ordered commutative monoid. In the example that I made, ‘
‘ is a catalyst in this sense. I don’t want to say more about this here, because catalysis will be discussed in Part 2!
I don’t think so, because the brackets don’t matter — that’s the point of associativity, which I tried to justify earlier.
I don’t actually understand this equation (or any of your other ones). Within the mathematical framework that I am developing, this would stand for ‘(timber + saw + workB) + (workA + hammer + nail)’ is a composite resource objected which can be converted into ‘nothing’. If one considers throwing things out and firing the workers to be feasible conversion operations, then this is trivial: in order to go from ‘(timber + saw + workB) + (workA + hammer + nail)’ to ‘nothing’, I simply dispose of the timber, nail, hammer and saw, and I fire workA and workB. Then I am left with nothing, as desired.
But thats true for any ressource. But well if you want another example then take incompatible tools, like a screw and a scewdriver which do not go together.
I don’t see how your comment justifies associativity.
My point is that in generic applications you easily may get non-associativity and I gave -what I think is- a concrete example in order to illustrate this.
With the correction I wrote above that
That is given commutativity depending on the bracketing you get another result.
Does any of this connect to linear logic? I have heard this spoken of as a theory of resources before, since you cannot duplicate and delete propositions arbitrarily. To put it another way: is there some system that linear logic is insufficient for, that leads to looking at the weaker structure of ordered commutative monoids?
Full-fledged linear logic has quite a few connectives: for example the usual ‘and’ and ‘or’ but also two more, ‘tensor’ and ‘par’. Working with ordered commutative monoids is a lot like working with just ‘and’: you can only use sentences like ‘(P and Q and R) implies (S and T)’; implies is not a full-fledged connective because you must use it exactly once, no more and no less.
Multiplicative intuitionistic linear logic is somewhere in between, and models of this kind of logic are closed symmetric monoidal categories. I wrote about them with Mike in our Rosetta Stone.
There are advantages to studying the simplest possible structures in exhaustive detail, and ordered commutative monoids are certainly close to the simplest kinds of ‘logic’ one can imagine.
One can illustrate what John said with the example of building a table:
How would you model this is linear logic? What’s the operational meaning of all the quantifiers, including negation? (I’m relatively ignorant of linear logic, so this is a genuine question.)
See also Section 10.1 of the paper. If my comparison to linear logic seems too naive, I’d be glad to know.
Your opening reminded me a bit of the motivating chapter of Andre Thess’s book The Entropy Principle (Springer, 2011) in which he uses the fable of Hans who manages to waste away a block of gold until he has nothing. The book was an interesting textbook-like conceptualization of Lieb and Yngvason’s work, which I always thought was due for a more thorough mathematical framework. I’m glad to see you not only reference them, but you appear to do what I’ve always wanted. Can’t wait to delve further into your actual paper.
Thanks very much, I didn’t know about that book and need to take a look! Also, I had no idea that somebody was just waiting for Lieb-Yngvason thermodynamics to be generalized ;) If you have any questions or comments while reading the paper, feel free to get back to me here or by email.
It looks like a very beautiful book! I’ve included a reference in the upcoming new version of the paper.
[…] Replied to a post on johncarlosbaez.wordpress.com : […]
For the same reasons you mention I’ll leave all my references for a linked paper–
http://fqxi.org/community/forum/topic/2420
Maybe you cover this in your paper, but we can’t claim to have put together a resource unless it works correctly. For example, if a flashlight we put together (as in the references) doesn’t work because the bulb is defective, we can’t claim to have a resource on hand.
For example if the bulb is defective, then the state of the switch no longer carries information about the state of the bulb. The switch carries information about the bulb because they are both part of the same system, which when it is not defective comprises information channels. One part of a system carries information about another part of the same system by virtue of the parts actually being parts of an existing system of information channels. If the system does not exist, and is instead what we might call a defective system, then what we might think is a part of it won’t carry information about another part of it. From this point of view, a correctly working resource is really a system of information channels.
Are there related ideas that I should pay special attention to when reading your paper?
I am thinking that a monoid without the associativity should work better to represent chemical reaction and elementary logic.
(the association like the boat on the river) or block copolymers could be solved correctly.
I am thinking that if the associativity is not true, a nested association is necessary, so that
In Part 1, I introduced ordered commutative monoids as a mathematical formalization of resources and their […]
This May, a small group of mathematicians is going to a workshop on the categorical foundations of network theory, or Jacob Biamonte. I’m trying to get us mentally prepared for this. We all have different ideas, yet they should fit together somehow.
Tobias Fritz, Eugene Lerman and David Spivak have all written articles here about their work, though I suspect Eugene will have a lot of completely new things to say, too. Now it’s time for me to say what my students and I have doing.
This May, a small group of mathematicians is going to a workshop on the categorical foundations of network theory, or Jacob Biamonte. I’m trying to get us mentally prepared for this. We all have different ideas, yet they should fit together somehow.
Tobias Fritz, Eugene Lerman and David Spivak have all written articles here about their work, though I suspect Eugene will have a lot of completely new things to say, too. Now it’s time for me to say what my students and I have doing.
Hugo Nava-Kopp and I have a new paper on resource theories:
• Brendan Fong and Hugo Nava-Kopp, Additive monotones for resource theories of parallel-combinable processes with discarding.
A mathematical theory of resources is Tobias Fritz’s current big project. He’s already explained how ordered monoids can be viewed as theories of resource convertibility in a three part series on this blog.
Ordered monoids are great, and quite familiar in network theory: for example, a Petri net can be viewed as a presentation for an ordered commutative monoid. But this work started in symmetric monoidal categories, together with my (Oxford) supervisor Bob Coecke and Rob Spekkens.
[…] See Resource Convertibility by Tobias Fritz […]
We are lucky to have Tobias in our course, helping the discussions along! He’s already posted some articles on resource theory here on this blog. We’re having fun bouncing between the relatively abstract world of monoidal preorders and their very concrete real-world applications to chemistry, scheduling, manufacturing and other topics. Here are the lectures so far:
• Lecture 18 – Chapter 2: Resource Theories
• Lecture 19 – Chapter 2: Chemistry and Scheduling
• Lecture 20 – Chapter 2: Manufacturing
• Lecture 21 – Chapter 2: Monoidal Preorders
• Lecture 22 – Chapter 2: Symmetric Monoidal Preorders
That’s a semi-intuitive example—i studied some chemistry and i’ve also built (actually repaired) a table (damaged in a domestic dispute–someone threw the table at someone else.).
I see they started to include the ‘work’ or ‘labor’ part in that –some nails and wood put next to each other won’t make a table in my experience. You need a worker–and then more resources–in general, workers have to eat and breath and even take a break from construction.
I see the author works at PI. I submitted an essay to FQXI associated with PI for a contest last year–it was rejected becuase it was improperly formatted and my references were not written in the standard form. Big names–Rovelli and G Ellis basically won that contest–got the $ or resources.
Smolin at PI among others also studies resource economics a bit—via guage theory.
I mostly study resource allocation from perspective of ecology and the economics of daily life. An ecosystem is similar to making a pie or table. You need some fish, snakes, deers, turkeys, foxes, coyotes, bears, frogs, trees etc and also some air and water and weather. The question is how many do you need and what is the optimal ‘ratios’. You can write that as kind of Cobbs-Douglas function from economics (or even a form of Ehrlich’s I=PAT).
Daily life is also a resource allocation problem. How do you spend your time or any money you have? Where do you fit in, in the ‘social ecosystem’? Some people don’t fit in anywhere–its like making a puzzle from pieces (or maybe one of those Penrose/Wang tilings to cover the plane noncomputably) –some puzzle pieces or tiles or people you just have to throw away.Ramanujan lasted 31 years before he was thrown away.