On the recognition problem for limits of entropy functions

Abstract

We prove that there is no algorithm to decide whether a given integer vector is in the closure of the entropic cone $\overline{\hat{I}{“}_n^{\ast }}$. Equivalently, there is no decision procedure to determine whether a given integer-valued function $h:\mathcal{P}(\{1,\dots ,n\})\to {\mathbb{Z}}_{\ge 0}$ is a pointwise limit of joint entropy functions. In other words, given such an $h$, it is undecidable whether for all $\epsilon >0$ there exists a finite probability space $(\hat{I}\text{c◯},P)$ with random variables $X_1,\dots ,X_n$ such that their joint entropy $H$ satisfies ${\max }_{I\subseteq \{1,\dots ,n\}}\left|H\left(X_I\right)-h\left(I\right)\right|<\epsilon$. This settles the last open case in a sequence of related undecidability results proved by L. Kühne and the author, with applications in algorithmic information theory. The main new tool is a Desargues'-type theorem for almost entropic polymatroids.

24 pages, 10 figures