Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

April 1, 2009

Convex Spaces

Posted by David Corfield

It’s good to see other people talking about things we chat about here. So I was interested to see today Tobias Fritz’s paper Convex Spaces I: Definition and Examples:

We propose an abstract definition of convex spaces as sets where one can take convex combinations in a consistent way. A priori, a convex space is an algebra over a finitary version of the Giry monad. We identify the corresponding Lawvere theory as the category from arXiv:0902.2554 and use the results obtained there to extract a concrete definition of convex space in terms of a family of binary operations satisfying certain compatibility conditions. After giving an extensive list of examples of convex sets as they appear throughout mathematics and theoretical physics, we find that there also exist convex spaces that cannot be embedded into a vector space: semilattices are a class of examples of purely combinatorial type. In an information-theoretic interpretation, convex subsets of vector spaces are probabilistic, while semilattices are possibilistic. Convex spaces unify these two concepts.

This deals with issues raised in Tom’s thread (referenced by Fritz) and in this recent thread.

Fritz goes on to discuss examples of convexity, including KMS states and torus actions on symplectic manifolds.

Posted at April 1, 2009 5:38 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1942



17 Comments & 0 Trackbacks

Re: Convex Spaces

Thanks for the publicity!
I sure would like to know what you guys think about this abstract approach. In particular, how natural are the convex spaces of combinatorial type? Somehow it still seems slightly contrived to me due to the discontinuities involved. On the other hand, I believe that they could unify concepts previously thought to be independent: e.g. today I realized that this seems to be the case for Fourier-Motzkin elimination and the resolution technique in Boolean logic. Both of these work by eliminating variables one at a time.

Posted by: Tobias Fritz on April 2, 2009 11:36 AM | Permalink | Reply to this

Re: Convex Spaces

So what other coefficient changing maps could there be other than the semiring homomorphism:

ℝ ≥0→𝒮 2,λ↦sgn(λ)? \mathbb{R}_{\geq 0} \to \mathcal{S}_2, \lambda \map sgn(\lambda) ?

𝒮 2\mathcal{S}_2 is what gets called here the rig of truth values.

Posted by: David Corfield on April 2, 2009 2:07 PM | Permalink | Reply to this

Re: Convex Spaces

good question. Another obvious change coefficient changing map is the inclusion ℝ ≥0↪ℝ\mathbb{R}_{\geq 0}\hookrightarrow\mathbb{R} This change of coefficients functorially turns every affine space into a convex space; this functor has a left adjoint sending every convex space to its universal enveloping affine space. However due to the classification theorem of convex spaces (forthcoming), I believe that there are no interesting coefficient changing maps besides the one you mentioned.
Posted by: Tobias Fritz on April 3, 2009 10:22 AM | Permalink | Reply to this

Re: Convex Spaces

I wonder if this approach could make contact with Discrete convex analysis (review and survey).

Posted by: David Corfield on April 3, 2009 1:34 PM | Permalink | Reply to this

Re: Convex Spaces

Except for the case of endpoints of the unit interval,
Definition 3.1 is basically the one of Swirszck as
given in the paper of Joe Flood [1, Definition 1.2].
Flood refers to a preprint of Swirszck [2]. I do not
know if this later transformed into Swirszck [3], as
I have not seen the Swirszck papers.

[1]
Flood, Joe: Semiconvex geometry
J. Austral. Math. Soc. Ser. A 30 (1980/81) 4, p. 496–510
MR621565 (82k:52005)

[2]
Swirszcz, T.: Monadic functors and categories of convex sets.
Preprint No. 70 (Proc. Inst. Math. Pol. Acad. Sci., Warsaw)

[3]
Swirszcz, T.: Monadic functors and convexity.
Bull. Acad. Polon. Sci. Ser. Sci. Math. Astronom. Phys. 22 (1974)
p. 39–42
MR0390019 (52 \#10846)

Posted by: quarc on April 2, 2009 5:32 PM | Permalink | Reply to this

Re: Convex Spaces

thank you for these references! Once I get ahold of them I will update my preprint accordingly. By the abstract, Flood’s paper doesn’t only contain an equivalent definition, it also seems that I rediscovered a variant of his generalized Hahn-Banach separation theorem (to be published in “Convex Spaces II”). I feel embarrassed for unintentional plagiarizing: first the discussion here, then these papers.

Posted by: Tobias Fritz on April 3, 2009 10:01 AM | Permalink | Reply to this

Re: Convex Spaces

Hardly plagiarism, which requires you to have seen the original already.

I suppose mathematics blogs may make the task of checking for precedents harder by increasing the number of places to look beyond journals.

On the other hand, they’re good places to find out about precedents, as in this case.

Posted by: David Corfield on April 3, 2009 10:48 AM | Permalink | Reply to this

Re: Convex Spaces

“thank you for these references! Once I get ahold of them I will update my preprint accordingly.”

I’m glad I could help a little. There is no need to feel embarassed, this is just the great point about having something like the ArXiv: a couple of hundred readers can spot more than just two.

Strangely enough, Swirszck is mentioned in Giry’s paper, but the given reference is to a report by Semadeni, not to any publication of Swirszck himself. Out of curiousity I looked for “semiconvex” at dml and was given an article of Nykyforchyn with these axioms (with yet another notation), where also a reference to Swirszcz paper is given, so I think the axioms are there.

( P.S.: I realized that my usual nickname sounds too funny in a blog with so many theoretical physicists :-)

Posted by: Marc Olschok on April 4, 2009 7:11 PM | Permalink | Reply to this

Re: Convex Spaces

Since work on updating the preprint is delayed due to immense procrastination and work on other projects, here’s a quick wrap-up.

Convex spaces appear in the literature under various names, some of them being “barycentric algebra”, “convexor”, and “semiconvex set”. A variant of convex spaces which includes the additional structure of a total ordering is included in von Neumann and Morgenstern’s classic 1944 book “theory of games and economic behavior” in the context of comparing the utility of economic decisions. The next occurence in the literature is possibly Stone’s 1949 paper “postulates for the barycentric calculus”, where he mentions that he had already been talking about this in 1939.

Some excerpts from private communication with George Svetlichny:

I had noticed your posting “Convex Spaces I…” on the archives and it deals with topics I’m interested in. You mention in the introduction that you believe that abstract convexity has not yet been introduced, yet axioms for this have been around for at least 30 years. Gudder’s axiomatization of convexity and its generalizations is probably the best known (Gudder, S.P. (1977), “Convexity and mixtures”, SIAM Review 19: 221-240; Stanley P. Gudder, “A general theory of convexity”, Milan Journal of Mathematics, 49: 89-96, (1979)). Motivated by quantum theory I introduced my own axioms and investigated the category of convex sets somewhere around 1971. This was part of a monograph that was not published in its entirety (abstract convexity did not make it to print). I have been presenting versions (usually very close to yours) of my axioms in class for some time now. Since the 1970’s I’ve witnessed various sporadic appearances of abstract convexity but unfortunately did not keep track of the references. So this is not a new topic, but I am glad to see another go at it, especially with a categorical flavor.

As to why abstract convexity is not well known, it’s probably because the concrete versions are generally sufficient for whatever one is doing. I got interested in the abstract version since once you formalize the set of states and questions (or more general observation procedures) for any science that gives probabilistic predictions, convexity is natural but convexity withing a linear or affine space is not intrinsically there. Hence abstract convexity. What I’ve done with this is in a monograph that you can download from my web site. Parts of this has been published in a series of papers but the abstract convexity part not. I must advise though that this is old and outdated material and I would do things now quite differently. In particular I’ve come to view convex cones as more basic than convex sets which are then slices of cones by affine subspaces. A convex cone is (under appropriate axioms) the action of the rig of non-negative real numbers on an abelian semigroup. Rig action is something one can really sink one’s categorical teeth into and I would go this way in the abstract setting.

On the history of abstract convexity I forgot to mention axiomatizations of color-mixing. I’ve seen several such axiomatic schemes, again unfortunately I’ve not kept the references. These axiomatic schemes are much older than the abstract convexity references I sent last time. Grassman’s axiomatic system dates from 1854.

Posted by: Tobias Fritz on May 12, 2009 6:31 PM | Permalink | Reply to this

Re: Convex Spaces

Do you understand how to make more precise:

A convex cone is (under appropriate axioms) the action of the rig of non-negative real numbers on an abelian semigroup.

Posted by: David Corfield on May 14, 2009 8:53 AM | Permalink | Reply to this

Re: Convex Spaces

Yes, let me try to explain.

‘Convex cone’ here is to be interpreted in the sense of ‘conical space’: an algebra of the conical combinations monad. The conical combinations monad is given by the functor which maps any set to the set of formal conical combinations of its elements, together with the obvious unit and multiplication. But now, a formal conical combination is nothing but a formal linear combination with coefficients in the rig ℝ ≥0\mathbb{R}_{\geq 0}. Hence, a conical space is just a module over ℝ ≥0\mathbb{R}_{\geq 0}. Does this answer your question?

By now, I’ve come to view convex spaces as a special case of a more general categorical theory. The basic observation is that in some situations one should consider more general coefficients than just ℝ ≥0\mathbb{R}_{\geq 0}. For example, tropical convex geometry uses the tropical numbers as coefficients. Since the free convex spaces, i.e. simplices, are (morally) the spaces of probability measures, other examples come from alternative theories of probability: in the tropical case, free objects should be sets of possibility measures. One should hope that Dempster-Shafer theory has an analogous description, and maybe even quantum mechanics and population genetics, again with different coefficients. As the last three examples show, rig coefficients are too restrictive for this, and the correct framework could be given by Durov’s generalized rings aka finitary monads (on Set), which are actually generalized rigs. (Convex spaces are even mentioned in Durov’s thesis several times, search for ‘abstract convex sets’.)

Generalized rings make me wonder:

  • Has anyone worked out a theory of Morita equivalence for monads?
  • Is there a general criterion for telling when all algebras of a monad are free? (As is the case e.g. for the monad of linear combinations with coefficients in a field.)
Posted by: Tobias Fritz on May 14, 2009 10:47 AM | Permalink | Reply to this

Re: Convex Spaces

So nothing unexpected meant by “under appropriate axioms”.

We’ve looked at different rigs at the Café, and modules for them, from time to time to time to time to time.

Posted by: David Corfield on May 14, 2009 3:12 PM | Permalink | Reply to this

Re: Convex Spaces

Thanks for the links! I like how one can do dequantization by switching to tropical coefficients.

Posted by: Tobias Fritz on May 14, 2009 5:44 PM | Permalink | Reply to this

Re: Convex Spaces

Interesting – Duality for Convexity by Bart Jacobs:

Abstract: This paper studies convex sets categorically, namely as algebras of a distribution monad. It is shown that convex sets occur in two dual adjunctions, namely one with preframes via the Boolean truth values {0,1}\{0, 1\} as dualising object, and one with effect algebras via the (real) unit interval [0,1][0, 1] as dualising object. These effect algebras are of interest in the foundations of quantum mechanics.

Posted by: David Corfield on November 20, 2009 11:57 AM | Permalink | Reply to this

Re: Convex Spaces

What I gather from the paper is that both adjunctions arise from the same kind of currying operation, but I’m having a hard time figuring out the general categorical picture. What follows is an explanation of the concrete construction; can anyone help in describing an abstract setting?

Consider the dual adjunction between the category of convex spaces ConvConv and the category of effect algebras EAEA, as it is described in the paper. It can be reformulated as follows: the unit interval [0,1][0,1] carries both the structure of a convex space and the structure of an effect algebra. Also, let X∈ConvX\in Conv and E∈EAE\in EA be arbitrary objects. Define a bimorphism to be a map

X×E⟶[0,1]X\times E\longrightarrow [0,1]

which is a morphism of convex spaces when the second argument is fixed, and a morphism of effect algebras when the first argument is fixed. By currying the second argument, the set of bimorphism is naturally isomorphic to Conv(X,[0,1] E)Conv(X,[0,1]^E) where [0,1] E[0,1]^E is the exponential in EAEA. By currying the first argument, the set of bimorphisms is also naturally isomorphic to EA(E,[0,1] X)EA(E,[0,1]^X), where [0,1] X[0,1]^X is the exponential in ConvConv. This ends the construction of the adjunction. It works in just the same way when [0,1][0,1] gets replaced by any other set which is both a convex space and an effect algebra, such that the two structures commute.

So what’s going on here, abstractly?

Posted by: Tobias Fritz on December 8, 2009 1:39 PM | Permalink | Reply to this

Re: Convex Spaces

Tobias wrote:

… any other set which is both a convex space and an effect algebra, such that the two structures commute.

So what’s going on here, abstractly?

Are you familiar with the general concept of a dualizing object? Does this abstractly explain the phenomena you’re seeing here?

I’m really glad you’re studying convex spaces in a category-theoretic manner! It’s very useful to think of them as part of Durov’s theory. I’ve added your paper and some other references to the nLab article on convex spaces, and I enourage you to contribute a little to this page.

Posted by: John Baez on December 8, 2009 5:18 PM | Permalink | Reply to this

Re: Convex Spaces

Are you familiar with the general concept of a dualizing object?

I thought I was! Turns out that only referred to the setting of star-autonomous categories, where ‘dualizing object’ has a somewhat different meaning.

Does this abstractly explain the phenomena you’re seeing here?

It seems that yes, will have to understand and check the details.

I enourage you to contribute a little to this page.

Point taken!

Posted by: Tobias Fritz on December 10, 2009 4:46 PM | Permalink | Reply to this

Post a New Comment