1.10 Effective Dimension Variants

We review two variants of effective dimension.

1.10.1 Mutual Dimension¶

One variant of effective dimension is mutual dimension, which was originally defined in Case & Lutz (2014). It intuitively captures the algorithmic information shared by two infinitary objects in the limit. In Shannon information theory, mutual information is a measure of the correlation between two distributions. A. Case and J. Lutz’s algorithmic notion of mutual information serves as a refinement of the classical notion. Namely, the (conditional) mutual information between two finitary objects $a, b \in \mathscr{N}$ given $c \in \mathscr{N}$ is

Extending their notation slightly, we define the mutual information between subsets $X \subseteq \mathbb{R}^m$ and $Y \subseteq \mathbb{R}^n$ as:

or zero if taken over the empty set. Then the mutual information between $x \in \mathbb{R}^m$ to precision-level $r$ and $y \in \mathbb{R}^n$ to precision-level $s$ is defined as:

Both $I$ and $I_{r : s}$ inherit many of their expected properties such as a chain rule and symmetry from $K$ and $K_{r \mid s}$. In particular, a slight generalization to Theorem 4.10 in Case & Lutz (2014) for distinct precision-levels proves the chain rule for $I_{r : s}$.

Case and Lutz further defined the lower and upper mutual dimensions of $x \in \mathbb{R}^m$ and $y \in \mathbb{R}^n$ as follows:

Both mutual dimensions possess a few special properties. For instance, if $x \in \mathbb{R}^m$ and $y \in \mathbb{R}^n$, then $0 \leq \operatorname{mdim}(x : y) \leq \min \seq{\operatorname{mdim}(x), \operatorname{mdim}(y)}$. As well as symmetry: $\operatorname{mdim}(x : y) = \operatorname{mdim}(y : x)$. Analogous statements hold for $\operatorname{Mdim}$.

1.10.2 Conditional Dimension¶

A conditional version of effective dimension was first defined in Lutz & Lutz (2018) using the lifted conditional prefix complexity $K_{r \mid s}$. The lower and upper conditional dimensions of $x \in \mathbb{R}^m$ given $y \in \mathbb{R}^n$ were defined as:

Conditional dimension may equivalently be characterized in terms of semimeasures and supergales as in Theorem 1.9.2.

These conditional dimensions were shown to relate with the weak and strong effective dimensions as follows:

1.10.3 Results on Mutual and Conditional Dimensions¶

Both mutual dimensions behave predictably under computable, uniformly-continuous maps. We cite here just one corollary of this robustness.

In his dissertation Reimann, 2004, J. Reimann argues why effective dimension is also preserved under bi-computable, (locally) bi-Lipschitz continuous maps. This fact was used by N. Lutz to confirm an analog of Marstrand’s Projection Theorem for the effective dimension of points Lutz, 2017. Results like these mimic the preservation of Hausdorff dimension under locally bi-Lipschitz continuous maps (e.g., Corollary 2.4 in Falconer (1990)). We will expand on this later in Section 2.2.

Finally, we summarize the known relations between mutual, conditional, and effective dimensions.

We note that two of these inequalities were already proved in Corollary 11 of Lutz & Lutz (2018). Our contribution is to add the uppermost bound in the top line, and the lowermost bound in the bottom line. All of these inequalities follow by re-expressing mutual dimension using the chain rules for $I_{r : r}$ and $K_{r \mid r}$ as in Theorems 1.10.1 and 1.7.6, respectively, and then distributing the limits inferior or superior appropriately over those terms.