From omega to Omega – Summer 2023 – IMS, Singapore

**Abstract.** We study the compressibility
of enumerations, and its role in the relative Kolmogorov complexity of
computably enumerable sets, with respect to density. With respect to a
strong and a weak form of compression, we examine the gain: the amount
of auxiliary information embedded in the compressed enumeration. Strong
compression and weak gainless compression is constructed for any
computably enumerable set, and a positional game is studied toward
understanding strong gainless compression.

Full paper at: `http://arxiv.org/abs/2304.03030`

Supported by NSFC grant No. 11971501.

**Extended abstract.** Consider the even
number game: given k>1, in each
round:

player 1 chooses k numbers

player 2 chooses an even number between smallest and largest chosen numbers

all choices are without repetition.

Any player that is unable to make a move loses the game. Who wins?

This problem is open for k>3 (player 1 has a winning strategy for k\leq 3).

Such positional games are key in understanding compressibility of enumerations.

**Problem:** given an effective enumeration
of A\subseteq\mathbb{N}, obtain a
compression of it, in the form of an effective enumeration of another
set D which:

essentially contains the information in A, but in a compact form.

This turns out to be the key to an open problem in Kolmogorov complexity (see below) but it is probably more interesting in its own right. By ‘essentially’ we mean indifference to finite errors: if D\upharpoonright_{\ell_n}, \ell_n\leq n is supposed to encode A\upharpoonright_{n}, we merely require that some computable f maps D\upharpoonright_{\ell_n} to an n-bit string f(D\upharpoonright_{\ell_n}) whose Hamming-distance from A\upharpoonright_n is bounded. Since A, D are computably enumerable (c.e.), this can be concisely expressed as C(A\upharpoonright_n\mid D\upharpoonright_{\ell_n})=\textrm{\textup O}\hspace{0.02cm}(1) where C(\sigma\mid\tau) denotes the conditional Kolmogorov complexity: the length of the shortest program that can generate \sigma from input \tau. By D being more compact than A we mean that \ell_n is considerably smaller than n or, at least, |\hspace{0.03cm}{D\upharpoonright_n}\hspace{0.03cm}| is considerably smaller than |\hspace{0.03cm}{A\upharpoonright_n}\hspace{0.03cm}|.

Given c.e. A,D, we say that D is a

compression of A if |\hspace{0.03cm}{D\upharpoonright_n}\hspace{0.03cm}|\leq |\hspace{0.03cm}{A\upharpoonright_n}\hspace{0.03cm}|/2 \ \wedge\ \ C(A\upharpoonright_n \mid D\upharpoonright_n)=\textrm{\textup O}\hspace{0.02cm}(1)

strong compression of A if C(A\upharpoonright_n \mid D\upharpoonright_{\lfloor n/2 \rfloor })=\textrm{\textup O}\hspace{0.02cm}(1).

Replacing n/2 by \epsilon n for \epsilon\in (0,1), in the same way we can define \epsilon-compression. If every c.e. set has a compression, by iteration it also has an \epsilon-compression; the same is true of strong compression. The simpler form often suffices for our purpose, as it can be iterated.

**Theorem 1**. *Given any c.e. A we can effectively enumerate a strong
compression of it.*

This process is relatively simple but introduces additional information, and which we call the gain, which is not recoverable from the source enumeration.

We say that a compression is gainless if it has finite gain, where the

gain of a compression D of A is C(D\upharpoonright_n \mid A\upharpoonright_n)

gain of a strong compression D of A is C(D\upharpoonright_{\lfloor n/2 \rfloor } \mid A\upharpoonright_n).

Obtaining gainless compressions is considerably harder and, useful for resolving problems about the Kolmogorov complexity of c.e. sets.

**Theorem 2**. *Given any c.e. A we can enumerate a gainless compression
D\subseteq A of it.*

The halting problem has a gainless strong \epsilon-compression, for arbitrary \epsilon\in (0,1).

**Open:** we do not know if every
c.e. set has a gainless strong compression.

Three preorders comparing the descriptive complexity of reals are \leq_{rK}, \leq_K, \leq_C: A\leq_{rK} B\iff C(A\upharpoonright_n\ \mid B\upharpoonright_n)=O(1) A\leq_{K} B\iff \forall n,\ K(A\upharpoonright_n)= K(B\upharpoonright_n)+O(1) where K denotes the Kolmogorov complexity with respect to prefix-free machines and \leq_{C} is defined similarly to \leq_K.

The question of density of c.e. sets with respect to \leq_{rK}, \leq_K, \leq_C is open.

We show that density holds amongst the c.e. sets that have a gainless strong compression.