Dimensionality and randomness

Abstract

Arranging the bits of a random string or real into k columns of a two-dimensional array or higher dimensional structure is typically accompanied with loss in the Kolmogorov complexity of the columns, which depends on k. We quantify and characterize this phenomenon for arrays and trees and its relationship to negligible classes.

Content Overview

Let $K(\cdot)$ denote the prefix-free Komogorov complexity. The deficiency $d(\sigma)$ of a string $\sigma$ is $|\sigma|-K(\sigma)$. The deficiency of a set of strings $E$ is $d(E)=\sup_{\sigma\in E}d(\sigma)$. $E$ is incompressible if it has finite deficiency.

Generally it is hard to transform “thin” set of incompressible strings, e.g. the set of prefixes of a random real to a “fat” set of incompressible strings, e.g. a tree. We give two theorems based on this observation, and also give positive results to show how “fat” the set needs to be in order to make this transformation hard.

Theorem. No incomplete random real computes an $g$-fat set of incompressible strings, if $g$ is a recursive order with $\lim_n n/g(n)=0$.

Theorem. Every random real computes an $n/(\log n)^2$-fat set of incompressible strings.

Theorem. No incomplete random real computes a proper pruned incompressible tree.

Theorem. Every random real computes a perfect weakly-incompressible tree.

These results have a connection to deep $\Pi^0_1$ classes, and we show that they are not direct corollary of previous results.

Theorem. There exists a perfect pruned incompressible tree $T\leq_T\emptyset’’$ which is not a member of any $\Pi^0_1$ class.

Theorem. For each $c$, the class of $c$-incompressible perfect trees which are not members of any deep $\Pi^0_1$ class is comeager in the space of $c$-incompressible trees.

Finally we study the lost of deficiency as a result of growth of “fatness”, and also with a positive result.

Theorem. No incomplete random real computes a tree $T$ with $\log|T\cap 2^n|\geq 2\log\log|T\cap 2^n|+d(T\cap 2^n)$.

Theorem. No incomplete random real computes a tree $T$ and an order $g$ with $\log|T\cap 2^n|\geq g(n)+d(T\cap 2^n)$ such that $n\mapsto|T\cap 2^n|$ is recursive.

Theorem. For any recursive order $g$, every random real computes a perfect pruned incompressible tree $T$ with $\log|T\cap 2^n|=g(n)$ and $\lim_n(\log|T\cap 2^n|-d(T\cap 2^n))=\infty$.

Open problems

Question. Is it true that no incomplete random real computes a tree $T$ and an order $g$ with $\log|T\cap 2^n|\geq g(n)+d(T\cap 2^n)$?

Question. How to define a deep $\Pi^0_2$ class or the depth for higher arithmetical classes?

Links and resources

• Arxiv Link
• article pdf
• A related paper by Laurent Bienvenu, Christopher P. Porter, Deep $\Pi^0_1$ Classes