# If you were to axiomatize the notion of entropy …

What are the axioms that a good notion of entropy must satisfy? Please note that I am not asking for the definitions of various types of entropy such as topological entropy or measure-theoretic entropy or etc. My question is, if $X$ is a 'space', in a broad sense (topological, measure, algebraic, etc.) and $\varphi:X\rightarrow X$ is a self-map, and if we want to define a good notion of entropy to measure the complexity of $\varphi$, what axioms should this notion satisfy?

EDIT: Perhaps a more reasonable question: For a system given by iterating a function, what should a good notion of entropy measure (with no or minimum reference to the type of space)?

-
pardon my ignorance, but haven't such questions long been considered in information theory? –  Suvrit Jun 30 '11 at 22:10
@Survit: I don't know. If you know of any reference, please post. –  Mahdi Majidi-Zolbanin Jun 30 '11 at 22:14
Check out the `characterization' section here, Mahdi: en.wikipedia.org/wiki/Entropy_(information_theory) –  Jon Bannon Jun 30 '11 at 22:19
@Jon: It seems that these axioms make sense in the context of a probability space, and they measure "uncertainty associated with a random variable" and would not make sense if $X$ is just a topological space. Yet, entropy can be defined in a topological dynamical system (see en.wikipedia.org/wiki/Topological_entropy). I was wondering if it is possible to characterize the notion of entropy with minimum reference to the type of the space involved? –  Mahdi Majidi-Zolbanin Jun 30 '11 at 22:34
how about "Kolmogorov complexity"? maybe the ideas behind it provide the necessary basis for the axiomatization that you are seeking? –  Suvrit Jul 1 '11 at 4:16

This isn't a full axiomatisation, partly because it's a little vague, and partly because I only am really familiar with the notion of entropy in two contexts: topological space and measure space. Nevertheless, there's a commonality to the procedure in both those cases.

1. Start with a space $X$ and a map $f\colon X\to X$.
2. Coarse-grain your space to a certain scale, so that orbit segments that are very close together are not distinguishable.
3. Count how many mutually distinguishable orbit segments of length $n$ it takes to be "significant"; call this number $a_n$.
4. Find the growth rate $\lim_{n\to\infty} \frac 1n \log a_n$; this is the entropy at the particular coarse scale you chose.
5. Let the coarse scale become finer and finer and take a limit to get the entropy.

Depending on how you make that procedure precise, you get various notions. For example, if $X$ is a topological space, "certain scale" means "code by an open cover", and "significant" means "covers X", then you get topological entropy. On the other hand, if $X$ is a measure space, "certain scale" means "code by a partition", and "significant" means "covers a set of uniformly positive measure", then you get measure-theoretic entropy.

I'd be interested in knowing if there are other notions of entropy for other sorts of spaces that have analogous definitions. Or for that matter, if there are other notions that don't have analogous definitions.

-
I almost e-mailed you about this question, but then decided to trust that you'd find it on your own. :) –  Paul Siegel Jul 1 '11 at 13:11
@Vaughn: There are also various notions of algebraic entropy that are defined for endomorphisms of algebraic structures such as groups or projective varieties. Some of these notions don't appear to have been defined according to the above axioms. For rational self-maps of projective varieties, for example, entropy is defined using its degree (see springerlink.com/content/nak975w6tk8lfjnl) and it seems that degree plays the role of the sequence $a_n$. –  Mahdi Majidi-Zolbanin Jul 1 '11 at 16:20

In addition to the wikipedia page, you can take a look at this fairly recent paper "A Characterization of Entropy in Terms of Information Loss" by John C. Baez, Tobias Fritz, Tom Leinster http://arxiv.org/abs/1106.1791

-
@Anthony: This is interesting, but still makes sense only in the context of a probability space. Please see my comment to Jon. –  Mahdi Majidi-Zolbanin Jun 30 '11 at 22:40

From a more physical perspective, there's the work of Lieb and Yngvason:

http://arxiv.org/abs/math-ph/0204007

-

The topological and measure-theoretic entropies of $(X,\varphi)$ formalize average entropy per iteration of partial observations ($\equiv$ the coarse-graining that Vaughn mentions above). (I am not familiar with other notions of entropy for dynamical systems.) In either case, one first needs an elementary notion of entropy for the class of allowed observations that is independent of $\varphi$.

Chris Hillman has some (sadly) unpublished notes in which he gives an elegant axiomatization of entropy that encompasses many more examples such as the Hausdorff dimension or what he calls the Galois entropy.

-

I want just to mention a framework in which we (Dikran Dikranjan, Anna Giordano Bruno and me) are going to redefine many notions of entropy.

The idea of prof. Dikranjan was to define the category of normed semigroups. Indeed, a normed semigroup is just a semigroup $S$ with a norm $$v:S\to \mathbb R_{\geq 0}$$ such that $v(xy)\leq v(x)+v(y)$. The morphisms in the category are just semigroup homomorphisms such that the norm of the image is $\leq$ than the norm of the original point.

In this category one can define a notion of entropy of an endomorphism $\phi:(S,v)\to (S,v)$. In fact one takes $$h(\phi)=\sup \left( \lim_{n\to\infty}\frac{v(x\phi(x)\dots\phi^{n-1}(x))}{n}: x\in S\right ) .$$ It is interesting to notice that already at this level, the above entropy function satisfies some good properties. Furthermore, it turns out that many of the usual notions of entropy (topological, algebraic, mesure-theoretic entropy, ...) for endomorphisms or automorphisms can be defined using a suitable functor from the category in which they are defined to the category of normed semigroups (the semigroup can be the set of subset with intersection (or sum in groups), the set of open covers with intersection, ... the norm can be $\log$ of the cardinality, measure, minimal cardinality of a subcover ...).

Let me conclude remarking that if you are looking for lists of axioms for entropy functions you should look to the following papers:

L. N. Stojanov, Uniqueness of topological entropy for endomorphisms on compact groups, Boll. Un. Mat. Ital. B 7 (1987) no. 3, 829–847. (axiomatic char. of topological entropy on compact groups)

D. Dikranjan and A. Giordano Bruno, Entropy on abelian groups, preprint; arXiv:1007.0533. (axiomatic char. of algebraic entropy on discrete groups)

L. Salce, P. Vamos, S. Virili, Length functions, multiplicities and algebraic entropy, Forum Math. (2011) (axiomatic char. of a notion of algebraic entropy on modules)

The above characterizations are discussed in the following survey,

D. Dikranjan, M. Sanchis, S. Virili, New and old facts about entropy in uniform spaces and topological groups, Topology appl. (2012) 1916-1942

-