On the recognition problem for limits of entropy functions
By: Geva Yashfe
Potential Business Impact:
Proves no computer can solve a certain math problem.
We prove that there is no algorithm to decide whether a given integer vector is in the closure of the entropic cone $\overline{\Gamma_{n}^{*}}$. Equivalently, there is no decision procedure to determine whether a given integer-valued function $h:\mathcal{P}(\{1,\ldots,n\})\rightarrow\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 $\varepsilon > 0$ there exists a finite probability space $(\Omega,P)$ with random variables $X_{1},\ldots,X_{n}$ such that their joint entropy $H$ satisfies $\max_{I\subseteq\{1,\ldots,n\}}\left|H\left(X_{I}\right)-h\left(I\right)\right|<\varepsilon$. This settles the last open case in a sequence of related undecidability results proved by L. K\"{u}hne and the author, with applications in algorithmic information theory. The main new tool is a Desargues'-type theorem for almost entropic polymatroids.
Similar Papers
Entropy approximations of algebraic matroids over finite fields
Combinatorics
Links math structures to information theory.
Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies
Combinatorics
Proves math problems are too hard to solve.
Conditions for equality and stability in Shannon's and Tao's entropy power inequalities
Probability
Proves when random data is "normal" or "special."