domain: math info

text:
George Barmpalias
email: barmpalias@gmail.com

Alexander Shen
email: alexander.shen@lirmm.fr

The Kučera-Gács Theorem Revisited by Levin

. Then we review the previous work about the oracle use when reducing a given sequence to another one, and its connection with algorithmic dimension theory.

The Kučera-Gács Theorem

The Kučera-Gács theorem [START_REF] Kučera | Measure, Π 0 1 -classes and complete extensions of PA[END_REF][START_REF] Gács | Every sequence is reducible to a random one[END_REF] says that every (infinite) sequence of zeros and ones is Turingreducible to some Martin-Löf random sequence. In other words, for every sequence α there exist a Martin-Löf random (with respect to the uniform Bernoulli distribution) sequence ω and a computable mapping T of the space of binary sequences to itself such that T ω = α.

Let us comment on the notions used in the statement. The notion of Martin-Löf random sequence was defined by Martin-Löf in 1966 [START_REF] Martin-Löf | The definition of random sequences[END_REF] and since then has become a standard notion in algorithmic randomness (see, e.g., [START_REF] Li | An introduction to Kolmogorov complexity and its applications[END_REF][START_REF] Downey | Algorithmic Randomness and Complexity[END_REF][START_REF] Nies | Computability and Randomness[END_REF][START_REF] Shen | Kolmogorov complexity and algorithmic randomness[END_REF]).

To define computable mappings, consider an oracle machine that has read access to an infinite bit sequence on the input tape and writes bits sequentially on the output tape. It computes a mapping T with domain Ω (the space of all infinite binary sequences) and codomain Σ (the space of all finite and infinite sequences). Mappings that correspond to oracle machines are called computable.

The proofs given by Kučera and Gács (as well as their subsequent improvements that limit the number of input bits needed to produce n output bits, see below) all follow the same scheme: given α, we construct some random sequence ω and some ad hoc mapping T that maps ω to α but has no meaning outside this context. However, there is an alternative approach. There is an image randomness theorem (see, e.g., [START_REF] Shen | Kolmogorov complexity and algorithmic randomness[END_REF], or [START_REF] Bienvenu | Layerwise computability and image randomness[END_REF] for more general version) that says that for a computable mapping T that maps a uniform Bernoulli distribution P on Ω to some probability distribution Q on Ω (this means that T (ω) is infinite for P-almost all ω), every sequence that is random with respect to Q = T (P) is a T -image of some P-random sequence. The alternative plan is to find some extension of this result to the case where the image measure T (P) is a semimeasure, and then derive the Kučera-Gács theorem from this extended version.

Let us explain this plan and the notion of a semimeasure in more details. Consider an arbitrary computable mapping T : Ω → Σ. Applying T to a random uniformly distributed point ω in Ω, we get some random variable ξ = T (ω) with values in Σ. For every string x we may consider the probability of the event "ξ starts with x". We get some non-negative real function M T (x) defined on all strings. Obviously, M T (Λ) = 1 for the empty string Λ, and

M T (x) M T (x0) + M T (x1) ( * )
for every string x. The last inequality may not be an equality; the difference

M T (x) -M T (x0) -M T (x1)
is the probability of the event "ξ is finite and equals x" (since it corresponds to the cases when x is a prefix of ξ but neither x0 nor x1 are).

The non-negative functions M on strings that have value 1 on the empty string and satisfy the inequality ( * ), are called semimeasures and correspond to arbitrary probability distributions on Σ; we often use the same letter for the probability distribution on Σ and the corresponding function on strings. One may ask which semimeasures can be obtained as M T for a computable mapping T , as described above. This question was answered by Levin in 1970 [START_REF] Zvonkin | The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms[END_REF]: the function M should be lower semicomputable. This means that the set of pairs r, x where x is a string and r is a rational number smaller that M(x), is (computably) enumerable.

In the same paper Levin noted that there exists a maximal (up to O(1)-factor) function in the class of lower semicomputable semimeasures; it is now called the continuous a priori probability.

More precisely, there are many such functions that differ by O(1)-factors; we fix one of them and denote it by M(x). The continuous a priori probability M(x) can be used to characterize randomness with respect to computable measures on Ω. Let Q be a computable measure on Ω, i.e., a lower semicomputable semimeasure such that all finite strings have probability zero:

Q(x) = Q(x0) + Q(x1)
for all x. Levin proved in [START_REF] Levin | On the notion of a random sequence[END_REF] that a sequence α is Martin-Löf random with respect to Q if and only if the ratio M(x)/Q(x) is bounded for all prefixes x of α. The intuitive meaning: α is not random with respect to Q if some prefixes of α are much more likely according to the a priori distribution M than according to Q (the ratio is unbounded).

Combining this characterization of randomness with the image randomness theorem mentioned above, we come to the following result.

Proposition 1. Let P be the uniform Bernoulli distribution on Ω. Let T : Ω → Σ be a computable mapping such that T (ω) is infinite for P-almost ω, and let Q = T (P) be the image distribution.

Then the following properties of an infinite sequence α are equivalent:

• M(x)/Q(x)
is bounded for all prefixes x of α;

• α = T (ω) for some Martin-Löf random (with respect to P) sequence ω.

If we could get rid of the restriction that T (ω) is infinite for almost all ω, thus extending this proposition to the case when Q is a semimeasure, the Kučera-Gács theorem will follow from this generalization. Indeed, the semimeasure M (being semicomputable) can be represented as T (P) where T is some computable mapping of Ω to Σ. Then M(x)/Q(x) = 1 is bounded everywhere, and this (hypothetical) generalization would imply that every sequence α is T (ω) for some random ω.

Levin's approach

However, this plan does not work: as found in [START_REF] Bienvenu | Randomness and semimeasures[END_REF], this generalized statement is not true. Levin [START_REF] Levin | Notes for Miscellaneous Lectures[END_REF] found a way to overcome these difficulties by using a less general statement. Namely, he made the following three observations The claim means that the n first bits of T (ω) depend only on 2n + O(1) bits of ω. In particular, if T (ω) has length less than n, then the same is true for all T (ω ′ ) if ω ′ and ω have the same first 2n bits.

Proposition 4. Let T : Ω → Σ be a computable mapping that uses only the first 2n + O(1) input bits to produce n output bits. Let P be the uniform Bernoulli distribution on Ω and let Q = T (P) be the image semimeasure. If the ratio M(x)/Q(x) is bounded for all prefixes of some infinite sequence α, then α = T (ω) for some Martin-Löf random (with respect to P) sequence ω.

Proof of Proposition 2. We may perform rounding and replace each value on some n-bit string by the maximal (2n + c)-bit binary fraction that is strictly smaller than this value. Here c is some constant that will be chosen later. This procedure gives a lower semicomputable function (here it is important that we use strict inequalities) with required granularity, but this function may not be a semimeasure. The property

Q(x) Q(x0) + Q(x1)
may be violated after rounding. Indeed, while the right-hand side may only decrease after rounding (and this is not a problem), the left-hand side also may decrease making the inequality false.

The change in the left-hand side is at most 2 -2n-c (where n = |x|), so a small safety margin is enough: if

Q(x) Q(x0) + Q(x1) + 2 -2n-c ,
then after rounding we have a semimeasure. (We should also change the value on the empty string to 1, but this change does not violate the other requirements.)

To guarantee this safety margin, we add to the maximal semimeasure M some other semimeasure with desired safety margin. (Then we have to divide the sum by 2 to get a semimeasure, but this only increases c by 1.) For example, the semimeasure

Q(x) = 2 -2|x| has safety margin 2 -2n -2 • 2 -2n-2 = 2 -2n-1
for n-bit strings, so for c 1 this is enough.

We need also to check that our semimeasure remains maximal after rounding. Indeed, the safety margin is bigger than the granularity, and the combined effect of the increase and rounding can only increase the value of the semimeasure.

Proof of Proposition 3. Here we have to recall the construction of the mapping for a given semimeasure (see [START_REF] Zvonkin | The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms[END_REF] or [31, Section 5.1] for details). This construction is performed in terms of space allocation. Assume that some semimeasure Q is given. For every string x of length n, we allocate to x some subset of Ω that is a union of cones (a cone Ω y is a set of all infinite sequences with a given finite prefix y) and has total measure Q(x). If Q(x) is a multiple of 2 -2n-c , we may use cones Ω y of size 2 -2n-c (with |y| = 2n + c) when allocating space to x. Since 2n + c is a monotone function of n, for the children of x we may use smaller cones inside the cones allocated to x. In this way we get a mapping where n output bits are determined by 2n + c input bits: the preimage of x is the union of cones allocated to x, and all these cones have size 2 -2n-c , so only the first 2n + c bits matter. 2Proof of Proposition 4. This proposition can be proven in different ways; for example, one can adapt the argument from [31, Section 5.9.3]. Levin gives a much simpler argument, but it uses the characterization of Martin-Löf randomness in terms of expectation-bounded randomness tests that were introduced by Levin in [START_REF] Levin | Uniform tests of randomness[END_REF] and then studied in [START_REF] Gács | Exact expressions for some randomness tests[END_REF] (and probably are not as well known as they deserve to be). We recall their definition and properties that we need (see [START_REF] Shen | Kolmogorov complexity and algorithmic randomness[END_REF]Section 3.5] and [START_REF] Bienvenu | Algorithmic tests and randomness with respect to a class of measures[END_REF] for a detailed exposition).

We consider lower semicomputable non-negative real functions on Ω (the infinite value +∞ is also allowed). The notion of lower semicomputability is an effective version of lower semicontinuity: function f is lower semicomputable if the set of pairs { r, ω : r < f (ω)} (where r is a rational number and ω ∈ Ω) is an effectively open set in Q × Ω (a union of an enumerable family of basic open sets of the form (p, q) × Ω u , where p < q are rational numbers and u is a binary string).

The sum of two lower semicomputable functions is lower semicomputable; the same is true for an (effectively given) series of semicomputable functions. A average-bounded randomness test is a lower semicomputable function whose integral (in other words, average, or expected value) over Ω (with uniform measure P) is finite. Taking a mix of all average-bounded randomness tests, we get a maximal, or universal average-bounded randomness test. It is defined up to O(1)-factors; we denote it by t and may assume that E P t < 1 (the expectation is less than 1). Now Martin-Löf random sequences can be equivalently defined as sequences ω ∈ Ω such that t(ω) < ∞.

Every non-negative integrable function on Ω (with finite integral) is a density function of some measure on Ω, so we construct a measure τ and let τ(X ) = X t(ω) dP(ω). The measure τ(Ω) of the entire space Ω is Ω t < 1. We can transform this measure into a lower semicomputable semimeasure by artificially declaring t(Λ) = 1 for the corresponding function on strings. 3Now we are ready to prove Proposition 4. In addition to Q = T (P) we consider the image measure M ′ = T (τ). It is easy to check that this measure also can be extended to a lower semicomputable semimeasure, and therefore it is does not exceed cM for some constant c.

Recall our assumption: the ratio M(x)/Q(x) is bounded for all prefixes x of α. Let c ′ be this bound, so M(x) c ′ Q(x) for all prefixes x of α. Combining this with the previous inequality, we conclude that M ′ = T (τ) cM cc ′ Q. Now let us look more closely at the values of M ′ (x) and Q(x) for some x that is a prefix of α. Since M ′ = T (τ) and Q = T (P), both values are (different) measures of the set U = T -1 (Ω x ), the set of all sequences that are mapped by T into some extensions of x. The first is τ(U) = U t(ω) dP(ω), the second is just P(U ). The inequality M ′ < cc ′ Q implies that there exists a sequence ω ∈ U (in other words, T (ω) starts with x) such that t(ω) cc ′ . We denote this sequence by ω x indicating that this sequence depends on x (while constants c and c ′ do not depend on x).

Taking longer and longer prefixes x of α, we get an infinite sequence of corresponding ω x . We know that t(ω x ) cc ′ for all ω x , and that T (ω x ) starts with x. Let x i be the prefix α that has length i, and let ω i = ω x i be the corresponding sequence. Using compactness, we take a limit point ω of the sequence ω i . Let us show that ω is a sequence that we need: a random sequence such that T (ω) = α. Indeed, ω is random since the set of all sequences ξ such that t(ξ ) cc ′ is closed (since t is lower semicomputable and therefore lower semicontinuous). And for every prefix x the corresponding set

U = T -1 (Ω x )
is not only open (as it will be for any computable mapping) but also closed due to our assumption (n output bits are determined by 2n + O(1) input bits), and contains all ω i starting from i = |x|, and therefore all limit points of the sequence ω 0 , ω 1 ,. . . . Proposition 4 is proven.

3 Remarks about Levin's argument

Stronger versions

We formulated Propositions 2-4 in the simplest form that is enough for the Kučera-Gács theorem. Levin's formulations are stronger.

Proposition 2. Here we may easily replace 2n by n

+ d(n) where d(n) is a computable function such that ∑ 2 -d(n) 1.
For that we use the safety margin 2 -n-d(n) for strings of length n, and the total additional weight is ∑ 2 -d(n) , since we have 2 n strings of length n with weight 2 -n-d(n) each. Moreover, Levin notes that we may let the granularity depend not only on the length of x, but on x itself, using K(x) + O(1) bound:

There exists a constant c and a maximal (up to O(1) factor) lower semicomputable semimeasure whose value at every string x is a finite binary fraction having at most K(x) + c bits.

To prove this, we use m(x) = 2 -K(x) (where K(x) is the prefix complexity of x) to provide a safety margin for string x. Consider a semimeasure S(x) = ∑ x y m(y), where the sum is taken over all strings y that have x as a prefix. As usual, we let S(Λ) = 1 to get a semimeasure. The semimeasure S corresponds to the following process: generate a finite string according to m, and stop (so S is concentrated on finite sequences).

Now consider the average M

′ (x) = [M(x) + S(x)]/2, where M is a maximal lower semicom- putable semimeasure. It is maximal up to an O(1) factor (since M is maximal). The safety margin M ′ (x) -M ′ (x0) -M ′ (x1)
for rounding is at least m(x)/2 (thanks to S). Let us then round M ′ (x) up to K(x) + c bits, for some large enough constant c: let M(x) be the maximal integer multiple of 2 -K(x)-c that is strictly smaller than M ′ (x) (and M(Λ) = 1, as usual).

For large enough c the safety margin m(x)/2 exceeds the rounding errors, so M is a semimeasure. However, some care is needed to show that M is lower semicomputable. The problem is that we cannot compute the value of K(x), we have only the approximations from above for K(x) that can decrease at any time. To construct the approximations from below to M, we consider the current approximation k for K(x) and take the maximal multiple of 2 -k-c that is strictly less than the current approximation from below to M ′ (x). At some point k reaches the final value, i.e., K(x), so the sequence converges to the maximal multiple of 2 K(x)-c that is strictly smaller than M ′ (x). However, we need the sequence of approximations to be increasing, and now this is not obvious, since k can decrease, and bigger granularity may lead to smaller approximations.

To achieve the monotonicity, we synchronize the increases in the approximations for m(x) and the corresponding increases in the approximations for M ′ (x) with decreases in k. If c is large enough, the increase in M ′ compensates the effects of increased granularity, and this finishes the argument.

For Proposition 3 we may replace 2n • the probability of the event "T (ω) starts with x" equals Q(x);

• the set of all ω such that T (ω) starts with x, is a union of intervals of size

2 -t(x) .
Proving this stronger version of Proposition 3, we may again assume that the growing approximations for Q(x) are multiples of 2 -t(x) for strings x where t(x) is defined (the other values of Q are not used). Then we inductively construct the T -preimage of Ω x as a union of intervals of size 2 -t(x) , choosing those intervals inside the intervals for the parent of x. Note that t(x0) and t(x1) may be different, and we may have to allocate space for x0 (intervals of size 2 -t(x0) ) knowing only the values of t(x) and t(x0) but not t(x1), or vice versa. For that we start filling an interval of size 2 -t(x) by intervals of size 2 -t(x0) from left to right, and by intervals of size 2 -t(x1) from right to left; when there is not enough space for the next interval in some direction, we continue in the same direction in the other interval of size 2 -t(x) (and use the remaining space in the first interval, if there is some, for the other direction).

Proposition 4 can be generalized in the following way (and the proof remains essentially unchanged):

Let t be a computable partial function on strings whose domain is a subtree. Let T be a computable mapping Ω → Σ, and for every x in the domain of t the event "T (ω) starts with x" is a union of intervals of size 2 -t(x) . Let P be the uniform distribution on Ω and let Q = T (P) be the image semimeasure. If all prefixes of some infinite sequence α are in the domain of t and the ratio M(x)/Q(x) is bounded for them, then α = T (ω) for some Martin-Löf random (with respect to P) sequence ω.

Combining these observations, we get an improved version of the Kučera-Gács theorem:

If t(x) is a partial computable function that is an upper bound for K(x) (where defined) such that the domain of t is a subtree and t(x) t(x0) and t(x) t(x1) if

both sides are defined, then for every infinite sequence α whose prefixes belong to the domain of t there exists a Martin-Löf random sequence ω and a machine M that computes α given oracle ω and uses at most t(x) + O(1) bits of ω when producing a prefix x of α.

The last statement means that machine M produces the same prefix x when applied to every infinite sequence that has the same t(x) first bits as the sequence ω.

Levin states this results for total t, but we give its natural generalization to compare Levin's argument with some other line of research discussed in the next sections: the monotonic compression.

Partially continuous transformations

This notion (used by Levin in [START_REF] Levin | Notes for Miscellaneous Lectures[END_REF]) is a generalization of the notion of an oracle machine, and a notion of a (monotone) computable operation defined by him in [START_REF] Levin | On the notion of a random sequence[END_REF]. Informally speaking, an oracle machine uses the bits from the oracle tape to produce output bits: the more it knows about the input, the more output bits are produced. If we want to consider finite and infinite inputs, we arrive to the notion of a (monotone) computable operation. Now Levin makes the next generalization step: a partially continuous transformation provides more information about the output if given more information about the input. Such a transformation is an effectively closed set in Ω × Ω and can be defined by a computable sequence of statements of the following form: "if the input sequence belongs to this cone, then the output sequence cannot belong to that cone". In this way we can do more than just specify output bits sequentially: transformation may say, for example, that 7th bit is zero or that 5th and 16th bits are equal without claiming anything about other bits.

The notion of partially continuous transformation is natural in itself, but is not strictly necessary for the argument: we may consider only oracle machines (as usual) and semimeasures defined on finite strings (and not on arbitrary clopen subsets of Ω).

Oracle use and compression

One may ask what could be the finite version of the Kučera-Gács theorem. The natural candidate says that every (finite) string x can be computed by a simple program f from a random string y. This is true for obvious reasons: let y be the shortest description of x (so the length of y equals the Kolmogorov complexity of x), and let the simple program f be the decompressor used in the definition of Kolmogorov complexity. One can check easily that the shortest description is incompressible, so we get the desired result.

Can this approach be used for the Kučera-Gács theorem? Here we have some infinite sequence α. We may find the shortest descriptions for all the prefixes of α, but these shortest descriptions may be unrelated to each other and are not necessarily prefixes of one sequence. We need some other type of compression where the compressed version is a sequence ω and its prefixes are used by the decompressor to produce prefixes of α. The natural definition of this type was suggested by Kobayashi [START_REF] Kovayashi | On compressibility of infinite sequences[END_REF]. Consider a sequence α that is computed by an oracle machine that has access to oracle ω. For every n, we consider the prefix of ω that is used while computing the first n bits of α. (We may assume that α is printed bit by bit on the write-only one-directional output tape while ω is provided on a read-only one-directional input tape, so you cannot read some bit of ω without reading all the previous bits.) The length of the prefix of the input tape (as a function of the length of the prefix of the output tape) is called the oracle use 4 when computing α with oracle ω. For example, for an oracle machine that copies input ω to output α = ω bit by bit, the oracle use is the identity function n → n. For a machine that remembers c first bits of α in its program and copies the rest from ω, the oracle use is n → max(0, nc). A similar type of compression was considered by Ryabko in [START_REF] Ya | Coding of combinatorial sources and Hausdorff dimension[END_REF] and [START_REF] Ya | Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity[END_REF].

It would be nice to prove the Kučera-Gács theorem in the following way: for a given (arbitrary) α we find some ω that decompresses into α with minimal oracle use, and then derive from this minimality that ω is random. However, no argument of this type is currently known. What can be done is different: (1) knowing the upper bounds for the complexity of the prefixes of α, we can construct a sequence ω that computes α with bounded oracle use, and then (2) reduce ω to some random ω ′ not increasing the oracle use too much. The composition of these two reductions is an oracle machine that computes α from a random ω ′ with bounded oracle use (thus coming to the same result in a different way).

Let us describe what was done in these two directions, starting with the second one. (Then we will discuss arguments that directly construct a reduction to a random sequence, thus avoiding this two-step procedure.)

Original proofs of Gács and Kučera and their optimal implementations Gács (1986) in [START_REF] Gács | Every sequence is reducible to a random one[END_REF] and [START_REF] Kučera | Measure, Π 0 1 -classes and complete extensions of PA[END_REF] in [START_REF] Kučera | Measure, Π 0 1 -classes and complete extensions of PA[END_REF] showed that every binary sequence can be computed using a random sequence as an oracle, with computable oracle use. The method in [START_REF] Gács | Every sequence is reducible to a random one[END_REF] is more sophisticated, and gives the bound n + O( √ n log n) which is explicitly stated, even in the abstract. 5 What is important here, as soon will be clear, is that the overhead √ n log n is o(n) (small compared to n). The argument in [START_REF] Gács | Every sequence is reducible to a random one[END_REF] can be described as block-coding, where the source α is broken into blocks (the ith block has length i) and each block is coded by the corresponding block of a random ω. In contrast to that, [START_REF] Kučera | Measure, Π 0 1 -classes and complete extensions of PA[END_REF] did not break α into blocks, and coded each bit separately (by a block of a random sequence). As a consequence, [START_REF] Kučera | Measure, Π 0 1 -classes and complete extensions of PA[END_REF] gives significantly larger oracle use. Kučera was not interested in precise or optimal oracle-bounds and, although n 2 is often quoted as the oracle use in this method, Barmpalias and Lewis-Pye [START_REF] Barmpalias | Limits of the Kučera-Gács coding method[END_REF] demonstrated that n log n is the actual oracle use in an optimal implementation of Kučera's construction. It was also demonstrated in [START_REF] Barmpalias | Limits of the Kučera-Gács coding method[END_REF], using the analysis of [START_REF] Merkle | On the construction of effectively random sets[END_REF] from [START_REF] Merkle | On the construction of effectively random sets[END_REF], that the bound n + √ n log n in [START_REF] Gács | Every sequence is reducible to a random one[END_REF] cannot be improved using the same method, by changing the block lengths or other parameters of the construction.

Note that the oracle use in the coding discussed above is oblivious: it does not depend on the source being coded (a sequence that we reduce to a random one). Note also that the we have n + o(n) oracle use; this will be important for the next results. (This bound can be improved, see below; Levin's argument discussed above can also be used to get n + 2 log n + O(1) bound or even better ones.)

How much can we compress a given sequence?

Now we concentrate on the other side of the question: given a sequence α, we want to find some other sequence ω (random or not) and an oracle machine that computes α with oracle ω, with minimal oracle use. What can we achieve, and what are the obstacles for the high compression?

If the n-bit prefix of α (denoted by α ↾n) is computed by a machine with oracle ω, and the oracle use is u n , then the Kolmogorov complexity of this prefix exceeds the complexity of ω ↾u n at most by O(log n), since α ↾n can be computed from n and ω ↾u n :

K(α ↾n) K(ω ↾u n ) + O(log n) u n + O(log n + log u n ).
Therefore, the oracle use has asymptotic lower bounds:

lim inf u n n lim inf K(α ↾n) n , lim sup u n n lim sup K(α ↾n) n .
The quantities in the right hand sides of these inequalities are known in algorithmic dimension theory (see [START_REF] Jack | Dimension in complexity classes[END_REF][START_REF] Mayordomo | A Kolmogorov complexity characterization of constructive Hausdorff dimension[END_REF][START_REF] Jack | The dimension of individual strings and sequences[END_REF][START_REF] Athreya | Effective strong dimension in algorithmic information and computational complexity[END_REF]) as effective Hausdorff dimension dim(α) (the first, one, with lim inf) and effective packing dimension Dim(α) (the second one, with lim sup) of the sequence α. Here we used prefix complexity in the definitions, but one can also use plain complexity C(α ↾n), since plain and prefix complexities differ at most by O(logn) for n-bit strings.

These bounds are tight. For the first bound it was essentially shown by Ryabko in [START_REF] Ya | Coding of combinatorial sources and Hausdorff dimension[END_REF][START_REF] Ya | Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity[END_REF]; his reasoning goes as follows. Assume that lim inf K(α↾n) n < d for some d. Then the sequence α has prefixes of lengths n 1 < n 2 < n 3 . . . such that K(α ↾n i ) < dn i for all i. We may assume without loss of generality that n i grow fast, so n 1 + n 2 + . . . + n i = o(n i+1 ). Then we can concatenate the optimal prefix free descriptions of α ↾n 1 , α ↾n 2 , . . . into an infinite sequence ω. Using ω as oracle, we compute all u↾n i using at most d(n 1 + . . . + n i ) = dn i + o(n i ) bits. This implies that lim inf u n n < d for the oracle usage u n in this oracle computation. It is important that we are use Hausdorff dimension and lim inf; this argument does not give any bound for packing dimensions since we have no way to compute prefixes of α that have intermediate lengths (between n i and n i+1 ) with bounded oracle use. The bound for packing dimension requires a bit more complicated argument that was suggested by Doty [START_REF] Doty | Every Sequence is Decompressible from a Random One[END_REF][START_REF] Doty | Dimension Extractors and Optimal Decompression[END_REF][START_REF] Doty | Dimension extractors and optimal decompression[END_REF]. This argument goes as follows.

Instead of using fast increasing lengths, let us split α into blocks α = a 1 a 2 a 3 . . . in such a way that a i has length i. These blocks are "not too small and not too large" in the following sense:

(1) every prefix of α of length n can be extended to some bigger prefix a 1 a 2 . . . a k of length at most n + O( √ n) ("blocks are not too large"), and, at the same time, k = O( √ n) ("blocks are not too small"). Using the Kolmogorov-Levin formula for complexity of pairs, we note that K(a 1 a 2 . . . a k ) = K(a 1 ) + K(a 2 |a 1 ) + . . .K(a k |a 1 . . . To formulate their results, let us introduce the following definition: A non-decreasing g is fastgrowing if ∑ i 2 -g(i) < ∞, and slow-growing otherwise. Typical examples of slow-growing and fast-growing functions are n → log n and n → 2 log n, respectively.

It was shown in [START_REF] Barmpalias | Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers[END_REF] that for each slow-growing computable g, there exists a sequence α that is not computable (from any random oracle) with oracle use n + g(n). This result seemed quite weak at that time; for example, it does not prevent reductions to a random sequence with overhead as low as 2 log n, in sharp contrast to √ n log n which was known to be the best possible upper bound for the methods used in [START_REF] Gács | Every sequence is reducible to a random one[END_REF][START_REF] Kučera | Measure, Π 0 1 -classes and complete extensions of PA[END_REF]. Surprisingly, this lower bound turned out to be tight.

Optimal oblivious oracle use

Barmpalias and Lewis-Pye (2016) [START_REF] Barmpalias | Optimal redundancy in computation from random oracles[END_REF] matched the lower-bounds of [START_REF] Barmpalias | Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers[END_REF] by showing that, for each computable fast-growing g, every sequence α is reducible to some random one with oracle use n + g(n). So in the oblivious case, a complete characterization of the possible oracle uses in computations from randoms was given in [START_REF] Barmpalias | Optimal redundancy in computation from random oracles[END_REF]. Note that the same result can now be obtained in a different way using Levin's argument, as we have discussed.

It is interesting to note that the same characterization applies to the case of computation of leftc.e. reals by random left c.e. reals: this was already established in [START_REF] Barmpalias | Optimal asymptotic bounds on the oracle use in computations from Chaitin's omega[END_REF] and motivated reaching the optimal overheads of [START_REF] Barmpalias | Optimal redundancy in computation from random oracles[END_REF], although they were significantly smaller than known ones at the time. 6As an algorithm, the coding in [START_REF] Barmpalias | Optimal redundancy in computation from random oracles[END_REF] is greedy and, in a sense, straightforward. The correctness proof, however, is more sophisticated than in the previous arguments due to its global character. Without getting into specifics, we can demonstrate the difference between [START_REF] Barmpalias | Optimal redundancy in computation from random oracles[END_REF] and the original argument from [START_REF] Gács | Every sequence is reducible to a random one[END_REF][START_REF] Kučera | Measure, Π 0 1 -classes and complete extensions of PA[END_REF] by exposing a key injectivity property of the code-map that exists in the older methods (making their verification easier) and is missing in [START_REF] Barmpalias | Optimal redundancy in computation from random oracles[END_REF].

Differences in oblivious coding methods

The proofs of the Kučera-Gács theorem (both in [START_REF] Gács | Every sequence is reducible to a random one[END_REF][START_REF] Kučera | Measure, Π 0 1 -classes and complete extensions of PA[END_REF] and [START_REF] Barmpalias | Optimal redundancy in computation from random oracles[END_REF]) construct some oracle machine Φ such that for every α there exists some random ω such that Φ(ω) = α. Moreover, this random ω has bounded randomness deficiency: we fix an effectively open set V of small measure that contains all non-random sequences (e.g., some level of the Martin-Löf's randomness test) and ensure that for every α there is some ω / ∈ V such that Φ(ω) = α.

All these proofs (in [START_REF] Gács | Every sequence is reducible to a random one[END_REF][START_REF] Kučera | Measure, Π 0 1 -classes and complete extensions of PA[END_REF] as well as in [START_REF] Barmpalias | Optimal redundancy in computation from random oracles[END_REF]) have the following injectivity property: for each α there exists a unique ω / ∈ V such that Φ(ω) = α. If u n is the oracle use in this proof, the machine Φ uses only the first u n bits of ω when computing the first n bits of α. So we get some mapping of u n -bit strings to n-bit strings. For the construction from [START_REF] Kučera | Measure, Π 0 1 -classes and complete extensions of PA[END_REF] this mapping on finite strings is also injective (local injectivity): if α ′ has the same first n bit as α, and ω and ω ′ are oracle sequences that let Φ compute α and α, then ω and ω ′ share the same first u n bits. The construction in [START_REF] Kučera | Measure, Π 0 1 -classes and complete extensions of PA[END_REF] can be vaguely described as follows: we embed sparsely the full binary tree (where α is one of the branches) into a full binary tree, mapping nodes of height n to nodes of height u n from which they could be decoded. When the effectively open set V shadows some part of the embedded tree, we restore this part inside the space that is still available; this is possible since the embedding is sparse. The sequence ω is then the image of α under the limit embedding.

The construction in [START_REF] Gács | Every sequence is reducible to a random one[END_REF] improves the oracle use by grouping bits of α in blocks (nth block has length n). This replaces the binary tree for α by a tree when nodes of height n have 2 n children; this tree is then sparsely embedded in the full binary tree. This construction uses space more efficiently; the local injectivity holds for n that are the block boundaries.

The construction in [START_REF] Barmpalias | Optimal redundancy in computation from random oracles[END_REF] is quite different and very far from being locally injective: a single source-string α ↾n may have unpredictably many random code-strings, all of which are necessary for making the induced map on the infinite sequences surjective: different ω ↾u n may be needed for different α with the same α ↾n. One could conjecture that this is necessary to get oracle use u n = n + O(log n). In the words of Kučera 7 , this type of coding is global in contrast to [START_REF] Gács | Every sequence is reducible to a random one[END_REF], [START_REF] Kučera | Measure, Π 0 1 -classes and complete extensions of PA[END_REF] which is local.

Let us note that Levin's construction is not even globally injective.

Toward the optimal adaptive oracle use.

A natural conjecture is that for each α there exists a random ω which computes α with oracle use at most K(α ↾n). Note that K(α ↾n) does not have the form of an oracle use function as it is not monotone, but we could consider instead the monotone function min i n K(α ↾i). (We may also try to compare the oracle use with monotone or a priori complexity; both are monotone.)

As we have seen, this question also makes sense without the requirement for ω to be random. (Then we add a second layer that uses the oblivious encoding considered above, as we have discussed.) Note that this bound is much stronger than the results of [START_REF] Ya | Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity[END_REF][START_REF] Doty | Dimension extractors and optimal decompression[END_REF], where all the bounds are up to o(n).

So why one would make such a strong guess? Here we bring up the analogy with the case of computing left-c.e. reals from random one, as we did in the case of the oblivious oracle use: 8Barmpalias and Downey (2017) [START_REF] Barmpalias | Kobayashi compressibility[END_REF] showed that every left-c.e. real α is computable by Chaitin's Ω (and any other random left-c.e. real) with oracle use min i n K(α ↾i). This conjecture remains unproven; two partial results in this direction were obtained by Barmpalias and Lewis-Pye (2019) in [START_REF] Barmpalias | Compression of data streams down to their information content[END_REF]. The first says that if K * is a partial computable function that is an upper bound for K (at the points where K * is defined), then every sequence α such that K * is defined on all prefixes of α, is computable from some random sequence with oracle use min i n K * (α ↾i). The argument used in [START_REF] Barmpalias | Compression of data streams down to their information content[END_REF] is based on some version of Kraft-Chaitin lemma that extends it to hierarchical space allocation requests. It directly constructs a random sequence ω that computes α with bounded oracle use (avoiding the two-step procedure described earlier and the corresponding overhead).

Note that K * has to be computable, while K is only upper semicomputable (and also nonmonotonic). This presented certain issues in the argument of [START_REF] Barmpalias | Compression of data streams down to their information content[END_REF], if we want to get an upper bound for oracle use in terms of K. They were only resolved by adding a logarithmic overhead: it is shown in [START_REF] Barmpalias | Compression of data streams down to their information content[END_REF] that every sequence α is computable from some random sequence with oracle use min i n [K(x↾i) + logi].

Both results come quite close to the conjecture formulated above, but the question whether the conjecture is true, remains open.

  a k-1 ) + O(k log |a 1 . . . a k |). Here K(u|v) stands for (prefix) conditional complexity of u given v; the logarithmic errors in k applications of the Kolmogorov-Levin formula are accumulated in the O(k log |a 1 . . . a k |) term.

  1

  + O(1) by arbitrary total computable non-decreasing function. The computability is needed to make the construction effective, and the function should be non-decreasing since we need to allocate intervals for x0 and x1 inside the intervals already allocated for x. (It seems that this requirement is not mentioned in [21, last paragraph of Section 7.1], but it is not clear how we can proceed without it.) We may also use a total computable function t(x), depending on the string x, not only on its length, if t(x) t(x0) and t(x) t(x1) for all strings x. Moreover, we may consider also partial computable functions t.

Let t be a computable partial function on strings, with natural values. Assume that the domain of t is a subtree (if t(x) is defined, then t(y) is defined for all prefixes y x), and inequalities t(x) t(x0) and t(x) t(x1) hold when both sides are defined. Let Q be a lower semicomputable semimeasure. Assume that Q(x) is an integer multiple of 2 -t(x) for all strings x in the domain of t. Then there exist a computable mapping T : Ω → Σ such that for every x where t(x) is defined, the following properties hold:

We first provide them in a simplified form that is enough for the Kučera-Gács theorem; see the next section for discussion.

A technical clarification: this argument assumes that the approximations to Q(x) are also multiples of 2 -2n-c . This can be achieved by rounding the approximations to the closest binary fraction with 2n + c bits; one could also note that the construction provided by Proposition 2 already has this property.

This semimeasure has a natural interpretation. Namely, the exact expression (see[START_REF] Gács | Exact expressions for some randomness tests[END_REF][START_REF] Bienvenu | Algorithmic tests and randomness with respect to a class of measures[END_REF]) for t says that it corresponds (up to a O(1)-factor) to the following random process: we first generate a finite string according to discrete a priori probability and then start adding random bits. But this is not important for the argument.

Technically speaking, this notion of oracle use is a bit more restrictive than before, when we required that n output bits depend only on some number of oracle bits: it may happen that machine reads more bits than it is actually necessary to determine the output bits. For example, the machine can copy its input to its output and read 2n input bits before producing n output bits. Moreover, one can construct a machine whose oracle use in the previous sense is smaller than the oracle use (in the new sense) for every machine computing the same mapping Ω → Σ. Indeed, let x 0 , x 1 , x 2 , . . . be a computable prefix-free sequence (say, x n = 0 n 1), and let P and Q be two inseparable enumerable sets of natural numbers. Consider the mapping T : Ω → Σ that maps all sequences with prefix x i 0 to x i 0 for every i; if i ∈ P, all sequences with prefix x i 1 are also mapped to x i 0; if i ∈ Q, all sequences with prefix x i 1 are mapped to x i 1. If i ∈ P, the prefix x i is enough to guarantee the output x i 0; if i ∈ Q, one needs to read the bit after x i to produce the correct output. Assume that some machine M computes T ; then, if it does not read the bit after x i for i ∈ P, we can separate P and Q by looking whether M reads more bits after x i or not.However, Levin's arguments (and the results mentioned below) can be adapted to this stronger notion in the same way as in[START_REF] Shen | Kolmogorov complexity and algorithmic randomness[END_REF] Theorem

50, p.86].[START_REF] Barmpalias | Limits of the Kučera-Gács coding method[END_REF] Gács[START_REF] Gács | Every sequence is reducible to a random one[END_REF] gives n + 3 √ n log n, which can be refined to n + √ n log n, as shown in[START_REF] Barmpalias | Limits of the Kučera-Gács coding method[END_REF].

We will come back to this while discussing the optimal adaptive coding into random sequences.

Said during the workshop Algorithmic Randomness Interacts with Analysis and Ergodic Theory at the Banff International Research Station for Mathematical Innovation and Discovery (BIRS), of Casa Matemática Oaxaca, December 2016.

This is only a heuristic argument; there is no deeper reason why the bounds for the left-c.e. reals would match

Supported by NSFC grant No. 11971501.

Coding method

Oracle use [START_REF] Kučera | Measure, Π 0 1 -classes and complete extensions of PA[END_REF] [START_REF] Kučera | Measure, Π 0 1 -classes and complete extensions of PA[END_REF] n log n [START_REF] Gács | Every sequence is reducible to a random one[END_REF] [START_REF] Gács | Every sequence is reducible to a random one[END_REF] n + √ n log n Ryabko (1986) [START_REF] Ya | Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity[END_REF] and [START_REF] Doty | Dimension extractors and optimal decompression[END_REF] [START_REF] Doty | Dimension extractors and optimal decompression[END_REF] in n • dim(α), n • Dim(α)

Barmpalias and Lewis-Pye (2016) [START_REF] Barmpalias | Optimal redundancy in computation from random oracles[END_REF] n + g(n) for any fast-growing g T 0

Barmpalias, Lewis-Pye, Fang (2016) [START_REF] Barmpalias | Optimal asymptotic bounds on the oracle use in computations from Chaitin's omega[END_REF] any fast-growing g T 0, if α is c.e.

Barmpalias and Downey (2017) [START_REF] Barmpalias | Kobayashi compressibility[END_REF] min i n K(α ↾i) if α is left-c.e. α is considered as a set of integers when we assume that α is computably enumerable (c.e.), and as a real when we assume that α is left computably enumerable.) In all the constructions, except for Ryabko's and Doty's ones, a reduction to random oracle is directly provided; in these two constructions an additional layer is needed.

Consider now the shortest prefix-free description w i for a i given a 1 . . . a i-1 , and a sequence ω = w 1 w 2 w 3 . . .. It can be decoded from left to right, and we need

bits to decode a 1 . . . a k . This inequality works only on the block boundaries; for arbitrary prefix of α we need to restore the partially used block completely, but (recall that blocks are not too large) this is again o(n) overhead.

Combining these observations with the Kučera-Gács theorem (with n +o(n) bound for the oracle use), we get the following result from [START_REF] Doty | Every Sequence is Decompressible from a Random One[END_REF]: for every sequence α there exists a Martin-Löf random sequence ω and an oracle machine M that transforms ω to α with oracle use u n such that lim inf

Note that the machine M can be fixed in advance (before α is given): consider the universal oracle machine that first reads some self-delimited description of the other machine and then simulates this machine on the rest of the oracle tape.

Lower bounds on the oracle use

After analyzing the optimal oracle use via the original methods of Kučera and Gács , one may wonder about lower bounds: the amount of the oracle use that is necessary in computations from random sequences. Downey and Hirschfeldt (2010) showed [14, Theorem 9.13.2] that constant overhead is not sufficient: there exist sequences that are not computable from any random sequence with oracle use n + O(1). Barmpalias, Lewis-Pye, Teutsch (2016) obtained better lower bounds in [START_REF] Barmpalias | Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers[END_REF] (and these bounds turned out to be tight, see below).

Coding Type Optimality

Kučera (1985) [START_REF] Kučera | Measure, Π 0 1 -classes and complete extensions of PA[END_REF] oblivious No [START_REF] Gács | Every sequence is reducible to a random one[END_REF] [START_REF] Gács | Every sequence is reducible to a random one[END_REF] oblivious optimal rate Doty (2008) [START_REF] Doty | Dimension extractors and optimal decompression[END_REF] adaptive optimal rate

Barmpalias and Lewis-Pye (2016) [START_REF] Barmpalias | Optimal redundancy in computation from random oracles[END_REF] oblivious optimal

Barmpalias, Lewis-Pye, Fang (2016) [START_REF] Barmpalias | Optimal asymptotic bounds on the oracle use in computations from Chaitin's omega[END_REF] oblivious optimal for c.e.

Barmpalias and Downey (2017) [START_REF] Barmpalias | Kobayashi compressibility[END_REF] adaptive optimal for left c.e.

Barmpalias and Lewis-Pye (2019) [START_REF] Barmpalias | Compression of data streams down to their information content[END_REF] adaptive "almost optimal" Table 2: Oracle use for coding by random sequences. The words "almost optimal" mean that there are two results that show that the bound is almost tight, with O(log n) overhead or with computable upper bounds, but the conjecture mentioned above is not proven.

Comparison

We gather the results mentioned above in Tables 1 and2. We see that (for the case of oblivious coding) the optimal oblivious overhead can be obtained by replacing a local injective coding used in [START_REF] Kučera | Measure, Π 0 1 -classes and complete extensions of PA[END_REF][START_REF] Gács | Every sequence is reducible to a random one[END_REF] by some non-local scheme. It seems that non-locality may be necessary even for getting O(log n) overhead.

For the case of adaptive coding, the arguments from [START_REF] Ya | Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity[END_REF][START_REF] Doty | Dimension extractors and optimal decompression[END_REF] also give a large overhead (o(n), but not O(log n), in the case of Doty's argument), that is then combined with additional layer of oblivious coding. This is enough to get the optimal rate. Still the arguments from [START_REF] Barmpalias | Compression of data streams down to their information content[END_REF] give much smaller overhead. The difference between the methods in [START_REF] Barmpalias | Compression of data streams down to their information content[END_REF] and [START_REF] Doty | Dimension extractors and optimal decompression[END_REF] is striking in the case of logarithmic complexity of prefixes when the overhead O( √ n log n) is large compared to the complexity of prefixes. If, for example, K(α ↾n) 3 log n for all n, the new construction gives 3 log n oracle use, while the previous ones gave more than √ n log n.

Let us note also the Levin's construction also gives the result from [START_REF] Barmpalias | Compression of data streams down to their information content[END_REF] for the special case when K * is a monotone computable upper bound for K. (We may always assume without loss of generality that the domain of K * is a tree.) It would be interesting to bridge the remaining gap by any of these techniques, or to modify Levin's argument to get the best currently known bounds.


Alexander Shen

The Kraft-Barmpalias-Lewis-Pye lemma revisited

This note provides a simplified exposition of the proof of hierarchical Kraft lemma proven by Barmpalias and Lewis-Pye [1] and its consequences for the oracle use in the Kučera-Gács theorem (saying that every sequence is Turing reducible to a random one).

Kraft's lemma and its online version

The following statement from coding theory is sometimes called Kraft's lemma 1 : for every n integers l 1 , . . . , l n 1 such that ∑ i 2 -l i 1, there exist binary strings x 1 , . . . , x n of lengths l 1 , . . ., l n that form a prefix-free code.

The prefix-free requirement means that strings x 1 , . . ., x n are incomparable: none of them is a prefix of another one.

It is convenient to identify strings with aligned intervals inside [0, 1]: let 0 be the left half, 01 be the second quarter (i.e., [ 1 4 , 1 2 ]), etc. Formally, a string x corresponds to the interval that contains numbers whose binary representations start with x. Then the statement can be reformulated in terms of space allocation. Each l i is interpreted as the request to allocate an aligned interval inside [0, 1] of length 2 -l i in such a way that all intervals are disjoint. This shows immediately that the condition ∑ 2 -l i 1 is necessary for the existence of the prefix code (the total space is bounded). To prove that Kraft inequality is sufficient, we may allocate the intervals in the order of decreasing length (=increasing l i ), from left to right. The decreasing length condition guarantees correct alignment.

However, this allocation strategy needs to know the entire list l 1 , . . . , l n in advance. A simple change in the allocation strategy makes it on-line (getting the next l i , we choose the next x i and this choice is final). For that, we keep at every moment the representation of the free space as a union of disjoint aligned intervals of different sizes. Initially we have one interval of size 1. When a new l i arrives, we look for an interval of size 2 -l i in the free space list. If there is one, we allocate it (and delete it from the list). If not, we take the minimal larger interval in the free space list, and split it into halves, then one half into two halves, etc., until we get two intervals of size 2 -l i . One of those intervals is allocated, and all other new parts (including the second interval of size 2 -l i ) are added to the free list. The minimality guarantees that there are no intervals of that size already in the list. There is only one remaining question: why the free list contains at least one interval of size at least 2 -l i ? If not, all free intervals are strictly smaller than 2 -l i and have different sizes that are powers of 2, so the sum of their lengths is less than 2 -l i , and that contradicts Kraft's inequality (note that the free space is 1 minus the total length of already allocated intervals).

This algorithm works for infinite sequences as well, so we get a corollary:

For every computable sequence of natural numbers l i 1 such that ∑ i 2 -l i 1, there exists a computable sequence of incomparable strings x i of lengths l i .

This result was used by Chaitin to prove the properties of prefix complexity and appears in his paper with the proof presented above (ascribed to N. Pippenger), see [START_REF] Chaitin | A Theory of Program Size Formally Identical to Information Theory[END_REF]Theorem 3.2,p. 333]. Now it is often called the Kraft-Chaitin lemma.

Later (also for algorithmic information theory purposes) George Barmpalias and Andrew Lewis-Pye generalized this statement to the case of hierarchical requests [START_REF] Barmalias | Optimal redundancy in computations from random oracles[END_REF]. In the rest of this note we try to provide an easy-to-read exposition of this result (based on the discussion at the Kolmogorov seminar on complexity; the metaphor of reselling the space was suggested by Bruno Bauwens).

Kraft-Barmpalias-Lewis-Pye lemma

In the generalized version of Kraft's lemma, formulated and proven by Barmpalias and Lewis-Pye [START_REF] Barmalias | Optimal redundancy in computations from random oracles[END_REF], the requests (still being labeled by natural numbers l i ) are structured hierarchically. When a new request arrives, it may be declared as a son of one of the previous requests. This means that the interval allocated for it should be a part of the father's intervals (instead of being disjoint with all previous intervals). Later this son may get his own sons, etc.

In other words, requests now form a tree. We add a dummy root for this tree; it will become a father of all requests that had no father. Those requests (of level 1, sons of the root) should get disjoint intervals. The requests of level 2 have fathers of level 1 (that appeared earlier), etc. The tree grows when a new request arrives: a new leaf is attached to one of existing vertices (the new request becomes a son of some existing request, or a son of a root, if it had no father). Every tree vertex, including the dummy root, may become the father of a new request.

Formally, each request consists of the natural number l i 1 (its label) and the reference to one of the previous requests or the dummy (root) one. Now we have to say more precisely what kind of objects should be constructed to satisfy these requests. Let us note first that the space allocation would be simple if the total space requested by all the sons of a vertex never exceeded the space requested by the vertex itself. Then we could use Kraft-Chaitin's allocation process (as described above) at every vertex: each vertex v would take care of the requests of all its sons and give them space inside its own space. The only difference is that instead of a unit interval each vertex gets an interval of some size and the requests from its sons do not exceed that size in total. Note that the requests from the grandsons will be fulfilled by their fathers inside the space allocated to them, so v will not need to worry about them.

We have a quite different setting: we do not require that the sum of the requests for sons of some vertex is bounded by the request for the vertex itself. Let us explain the changes needed to adapt the Kraft lemma to this situation.

Recall that the requests form a growing tree, and every request has a non-negative integer label l i that means that an aligned interval of size 2 -l i is requested. The labels l i may be arbitrary: for example, a vertex v can have a son w whose request is bigger than the request for v; or v can have many sons with total requested size bigger than the request for v. The only restriction for the labels is that the total size ∑ 2 -l i is bounded by 1. Note that this sum includes, for example, both the requests from a vertex v and its son w, even if the size of the w-request is small and it can be fulfilled inside v-space. So this condition is much stronger than necessary for the case we discussed (when sons' requests fit into the father's one).

We make the following changes for the hierarchical version of the lemma:

• The allocation process is more complex. Initially for a request with label l i an aligned interval of size 2 -l i is allocated. But later more aligned intervals could be allocated to the same request (to the same vertex of the requests' tree). All these intervals should be of size 2 -l i or bigger. Additional intervals can be allocated at any stage, so the space allocated to a vertex is a (growing) list of disjoint intervals of size at least 2 -l i each.

• We have two requirements for allocations. The first says that the son's space is always inside the father's space: each interval allocated to the son is a part of some interval allocated to the father.

• The second requirement says that brothers have disjoint space: if w and w ′ are sons of some vertex v, then intervals allocated to w should be disjoint with intervals allocated to w ′ .

Note that for the one-layer tree (root and its sons) we get essentially the statement of the original Kraft lemma, because additional allocated intervals are not helpful in any way.

In other words, the generalized allocation process goes as follows: a new request with label l i arrives (thus extending the tree); then a new space (an interval2 of size 2 -l i ) is allocated for this request and some new intervals may be added to the space allocated to other vertices (in fact, this happens only for the tree ancestors of the new request) in such a way that all the conditions mentioned above are satisfied.

Lemma (Barmpalias-Lewis-Pye). A space allocation algorithm that guarantees these properties (assuming that ∑ i 2 -l i 1) exists.

Proof of the Kraft-Barmpalias-Lewis-Pye lemma

The allocation algorithm works in a hierarchical way. In the root vertex we have a Kraft space allocator that works as described above. Each vertex of the first level asks the root for an interval of required size and gets it. If no vertices of the higher level appear, that is all. Vertices of higher level request space from their fathers (so the root allocator does not deal with their requests directly).

It is useful to describe this process in terms of buying and reselling space for a fixed price (aligned interval of size 2 -l costs 2 -l ). If there are no hierarchical requests, we are in the situation of standard Kraft-Chaitin lemma: the root allocator sells space inside [0, 1] to customers (i.e., requests of level 1), keeping the information about remaining free space as a list of disjoint intervals. Initially the root allocator has no money, but owns the entire interval (the free list contains one interval of size 1). Gradually the amount of space in its possession decreases, and the amount of money increases. The sum (space + money) always remains the same [START_REF] Barmalias | Optimal redundancy in computations from random oracles[END_REF]. The root allocator never runs out of space because ∑ 2 -l i 1.

In this case (no hierarchical requests) no reselling is happening, and each customer comes to the root allocator only once. Both things change when hierarchical requests appear. As we mentioned, a request (a node of the requests' tree) of level greater than 1 never talks directly with the root allocator. Instead, it speaks only with its father, who may resell some space bought earlier, or -if neededmay buy more space from its own father and resell all or part of this space to its son. In this scheme a node with label l can sequentially request several intervals from its father, but none of these intervals should be smaller than 2 -l (the size of the original request). Therefore, to satisfy small requests of its sons, a node should aggregate their requests, buying the space in big chunks and reselling it in smaller ones.

Let us note that

• each seller does not make any difference between new and old customers: all requests are processed in the same way;

• a vertex that does not have enough space requests additional space from its father, so one request may trigger a chain of actions (that may propagate to the root).

To finish the proof, we should describe the aggregation algorithm and prove its correctness (this means that no vertex will run out of money or space).

Initially, a request with label l has 2 -l units of money. It uses this money to buy an (aligned) interval of size 2 -l from its father. After that it has no money, only the space. Then it starts reselling the space to its children (when/if they arrive). In this process it may need to buy additional amount of space from the father. Here is the algorithm for the vertex:

• Keep the information about the space you own as the list of disjoint aligned intervals of different sizes; note that the size of this space plus the amount of money you have is always 2 -l , where l is your label.

• If an interval of some size is requested, and an interval of exactly this size exists in the list, then sell this interval (and delete it from the list). The space reserve decreases and the money reserve increases (by the same value, the length of the resold interval).

• If there is no interval of the requested size in the free list, but there is a bigger free interval, then split this bigger interval into two halves, split one half in two halves, etc., until two intervals of the requested size appear. Sell one of them, and keep the other (and all bigger new intervals) in the free list. Again, the space reserve decreases, and the money reserve increases.

• It may happen also that you get a request of size 2 -l or bigger. In this case buy an interval of the requested size from your father and immediately resell it to your son. (Free space and the amount of money remain the same.)

• Finally, it may happen that an interval of size smaller that 2 -l is requested but all free intervals are smaller than the requested one. Since free intervals are of different sizes, this implies that the total amount of the free space is smaller than the requested interval. In this case you are low in space, but high in money: the amount that is missing for buying a new interval of size 2 -l (this missing amount is equal to the size of free space) is smaller than the size (=price) of the requested interval. Use the money reserves plus the customer payment to get a new interval of size 2 -l and split is as before, then give its part to the customer, and put the rest in the free list. (Since the existing free intervals were smaller than the request, the list again will consist of intervals of different sizes.)

In this scheme no cash is injected except for the 2 -l i amounts initially given to the requests, so the root allocator will never run out of space (since ∑ 2 -l i 1). Note that the description of the allocation algorithm does not refer to money at all; all this accounting (similar to what is done sometimes for amortized analysis) is needed only to prove that the root allocator will never run out of space.

The Kraft-Barmpalias-Lewis-Pye lemma is proven.

Remark. We considered the case of binary alphabet. If we have m letters, we get a tree with branching factor m, and the Kraft inequality has the form ∑ m -l i 1. Both the original Kraft-Chaitin argument and the proof of Kraft-Barmpalias-Lewis-Pye lemma can be easily adapted to this case. Now the invariant is that the list of free intervals may contain at most m -1 copies of the intervals of the same size. (For m = 2 we get the previous requirement: all intervals are different.) In this way, the numbers of intervals of each size correspond to the digits in the m-ary representation of the amount of the free space. The allocation algorithm remains essentially the same: if there is an interval of the required size, allocate it; if not, take the minimal bigger free interval and split it into m pieces, then do the same for one of the pieces, etc. This process corresponds to subtracting 1 from m-ary number 100 . . . 0: we get (m -1) new free intervals of all intermediate sizes.

Positive result: efficient coding

The Kraft lemma has a natural interpretation in terms of coding; it allows us to construct a prefix code for k letters with codewords of lengths l 1 , . . . , l k assuming that ∑ k i=1 2 -l i 1. The Kraft-Chaitin lemma extends this result to countably many letters. The Kraft-Barmpalias-Lewis-Pye provides hierarchical coding: we require that codes of some letters are extensions of the code of others letters, so the tree structure of letters should be preserved in the tree of codes. Using the compactness argument, we may get a similar conclusion for infinite branches. Note that the Kraft-Barmpalias-Lewis-Pye lemma is valid both for finite and infinite sequences of requests. In the latter case the requests' tree grows when new requests arrive, and we can consider the limit (infinite) tree of requests which includes all the requests.

Lemma. Assume that the tree of requests has an infinite branch r 1 , r 2 , . . ., where r 1 is the request of the first level, and r i+1 is a son of r i . Then there exists a sequence of strings x 1 , x 2 , . . . such that x i is a prefix of x i+1 for all i, and every x i is one of the codes of r i obtained by Barmpalias-Lewis-Pye construction (and, therefore, the length of x i does not exceed the label of the request r i ).

Note that several strings (intervals) may correspond to the same request r i , and we claim that one can choose one of them (x i ) for every i in such a way that x i is a prefix of x i+1 . This choice is not effective, though.

Proof. Let x i be arbitrary string that is allocated to r i during the construction. Then the corresponding interval is inside the space allocated to r i-1 , so x i has some prefix x i-1 that earlier was allocated to r i-1 . Then we can find some prefix x i-2 of x i-1 allocated to r i-2 , etc.

The only problem is that for different i we get different sequences x 1 , . . . , x i , so we do not get directly an infinite sequence x 1 , x 2 , . . . of strings allocated to r 1 , r 2 , . . .. We need to use compactness argument (König's lemma). Note that every request r i has only finitely many strings allocated to it (at most 2 -l if the label is l). So some x 1 appears for infinitely many i. Choosing this x 1 and retaining only the values of i when this x 1 is used, we then choose some x 2 that appears infinitely many times, etc.

Note that this argument does not provide a computable sequence of x i even if both the sequence of requests and the branch r 1 , r 2 , . . . are computable.

This lemma implies the following result (which was one of the main goals of [START_REF] Barmalias | Optimal redundancy in computations from random oracles[END_REF]) Theorem 1. Let K be a total computable function on binary strings such that ∑ x 2 -K(x) 1. Then there exists an oracle machine M with the following property: for every bit sequence α there exists a bit sequence β such that M computes α with oracle β , and the oracle use when computing the prefix α↾n is at most K(α↾n).

The oracle machine has an input tape where an infinite sequence of zeros and ones (the oracle) is written. The machine reads the input tape bit by bit, while performing some other computations, and writes the output bit sequence (one bit at a time). For a given oracle β the output sequence α may be finite or infinite; for every prefix α↾n of α we consider the number of input bits read up to the moment when n output bits were produces, and this number is called the oracle use.

Proof. Let us consider strings 0 and 1 as two requests of the first level with labels K(0) and K(1); then 00 and 01 are requests of level 2 that are sons of the request 0 and have labels K(00) and K(01); in the same way 10 and 11 are sons of 1, etc. Applying Kraft-Barmpalias-Lewis-Pye lemma, we get a computable sequence of allocations.

Let us first look on the strings allocated to the requests of the first level (0 and 1). They form an enumerable prefix-free set of strings that consists of two disjoint parts: codewords for 0 and codewords for 1. We need to construct an oracle machine that outputs 0 if the oracle has a prefix of the first type, and outputs 1 if the oracle has a prefix of the second type. It would be trivial without the additional requierements (just read the oracle bits and enumerate these two parts in parallel), but we want that the machine does not read any bits after the codeword. To satisfy this additional requirement, we may delay the reading the next bit until some codeword appears that is a proper extension of an already read prefix z of the oracle. If this never happens, either z is a codeword itself (and we will find this out at some point, and produce the output bit as required), or z is not a prefix of any codeword (then we produce no output, and this is the right behavior). If this happens at some point, then we know that (because of prefix-free requirement) z is not a codeword, so we can safely read the next bit, and continue in the same way. (Formally we maintain the following invariant: any proper prefix of the already read part of oracle is not a codeword, see [START_REF] Shen | Kolmogorov Complexity and Algorithmic Randomness[END_REF]Theorem 50,p. 86] for the details.)

After a codeword for 0 or 1 is read, we perform the same operation for the next bit. For example, if the codeword for 0 is read, we are looking for its extensions that are codewords for 00 and 01 in the same way. Theorem is proven.

Remarks.

1. Note that the oracle use is monotone, so the bound implies that the oracle use is at most min i n K(α↾i).

2. The same argument works if K is a partial computable function (with natural values) defined on a subtree of the full binary tree: a new vertex to the requests tree is added when the value of K on the corresponding string is computed. Moreover, if K is a computable finction with an arbitrary domain, we may restrict K to the maximal subtree inside the domain of K (by checking whether K is defined on all prefixes). In this way we get a similar statement where K is an arbitrary partial computable function and we additionally assume that K(x) is defined for all prefixes x of a given sequence α (that can be now finite or infinite).

Contaminated space and reduction to random sequences

A stronger version of Theorem 1 guarantees that the sequence β is Martin-Löf random 3 . According to the definition, the set of all non-random sequences is contained in an effectively open set of arbitrarily small measure. Now we assume that ∑ x 2 -K(x) < 1 (strict inequality) and take an effectively open set U whose measure is smaller than the gap between ∑ x 2 -K(x) and 1. Then we use the same argument with the following stronger version of Barmpalias-Lewis-Pye lemma. Again, we consider a sequence of hierarchical requests. In addition we have a parallel process that enumerates a set of aligned intervals that are considered as "contaminated". So at every moment we have an clopen contaminated subset of the unit interval that increases with time. (Only this subset matters; we do not care how this subset is split into a union of intervals.) We assume that that the contaminated part remains small; namely, we assume that the total size of all the requests plus the size of the contaminated part never exceeds 1.

Lemma. In this case one can arrange the allocation process for all the requests with the following additional requirement: when an interval is allocated, it is not completely contaminated, i.e., is not covered by the part of the contaminated space known at the moment of the allocation.

Remark. Note that the statement of the lemma does not prevent the following cases:

• part of the interval just allocated is contaminated;

• at some later stage the entire interval will get contaminated.

Proof. Let us add to our picture the following insurance service: if an allocated interval (obtained from the father node) turns out to be entirely in the contaminated space at the moment of its allocation, the insurance reimburses you for the amount paid for this interval (i.e., its length), but you cannot use this interval later for reselling. With the insurance money you can then buy another interval of the same length, and if again it turns out to be completely inside the contaminated space, you again get the money back, and then buy one more interval, etc.. This process will stop at some point (since there are only finitely many intervals of the same length).

Note that you cannot get reimbursement later (only at the moment of allocation and only if the allocated interval is completely in the already contaminated zone).

The only thing to check is that the total amount of money paid by all clients during the allocation is at most 1. This money comes from two sources: the initial money the clients have, and the money paid by the insurance. Note that the insurance service never reimburses the same space twice: if an interval is reimbursed, it is blocked for the future use, and neither its owner or his brothers can use it. So when an interval is reimbursed, it is disjoint with all previously reimbursed intervals. Now this lemma can be used to prove the following stronger version of coding theorem: Theorem 2. Let K be a partial computable function on binary strings such that ∑ 2 -K(x) < 1. Then there exists an oracle machine M with the following property: for every bit sequence α such that K(α↾n) is defined for all n, there exists a Martin-Löf random bit sequence β such that M computes α with oracle β , and the oracle use when computing the prefix α↾n is at most K(α↾n).

Note that the inequality is strict here, and the sequence β is guaranteed to be random. This is a strong version of Kučera-Gács theorem saying that every sequence is Turing reducible to a random one; see [START_REF] Barmpalias | The Kučera-Gács theorem revisited by Levin[END_REF] about the (rather long) history of improvements on the oracle use bound in this theorem and related results.

Proof. The proof goes as before, but we start with taking an effectively open set U that covers all non-random sequences and whose measure is small enough, so together with ∑ 2 -K(x) it does not exceed 1. Then we can apply the lemma, using the enumeration of this effectively open set as a generation of contaminated space, and get in the same way the sequence β that computes α. We need to show only that β (the limit sequence) does not belong to U . Assume that β belongs to U ; then some prefix b of β has the corresponding interval completely covered by U (since U is open). Then at some point (as the compactness argument shows) the interval corresponding to b will be completely contaminated. Starting from this moment, all the smaller intervals are also fully contaminated and cannot be allocated. On the other hand, only finitely many prefixes of β are allocated before this moment, so we get a contradiction.

Prefix complexity and oracle use

We assumed that the function K (the upper bound for the oracle use) was computable; the natural question is whether this result can be extended to upper semicomputable functions, or, equivalently, whether a bound with prefix complexity is valid.

This question is mentioned as open in the paper of Barmpalias and Lewis-Pye [2, p. 4484, Conjecture]. Here is the exact statement. Let K be the prefix complexity function (not to mix with italic K that appeared earlier and was a computable upper bound for K).

Let α be an arbitrary sequence. Can we always construct a sequence β and the oracle machine M such that α is computed by M with oracle β and the oracle use for n-bit prefix α↾n of α is bounded by min i n K(α↾i) + c for some c and all n?

More precisely, the statement is that the Kraft inequality mentioned here is necessary and sufficient for the existence of a prefix-free code, see, e.g.,[START_REF] Robert | Information theory and reliable communication[END_REF] Theorem 3.2.1].

Or even several intervals of size at least 2 -l i , though in our construction this would never happen.

From now on we assume that the reader is familiar with algorithmic randomness and Kolmogorov complexity theory; all the needed notions and results can be found, e.g., in[START_REF] Shen | Kolmogorov Complexity and Algorithmic Randomness[END_REF].

It would be interesting to find an easy proof of this result by adapting the arguments explained above.

Acknowledgements

This paper is based on the discussions with George Barmpalias, Bruno Bauwens, Laurent Bienvenu, Michael Raskin, Mikhail Vyalyi and other participants of Kolmogorov seminar on description complexity. I thank the (anonymous) reviewers of the CCR2023 conference for their comments.

Supported by ANR-21-CE48-0023 FLITTLA grant.

A weaker result 4 appears in the same paper as Theorem I.5: it replaces K(α↾i) by [K(α↾i) + log 2 i].

One can consider a stronger conjecture where the bound is replaced by min K(y) over all y that are extensions of α↾n (and not only for prefixes of α). For this stronger conjecture the answer is negative. The counterexample, a sequence α that does not have this property, can be (as proven by Mikhail Raskin, who kindly permitted to include his argument) constructed diagonally. At each step we extend the existing prefix a of α to some longer a ′ preventing some machine M from satisfying the requirement with some constant c. (There are countably many pairs M, c, so we can diagonalize against all of them.) So let us assume that a, M and c are fixed. We want to find some b that extends a and has the following property: machine M cannot compute any infinite extension of b with required bound for the oracle use. To achieve this goal, we select some computable infinite sequence that starts with a (for example, we can write all zeros after a) and let a ′ be a long prefix of this sequence whose prefix complexity is negligible compared to length. (To specify the prefix of a computable sequence, we use finitely many bits to specify the program, and the remaining bits are used to specify its length that can be very large compared to the complexity.)

Now K(a ′ ) is fixed, and we may try all strings of size K(a ′ ) + c as oracles for machine M. Each of them computes some sequence (finite or infinite), and we compare all these sequences with a and a ′ . Several cases are possible:

• Some of these sequences do not go through a at all.

• Some of them start with a and then stop or deviate from a ′ .

• Finally, some other could reach a ′ .

In any case, since there are many prefixes between a and a ′ , one can find some a ′′ with the following property: any program that reaches a ′′ , makes one more step in the direction of a ′ . Then finally we let b be the extension of a ′′ that deviates from the path to a ′ .

The chosen b has the required property. Let β be any infinite extension of b. Assume that M computes β with some oracle α with the bounded oracle use. Since a ′′ is a prefix of β and at the same time prefix of a ′ , the oracle use for a ′′ should be at most K(a ′ ) + c. But all oracles that compute a ′′ with this oracle use, compute also the next bit of a ′ and therefore are unsuitable for b.

Remark. A more accurate accounting disproves a weaker conjecture where min K(y) over all extensions of α↾n is replaced by min[K(y) + 0.99 log |y|] over the same extensions. Indeed, we need that the number of possible oracle prefixes of size K(a ′ ) + 0.99 log|a ′ | + c is smaller than the difference between the lengths of a ′ and a (so we can find some a ′′ with required properties). The length of a is fixed, so we need that 2 [K(a ′ )+0.99 log |a ′ |+c] ≪ a ′ , and this is possible since K(a ′ ) + c can be small compared to 0.01 log|a ′ |'.

Note that this example shows also that one cannot always find β that computes α with oracle use KM(α↾n), where KM stands for monotone complexity. Indeed, since KM(z) K(z) for all z and KM is monotone, we have KM(x) min K(z) when the minimum is taken over all extensions z of x. (This question is natural since KM(α↾n) is an obvious lower bound for the oracle use.)