Title: Being low for $\mathrm{K}$ along sequences and elsewhere

Slides

Abstract:
Given a set $D$ of strings, say a sequence $X$ is low for prefix-free Kolmogorov complexity $\mathrm{K}$ on $D$ in case access to $X$ as an oracle does not improve the prefix-free complexity of any string in $D$ by more than an additive constant. Furthermore, say $X$ is weakly low for $\mathrm{K}$ on $D$ in case $X$ is low for $\mathrm{K}$ on some, then necessarily infinite, subset of $D$. The usual notions of being low for $\mathrm{K}$ and being weakly low for $\mathrm{K}$ are obtained by letting $D$ be equal to the set of all strings. We investigate into the question what can be said about sequences that are low for $\mathrm{K}$ or weakly low for $\mathrm{K}$ on specific sets of strings, e.g., on the set of initial segments of some sequence. Accordingly, say $X$ is low or weakly low for $\mathrm{K}$ along a sequence $A$ in case $X$ is low or weakly low, respectively, for $\mathrm{K}$ on the set of initial segments of $A$. More specifically, for an infinite subset $I$ of the natural numbers, say $X$ is low or weakly low for $\mathrm{K}$ along $A$ on $I$ in case $X$ is low or weakly low, respectively, for $\mathrm{K}$ on the set of initial segments of $A$ with length in $I$.

Among others, we demonstrate the following results. If a sequence $X$ is not low for $\mathrm{K}$, then for any sequence $A$ and any infinite computable set $I$, the sequence $X$ is not low along $A$ on $I.$ As an immediate corollary, a sequence $X$ is low for $\mathrm{K}$ if and only if $X$ is low along all sequences on all infinite computable sets if and only if $X$ is low along some sequence on some infinite computable set. Furthermore, in case a sequence $X$ is weakly low for $\mathrm{K}$, then $X$ is weakly low along almost all sequences (in the sense of Lebesgue measure). Hence $X$ is weakly low for $\mathrm{K}$ if and only if $X$ is weakly low for $\mathrm{K}$ along almost all sequences if and only if X is weakly low for $\mathrm{K}$ along some sequence. Finally, for any infinite set $D$ of strings, the set of sequences $X$ such that $X$ is low for $\mathrm{K}$ on $D$ has measure 0 whereas the set of sequences $X$ such that $X$ is weakly low for $\mathrm{K}$ on $D$ has measure 1.

Joint work with Liang Yu.