Resource Convertibility (Part 1)

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:

\mathrm{timber} + \mathrm{nails} \geq \mathrm{table}

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:

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

Notice that this kind of equation is analogous to a chemical reaction equation like this:

2 \mathrm{H}_2 + \mathrm{O}_2 \geq \mathrm{H}_2\mathrm{O}

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 ‘\rightarrow’ instead of an ordering symbol ‘\geq’ , but here we interpret the equation slightly differently. As with the timber and the nails and nails above, the inequality says that if we have two hydrogen atoms and an oxygen atom, then we can let them react to a molecule of water, but we don’t have to. In this sense, having two hydrogen atoms and an oxygen atom is at least as good as having a molecule of water.

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 ‘\geq’ in between. The stuff on each side consists of a bunch of objects tacked together via ‘+’ . With respect to these two pieces of structure, the collection of all our resource objects forms an ordered commutative monoid:

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.

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 x,y\in A are the resource objects, corresponding to the ‘collections of stuff’ in our earlier examples, such as x = \text{timber} + \text{nails} or y = 2 \text{H}_2 + \text{O}_2. Then the addition operation simply joins up collections of stuff into bigger collections of stuff. The ordering relation \geq is what formalizes resource convertibility, as in the examples above. The third axiom states that if we can convert x into y, then we can also convert x together with z into y together with z for any z, for example by doing nothing to z.

A mathematically minded reader might object that requiring A to form a partially ordered set under \geq is too strong a requirement, since it requires two resource objects to be equal as soon as they are mutually interconvertible: x \geq y and y \geq x implies x = y. However, I think that this is not an essential restriction, because we can regard this implication as the definition of equality: ‘x = y’ is just a shorthand notation for ‘x\geq y and y\geq x’ which formalizes the perfect interconvertibility of resource objects.

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!

Resource convertibility: part 2.

Resource convertibility: part 3.

29 Responses to Resource Convertibility (Part 1)

  1. Bruce Smith says:

    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.

    • Tobias Fritz says:

      That’s a good point, thanks! You’re absolutely right in saying that what I mean is really something like this:

      10 \cdot \mathrm{plank} + 20\cdot \mathrm{nail} \geq \mathrm{table},

      where ‘10\cdot \mathrm{plank}‘ is shorthand for the 10-fold sum \mathrm{plank}+\ldots+\mathrm{plank}, and similarly for the nails.

      But: it’s not necessary to formalize the example like this. I could also take ‘\mathrm{timber}‘ to stand for an infinite number of planks, resulting in

      \mathrm{timber} + \mathrm{timber} = \mathrm{timber},

      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:

      \mathrm{timber} + \mathrm{nails} \geq \mathrm{timber} + \mathrm{nails} + \mathrm{table}.

      Does this clarify things?

  2. Tobias Fritz says:

    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.

    • John Baez says:

      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.

  3. John Baez says:

    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: a \le b if you can get some multiple of a by adding something to b. 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.

    • Tobias Fritz says:

      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 A is idempotent if x\geq x+x\geq x for all x\in A. Can we describe this kind of structure in purely order-theoretic terms? Do we need to equip A with two ordering relations in order to do so?

  4. nad says:

    Ordered commutative monoids are the mathematical formalization of resource convertibility and combinability as follows.

    To me this would eventually sound better if formulated as

    Ordered commutative monoids are a way of a mathematical formalization of resource convertibility and combinability as follows.

    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 \leq workA + timber + saw and table \leq workB + +timber +hammer + nail but “nothing” \leq workB+ timber + saw and “nothing” \leq workA + timber+hammer + nail then
    table \leq (timber + saw + workA)+(workB + timber+hammer + nail) but “nothing” \leq $ (timber + saw) +(workA+workB) + (timber+hammer + nail) as I would think.

    ?

  5. Tobias Fritz says:

    Nad wrote:

    if one leaves away time and space considerations (in particular the optimization of assembly lines is often rather nontrivial)

    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 \geq solution to assembly line problem,

    it becomes clearly analagous to the timber-and-table example from my post.

    there is e.g- still the aspect of incompatibility,

    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 10\textrm{planks} + 20\textrm{nails} + \textrm{hammer} + \textrm{saw}, 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.

    work ressource A, called workA does not know how to use a hammer

    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,

    \textrm{workA} + 10\textrm{planks} + 20\textrm{nails} + \textrm{hammer} + \textrm{saw} \not\geq \textrm{workA} + \textrm{table} + \textrm{hammer} + \textrm{saw} .

    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,

    \textrm{workA} + \textrm{workB} + 10\textrm{planks} + 20\textrm{nails} + \textrm{hammer} + \textrm{saw} \not\geq \textrm{workA} + \textrm{workB} + \textrm{table} + \textrm{hammer} + \textrm{saw} .

    • Tobias Fritz says:

      Ugh, sorry, this should have been a reply to nad and the last inequality should not be negated…

      • nad says:

        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
        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 \leq). 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:

        “nothing” \leq $ (timber + saw +workA)+(workB + timber+hammer + nail)

      • Tobias Fritz says:

        Nad wrote:

        sure workforce is a ressource.

        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 also don’t see that
        if two team up that this is necessarily catalyzing.

        I have used the term ‘catalyze’ in the technical sense that x+z\geq y+z, but x\not\geq y for elements x,y,z of an ordered commutative monoid. In the example that I made, ‘workA + workB‘ is a catalyst in this sense. I don’t want to say more about this here, because catalysis will be discussed in Part 2!

        because I actually did the brackets not as I wanted to

        I don’t think so, because the brackets don’t matter — that’s the point of associativity, which I tried to justify earlier.

        “nothing” \leq (timber + saw +workB)+(workA + timber+hammer + nail)

        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.

        • nad says:

          The answer to this strongly depends on the application context, and also on the goals that the model is being designed for.

          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 think so, because the brackets don’t matter — that’s the point of associativity, which I tried to justify earlier.

          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

          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 \leq workA + timber + saw and table \leq workB + +timber +hammer + nail but “nothing” \leq workB+ timber + saw and “nothing” \leq workA + timber+hammer + nail then
          table \leq (timber + saw + workA)+(workB + timber+hammer + nail) but “nothing” \leq (timber + saw +workB)+(workA + timber+hammer + nail)

          That is given commutativity depending on the bracketing you get another result.

  6. Robert says:

    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?

    • John Baez says:

      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.

    • Tobias Fritz says:

      One can illustrate what John said with the example of building a table:

      20\cdot\text{planks} + 10\cdot\text{nails}\geq \text{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.

  7. 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.

    • Tobias Fritz says:

      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.

    • Tobias Fritz says:

      It looks like a very beautiful book! I’ve included a reference in the upcoming new version of the paper.

  8. lee bloomquist says:

    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?

  9. domenico says:

    I am thinking that a monoid without the associativity should work better to represent chemical reaction and elementary logic.
    I am thinking that if the associativity is not true, a nested association is necessary, so that fox+goose+beans \geq river crossing (the association like the boat on the river) or block copolymers could be solved correctly.

  10. In Part 1, I introduced ordered commutative monoids as a mathematical formalization of resources and their […]

  11. 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.

  12. 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.

  13. 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.

  14. […] See Resource Convertibility by Tobias Fritz […]

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s