Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

2.1 Lifting Prefix Complexity to Reals

This page discusses how our measures of incompressibility (via Kolmogorov complexity) can be lifted to quantity the (limiting) incompressibility of points in Euclidean space. In general, prefix complexity may be lifted to infinitary objects via finitary approximations. We state the following results how they were originally presented: over Euclidean space. Analogous statements also hold over Cantor space.

2.1.1Lifting Conditional Complexity

Take any ambient dimensions m,n∈ωm, n \in \omega, points x∈Rmx \in \mathbb{R}^m and y∈Rny \in \mathbb{R}^n, and precision-levels r,s∈ωr, s \in \omega. A straightforward definition of the complexity of xx given yy up to these precision-levels would be to evaluate the complexity: K(x↾r∣y↾s)K(\restrict{x}{r} \mid \restrict{y}{s}).

An alternative lift comes from the intuition offered by A. Shen and N. Vereshchagin in Shen & Vereshchagin (2002): that for rationals p∈Qmp \in \mathbb{Q}^m and q∈Qnq \in \mathbb{Q}^n, the conditional complexity K(p∣q)K(p \mid q) could be understood as the complexity of the problem Q→PQ \to P, where PP is the problem “construct pp” and QQ is the problem “construct qq.” So, the lift of conditional complexity to arbitrary subsets X⊆RmX \subseteq \mathbb{R}^m given Y⊆RnY \subseteq \mathbb{R}^n should reflect the complexity of constructing a point p∈X∩Qmp \in X \cap \mathbb{Q}^m from any point q∈Y∩Qnq \in Y \cap \mathbb{Q}^n. This definition was made explicit by J. Lutz and N. Lutz in Lutz & Lutz (2018).

In particular, they defined the conditional prefix complexity of XX given YY to be:

K(X∣Y):=max⁡q{min⁡p{K(p∣q):p∈X∩Qm}:q∈Y∩Qn},\begin{aligned} \Kc{X}{Y} := \max_{q} \set{\min_{p} \set{\Kc{p}{q}}{p \in X \cap \mathbb{Q}^m}}{q \in Y \cap \mathbb{Q}^n}, \end{aligned}

or +∞+\infty if either set is empty. Notice that this notion of complexity is governed only by the rational elements of the sets involved. Unconditionally, the prefix complexity of XX is:

K(X):=min⁡{K(p):p∈X∩Qm},\begin{aligned} \K{X} := \min\set{\K{p}}{p \in X \cap \mathbb{Q}^m}, \end{aligned}

or +∞+\infty whenever XX contains no rationals. Thus, a set is as simple as its simplest, rational element.

Now, for any x∈Rmx \in \mathbb{R}^m and y∈Rny \in \mathbb{R}^n, the conditional prefix complexity of xx to precision-level rr given yy to precision-level ss is:

Kr∣s(x∣y):=K(B2−r(x)∣B2−s(y)),\begin{aligned} \KcAt{r \mid s}{x}{y} := \Kc{B_{2^{-r}}(x)}{B_{2^{-s}}(y)}, \end{aligned}

while the prefix complexity of xx to precision-level rr (possibly given q∈Qnq \in \mathbb{Q}^n) is:

Kr(x∣q):=K(B2−r(x)∣{q}), andKr(x):=K(B2−r(x)).\begin{aligned} K_r(x \mid q) &:= K(B_{2^{-r}}(x) \mid \seq{q}), \text{ and}\\ K_r(x) &:= K(B_{2^{-r}}(x)). \end{aligned}

In the coming subsection, we will compare Kr∣s(x∣y)K_{r \mid s}(x \mid y) to K(x↾r∣y↾s)K(\restrict{x}{r} \mid \restrict{y}{s}).

It will also serve us to identify rational elements of a subset which witness the set’s prefix complexity. We borrow the nomenclature of A Case. and J. Lutz Case & Lutz, 2014.

2.1.2Results on Lifted Conditional Complexity

We recall two lemmas about Kr∣sK_{r \mid s} known as its linear sensitivities.

A consequence of the linear sensitivities is that one may approximate the conditional prefix complexity of Euclidean points more simply via dyadic truncations.

One may then conclude an approximate symmetry of information for prefix complexity on Euclidean space. Again, this is a weak form of symmetry of information.

We note that when computing with infinitary objects such as infinite binary strings or Euclidean reals, one must distinguish between oracle and conditional accesses. While oracle access permits computations with approximations of the given data to arbitrary precisions, conditional access places a firm limit on the precision-level to which one may access the given data.

2.1.3Lifts via Dyadic Cubes

The dyadic cubes serve as a convenient geometric basis over which to measure complexity along the reals.

As illustrated above, the standard method for lifting prefix complexity to points in a metric space is via a computable, dense subset. Recall that the complexity of an arbitrary subset X⊆RmX \subseteq \mathbb{R}^m was defined as the minimal complexity of a rational in XX (or +∞+\infty if no such rational exists). Intuitively, this definition captures the idea that a set is simple if it contains a point that is simple to describe, and complex otherwise. Likewise, the complexity of an arbitrary point x∈Rmx \in \mathbb{R}^m is definable to some precision-level r∈ωr \in \omega as the minimum complexity of a rational in the open 2−r2^{-r}-ball about xx. And, as we saw above, this is essentially equivalent to evaluating the complexity of the dyadic truncation of xx up to precision 2−r2^{-r} as in Lemma 2.1.4, or to finding a KK-minimizer to B2−r(x)B_{2^{-r}}(x) as in Lemma 4.9 of Case & Lutz (2014).

Something similar is true in the conditional case using either the max-min or min-max definitions of conditional prefix complexity Kr∣sK_{r \mid s} as discussed later in section 2.5. Already, Lemma 2.1.5 shows the ability for dyadic truncation to approximate Kr∣sK_{r \mid s}, while Proposition 2.5.9 will do the same via KK-minimizers.

Let us now introduce a family of lifts of prefix complexity to Euclidean space via dyadic cubes.

On the Notation page, we defined the collection Qm\mathcal{Q}^m of all dyadic rational cubes over Rm\mathbb{R}^m. If Q∈QmQ \in \mathcal{Q}^m is a dyadic cube, let K(Q)K(Q) denote the prefix complexity K(i)K(i) of the index of QQ in a standard (computable) enumeration of Qm\mathcal{Q}^m.

First, let

Hr(x):=min⁡{K(Q):Q∈Qm and Q⊆B2−r(x)},\begin{aligned} H_r(x) := \min \set{K(Q)}{Q \in \mathcal{Q}^m \text{ and } Q \subseteq B_{2^{-r}}(x)}, \end{aligned}

or +∞+\infty if the minimum is taken over the empty set, denote a third lift of complexity to points in Rm\mathbb{R}^m. Intuitively, this definition captures the idea that a point is simple if there are always sufficiently simple dyadic cubes in its vicinity. Clearly, Hr(x)≥+Kr(x)H_r(x) \geq^+ K_r(x), as the center cQc_Q of any dyadic cube QQ satisfying Q⊆B2−r(x)Q \subseteq B_{2^{-r}}(x) will satisfy cQ∈B2−r(x)c_Q \in B_{2^{-r}}(x). Yet, these notions do not differ significantly.

Another lift of prefix complexity to Euclidean space may be defined which does not significantly differ from the rest. Let

Gr(x):=min⁡{K(Q):x∈Q∈Qm and diam⁡(Q)≤2−r},\begin{aligned} G_r(x) := \min \set{K(Q)}{x \in Q \in \mathcal{Q}^m \text{ and } \diam(Q) \leq 2^{-r}}, \end{aligned}

or +∞+\infty if the minimum is taken over the empty set. Then, Gr(x)G_r(x) denotes a fourth lift of prefix complexity to points in Rm\mathbb{R}^m. Intuitively, this definition captures the idea that a point is simple if there are sufficiently small and simple dyadic cubes covering it. Compared to Hr(x)H_r(x), this fourth notion Gr(x)G_r(x) minimizes prefix complexity over a smaller class of dyadic cubes, since x∈Qx \in Q and diam⁡(Q)≤2−r\diam(Q) \leq 2^{-r} imply Q⊆B2−r(x)Q \subseteq B_{2^{-r}}(x), but not vice versa. Nevertheless, we observe asymptotic coincidence between the two notions.

The proof of Proposition 2.1.9 is nearly identical to that of Proposition 2.1.8, noting that exactly one of the at most (4/m)m(4 / \sqrt{m})^m dyadic cubes in B2⋅2−r(x↾r)B_{2 \cdot 2^{-r}}(\restrict{x}{r}) must contain xx.

The final variant begins with a definition: let a rational closed ball be a set

B‾δ(q):={x∈Rm:∣∣x−q∣∣≤δ}\overline{B}_\delta(q) := \set{x \in \mathbb{R}^m}{\norm{x - q} \leq \delta}

with q∈Qmq \in \mathbb{Q}^m and δ∈Q>0\delta \in \mathbb{Q}_{> 0}. Fix a computable encoding of rational closed balls by strings, so that for each oracle AA the machine UPF⁡A\mathbf{U}^A_{\operatorname{PF}} induces a partial map UA\mathbf{U}^A from programs to rational closed balls, ignoring outputs that do not encode a ball. Its domain is prefix-free. The ball complexity of xx at precision-level rr relative to AA is

LrUA(x):=min⁡{len⁡(π):UA(π)↓∋x and diam⁡UA(π)≤2−r}.\begin{aligned} L^{\mathbf{U}^A}_r(x) := \min \set{\operatorname{len}(\pi)}{\mathbf{U}^A(\pi) \downarrow \ni x \text{ and } \operatorname{diam} \mathbf{U}^A(\pi) \leq 2^{-r}}. \end{aligned}

This is the special case φ=UA\varphi = \mathbf{U}^A of the code length Lrφ(x)L^\varphi_r(x) of an arbitrary prefix-free ball code φ\varphi (Definition 2.4.4). We see another asymptotic agreement due to Miyabe:

2.1.4Lifting Discrete Semimeasures

Continuing the discussion of section 1.5, we might naturally extend a discrete semimeasure m:Qn→[0,1]m : \mathbb{Q}^n \to [0, 1] defined on the rationals to a set function over Rn\mathbb{R}^n in one of two ways:

μm(X):=∑q∈X∩Qnm(q),Πm(X):=sup⁡q∈X∩Qnm(q).\begin{aligned} \mu_m(X) &:= \sum_{q \in X \cap \mathbb{Q}^n} m(q), \\ \Pi_m(X) &:= \sup_{q \in X \cap \mathbb{Q}^n} m(q). \end{aligned}

The first, μm\mu_m, is a purely additive atomic measure defined on every subset of Rn\mathbb{R}^n. Whereas the second, Πm\Pi_m, is an outer measure on Rn\mathbb{R}^n with Πm(Rn)≤1\Pi_m(\mathbb{R}^n) \leq 1, and it is completely maxitive in the sense that for every arbitrary index set II:

Πm(⋃i∈IXi)=sup⁡i∈IΠm(Xi).\Pi_m \left(\bigcup_{i \in I} X_i\right) = \sup_{i \in I} \Pi_m(X_i).

It is also continuous from below along arbitrary increasing sequences; and is continuous from above along decreasing sequences of compact sets. In the language of capacities, Πm\Pi_m is a maxitive Choquet capacity whose point density function is mm on Qn\mathbb{Q}^n and zero everywhere else. After normalization, we might further refer to this outer measure as a possibility measure with possibility distribution gmg_m.

Always Πm≤μm\Pi_m \leq \mu_m.

In his doctoral dissertation, N. Lutz introduced the function κ(X):=2−K(X)\boldsymbol{\kappa}(X) := 2^{-K(X)}, where K(X):=min⁡{K(q):q∈X∩Qn}K(X) := \min \{ K(q) : q \in X \cap \mathbb{Q}^n \}, and zero if XX contains no rational points Lutz, 2017. This is exactly Πm(X)\Pi_m(X) for m(q):=2−K(q)m(q) := 2^{-K(q)}, so it is an outer measure.

Relative to any oracle AA, the Coding Theorem 1.5.2 gives for any X⊆RnX \subseteq \mathbb{R}^n:

κA(X)=∗ΠmA(X).\boldsymbol{\kappa}^A(X) =^* \Pi_{\mathbf{m}^A}(X).

J. Lutz and N. Lutz showed that, while μm\mu_{\mathbf{m}} is globally optimal (dominating every strongly finite, lower-semicomputable outer measure up to a multiplicative constant on all subsets), κ\boldsymbol{\kappa} is only locally optimal Lutz & Lutz, 2020. This contrast comes down to the inherent differences between the μ\mu and Π\Pi lifts.

This motivates a comparison to how Case and Lutz extended the a priori probability and Kolmogorov complexity notations to sets of strings S⊆2<ωS \subseteq 2^{<\omega} Case & Lutz, 2014:

Q(S):=∑UPF⁡(π)↓∈S2−len⁡(π)=∑σ∈SQ(σ),K(S):=min⁡σ∈SK(σ).\begin{aligned} Q(S) &:= \sum_{\mathbf{U}_{\operatorname{PF}}(\pi) \downarrow \in S} 2^{-\operatorname{len}(\pi)} = \sum_{\sigma \in S} Q(\sigma),\\ K(S) &:= \min_{\sigma \in S} K(\sigma). \end{aligned}

They define a layered disjoint system (LDS) as a set B⊆ω×ω×2<ωB \subseteq \omega \times \omega \times 2^{<\omega} whose blocks Br,t:={σ:(r,t,σ)∈B}B_{r,t} := \{ \sigma : (r, t, \sigma) \in B \} are pairwise disjoint within each layer rr: so Br,s∩Br,t=∅B_{r,s} \cap B_{r,t} = \emptyset whenever s≠ts \neq t.

The reverse inequality K(Br,t)≥−log⁡Q(Br,t)−O(1)K(B_{r,t}) \geq -\log Q(B_{r,t}) - O(1) fails in general, since a block may contain many strings. The theorem says instead that the total mass of a block exceeds the mass of its best element by at most a factor 2K(r)+O(1)2^{K(r) + O(1)}. Levin’s Coding Theorem (1.5.2) is the special case where every block is a singleton.

Apply the LDS Coding theorem to Rn\mathbb{R}^n: the layers Qrn\mathcal{Q}^n_r of the half-open dyadic cubes can computably enumerate their blocks (r,t)(r, t). And the blocks of Qrn\mathcal{Q}^n_r partition Rn\mathbb{R}^n. This builds an LDS. Using 2.1.11, we may conclude that ΠmA\Pi_{\mathbf{m}^A} and μmA\mu_{\mathbf{m}^A} essentially agree on half-open dyadic cubes.

That is, at each dyadic layer, the additive and maxitive extensions of mA\mathbf{m}^A agree up to a factor of 2o(r)2^{o(r)}. This is the fact that J. Lutz and N. Lutz use to prove that κ\boldsymbol{\kappa} is locally optimal Lutz & Lutz, 2020.

In summary, we have Kr(x)=K(B2−r(x))=−log⁡κ(B2−r(x))K_r(x) = K(B_{2^{-r}}(x)) = -\log \boldsymbol{\kappa}(B_{2^{-r}}(x)), while κ=∗Πm\boldsymbol{\kappa} =^* \Pi_{\mathbf{m}}. And the other lifts K(x↾r)K(x \upharpoonright r), Gr(x)G_r(x), Hr(x)H_r(x), and LrU(x)L^{\mathbf{U}}_r(x) agree up to logarithmic factors in rr. Likewise, μm\mu_{\mathbf{m}} agrees up to logarithmic factors on dyadic cubes.

References
  1. Shen, A., & Vereshchagin, N. (2002). Logical operations and Kolmogorov complexity. Theoretical Computer Science, 271(1), 125–129. https://doi.org/10.1016/S0304-3975(01)00035-4
  2. Lutz, J. H., & Lutz, N. J. (2018). Algorithmic information, plane Kakeya sets, and conditional dimension. ACM Trans. Comput. Theory, 10(2), Art. 7, 22. 10.1145/3201783
  3. Case, A., & Lutz, J. H. (2014). Mutual Dimension. https://arxiv.org/abs/1410.4135
  4. Lutz, N. J., & Stull, D. M. (2020). Bounding the dimension of points on a line. Inform. and Comput., 275, 104601, 15. 10.1016/j.ic.2020.104601
  5. Miyabe, K. (2026). Ball codes: A coding characterization of Hausdorff and packing dimensions.
  6. Lutz, N. J. (2017). Algorithmic Information, Fractal Geometry, and Distributed Dynamics [Phdthesis, Rutgers, The State University of New Jersey]. 10.7282/T3639SV4
  7. Lutz, J. H., & Lutz, N. J. (2020). Algorithmically Optimal Outer Measures.