×

Resource convertibility and ordered commutative monoids. (English) Zbl 1410.91308

Summary: Resources and their use and consumption form a central part of our life. Many branches of science and engineering are concerned with the question of which given resource objects can be converted into which target resource objects. For example, information theory studies the conversion of a noisy communication channel instance into an exchange of information. Inspired by work in quantum information theory, we develop a general mathematical toolbox for this type of question. The convertibility of resources into other ones and the possibility of combining resources is accurately captured by the mathematics of ordered commutative monoids. As an intuitive example, we consider chemistry, where chemical reaction equations such as \[ 2\mathrm{H}_2 + \mathrm{O}_2 \to 2\mathrm{H}_2\mathrm{O}, \] are concerned both with a convertibility relation ‘\(\to\)’ and a combination operation ‘\(+\)’. We study ordered commutative monoids from an algebraic and functional-analytic perspective and derive a wealth of results which should have applications to concrete resource theories, such as a formula for rates of conversion. As a running example showing that ordered commutative monoids are also of purely mathematical interest without the resource-theoretic interpretation, we exemplify our results with the ordered commutative monoid of graphs.
While closely related to both Girard’s linear logic and to Deutsch’s constructor theory, our framework also produces results very reminiscent of the utility theorem of von Neumann and Morgenstern in decision theory and of a theorem of Lieb and Yngvason on the foundations of thermodynamics.
Concerning pure algebra, our observation is that some pieces of algebra can be developed in a context in which equality is not necessarily symmetric, i.e. in which the equality relation is replaced by an ordering relation. For example, notions like cancellativity or torsion-freeness are still sensible and very natural concepts in our ordered setting.

MSC:

91B32 Resource and cost allocation (including fair division, apportionment, etc.)
91B16 Utility theory
06F05 Ordered semigroups and monoids
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] AbeyesingheA., DevetakI., HaydenP. and WinterA. (2009). The mother of all protocols: Restructuring quantum information’s family tree. Proceedings of the Royal Society A465 (2108) 2537-2563.10.1098/rspa.2009.0202 · Zbl 1186.81044
[2] AdámekJ., HerrlichH. and StreckerG.E. (1990). Abstract and Concrete Categories: The joy of cats, Pure and Applied Mathematics, New York, John Wiley & Sons, Wiley-Interscience Publication. Inc. Available at: tac.mta.ca/tac/reprints/articles/17/tr17abs.html. · Zbl 0695.18001
[3] AliprantisC.D. and TourkyR. (2007). Cones and Duality, Graduate Studies in Mathematics, volume 84, American Mathematical Society. · Zbl 1127.46002
[4] AubrunG. and NechitaI. (2008). Catalytic majorization and ℓ_p norms. Communications in Mathematical Physics278(1)133-144.10.1007/s00220-007-0382-4 · Zbl 1140.81318
[5] BennettC.H. (1998). Quantum information. Physica ScriptaT76210-217.10.1238/Physica.Topical.076a00210 · Zbl 1219.81069 · doi:10.1238/Physica.Topical.076a00210
[6] BennettC.H., BernsteinH.J., PopescuS. and SchumacherB. (1996a). Concentrating partial entanglement by local operations. Physical Review A53(4)2046-2052.10.1103/PhysRevA.53.2046
[7] BennettC.H., BrassardG., PopescuS., SchumacherB., SmolinJ.A. and WoottersW.K. (1996b). Purification of noisy entanglement and faithful teleportation via noisy channels. Physical Review Letters76(5)722-725.10.1103/PhysRevLett.76.722
[8] BennettC.H., DevetakI., HarrowA.W., ShorP.W. and WinterA. (2014). The quantum reverse shannon theorem and resource tradeoffs for simulating quantum channels. IEEE Transactions on Information Theory60(5)2926-2959.10.1109/TIT.2014.2309968 · Zbl 1360.81085
[9] BlackadarB. (1998). K-Theory for Operator Algebras, Mathematical Sciences Research Institute Publications, volume 5, 2nd edition, Cambridge, Cambridge University Press. · Zbl 0913.46054
[10] BlackadarB. and RørdamM. (1992). Extending states on preordered semigroups and the existence of quasitraces on C*-algebras. Journal of Algebra152(1)240-247.10.1016/0021-8693(92)90098-7 · Zbl 0789.46047
[11] BrandãoF.G.S.L. and GourG. (2015). Reversible framework for quantum resource theories. Physical Review Letters115 070503.
[12] BrandãoF.G.S.L., HorodeckiM., NgN.OppenheimJ. and WehnerS. (2013). The second laws of quantum thermodynamics. Proceedings of the National Academy of Sciences of the United States of America112(11)3275-3279.
[13] BrandãoF.G.S.L., HorodeckiM., OppenheimJ., RenesJ.M. and SpekkensR.W. (2013a). Resource theory of quantum states out of thermal equilibrium. Physical Review Letters111250404.10.1103/PhysRevLett.111.250404
[14] BrandomR. (2000). Articulating Reasons, Harvard University Press.
[15] ChudnovskyM., RobertsonN., SeymourP. and ThomasR. (2006). The strong perfect graph theorem. Annals of Mathematics164(1)51-229.10.4007/annals.2006.164.51 · Zbl 1112.05042
[16] CimpričJ., MarshallM. and NetzerT. (2011). Closures of quadratic modules. Israel Journal of Mathematics183(1)445-474.10.1007/s11856-011-0056-y · Zbl 1235.13021
[17] CoeckeB., FritzT. and SpekkensR. W. (2014). A mathematical theory of resources. arXiv:1409.5531. · Zbl 1353.81029
[18] CubittT., MančinskaL., RobersonD., SeveriniS., StahlkeD. and WinterA. (2014). Bounds on entanglement assisted source-channel coding via the lovasz theta number and its variants. IEEE Transactions on Information Theory60(11)7330-7344.10.1109/TIT.2014.2349502 · Zbl 1360.81053
[19] CubittT.S., LeungD., MatthewsW. and WinterA. (2011). Zero-error channel capacity and simulation assisted by non-local correlations. IEEE Transactions on Information Theory57(8)5509-5523.10.1109/TIT.2011.2159047 · Zbl 1365.81024
[20] DarnelM.R. (1995). Theory of Lattice-Ordered Groups, Monographs and Textbooks in Pure and Applied Mathematics, volume 187, New York, Marcel Dekker Inc. · Zbl 0810.06016
[21] DattaN. and HsiehM.-H. (2011). The apex of the family tree of protocols: Optimal rates and resource inequalities. New Journal of Physics13 093042. · Zbl 1448.81161
[22] DeutschD. (2013). Constructor theory. Synthese190(18)4331-4359.10.1007/s11229-013-0279-z · Zbl 1302.03027 · doi:10.1007/s11229-013-0279-z
[23] DeutschD. and MarlettoC. (2014). Constructor theory of information. arXiv:1405.5563. · Zbl 1371.81063
[24] DevetakI., HarrowA.W. and WinterA. (2008). A resource framework for quantum Shannon theory. IEEE Transactions on Information Theory54(10)4587-4618.10.1109/TIT.2008.928980 · Zbl 1322.81016
[25] Di CosmoR. and MillerD. (2006-2015). Linear logic. In: ZaltaE.N. (ed.) The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University. Available at: http://plato.stanford.edu/archives/sum2015/entries/logic-linear/.
[26] DuanR., FengY., LiX. and YingM. (2005). Multiple-copy entanglement transformation and entanglement catalysis. Physical Review A71042319. Available at: http://arxiv.org/abs/quant-ph/0404148.10.1103/PhysRevA.71.042319
[27] EnglerJ.-O. and BaumgärtnerS. (2013). An Axiomatic Approach to Decision under Knightian Uncertainty. Available at: eea-esem.com/eea-esem/2013/prog/viewpaper.asp?pid=1914.
[28] FakhruddinS.M. (1986). Absolute flatness and amalgams in pomonoids. Semigroup Forum33(1)15-22.10.1007/BF02573178 · Zbl 0581.06008 · doi:10.1007/BF02573178
[29] FeinbergM. and LavineR. (1983). Thermodynamics based on the Hahn-Banach theorem: The Clausius inequality. Archive for Rational Mechanics and Analysis82(3)203-293. · Zbl 0587.73008
[30] FritzT. (2009). Possibilistic Physics. Available at: fqxi.org/community/forum/topic/569.
[31] FuchssteinerB. and LuskyW. (1981). Convex Cones, North-Holland Mathematics Studies, volume 56, Amsterdam-New York, North-Holland Publishing Co. · Zbl 0478.46002
[32] GirardJ.-Y. (1987). Linear logic. Theoretical Computer Science50(1)101. · Zbl 0647.03016
[33] GlassA.M.W. (1999) Partially Ordered Groups, Series in Algebra, volume 7, River Edge, NJ, World Scientific Publishing Co., Inc. · Zbl 0933.06010
[34] GodsilC., RobersonD. W., ŠámalR. and SeveriniS. (2015). Sabidussi versus Hedetniemi for three variations of the chromatic number. Combinatorica. Available at: http://link.springer.com/article/10.1007
[35] GolanJ.S. (1999). Semirings and Their Applications, Dordrecht, Kluwer Academic Publishers. Updated and expanded version of The Theory of Semirings, with Applications to Mathematics and Theoretical Computer Science [Harlow, Longman Sci. Tech., 1992]. · Zbl 0780.16036
[36] GoodearlK.R. (1986). Partially Ordered Abelian Groups with Interpolation, Mathematical Surveys and Monographs, volume 20, Providence, RI, American Mathematical Society. · Zbl 0589.06008
[37] GourG., MüllerM.P., NarasimhacharV., SpekkensR.W. and HalpernN.Y. (2013). The resource theory of informational nonequilibrium in thermodynamics. Physics Reports5831-58. · Zbl 1357.81040
[38] GourG. and SpekkensR.W. (2008). The resource theory of quantum reference frames: Manipulations and monotones. New Journal of Physics10 033023.
[39] GrilletP.A. (2001). Commutative Semigroups, Advances in Mathematics, volume 2, Dordrecht, Kluwer Academic Publishers. · Zbl 1040.20048
[40] HalpernN.Y. (2014). Beyond heat baths II: Framework for generalized thermodynamic resource theories. arXiv:1409.7845. · Zbl 1387.82023
[41] HalpernN.Y. and RenesJ.M. (2014). Beyond heat baths: Generalized resource theories for small-scale thermodynamics. arXiv:1409.3998.
[42] HarrowA.W. (2010). Entanglement spread and clean resource inequalities. In: Proceedings of the 16th International Congress on Mathematical Physics, World Scientific, 536-540.
[43] HorodeckiM., HorodeckiP. and OppenheimJ. (2003). Reversible transformations from pure to mixed states, and the unique measure of information. Physical Review A67 062104. · Zbl 1267.81098
[44] HorodeckiM. and OppenheimJ. (2013). (Quantumness in the context of) resource theories. International Journal of Modern Physics B27 1345019. · Zbl 1279.81023
[45] HorodeckiR., HorodeckiP., HorodeckiM. and HorodeckiK. (2009). Quantum entanglement. Reviews of Modern Physics81(2)865-942.10.1103/RevModPhys.81.865 · Zbl 1205.81012
[46] HoweE. (1986). A new proof of Erdős’ theorem on monotone multiplicative functions. American Mathematical Monthly93(8)593-595.10.2307/2322314 · Zbl 0614.10001 · doi:10.2307/2322314
[47] HsiehM.-H. and WildeM. (2010a). Entanglement-assisted communication of classical and quantum information. IEEE Transactions on Information Theory56(9)4682-4704.10.1109/TIT.2010.2053903 · Zbl 1366.81097
[48] HsiehM.-H. and WildeM. (2010b). Trading classical communication, quantum communication, and entanglement in quantum shannon theory. IEEE Transactions on Information Theory56(9)4705-4730.10.1109/TIT.2010.2054532 · Zbl 1366.81098
[49] ImrichW. and KlavžarS. (2000). Product Graphs, Structure and Recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization. New York, Wiley-Interscience. · Zbl 0963.05002
[50] JanzingD., WocjanP., ZeierR., GeissR. and BethT. (2000). The thermodynamic cost of reliability and low temperatures: Tightening Landauer’s principle and the second law. International Journal of Theoretical Physics39(12)2217-2753. · Zbl 0986.81015
[51] JoyalA., StreetR. and VerityD. (1996). Traced monoidal categories. Mathematical Proceedings of the Cambridge Philosophical Society119(3)447-468.10.1017/S0305004100074338S0305004100074338 · Zbl 0845.18005
[52] KaroubiM. (1978). K-Theory, Berlin-New York, Springer-Verlag. An introduction, Grundlehren der Mathematischen Wissenschaften, Band 226. · Zbl 0382.55002
[53] KehayopuluN. and TsingelisM. (1998). On separative ordered semigroups. Semigroup Forum56(2)187-196.10.1007/PL00005940 · Zbl 0979.06008
[54] KelleyJ.L. and NamiokaI. (1976). Linear Topological Spaces, Graduate Texts in Mathematics, volume 36, Springer-Verlag, New York-Heidelberg. · Zbl 0318.46001
[55] KellyG.M. (2005). Basic concepts of enriched category theory. Reprints Theory and Applications of Categories10 vi+137. Reprint of the 1982 original. Available at: tac.mta.ca/tac/reprints/articles/10/tr10abs.html. · Zbl 1086.18001
[56] KlimeshM. (2007). Inequalities that collectively completely characterize the catalytic majorization relation. arXiv:0709.3680.
[57] KnuthD.E. (1994). The sandwich theorem. Electronic Journal of Combinatorics1A1. · Zbl 0810.05065
[58] KockJ. (2004). Frobenius Algebras and 2D Topological Quantum Field Theories, London Mathematical Society Student Texts, volume 59, Cambridge, Cambridge University Press. · Zbl 1046.57001
[59] KrepsD.M. (1988). Notes on the Theory of Choice, Westview Press.
[60] LawvereF.W. (2002). Metric spaces, generalized logic, and closed categories [Rend. Sem. Mat. Fis. Milano 43 (1973), 135-166 (1974)]. Repr. Theory Applications of Categories11-37. With an author commentary: Enriched categories in the logic of geometry and analysis. Available at: tac.mta.ca/tac/reprints/articles/1/tr1abs.html. · Zbl 0335.18006
[61] LeinsterT. (2014). Basic Category Theory, Cambridge University Press. · Zbl 1295.18001
[62] LiebE.H. and YngvasonJ. (1998). A guide to entropy and the second law of thermodynamics. Notices Amer. Math. Soc.45571-581. · Zbl 1038.80504
[63] LiebE.H. and YngvasonJ. (1999). The physics and mathematics of the second law of thermodynamics. Physics Reports3101-96.10.1016/S0370-1573(98)00082-9 · Zbl 1027.80504
[64] LiebE.H. and YngvasonJ. (2000). A fresh look at entropy and the second law of thermodynamics. Physics Today53(4)32-37.
[65] LiebE.H. and YngvasonJ. (2002). The mathematical structure of the second law of thermodynamics. In: Current Developments in Mathematics, 2001, Int. Press, Somerville, MA, 89-129. · Zbl 1027.80002
[66] LiebE.H. and YngvasonJ. (2014). Entropy meters and the entropy of non-extensive systems. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science470 (2167) 20140192.10.1098/rspa.2014.0192 · Zbl 1371.80005
[67] LovászL. (1979). On the Shannon capacity of a graph. IEEE Transactions on Information Theory25(1)1-7. Available at: cs.elte.hu/ lovasz/scans/theta.pdf.10.1109/TIT.1979.1055985 · Zbl 0395.94021
[68] LuttikB. (2003). A unique decomposition theorem for ordered monoids with applications in process theory (extended abstract). In: Mathematical Foundations of Computer Science 2003, Lecture Notes in Computer Science volume 2747, Springer, Berlin, 562-571. Available at: win.tue.nl/ luttik/Papers/Udecomp.pdf. · Zbl 1124.68393
[69] MarlettoC. (2015). The constructor theory of life. Royal Society Interface12(104) arXiv:1407.0681. · Zbl 1371.81063
[70] MarshallA.W. and OlkinI. (1979). Inequalities: Theory of Majorization and its Applications, Mathematics in Science and Engineering, volume 143, Academic Press, Inc. · Zbl 0437.26007
[71] MarvianI. and SpekkensR.W. (2013). The theory of manipulations of pure state asymmetry: Basic tools and equivalence classes of states under symmetric operations. New Journal of Physics15 033001. · Zbl 1451.81117
[72] MarvianI. and SpekkensR.W. (2014). Modes of asymmetry: The application of harmonic analysis to symmetric quantum dynamics and quantum reference frames. Physical Review A90 062110. · Zbl 1306.81022
[73] Moreira Dos SantosC.Decomposition of strongly separative monoids. Journal of Pure and Applied Algebra172(1)25-47.10.1016/S0022-4049(01)00141-4 · Zbl 1003.06007 · doi:10.1016/S0022-4049(01)00141-4
[74] NakadaO. (1951). Partially ordered Abelian semigroups. I. On the extension of the strong partial order defined on Abelian semigroups. Journal of the Faculty of Science, Hokkaido University. Series I.11181-189. · Zbl 0053.21101
[75] NielsenM.A. (1999). Conditions for a class of entanglement transformations. Physical Review Letters83 436.
[76] nLab. Stuff, structure, property, (2014). Available at: ncatlab.org/nlab/revision/stuff,+structure,+property/38.
[77] PaulsenV. and TomfordeM. (2009). Vector spaces with an order unit. Indiana University Mathematics Journal31319-1359. · Zbl 1211.46016
[78] PultrA. and TrnkováV. (1980). Combinatorial, Algebraic and Topological Representations of Groups, Semigroups and Categories, North-Holland Mathematical Library, volume 22, Amsterdam-New York, North-Holland Publishing Co. · Zbl 0418.18004
[79] RafteryJ.G. and van AltenC.J. (2000). Residuation in commutative ordered monoids with minimal zero. Reports on Mathematical Logic3423-57. Algebra & substructural logics (Tatsunokuchi, 1999). Available at: http://rml.tcs.uj.edu.pl/rml-34/cont-34.htm. · Zbl 0996.03040
[80] RobersonD.E. (2013). Variations on a Theme: Graph Homomorphisms. PhD thesis, University of Waterloo. Available at: uwspace.uwaterloo.ca/handle/10012/7814.
[81] RobersonD.E. and MančinskaL. (2012). Graph homomorphisms for quantum players. In: Proceedings of the 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) 212-216. · Zbl 1360.91048
[82] RørdamM., LarsenF. and LaustsenN. (2000) An Introduction to K-Theory for C*-Algebras, London Mathematical Society Student Texts, volume 49, Cambridge, Cambridge University Press. See also math.ku.dk/ rordam/K-theory.html. · Zbl 0967.19001
[83] RosalesJ.C. and García-SánchezP.A. (2009). Numerical Semigroups, Developments in Mathematics, volume 20, New York, Springer. · Zbl 1220.20047
[84] RosenthalK.I. (1990). Quantales and their Applications, Pitman Research Notes in Mathematics Series, volume 234, New York, Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc. · Zbl 0703.06007
[85] SchaeferH.H. and WolffM.P. (1999). Topological Vector Spaces, Graduate Texts in Mathematics, volume 3, 2nd edition, New York, Springer-Verlag. · Zbl 0983.46002
[86] ScheinermanE.R. and UllmanD.H. (2011). Fractional Graph Theory, Mineola, NY, Dover Publications, Inc. A rational approach to the theory of graphs, With a foreword by Claude Berge, Reprint of the 1997 original. · Zbl 1254.05003
[87] ShannonC.E. (1948). A mathematical theory of communication. Bell System Technical Journal27379-423, 623-656. Available at: cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf.10.1002/j.1538-7305.1948.tb00917.x · Zbl 1154.94303
[88] ShannonC.E. (1956). The zero error capacity of a noisy channel. IRE Transactions on Information Theory2(3)8-19.10.1109/TIT.1956.1056798 · doi:10.1109/TIT.1956.1056798
[89] ShirahataM. (1996). A Sequent Calculus for Compact Closed Categories. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.3906.
[90] ThessA. (2011). The Entropy Principle. Thermodynamics for the Unsatisfied, Springer. · Zbl 1216.80001
[91] TsinakisC. and ZhangH. (2004). Order algebras as models of linear logic. Studia Logica76(2)201-225. Available at: my.vanderbilt.edu/constantinetsinakis/files/2014/03/petri.pdf.10.1023/B:STUD.0000032085.13087.bd · Zbl 1044.03050
[92] VidalG. (2000). Entanglement monotones. Journal of Modern Optics47355-376.10.1080/09500340008244048 · doi:10.1080/09500340008244048
[93] von NeumannJ. and MorgensternO. (2007). Theory of Games and Economic Behavior, Princeton, NJ, Princeton University Press, anniversary edition. With an introduction by Harold W. Kuhn and an afterword by Ariel Rubinstein. · Zbl 0205.23401
[94] WehrungF. (1992). Injective positively ordered monoids. I, II. Journal of Pure and Applied Algebra83(1)43-100.10.1016/0022-4049(92)90104-N · Zbl 0790.06016 · doi:10.1016/0022-4049(92)90104-N
[95] World Wide Web Consortium. (2006). The rule of least power. Available at: w3.org/2001/tag/doc/leastPower.html.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.