Universal codings of integers

A (binary) coding of the integers is a prefix-free code of the natural numbers, whose codewords are non-decreasing in size. A coding is universal if it is short enough (log n + o(log n)), but that's not important.

Some examples:

• The unary coding 0, 10, 110, ...; code length is n
• Code first the length of the number in unary, then the number itself in binary; code length is about 2log n
• Code first the length of the number using the previous coding, then the number itself in binary; code length is about log n + 2log log n
• ...
• Diagonalize the construction to get code length of log n + log log n + ... + 2log^* n
• Continue this way through the constructible ordinals

The diagonalized code, known as the $\omega$-code, is due to Peter Elias.

A partial ordering of codes

The sequence of codes above are progressively better, in the following sense:

• A coding a is better than a coding b if |b(n)| - |a(n)| tends to infinity.

There are some natural questions to ask:

• Is there a best code?
• If not, is there an optimal sequence of codes?

As it turns out, not only is there no best code, but given any sequence of codes, we can always find a code which is better than all of them; the proof from one of Hausdorff's papers (Untersuchungen über Ordnungtypen V from 1907) can be adapted to our setting.

Scales

The best thing that can be hoped for is a chain of codes which is cofinal for the poset of codes, i.e. a set of mutually comparable codings, such that for each arbitrary coding, our scale contains a superior one (such a beast Hausdorff called a Pantachie).

The problem of scales is well-known, and it is easy to show the existence of a scale given CH (following Hausdorff's steps). In other settings (and possibly this one), existence already follows from MA. However, most of the literature deals with somewhat different posets, and it is not clear that their results apply in this case.

Here are some pointers:

• Hausdorff Gaps and Limits by Frankiewicz and Zbierski, which deals with the ordering f > g if f(n) > g(n) infinitely often.
• Gaps in $\omega^\omega$ by Marion Scheepers, which deals with the ordering f > g if f(n) - g(n) tends to infinity.

In their settings, Hechler forcing can be used to produce worlds in which there is no scale.

Is the existence of scale (in the context of monotone codings of integers) independent of set theory?

Codings and series

Some easy reductions connect our problem with problems involving convergent series and divergent series satisfying some extra conditions, which stem from our monotonicity requirements; the key is Kraft's inequality, stating that a code with codeword lengths w_i exists iff the sum $\sum 2^{-w_i}$ converges.

The reductions are most easily stated if we extend our posets with some equivalence relation. We then say that two posets are interlacing if there are two order-preserving mappings (between the two posets in both directions) which are pseudo-inverses, i.e. their composition sends a point to an equivalent one. Given two interlacing posets, one has a scale iff the other one has a scale.

The following posets are interlacing:

• Arbitrary (non-monotone) codes, with a < b if b is better than a, and a ~ b if |a(n)-b(n)| is bounded.
• Convergent positive series, with a < b if b(n) = o(a(n)), and a ~ b if a(n) = O(b(n)) and b(n) = O(a(n)).
• Divergent positive series (reverse definition of <).

Monotonicity complicates the picture (the corresponding series are no longer arbitrary) but seems necessary, since one can give a non-monotone code with the property that no monotone code is better than it.

Effective and efficient codings

The motivation behind the question is the actual usage of universal codings by computer engineers. New, impractical methods of codings are suggested all the time, but no one seems to have tackled the fundamental question.

This prompts us to ask similar questions for effective (computable) codings.

Can classical recursion theory hierarchies be adapted to the setting of codes?

It would be nice to get an analog of the fast-growing hierarchy, for example.

We could further wonder what happens if we ask our coding procedure to be efficient, for example linear-time computable.