Laurent Bienvenu

Rupert Hölzl

Joseph S Miller

André Nies

The Denjoy alternative for computable functions

The Denjoy-Young-Saks Theorem from classical analysis states that for an arbitrary function f : R → R, the Denjoy alternative holds outside a null set. This means that for almost every real x, either the derivative of f exists at x, or the derivative fails to exist in the worst possible way: the limit superior of the slopes around x equals +∞, and the limit inferior -∞. Algorithmic randomness allows us to define randomness notions giving rise to different concepts of almost everywhere. It is then natural to wonder which of these concepts corresponds to the almost everywhere notion appearing in the Denjoy-Young-Saks theorem. To answer this question Demuth investigated effective versions of the theorem. In his first variation, the function f is stipulated to be computable, and in the second one the function f is only Markov computable. For this second version, Demuth introduced a strong notion of randomness (stronger for example than Martin-Löf randomness) now known as Demuth randomness, which he proved to be sufficient to satisfy the Denjoy alternative for all Markov computable functions. In this paper, we in turn investigate these two effective theorems. We first show that the set of points that fulfill the Denjoy alternative for computable functions coincides with the set of computably random reals. We then show that the set of points that fulfill the Denjoy alternative for Markov computable functions is strictly bigger than the set of Demuth random reals -showing that Demuth's sufficient condition was too strong -and moreover is incomparable with Martin-Löf randomness (meaning in particular that it does not correspond to any known set of random reals).

To prove these two theorems, we study density-type theorems, such as the Lebesgue density theorem and obtain results of independent interest. We show for example that the classical notion of Lebesgue density can be characterized in an interesting way by the only very recently defined notion of difference randomness: x being difference random is equivalent to it being Martin-Löf random and having positive density in every effectively closed class in which x is contained. This is to our knowledge the first analytical characterization of difference randomness. We also consider the concept of porous points, a special type of Lebesgue non-density points that are well-behaved in the sense that the "density holes" around the point are continuous intervals whose

Introduction

The aim of the theory of algorithmic randomness is to give a precise definition of what it means for a single object (usually a finite or infinite binary sequence) to be random. For infinite binary sequences (or reals, as any real can be represented by an infinite binary sequence) a satisfactory definition was given by Martin-Löf [START_REF] Martin-Löf | The definition of random sequences[END_REF]. Informally an infinite sequence x is Martin-Löf random if it does not belong to any set which can computably be shown to have measure 0. Even though Martin-Löf's definition is still believed to be the best one (at least the most well-behaved), many alternative notions of randomness have appeared in the literature over the years, some weaker than Martin-Löf randomness, some stronger. We refer the reader to the two recent books [7,11] for an extensive survey of these notions.

An interesting line of research is to study the connections between algorithmic randomness and computable analysis. The latter is concerned with effective versions of classical theorems in analysis, i.e. analytical theorems where the objects involved (functions, sets, points, etc.) are effective, i.e., computable in some sense. Now take a classical theorem of type "for any function f , for almost every x, . . . ". Its effective version will look like "for any effective function f , for almost every x, . . . ". Now, since there are only countably many effective functions (no matter what meaning is given to effective), one can reverse the quantifiers, and get a statement of type: "for almost every x, for every effective function f , ...". Therefore, a sufficiently random x will satisfy the conclusion of the theorem. For each such theorem, we can thus look at the following question: How much randomness is needed for x to satisfy the conclusion of the theorem? A recent example is a result proven in [START_REF] Bienvenu | Ergodic-type characterizations of algorithmic randomness[END_REF] and [START_REF] Johanna | Martin-Löf random points satisfy Birkhoff's ergodic theorem for effectively closed sets[END_REF] showing that Martin-Löf randomness is precisely the level of randomness needed to satisfy the most natural effective version of Birkhoff's ergodic theorem. Another is a result of Brattka, Miller and Nies [START_REF] Brattka | Randomness and differentiability[END_REF], which is closely connected to study conducted in this paper. They considered the effective version of the following theorem. If f is a non-decreasing function from R to R, then f is differentiable almost everywhere. Following the above scheme, they studied the class of reals x such that every computable non-decreasing function f is differentiable at x and were able to show that this class precisely coincides with the class of computably random reals. This was surprising as computable randomness -a weakening of Martin-Löf randomness that in many ways behaves quite pathologically -had very few known characterizations other than its original definition, and in particular no known analytical characterization.

Demuth [START_REF] Demuth | Reducibilities of sets based on constructive functions of a real variable[END_REF] studied an effective version of a related theorem, the so-called Denjoy-Young-Saks theorem, which asserts that any function f : R → R satisfies the Denjoy alternative at almost all points. The Denjoy alternative at a point x states that either the function is differentiable at x or the derivative fails to exists in the most dramatic way, i.e. the function f has around x arbitrarily large positive slopes and negative slopes. Demuth mainly studied the Denjoy alternative for Markov computable functions (which we will define in the moment) and studied the set DA of points x such that any Markov computable function satisfies the Denjoy alternative at x. Demuth introduced a randomness notion, now called Demuth randomness, which he proved to be sufficient to be in DA. The main result of this paper is that Demuth randomness is in fact too strong a condition, and that the class DA is strictly larger that the class of Demuth random reals.

We show that difference randomness (a notion of randomness strictly stronger than Martin-Löf randomness and strictly weaker than Demuth randomness) constitutes a sufficient condition for the Denjoy alternative to hold for Markov computable functions.

Theorem 1. Every difference random real belongs to DA.

We then show that this result cannot be strengthened to Martin-Löf randomness: in fact, Martin-Löf randomness is neither sufficient nor necessary to ensure the Denjoy alternative for Markov computable functions. Theorem 2. The set DA of reals which satisfy the Denjoy alternative for all Markov computable functions is incomparable under inclusion with the set of Martin-Löf random reals. These results will be proven in Section 3.

Preliminaries

We provide notation, recall the definitions of computable and Markov computable functions on the real numbers, and recall the definitions of Martin-Löf randomness, difference randomness, and computable randomness.

Basic notation. The set of finite binary sequences (we also say strings) is denoted by 2 <ω , and the set of infinite binary sequences, called Cantor space, is denoted by 2 ω . For a string σ, |σ| is the length of σ. If σ is a string, and x is either a string or an infinite binary sequence, we say that σ is a prefix of x, which we write σ x, if the first |σ| bits of x are exactly the string σ. Given an binary sequence, infinite or finite with length at least n, x↾n denotes the string made of the first n bits of x.

The Cantor space is classically endowed with the product topology. A basis of this topology is the set of cylinders: given a string σ ∈ 2 <ω , the cylinder [[σ]] is the set of elements of 2 ω having σ as a prefix. If A is a set of strings, [[A]] is the union of the cylinders [[σ]] with σ ∈ A. The Lebesgue measure λ (or uniform measure) on the Cantor space is the probability measure assigning to each bit the value 0 with probability 1/2 and the value 1 with probability 1/2, independently of all other bits. Equivalently it is the measure λ such that λ([[σ]]) = 2 -|σ| for all σ. We abbreviate λ([[σ]]) by λ(σ). Given two subsets X and Y, the second one being of positive measure, the conditional measure λ(X |Y) of X knowing Y is the quantity λ(X ∩ Y)/λ(Y). As before, if X or Y is a cylinder [[σ]], we will simply write it as σ.

Computable real-valued functions. Most of the paper will focus on functions from [0, 1] to R. The set [0, 1] is typically identified with 2 ω , where a real x ∈ [0, 1] is identified with its binary expansion. This extension is unique, except for dyadic rationals (of the form a2 -b with a, b positive integers) which have two. A cylinder [[σ]] will be commonly identified with the open interval (0.σ, 0.σ + 2 -n ), where 0.σ is the dyadic rational whose binary extension is 0.σ000 . . ..

We say that a function f : [0, 1] → R is computable (over the reals) if it can be effectively approximated with arbitrary precision. More precisely, f is computable (over the reals) if there exists a computable function f :

Q × N → Q and a computable ψ : N → N such that for all x ∈ [0, 1], |x -q| < 2 -ψ(n) ⇒ |f (x) -f (q, n)| < 2 -n .
Note that a computable function over the reals is by this definition necessarily continuous. A real x is computable if the constant function x is computable. Equivalently, a real is computable if its binary expansion, seen as a function from N to {0, 1} is computable.

We denote the set of computable reals by R c . The image of a computable real by a computable function is itself a computable real. Since the computable reals form a dense subset of the reals, a computable function is uniquely determined by its restriction R c → R c . The class of Markov computable functions is a larger class of functions R c → R c . As we just said, a real x is computable if there is a computable function β which computes its binary expansion. Any index i of β in an uniform enumeration (φ i ) i of partial computable functions is called a name for x. A function f : R c → R c is said to be Markov computable if from a name of x ∈ R c , one can effectively compute a name for f (x). More precisely, f is Markov computable if there exists a partial computable function f : N → N such that for all x ∈ R c , if i is a name for x, then f (i) is defined and is a name for f (x). Given a Markov computable function f , x ∈ [0, 1] and s ∈ N, we write sometimes use the notation f (x) s to denote the approximation of f (x) at stage s. Unless specified otherwise, a Markov computable function is always assumed to be total on [0, 1] ∩ R c . An important theorem of Tseitin [START_REF] Tseitin | Algorithmic operators in constructive metric spaces[END_REF] states that a total Markov computable function is always continuous on its domain.

We define the following analytical notations: for a function f , the slope at a pair a, b of distinct reals in its domain is

S f (a, b) = f (a) -f (b) a -b .
Recall the following definitions for the case that z is in the domain of f .

Df (z) = lim sup h→0 S f (z, z + h) and Df (z) = lim inf h→0 S f (z, z + h)
The derivative f ′ (z) exists if and only if these values are equal and finite.

In this article we will work with functions that are not necessarily defined on all reals, e.g. Markov computable functions. When working with these functions Df (z) and Df (z) are not defined for all z. Nonetheless, in case the set dom(f ) is a dense subset of [0, 1], one can consider the lower and upper pseudo-derivatives defined by:

D f (z) = lim inf h→0 + {S g (a, b) : a, b ∈ dom(f ) ∧ a ≤ x ≤ b ∧ 0 < b -a ≤ h}. Df (z) = lim sup h→0 + {S g (a, b) : a, b ∈ dom(f ) ∧ a ≤ x ≤ b ∧ 0 < b -a ≤ h}.
It is not true in general that if a function f is defined at a point z, then D f (z) = Df (z) and Df (z) = Df (z). This is true however when the function f is continuous on its (dense) domain, which is the case for computable and Markov computable functions. Note also that in this special case, one can replace, in the definition of D f and Df , dom(h) by any dense subset of dom(h) (for Markov computable functions, one could for example take Q instead).

We also later need the following technical lemma. Lemma 3. Let h : ⊆ [0, 1] → R + 0 be a computable function that is defined and non-decreasing on an effectively closed class C. Then h ↾ C can be extended to a function g : [0, 1] → R + 0 that is computable and non-decreasing on [0, 1].

Proof. Before we can prove Lemma 3 we prove the following easy claim. Claim Let C be an effectively closed class. Let h : ⊆ [0, 1] → R + 0 be a computable function with domain containing C. Then sup x∈C {h(x)} is right-c.e. and inf x∈C {h(x)} is left-c.e. uniformly in an index for C. Proof. We prove the statement for the supremum; the proof for the infimum is analogous. We use the signed digit representation of reals, that is every real is represented by an infinite sequence in {-1, 0, 1} ∞ .

We run in parallel an enumeration of C c and for all x ∈ [0, 1] (given by a Cauchy name (x n ) n∈N ) the computations of h(x) up to precision 2 -n . That is, we want to compute (h(x)) n , the n-th entry of a Cauchy name for h(x).

Due to uniform continuity, for each n there is a number n ′ such that for all x in order to accomplish the computation it suffices to have access to the initial segment (x 0 , . . . , x n ′ ) of the Cauchy name of x. When the computation of (h(x)) n halts for some x it also halts for all other x ′ which have a Cauchy name that begins with (x 0 , . . . , x n ′ ), since the computation is clearly the same. We do not know n ′ , so we build a tree of computations that branches into three directions (-1, 0 and 1) whenever we access a new entry of the Cauchy name of the input. We remove a branch of the tree when it gets covered by C c . Due to the existence of n ′ the tree will remain finite.

Write sup x∈C {h(x)}[n] for the approximation to the value sup x∈C {h(x)} that we achieve when we proceed as described with precision level 2 -n . If we increase the precision, more of C c may get enumerated before halting has occurred everywhere on the tree; so we see that the sequence (sup x∈C {h(x)}[n]+2 -n ) n→∞ is a right-c.e. approximation to sup x∈C {h(x)}. The claim is proved. ⋄ Now, since C is compact and closed, h is uniformly continuous on C, that is, for every ε > 0 there exists a single δ(ε) > 0 such that for any point x ∈ E the continuity condition

|y -x| < δ(ε) ⇒ |h(y) -h(x)| < ε is satisfied.
Idea. We do not know δ(ε) for a given ε, but we can search for it using in parallel the following construction for different candidate δ's:

We split the unit interval into intervals (I k ) k of length δ and write l k for the left border point of I k . Write i k for inf{h(x) | x ∈ I k ∩ E} and s k for sup{h(x) | x ∈ I k ∩ E} if these values exist. We use the above claim to approximate i k and s k for all intervals, and at the same time we enumerate C c , the complement of C.

We do this until we have found a δ (called ε-fit) such that every interval has been dealt with; by this we mean that for every interval I k we have either covered I k with C c , or we have found that s ki k < ε, that is we already know h up to precision ε. In the latter case we set our approximation to h to be the line from point (l k , i k ) to point (l k+1 , s k ); on the remaining intervals (the former case) we interpolate linearly. Call the new function g 0 . We can then output g 0 (x) up to precision ε at any point x ∈ [0, 1].

A problem with this construction. The following problem can occur with g 0 : Assume we have for some ε found a δ that is ε-fit. We construct g 0 as described and interpolate linearly on, say, the maximal connected sequence I k , . . . , I k+n , all contained in C c . But if we look at the same construction for g 0 at a better precision ε ′ < ε, we might actually enumerate more of C c until we find an ε ′ -fit δ ′ , and this might extend the sequence I k , . . . , I k+n to, say, I k-i , . . . , I k+n+j , all contained in C c . The linear interpolation on this sequence of intervals would then be significantly flatter than at level ε. So for some x ∈ I k-i ∪ • • • ∪ I k+n+j we might have that the approximation to g 0 with precision ε differs by more than ε from the approximation to g 0 with precision ε ′ , which is not allowed.

To fix this problem we need to define g inductively over all precision levels, and "commit" to all linear interpolations that have happened at earlier precision levels, as will be described now.

Formal construction. Assume we want to compute the n-th entry of a Cauchy name for g(x), that is we want to compute g(x) up to precision 2 -n . We say that we are at precision level n. We do not know δ(2 -n ) so we do the following with δ = 2 -p in parallel for all p until we find a δ that is n-fit, defined as follows:

Split the interval [0, 1] into intervals of length δ and write

I k = [(k -1) • 2 -p , k • 2 -p )
for the k-th interval and l k = (k -1) • 2 -p for the left border point of I k . For mathematical precision set

I p := [1 -2 -p , 1]. Call an interval I k n-treated if
there exists a smaller precision level n ′ < n where I k has been covered by C c and therefore a linear interpolation on I k has been defined. We say that δ is n-fit if

• for every interval I k we have that 1. I k is n-treated or 2. I k ∩ E = ∅ or 3. s k -i k < 2 -n
• and if for all k, where both I k and I k+1 fulfill condition 3, we have i k+1 < s k ;

that is, we have that intervals that directly follow each other have a "vertical overlap" in their approximations.

The following linear interpolation is an 2 -n -close approximation to g: First, inductively replay the construction for all precision levels n ′ < n to find all ntreated intervals. For the remaining intervals, run in parallel the right-c.e. and left-c.e. approximations to s k and i k , respectively, and the enumeration of C c , until for every interval either condition 2 or 3 are satisfied.

Build the following piecewise linear function: For all intervals that are already n-treated, keep the linear interpolations from the earlier precision level n -1. In all remaining intervals I k that fulfill condition 3 we set g to be the line from point (l k , i k ) to (l k+1 , s k ), that is, for

x ∈ I k we let g(x) = i k + (x -l k ) • (s k -i k ) l k+1 -l k = i k + (x -l k ) (s k -i k ) δ .
Now look at the remaining intervals that have not yet been assigned a linear interpolation. In every maximal connected sequence I k , . . . , I k+n of such intervals every interval must fulfill condition 2. We interpolate linearly over I k , . . . , I k+n in the straightforward way, that is we draw a line from point (s k , g(l k )) to point (s k+n+1 , g(l k+n+1 )) (strictly speaking g(l k ) is not yet defined, so use lim x→l k g(x) instead).

Verification. It is clear that g is everywhere defined and non-decreasing. Whenever h was defined on a point x ∈ I k inside E, g gets assigned a value between i k and s k and since

s k > h(x) > i k and s k -i k < 2 -n we have |h(x) -g(x)| < 2 -n .
To see that g is computable note that s k and i k are defined on any interval that is not entirely contained in C c and that these values can be approximated in a right-c.e. and left-c.e. way, respectively, by using the claim proved earlier in this proof.

λ(U n ) = 0. Definition 4. A sequence x ∈ 2 ω is called Martin-Löf random if there is no Martin-Löf test covering it, i.e., for any Martin-Löf test (U n ) n we have x ∈ n U n . A sequence x ∈ 2 ω is called weak-2-random if there is no strong test covering it, i.e., for any strong test (U n ) n we have x ∈ n U n . A sequence x ∈ 2 ω is called difference random if there is no difference test covering it, i.e., if for any difference test ((U n ) n , C ) we have x ∈ n (U n ∩ C ).
The notion of difference randomness was introduced by Franklin and Ng [START_REF] Franklin | Difference randomness[END_REF]. They proved that the set of difference random reals in fact coincides with the set of Martin-Löf random reals that are Turing incomplete. Proposition 5. For both Martin-Löf randomness and difference randomness, it is equivalent (see for example [7]) to require "almost avoidance": a sequence x ∈ 2 ω is Martin-Löf random (resp. difference random) if and only if for every Martin-Löf test (U n ) (resp. difference test ((U n ), C )), x only belongs to finitely many U n (resp. finitely many U n ∩ C ).

Note that this type of "almost avoidance" variation of definitions is not admissible for weak 2-randomness.

Another strengthening of Martin-Löf randomness is Demuth randomness. A Demuth test is a sequence (U n ) of effectively open sets, which is not necessarily uniformly c.e. but instead enjoys the following weak form of uniformity: there exists an ω-c.e. function f : N → N which for each n gives a c.e. index for a set of strings generating U n . Definition 6. A sequence x ∈ 2 ω is said to be Demuth random if for every Demuth test (U n ), x belongs to only finitely many U n .

The last notion of randomness we will discuss in the paper is computable randomness. Its definition involves the notion of martingale.

Definition 7. A martingale is a function d : 2 <ω → [0, ∞) such that for all σ ∈ 2 <ω d(σ) = d(σ0) + d(σ1) 2 .
Intuitively, a martingale represents a betting strategy where a player successively bets money on the values of the bits of an infinite binary sequence (doubling its stake when guess is correct); d(σ) then represents the capital of the player after betting on initial segment σ. With this intuition, a martingale succeeds against a sequence x if lim sup n d(x↾n) = +∞. A computably random sequence is a sequence against which no computable betting strategy succeeds. In other words: Definition 8. A sequence x ∈ 2 ω is computably random if and only if for every computable martingale d, lim sup n d(x↾n) < +∞ We denote by MLR, W2R, DiffR, DemR, CR the classes of Martin-Löf random, weak-2random, difference random, Demuth random and computably random sequences respectively. Given a sequence x ∈ 2 ω , the following implications

x ∈ W2R ց x ∈ DiffR -→ x ∈ MLR -→ x ∈ CR ր x ∈ DemR
hold and no other implication holds in general (other than those which can be derived by transitivity from the above diagram). See for example [11] for a detailed exposition.

Density and porosity

In this section, we initiate the study of effective aspects of Lebesgue density, which will be crucial in the proofs of Theorems 1 and 2. In this section, we mostly focus on what is needed for the proofs of these theorems. In Section 4 we will provide further results on density.

Let us first recall the concept of Lebesgue density:

Definition 9. We define the (Lebesgue) density ρ of a set C ⊆ R at a point x to be the quantity

ρ(x|C ) := lim inf δ→0 + λ([x -δ, x + δ] ∩ C ) λ([x -δ, x + δ]) ,
where λ is the Lebesgue measure.

Intuitively, this measures what fraction of the space is filled by C around x if we "zoom in" arbitrarily close. Note that the density of a set at a point is between 0 and 1.

Again, in the rest of the paper, we will freely identify 2 ω and [0, 1] and will therefore be able to talk about density of a set C ⊆ 2 ω at a point.

Theorem 10 (Lebesgue density theorem). Let C ⊆ R be a measurable set. Then ρ(x|C ) = 1 for all points x ∈ C outside a set of measure 0.

The concept of porosity of a set at a point forms a cornerstone of the proofs of Theorems 1 and 2. The following definition is due to E.P. Dolzhenko, 1967 (see for instance [2, 5.8.124], but note the typo in the definition there).

Definition 11. We say that C is porous at x via ε > 0 if for each α > 0 there exists β with 0 < β ≤ α such that (xβ, x + β) contains an open interval of length εβ that is disjoint from C. We say that C is porous at x if it is porous at x via some ε. We call non-porosity point a real x such that every effectively closed class to which it belongs is non-porous at x.

Clearly porosity of C at x implies ρ(x|C) < 1. Therefore, given an effectively closed class C, for almost every point x of this class, C is not porous at x. Since there are only countably many effectively closed sets, it follows that the set of non-porosity points has measure 1. Our next proposition makes this more precise.

Lemma 12. Let C ⊆ [0, 1] be an effectively closed class. If z ∈ C is difference random, then C is not porous at z.
Proof. In this proof, we say that a string

σ meets C if [[σ]] ∩ C = ∅.
Fix c ∈ N. We build a difference test covering the points x at which C is porous via 2 -c+2 . For each string σ consider the set of minimal "porous" extensions at stage t,

N t (σ) = ρ σ ∃τ |τ | = |ρ| ∧ |0.τ -0.ρ| ≤ 2 -|ρ|+c ∧ [[τ ]] ∩ C t = ∅ ∧ ρ is minimal with this property .
Note that by the formal details of this definition even the "holes" τ are ρ's, and therefore contained in the sets N t (σ). This will be essential for the proof of the first of the following two claims. In contrast to this, note that if ρ meets C then ρ = τ , which implies

ρ∈Nt(σ) ρ meets C 2 -|ρ| ≤ (1 -2 -c )2 -|σ| . (1)
At each stage t of the construction we define recursively a sequence of anti-chains as follows.

B 0,t = {∅}, and for n > 0 :

B n,t = {N t (σ) : σ ∈ B n-1,t } Claim. If a string ρ is in B n,t then it has a prefix ρ ′ in B n,t+1
. This is clear for n = 0. Suppose inductively that it holds for n -1. Suppose further that ρ is in B n,t via a string σ ∈ B n-1,t . By the inductive hypothesis there is σ ′ ∈ B n-1,t+1 such that σ ′ σ. Since ρ ∈ N t (σ), ρ is a viable extension of σ ′ at stage t + 1 in the definition of N t+1 (σ ′ ), except maybe for the minimality. Thus there is ρ ′ ρ in N t+1 (σ ′ ). This establishes the claim. 3

Claim. For each n, t, we have

{2 -|ρ| : ρ ∈ B n,t ∧ ρ meets C} ≤ (1 -2 -c ) n .
This is again clear for n = 0. Suppose inductively it holds for n -1. Then, by [START_REF] Bienvenu | Ergodic-type characterizations of algorithmic randomness[END_REF],

ρ∈Bn,t ρ meets C 2 -|ρ| = σ∈B n-1,t σ meets C ρ∈Nt(σ) ρ meets C 2 -|ρ| ≤ σ∈B n-1,t σ meets C 2 -|σ| (1 -2 -c ) ≤ (1 -2 -c ) n .
This establishes the claim.

3

Now let U n = [[ t B n,t ]].
Clearly the sequence (U n ) n∈N is uniformly effectively open. By the first claim we have

U n = t [[B n,t ]], so the second claim implies that λ(C ∩U n ) ≤ (1-2 -c ) n .
Every interval (a, b) ⊆ [0, 1] contains an interval of the form [[ρ]] for a dyadic string ρ such that the length of [[ρ]] is no less than (ba)/4. Therefore, if C is porous at x via 2 -c+2 then x ∈ n U n for each n. Take a computable subsequence (U g(n) ) n∈N such that λ(C ∩ U g(n) ) ≤ 2 -n to obtain a difference test that x fails.

Effective forms of the Denjoy-Young-Saks Theorem

We begin with the formal definition of the Denjoy alternative.

Definition 13. Let f :⊆ [0, 1] → R be a partial function whose domain is dense. We say that f satisfies the Denjoy alternative at x if • either the pseudo-derivative of f at x exists (meaning that Df (x) = D f (x))

• or Df (x) = +∞ and D f (x) = -∞ Intuitively this means that there are two ways for the alternative to hold: either the function behaves well on x by having a derivative at this place, or, if it behaves badly, it does so in the worst possible way, that being the fact that the limit superior and the limit inferior diverge as much as possible. The Denjoy-Young-Saks theorem (see, e.g., Bruckner [START_REF] Bruckner | Differentiation of real functions[END_REF]) states that the Denjoy alternative holds at almost all points for any function f .

Computable randomness means that all computable function satisfy the Denjoy alternative

Definition 14 (Demuth [START_REF] Demuth | Preprint for Remarks on Denjoy sets[END_REF]). A real z ∈ [0, 1] is called Denjoy random (or a Denjoy set) if for no Markov computable function g we have D g(z) = +∞.

In a preprint by Demuth [5, p. 6] it is shown that if z ∈ [0, 1] is Denjoy random, then for every computable f : [0, 1] → R the Denjoy alternative holds at z. By combining this result with the results in [START_REF] Brattka | Randomness and differentiability[END_REF] we can achieve the following result that provides a pleasing characterization of computable randomness through differentiability of computable functions.

Theorem 15 (Demuth, Miller, Nies, Kučera). The following are equivalent for a real z ∈ [0, 1].

1. z is Denjoy random.

2. z is computably random.

3. For every computable f : [0, 1] → R the Denjoy alternative holds at z.

Note that all we needed for the last implication was that g(q) is a computable real uniformly in a rational q ∈ [0, 1]∩Q. Thus, in Definition 14 we can replace Markov computability of g by this weaker hypothesis.

Proof. (1) ⇒ (3) is a result of Demuth [START_REF] Demuth | Preprint for Remarks on Denjoy sets[END_REF].

(3) ⇒(2): Let f be a nondecreasing computable function. Then f satisfies the Denjoy alternative at z. Since D f (z) ≥ 0, this means that f ′ (z) exists. This implies that z is computably random by Brattka et al. [START_REF] Brattka | Randomness and differentiability[END_REF]Thm. 4.1].

( Define a computable martingale M on extensions τ σ that succeeds on (the binary expansion of) z. In the following τ ranges over such extensions.

First note that S g (τ ) is a computable real uniformly in τ . Furthermore, the function τ → S g (τ ) satisfies the martingale equality, and succeeds on z in the sense that its values are unbounded (even converge to ∞) along z. However, this function may have negative values; informally, this is as if we were allowed to "bet with debt" because we can increase our capital at a string σ0 beyond 2S g (σ) by incurring a debt, i.e. negative value, at S g (σ1). We now define a computable martingale M that succeeds on z and does not bet with debt.

Let M(∅) = S g (∅). Suppose now that M(τ ) has been defined and is positive. Case 1. There is u ∈ {0, 1} such that, where v = 1u, we have S(τ v) 1 < 1 (this is the second term in the Cauchy name for the computable real S(τ v), which is at most 1/2 away from that real). Then S(τ v) < 2. By choice of a, b we now know that z is not an extension of τ v. Thus, we let M double its capital along τ u, let M(ρ) = 0 for all ρ τ v. (The martingale M stops betting on these extensions.) Case 2. Otherwise. Then S(τ v) > 0 for v = 0, 1. We let M bet with the same betting factors as S g :

M(τ u) = M(τ ) S g (τ u) S g (τ )
for u = 0, 1.

Note that M(τ u) > 0.

If Case 1 applies to infinitely many initial segments of the binary expansion of z, then M doubles its capital along z infinitely often. Since M has only positive values along z, this means that lim n M(z ↾ n ) fails to exist, whence z is not computably random by the effective version of the Doob martingale convergence theorem [7, Theorem 7. 1.3].

Otherwise, along z, M is eventually in Case 2. So M succeeds on z because S g does.

Difference randomness implies that all Markov computable function satisfy the Denjoy alternative

We now turn to the proof of Theorem 1. Using the results of the previous section, it will be enough to prove the following.

Proposition 16. Let x ∈ 2 ω be a computably random real that is also a non-porosity point. Then x ∈ DA, i.e., all Markov computable functions satisfy the Denjoy alternative at x.

To get Theorem 1 from this proposition, remember that a difference random point is always computably random, and, by Lemma 12 a difference random real is also always a non-porosity point.

Proof. We first prove a lemma, which takes advantage of the special way in which a set is arranged around its non-porosity points.

Lemma 17. Suppose that f : ⊆ [0, 1] → R is Markov computable. Let C ⊆ [0, 1]
be an effectively closed class such that there is an n with D f (z) > -n for all z ∈ C. Let the computably random real x ∈ C be a non-porosity point of C. Then f is differentiable at x.

Proof. We effectivize an argument of Bogachev [2, p. 371]. Replacing f by f (x) + nx, we may assume that for x ∈ C, we have

∀a, b [r ≤ a ≤ x ≤ b ≤ s → S f (a, b) 0 > 1]. Let f * (x) = sup a≤x f (a). Then f * is nondecreasing on C.
Claim. The function f * ↾ E is computable. To see this, recall that p, q range over [0, 1] ∩ Q, and let f * (x) = inf q≥x f (q). If x ∈ C and f * (x) < f * (x) then x is computable: fix a rational d in between these two values. Then p < x ↔ f (p) < d, and q > x ↔ f (q) > d. Hence x is both left-c.e. and right-c.e., and therefore computable. Now a Markov computable function is continuous at every computable x. Thus f * (x) = f * (x) for each x in C.

To compute f (x) for x ∈ C up to precision 2 -n , we can now simply search for rationals p < x < q such that 0 < f (q) n+2f (p) n+2 < 2 -n-1 , and output f (p) n+2 . If during this search we detect that x ∈ C, we stop. This shows the claim.

3

By Lemma 3 there is a computable nondecreasing function g defined on [0, 1] that extends f * . Then by a classic theorem of Lebesgue, g ′ (x) exists for a.e. x ∈ [0, 1]. A result by Brattka, Miller and Nies [START_REF] Brattka | Randomness and differentiability[END_REF]Thm. 4.1] states that in fact computable randomness of x is enough to guarantee the existence of g ′ (x).

It therefore suffices to show that for each x ∈ C such that g ′ (x) is defined and C is not porous at x, we have Df (x) ≤ g ′ (x) ≤ D f (x). Since D f (x) ≤ Df (x), this would establish the theorem.

To see this, we show Df (x) ≤ g ′ (x), the other inequality being symmetric. Fix

ε > 0. Choose α > 0 such that ∀u, v ∈ C [(u ≤ x ≤ v ∧ 0 < v -u ≤ α) → S f * (u, v) ≤ g ′ (x)(1 + ε)] (2)
S f (a, b) ≤ f * (v) -f * (u) b -a ≤ S f * (u, v)(1 + 4ε) ≤ g ′ (x)(1 + 4ε)(1 + ε).
We are now ready to prove Proposition 16. Suppose x is computably random and is a non-porosity point. Let f be a Markov computable function. Suppose that f does not satisfy the Denjoy alternative at x by strong failure of the existence of the pseudo-derivative at x. We therefore are D f (x) > -∞ or Df (x) < +∞. Suppose the first one holds (the proof for the other case is similar), and take an n such that D f (x) > -n. By definition of D , this means that for some fixed positive rational ε and some fixed t, x belongs to the effectively closed class:

C = {x ∈ [0, 1] | ∀q 1 , q 2 ∈ Q s.t. x ∈ [q 1 , q 2 ] ∧ |q 2 -q 1 | < ε, S f (q 1 , q 2 ) t > -n}
We can therefore apply Proposition 16 to this class C (every point z ∈ C is such that D f (z) > -n, x belongs to C, x is computably random and is a non-porosity point). Therefore, f is differentiable at x, and thus the Denjoy alternative holds indeed.

The class DA is incomparable with the Martin-Löf random reals

Theorem 18. There exists a real x which is not Martin-Löf random but nonetheless satisfies the Denjoy alternative for all constructive functions.

Proof sketch. The Denjoy alternative at x can be met in two ways. We will say "the DA for f is fulfilled by existence" if the (pseudo-)derivative of f at x exists and say that "the DA for f is fulfilled by failure" in the other case. To prove the statement we construct a set x by forcing that is CR, not MLR and for every Markov computable function either fulfills the DA by failure for this function or is a density point (and therefore certainly not a porosity point) of a certain effectively closed class L such that L and f fulfill the requirements of Lemma 17. The argument to prove the statement then goes like this: if we fulfill the DA by failure we are done. Otherwise we will be in the effectively closed class L. Since x ∈ CR we can invoke Lemma 17 to show that f is differentiable and therefore fulfills the DA by existence. Assume we have constructed the initial segment σ of x so far, and are given a computable martingale M. The most interesting part of the argument is how to ensure that we are density points of certain effectively closed classes of the form L := {x σ | M(x↾n) < ε for all n > |σ|}. To do this we need to make sure that the density of x in L will be 1 in the limit. At every stage of the construction we will make sure that the density of x is at least 1q for some q by choosing the right extension σ ′ of σ. When we later extend σ ′ further we will make q smaller and smaller while forever staying inside L. This way in the limit we reach density 1 in L.

To achieve density 1q as required we look at the quantity m := inf τ σ d(τ ). We interpret m as an amount of capital that the martingale M has put on a savings account and is not touching anymore. Of course this implies that M also has less capital available for betting and can therefore reach capital ε only on a smaller fraction of the extensions of σ. By applying the Ville-Kolmogorov inequality for martingales to Mm it is clear that M can reach capital ε only on a set of extensions of σ of relative measure 1 -M (σ)-m ε-m . Or, in other words, σ has density 1 -(M(σ)m)/(εm) in L. By replacing σ with a long enough extension we can make sure that d(σ) is arbitrarily close to m and thereby raise the density to the desired level 1q.

Formal construction. We will use a finite extension argument which we present in the language of forcing. Our set of conditions P will have the form M, σ, ε where M is a computable martingale, σ a string and ε a rational, and such that M(σ) < ε. We say that

M ′ , σ ′ , ε ′ extends M, σ, ε which we write M ′ , σ ′ , ε ′ ≤ M, σ, ε if • M ′ ≥ M • σ σ ′ and M ′ (τ ) < ε for all σ τ σ ′ • ε ′ ≤ ε
To each condition p = M, σ, ε we associate the effectively closed set (of positive measure)

L M,σ,ε = {x ∈ 2 ω | (∀τ ) σ τ ≺ x → M(τ ) < ε} (notice that M ′ , σ ′ , ε ′ ≤ M, σ, ε implies L M ′ ,σ ′ ,ε ′ ⊆ L M,σ,ε )
We claim that for a sufficiently generic filter G ⊆ P, the closed set

M,σ,ε ∈G L M,σ,ε
is a singleton {x} and x is Martin-Löf random but satisfies the Denjoy alternative for every Markov computable function.

Claim 1. For any filter G ⊆ P, the set G = M,σ,ε ∈G L M,σ,ε is non-empty. If G is sufficiently generic, G is in fact a singleton x which is equal to the union of the strings appearing in the conditions of G. Proof. By compactness, if G is empty, then there are finitely many conditions M i , σ i , ε i such that i L M i ,σ i ,ε i . Since G is a filter, let M * , σ * , ε * be a condition extending all the M i , σ i , ε i . We have i L M i ,σ i ,ε i ⊇ L M * ,σ * ,ε * , and the latter is non-empty as it has positive measure.

Now, for all n, let D n to be the set of conditions M, σ, ε with |σ| ≥ n. One can see that D n is dense: indeed, for a condition M, σ, ε , if |σ| < n, then diagonalizing against M during n -|σ| steps, one can find an extension τ of σ of length at least n such that M, τ, ε extends M, σ, ε . Therefore if G is sufficiently generic, it contains conditions M, σ, ε for arbitrarily long σ. Since G is a filter, all the strings appearing in its elements must be comparable, hence there is a unique real x that extends them all. Therefore G contains at most the singleton {x}. Since G is non-empty, it is equal to the singleton {x}.

3 From now on we assume that "sufficiently generic" means in particular that G is a singleton {x}. Claim 2. If G is sufficiently generic, and M, σ, ε is a condition in G, then M(x↾n) < ε for all n ≥ |σ|. Proof. Trivial by definition of x.

3

Claim 3. If G is sufficiently generic, x is computably random. Proof. This is the usual argument. Let N be a computable martingale. Let M, σ, ε be a condition. Let δ be a rational such that M(σ) < εδ. Then, setting M ′ = M + 2 -|σ| δN, it is easy to see that M ′ , σ, ε is a condition, and that N does not succeed on any element of L M ′ ,σ,ε . 3

Claim 4. If G is sufficiently generic, and M, σ, ε is a condition in G, then x is a density point of L M,σ,ε .

Proof. Suppose M, σ, ε is a condition, i.e., M(σ) < ε. We want to show that x is a density point of L M,σ,ε i.e. that the conditional measure of L M,σ,ε below x↾n tends to 1. Fix δ arbitrarily small. Let ε ′ < ε be the infimum of the values M can take on extensions of σ, i.e., m = inf{M(τ ) | τ σ}

Then take ε ′ a rational between m and ε that is much closer to m than to ε. More precisely, take it such that

ε ′ -m ε -m < δ
Now, pick τ σ such that M(τ ) < ε ′ (which must exist by definition of m and ε ′ ). It is clear that M, τ, ε ′ is an extension of M, σ, ε . We claim that if this new condition is in G, then the conditional measure of L M,σ,ε below x↾n for all n ≥ |τ | is at least 1δ, which will complete the proof.

To prove this claim, pick some n ≥ |τ | and consider the initial segment x↾n, which extends τ . Define the martingale N by N(ν) = M(x↾n ⌢ ν)m. This is a martingale of initial capital M(τ )m which is non-negative by definition of m. Therefore, the Ville-Kolmogorov inequality yields

µ z | (∀k) N(z↾k) < ε -m ≥ 1 - M(τ ) -m ε -m > 1 -δ
Now, notice that by definition of N, the measure µ z | (∀k) N(z↾k) < εm is exactly µ x↾n (L M,τ,ε ), but also µ x↾n (L M,σ,ε ) as τ is an extension of σ. Therefore, we have

µ x↾n (L M,σ,ε ) > 1 -δ for all n ≥ |τ |. 3
Claim 5. If G is sufficiently generic, then every constructive function satisfies the Denjoy alternative at x. Proof. Let M, σ, ε be a condition and let f be a constructive function. We distinguish two cases.

Case 1. The elements of the set L M,σ,ε have a uniform bound on their lower derivative. Formally, (∃n

) ∀z ∈ L M,σ,ε D f (z) > -n
In this case, G being sufficiently generic ensures that x is computably random (Claim 3) and is a density point of L M,τ,ε (Claim 4), so we can directly apply Lemma 17, from which we get that f is differentiable at x.

Case 2. If the above case does not hold, then for any large given n, say n = |σ| + 1, one can find some z ∈ L M,τ,ε and a, b ∈ R c with a < b such that

• z ∈ (a, b) • |b -a| < 2 -n • f (b)-f (a) b-a < -n
In that case, one can extend M, σ, ε to M, τ, ε where [τ ] ⊆ (a, b). Now, G being sufficiently generic, we ensure that either D f (x) = -∞ (when there are conditions M, σ, ε in G with arbitrarily large σ that put us in Case 2) or that f is differentiable at x (when for all sufficiently large σ, all M, σ, ε in G put us in Case 1). 3 Claim 6. If G is sufficiently generic, x is not Martin-Löf random. Proof. This part is quite standard. Let M, σ, ε be a condition and let c be a constant. Since one can computably diagonalize against a computable martingale there exists a computable sequence z extending σ such that M(z↾n) < ε for all n > |σ|. Since z is computable, it is possible to take n large enough so that τ = z↾n satisfies K(τ ) < |τ |c. This proves that a sufficiently generic G will yield a sequence x that is not Martin-Löf random. ). There are two cases.

1. Either adding this interval does not change the value of Ω (i.e., Ω s+1 = Ω s ). In that case, define the function F to be equal to zero on the whole interval (σ).

2. Or, this interval does change the value of Ω: Ω s+1 > Ω s . In this case, define F on (a, b) to be the triangular function taking value 0 on the endpoints of (σ) and reaching the value v at the middle point, where v is defined as follows. Let t be the last stage at which the previous increase of Ω occurred (i.e., t is maximal such that t < s and Ω t+1 > Ω t ). Let n be the smallest integer such that the real interval

[Ω t , Ω t+1 ] contains a multiple of 2 -n . For that n, set v = 2 -n/2 .
First, we see that the restriction f of F to R c is Markov computable: given a code i, we try to compute the real x coded by i (remember that such an x might not exist) until we find a sufficiently good estimate a < x < b, with a, b dyadic, such that the interval [a, b] is contained in one of the intervals (σ) appearing in the enumeration of U 1 . It is then easy to compute F at x as one can decide which of the above cases hold, and both the zero function and the triangular function are computable on R c (for the triangular function, remark that the value n of the construction can be found computably).

We claim that the function f does not satisfy the Denjoy alternative at Ω. More precisely, we have Df (Ω) = 0 and D f (Ω) = -∞. Notice that f is equal to 0 on (Ω, 1] ∩ R c and nonnegative on [0, Ω) ∩ R c , taking the value 0 at computably real points arbitrarily close to Ω (at least the endpoints of intervals (σ) enumerated on the left of Ω), therefore Df (Ω) = 0 is clear. To see that D f (Ω) = -∞, consider for all k the dyadic real a k which is a multiple of 2 -k , is smaller than Ω and such that Ωa k < 2 -k . Since a k < Ω, there exists a stage t such that a n ∈ [Ω t , Ω t+1 ]. Let s > t be the next stage at which Ω increases. By definition, F is then defined to be a triangular function on [Ω s , Ω s+1 ] of height 2 -n/2 , where n has to be greater than k as [Ω s , Ω s+1 ] does not contain any multiple of 2 -k (a k is the largest such real that is smaller than Ω). Thus, calling x k the middle point of [Ω s , Ω s+1 ], we have

S f (x k , Ω) = f (Ω) -f (x k ) Ω -x ≤ 0 -2 -k/2 2 -k ≤ -2 k/2 ;
and since this happens for all k we have D f (Ω) = -∞.

It remains to show that the function F is continuous on [0, 1]. But this is almost immediate as one can write F = n h n where h n is the function equal to 0 except on the intervals on which F is a triangular function of height 2 -n/2 , and on that interval h n = F . It is obvious that the h n are continuous and of magnitude 2 -n/2 . Therefore n ||h n || < ∞, so by the Weierstrass M-test we can conclude that the convergence is uniform hence the function n h n is continuous.

Positive density as a randomness notion

We return to the notion of positive density and give an interesting characterization of incomplete Martin-Löf random sets.

Theorem 20. The following statements are equivalent for a real x.

1.

x is difference random.

2.

x is Martin-Löf random and x has incomplete Turing degree.

λ(U k ∩ C ) = σ∈G k λ(C ∩ [σ]) = σ∈G k 2 -|σ| • λ(C | [σ]) ≤ σ∈G k 2 -|σ| • 2 -k ≤ 2 -k .
Since x ∈ C , by the original assumption, this difference test clearly covers x.

(3) ⇒ (2): Suppose now that x is Martin-Löf random and Turing complete. We are going to show that x has lower density 0 inside some effectively closed class C . We show that, given a rational ε, we can effectively construct an effectively closed class C ε such that x ∈ C ε and λ(C ε | x↾n) < ε for some n. It will then suffice to let C := ε C ε for an effective list of ε's that converge to 0. Idea. Fix ε > 0. In this construction, we will build an auxiliary c.e. set W . By the recursion theorem, since x is complete, we can assume to know in advance a Turing reduction Γ such that Γ x = W .

In order to lower the density of C ε around x we need to remove many reals from C ε . Since we don't know x this comes at the risk of inadvertently removing x as well. The approach of the proof is then to make use of the fact that we control W . We keep observing the results of the reduction Γ relative to all possible oracles and wait until we see a certain type of behavior (reduction outputs 0) on all oracles except fraction ε. As soon as this happens we change W in such a way that it does exactly not show this behavior. Since x computes W it certainly cannot be among the 1ε fraction of oracles showing the special behavior, so we can safely remove them from C ε .

Of course it must be avoided that we wait forever, since in that case the measure of C ε would forever remain equal to 1. It will therefore be necessary to argue why we can be sure that we will eventually observe the special behavior. To see this, we will argue that if we never observe that behavior, x is in a descending chain of sets U k such that U k always has measure 1ε relative to U k-1 , and that this chain actually is a Martin-Löf test covering x. This of course contradicts x ∈ MLR.

Formal construction. Look at the following effective procedure P (σ, k, ε) that enumerates the complement of C ε . 1) Pick a fresh integer n = n(σ, k).

2) Enumerate the set V of reals y that extend σ and satisfy Γ y (n) = 0. Due to the use principle this will always happen on whole open cylinders of y's. Therefore we can represent V by a c.e. enumeration of finite strings. It is easy to see that we can force this enumeration to be prefix-free. As long as the conditional measure of V above σ does not exceed 1ε, put every enumerated string τ into U k and for each of them start the procedure P (τ, k + 1, ε).

3) If at some stage s some new τ is found such that Γ τ (n) = 0 but the conditional measure U k [s]∪{τ } above σ exceeds 1-ε, then enumerate n into W , enumerate all of U k [s]∪{τ } in the complement of C ε , and terminate the whole tree of procedures.

  Randomness notions. As we have seen above, an open set U ⊆ 2 ω is a union of cylinders. If it is a union of a computably enumerable (c.e.) family of cylinders, it is said to be effectively open (or c.e. open). A set is called effectively closed set if its complement is effectively open. If (U n ) is a sequence of open sets, it is said a to be a uniformly c.e. sequence of open sets if there is a sequence (W n ) of uniformly c.e. sets of strings such that each U n is the union of the cylinders generated by the strings in W n . A Martin-Löf test is a uniformly c.e. sequence (U n ) n of open sets such that for all n, λ(U n ) < 2 -n . A difference test is a pair ((U n ) n , C ) of a uniformly c.e. sequence (U n ) n of open classes and a single effectively closed class C such that for all n, λ(U n ∩ C ) < 2 -n . A strong test is a sequence of uniformly c.e. sequence (U n ) n of open sets with the weaker condition that lim n

  ) ⇒ (1): Given a binary string σ, we write S f (σ) to mean S f (a, b) where (a, b) = [[σ]]. By hypothesis z is incomputable, and in particular not a rational. Suppose that the function g is Markov computable and D g(z) = +∞. Choose dyadic rationals a, b such that (a, b) = [[σ]] for some string σ, z ∈ (a, b) ⊆ [0, 1] and S g (r, s) > 4 for each r, s such that z ∈ (r, s) ⊆ (a, b).

  furthermore, since C is not porous at x, for each β ≤ α, the interval (xβ, x + β) contains no open subinterval of length εβ that is disjoint from C. Now suppose that a, b ∈ [0, 1] ∩ Q, a < x < b and β = 2(ba) ≤ α. There are u, v ∈ C such that 0 ≤ au ≤ εβ and 0 ≤ vb ≤ εβ. Since u, v ∈ C we have f * (u) ≤ f (a) and f (b) ≤ f * (v). Therefore vu ≤ ba + 2εβ = (ba)(1 + 4ε). It follows that

3 .

 3 x is Martin-Löf random and a point of positive lower density in every effectively closed class C with x ∈ C , that is, ρ(x|C ) = 0.Proof. The equivalence between (1) and (2) has been shown by Franklin and Ng[START_REF] Franklin | Difference randomness[END_REF].(1) ⇒ (3): Proof by contraposition. Assume that x ∈ MLR and that for all ε there is an n such that λ(C | x↾n) < ε. Then for all k letU k := {z | ∃n λ(C | z↾n) < 2 -k }.Since C is effectively closed, these classes are uniformly effectively open. Let G k be a minimal prefix-free set of strings generating U k . Then the following computation shows that (U k ) k is a difference test.

3

  Theorem 19. There exists a Markov computable function f for which the Denjoy alternative does not hold at Chaitin's Ω. Moreover, f can be taken to be uniformly continuous, i.e., it can be built in such a way that it has a (unique) continuous extension to [0, 1].

Proof. Let (U n ) be a universal Martin-Löf test, i.e. a test such that all reals that are not in MLR are covered by it (the existence of such a Martin-Löf test is well-known). No computable real can be Martin-Löf random, every x ∈ R c belongs to U 1 . Let Ω be the leftmost point of the complement of U 1 . Since U 1 is a c.e. open set Ω can be approximated from below by the computable sequence of rationals (Ω s ) s , where Ω s is the leftmost point of U 1 [s] (the approximation of U 1 after s stages). Our function f is defined as the restriction to R c of the following function F . Outside U 1 , F is equal to 0. On U 1 , it is constructed sequentially as follows. At stage s + 1, enumerate a new interval (σ) inside U 1 (we can assume that it is disjoint from U 1

[s]

The second author is supported by a Feodor Lynen postdoctoral research fellowship by the Alexander von Humboldt Foundation.

Verification. We need to verify that running P (λ, 0, ε) actually produces C ε as desired. First, notice that x remains in C ε at all time during the construction. Indeed, when we put a string τ into the complement of C ε during some procedure P (σ, k, ε) at step 3, this τ satisfies Γ τ (n) = 0, and we precisely make sure at that point that n ∈ W . Since Γ x = W , this shows that τ is not a prefix of x.

Secondly, note that if for some prefix σ of x and some k, the procedure P (σ, k, ε) gets executed and reaches step 3, then we are done since step 3 ensures that λ(C ε | σ) < ε. So we need to argue that the conditions for step 3 will eventually be met. Assume that this is not the case. Then the following claim states that U k will become defined for all k ∈ N. Claim. Let σ be a prefix of x and k an integer. If the procedure P (σ, k, ε) is executed but never reaches step 3, then some longer prefix σ ′ of x is put into U k and procedure P (σ ′ , k+1, ε) is executed. Proof. Indeed, if step 3 is never reached, then n = n(σ, k) never gets enumerated in W , therefore Γ x (n) = W (n) = 0, which by definition of step 2 shows that some prefix σ ′ of x is put into U k and procedure P (σ ′ , k + 1) is executed.

3 Observe that (U k ) k is a Martin-Löf test, by induction: every time a string σ is enumerated U k , some of its extensions are enumerated into U k+1 during procedure P (σ, k + 1, ε). The relative weight of these strings above σ is at most 1ε, therefore we have

The claim shows that if step 3 is never reached in any of the executed procedures P (σ, k, ε) with σ a prefix of x, then x ∈ [U k ] for all k. This contradicts the fact that x is Martin-Löf random.

Together with Lemma 12 we get the following corollary. To the best of our knowledge there exists no direct proof of this fact.

Corollary 21. For any x ∈ MLR the following implication holds: If for all effectively closed classes C with x ∈ C it holds that ρ(x|C ) > 0 then for all effectively closed classes C with x ∈ C we have that C is not porous at x. Note that the set of weakly 2-random sequences is contained in the set D := {x | ∀ Π 0 1 C : ρ(x|C ) = 1}. This is because for x to have ρ(x|C ) < 1 in some C can be written as ∃ε, δ 0 ∀δ < δ 0 : λ([x-δ,x+δ]∩C ) λ([x-δ,x+δ]) < 1ε, which is a Σ 0 2 condition. Due to the Lebesgue density theorem the set of these x (for each C ) is also null, so they are covered by a strong test.


Giovanni Peccati

Cengbo Zheng

Universal Gaussian fluctuations on the discrete Poisson chaos

Keywords: Central Limit Theorems, Contractions, Discrete Poisson Chaos, Universality. 2010 Mathematics Subject Classification: 60F05, 60G51, 60G57, 60H05

We prove that homogenous sums inside a fixed discrete Poisson chaos are universal with respect to normal approximations. This result parallels some recent findings, in a Gaussian context, by Nourdin, Peccati and Reinert (2010). As a by-product of our analysis, we provide some refinements of the CLTs for random variables on the Poisson space proved by Peccati, Solé, Taqqu and Utzet (2010), and by Peccati and Zheng (2010).

Introduction

Overview

A universality result is a mathematical statement implying that the asymptotic behaviour of a large random system does not depend on the distribution of its components. Universality results are one of the leading themes of modern probability, distinguished examples being the Central Limit Theorem (CLT), the Donsker Theorem, or the Semicircular and Circular Laws in random matrix theory.

In this paper, we shall prove a new class of universality statements involving homogeneous sums based on a sequence of centered independent Poisson random variables. Homogeneous sums (see Definition 1.1) are almost ubiquitous probabilistic objects: for instance, they provide archetypal examples of U -statistics, and they are the building blocks of such fundamental collections of random variables as the Gaussian Wiener chaos, the Poisson Wiener chaos or the Walsh chaos. See e.g. [START_REF] Nourdin | Normal Approximations Using Malliavin Calculus: from Stein's Method to Universality[END_REF][START_REF] Nourdin | Stein's method and stochastic analysis of Rademacher sequences[END_REF][START_REF] Nualart | The Malliavin calculus and related topics[END_REF][START_REF] Peccati | Wiener Chaos: Moments, Cumulants and Diagrams: A survey with Computer Implementation[END_REF][START_REF] Privault | Stochastic Analysis in Discrete and Continuous Settings: With Normal Martingales[END_REF], as well as the forthcoming Section 1.2, for an introduction to these concepts.

Our findings extend to the Poisson framework the results of [START_REF] Nourdin | Invariance principles for homogeneous sums: Universality of Gaussian Wiener chaos[END_REF], by Nourdin, Peccati and Reinert, where the authors discovered a remarkable universality property involving the normal approximation of homogeneous sums living inside a fixed Gaussian Wiener chaos. According to [START_REF] Nourdin | Invariance principles for homogeneous sums: Universality of Gaussian Wiener chaos[END_REF], the following universal phenomenon takes indeed place:

Let {F n } be a sequence of random variables such that each F n is a homogeneous sum of a fixed order ≥ 2 based on a sequence of i.i.d. standard Gaussian random variables, and assume that {F n } verifies a CLT. Then, the CLT continues to hold if one replaces the i.i.d. Gaussian sequence, inside the definition of each F n , with a generic collection of independent and identically distributed random variables with mean zero and unit variance. (See Theorem 1.6 below for a precise statement).

To describe this fact, one says that homogeneous sums inside the Gaussian Wiener chaos are universal with respect to normal approximations.

In this paper, we shall address the following natural question: are there other examples of homogeneous sums that enjoy the same universal property? As anticipated, our proof of the universal character of homogeneous sums inside the Poisson Wiener chaos will yield a positive answer. As discussed in Remark 3.5, and similarly to the Gaussian case, our conclusions do not extend to sums of order 1.

It is important to note that [START_REF] Nourdin | Invariance principles for homogeneous sums: Universality of Gaussian Wiener chaos[END_REF] also contains an elementary counterexample, implying that homogeneous sums based on Rademacher sequences are not universal. This argument is reproduced in the proof of Proposition 1.7 below.

The findings of the present work are a continuation of the theory developed in [START_REF] Peccati | Stein's method and normal approximation of Poisson functionals[END_REF][START_REF] Peccati | Multi-dimensional Gaussian fluctuations on the Poisson space[END_REF], respectively by Peccati, Solé, Taqqu and Utzet and by Peccati and Zheng, where the authors combined two probabilistic techniques, namely the Stein's method for probabilistic approximations and the Malliavin calculus of variations, in order to compute explicit bounds in (possibly multidimensional) CLTs involving functionals of a given Poisson field. One of our main findings, see Theorem 3.2 below, provides a substantial refinement these results, which is indeed an analogous for Poisson homogeneous sums of the 'fourth moment theorem' proved by Nualart and Peccati in [START_REF] Nualart | Central limit theorems for sequences of multiple stochastic integrals[END_REF]. One should note that the study of normal approximations on the Poisson space has recently gained much relevance, specifically in connection with stochastic geometry -see [START_REF] Decreusefond | Simplicial homology of random configurations[END_REF][START_REF] Ferraz | Statistics of geometric random simplicial complexes[END_REF][START_REF] Peccati | Fine Gaussian fluctuations on the Poisson space: cumulants contractions and random graphs[END_REF][START_REF] Reitzner | Central Limit Theorems for U-Statistics of Poisson Point Processes[END_REF][START_REF] Schulte | Exact and asymptotic results for intrinsic volumes of Poisson k-flat processes[END_REF].

Other relevant references are the paper by Mossel et al. [START_REF] Mossel | Noise stability of functions with low influences: variance and optimality[END_REF], containing an invariance principle on which [START_REF] Nourdin | Multivariate normal approximation using Stein's method and Malliavin calculus[END_REF] is based, and de Jong [START_REF] Jong | Central Limit Theorems for generalized multilinear forms[END_REF][START_REF] Jong | A central limit theorem for generalized multilinear forms[END_REF], where one can find remarkable CLTs for general degenerate U -statistics.

The subsequent Section 1.2 contains a formal introduction to the objects studied in this paper. From now on, we assume that every random element is defined on a common probability space (Ω, F, P).

Framework and motivation

The following three objects will play a crucial role in our discussion.

-G = {G i : i ≥ 1} indicates a collection of independent and identically distributed (i.i.d.)

Gaussian random variables such that G i ∼ N (0, 1);

-E = {e i : i ≥ 1} denotes a
Rademacher sequence, that is, the random variables e i are i.i.d. and such that P(e i = 1) = P(e i = -1) = 1 2 for every i ≥ 1; -P = {P i : i ≥ 1} stands for a collection of independent random variables such that

P i law = P (λ i ) -λ i √ λ i , i ≥ 1, (1.1)
where P (λ i ) indicates a Poisson random variable with parameter λ i ∈ (0, ∞).

We now formally introduce the notion of homogeneous sum.

Definition 1.1 (Homogeneous sums) Fix some integers 1 ≤ q ≤ N , and write [N ] for the set {1, 2, • • • , N }. Let X = {X i : i ≥ 1} be a collection of independent random variables, and let f : [N ] q → R be a symmetric function vanishing on diagonals (i.e.

f (i 1 , • • • , i q ) = 0 if ∃k = l : i k = i l ). The random variable Q q = Q q (N, f, X) = 1≤i 1 ,••• ,iq≤N f (i 1 , • • • , i q )X i 1 • • • X iq
is called the multilinear homogeneous sum, of order q, based on f and on the first N elements of X. Plainly, a homogeneous sum of order 1 is a finite sum of the type N i=1 f (i)X i .

Remark 1.2 If, for i = 1, 2, . . ., E[X i ] = 0 and E[X 2 i ] = 1 (as e.g. for X = G, E or P), then we deduce immediately that the mean and variance of Q q = Q q (N, f, X) are given by:

E[Q q ] = 0, E[Q 2 q ] = q! 1≤i 1 ,••• ,iq≤N f 2 (i 1 , • • • , i q ).
The next three examples show that homogeneous sums based on G, E and P can always be represented as 'chaotic random variables'. The reader is referred to [START_REF] Nourdin | Normal Approximations Using Malliavin Calculus: from Stein's Method to Universality[END_REF][START_REF] Nualart | The Malliavin calculus and related topics[END_REF] and [START_REF] Nourdin | Stein's method and stochastic analysis of Rademacher sequences[END_REF], respectively, for definitions and results concerning the Gaussian Wiener chaos and the Walsh chaos. An introduction to the Poisson Wiener chaos is provided in Section 2 below.

Example 1.3 (Homogeneous sums based on G) Let G = {G i : i ≥ 1} be defined as above. Without loss of generality, we can always assume that

G i = I G 1 (h i ) = G(h i )
, for some isonormal Gaussian process G = {G(h) : h ∈ H} based on a real separable Hilbert space H, where {h i : i ≥ 1} is an orthonormal system in H, and I G 1 denotes a Wiener-Itô integral of order 1 with respect to G. With this representation, one has that Q q (N, f, G) belongs to the so-called q-th Gaussian Wiener chaos of G. Indeed, we can write

Q q (N, f, G) = I G q (h),
where

h = N i 1 ,••• ,iq f (i 1 , • • • , i q )h i 1 ⊗ • • • ⊗ h iq , (1.2)
and the symbol ⊗ is a usual tensor product. It is a classic result that random variables of the type I G q (h), where h is as in (1.2), are dense in the qth Wiener chaos of G (see e.g. [15, Chapter 1]).

Example 1.4 (Homogeneous sums based on E) Fix q ≥ 1, let f : N q → R be a symmetric function vanishing on diagonals. We consider the Rademacher sequence E = {e i : i ≥ 1} defined above. Random variables with the form

J q = i 1 ,••• ,iq f (i 1 , • • • , i q )e i 1 • • • e iq ,
where the series converge in L 2 (P), compose the so-called qth Walsh chaos of E. (See [7, Chapter IV], or Remark 2.7 in [START_REF] Nourdin | Stein's method and stochastic analysis of Rademacher sequences[END_REF].) In particular, let f : [N ] q → R be a symmetric function vanishing on diagonals, then homogeneous sums of the type

Q q (N, f, E) = N i 1 ,••• ,iq f (i 1 , • • • , i q )e i 1 • • • e iq
are elements of q-th Walsh chaos of E. Recall that the Walsh chaos enjoys the following decomposition property: for every F ∈ L 2 (σ(E)) (that is, the set of square integrable functional of the sequence E), there exists a unique sequence of square-integrable symmetric functions vanishing on diagonals {f q : q ≥ 1}, such that

F = E[F ] + q≥1 q! i 1 <i 2 <...<iq f q (i 1 , . . . , i q )e i 1 • • • e iq ,
where the double series converges in L 2 .

Example 1.5 (Homogeneous sums based on P) Let P = {P i : i ≥ 1} be defined as above. Without loss of generality, we can always assume that, for every i ≥ 1,

P i = I 1 (g i ) = I η 1 (g i ),
where I 1 = I η 1 indicates a single Wiener-Itô integral with respect to a compensated Poisson measure η on some measurable space (Z, Z), with σ-finite and non-atomic control measure µ. Here, g = {g i : i ≥ 1} is a collection of functions in L 2 (Z, Z, µ) such that

g i = 1 A i / √ λ i
, where the {A i : i ≥ 1} are disjoint measurable sets such that µ(A i ) = λ i . For instance, one may take

Z = R + , µ = Lebesgue measure, g i = 1 (λ 1 +•••+λ i-1 ,λ 1 +•••+λ i ] for i ≥ 2, and g 1 = 1 [0,λ 1 ]
. It follows that the homogeneous sum Q q (N, f, P) belongs to q-th Poisson Wiener chaos of η, since Q q (N, f, P) = I q (g) = I η q (g), where

g = N i 1 ,••• ,iq f (i 1 , • • • , i q )g i 1 ⊗ • • • ⊗ g iq . (1.3)
and I q = I η q indicates a multiple Wiener-Itô of order q with respect to η. It is well-known that random variables of the type I q (g), where g is as in (1.3), are dense in the qth Wiener chaos of η (see e.g. [START_REF] Peccati | Wiener Chaos: Moments, Cumulants and Diagrams: A survey with Computer Implementation[END_REF]Chapter 5]), Concerning the 'universal nature' of homogeneous sum based on G, the following result was proved in [START_REF] Nourdin | Invariance principles for homogeneous sums: Universality of Gaussian Wiener chaos[END_REF] (see also [START_REF] Nourdin | Normal Approximations Using Malliavin Calculus: from Stein's Method to Universality[END_REF]Chapter 11]).

Theorem 1.6 (Theorem 1.10 in [START_REF] Nourdin | Invariance principles for homogeneous sums: Universality of Gaussian Wiener chaos[END_REF]) Homogeneous sums based on G are universal with respect to normal approximations, in the following sense: fix q ≥ 2, let {N (n) : n ≥ 1} be a sequence of integers going to infinity, and let {f (n) : n ≥ 1} be a sequence of mappings, such that each function f (n) : [N (n) ] q → R is symmetric and vanishes on diagonals. Assume that

E[Q q (N (n) , f (n) , G) 2 ] → 1 as n → ∞.
Then, the following four properties are equivalent as n → ∞.

(1) The sequence

{Q q (N (n) , f (n) , G) : n ≥ 1} converges in distribution to Y ∼ N (0, 1); (2) E[Q q (N (n) , f (n) , G) 4 ] → 3;
(3) for every sequence X = {X i : i ≥ 1} of independent centered random variables with unit variance and such that

sup i E|X i | 2+ǫ < ∞, the sequence {Q q (N (n) , f (n) , X) : n ≥ 1} converge in distribution to Y ∼ N (0, 1);
(4) for every sequence X = {X i : i ≥ 1} of independent and identically distributed centered random variables with unit variance, the sequence

{Q q (N (n) , f (n) , X) : n ≥ 1} converge in distribution to Y ∼ N (0, 1).
For several applications of Theorem 1.6 in random matrix theory, see [START_REF] Nourdin | Universal Gaussian fluctuations of non-Hermitian matrix ensembles: from weak convergence to almost sure CLTs[END_REF]. The following negative result concerns homogeneous sums based on E. Proposition 1.7 Homogeneous sums inside the Walsh chaos are not universal with respect to normal approximations.

Proof. To show this assertion, we present the counterexample described in [13, p. 1956]. Let G and E be defined as above. Fix q ≥ 2. For each N ≥ q, we set

f N (i 1 , i 2 , . . . , i q ) = 1/(q! √ N -q + 1), if {i 1 , i 2 , . . . , i q } = {1, 2, . . . , q -1, s} for q ≤ s ≤ N ; 0, otherwise.
The homogeneous sum thus defined is

Q q (N, f N , E) = e 1 e 2 • • • e q-1 N i=q e i √ N -q + 1 , with E[Q q (N, f N , E)] = 0 and Var[Q q (N, f N , E)] = 1. Since e 1 e 2 • • • e q-1 is a random sign independent of {e i : i ≥ q}, we have that Q q (N, f N , E) law -→ N (0, 1), as N → ∞, by virtue of the usual CLT. However, for every N ≥ 2, one has that Q q (N, f N , G) law = G 1 G 2 • • • G q . Since G 1 G 2 • • • G q is not Gaussian for every q ≥ 2, we deduce that Q q (N, f N , G) does not converge in distribution to a normal random variable.
The principal aim of this paper is to provide a positive answer to the following question.

Problem 1 Are homogeneous sums based on P universal with respect to normal approximations? In other words: can we replace G with P inside the statement of Theorem 1.6?

We will see in Section 3 that the answer is positive both in the one-dimensional and multidimensional cases. Our techniques are based on the tools developed in [START_REF] Peccati | Stein's method and normal approximation of Poisson functionals[END_REF][START_REF] Peccati | Multi-dimensional Gaussian fluctuations on the Poisson space[END_REF], that are in turn recent developments of the so-called 'Malliavin-Stein method'-given by the combination of Stein's method and Malliavin calculus.

As a by-product of our achievements, we will also prove some new CLTs on the Poisson Wiener chaos. Indeed, in the forthcoming Theorem 3.2 and Theorem 3.8, we shall show that, in the special case of elements of the Poisson Wiener chaos that are also homogeneous sums, the sufficient conditions for normal approximations established in [START_REF] Peccati | Stein's method and normal approximation of Poisson functionals[END_REF][START_REF] Peccati | Multi-dimensional Gaussian fluctuations on the Poisson space[END_REF] turn out to be also necessary. As anticipated, this yields some new examples of 'fourth moment theorems' -such as the ones proved by Nualart and Peccati in [START_REF] Nualart | Central limit theorems for sequences of multiple stochastic integrals[END_REF] (see also Chapter 5 in [START_REF] Nourdin | Normal Approximations Using Malliavin Calculus: from Stein's Method to Universality[END_REF]). Other 'fourth moment theorems' in a Poisson setting can be found in [START_REF] Peccati | Fine Gaussian fluctuations on the Poisson space: cumulants contractions and random graphs[END_REF].

The paper is organized as follows. In Section 2, we discuss some preliminaries, including multiple Wiener-Itô integrals on the Poisson space, product formulae and star contractions. In Section 3 we present the main results, in both the one-dimensional and multi-dimensional cases, and demonstrate the universal nature of homogeneous sums inside the Poisson Wiener chaos. Section 4 is devoted to an important technical proposition as well as to the proofs of our main results.

2 Some preliminaries

Poisson measures and integrals

Let (Z, Z, µ) be a measure space such that Z is a Borel space and µ is a σ-finite nonatomic Borel measure. We set Z µ = {B ∈ Z : µ(B) < ∞}. In what follows, we write η = {η(B) : B ∈ Z µ } to indicate a compensated Poisson measure on (Z, Z) with control µ. In other words, η is a collection of random variables defined on some probability space (Ω, F, P), indexed by the elements of Z µ and such that: (i) for every B, C ∈ Z µ such that B ∩C = ∅, the random variables η(B) and η(C) are independent; (ii) for every B ∈ Z µ , η(B) law = η(B)-µ(B), where η(B) is a Poisson random variable with paremeter µ(B). A random measure verifying property (i) is customarily called 'completely random' or, equivalently, 'independently scattered' (see e.g. the monograph [START_REF] Peccati | Wiener Chaos: Moments, Cumulants and Diagrams: A survey with Computer Implementation[END_REF] for a detailed discussion of these concepts).

In order to simplify the forthcoming discussion, we shall make use of the following conventions:

-We shall write interchangeably

1≤i 1 ,••• ,iq≤N and N i 1 ,••• ,iq . -For every k ≥ 1 and f ∈ L k (Z q , Z q , µ q ) := L k (µ q ), we write f L k to indicate the norm f L k (µ q ) .
-For every q ≥ 2, the class L k s (µ q ) as defined is the subspace of L k (µ q ) of functions that are µ q -almost everywhere symmetric; also, one customarily writes

L k s (µ 1 ) = L k (µ 1 ) = L k s (µ) = L k (µ).
-For any positive integer N , [N ] stands for the set {1, 2,

• • • , N }.
-For any two functions f, g ∈ L 2 (µ), f ⊗ g is the tensor product of f and g, that is,

f ⊗ g(x, y) = f (x)g(y). Iterated tensor products of the type f 1 ⊗ f 2 ⊗ • • • ⊗ f q (x 1 , . . . , x q )
are defined by recursion.

Definition 2.1 For every deterministic function h ∈ L 2 (µ), we write

I 1 (h) = η(h) = Z h(z)η(dz)
to indicate the Wiener-Itô integral of h with respect to η. For every q ≥ 2 and every f ∈ L 2 s (µ q ), we denote by I q (f ) the multiple Wiener-Itô integral, of order q, of f with respect to η. We also set I q (f ) = I q ( f ), for every f ∈ L 2 (µ q ), and I 0 (C) = C for every constant C. Here, f is the symmetrization of the function f . For every q ≥ 1, the collection of all random variables of the type I q (f ), f ∈ L 2 s (µ q ), is denoted by C q and is called the qth Wiener chaos of η.

We recall the following chaotic decomposition of L 2 (σ(η)) (that is, the space of all squareintegrable functionals of η):

L 2 (σ(η)) = R ⊕ ∞ q=1 C q ,
where the symbol ⊕ denotes a direct sum in L 2 (P). The reader is referred e.g. to Peccati and Taqqu [START_REF] Peccati | Wiener Chaos: Moments, Cumulants and Diagrams: A survey with Computer Implementation[END_REF], Privault [START_REF] Privault | Stochastic Analysis in Discrete and Continuous Settings: With Normal Martingales[END_REF] or Nualart and Vives [START_REF] Nualart | Anticipative calculus for the Poisson process based on the Fock space[END_REF] for a complete discussion of multiple Wiener-Itô integrals and their properties. The following proposition contains two fundamental properties that we will use in sequel.

Proposition 2.2

The following equalities hold for every q, m ≥ 1, every f ∈ L 2 s (µ q ) and every g ∈ L 2

s (µ m ):

1. E[I q (f )] = 0, 2. E[I q (f )I m (g)] = q! f, g L 2 (µ q ) 1 (q=m) (isometric property).
Remark 2.3 For every q ≥ 1 and every f ∈ L 2 s (µ q ), we shall also denote by I G q (f ) the multiple Wiener-Itô integral, of order q, of f with respect to an isonormal process G over the Hilbert space H = L 2 (Z, Z, µ). A detailed introduction to these objects can be found in [START_REF] Nourdin | Normal Approximations Using Malliavin Calculus: from Stein's Method to Universality[END_REF][START_REF] Nualart | The Malliavin calculus and related topics[END_REF][START_REF] Peccati | Wiener Chaos: Moments, Cumulants and Diagrams: A survey with Computer Implementation[END_REF].

Product formulae

In order to give a simple description of the Product formulae for multiple Poisson integrals (see formula (2.6)), we (formally) define a contraction kernel f ⋆ l r g on Z p+q-r-l for functions f ∈ L 2 s (µ p ) and g ∈ L 2 s (µ q ), where p, q ≥ 1, r = 1, . . . , p ∧ q and l = 1, . . . , r, as follows:

f ⋆ l r g(γ 1 , . . . , γ r-l , t 1 , , . . . , t p-r , s 1 , , . . . , s q-r ) (2.4)

= Z l µ l (dz 1 , . . . , dz l )f (z 1 , , . . . , z l , γ 1 , . . . , γ r-l , t 1 , . . . , t p-r )
×g(z 1 , , . . . , z l , γ 1 , . . . , γ r-l , s 1 , . . . , s q-r ).

In other words, the star operator ' ⋆ l r ' reduces the number of variables in the tensor product of f and g from p + q to p + qrl: this operation is realized by first identifying r variables in f and g, and then by integrating out l among them. We also use the notation

f ⊗ r f = f ⋆ r
r g(t 1 , , . . . , t p-r , s 1 , , . . . , s q-r ) (2.5)

= Z r
µ l (dz 1 , . . . , dz r )f (t 1 , . . . , t p-r , z 1 , . . . , z r ) × g(s 1 , . . . , s q-r , z 1 , . . . , z r ).

The operator f ⊗ r f and its symmetrization f ⊗r f play a fundamental role in the derivation of limit theorems inside the Gaussian Wiener-Itô chaos, see e.g. [START_REF] Nourdin | Normal Approximations Using Malliavin Calculus: from Stein's Method to Universality[END_REF][START_REF] Nualart | Central limit theorems for sequences of multiple stochastic integrals[END_REF].

We present here an important product formula for Poisson multiple integrals (see e.g. [START_REF] Kabanov | On extended stochastic integrals[END_REF][START_REF] Peccati | Wiener Chaos: Moments, Cumulants and Diagrams: A survey with Computer Implementation[END_REF][START_REF] Surgailis | On multiple Poisson stochastic integrals and associated Markov semigroups[END_REF] for a proof).

Proposition 2.4 (Product formula) Let f ∈ L 2
s (µ p ) and g ∈ L 2 s (µ q ), p, q ≥ 1, and suppose moreover that f ⋆ l r g ∈ L 2 (µ p+q-r-l ) for every r = 1, . . . , p ∧ q and l = 1, . . . , r such that l = r. Then,

I p (f )I q (g) = p∧q r=0 r! p r q r r l=0 r l I p+q-r-l f ⋆ l r g , (2.6)
with the tilde ∼ indicating a symmetrization, that is,

f ⋆ l r g(x 1 , . . . , x p+q-r-l ) = 1 (p + q -r -l)! σ f ⋆ l r g(x σ(1) , . . . , x σ(p+q-r-l) ),
where σ runs over all (p + qrl)! permutations of the set {1, . . . , p + qr -l}.

Fix integers p, q ≥ 0 and |q -p| ≤ k ≤ p + q, consider two kernels f ∈ L 2 s (µ p ) and g ∈ L 2

s (µ q ), and recall the multiplication formula (2.6). We will now introduce an operator G p,q k , transforming the function f , of p variables, and the function g, of q variables, into a function G p,q k (f, g), of k variables. More precisely, for p, q, k as above, we define the function (z 1 , . . . , z k ) → G p,q k (f, g)(z 1 , . . . , z k ), from Z k into R, as follows:

G p,q k (f, g)(z 1 , . . . , z k ) = p∧q r=0 r l=0 1 (p+q-r-l=k) r! p r q r r l f ⋆ l r g(z 1 , . . . , z k ), (2.7)
where the tilde ∼ means symmetrization, and the star contractions are defined in formula (2.4) and the subsequent discussion. Observe the following three special cases: (i) when p = q = k = 0, then f and g are both real constants, and G 0,0 0 (f, g) = f × g, (ii) when p = q ≥ 1 and k = 0, then G p,p 0 (f, g) = p! f, g L 2 (µ p ) , (iii) when p = k = 0 and q > 0 (then, f is a constant), G 0,p 0 (f, g)(z 1 , . . . , z q ) = f × g(z 1 , . . . , z q ). By using this notation, (2.6) becomes

I p (f )I q (g) = p+q k=|q-p| I k (G p,q k (f, g)).
(2.8)

The advantage of representation (2.8) (as opposed to (2.6)) is that the RHS of (2.8) is an orthogonal sum, a feature that will simplify the computations to follow.

3 Main results

One-dimensional case: fourth moments and universality

We recall the following theorem, first proved in [START_REF] Nualart | Central limit theorems for sequences of multiple stochastic integrals[END_REF], stating that the convergence in law of a sequence of Gaussian Wiener integrals towards a normal distribution can be characterized by their variances and fourth moments. See [10, Chapter 5] for a detailed discussion, as well as examples and bibliographic remarks.

Theorem 3.1 (See [START_REF] Nualart | Central limit theorems for sequences of multiple stochastic integrals[END_REF][START_REF] Nualart | Central limit theorems for sequences of multiple stochastic integrals[END_REF]) Fix q ≥ 2, let h (n) ∈ L 2 s (µ q ), n ≥ 1, and let

Z (n) = I G q (h (n) ), n ≥ 1,
be a sequence of random variables having the form of a multiple Wiener-Itô integral of order q, of h (n) with respect to an isonormal Gaussian process G over the Hilbert space H = L 2 (µ). Assume that lim n→∞ Var(Z (n) ) = lim n→∞ E Z (n) 2 = 1. Then, the following three assertions are equivalent as n → ∞:

(1)

Z (n) law -→ Y ∼ N (0, 1); (2) E Z (n) 4 → E[Y 4 ] = 3 ;
(3) ∀r = 1, . . . , q -1, h (n) ⊗ r h (n) L 2 → 0, where the contraction ⊗ r = ⋆ r r is defined according to (2.5).

Extending Theorem 3.1 to multiple integrals with respect to a Poisson measure is a demanding task, since the product formula (2.6) (which is more involved than in the Gaussian case) quickly leads to some inextricable expressions for moments of order four. A partial 'fourth moment theorem' can be found in [START_REF] Peccati | Central limit theorems for double Poisson integrals[END_REF]Theorem 2], in the special case of double Poisson integrals. We now present an exact analogous of Theorem 3.1 for homogeneous sums inside a fixed Poisson Wiener chaos. Its proof, together with the one of the subsequent Theorem 3.4, is deferred to Section 4. Theorem 3.2 (Fourth moment theorem for Poisson sums) Let {λ i : i ≥ 1} be a collection of positive real numbers, and assume that inf

i≥1 λ i = α > 0. Let P = {P i : i ≥ 1}
be a collection of independent random variables verifying (1.1). Fix an integer q ≥ 1. Let {N (n) , f (n) : n ≥ 1} be a double sequence such that {N (n) : n ≥ 1} is a sequence of integers diverging to infinity, and each f (n) : [N (n) ] q → R is symmetric and vanishes on diagonals. We set

F (n) = Q q (N (n) , f (n) , P) = N (n) i 1 ,••• ,iq f (n) (i 1 , • • • , i q )P i 1 • • • P iq = I q (g (n) ),
where

g (n) = N (n) i 1 ,••• ,iq f (n) (i 1 , • • • , i q )g i 1 ⊗ • • • ⊗ g iq , n ≥ 1,
and the representation of F (n) as a multiple Wiener-Itô integral is the same as in Example 1.5.

Suppose that E F (n) 2 → σ 2 ∈ (0, ∞). Then, the following two statements are equivalent, as n → ∞:

(1) F (n) law -→ Y ∼ N (0, σ 2 ); (2) E F (n) 4 → E[Y 4 ] = 3σ 4 .
When q = 1, either one of conditions (1)-( 2) is equivalent to (3a)

N (n) i=1 f (n) (i) 4 1 λ i → 0.
Finally, when q ≥ 2, either one of conditions (1)-( 2) is equivalent to either one of the following two equivalent conditions (3b)-(3b')

(3b) Z q g (n) 4 → 0 and ∀r = 1, • • • , q, ∀l = 1, • • • , r ∧ (q -1), g (n) ⋆ l r g (n)
L 2 → 0, where the star contractions ⋆ l r are defined according to (2.4); The next statement, that will be proved by means of Theorem 3.2, establishes the universal nature of Poisson homogeneous sums of order q ≥ 2. Theorem 3.4 (Universality of the Poisson Wiener chaos) Let the sequence P verify the same assumptions as in Theorem 3.2. Fix q ≥ 2, let {N (n) : n ≥ 1} be a sequence of integers going to infinity, and let {f (n) : n ≥ 1} be a sequence of mappings, such that each function f (n) : [N (n) ] q → R is symmetric and vanishes on diagonals. Assume that E[Q q (N (n) , f (n) , P) 2 ] → 1 as n → ∞. Then, the following four properties are equivalent, as n → ∞.

(3b') ∀r = 1, • • • , q -1, g (n) ⋆ r r g (n) L 2 = g (n) ⊗ r g (n) L 2 → 0.
(1) The sequence {Q q (N (n) , f (n) , P) : n ≥ 1} converges in distribution to Y ∼ N (0, 1);

(2) E[Q q (N (n) , f (n) , P) 4 ] → 3;
(3) for every sequence X = {X i : i ≥ 1} of independent centered random variables with unit variance and such that

sup i E|X i | 2+ǫ < ∞, the sequence {Q q (N (n) , f (n) , X) : n ≥ 1} converge in distribution to Y ∼ N (0, 1);
(4) for every sequence X = {X i : i ≥ 1} of independent and identically distributed centered random variables with unit variance, the sequence {Q q (N (n) , f (n) , X) : n ≥ 1} converge in distribution to Y ∼ N (0, 1).

Remark 3.5 Theorem 3.4 is false in general for q = 1, as one can see by considering the case N (n) = n, λ i = i, and f n such that f n (n) = 1 and f n (i) = 0 for i = n. On the other hand, one can prove an equivalent of Theorem 3.4 for q = 1, by assuming in addition that sup i λ i < ∞ and by applying the standard Lindberg's CLT (see e.g. [4, Theorem 9.6.1]). The details are left to the reader.

We conclude this section with a result implying that the Wasserstein distance metrizes the convergence to Gaussian for any sequence of homogeneous sums based on a Poisson field. Recall that, given random variables X, Y ∈ L 1 (P), the Wasserstein distance between the law of X and the law of Y is defined as the quantity

d W (X, Y ) = sup f ∈Lip(1) E[f (X)] -E[f (Y )] ,
where Lip(1) indicates the class of Lipschitz real-valued function with Lipschitz constant ≤ 1. It is well-known that the topology induced by d W , on the class of probability measures on the real line, is strictly stronger than the one induced by the convergence in distribution.

Proposition 3.6 Let the sequence of homogeneous sums {F

(n) : n ≥ 1} satisfy the assump- tions of Theorem 3.2. If F (n) converges in distribution to Y ∼ N (0, 1), as n → ∞, then necessarily d W (F (n) , Y ) → 0.
Proof. Using Corollary 3.4 (for the case q = 1) and Theorem 4.1 (for the case q ≥ 2) in [START_REF] Peccati | Stein's method and normal approximation of Poisson functionals[END_REF], we see that, if conditions (3a)-(3b) are verified, then d W (F (n) , Y ) → 0, so that the conclusion follows from Theorem 3.2.

Multi-dimensional case

We now present some multidimensional extensions of the results presented in the previous section: the proofs are similar to those of the results in the previous section, and are mostly left to the reader. Our starting point is the following multi-dimensional extension of Theorem 3.1, first proved by Peccati and Tudor in [START_REF] Peccati | Gaussian limits for vector-valued multiple stochastic integrals[END_REF]. For details and generalizations, see [START_REF] Nourdin | Multivariate normal approximation using Stein's method and Malliavin calculus[END_REF][START_REF] Nualart | Central limit theorems for sequences of multiple stochastic integrals[END_REF]. Theorem 3.7 Let G be an isonormal Gaussian process over the Hilbert space H = L 2 (µ). Fix d ≥ 2 and let C = {C(i, j) : i, j = 1, . . . , d} be a d × d positive definite matrix. Fix integers

1 ≤ q 1 ≤ • • • ≤ q d . For any n ≥ 1 and i = 1, . . . , d, let h (n) i belong to L 2
s (µ q i ). Assume that

F (n) = (F (n) 1 , . . . , F (n)
d ) := (I G q 1 (h (n) 1 ), . . . , I G q d (h (n) d )) n ≥ 1, is such that lim n→∞ E[F (n) i F (n) j ] = C(i, j), 1 ≤ i, j ≤ d.
Then, as n → ∞, the following four assertions are equivalent:

(1) The vector F (n) converges in distribution to a d-dimensional Gaussian vector N d (0, C);

(2) for every

1 ≤ i ≤ d, E (F (n) i ) 4 → 3C(i, i) 2 ;
(3) for every 1 ≤ i ≤ d and every

1 ≤ r ≤ q i -1 , h (n) i ⊗ r h (n) i L 2 → 0; (4) for every 1 ≤ i ≤ d, F (n) i
converges in distribution to a centered Gaussian random variable with variance C(i, i).

Combining the previous Theorem 3.2 with [24, Theorem 5.8] we deduce the following analogue of Theorem 3.7 for homogeneous sums inside the Poisson Wiener chaos. Theorem 3.8 Let {λ i : i ≥ 1} be a collection of positive real numbers, and assume that inf i λ i = α > 0. Let P = {P i : i ≥ 1} be a collection of independent random variables such that ∀i, P i verifies relation (1.1). Fix integers d ≥ 1 and

q d ≥ • • • ≥ q 1 ≥ 1. Let {N (n) j , f (n) j : j = 1, • • • , d; n ≥ 1} be such that for every fixed j, {N (n) j
: n ≥ 1} is a sequence of integers going to infinity, and each f

(n) j : [N (n) j ] q j →
R is symmetric and vanishes on diagonals. We consider a sequence of random vectors

F (n) = (F (n) 1 , • • • , F (n) d ), n ≥ 1, where for every 1 ≤ j ≤ d, F (n) j = Q q j (N (n) j , f (n) j , P) = N (n) j i 1 ,••• ,iq j f (n) j (i 1 , • • • , i q j )P i 1 • • • P iq j = I q j (g (n) j ) with g (n) j = N (n) j i 1 ,••• ,iq j f (n) j (i 1 , • • • , i q j )g i 1 ⊗ • • • ⊗ g iq j ,
and the representation of F (n) j as a multiple integral is the same as in Example 1.5. Given

a d × d positive definite matrix C = C(i, j) i,j=1,...,d , suppose that lim n→∞ E[F (n) i F (n) j ] → C(i, j
), for every i, j = 1, . . . , d. Then, the following four statements are equivalent, as n → ∞:

(1) F (n) law -→ (Y 1 , . . . , Y d ) ∼ N d (0, C), where N d (0, C) indicates a d-dimensional Gaussian distribution with covariance matrix C; (2) for each j = 1, • • • , d, E[(F (n) j ) 4 ] → 3C(j, j) 2 ; (3) for each j = 1, • • • , d such that q j ≥ 2, ∀r = 1, • • • , q j -1, g (n) j ⋆ r r g (n) j L 2 = g (n) j ⊗ r g (n) j L 2 → 0,
and, for every j such that q j = 1,

N (n) i=1 f (n) j (i) 4 1 λ i → 0; (4) for each j = 1, • • • , d, F (n) j law -→ N (0, C(j, j)).
Finally, we present a multi-dimensional analogous of the universality statement contained in Theorem 3.4: it is deduced by combining Theorems 3.7 and 3.8 above with [13, Theorem 7.1] Theorem 3.9 (Multi-dimensional Universality) Let the assumptions and notations of Theorem 3.8 prevail. Then, the following two assertions are equivalent as n → ∞:

(1) The sequence {F (n) : n ≥ 1} converges in distribution to (Y 1 , . . . , Y d ) ∼ N d (0, 1);

(2) for every sequence X = {X i : i ≥ 1} of independent centered random variables with unit variance and such that sup i E|X i | 3 < ∞, the sequence of d-dimensional vectors 4 Proofs

{Q q (N (n) j , f (n)

A technical result

The following technical statement is the key to our main results.

Proposition 4.1 Let the notation and assumptions of Theorem 3.2 prevail, and fix q ≥ 2. If ∀p = 1, 2, . . . , q -1, one has lim n→∞ g (n) ⋆ p p g (n) L 2 = 0, then, as n → ∞:

(a) Z q g (n) 4 → 0 ; (b) ∀r = 1, • • • , q, ∀l = 1, • • • , r ∧ (q -1), g (n) ⋆ l r g (n) L 2 → 0.
Proof. In the following proof, we shall write

i 1 ,••• ,ip to indicate N (n) i 1 ,••• ,ip . For p = 1, 2, . . . , q -1, g (n) ⋆ p p g (n) = i 1 ,••• ,iq j 1 ,••• ,jq f (n) (i 1 , • • • , i q )f (n) (j 1 , • • • , j q ) ×(g i 1 ⊗ • • • ⊗ g iq ) ⋆ p p (g j 1 ⊗ • • • ⊗ g jq ) = a 1 ,••• ,ap i 1 ,••• ,i q-p j 1 ,••• ,j q-p p l=1 g a l 2 L 2 × f (n) (a 1 , • • , a p , i 1 , • • • , i q-p ) ×f (n) (a 1 , • • • , a p , j 1 , • • • , j q-p ) g i 1 ⊗ • • • ⊗ g i q-p ⊗ g j 1 ⊗ • • • ⊗ g j q-p = k 1 ,••• ,k 2q-2p a 1 ,••• ,ap f (n) (a 1 , • • • , a p , k 1 , • • • , k q-p )f (n) (a 1 , • • • , a p , k q-p+1 , • • • , k 2q-2p ) × p l=1 g a l 2 L 2 × g k 1 ⊗ • • • ⊗ g k 2q-2p = k 1 ,••• ,k 2q-2p a 1 ,••• ,ap f (n) (a 1 , • • • , a p , k 1 , • • • , k q-p )f (n) (a 1 , • • • , a p , k q-p+1 , • • • , k 2q-2p ) ×g k 1 ⊗ • • • ⊗ g k 2q-2p ,
from which we deduce that

g (n) ⋆ p p g (n) 2 L 2 = k 1 ,••• ,k 2q-2p a 1 ,••• ,ap f (n) (a 1 , • • • , a p , k 1 , • • • , k q-p ) ×f (n) (a 1 , • • • , a p , k q-p+1 , • • • , k 2q-2p ) 2 .
(4.9)

We first prove (a). Using the definition of the functions {g i : i ≥ 1},

g (n) 4 = i 1 ,••• ,iq j 1 ,••• ,jq k 1 ,••• ,kq s 1 ,••• ,sq f (n) (i 1 , • • • , i q )f (n) (j 1 , • • • , j q )f (n) (k 1 , • • • , k q )f (n) (s 1 , • • • , s q ) ×(g i 1 ⊗ • • • ⊗ g iq ) × (g j 1 ⊗ • • • ⊗ g jq ) × (g k 1 ⊗ • • • ⊗ g kq ) × (g s 1 ⊗ • • • ⊗ g sq ) = i 1 ,••• ,iq f (n) 4 (i 1 , • • • , i q ) g i 1 ⊗ • • • ⊗ g iq × q l=1 1 λ 3/2 i l , yielding g (n) 4 dµ q = i 1 ,••• ,iq f (n) 4 (i 1 , • • • , i q ) q l=1 1 λ i l ≤ 1 α q i 1 ,••• ,iq f (n) 4 (i 1 , • • • , i q ).
Now, specializing formula (4.9) to the case p = q -1, we deduce

g (n) ⋆ q-1 q-1 g (n) 2 L 2 = k 1 ,k 2 a 1 ,••• ,a q-1 f (n) (a 1 , • • • , a q-1 , k 1 ) ×f (n) (a 1 , • • • , a q-1 , k 2 ) 2 ≥ k a 1 ,••• ,a q-1 f (n) 2 (a 1 , • • • , a q-1 , k) 2 = a 1 ,••• ,a q-1 b 1 ,••• ,b q-1 k f (n) 2 (a 1 , • • • , a q-1 , k) f (n) 2 (b 1 , • • • , b q-1 , k) ≥ a 1 ,••• ,a q-1 f 4 (a 1 , • • • , a q ) ≥ g (n) 4 dµ q × α q ,
which proves (a), since α = inf i λ i > 0 by assumption.

The proof of (b) consists of two steps.

(b1) Let r = q. For any l ∈ {1, • • • , q -1}, we have,

g (n) ⋆ l q g (n) = i 1 ,••• ,iq j 1 ,••• ,jq f (n) (i 1 , • • • , i q )f (n) (j 1 , • • • , j q )[g i 1 ⊗ • • • ⊗ g iq ] ⋆ l r [g j 1 ⊗ • • • ⊗ g jq ] = a 1 ,••• ,a l b 1 ,••• ,b q-l g b 1 ⊗ • • • ⊗ g b q-l × f 2 (a 1 , • • • , a l , b 1 , • • • , b q-l ) q-l t=1 λ -1/2 bt = b 1 ,••• ,b q-l g b 1 ⊗ • • • ⊗ g b q-l q-l t=1 λ -1/2 bt a 1 ,••• ,a l f 2 (a 1 , • • • , a l , b 1 , • • • , b q-l ) .
These equalities lead to the estimate

g (n) ⋆ l q g (n) 2 L 2 = b 1 ,••• ,b q-l q-l t=1 λ -1 bt a 1 ,••• ,a l f 2 (a 1 , • • • , a l , b 1 , • • • , b q-l ) 2 ≤ 1 α q-l g (n) ⋆ l l g (n) 2 L 2 , yielding (since α > 0) that g (n) ⋆ l l g (n) L 2 → 0 implies g (n) ⋆ l q g (n) L 2 → 0.
(b2) For any r = 1, • • • , q -1, and l = 1, • • • , r, we see that

g (n) ⋆ l r g (n) = a 1 ,••• ,a l   b 1 ,••• ,b r-l r-l u=1 λ -1/2 bu g b 1 ⊗ • • • ⊗ g b r-l   i 1 ,••• ,i q-r j 1 ,••• ,j q-r g i 1 ⊗ • • • ⊗ g i q-r ⊗ g j 1 ⊗ • • • ⊗ g j q-r ×f (a 1 , • • • , a l , b 1 , • • • , b r-l , i 1 , • • • , i q-r )f (a , • • • , a l , b 1 , • • • , b r-l , j 1 , • • • , j q-r ) = b 1 ,••• ,b r-l i 1 ,••• ,i q-r j 1 ,••• ,j q-r r-l u=1 λ -1/2 bu g b 1 ⊗ • • • ⊗ g b r-l ⊗ g i 1 ⊗ • • • ⊗ g i q-r ⊗ g j 1 ⊗ • • • ⊗ g j q-r × a 1 ,••• ,a l f (a 1 , • • • , a l , b 1 , • • • , b r-l , i 1 , • • • , i q-r )f (a 1 , • • • , a l , b 1 , • • • , b r-l , j 1 , • • • , j q-r ).
Consequently,

g (n) ⋆ l r g (n) 2 L 2 = b 1 ,••• ,b r-l i 1 ,••• ,i q-r j 1 ,••• ,j q-r r-l u=1 λ -1 bu × a 1 ,••• ,a l f (a 1 , • • • , a l , b 1 , • • • , b r-l , i 1 , • • • , i q-r )f (a 1 , • • • , a l , b 1 , • • • , b r-l , j 1 , • • • , j q-r ) 2 ≤ 1 α r-l g (n) ⋆ l l g (n) 2 L 2 .
Since α > 0, this relation yields the desired implication: if g

(n) ⋆ l l g (n) L 2 → 0, then g (n) ⋆ l r g (n) L 2 → 0.

Proofs of the main results

Proof of Theorem 3.2.

We shall first prove the implication (1) ⇒ (2) for a general q ≥ 1. For every λ > 0, let P (λ) be a Poisson random variable with parameter λ. For every integer k ≥ 0, we introduce the mapping

λ → T k (λ) = E[(P (λ) -λ) k ], λ > 0,
so that, for instance, T 0 (λ) = 1 and T 1 (λ) = 0. It is well-known (see e.g. [START_REF] Peccati | Wiener Chaos: Moments, Cumulants and Diagrams: A survey with Computer Implementation[END_REF]Proposition 3.3.4]) that the following recursive relation takes place: for every k ≥ 1,

T k+1 (λ) = λ k-1 j=0 k j T j (λ).
Elementary considerations now yield that, for every k ≥ 1, the mapping T k (•) is a polynomial of degree (k -1)/2 if k is odd, and of degree k/2 is k is even. As a consequence, for every real q ≥ 1 the mapping

λ → E[|P (λ) -λ| q ]
λ q/2 is bounded on the set [α, ∞). Using (1.1) together with the assumption α = inf i λ i > 0, we infer that sup i≥1 E[|P i | q ] < ∞ for every q ≥ 1. Standard hypercontractivity estimates (see for instance [START_REF] Nourdin | Invariance principles for homogeneous sums: Universality of Gaussian Wiener chaos[END_REF]Lemma 4.2]) yield therefore that, since E[(F (n) ) 2 ] → σ 2 , then sup n≥1 E[|F (n) | q ] < ∞, for every q ≥ 1. As a consequence, if (1) is in order, then necessarily E[(

F (n) ) k ] → E[Y k ]
for every integer k ≥ 1; in particular, (2) is verified. Now assume that q = 1 and (2) is verified. A quick computation reveals that

E[(F (n) ) 4 ] -3E[(F (n) ) 2 ] 2 = g (n) 4 L 4 = N (n) i=1
f n (i) 4 1 λ i , thus yielding the implication (2) ⇒ (3a). On the other hand, if (3a) is verified, then one has that (by the Cauchy-Schwarz inequality)

g (n) 3 L 3 ≤ g (n) L 2 g (n) 1/2 L 4 → 0, as n → ∞,
so that the implication (3a) ⇒ (1) follows from [START_REF] Peccati | Stein's method and normal approximation of Poisson functionals[END_REF]Corollary 3.4], thus concluding the proof for q = 1.

We now fix q ≥ 2. The implication (3b) ⇒ (1) is a direct consequence of [START_REF] Peccati | Stein's method and normal approximation of Poisson functionals[END_REF]Theorem 5.1], whereas the equivalence between (3b) and (3b') follows from Proposition 4.1. In view of the first part of the proof, we need only to show that (2) ⇒ (3b'). We start by exploiting formula (2.8) in order to write the chaotic decomposition of I q (h (n) ), namely:

I q (g (n) ) 2 = 2q k=0
I k G q,q k (g (n) , g (n) ) .

As a consequence, by exploiting the orthogonality of multiple integrals with different orders,

E[I q (g (n) ) 4 ] = 2q k=0
k! G q,q k (g (n) , g (n) ) 2

L 2 = G q,q 0 (g (n) , g (n) ) 2 L 2 + (2q)! G q,q 2q (g (n) , g (n) ) 2 L 2 (4.10)

+ 2q-1 k=1 k! G q,q k (g (n) , g (n) ) 2 L 2 ,
where G q,q 0 (g (n) , g (n) ) 2 L 2 = q! 2 g (n) 4 L 2 , and (2q)! G q,q 2q (g (n) , g

(n) ) 2 L 2 = (2q)! g (n) ⋆ 0 0 g (n) 2 L 2 (4.11) = 2q! 2 g (n) 4 + q-1 p=1 (q!) 4 (p!(q -p)!) 2 g (n) ⋆ p p g (n) 2 L 2 ,
where we have used [22, formula (11.6.30)]. Since q! 2 g (n) 4 L 2 → σ 4 by assumption, we deduce that, if (2) is verified, then g (n) ⋆ p p g (n) L 2 → 0 for every p = 1, . . . , q -1, and the desired implication follows from Proposition 4.1.

Proof of Theorem 3.4. By virtue of Theorem 1.6, it suffices to show that, if condition (1) in Theorem 3.4 is in order, then the sequence {Q q (N (n) , f (n) , G) : n ≥ 1} converges in distribution to Y . Using the same notation as in Example 1.3, with H = L 2 (µ) and h i = g i , one has that the homogeneous sum Q q (N (n) , f (n) , G) can be represented as a multiple Wiener-Itô integral as follows:

Q q (N (n) , f (n) , G) = N (n) i 1 ,••• ,iq f (n) (i 1 , • • • , i q )G i 1 • • • G iq = I G q (h (n) ),
where

h (n) = g (n) = N (n) i 1 ,••• ,iq f (n) (i 1 , • • • , i q )g i 1 ⊗ • • • ⊗ g iq .
Now, if condition (1) in Theorem 3.4 holds, then for every r = 1, . . . , q-1, g (n) ⋆ r r g (n) L 2 → 0, and we immediately deduce the conclusion by combining Theorem 3.2 and Theorem 3.1.

Remark 3 . 3

 33 The assumption inf i≥1 λ i > 0 is necessary for proving the two implications: (1) ⇒ (2) and (3b') ⇒ (3b).

j

  , X) : j = 1, . . , d}, n ≥ 1, converges in distribution to (Y 1 , . . . Y d ).

Faculté des Sciences, de la Technologie et de la Communication; UR en Mathématiques, Université du Luxembourg . 6, rue Richard Coudenhove-Kalergi, L-1359 Luxembourg. Email: giovanni.peccati@gmail.com

[START_REF] Jong | Central Limit Theorems for generalized multilinear forms[END_REF] LAMA, Université Paris-Est Marne-la-Vallée, 5 Boulevard Descartes, 77454 Champs sur Marne, and LPMA, Université Paris VI, Paris, France. Email: zhengcb@gmail.com