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.
Take any ambient dimensions m,n∈ω, points x∈Rm and y∈Rn, and precision-levels r,s∈ω. A straightforward definition of the complexity of x given y up to these precision-levels would be to evaluate the complexity: K(x↾r∣y↾s).
An alternative lift comes from the intuition offered by A. Shen and N. Vereshchagin in Shen & Vereshchagin (2002): that for rationals p∈Qm and q∈Qn, the conditional complexity K(p∣q) could be understood as the complexity of the problem Q→P, where P is the problem “construct p” and Q is the problem “construct q.” So, the lift of conditional complexity to arbitrary subsets X⊆Rm given Y⊆Rn should reflect the complexity of constructing a point p∈X∩Qm from any point q∈Y∩Qn. This definition was made explicit by J. Lutz and N. Lutz in Lutz & Lutz (2018).
In particular, they defined the conditional prefix complexity of X given Y to be:
K(X∣Y):=qmax{pmin{K(p∣q):p∈X∩Qm}:q∈Y∩Qn},
or +∞ 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 X is:
K(X):=min{K(p):p∈X∩Qm},
or +∞ whenever X contains no rationals. Thus, a set is as simple as its simplest, rational element.
Now, for any x∈Rm and y∈Rn, the conditional prefix complexity of x to precision-level r given y to precision-level s is:
Kr∣s(x∣y):=K(B2−r(x)∣B2−s(y)),
while the prefix complexity of x to precision-level r (possibly given q∈Qn) is:
In the coming subsection, we will compare Kr∣s(x∣y) to K(x↾r∣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.
We recall two lemmas about Kr∣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.
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⊆Rm was defined as the minimal complexity of a rational in X (or +∞ 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∈Rm is definable to some precision-level r∈ω as the minimum complexity of a rational in the open 2−r-ball about x. And, as we saw above, this is essentially equivalent to evaluating the complexity of the dyadic truncation of x up to precision 2−r as in Lemma 2.1.4, or to finding a K-minimizer to B2−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∣s as discussed later in section 2.5. Already, Lemma 2.1.5 shows the ability for dyadic truncation to approximate Kr∣s, while Proposition 2.5.9 will do the same via K-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 of all dyadic rational cubes over Rm. If Q∈Qm is a dyadic cube, let K(Q) denote the prefix complexity K(i) of the index of Q in a standard (computable) enumeration of Qm.
First, let
Hr(x):=min{K(Q):Q∈Qm and Q⊆B2−r(x)},
or +∞ if the minimum is taken over the empty set, denote a third lift of complexity to points in Rm. 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), as the center cQ of any dyadic cube Q satisfying Q⊆B2−r(x) will satisfy cQ∈B2−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},
or +∞ if the minimum is taken over the empty set. Then, Gr(x) denotes a fourth lift of prefix complexity to points in Rm. 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), this fourth notion Gr(x) minimizes prefix complexity over a smaller class of dyadic cubes, since x∈Q and diam(Q)≤2−r imply Q⊆B2−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 dyadic cubes in B2⋅2−r(x↾r) must contain x.
The final variant begins with a definition: let a rational closed ball be a set
Bδ(q):={x∈Rm:∣∣x−q∣∣≤δ}
with q∈Qm and δ∈Q>0. Fix a computable encoding of rational closed balls by strings, so that for each oracleA the machine UPFA induces a partial map UA from programs to rational closed balls, ignoring outputs that do not encode a ball. Its domain is prefix-free. The ball complexity of x at precision-level r relative to A is
LrUA(x):=min{len(π):UA(π)↓∋x and diamUA(π)≤2−r}.
This is the special case φ=UA of the code length Lrφ(x) of an arbitrary prefix-free ball code φ (Definition 2.4.4). We see another asymptotic agreement due to Miyabe:
Continuing the discussion of section 1.5, we might naturally extend a discrete semimeasure m:Qn→[0,1] defined on the rationals to a set function over Rn in one of two ways:
μm(X)Πm(X):=q∈X∩Qn∑m(q),:=q∈X∩Qnsupm(q).
The first, μm, is a purely additive atomic measure defined on every subset of Rn. Whereas the second, Πm, is an outer measure on Rn with Πm(Rn)≤1, and it is completely maxitive in the sense that for every arbitrary index set I:
Πm(i∈I⋃Xi)=i∈IsupΠm(Xi).
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 is a maxitive Choquet capacity whose point density function is m on Qn and zero everywhere else. After normalization, we might further refer to this outer measure as a possibility measure with possibility distribution gm.
Always Πm≤μm.
In his doctoral dissertation, N. Lutz introduced the function κ(X):=2−K(X), where K(X):=min{K(q):q∈X∩Qn}, and zero if X contains no rational points Lutz, 2017. This is exactly Πm(X) for m(q):=2−K(q), so it is an outer measure.
Relative to any oracle A, the Coding Theorem 1.5.2 gives for any X⊆Rn:
κA(X)=∗ΠmA(X).
J. Lutz and N. Lutz showed that, while μm is globally optimal (dominating every strongly finite, lower-semicomputable outer measure up to a multiplicative constant on all subsets), κ is only locally optimalLutz & Lutz, 2020. This contrast comes down to the inherent differences between the μ and Π 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<ωCase & Lutz, 2014:
They define a layered disjoint system (LDS) as a set B⊆ω×ω×2<ω whose blocksBr,t:={σ:(r,t,σ)∈B} are pairwise disjoint within each layerr: so Br,s∩Br,t=∅ whenever s=t.
The reverse inequality K(Br,t)≥−logQ(Br,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). Levin’s Coding Theorem (1.5.2) is the special case where every block is a singleton.
Apply the LDS Coding theorem to Rn: the layers Qrn of the half-open dyadic cubes can computably enumerate their blocks (r,t). And the blocks of Qrn partition Rn. This builds an LDS. Using 2.1.11, we may conclude that ΠmA and μmA essentially agree on half-open dyadic cubes.
That is, at each dyadic layer, the additive and maxitive extensions of mA agree up to a factor of 2o(r). This is the fact that J. Lutz and N. Lutz use to prove that κ is locally optimal Lutz & Lutz, 2020.
In summary, we have Kr(x)=K(B2−r(x))=−logκ(B2−r(x)), while κ=∗Πm. And the other lifts K(x↾r), Gr(x), Hr(x), and LrU(x) agree up to logarithmic factors in r. Likewise, μm agrees up to logarithmic factors on dyadic cubes.
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
Miyabe, K. (2026). Ball codes: A coding characterization of Hausdorff and packing dimensions.
Lutz, N. J. (2017). Algorithmic Information, Fractal Geometry, and Distributed Dynamics [Phdthesis, Rutgers, The State University of New Jersey]. 10.7282/T3639SV4
Lutz, J. H., & Lutz, N. J. (2020). Algorithmically Optimal Outer Measures.