nLab convex space

Idea

A convex space (also called barycentric algebra and other terms, invented independently many times) is a set equipped with a notion of taking weighted averages, or convex-linear combinations, of its elements. Do not confuse this with an (abstract) convex set, which a special kind of convex space, also defined below.

The category of convex spaces is the category of algebras of a Lawvere theory, being the affine part of the theory of $K$-(semi)modules with only the idempotent operations. This definition is used by Meng (1989), and many basic properties of the category are detailed therein. Equivalently, the category of convex spaces is the category of algebras of a finitary monad, as explained by Jacobs (2010) and Swirszcz.

The category of convex spaces is is complete, cocomplete, symmetric monoidal closed under the (usual) tensor product construction, and has a cogenerator Börger and Kemper (1994). The subcategory consisting of the single object, the unit interval, is dense (left-adequate) in the category. This follows from Isbell’s theorem on left adequate subcategories for algebraic theories, using the fact that the free convex space on 2 elements is the unit interval.

Axiomatically, a convex space can be characterized as a set $X$ equipped with a family of functions $c_p : X \times X \to X$ satisfying some natural axioms (described below).

For examples all nonunital commutative rings are convex spaces, with the map $c_p(x,y) = x + p(y-x)$.

The monad assigning to any set the free convex space on that set is a finitary commutative monad (see Jacobs (2010)). We can thus follow Durov in thinking of it as a generalized ring. This allows us to think of convex spaces as ‘modules’ of a generalized ring, very much as vector spaces are modules of a field. This is also true of the relatives of convex spaces: affine spaces and conical spaces. For example, all affine spaces are convex spaces as defined below.

Of particular importance are convex spaces parametrized by the interval $P = [0,1]$ or the Boolean algebra $P = \{0,1\}$. These two algebras are dual, in a certain sense described by Jacobs (2009). This duality is functorial, and therefore is present for convex spaces for general $P$. This leads to the notion of a dual convex space?.

Definition

A convex space is a set $X$ equipped with:

• a multiplicatively closed subset $Q$ of a (semi)ring $P$, so that for each element $p\in Q$ there exists an element $q\in Q$ such that $p+q=1$, and

• an operation $c_p: X \times X \to X$ defined for all $p\in Q$,

such that the following identities always hold:

• $c_0(x,y) = x$,
• $c_p(x,x) = x$ for all $p \in P$,
• $c_p(x,y) = c_{1-p}(y,x)$ for all $p \in P$ (in semiring case replace $1-p$ by $q$ and require that $p+q = 1$),
• $c_p(x, c_q(y,z)) = c_{p q}(c_r(x,y),z)$ for all $p,q,r \in P$ satisfying $p(1 - q) = (1 - p q)r$.

As a consequence of the first and third axioms, $c_1(x,y) = c_0(y,x) = y$.

This defines convex spaces as a variety of algebras, with one binary operation for each $p$.

The intended interpretation is that $c_p(x,y) = x + p(y-x) = (1-p)x + p y$. i.e., $c_p(x,y)$ is the $p$-weighted average of $x$ and $y$, where $x$ gets weight $1-p$ and $y$ gets weight $p$. By thinking of $p$ as a continuous parameter, this interpretation has the advantage of “starting” at $x$, then moving toward $y$ at “rate” $p$.

This interpretation is ‘biased’, in the sense that the centered choice $p=0$ favors $x$. It is also possible to give an ‘unbiased’ definition, which characterizes to convex-linear combinations of many points. This is an $n$-ary operation parametrised by a list $p := (p_1,\ldots,p_n)$ satisfying $\sum_{i = 1}^n p_i = 1$. If $x := (x^1,\ldots, x^n)$, then $c_p(x) := \sum_i p_i x^i$.

A homomorphism of convex spaces may be called a convex-linear map or an affine linear map (since an affine space is a convex space with extra properties, as in the examples below). It should probably not be called a ‘convex map’, which (between affine spaces) is something more general.

Examples

Any real vector space is a convex space, with $c_p(x,y) = x + p(y-x)$. In the unbiased version, any convex-linear combination is a linear combination. Note that a convex-linear map between vector spaces may not be a linear map, since it may not preserve the identity; thus, a vector space is a convex space with extra structure.

More generally, any real affine space is a convex space; since $p + (1 - p) = 1$, the expression for $c_p$ in a vector space is valid in an affine space. In the unbiased version, any convex-linear combination is an affine linear combination. Now any convex-linear map between affine spaces is an affine linear map (and conversely); an affine space is a convex space with extra properties.

Still more generally, any convex subset (that is, one containing the entire line segment between two given points) of a real affine space is a convex space (again with extra properties, which are described algebraically below).

The Boolean field $\{0,1\}$ is a convex space with $c_p(x,y) = x \vee y = x + y - x y$ whenever $0 \lt p \lt 1$ (with $c_0(x,y) = x$ and $c_1(x,y) = y$ as always); this cannot be realised as a subset of a vector space. This can be generalised to any (possibly unbounded) semilattice. (It would be nice to find an example like this that can be defined constructively; this one relies on excluded middle.)

Abstract convex sets

There is a nice abstract converse to the example of a convex subset of an affine space. A convex space is cancellative if $y = z$ whenever $c_p(x,y) = c_p(x,z)$ for some $x$ and $p \ne 0$. We may call a cancellative convex space an abstract convex set. The justification for this terminology is this

Theorem (Thm. 2 in the paper by Stone)

A convex space is cancellative if and only if it is isomorphic (as a convex space) to a convex subset of some real affine space.

Compare this with the theorem that a monoid is cancellative if and only if it is isomorphic to a submonoid of some group.

Of course, most of the examples given above are cancellative, being manifestly given as convex subsets of real affine space. However, the last example — a semilattice with $c_p(x,y) = x \vee y$ whenever $0 \lt p \lt 1$ — is non-cancellative.

Related concepts

• super convex space
• convex function
• distribution monad
• monads of probability, measures, and valuations
• vector space, affine space, conical space

References

Convex spaces have been rediscovered many times under many different names. References tend to define $c_p$ only for $0 \lt p \lt 1$, but it seems obvious that it's best to include the edge cases as well. Classically, it makes no difference, but the definition above is probably better in constructive mathematics.

• Handbook of Analysis and its Foundations, Section 12.7 (short and to the point).

• Börger & Kemper, Cogenerators for convex spaces, Applied Categorical Structures, Vol. 2 (1994), 1-11.

• Romanowska, Smith, Orłowska; Abstract barycentric algebras; pdf. This generalises from $[0,1]$ to an arbitrary $L \Pi$-algebra ($L$ for ‘Łukasiewicz’, $\Pi$ for ‘product’, so think of $[0,1]$ as a space of fuzzy truth values).

• Romanowska & Smith (1985); Modal Theory: An Algebraic Approach to Order, Geometry, and Convexity; Res. Exp. Math. 9; Heldermann-Verlag, Berlin, 1985.

• Marshall Harvey Stone, Postulates for the barycentric calculus, Ann. Mat. Pura. Appl. (4), 29:25–30, 1949.

• Tobias Fritz, Convex spaces I: definition and examples.

  arXiv/0903.5522

• John Baez, Tobias Fritz, Tom Leinster, Convex spaces and an operadic approach to entropy, $n$Lab draft

• Bart Jacobs, Duality for convexity arXiv/0911.3834

• Bart Jacobs, Convexity, duality and effects. In: IFIP International Conference on Theoretical Computer Science. Springer. 2010, pp. 1–19. (pdf)

• J.R. Isbell, Adequate subcategories, Illinois Journal of Math, 4, 541-552 (1960).

• Shiri Artstein-Avidan, Vitali Milman, The concept of duality in convex analysis, and the characterization of the Legendre transform, Annals of Math. 169, n.2, 661-674 (2009)

• Joe Flood, Semiconvex geometry, J. Austral. Math. Soc. Ser. A 30 (1980/81), 496-–510.

• T. Swirszcz, Monadic functors and categories of convex sets , Preprint No. 70, Proc. Inst. Math. Pol. Acad. Sci., Warsaw; Monadic functors and convexity, Bull. Acad. Polon. Sci. Ser. Sci. Math. Astronom. Phys. 22 (1974), 39–42.

• Stanley P. Gudder, Convexity and mixtures, SIAM Review 19 (1977), 221–240; A general theory of convexity, Milan Journal of Mathematics, 49 (1979), 89–96.

• Xiao-qing Meng, Categories of convex sets and of metric spaces with applications to stochastic programming and related areas, PhD thesis (djvu)

Many other references, and a discussion of how convex spaces have been repeatedly rediscovered, can be found at the $n$-Category Café post Convex Spaces.