Vincent Guedj
email: vincent.guedj@math.univ-toulouse.fr

AND Boris Kolev
email: kolev@cmi.univ-mrs.fr

Nader Yeganefar
email: nader.yeganefar@cmi.univ-mrs.fr

A LICHNEROWICZ ESTIMATE FOR THE FIRST EIGENVALUE OF CONVEX DOMAINS IN K ÄHLER MANIFOLDS

Keywords: 2010 Mathematics Subject Classification. 58C40, 53C21 Lichnerowicz estimate, first eigenvalue, convex domains in Kähler manifold

In this article, we prove a Lichnerowicz estimate for a compact convex domain of a Kähler manifold whose Ricci curvature satisfies Ric ≥ k for some constant k > 0. When equality is achieved, the boundary of the domain is totally geodesic and there exists a nontrivial holomorphic vector field.

We show that a ball of sufficiently large radius in complex projective space provides an example of a strongly pseudoconvex domain which is not convex, and for which the Lichnerowicz estimate fails.

Introduction

Let (M n , g) be a compact n-dimensional Riemannian manifold. Assume first that M has no boundary. A theorem of Lichnerowicz [START_REF] Lichnerowicz | Géométrie des groupes de transformations[END_REF] asserts that if the Ricci curvature Ric of M satisfies Ric ≥ k for some constant k > 0, then the first nonzero eigenvalue λ of the Laplace operator satisfies

(1.1) λ ≥ n n -1 k.
Here, nk/(n -1) should be viewed as the first nonzero eigenvalue of the round n-dimensional sphere S n (k/(n -1)) of constant curvature k/(n -1). Moreover, by a result of Obata [START_REF] Obata | Certain conditions for a Riemannian manifold to be isometric with a sphere[END_REF], the equality case in (1.1) is obtained if and only if M is isometric to this sphere. Reilly considered a similar problem, but for compact manifolds with boundary [START_REF] Reilly | Applications of the Hessian operator in a Riemannian manifold[END_REF]. Namely, he proved that if M is as in Lichnerowicz theorem, except that it has now a boundary such that its mean curvature with respect to the outward normal vector field is nonnegative, then the first eigenvalue λ of the Laplace operator with the Dirichlet boundary condition still satisfies (1.1). He also proved that the equality case characterizes a hemisphere in S n (k/(n -1)).

In another direction, Lichnerowicz showed that for Kähler manifolds, his estimate (1.1) can be improved. To explain this, we modify slightly our normalization conventions: we consider a closed Kähler manifold M of real dimension n = 2m, whose Ricci curvature satisfies Ric ≥ k > 0. On a Kähler manifold, there are a priori three Laplace operators, namely the usual Laplace operator associated to exterior differentiation, and two Laplace operators associated to ∂ and ∂ respectively. Moreover, the latter two are actually equal and coincide with half the usual Laplacian. In the sequel, we will consider the Laplace operator associated with ∂, and we will denote it by ∆, so that ∆ = ∂ * ∂ + ∂ ∂ * . The first nonzero eigenvalue of ∆ acting on functions will be denoted by λ. In view of these conventions, the condition Ric ≥ k and the Lichnerowicz estimate (1.1) give

λ ≥ mk (2m -1)
.

Lichnerowicz improved this bound by showing that

λ ≥ k
Moreover, if equality is achieved, then there is a non trivial holomorphic vector field on M . The purpose of this note is to consider the case of compact Kähler manifolds with boundary. As in Reilly's result, we will have to impose some convexity property on the boundary: Theorem 1.1. Let M be a compact convex domain in a Kähler manifold. Assume that the Ricci curvature satisfies Ric ≥ k for some constant k > 0. Then the first nonzero eigenvalue λ of the Laplacian with Dirichlet boundary condition satisfies λ ≥ k. Moreover, if equality is achieved, then the boundary ∂M is totally geodesic and there is a nontrivial holomorphic vector field on M . Remark 1.2. As we will see in the proof, the convexity hypothesis may be relaxed into another condition of mean curvature type (see condition (4.1) below). However, this condition has no clear geometrical meaning, so that we have stated our theorem with the convexity hypothesis instead.

Remark 1.3. It is natural to ask whether our result remains true if one assumes the pseudoconvexity of the boundary instead of its convexity. It turns out that a ball of sufficiently large radius in complex projective space provides an example of a strongly pseudoconvex domain which is not convex, and for which the Lichnerowicz estimate fails (see Proposition 4.1 for more details on this).

Remark 1.4. In the real setting, one can consider the Laplacian with the Neumann boundary condition, and again with the convexity condition, one can show that the Lichnerowicz estimate (1.1) still holds for the first nonzero eigenvalue [START_REF] Pak | On the first eigenvalue estimate of the Dirichlet and Neumann problem[END_REF]. In the Kähler setting, by using the method of proof of Theorem 1.1, it should also be possible to prove that the conclusion of this theorem is true for the first nonzero eigenvalue of the ∂-Laplacian with the absolute ∂-condition on the boundary.

An immediate consequence of our theorem is Corollary 1.5. Assume that M is a strongly convex domain in a complex manifold which can be endowed with a Kähler metric whose Ricci curvature satisfies Ric ≥ k for some constant k > 0. Then the first nonzero eigenvalue λ of the Laplacian with Dirichlet boundary conditions satisfies λ > k.

Our proof follows the same strategy as in the original proofs of Lichnerowicz and Reilly. We use an appropriate Bochner formula for the Laplacian acting on (0, 1)-forms and apply it to ∂f , where the function f is an eigenfunction of ∆ for the first eigenvalue. After integrating the result on M and integrating by parts, the desired eigenvalue estimate follows if we can prove that some boundary term is nonpositive, which is the case under the convexity hypothesis.

Background material

In this section, we recall some well-known facts that will be used in the proof of our main result.

2.1. Decomposition of the Hessian. Let f be a real valued smooth function on a Kähler manifold (M, J, g). Its Riemannian Hessian Hess f is as usual defined by Hess f = ∇df This Hessian may be decomposed as the sum of a J-symmetric bilinear form and a J-skew-symmetric bilinear form. More specifically, we have

Hess f = H 1 f + H 2 f
where for tangent vectors A and B,

H 1 f (A, B) = 1 2 {Hess f (A, B) + Hess f (JA, JB)}
and

H 2 f (A, B) = 1 2 {Hess f (A, B) -Hess f (JA, JB)}
The two following facts may easily be checked:

(1) The (1, 1)-form associated to H 1 f by the complex structure J is i∂ ∂f :

H 1 f (JA, B) = i∂ ∂f (A, B).
(2) In local coordinates, H 2 f has the following components

(H 2 f ) pq = (H 2 f ) pq = ∂ 2 f ∂z p ∂z q -Γ r pq ∂f ∂z r ,
and the other components vanish. H 2 f is called the complex Hessian.

2.2. Bochner formula for the Laplacian. Let (M, g) be a Kähler manifold, and denote by D its Levi-Civita connection. If α is a (0, 1)-form, we denote by D ′′ α the (0, 2)-part of Dα. More precisely, Dα is a section of the bundle T * M ⊗ (T * ) 0,1 M ; this bundle decomposes as a direct sum

((T * ) 1,0 M ⊗ (T * ) 0,1 M ) ⊕ ((T * ) 0,1 M ⊗ (T * ) 0,1 M ),
and D ′′ α is the projection of Dα on the second factor of this decomposition.

In local complex coordinates, we have

(D ′′ α) pq = ∂α q ∂ zp -Γ r pq α r.
Let now (D ′′ ) * be the formal adjoint of D ′′ . For a section β of (T * ) 0,1 M ⊗ (T * ) 0,1 M one can see that locally

((D ′′ ) * β) p = -g qr ∂β r p ∂z q .
Then we have the following Bochner formula for the ∂-Laplacian ∆ acting on (0, 1)-forms:

(2.1) ∆ = (D ′′ ) * D ′′ + Ric .

For future reference, we also give the integration by parts formula for D ′′ in the presence of a boundary (see e.g. [Tay96, Proposition 9.1]). Here, we assume that M is compact, and we let n denote the outward unit normal vector field on ∂M . The (0, 1) part of the dual 1-form ν corresponding to n by the metric will be denoted by ν 0,1 . Finally, we let σ denote the measure induced on the boundary by the metric. For smooth α and β, we then have

(2.2) D ′′ α, β L 2 (M ) = α, (D ′′ ) * β L 2 (M ) + ∂M ν 0,1 ⊗ α, β σ.

Estimate of the first eigenvalue

In this section, M is a compact smooth domain in a Kähler manifold of complex dimension m, with metric g and Ricci curvature bounded from below by some positive constant k. The outward unit normal vector field on the boundary ∂M is denoted by n and its covariant associated 1-form by ν.

3.1. Bochner formula and the first eigenvalue. Let f be a real valued eigenfunction of ∆ corresponding to the first nonzero eigenvalue λ of ∆, so that f : M → R is smooth, vanishes on the boundary ∂M , and satisfies ∆f = λf . (Note that it is possible to choose f to be real valued, because ∆ is equal to half the usual Laplacian.) We write the Bochner formula (2.1) for the (0, 1)-form ∂f and take the L 2 -inner product of the resulting equality with ∂f itself:

(3.1) ∆ ∂f, ∂f L 2 (M ) = (D ′′ ) * D ′′ ∂f, ∂f L 2 (M ) + M Ric ( ∂f, ∂f ).
Using the fact that ∆ ∂ = ∂∆ and that f | ∂M = 0, we can integrate by parts the left hand side of (3.1) to get

∆ ∂f, ∂f L 2 (M ) = ∂∆f, ∂f L 2 (M ) = ∂(λf ), ∂f L 2 (M ) = λ ∆f, f L 2 (M ) = λ 2 f 2 L 2 (M )
. We can deal with the Ricci term in the right hand side of (3.1) in a similar way

M Ric ( ∂f, ∂f ) ≥ k ∂f, ∂f L 2 (M ) = k ∆f, f L 2 (M ) = kλ f 2 L 2 (M ) .
Finally, we can integrate by parts the first term in the right hand side of (3.1) (see formula (2.2)):

(3.2) (D ′′ ) * D ′′ ∂f, ∂f L 2 (M ) = D ′′ ∂f 2 L 2 (M ) - ∂M D ′′ ∂f, ν 0,1 ⊗ ∂f σ,
and combining this with our previous estimates, we obtain

(3.3) λ(λ -k) f 2 L 2 (M ) ≥ D ′′ ∂f 2 L 2 (M ) - ∂M D ′′ ∂f, ν 0,1 ⊗ ∂f σ.
As a consequence, if we set

I = - ∂M D ′′ ∂f, ν 0,1 ⊗ ∂f σ,
we will get λ ≥ k provided we can prove that I ≥ 0. In the next subsection, we will see that this is indeed the case under suitable assumptions on the boundary.

Boundary term.

To estimate the boundary term I, we first notice that as f is real valued, we have

(D ′′ ∂f ) pq = (H 2 f ) pq so that I = - ∂M H 2 f, ν 0,1 ⊗ ∂f σ = - ∂M H 2 f (n 0,1 , (∂f ) ♯ ) σ.
We then choose a boundary defining function ρ for ∂M . This means that ρ is a smooth real valued function such that M = {ρ ≤ 0}, ∂M = {ρ = 0} and dρ does not vanish on ∂M . By multiplying ρ by a suitable smooth positive function if necessary, we may assume that n = grad ρ.

Moreover, near a fixed (but arbitrary) point of the boundary ∂M , we fix a local orthonormal frame adapted to the complex structure J which has the form v 1 , Jv 1 , . . . , v m , Jv m = n = grad ρ.

We also set

e p = 1 √ 2 (v p -iJv p ), p = 1, . . . , m.
Note that as f vanishes on ∂M , its derivatives along tangent vectors to ∂M also vanish and consequently

(∂f ) ♯ = -i √ 2 (n • f )ē m , n 0,1 = -i √ 2 ēm ,
where n • f means df (n). Therefore,

I = 1 2 ∂M (n • f ) Hess f (ē m , ēm ) σ
which can be decomposed as I = I 1 + iI 2 with

I 1 = 1 4 ∂M (n • f ) [Hess f (Jn, Jn) -Hess f (n, n)] σ
and

I 2 = -1 2 ∂M (n • f ) Hess f (Jn, n) σ.
Actually I 2 vanishes because I is a real number. (This follows from the fact that in equation (3.1), the left hand side and the Ricci term are real numbers, so that the term involving D ′′ is also a real number. This implies, by equation (3.2), that the boundary term I is a real number as well. There is also a more conceptual reason for the vanishing of I 2 , see section 3.3). We now turn our attention to I 1 . As △f = λf = 0 on ∂M , the trace of Hess f is also zero on ∂M :

Hess f (Jn, Jn) -Hess f (n, n) = m-1 k=1 [Hess f (v k , v k ) + Hess f (Jv k , Jv k )]
+ 2 Hess f (Jn, Jn).

We notice that all vectors appearing in the right hand side are tangent to the boundary. For such a vector u, we have on ∂M

Hess f (u, u) = -∇ u u, n (n • f ) = ∇ u n, u (n • f ) = (n • f ) Hess ρ(u, u).
This implies

(3.4) I 1 = 1 4 ∂M (n • f ) 2 m-1 k=1 [Hess ρ(v k , v k ) + Hess ρ(Jv k , Jv k )]
+ 2 Hess ρ(Jn, Jn) σ.

If we assume that ∂M is convex, then all terms in the integrand of the right hand side are nonnegative, so that I = I 1 ≥ 0 as desired. This proves that λ ≥ k in the convex case. It remains to deal with the equality case. If we assume that λ = k, then by equation (3.3), we must have D ′′ ∂f = 0 and I = 0. On the one hand, D ′′ ∂f = 0 means that the (1, 0)-vector field associated to ∂f by the metric is a (nonzero) holomorphic vector field. On the other hand, from I = 0, we infer that the integrand in equation (3.4) has to vanish identically on the boundary:

(n • f ) 2 m-1 k=1 {Hess ρ(v k , v k ) + Hess ρ(Jv k , Jv k )} + 2 Hess ρ(Jn, Jn) = 0.
Assume by contradiction that ∂M is not totally geodesic (but still convex of course). Then the term between the brackets is positive at some point and we will get the vanishing of n.f on an open subset of ∂M . But f is in the kernel of the elliptic operator ∆ -λ and vanishes on ∂M . By the unique continuation principle for elliptic operators (see e.g. [START_REF] Booß-Bavnbek | Elliptic boundary problems for Dirac operators[END_REF]), f has to vanish on M as well, which is absurd. Therefore, ∂M is totally geodesic. This completes the proof of Theorem 1.1.

3.3.

A direct proof that the boundary term is real. The fact that

I 2 = -1 2 ∂M (n • f ) Hess f (Jn, n) σ
vanishes is also a consequence of the fact that the expression

(n • f ) Hess f (Jn, n) σ = (n • f )(Jn • n • f ) σ
is an exact differential form on the closed manifold ∂M . Indeed, the vector field Jn = J grad ρ is the Hamiltonian vector field associated to ρ. This means that if ω is the Kähler form, then

i Jn ω = -dρ.
Hence

d i Jn i n ω m = -md(n • ρ) ∧ ω m-1 -m(m -1)dρ ∧ d i n ω ∧ ω m-2
Let j : ∂M → M be the inclusion map. Since the functions n • ρ and ρ are constant on ∂M , we have

j * (d i Jn i n ω m ) = 0.
Now, Jn is a vector field defined on a neighborhood of ∂M whose restriction to ∂M is tangent to ∂M , so that j * (i Jn β) = i Jn j * (β) for any differential form β. As a consequence, we get

d i Jn j * (i n ω m ) = 0.
Finally, we have j * (i n ω m ) = σ, and d i Jn σ = 0. Defining a vector field X by

X = 1 2 (n • f ) 2 Jn,
it follows that on ∂M , we have

d i X σ = (n • f )(Jn • n • f )σ.

Counter-example in the pseudoconvex case

We use the notation introduced in the previous section. It is clear from the proof of Theorem 1.1 that in order to get the estimate λ ≥ k, it is enough to assume that on the boundary we have Here, m-1 k=1 H 1 ρ(v k , v k ) is the trace of the Levi form of the boundary, which would be nonnegative if ∂M were assumed to be only pseudoconvex. The extra term Hess ρ(Jn, Jn), however, can usually not be controlled in the pseudoconvex case. This suggests that the conclusion of Theorem 1.1 does not generally hold in this case, as we now explain.

We consider here the complex m-dimensional projective space P m (C) equipped with the Fubini-Study metric normalized so that the holomorphic sectional curvature is 4 (the Einstein constant is thus 2(m + 1) and the diameter is π/2). Proposition 4.1. Fix some point x ∈ P m (C), some r 0 ∈]0, π/2[, and let M be the geodesic ball centered at x, of radius r 0 .

(i) If r 0 ∈]π/4, π/2[, then M is strongly pseudoconvex, not convex.

(ii) The first nonzero eigenvalue of M with Dirichlet boundary conditions goes to 0 as r 0 approaches π/2

Proof. The first point is a well-known result. For completeness, we outline the proof here. Denote by r the distance function from x, and set ρ = r 2 -r 2 0 , so that ρ is a smooth defining function for M . We want to compute the eigenvalues of the Hessian of ρ. As Hess ρ = 2r Hess r + 2dr ⊗ dr, we will only have to compute the eigenvalues of Hess r. To do this, we proceed as in the proof of [GW79, Theorem A, p.19]. Recall that for a tangent vector u, the curvature R(u, .)u of P m (C) is given by (

[BGM71, Proposition F.34]) R(u, .)u =    0,
on Ru; 4Id, on RJu; Id, on the orthogonal complement of (u, Ju).

Let γ be a normal geodesic starting from x. We can choose a parallel frame along γ which has the form v 1 , Jv 1 , . . . , v m , Jv m = grad r. Using the explicit expression of R, it is then easy to check that the space of Jacobi fields V along γ satisfying V (0) = 0 and V ⊥ γ has as basis V i = sin (r)v i , JV i , i = 1, . . . , m -1 and V m = sin (2r)v m . Using the second variation formula, we see that Hess r is diagonalized in the basis v 1 , Jv 1 , . . . , v m , Jv m with eigenvalues cot (r) (of order 2m -2), 2 cot(2r) and 0. If r = r 0 ∈ ]π/4, π/2[, we infer that the Levi form of ρ is positive definite, being equal to 2r 0 cot (r 0 )Id on the Levi distribution. In other words, M is strongly pseudoconvex. However, M is not convex because the principal curvature 2 cot (2r 0 ) is negative.

As for the second point of our proposition, it is for example a consequence of a more general result due to Chavel and Feldman [CF78, Theorem 1] which states the following: let X be a compact Riemannian manifold and let X ′ ⊂ X be a submanifold. For small ε > 0, let X ′ ε be the ε-neighborhood of X ′ in X and denote by Ω ε the set X \ X ′ ε . Let (λ j ) be the spectrum of X and let (λ j (ε)) be the spectrum of Ω ε with Dirichlet boundary conditions. If the codimension of X ′ in X is at least 2, then for all j, λ j (ε) → λ j-1 as ε → 0. In our case, we can take X = P m (C) and X ′ = P m-1 (C) which we view as the cut locus of our fixed point x. If ε = π/2 -r 0 , then Ω ε coincides actually with M and we get (ii).

  v k , v k ) + Hess ρ(Jv k , Jv k )} + 2 Hess ρ(Jn, Jn) ≥ 0,and not necessarily the convexity of ∂M . We may rewrite this condition as m-1 k=1 H 1 ρ(v k , v k ) + Hess ρ(Jn, Jn) ≥ 0.


Laurent Bienvenu
email: laurent.bienvenu@liafa.jussieu.fr

Adam Day
email: adam.day@msor.vuw.ac.nz

Mathieu Hoyrup
email: mathieu.hoyrup@loria.fr

Ilya Mezhirov
email: mezhirov@gmail.com

Alexander Shen
email: alexander.shen@lif.univ-mrs.fr

A constructive version of Birkhoff's ergodic theorem for Martin-Lof random points

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The classical setting for the ergodic theorem is as follows. Let X be a space with a probability measure µ on it, and let T : X → X be a measure-preserving transformation. Let f be a real-valued integrable function on X. Birkhoff's ergodic theorem (see for example [?]) says that the average value f (x) + f (T (x)) + f (T (T (x))) + . . . + f (T (n-1) (x)) n has a limit (as n → ∞) for all x except for some null set, and this limit (the "time-average") equals the "space average" f (x) dµ(x) if the transformation T is ergodic (i.e., has no nontrivial invariant subsets).

The classical example of an ergodic transformation is the left shift on Cantor space Ω (the set of infinite binary sequences, also denoted by 2 N or 2 ω ):

σ ω(0)ω(1)ω(2) . . . = ω(1)ω(2)ω(3) . . . The left shift preserves Lebesgue measure (a.k.a. uniform measure) µ on Ω and is ergodic. Therefore, the time and space averages coincide for almost every starting point ω. For a special case where f is an indicator function of some (measurable) set A, we conclude that almost surely (for all ω outside some null set) the fraction of terms in the sequence ω, σ(ω), σ(σ(ω)), . . . that are inside A, converges to the measure of A.

It is natural to ask whether Birkhoff ergodic theorem has an effective version for individual points saying that for a Martin-Löf random starting point the time average coincides with the space average (under some effectivity assumptions for the space and the transformation). This question was posed by van Lambalgen [?] and answered by Vyugin [?] who proved this statement for the case of computable function f (he also proved the convergence result for non-ergodic transformations). The result was later extended to larger classes of functions [?,?]. However, we cannot directly apply these results to an indicator function of an effectively open set (recall that an open set U is effectively open if there is a computably enumerable set S of finite strings such that U consists exactly of the infinite sequences having a prefix in S). Indeed, the characteristic function of such a set is not computable (it is only lower semicomputable, i.e., it is the limit of a non-decreasing sequence of computable functions).

So for effectively open sets (and lower semicomputable functions) the question remained open. 6In this paper we answer this question and show that effective ergodic theorem remains true for effectively open sets and lower semicomputable functions (Section ??). The proof goes in several steps.

First, in Section ?? we consider the following corollary of Birkhoff's ergodic theorem: if A has positive measure, for almost every starting point at least one element of the trajectory belongs to A. Switching to complements: if A has measure less than 1, then (almost surely) some points in the trajectory are outside A. An effective version of this statement (for effectively open sets of measure less than 1 and left shifts in Cantor space) was proved by Kučera [?]. We reproduce Kučera's proof and prove several similar statements. (Most of them are consequences of the general results of Section ??, so the direct proofs are redundant, but they are nice and simple.)

Then in Section ?? we consider the general effective ergodic theorem. In Section ?? we prove a general version of Kučera's theorem for computable ergodic transformations of Cantor space. Then (Section ??) we show how the effective version of ergodic theorem for effectively open sets and lower semicomputable functions can be reduced to classical Birkhoff's ergodic theorem and the general version of Kučera's theorem proved in Section ??. Finally, we outline the generalization of these results to other probability spaces (Section ??).

In Section ?? we use the results of Section ?? to provide a generalized version of van Lambalgen's theorem (generalizing an earlier result of Miyabe).

The results of Sections ?? and ?? were presented at the Computability in Europe conference (and published in its proceedings [?]). The improvement in this paper is Theorem ??, showing that one can go further and reduce the general effective version of Birkhoff's er-godic theorem for effectively open sets to this special case. This last result was obtained independently in [?].

Variations of Kučera's theorem

In this section, we prove several variants of Kučera's theorem. Let us first recall the original version proved in [?]. Let σ be the left shift in Cantor space (i.e., an ergodic transformation of this space equipped with uniform measure).

Theorem 1. If A is an effectively open subset of the Cantor space of measure less than 1, then for every Martin-Löf random sequence ω at least one of its tails ω, σ(ω), σ(σ(ω)),. . . does not belong to A.

Recalling the definition of Martin-Löf randomness (a sequence is random if it is outside any effectively null set) we can reformulate Kučera's theorem as follows:

Let A be an effectively open set of measure less than 1. Consider the set A * of all sequences ω such that every tail σ (n) (ω) belongs to A. Then A * is an effectively null set.

Before presenting the proof, let us mention an interpretation of this result. Recall that the universal Martin-Löf test is a computable sequence U 1 , U 2 , . . . of effectively open sets such that µ(U i ) ≤ 1/2 i and the intersection ∩ i U i is the maximal effectively null set, i.e., the set of all non-random sequences. Kučera's theorem shows that randomness can be (in a paradoxical way) characterized by U 1 alone: a sequence is non-random if and only if all its tails belong to U 1 . (In one direction it is Kučera's theorem, in the other direction we need to note that a tail of a non-random sequence is non-random.)

Proof (of Kučera's theorem). We start with the following observation: it is enough to show that for every interval I, we can uniformly construct an effectively open set J ⊂ I that contains I ∩ A * and such that µ(J) ≤ rµ(I) for some fixed r < 1 (here we call an interval any set of type xΩ, where x is some finite string, i.e., the set of infinite binary sequences that start with x). Then we represent the effectively open set A of measure r < 1 as a union of disjoint intervals I 1 , I 2 , . . ., construct the sets J i for every I i and note that the union A 1 of all J i is an effectively open set that contains A * and has measure r 2 or less. Splitting A 1 into disjoint intervals and repeating this argument, we get a set A 2 of measure at most r 3 , etc. In this way we get a effectively open cover for A * of arbitrarily small measure, so A * is an effectively null set.

It remains to show how to find J given I. The interval I consists of all sequences that start with some fixed prefix x, i.e., I = xΩ. Since sequences in A * have all their tails in A, the intersection I ∩ A * is contained in xA, and the latter set has measure rµ(I) (where r = µ(A)).

⊓ ⊔

Note that this proof also shows the following: suppose A is an effectively open set of measure less than 1, and A can be written as a disjoint union of intervals A = x 1 Ω∪x 2 Ω∪. . ..

Let ω be an infinite sequence that can be written as ω = w 1 w 2 w 3 . . . where for all i, w i = x j for some j. Then ω is not random. (If A contains all non-random sequences, the reverse implication is also true, and we get yet another criterion of randomness.)

Effective Kolmogorov 0-1 law

Trying to find characterizations of randomness similar to Kučera's theorem, one may look at Kolmogorov's 0-1-law. It says that any measurable subset A of the Cantor space that is stable under finite changes of bits (i.e. if ω ∈ A and ω ′ is equal to ω up to a finite change of bits, then ω ′ ∈ A) has measure 0 or 1. It can be reformulated as follows: let A be a (measurable) set of measure less than 1. Consider the set A * defined as follows: ω ∈ A * if and only if all sequences that are obtained from ω by changing finitely many terms, belong to A. Then A * has measure zero (indeed, A * is stable under finite changes and cannot have measure 1). Note also that we may assume without loss of generality that A is open (replacing it by an open cover of measure less than 1).

A natural effective version of Kolmogorov's 0-1-law can then be formulated as follows. (In fact, this statement was considered and proved by Kučera but was not explicitly mentioned in [?].) Theorem 2. Let A be an effectively open set of measure r < 1. Consider the set A * of all sequences that belong to A and remain in A after changing finitely many terms. Then A * is an effectively null set.

(As we have seen, the last two sentences can be replaced by the following claim: any Martin-Löf random sequence can be moved outside A by changing finitely many terms.) Proof. To prove this effective version of the 0-1-law, consider any interval I. As before, we want to find an effectively open set U ⊂ I that contains A * ∩ I and has measure at most rµ(I). Let x be the prefix that defines I, i.e., I = xΩ. For every string y of the same length as x, consider the set A y = {ω | yω ∈ A}. It is easy to see that the average measure of A y (over all y of a given length) equals µ(A) = r. Therefore, the set B = y A y (which is effectively open as an intersection of an effectively defined finite family of open sets) has measure at most r. Now take U = xB. Let us show that U is as wanted. First, U is an effectively open set, contained in I, and of measure rµ(I). Also, it contains every element of A * ∩ I. Indeed, if α ∈ A * ∩ I, x is a prefix of α, so one can write α = xβ. Since α ∈ A * , any finite variation of α is in A, so for all y of the same length as x, yβ ∈ A. Therefore, β is in all A y , and therefore is in

B. Since α = xβ, it follows that α is in xB = U . ⊓ ⊔

Adding prefixes

We have considered left shifts (deletion of prefixes) and finite changes. Another natural transformation is the addition of finite prefixes. It turns out that a similar result can be proven in this case (although the proof becomes a bit more difficult).

Theorem 3. Let A be an effectively open set of measure r < 1. Let A * be the set of all sequences ω such that xω ∈ A for every binary string x. Then A * is an effectively null set.

In other words, for every Martin-Löf random sequence ω there exists a string x such that xω / ∈ A.

Proof. To prove this statement, consider again some interval I = xΩ. We want to cover A * ∩ I by an effectively open set of measure rµ(I). (In fact, we get a cover of measure sµ(I) for some constant s ∈ (r, 1), but this is enough.) Consider some string z. We know that the density of A * in I does not exceed the density of A in zI = zxΩ. Indeed, xω ∈ A * implies zxω ∈ A by definition of A * . Moreover, for any finite number of strings z 1 , . . . , z k the set A * is contained in the intersection of sets {ω | z i ω ∈ A}, and the density of A * in I is bounded by the minimal (over i)

density of A in z i I = z i xΩ.
Now let us choose z 1 , . . . , z k in such a way that the intervals z i xΩ are disjoint and cover Ω except for a set of small measure. This is possible for the same reason as in a classic argument that explains why the Cantor set in [0, 1] has zero measure. We start, say, with z 1 = Λ and get the first interval xΩ. The rest of Ω can be represented as a union of disjoint intervals, and inside each interval uΩ we select a subinterval uxΩ thus multiplying the size of the remaining set by (1 -2 -|x| ). Since this procedure can be iterated indefinitely, we can make the rest as small as needed.

Then we note that the density of A in the union of disjoint intervals (and this density is close to r if the union covers Ω almost entirely) is greater than or equal to the density of A in one of the intervals, so the intersection (an effectively open set) has density at most s for some constant s ∈ (r, 1), as we have claimed. (We need to use the intersection and not only one of the sets since our construction should be effective even when we do not know for which interval the density is minimal.) ⊓ ⊔

Bidirectional sequences and shifts

Recall the initial discussion in terms of ergodic theory. In this setting it is more natural to consider bi-infinite binary sequences, i.e., mappings of type Z → B = {0, 1}; the uniform measure µ can be naturally defined on this space, too. On this space the transformation T corresponding to the shift to the left is reversible: any sequence can be shifted left or right. The result of Theorem ?? remains true in this setting.

Theorem 4. Let A be an effectively open set of B Z , of measure r < 1. The set A * of all sequences that remain in A after any arbitrary shift (any distance in any direction) is an effectively null set.

To prove this statement, consider any s ∈ (r, 1). As usual, it is enough to find (effectively) for every interval I x an effectively open subset of I x that contains A * ∩ I x and has measure at most sµ(I x ). Here x is a finite partial function from Z to B and I x is the set of all its extensions. (One may assume that x is contiguous, since every other interval is a finite union of disjoint contiguous intervals, but this is not important for us.) Then we may iterate this construction, replacing each interval of an effectively open set by an open set inside this interval, and so on until the total measure (s k , where k is the number of iterations) becomes smaller than any given ε > 0.

Assume that some I x is given. Note that A * is covered by every shift of A, so any intersection of I x with a finite collection of shifted versions of A (i.e., sets of type T n (A) for n ∈ Z) is a cover for I x ∩ A * . It remains to show that the intersection of properly chosen shifts of A has density at most s inside I x . To estimate the measure of the intersection, it is enough to consider the minimum of measures, and the minimum can be estimated by estimating the average measure.

More formally, we first note that by reversibility of the shift and the invariance of the measure, we have

µ I x ∩ T -n (A) = µ A ∩ T n (I x )
for all n. Then we prove the following lemma:

Lemma 5 Let J 1 , . . . , J k be independent intervals of the same measure d corresponding to disjoint functions x 1 , . . . , x k of the same length. Then the average of the numbers

µ(A ∩ J 1 ), . . . , µ(A ∩ J k )
does not exceed sd if k is large enough. Moreover such a k can be found effectively.

Proof (of Lemma ??). The average equals

1 k i E(χ A • χ i )
where χ A is the indicator function of A and χ i is the indicator function of J i . Rewrite this as

E χ A • 1 k i χ i , and note that 1 k i χ i
is the frequency of successes in k independent trials with individual probability d. (Since the functions x i are disjoint, the corresponding intervals J i are independent events.) This frequency (as a function on the bi-infinite Cantor space B Z ) is close to d everywhere except for a set of small measure (by the central limit theorem; in fact Chebyshev's inequality is enough). The discrepancy and the measure of this exceptional set can be made as small as needed using a large k, and the difference is then covered by the gap between r and s. This ends the proof of the lemma. Now, given an interval I x , we cover I x ∩ A * as follows. First, we take a integer N larger than the size of the interval I x . The intervals T N (I x ), T 2N (I x ), T 3N (I x ), . . . are independent and have the same measure as I x , so we can apply the above lemma and effectively find a k such that the average of

µ(A ∩ T N (I x )), . . . , µ(A ∩ T kN (I x ))
does not exceed sµ(I x ). This means that for some i ≤ k one has

µ(I x ∩ T -iN (A)) = µ(A ∩ T iN (I x )) ≤ sµ(I x ) Therefore, I x ∩ i≤k T -iN (A) is an effectively open cover of A * of measure at most sµ(I x ). ⊓ ⊔
The statement can be strengthened: we can replace all shifts by any infinite enumerable family of shifts. (Reformulation: let A be an effectively open set of measure less than 1; let S be an infinite computably enumerable set of integers; let α be a Martin-Löf random bi-infinite sequences. Then there exists s ∈ S such that the s-shift of ω is not in A.)

Proof. The proof remains the same: indeed, having infinitely many shifts, we can choose as many disjoint shifts of a given interval as we want.

⊓ ⊔

The argument used to prove Theorem ?? (and Theorem ??) is more complicated than the previous ones (that do not refer to the central limit theorem): previously we were able to use disjoint intervals instead of independent ones. In fact the results about shifts in unidirectional sequences (both) are corollaries of the last statement. Indeed, let A be an effectively open set of right-infinite sequences of measure less than 1. Let ω be a right-infinite Martin-Löf random sequence. Then it is a part of a bi-infinite random sequence ω (one may use, e.g., van Lambalgen's theorem [?] on the random pairs, see Section ?? for a precise statement). So there is a right shift that moves ω outside Ā, and also a left shift with the same property (here by Ā we denote the set of bi-infinite sequences whose right halves belong to A).

A generalization to all ergodic transformations 3.1 Generalizing Kučera's theorem

First let us recall the notion of a computable transformation of the Cantor space Ω. Consider a Turing machine with a read-only input tape and write-only output tape (where head prints a bit and moves to the next blank position). Such a machine determines a computable mapping of Ω into the space of all finite and infinite binary sequences. Restricting this mapping to the inputs where the output sequence is infinite, we get a (partial) computable mapping from Ω into Ω.

Theorem 7. Let µ be a computable measure on Ω. Let T : Ω → Ω be a partial computable, almost everywhere defined, measure-preserving, ergodic transformation of Ω. Let A be an effectively open subset of Ω of measure less than 1. Let A * be the set of points x ∈ Ω such that T n (x) ∈ A for all n ≥ 0. Then, A * is an effectively null set.

Proof. Let r be a real number such that µ(A) < r < 1. As before, given an interval I, we want to (effectively) find an n such that I ∩ i≤n T -i (A) has measure at most rµ(I). This gives us an effectively open cover of A * ∩ I having measure at most rµ(I); iterating this process, we conclude that A * is an effectively null set.

(A technical clarification is needed here. If we consider T only on inputs where the output sequence is infinite, the set T -1 (A) (and in general T -i (A)) may no longer be open in Ω. But since T is almost everywhere defined, we may extend T to the space Ω of infinite and finite sequences in a natural way and get an effectively open cover of the same measure.)

To estimate µ(I ∩ i≤n T -i (A)), we note that it does not exceed the minimal value of µ(I ∩ T -i (A)), which in its turn does not exceed the average (over i ≤ n) of µ(I ∩ T -i (A)). This average,

1 n+1 µ(I ∩ A) + µ(I ∩ T -1 (A)) + . . . + µ(I ∩ T -n (A)) ( * )
can be rewritten as

1 n+1 µ(T -n (I) ∩ T -n (A)) + µ(T -(n-1) (I) ∩ T -n (A)) + . . . + µ(I ∩ T -n (A))
since T is measure preserving. The latter expression is the inner product of the indicator function of T -n (A) and the average a n = (χ 0 + . . . + χ n )/(n + 1), where χ i is the indicator function of T -i (I).

As n → ∞, the average a n converges in L 2 to the constant function µ(I), due to von Neumann's mean ergodic theorem. By the Cauchy-Schwarz inequality, this implies that the scalar product converges to µ(A)µ(I) and therefore does not exceed rµ(I) for n large enough.

It remains to (effectively) find a value of n for which the L 2 -distance between a n and the constant µ(I) is small. Note that for all i the set T -i (I) is an effectively open set of measure µ(I) (recall that T is measure preserving), and µ(I) is computable since µ is a computable measure. Therefore, for any i and ε > 0, one can uniformly approximate T -i (I) by its subset U that is a finite union of intervals such that µ(T -i (I) \ U ) < ε. This means that the L 2distance between a n and the constant function µ(I) can be computed effectively, and we can wait until we find a term with any precision needed. In particular, we can effectively find an n such that the average ( * ) is less than r. By the above discussion, we then have µ(I ∩ i≤n T -i (A)) < rµ(I), as needed.

⊓ ⊔

Now we get all the theorems of Section ?? (except for Theorem ??) as corollaries: the effective ergodic theorem for the bidirectional shift (Theorem ??) immediately follows as the bidirectional shift is clearly computable, measure-preserving and ergodic. Remark: technically we proved Theorem ?? only for the Cantor space Ω, but the space of functions Z → B on which the bidirectional shift is defined, is computably isomorphic to Ω. By this we mean that there exists a computable measure preserving bijection from one space to another; for example, one could represent a two-directional sequence . . . ω(-2)ω(-1)ω( 0)ω( 1)ω(2) . . . by a one-directional sequence ω(0)ω(-1)ω( 1)ω(-2)ω(2) . . ., and under this representation we can therefore represent the bidirectional shift as a measure preserving map from Ω to itself.

Recalling the discussion in Section ??, we see also that one can derive both Theorem ?? (Kučera's theorem for deletion of finite prefixes) and Theorem ?? (addition of finite prefixes) from Theorem ??.

It turns out that even Theorem ?? (finite change of bits) can be proven in this way. Indeed, let us consider the map F defined on Ω by: F (1 n 0ω) = 0 n 1ω for all n, and F (11111 . . .) = 00000 . . . (F adds 1 to the sequence in the dyadic sense). It is clear that F is computable and measurepreserving. That it is ergodic comes from Kolmogorov's 0-1 law, together with the observation that any two binary sequences ω, ω ′ that agree on all but finitely many bits are in the same orbit: ω ′ = F n (ω) for some n ∈ Z. The reverse is also true except for the case when sequences have finitely many zeros or finitely many ones. This cannot happen for a random sequence, so this exceptional case does not prevent us to derive Theorem ?? from Theorem ??.

Remark 1. Theorem ?? asserts that given a random ω, and an effectively open set U of measure less than 1, there exists an n such that T n (ω) / ∈ U (where T is the shift in the space of bidirectional sequences), and that moreover n can be found in a computable enumerable set fixed in advance. This of course still holds for the unidirectional shift on Ω, but this does not hold for all ergodic maps. Indeed, this fact is related to the so-called strong mixing property of the shift, which not all ergodic maps have. For example, a rotation of the circle by a computable irrational angle α (i.e., a mapping x → x + α mod 1 on Ω seen as the interval [0, 1]) is a computable ergodic map that does not have this property, and it is easy to construct a counterexample to the claim of Theorem ?? for that particular map.

An effective version of Birkhoff 's ergodic theorem

The generalization of Kučera's theorem we proved in the previous section (Theorem ??) is only a weak form of ergodic theorem. It asserts that under the action of a computable ergodic map, the orbit of a Martin-Löf point will intersect any given effectively closed set of positive measure, but it does not say anything about the frequency. This is what we achieve with the next theorem.

Theorem 8. Let µ be a computable measure on Ω. Let T : Ω → Ω be a computable almost everywhere defined µ-preserving ergodic transformation. Let U be an effectively open set. For every Martin-Löf random point ω,

lim n→∞ 1 n n-1 k=0 χ U (T k (ω)) = µ(U ).
Note that the statement is symmetric, so the same is true for an effectively closed set C.

Proof. Let g n (ω) = 1 n n-1 k=0 χ U (T k (ω)
) be the frequency of U -elements among the first n iterations of ω. Let us first prove that lim sup g n (ω) ≤ µ(U ). Then we show (see part (2) below) that lim inf g n (ω) ≥ µ(U ).

(1) Let r > µ(U ) be some rational number and let

G N = {ω : (∃n ≥ N ) g n (ω) > r}
be the set of points where some far enough frequency (average of at least N terms) exceeds r.

The set G N is an effectively open set; indeed, the functions g n are lower semicomputable (uniformly in n), hence the condition g n (ω) > r is enumerable. The sets G N form a decreasing sequence. We know by the classical Birkhoff's pointwise ergodic theorem that µ( N G N ) = 0, since the sequence of functions g n converges to µ(U ) < r µ-almost everywhere. As a result, there exists N such that µ(G N ) < 1. We can thus apply Theorem ?? to this G N and conclude that for every Martin-Löf random ω there exists k such that T k (ω) / ∈ G N . Hence lim sup n g n (T k (ω)) ≤ r. Since a finite number of iterations does not change the lim sup, we conclude that lim sup g n (ω) ≤ r. The number r was an arbitrary rational number greater than µ(U ), so lim sup g n (ω) ≤ µ(U ).

(2) We now prove that lim inf g n (ω) ≥ µ(U ). This in fact can be deduced from the first part of the proof. The set X is open, so it is a countable union of disjoint intervals. Taking a finite part of this countable union, we get an effectively closed set C ⊂ U and can apply the previous statement to its complement. It says that the orbit of a Martin-Löf random point ω will be in X ′ with frequency at least µ(X ′ ) (the upper bound for the complement of C means a lower bound for C). Since µ(C) can be arbitrarily close to µ(X), we conclude that lim inf g n (ω) ≥ µ(U ).

⊓ ⊔ Remark 2. The inequality lim inf g n (ω) ≥ µ(X) can actually be derived from the algorithmic version of Birkhoff's theorem proved by V'yugin [?], since X ′ is open and closed set, but it is easier to refer to the first part of the proof. Note also that in this direction we do not need effectivity: lim inf g n (ω) ≥ µ(X) for every open set X and every Martin-Löf random point ω. Of course the other inequality generally fails for (non-effectively) open sets: indeed, the orbit of every point ω can be enclosed in a (non-effectively) open set of small measure.

Theorem ?? extends to a larger class of sets in a straightforward way. We say that a set A is effectively µ-approximable if µ(A) = sup{µ(F ) : F effectively closed and F ⊆ A} = inf{µ(G) : G effectively open and A ⊆ G}. For instance, any ∆ 0 2 -set is effectively µ-approximable.

Corollary 1. Let X ⊂ Ω be an effectively µ-approximable set. For every Martin-Löf µrandom ω, lim 1 n (χ X (ω) + . . . + χ X (T n-1 (ω))) = µ(X). Proof. For every ε > 0 we can apply Theorem ?? to the upper and lower ε-approximations of X; the frequency for X is between them.

⊓ ⊔

Theorem ?? can also be extended a wider class of functions than characteristic functions of sets.

Theorem 9. Let f : Ω → [0, +∞] be lower semicomputable. For every Martin-Löf random ω,

lim n→∞ 1 n n-1 k=0 f (T k (ω)) = f dµ.
Note that we allow the integral to be infinite; in this case the sequence in the left-hand side has limit +∞.

Proof. Let f be a lower semicomputable function with a finite integral. Let f n = 1 n (f + . . . + f • T n-1 ). Let r > f dµ be a rational number and

G N = {ω : (∃n ≥ N ) f n (ω) > r}.
The set G N is an effective open set and µ( N G N ) = 0 as f n (ω) → f dµ < r for µ-almost every ω (by the classical version of Birkhoff's ergodic theorem). As a result, there exists N such that µ(G N ) < 1. By Theorem ??, if ω is Martin-Löf random then there exists k such that T k (ω) / ∈ G N . Hence lim sup f n (T k (ω)) ≤ r, and lim sup f n (ω) = lim sup f n (T k (ω)) ≤ r. Since r > f dµ can be arbitrarily close to the integral, we have that lim sup f n (ω) ≤ f dµ.

It remains to prove that lim inf f n (ω) ≥ f dµ. This is true for every lower semicontinuous f . Indeed, consider some lower bound for f that is a basic function (a linear combination of indicators of intervals). For these basic functions the statement of the theorem is true (as we already know), and their integrals can be arbitrarily close to f dµ. (This argument works also for the case f dµ = +∞.) ⊓ ⊔

Theorem ?? is, to the extent of our knowledge, the strongest form of effective ergodic theorem proven so far, in the case of an ergodic transformation. In particular, it strengthens the results that appeared in [?,?,?] for ergodic measures. We will see in the next section that it can even be extended a bit further, namely to other spaces than Ω and to ergodic maps that are only "weakly computable" (in a sense which we will explain below). However, whether the Birkhoff averages of an effectively open set converge at all Martin-Löf random points when the measure is not ergodic remains an open problem (note that in the nonergodic case, if the limit exists at a point, that limit is no longer the measure of the open set but depends on the particular point).

But let us mention first an interesting consequence of Theorem ??. Recall that the randomness deficiency of a sequence ω is defined as

d µ (ω) = sup n {-log µ[ω 0 . . . ω n-1 ] -K(ω 0 . . . ω n-1 )}
where K(w) is the (prefix) Kolmogorov complexity of w.

The following was proven by Gács [?]: a sequence ω is Martin-Löf random with respect to µ if and only if d µ (ω) is finite. Moreover, t µ := 2 dµ is a universal randomness test in the sense that it is lower semicomputable, µ-integrable, and for every lower semicomputable µ-integrable f : Ω → [0, +∞] there exists c such that f ≤ ct µ .

For a computable µ-preserving mapping T it is already known that if ω is Martin-Löf random, then so are T (ω), T 2 (ω), etc. Theorem ?? applied to t µ yields a stronger result for the case of ergodic T : not only the values t µ (ω), t µ (T (ω)), t µ (T 2 (ω)), etc. are finite, but also their average is bounded. In this sense, the iterates of a random point are "random in the average". It is still an open problem whether this still holds in the non-ergodic case.

A final generalization: computable probability spaces and layerwise computable functions

We now briefly present two "orthogonal" ways in which the previous results can be extended to other contexts. On the one hand, the algorithmic theory of randomness has been extended from the Cantor space to any computable metric space, where the computability of probability measures is now well understood. All the results presented above extend to such spaces. On the other hand, on the Cantor space as well as any computable metric space, the computability assumption on the mapping T can be weakened into layerwise computability introduced in [?]. Intuitively, this weakening corresponds in analysis to replacing continuity with measurability.

The first generalization can be carried out in two ways: the proof on the Cantor space can generally be adapted to any computable probability space, or the isomorphism between such spaces (see [?]) can be used to transfer the result without proving it again. The second generalization is also rather direct: replacing computability notions with their "layerwise" counterparts generally leaves the proofs correct. Caution is sometimes needed and appropriate lemmas then have to be used (especially regarding composition of functions).

We now give a brief overview of the aforementioned concepts. More details can be found in [?,?,?,?].

The algorithmic theory of randomness has been extended from the Cantor space to any computable metric space, i.e. any separable metric space with a distinguished dense countable set on which the metric is computable. A computable probability space is such a space X, endowed with a computable Borel probability measure µ. A universal Martin-Löf test always exist on such spaces, and induces a canonical decomposition of the set of Martin-Löf random points

R µ = n R µ n with R µ n ⊆ R µ n+1 and µ(R µ n ) > 1 -2 -n (namely, R µ n is
the complement in X of the n-th level of a universal µ-Martin-Löf test). Using this decomposition, one can weaken many computability notions, starting with the notion of a computable function: we say that a function f : X → Y (where Y is a computable metric space) is µ-layerwise computable if it is computable on each R µ n (uniformly in n) 7 . Such a function 4 An application: the generalized van Lambalgen's theorem

The celebrated van Lambalgen theorem [?] asserts that in the probability space Ω 2 (pairs of binary sequences with independent uniformly distributed components) a pair (ω 0 , ω 1 ) is random if and only if ω 0 is random and ω 1 is ω 0 -random (random relative to the oracle ω 0 ). This can be easily generalized to k-tuples: an element (ω 0 , ω 1 , . . . , ω k-1 ) of Ω k is random if and only if ω 0 is random and ω i is (ω 0 , . . . , ω i-1 )-random for all i = 1, 2 . . . , k -1. Can we generalize this statement to infinite sequences? Not completely: there exists an infinite sequence (ω i ) i∈N such that ω 0 is random and ω i is (ω 0 , . . . , ω i-1 )-random for all i ≥ 1; nevertheless, (ω i ) i∈N is non-random as an element of Ω N . To construct such an example, take a random sequence in Ω N and then replace the first i bits of ω i by zeros. Informally, in this example all ω i are random, but their "randomness deficiency" increases with i, so the entire sequence (ω i ) is not random (in Ω N ). K. Miyabe [?] has shown recently that one can overcome this difficulty allowing finitely many bit changes in each ω i (number of changed bits may depend on i):

Theorem 12 (Miyabe). Let (ω i ) i∈N be a sequence of elements of Ω such that ω 0 is random and ω i is (ω 0 , . . . , ω i-1 )-random for all i ≥ 1. Then there exists a sequence (ω ′ i ) i∈N such that -For every i the sequence ω ′ i is equal to ω i except for a finite number of places. -The sequence (ω ′ i ) i∈N is a random element of Ω N . Informally, this result can be explained as follows: as we have seen (Theorem ??), a change in finitely many places can decrease the randomness deficiency (starting from any non-random sequence, we get a sequence that is not covered by a first set of a Martin-Löf test) and therefore can prevent "accumulation" of randomness deficiency. This informal explanation can be formalized and works not only for finite changes of bits but for any ergodic transformation. In fact, the results of this paper allow us to get a short proof of the following generalization of Miyabe's result (Miyabe's original proof used a different approach, namely martingale characterizations of randomness). We restrict ourselves to the uniform measure, but the same argument works for arbitrary computable measures.

Theorem 13. Let (ω i ) i∈N be a sequence of elements of Ω such that ω 0 is random and ω i is (ω 0 , . . . , ω i-1 )-random for all i ≥ 1. Let T : Ω → Ω be a computable bijective ergodic map. Then, there exists a sequence (ω ′ i ) i∈N such that -For every i, the sequence ω ′ i is an element of the orbit of ω i (i.e., ω ′ i = T n i (ω i ) for some integer n i ).

-The sequence (ω ′ i ) i∈N is a random element of Ω N . Proof. Let U be the first level of a universal Martin-Löf test on Ω N , with µ(U ) ≤ 1/2. We will ensure that the sequence (ω ′ i ) i∈N is outside U , and this guarantees its randomness. Consider the set V 0 consisting of those α 0 ∈ Ω such that the section U α 0 = {(α 1 , α 2 , . . .) | (α 0 , α 1 , α 2 , . . .) ∈ U }

Theorem 6 .

 6 Let A be an effectively open set (of bi-infinite sequences) of measure α < 1. Let S be an computably enumerable infinite set of integers. Then the set A * = {ω | ω remains in A after shift by s, for every s ∈ S} is an effectively null set.

It was proved in [?] that the result holds for any effectively open set whose measure is computable.

When X = Y = Ω, it means that there is a Turing machine that on input n and oracle x ∈ R µ n progressively writes f (x) on the output tape. The machine does not need to behave well when x / ∈ R µ n .

Acknowledgements. We would like to thank two anonymous referees for their very helpful comments and suggestions.

⋆ Supported by ANR Sycomore, NAFIT ANR-08-EMER-008-01, RFBR 09-01-00709-a grants and Shapiro visitors program at Penn State University.

may be discontinuous, but is still continuous on each R µ n , which is a totally disconnected set. It turns out that this notion admits a characterization in terms of effective measure theory.

Observe that µ-layerwise computability of real-valued functions is closed under basic operations such as sum, product, multiplication by a computable real number, and absolute value. Composition does not automatically preserve layerwise computability without an assumption on the preservation of the measure. If f : X → [-∞, +∞] and T : X → X are µ-layerwise computable and T preserves µ, then f •T is µ-layerwise computable. If, moreover, f is bounded, then f dµ is computable, uniformly in f and a bound on f . In particular, f 1 and f 2 are computable.

The main reason for which layerwise computability fits well with Martin-Löf randomness is that Martin-Löf random points pass a class of tests that is wider than the usual Martin-Löf tests: the tests that, on each R µ k , "look like" Martin-Löf tests. Lemma 10 Let A n ⊆ X be such that there exist uniformly effective open sets U n,k such that

Let us show how to adapt a part of the proof of Theorem ?? to computable probability spaces and µ-layerwise computable mappings.

Theorem 11. Let (X, µ) be a computable probability space. Let T : X → X be a µ-layerwise computable, measure-preserving, ergodic transformation of X. Let A be an effectively open subset of X of measure less than 1. For every µ-random point x, there exists n such that T n (x) / ∈ A.

Proof (Sketch). The proof is essentially the same as that of Theorem ??. The only differences are: adapting the notion of cylinder; using properties of layerwise computability; using Lemma ??.

A computable probability space always admits a basis of metric balls with computable centers and radii, whose borders have null measure. These balls correspond in a sense to the cylinders of the Cantor space: for instance, their measures are computable. Let then B = B(x, r) be a metric ball with computable center and radius, such that µ({y : d(x, y) = r}) = 0. Then µ(B) is computable, χ B is µ-layerwise computable and for all n the function

As a result, the L 2 -norms of the functions f n -µ(B) are all uniformly computable. Hence we can effectively find n such that µ(B ∩ i≤n T -i (A)) < rµ(B).

In the proof of Theorem ??, the computability of T implied that the set B ∩ i≤n T -i (A) was effectively open. When T is µ-layerwise computable, the set B∩ i≤n T -i (A) is effectively open on every R µ k . We end up with a test as in Lemma ?? enclosing n T -n (A), which implies the result.

⊓ ⊔

In the same way, Theorems ?? and ?? are true for computable probability spaces and for µ-layerwise computable mappings T . In Theorem ??, the function f can be assumed to be µ-layerwise lower semicomputable. has measure greater than 2/3. The measure of V 0 is less than 1, otherwise we would have µ(U ) > 1/2. It is easy to see that V 0 is an effectively open subset of Ω. Since ω 0 is random, by Theorem ?? there exists an integer n 0 such that ω ′ 0 = T n 0 (ω 0 ) is outside V 0 . This ω ′ 0 will be the first element of the sequence we are looking for. Now we repeat the same procedure for U ω ′ 0 instead of U . Note that it is an open set of measure at most 2/3, and, moreover, an effectively open set with respect to oracle ω ′ 0 . Since ω 0 and ω ′ 0 differ by a computable transformation, the set U ω ′ 0 is effectively open with oracle ω 0 . We repeat the same argument (where 1/2 and 2/3 are replaced by 2/3 and 3/4 respectively) and conclude that there exists an integer n 1 such that the sequence ω ′ 1 = T n 1 (ω 1 ) has the following property: the set

has measure at most 3/4. (Note that we need to use ω 0 -randomness of ω 1 , since we apply Theorem ?? to an ω 0 -effectively open set.) At the next step we get n 2 and ω ′ 2 = T (n 2 ) ω 2 such that

has measure at most 4/5, etc. Is it possible that the resulting sequence (ω ′ 0 , ω ′ 1 , ω ′ 2 , . . .) is covered by U ? Since U is open, it would be then covered by some interval in U . This interval may refer only to finitely many coordinates, so for some m all sequences (ω ′ 0 , ω ′ 1 , . . . , ω ′ m-1 , α m , α m+1 , . . .)

would belong to U (for every α m , α m+1 , . . .). However, this is impossible because our construction ensures that the measure of the set of all (α m , α m+1 , . . .) with this property is less than 1.

⊓ ⊔

Of course, the discussion of Section ?? shows that Theorem ?? can be extended to any computable probability space instead of the Cantor space, and to a layerwise computable ergodic map instead of a computable one. The details are left to the reader.