Giuseppe Cattaneo
email: cattaneo@unisa.it

Gianluca Roscigno
email: giroscigno@unisa.it

Umberto Ferraro Petrillo

Experimental Evaluation of an Algorithm for the Detection of Tampered JPEG Images

Keywords: Digital Image Forensics, JPEG Image Integrity, Double Quantization Effect, Evaluation Datasets

. We developed a reference implementation for this algorithm and performed a deep experimental analysis, by measuring its performance when applied to the images of the CASIA TIDE public dataset, the de facto standard for the experimental analysis of this family of algorithms. Our first results were very positive, thus confirming the good performance of this algorithm. However, a closer inspection revealed the existence of an unexpected anomaly in a consistent part of the images of the CASIA TIDE dataset that may have influenced our results as well as the results of previous studies conducted using this dataset. By taking advantage of this anomaly, we were able to develop a variant of the original algorithm which exhibited better performance on the same dataset.

Introduction

Nowadays, the manipulation of digital images is simpler than ever thanks to solutions like sophisticated photo-editing software or photo-sharing social networks. Indeed, one of the key characteristics of digital images is their pliability to manipulation. As a consequence, we can no longer take the authenticity of digital photos for granted. This can be a serious problem in situations where the reliability of the images plays a crucial role, such as when conducting criminal investigations. This has led, in the recent years, to the development of the Digital Image Forensics, a discipline that is responsible for the acquisition and the analysis of images found on digital devices for investigation purposes (see, e.g., [START_REF] Lukáš | Digital Camera Identification from Sensor Pattern Noise[END_REF][START_REF] Khanna | Scanner Identification using Sensor Pattern Noise[END_REF][START_REF] Ye | Detecting Digital Image Forgeries by Measuring Inconsistencies of Blocking Artifact[END_REF][START_REF] Farid | Exposing Digital Forgeries from JPEG Ghosts[END_REF][START_REF] Cattaneo | Experiments on improving sensor pattern noise extraction for source camera identification[END_REF][START_REF] Castiglione | Experimentations with Source Camera Identification and Online Social Networks[END_REF]).

One of the problems faced by this discipline is to verify if a digital image is authentic or has been manipulated after the acquisition (image tampering). Several algorithms have been proposed in the scientific literature for solving this problem, such as [START_REF] Lin | Fast, Automatic and Fine-grained Tampered JPEG Image Detection via DCT Coefficient Analysis[END_REF], [START_REF] Ye | Detecting Digital Image Forgeries by Measuring Inconsistencies of Blocking Artifact[END_REF], [START_REF] Farid | Exposing Digital Forgeries from JPEG Ghosts[END_REF]. It is a common practice to accompany these contributions with an experimental analysis devoted to prove the viability of the proposed approach in the real practice. A popular dataset that is widely used for these experimentations is the CASIA TIDE dataset [START_REF]CASIA Tampered Image Detection Evaluation Database (CASIA TIDE)[END_REF]. In this paper, we focus our attention on a particular algorithm for the detection of tampered JPEG digital images: the algorithm by Lin et al. [START_REF] Lin | Fast, Automatic and Fine-grained Tampered JPEG Image Detection via DCT Coefficient Analysis[END_REF]. Despite its popularity, this algorithm has never been tested on the CASIA TIDE dataset. We decided to close this gap, by developing an implementation of this algorithm and testing it over several different variants of this dataset. The results are contrasting. On a side, they confirm the good performance of the Lin et al. algorithm. On the other side, we experimented an anomaly in a consistent number of images forming the CASIA TIDE dataset which is likely to partially influence the results of the experiments conducted using these images. By taking advantage of this anomaly, we were able to further improve the performance of the original algorithm.

Organization of the paper

In Section 2 we provide some details about the JPEG standard. In Section 3, we review some of the main contributions in the field of the JPEG image integrity. The aim of this work is illustrated in Section 4. Then, in Section 5, we focus on the Lin et al. algorithm. Section 6 describes the experiments we have conducted and their results. Finally, in Section 7 we draw some concluding remarks for our work.

The JPEG Standard

The JPEG [START_REF] Wallace | The JPEG Still Picture Compression Standard[END_REF] is a very popular standard for the encoding of digital images. It uses several techniques to guarantee very high compression rates at the expense of a small degradation in the image quality. The core of this standard is a lossy-compression technique based on the discrete cosine transform (DCT). In a few words, this technique assumes that an input image is encoded in the YCbCr format, where the Y channel holds the luminance component of the image, and the Cb and Cr chrominance channels hold, respectively, the blue minus luminance component of the image and the red minus luminance component of the image. The DCT operation works by logically splitting each image channel into blocks of 8 × 8 pixels and by converting them from the spatial domain into the frequency domain, producing blocks of 8 × 8 DCT coefficients, for a total of 64 frequencies. Once in the frequency domain, these coefficients are compressed by drastically reducing the amount of information provided by the high frequencies (i.e., quantization). This is done by dividing for a fixed constant (quantization step) each component of the 8×8 block of the DCT coefficient matrix and, then, by rounding the resulting values. The quantization steps can be chosen according to the amount of information to leave out from the frequencies, thus influencing the quality and the size of the compressed image (quality factor, QF). For different frequencies and channels, the quantization steps are saved in quantization matrices which can be extracted from the JPEG image. In general, there is a luminance quantization matrix for the luminance channel and a chroma quantization matrix for the two chrominance channels. At the end of this step, quantized coefficients are sequenced and losslessly compressed. The quality factor of a JPEG image (see [START_REF]Independent JPEG Group code library[END_REF]) can vary in the range [START_REF] Lin | Fast, Automatic and Fine-grained Tampered JPEG Image Detection via DCT Coefficient Analysis[END_REF]100], where smaller values result in a lower quality of the compressed image and a higher compression degree.

JPEG Image Integrity

The digital image integrity research field concerns with the problem of assessing if a digital image is the result of some forging operation. By this term, we mean all the techniques used to alter the contents of an authentic image, such as painting new objects in a portrayed scene or copying the region of an image over another image (splicing operation). Detecting the forgery of a JPEG image can be harder than for other formats because the compression steps employed by this encoding may delete the forgery traces left in a tampered image. However, an algorithm could also try to discover new traces caused by recompression of a tampered image and use these traces to detect the forgeries. In fact, the artifacts introduced by JPEG compression (so said JPEG blocking artifacts) can be seen as an inherent "watermark" for compressed images. These artifacts result to be modified when a JPEG image is altered by means of forging operations. Many image integrity algorithms follow this approach (see, e.g., [START_REF] Lin | Fast, Automatic and Fine-grained Tampered JPEG Image Detection via DCT Coefficient Analysis[END_REF], [START_REF] Ye | Detecting Digital Image Forgeries by Measuring Inconsistencies of Blocking Artifact[END_REF], [START_REF] Farid | Exposing Digital Forgeries from JPEG Ghosts[END_REF]). These algorithms use some of the statistical properties of the DCT coefficients to detect inconsistencies in the blocking artifacts of a target JPEG image. One of the first detection technique is described in [START_REF] Lukáš | Estimation of Primary Quantization Matrix in Double Compressed JPEG Images[END_REF]: it is a method that estimates the primary quantization matrix from a doubly compressed JPEG image using the histograms of the individual DCT coefficients. A similar approach has been proposed by Ye et al. in [START_REF] Ye | Detecting Digital Image Forgeries by Measuring Inconsistencies of Blocking Artifact[END_REF]. First, they used the histogram of the DCT coefficients to estimate the quantization step size and, then, they measured the inconsistency of quantization errors between different image regions for estimating local compression blocking artifacts measure. A major drawback of this algorithm is that it requires a preliminary human intervention to select a suspicious region of the image to analyze. Farid [START_REF] Farid | Exposing Digital Forgeries from JPEG Ghosts[END_REF] proposed a technique, based on the detection of JPEG ghosts, to establish whether a region of an image was originally compressed at quality factor different than others regions of the same image. The disadvantage of this technique is that it only works when the tampered region has a lower quality than the surrounding image. Lin et al. presented in [START_REF] Lin | Fast, Automatic and Fine-grained Tampered JPEG Image Detection via DCT Coefficient Analysis[END_REF] a method for detecting and locating doubly compressed blocks in a JPEG image. This is done by examining the double quantization (DQ) effect contained in the DCT coefficients, and computing the Block Posterior Probability Map (BPPM) using a Bayesian approach.

The aim of this work is to experimentally assess the effectiveness of the Lin et al. algorithm for detecting the tampering of JPEG images. The authors of this algorithm already conducted an experimental evaluation of its performance. However, this evaluation was conducted using a proprietary dataset, thus limiting the possibility to compare the performance of their algorithm with other alternative approaches. As recognized by the authors of the algorithm, such a choice was motivated by the difficulty in assembling a large set of images that have not been (or that have been) tampered for sure. Nowadays, this problem seems to be partially solved. The arising interest toward this topic has led to the development of datasets of images, to be used for evaluating digital tampering detection algorithms. This fact marks an important opportunity for the scientific community working in this field, as it allows to compare the different algorithms proposed so far according to a common benchmark. Moreover, it becomes possible to evaluate the performance of an algorithm in a neutral way.

The Algorithm by Lin et al.

The algorithm by Lin et al. [START_REF] Lin | Fast, Automatic and Fine-grained Tampered JPEG Image Detection via DCT Coefficient Analysis[END_REF] detects tampered images by examining the double quantization (DQ) effect contained in the DCT coefficients. This effect occurs when the DCT coefficients histogram of an image has periodically missing values or some periodic pattern of peaks and valleys. According to Lin et al., this effect can be used for image authentication. To this end, they show that the image regions (i.e. 8 × 8 blocks) that do not exhibit the DQ effect are probably tampered. Namely, in a tampered image, untampered blocks will exhibit the DQ effect, while tampered blocks (also called doctored blocks) will not. The algorithm works as follows. As a preliminary step, if the input image I is not a JPEG image, it is converted to this format at highest quality. The first step of the algorithm is the extraction from I of the DCT coefficients and of the quantization tables for each of the three YCbCr channels. As second step, the algorithm builds one DCT coefficients histogram for each of the three YCbCr channels and for each of the 64 frequencies. The computed histograms are used for determining a probability value which indicates if a particular 8 × 8 block of the input channel image is doctored, by checking the DQ effect. In turns, in the third step, these probabilities are combined together to produce the Block Posterior Probability Map (BPPM). The resulting BPPM is thresholded to distinguish between (probably) doctored parts and undoctored parts. In details, for each image and for each channel, the values of the corresponding BPPM are classified, according to a threshold T , into two classes: tampered blocks (C0) and untampered blocks (C1). The fourth step is the extraction of a four-dimensional feature vector for each of the three YCbCr channels. The first feature is the sum of the variances of the probabilities in C0 and C1. The second feature is the squared difference between the mean probabilities of C0 and C1. The third feature, Topt, is a threshold that maximizes the ratio between the second feature and the first feature. When using Topt, we expect that the blocks in the class C0 (i.e. those that have lower probability of Topt) correspond to the doctored blocks. The last feature, K0, is a measure of the connectivity of C0 blocks: more is connected C0, then smaller is K0. In the last step of the algorithm, a trained Support Vector Machine (SVM) dichotomous classifier is run to decide, starting from the previously extracted features, whether the image is doctored or not.

Experimental Analysis

In this section we detail the results of the experimental analysis we conducted on the Lin et al. algorithm. To begin, we developed a Java-based implementation of this algorithm3 . This implementation, here named DQD, includes two core modules:

-The Feature Extractor module is in charge of extracting the features used for the classification by the Lin et al. algorithm from a batch of input images. The extraction is performed with the help of the libjpeg library [START_REF]Tom Lane and the Independent JPEG Group[END_REF]. If the input image is not in the JPEG format, we apply the JPEG compression algorithm at the maximum quality factor. -The SVM Manager module is in charge of managing the SVM classifier to be used for detecting tampered images or not. It uses the SVM implementation available with the Java Machine Learning library [START_REF] Abeel | Java-ML: A Machine Learning Library[END_REF], using the LIBSVM module. To get more accurate decisions, our classifier uses the Cross Validation (CV ) and the Grid Search (GS) techniques. The CV technique is a method of sampling used to divide the original sample into two subsets: in the first subset we estimate the parameters of a model, while in the second subset we measure the predictive ability of the estimate. The GS technique is a search technique used to identify the parameters that optimize the performance of the classifier exploiting the cross validation. The next step has been to assess the performance of the developed implementation by analyzing its experimental behavior on several datasets. In the following, we introduce the datasets used in our experimentations, then we describe the experimental setting and discuss the outcoming results.

Dataset

In the recent years, several public datasets have been released for evaluating tampered image detection algorithms. If we restrict our interest to JPEG-based datasets, there is only one choice that has become the de facto standard for these experimentations: the CASIA TIDE dataset4 [START_REF]CASIA Tampered Image Detection Evaluation Database (CASIA TIDE)[END_REF]. It is available in two versions: v1.0 and v2.0. The v1.0 version is a small-scale dataset of low resolution images. The v2.0 version is a large-scale dataset containing 7, 491 authentic and 5, 123 tampered color images. The images have different resolutions, varying from 240 × 160 to 900 × 600 pixels, and different formats (i.e., BMP, TIFF, JPEG). Tampered images included in this dataset are the result of a splicing that has been dissimulated, sometimes, by using a blur operation over the tampered image. We have chosen for our experiments the v2.0 of the dataset because it contains a large number of high resolution images, tampered using more sophisticated techniques. In addition, dataset has been widely used in the scientific literature for evaluating tampered images detection algorithms. Thus, its adoption would simplify the comparison of the performance of the Lin et al. algorithm with other detection algorithms. Starting from the original CASIA TIDE v2.0 dataset, we extracted a subset of images, called SC ALL, containing 2, 000 random training photos divided into 1, 000 authentic (990 JPEG and 10 BMP) and 1, 000 tampered (633 TIFF and 367 JPEG). The remaining 6, 491 authentic (44 BMP and 6, 447 JPEG) and 3, 875 tampered images (2, 426 TIFF and 1, 449 JPEG) were used for SVM testing. Notice that some tampered images were left out of our experiments because they originated from non-JPEG images and, thus, they could not exhibit the DQ effect on which relies the Lin et al. algorithm. A second dataset, called SC JPEG, has been obtained by filtering only the JPEG images of SC ALL. A third dataset, called DC ALL, was obtained by considering all images of SC ALL and performing a JPEG recompression on authentic images using a quality factor randomly chosen in the set {100, 99, 95, 90, 85, 80, 75, 70}. Finally, we introduced a fourth dataset, DC JPEG, obtained by filtering only the JPEG images existing in DC ALL.

Preliminary Experimentations

In this section, we present the results of a first round of experimentations of the Lin et al. algorithm. To begin, we conducted a preliminary test to evaluate the optimal number of frequencies to be used for building the DCT coefficients histograms required by the algorithm. In theory, for each color channel, these coefficients are related to an overall number of 64 frequencies. However, since the high frequencies DCT coefficients are often quantized to zero, we will use only the lower frequencies histograms for each channel. To this end, we ran the algorithm on our datasets using, respectively, the 32, the 48 and the 64 lower frequencies. The outcoming results show that the best setting, in terms of recognition rate (RR, i.e. the percentage of testing images correctly recognized as authentic or tampered), is reached when using 32 frequencies. Therefore, in subsequent experiments, we will always use this value. Table 1 shows the percentage of testing images correctly recognized as authentic or tampered (RR) when we ran DQD on the datasets defined in Section 6.1 using the 32 lower frequencies. These numbers confirm the good performance of the Lin et al. algorithm. We observe that the algorithm was able to correctly recognize as original or tampered about This percentage increases by, approximately, a 15% when considering the variants of these datasets including only JPEG images. This seems to indicate that, differently from TIFF tampered images, JPEG tampered images are able to retain some statistical artifacts useful for the classifier to detect their forgery. This is confirmed by the improvement of the performance of the algorithm on doubly compressed images (recall that the algorithm has been designed for dealing with doubly compressed JPEG images) while the inclusion of TIFF images (DC ALL) leads to a small degradation of the overall performance of the algorithm. A deeper analysis of the images of the CASIA TIDE dataset revealed a sort of anomaly. The luminance quality factor of the majority of the JPEG tampered images is always the same (i.e., either set to about 90 or to about 100), while authentic images have more variable quality factors, ranging mostly in the interval [70,100]. This fact may compromise the quality of this dataset since it introduces a separation criteria between authentic and tampered images that is relatively easy to verify.

Experimenting with New Features

Starting from the observations made in Section 6.2, we explored the possibility to improve the performance of the Lin et al. algorithm, by enriching the SVM classifier with three additional groups of features. The first feature is an estimation of the image luminance quality factor. This feature has been chosen for two reasons. First, we noticed that some of the Lin et al. algorithm features are influenced by the applied JPEG compression rate, i.e. quality factor. Second, we are interested in exploiting the anomaly found in the CASIA TIDE dataset, about the luminance quality factors being always the same for tampered images, to see how much it could influence the performance of the classification.

In our experiments, we extracted this feature starting by the luminance quantization table embedded in each JPEG image. Namely, we apply an estimate of the inverse formula of [START_REF]Independent JPEG Group code library[END_REF] that, given a JPEG image quantization table and the standard quantization table, returns an estimation of the quality factor used to determine the image quantization matrix.

The second feature is the relative frequency of doctored blocks existing in authentic and tampered images on each channel. We noticed that both tampered and authentic images contain blocks that have been considered doctored by the Lin et al. method. However, if we consider only the chrominance channels, the average number of doctored blocks for tampered images clearly differs from the average number of doctored blocks for authentic images. Therefore, this information can improve the separation of these two classes.

The third feature we introduce is the spatial resolution of the input image (i.e., width and height). We consider this feature because we noticed that some of the features used by the Lin et al. algorithm in part depend on the resolution of the input image.

After introducing these new features, we have trained and tested the SVM classifier using the original features of the Lin et al. algorithm plus different combinations of the new ones. The results are presented in Table 1. Here, the R capital letter marks the inclusion of the image resolution feature (i.e, width feature and height feature), the F capital letter marks the inclusion of the relative frequencies of tampered blocks for each color channel feature and the Q capital letter marks the inclusion of the luminance quality factor estimation feature.

According to these results, it seems that the introduction of the feature related to the image resolution (DQD R) brings only a slight advantage on the performance of the DQD algorithm on all considered datasets. An improvement is also achieved when considering the features related to the relative frequencies of tampered blocks (DQD F), especially for the case of JPEG images. This is a further confirmation of the ability of the algorithm to detect the DQ effect on doubly compressed JPEG tampered images.

A completely different behavior is the one we observed with the introduction of the feature related to the image luminance quality factor. On the SC ALL dataset, the inclusion of this feature led to a consistent performance improvement over DQD. On the DC ALL dataset the improvement was consistent ye,t but smaller than on the SC ALL dataset. On the SC JPEG and DC JPEG datasets, we measured only a slight performance improvement. To explain this we recall the observation made in Section 6.2 about the JPEG tampered images belonging to the CASIA TIDE datasets. These images are always saved using fixed quality factors, whereas their non-tampered counterparts are saved using variable quality factors. In addition, TIFF tampered images are automatically converted by our algorithm into JPEG images with a quality factor fixed to 100. These two facts provide the classifier with a clear distinction between tampered and non-tampered images, thus justifying the performance boost of DQD Q on SC ALL. If we leave out from the comparison the TIFF images, like in the SC JPEG case, the improvement is still present but is smaller. Here the gap between the quality factor of authentic images (87, in the average) and tampered images (90, in the average) is smaller, thus preventing a clear separation between these two sets.

The anomaly of the CASIA TIDE dataset is weakened when considering authentic images that have been recompressed using random quality factors, such as in DC ALL. Here, the performance boost of DQD Q is much smaller than in the SC ALL case. Instead, the recompression of the input images brings a little benefit to DQD Q when dealing with only JPEG images. In this case, the performance loss due to the absence of a clear distinction between the quality factor of tampered and authentic images is balanced by the ability of the algorithm to perform better when dealing with the DQ effect of doubly compressed images. According to our experiments, even the mixing of these new features improves the overall quality of the detection. This is especially the case of DQD FQR algorithm, which is the variant of the Lin et al. algorithm exhibiting the better performance, by considering all the features of the original algorithm plus all the features we introduced in our experiments.

Conclusions and Future Work

In this paper, we analyzed the experimental performance of the algorithm by Lin et al. [START_REF] Lin | Fast, Automatic and Fine-grained Tampered JPEG Image Detection via DCT Coefficient Analysis[END_REF], a popular technique for the detection of tampered JPEG images. The experiments have been conducted on several variants of the v.2.0 CASIA TIDE dataset, a collection of images developed for the experimental evaluation of this family of algorithms. The final aim of this experimentation was to facilitate the comparison of the Lin et al. algorithm with other alternative approaches by measuring its performance on a widely-used testbed. On a side, the results we obtained confirmed the good performance of this algorithm. On the other side, we were able to detect a sort of anomaly in the way the CASIA TIDE dataset has been built (i.e., many of the tampered images have been saved using almost-fixed quality factors) that could facilitate the detection activity. The relevance of this anomaly has been confirmed by a further experimentation, where we added to the original Lin et al. algorithm the ability to detect whether an image is tampered or not by looking also at this anomaly. As a matter of fact, the revised version of the algorithm exhibited a significant performance boost on a dataset featuring almost all the images of the CASIA TIDE dataset. These observations pose the question about the full statistical soundness of the CASIA TIDE dataset while suggesting the opportunity to reconsider the results of all the experimental studies that have been conducted so far using this dataset. As a future direction, it would be useful to fix the anomaly we found in the CASIA TIDE dataset or, as an alternative, to introduce of an improved testbed for the experimentation of image integrity detection algorithm able to solve the problems existing in the CASIA TIDE dataset. Concerning the Lin et al. algorithm, a future direction for this work would be to extend our experimental analysis to other relevant contributions existing in the field of algorithms for assessing the integrity of JPEG images.

Table 1 .

 1 Recognition rates, in percentage, of the Lin et al. algorithm on different variants of the CASIA TIDE v2.0 dataset using different features.

	Algorithm	SC ALL	DC ALL	SC JPEG DC JPEG
	DQD	71.00	69.55	84.32	85.08
	DQD R	71.92	71.29	84.79	85.51
	DQD F	71.74	70.85	85.76	86.41
	DQD Q	86.01	74.41	85.37	85.79
	DQD FQ	88.78	78.72	87.46	89.30
	DQD QR	86.13	75.10	85.45	85.93
	DQD FR	73.06	72.25	86.36	87.30
	DQD FQR	89.15	80.17	89.25	90.10

the 70% of the images belonging to the SC ALL and DC ALL datasets.

A copy of the source code of our implementation is available upon request.

Credits for the use of the CASIA Tampered Image Detection Evaluation Database (CASIA TIDE) v2.0 are given to the National Laboratory of Pattern Recognition, Institute of Automation, Chinese Academy of Science, Corel Image Database and the photographers. http://forensics.idealtest.org


domain: math info

text:
Benoit Monin
email: benoit.monin@gmail.com

Higher randomness and forcing with closed sets

Keywords: Effective descriptive set theory, Higher computability, Effective randomness, Genericity

). In this paper, we refute this conjecture and show that this nullset is merely Σ 0 3 . Together with a result of Liang Yu, our result also implies that the exact Borel complexity of this set is Σ 0 3 . To do this proof, we develop the machinery of effective randomness and effective Solovay genericity, investigating the connections between those notions and effective domination properties.

Introduction

We will study in this paper the notion of forcing with closed sets of positive measure and several variants of it. This forcing is generally attributed to Solovay, who used it in [START_REF] Solovay | A model of set-theory in which every set of reals is Lebesgue measurable[END_REF] to produce a model of ZF + DC in which all sets of reals are Lebesgue measurable. Stronger and stronger genericity for this forcing coincides with stronger and stronger notions of randomness. It is actually possible to express most of the randomness definitions that have been made over the years by forcing over closed sets of positive measure. by a notion introduced by Jockusch in [START_REF] Jockusch | Simple proofs of some theorems on high degrees of unsolvability[END_REF] about effective genericity for Cohen forcing. This new definition will reveal itself to be interesting for its connections with effective domination properties. In the third section we will give a quick description of what we need of higher computability theory and higher randomness to approach the last section. Finally in the last section we give higher analogues of the Solovay genericity notions studied in section two, and we show again their connections with randomness and higher effective domination properties. This will allow us to conclude with the Borel complexity of the largest Π 1 1 nullset.

General Background

In this paper, we will work in the space of infinite sequences of 0's and 1's, called the Cantor space, denoted by 2 ω . We will call strings finite sequences of 0's and 1's, sequences elements of the Cantor space and sets the sets of sequences. For a string σ, we will denote the set of sequences extending σ by [σ].

The set of integers W e will denote the domain of the computable function Φ e , and [W e ] will denote σ∈We [σ], where W e is seen as a set of strings. We will denote by , a fixed computable pairing function from ω × ω to ω.

We will consider computable functionals (computable functions using sequences as oracles) as functions from the Cantor space to the Baire space. Then a computable functional Φ is considered define on X ∈ 2 ω if ∀n Φ X (n) ↓ and we denote by dom Φ the set {X | ∀n Φ X (n) ↓}. We say that a function f is computable relative to X or X-computable if there is a computable functional defined on X such that Φ X = f . The topology on Cantor space is generated by the basic intervals [σ] = {X ∈ 2 ω | X σ} for σ a string. For A ⊆ 2 ω Lebesgue-measurable, λ(A) will denote the Lebesgue measure of A, which is the unique Borel measure such that λ([σ]) = 2 -|σ| for all strings σ.

About the arithmetical complexity of sets

In the Cantor space, open sets can be described as countable unions of strings.

We call an open set effective if it can be described as the union of a computably enumerable set of strings, i.e. if it is equal to [W e ] for some e. Such a set is said to be Σ 0 1 . On the other hand, when it is open but not necessarily effectively open, the set is said to be Σ 0 1 . However, a non-effective open set is always effective relatively to some oracle. If X is such an oracle, we say that the set is Σ 0 1 (X). A closed set is called effective if its complement is an effective open set, in which case we say that the closed set is a Π 0 1 set. We can then continue to describe the effective Borel sets through the arithmetical hierarchy as effective unions of effective Borel set of lower complexity and as their complements. So a Σ 0 n+1 set will be an effective union of Π 0 n sets, and a Π 0 n+1 set will be the complement of a Σ 0 n+1 set. For example, a set A is Σ 0 4 if we have an integer e such that A =

m1∈We m2∈Wm 1 m3∈Wm 2 [W m3 ] c .
We have a canonical surjection from integers to Σ 0 1 sets (The one which associates to e the computably enumerable set [W e ]), but also from integers to Σ 0 n sets for a fixed n. In the above example, with n = 4 the integer e is associated to the Σ 0 4 set A. In this context e will be called an index for the set A.

Also for a computably enumerable set of integers W , we denote by W [t] the enumeration of W up to stage t. We extend this definition to effective open sets

: if O = [W ], then O[t] = [W [t]]. Similarly, if F = O c , F [t] = O[t] c .

About algorithmic randomness

In 1966, Martin-Löf gave in [START_REF] Martin-Löf | The definition of random sequences[END_REF] a definition capturing elements of the Cantor space that can be considered 'random'. Many nice properties of the Martin-Löf random sequences make this notion of randomness one of the most interesting and one of the most studied.

Intuitively a random sequence should not have any atypical property. A property is here considered atypical if the set of sequences having it is of measure 0. It also makes sense to consider only properties which can be described in some effective way (because any X has the property of being in the set {X} and thus nothing would be random).

Definition 1 An intersection of measurable sets n A n is said to be effectively of measure 0 if the function which to n associates the measure of A n is bounded by a decreasing computable function whose limit is 0. A Martin-Löf test is a Π 0 2 set n O n effectively of measure 0. We say that X ∈ 2 ω is Martin-Löf random if it is in no Martin-Löf test.

One can iterate this idea by considering Π 0 n sets effectively of measure 0 for any n ≥ 2. Martin-Löf randomness is also called 1-randomness, the use of Π 0 3 sets effectively of measure 0 gives us 2-randomness, Π 0 4 sets give us 3-randomness, and so on. The requirement for a Martin-Löf test to be effectively of measure 0 is important and leads to very nice properties. In particular there exists a universal Martin-Löf test, i.e. a test containing all the others (see [START_REF] Martin-Löf | The definition of random sequences[END_REF]). This is not the case anymore if we drop the 'effectively of measure 0' condition. Instead we get a notion known as weak-2-randomness.

Definition 2 We say that X ∈ 2 ω is weakly-2-random if it is in no Π 0 2 nullset.
As a randomness notion, weak-2-randomness is a strictly stronger than 1-randomness, but is strictly weaker than 2-randomness (see [START_REF] Nies | Computability and Randomness[END_REF] section 3.6).

Solovay genericity and its variants

Cohen introduced in [START_REF] Cohen | Set theory and the continuum hypothesis[END_REF] the general technique of forcing by forcing with all dense open sets of the Cantor space (with the usual topology) in a countable model of ZFC. The most basic effective version of this would be to say that X is generic if it belongs to all dense Σ 0 1 sets, a notion introduced by Kurtz in [START_REF] Kurtz | Randomness and genericity in the degrees of unsolvability[END_REF]. Jockusch introduced and studied in [START_REF] Jockusch | Simple proofs of some theorems on high degrees of unsolvability[END_REF] a slightly different notion.

Definition 3 (Kurtz, Jockusch) We say that X is weakly-1-generic if it belongs to all dense Σ 0 1 sets. We say that X is 1-generic if for any Σ 0 1 set U , either X belongs to U or X belongs to some other Σ 0 1 set U disjoint from U .

We will apply Jockusch's idea behind 1-genericity to forcing with Π 0 1 sets. First note that by definition, the weakly-2-randoms are exactly the sequences which are in all Σ 0 2 sets of measure 1. If we consider the topology generated by Π 0 1 sets of positive measure, because Σ 0 2 sets of measure 1 are then dense open sets for this topology, we also get in some sense a genericity notion. Definition 4 Let {G i } i∈ω be the collection of all Σ 0 2 sets which intersect all the Π 0 1 sets. We say that X is weakly-Π 0 1 -generic if it belongs to i G i .

As the next proposition shows, weak-Π 0 1 -genericity has nothing to do with randomness.

Proposition 1 No weakly-Π 0 1 -generic sequence is 2-random.

Proof We construct uniformly in n a Σ 0 2 set intersecting all Π 0 1 sets and with measure smaller than 2 -n . Let {F e } e∈ω be an enumeration of the Π 0 1 sets. For each e we initialize σ e to the first string (using lexicographic order) of length n + e + 1. Our Σ 0 2 set will consist of a computably enumerable set A of indices of Π 0 1 sets. We now describe the algorithm to enumerate elements of A: At stage t, for each substage e < t in increasing order, if the index of F e ∩ [σ e ] has not been enumerated yet into A, then enumerate it. After that, if (F e ∩ [σ e ])[t] = ∅ then reset σ e to be the string of length n + e + 1 following σ e in the lexicographic order. If σ e is already the last such string, leave it unchanged.

Let us prove that the measure of the Σ 0 2 set represented by A is smaller than 2 -n . For each e, if F e ∩[σ e ] = ∅ then by compactness (F e ∩[σ e ])[t] = ∅ for some t. Thus at most one string σ e of length n+e+1 such that F e ∩[σ e ] = ∅ has been enumerated into A, and the measure of A is bounded by e 2 -n-e-1 ≤ 2 -n . Now our Σ 0 2 set is dense because if F e is not empty then there exists a string σ e of length n + e + 1 such that F e ∩ [σ e ] is not empty and then A will intersect F e .

From this we can then construct a Π 0 3 set effectively of measure 0 and containing all the weakly-Π 0 1 -generic sequences.

Following Jockusch's 1-genericity idea we now define Π 0 1 -genericity:

Definition 5 A sequence X is Π 0 1 -generic if for all Σ 0 2 sets G, either X is in G or there is a Π 0 1 set F disjoint from G such that X is in F .
We now establish a simple but surprising connection with computability theory, which appears to be previously unknown. We say that a sequence X is computably dominated if for every total function f : ω → ω, computable relative to X, there exists a total computable function g such that g dominates

f (i.e. ∀n f (n) ≤ g(n)). Proposition 2 A set X is Π 0 1 -generic iff it is computably dominated.
Proof Suppose X is computably dominated and take any

Σ 0 2 set n F n . Sup- pose that X belongs to its complement, a Π 0 2 set n O n . Let us define the X-computable function f : ω → ω which to n associates the smallest t so that X ∈ O n [t]. As X is computably dominated, there is a computable function g which dominates f . Then X ∈ n O n [g(n)], an effectively closed set disjoint from n F n .
Conversely suppose that X is Π 0 1 -generic and consider a functional Φ, defined on X. We have that dom

Φ = {X | ∀n Φ X (n) ↓} is a Π 0 2 set containing X. But then as X is Π 0 1 -generic, it is contained in a Π 0 1 set F contained in the domain of Φ.
Let us now build 1 a computable function f such that ∀X ∈ F Φ X < f . To compute the value of f (n) we find the smallest pair m, t such that for all strings σ of size m with [σ] ⊆ F [t], the functional Φ halts on n in less than t steps with σ as an oracle (considering that if Φ needs to use bits of the oracle at positions bigger than |σ|, it does not halt). Then we set f (n) to the sum of all those values plus one. All we need to show is that f is total. Fix n and let us prove there is a m so that for all X ∈ F we have Φ X m (n) ↓. Suppose not, then for all m there is X ∈ F with Φ σm (n) ↑ where σ m = X m . As {σ m } m∈ω is infinite it has at least one limit sequence Y and as F is closed we have Y ∈ F . Also as Φ Y m (n) ↑ for all m we have that Φ is not defined on Y which contradicts the hypothesis. Thus for some t we have that F [t] is covered by a finite union i≤k [σ i ] such that Φ σi (n) ↓. It follows that for some t and some m we have that Φ σ (n) halts in less than t steps for all strings σ of size m such that

[σ] ⊆ F [t].
A direct computation shows that the set of computably dominated sequences is Π 0 4 . The above proposition lowers down the Borel complexity to Π 0 3 : if for every set A we denote by A • the interior of A for the topology generated by Π 0 1 sets, i.e. the union of all Π 0 1 sets included in A, then the set of computably dominated sequences is the intersection over all the Π 0 2 sets P , of P • ∪ P c . We will show later with Theorem 1 that this characterization is optimal: The set of computably dominated sequences is not Σ 0 3 .

3.2 Forcing with Π 0 1 sets of positive measure

We now introduce a notion of genericity which is a measure-theoretic variation of Π 0 1 -genericity defined in the previous section. The notion will be interesting for its counterpart in Higher computability. It will also help us to show that the set of computably dominated sequence is not Σ 0 3 . Let us consider the topology generated by Π 0 1 sets of positive measure. To obtain weak-2-randomness we consider only Σ 0 2 sets of measure 1. We now would like to consider all Σ 0 2 sets which intersect with positive measure every Π 0 1 set of positive measure. In order to keep a genericity notion, we would like to avoid asking explicitly for the intersection to be of positive measure. To do so, we can consider the topology generated by Π 0 1 sets containing only Martin-Löf randoms: such sets are necessarily of positive measure, and if they intersect other Π 0 1 sets, then also the intersection must be of positive measure. Definition 6 Let {G i } i∈ω be the collection of all Σ 0 2 sets A intersecting every Π 0 1 sets of Martin-Löf randoms. Then we say that X is weakly-Π 0 1 -Solovaygeneric if it belongs to i G i .

Definition 7

We say that X is Π 0 1 -Solovay-generic if for any Σ 0 2 set A, either X is in it or there exists a Π 0 1 set F of Martin-Löf randoms and disjoint from A such that X is in it.

Proposition 3 A set X is Π 0 1 -Solovay-generic iff it is weakly-2-random and computably dominated.

Proof Suppose that X is weakly-2-random and computably dominated. Take any Σ 0 2 set and suppose that X does not belong to it. By Proposition 2, as X is computably dominated, we have that X belongs to some Π 0 1 set disjoint from the Σ 0 2 set. Also as X is weakly-2-random it is in particular Martin-Löf random and thus it must belong to a Π 0 1 set containing only Martin-Löf randoms. But the intersection of these two Π 0 1 sets must contain only Martin-Löf randoms and is disjoint from the Σ 0 2 set. Conversely, suppose that X is Π 0 1 -Solovay-generic. It is weakly-2-random, because in particular it is in every Σ 0 2 set of measure 1. It is also by definition Π 0 1 -generic. Then by Proposition 2 we have that it is computably dominated.

We now use this notion of forcing with Π 0 1 sets of Martin-Löf randoms, in order to show that the set of computably dominated sequences is not Σ 0 3 . For this we adapt a technic that Liang Yu exposed in [START_REF] Yu | Descriptive set theoretical complexity of randomness notions[END_REF], in order to show that the Borel complexity of the weak-2-randoms is not Σ 0 3 . The proof we give is very similar and uses the same key lemma: Lemma 1 (Yu Liang [START_REF] Yu | Descriptive set theoretical complexity of randomness notions[END_REF]) For every Π 0 1 set P , there is a Π 0 2 set n V n of measure 0, such that for any string σ, if

P ∩ [σ] = ∅, then P ∩ [σ] ∩ n V n = ∅.
Theorem 1 The set of computably dominated sequences is not Σ 0 3 . Proof Suppose that a Π 0 2 set n U n contains only computably domibated sequences. Let

B = {T | T ∩ n U n = ∅ and T is a Π 0 1 set of Martin-Löf randoms}
Let us prove that the set B intersects any non-empty Π 0 1 set containing only Martin-Löf randoms. Take any non-empty Π 0 1 set P containing only Martin-Löf randoms. We claim that there must exists a string σ such that [σ] ∩ P = ∅ but such that [σ] ∩ P ∩ n U n = ∅. Suppose otherwise and consider n V n , the Π 0 2 set of measure 0 given by Lemma 1. Note that we can suppose that both n U n and n V n are decreasing intersections. Let σ 0 be such that [σ 0 ]∩P = ∅. By hypothesis on n V n and n U n , there must exists an extention σ 1 of σ 0 with [σ 1 ] ⊆ V 0 , [σ 1 ] ⊆ U 0 and such that [σ 1 ] ∩ P = 0. By iterating the same argument, we can build a sequence of strings

σ 0 ≺ σ 1 ≺ σ 2 ≺ . . . such that [σ i+1 ] ⊆ V i , [σ i+1 ] ⊆ U i and such that [σ i+1 ] ∩ P = ∅. It follows that the unique sequence Y ∈ n [σ n ] ∩ P also belongs to n V n and n U n . As Y ∈ n U n it must be computably dominated. As Y ∈ n V n it is not weakly- 2-random. But as Y ∈ P it is Martin-Löf random.
Also by a classical result of algoritmic randomness, if X is Martin-Löf random but not weakly-2-random, it is not computably dominated (see for instance Proposition 3.6.4 of [START_REF] Nies | Computability and Randomness[END_REF]), which gives a contradiction. Thus for every Π 0 1 set P containing only Martin-Löf randoms, there must exists some string σ such that [σ] ∩ P = ∅ but such that [σ] ∩ P ∩ n U n = ∅. Consequently B is dense for the topology generated by Π 0 1 sets of Martin-Löf randoms. Consider now any countable union of Π 0 2 sets n G n containing only computably dominated sequences. For each set G n we associate a set B n defined as above, which is dense for the topology generated by Π 0 1 sets of Martin-Löf randoms. From Proposition 3, if something is sufficiently generic for this topology, it is computably dominated (and weakly-2-random). Thus there is a computably dominated sequence in n B n . But we also have by design of the B n that n B n ∩ n G n = ∅, which contradicts the fact that n G n contains all the computably dominated sequences.

A separation for weak and non weak-genericity

We will now prove that weak-genericity is not enough to obtain computable domination. For this we shall adapt a proof of a theorem in [START_REF] Barmpalias | Jump inversions inside effectively closed sets and applications to randomness[END_REF] saying that for any function f , there is a weakly-2-random X and an X-computable function g not dominated by f . Here we want weak-Π 0 1 -Solovay-genericity instead of weak-2-randomness.

Theorem 2 For any function f : ω → ω there is an X weakly-Π 0 1 -Solovaygeneric computing a function g : ω → ω which is above f infinitely often.

Proof For this proof we will use the Kucěra-Gács theorem, saying that within any Π 0 1 set of positive measure, we can computably encode any real by some sequence of this Π 0 1 set. However for both the encoding and the decoding we need to know the same lower bound on the measure of the set. We give here the exact theorem that we use to do our proof: Theorem 3 (Kucěra-Gács) There is a computable function Φ such that uniformly in an integer n, a rational q and an index e for a Π 0 1 set F with λ(F ) > q, one can find, relatively to the halting problem, a string σ so that [σ] ∩ F is still of positive and so that the function Φ with σ as an oracle and applied to e, q , outputs n.

One can find a detailed proof of this theorem in section 3.3.2 of [START_REF] Nies | Computability and Randomness[END_REF]. Let us say that a Σ 0 2 set has the ( * ) property if it intersects with positive measure all Π 0 1 sets of positive measure. The weakly-Π 0 1 -Solovay-generic sequence X will be defined as the limit of a sequence of strings σ 0 ≺ σ 1 ≺ σ 2 ≺ . . . of longer and longer length. We first give a naive version of our argument: In the first Π 0 1 component F of the first Σ 0 2 set with the (*) property, we use the Kucěra-Gács theorem to encode f (0) + 1 using an index e for F and a lower bound q for the measure of F . It means that as specified in Theorem 3 we find a string σ 0 so that the function Φ with σ 0 as an oracle and applied to q, e will output f (0) + 1. As [σ 0 ] ∩ F still has positive measure there is a Π 0 1 set enumerated in the second Σ 0 2 set with the ( * ) property, which intersects [σ 0 ] ∩ F with positive measure. We then encode in this second Π 0 1 set the value f (1) + 1. We can continue like this for all Σ 0 2 sets with the (*) property. There are two obstacles here. During the decoding, we do not know what Π 0

1 sets and what lower bound on their measure have been used for the encoding. So we do not just encode in each Π 0 1 set the value f (n) + 1, but also the index of the next Σ 0 2 set with the ( * ) property. But even if we have the right Σ 0 2 set, we still do not know which of its Π 0 1 sets have been used. We fix this by doing something special in both the encoding and the decoding. Fix in advance an enumeration { n i , q i } i<ω where n i is an integer and q i a rational. During the encoding, pick the Π 0 1 set number n i such that the pair n i , q i is the first in the enumeration with the property that q i is a lower bound of its measure. During the decoding, we will pick Π 0 1 sets in the order given by the same enumeration. If at some point the measure goes below the corresponding rational we will know it in a finite time. Then we restart the decoding with the next Π 0 1 set in the enumeration. We know that at some point we will have the right one.

However, a last problem is that by the time we have the right Π 0 1 set, we might have decided a lot of values of the function f and maybe the one that we have coded is already taken. The trick is to design the encoding in a way that we know in advance the time it will take to reach the right Π 0 1 set. The value of f we encode has to be chosen accordingly. We now give the details.

The encoding:

Without loss of generality we can suppose f strictly increasing. Let {S i } i∈ω be an enumeration of all the Σ 0 2 sets. For each S i and each n let us define the Π 0 1 set F i,n so that S i = n F i,n . Now let {e i } i<ω be a list of indices for all the Σ 0 2 sets S ei having the ( * ) property. Let { n i , q i } i<ω be an effective list of all pairs of integers and rationals.

Let us define a string σ 0 = (the empty string), a Π 0 1 set T 0 = F e0,0 , and an integer representing time with t 0 = 0. Start by encoding f (0) + 1 and e 1 into T 0 ∩ [σ 0 ], assuming without loss of generality that it has measure bigger than some q that we will reuse in the decoding. Let σ 1 be the string encoding those values. Suppose now that for i ≤ k + 1 the strings σ i have been defined, and for i ≤ k the integers t i and the Π 0 1 sets T i have been defined. Let us define σ k+2 , t k+1 and T k+1 . Let i be the smallest integer such that λ(F e k+1 ,ni ∩ T k ∩ [σ k+1 ]) ≥ q i . Let t be the computational time necessary to decode the two values encoded in T k ∩ [σ k ], which is also the computational time necessary to find σ k+1 during the decoding, assuming we already know X, T k , σ k , and the lower bound on the measure of T k ∩ [σ k ] that has been used for the encoding. Let t be the smallest computational time s so that for all j < i we have λ(F e k+1 ,nj ∩ T k ∩ [σ k+1 ])[s] < q j , and let t k+1 = t k + t + t . let T k+1 be F e k+1 ,ni ∩ T k . Then we encode f (t k+1 + 1) + 1 and e k+2 into T k+1 ∩ σ k+1 , using q i as a lower bound. Finally let σ k+2 be the string encoding those values.

The decoding:

We set e 0 to be the same as the one used in the encoding, n 0 = 0, q 0 to be the measure used in the encoding of the first two values in T 0 ∩ [σ 0 ], and T 0 = F e0,n0 . For each k > 0 we initialize the Π 0 1 set T k = ∅, the integers e k = 0 and the pairs n k , q k to be the first element in the list { n i , q i } i<ω . Then we set for each k ≥ 0 the string σ k = .

At stage t for each substage k ≤ t in increasing order, if

T k = ∅ go to the stage t + 1. Otherwise check whether λ(T k ∩ [σ k ])[t] ≥ q k . Case 1 : λ(T k ∩ [σ k ])[t] ≥ q k .
Then perform the t first computation steps of the decoding with T k ∩ [σ k ] as the Π 0 1 set and q k as the lower bound on the measure. If in t steps or less we get two values a and b, set all the unassigned values of g(m) for m ≤ t to be a and set e k+1 to be b. Also set σ k+1 to be the prefix used in the decoding and T k+1 to be T k ∩ F e k+1 ,n k+1 . Then go to next substage, or next stage if it is the last substage.

Case 2 : λ(T k ∩ [σ k ])[t] < q k . Then move n k , q k to the next element in the list { n i , q i } i<ω . Set T k = T k-1 ∩ F e k ,
n k . Also for all k > k reset T k to be ∅ and n k , q k to the first element in the list { n i , q i } i<ω . Then restart at the same stage t and the same substage k.

Verification:

Let the stages t k be those that we defined during the encoding process. Let us prove that at stage t k and substage k of the decoding process we have the right Π 0 1 set T k , the right string σ k and the right value q k used for the encoding.

It is obviously true for t 0 . Suppose this is true up to k and let us show this is true for k + 1. Let i be the index so that n i , q i is the first pair in the enumeration with λ(F e k+1 ,ni ∩ T k ∩ [σ k+1 ])[t] ≥ q i . Recall that t k+1 = t k + t + t , where t is the smallest time such that for all j < i we have λ(F e k+1 ,nj ∩T k ∩[σ k+1 ])[t] < q j and where t is the computational time necessary to find σ k+1 during the decoding, assuming we already know T k , σ k and the lower bound on the measure of T k ∩ [σ k ] that have been used for the encoding. By the induction hypothesis we already have those three inputs at time t k . Then at time t k +t we know T k , σ k+1 , and using σ k+1 , we know e k+1 . Obviously by the time t k + t + t we could eliminate all the F e k+1 ,nj for j < i and then we have the right T k+1 . Now let us prove that g is infinitely often bigger than f . When we just moved to the right T k , no more values of g will be decided until the two values are decoded inside T k ∩ [σ k ]. The reason is that for all k > k the set T k is reset to ∅ in the algorithm. Then until this is done the values of g are decided at most up to t k . And once this is done we have the right value of f (t k + 1) + 1 that we will have assigned to some g(s) for at least one s ≤ t k + 1. As f is strictly increasing we have g(s) > f (s).

Using Theorem 2, we have some weakly-Π 0 1 -Solovay-generics which are not computably dominated and so not Π 0 1 -Solovay-generic. One can prove that weakly-Π 0 1 -Solovay-genericity implies weakly-Π 0 1 -genericity by showing that any Σ 0 2 set intersecting all the Π 0 1 sets also intersects with positive measure all Π 0 1 sets of positive measure. Take any Σ 0 2 set intersecting all the Π 0 1 sets. Take now a set F of positive measure and consider the Σ 0 2 set n F n of Martin-Löf randoms (the complement of the universal Martin-Löf test). As it has measure 1, there is some F n such that F ∩ F n has positive measure. But by hypothesis our Σ 0 2 set intersects F ∩F n . The intersection contains only Martin-Löf random sequences and thus is necessarily of positive measure. Thus there is also some weakly-Π 0 1 -generics which are not Π 0 1 -generics.

4 Background on higher computability and higher randomness

We now give a few definitions of higher computability and higher randomness. The Turing reductions are replaced by hyperarithmetical reductions. One intuitive way to understand a hyperarithmetical computation is to think of a standard Turing computation, but with an infinite-time Turing machine. For those machines the computational time is not an integer anymore, but an ordinal. Tapes are infinite and pre-filled with 0's, at a successor stage everything happens as in a regular Turing machine. At a limit stage, the machine changes to a special 'limit' state, the head comes back to the first cell of the first tape and if the value of a cell of a tape does not converge, it is reset to 0 (otherwise it is set to the limit of its previous values). The rest works as usual.

For example, we can build the ordinal time Turing machine which on a tape, at finite computation time t = s, e write 1 on the cell number e of this tape if the program number e halts in less than s steps. At ordinal time ω we then have the halting problem on this tape. Then stages ω + n can be used to compute what one could compute with the halting problem. This can be iterated to compute anything that could be computed in a finite jump. But we can even go beyond a finite jump and continue through the ordinal jumps. To formalize this properly we need to fix the notion of notation for computable ordinals.

Computable ordinals

More details about this section can be found in [START_REF] Sacks | Higher recursion theory[END_REF]. An ordinal is defined as the order type of a well-ordered set. When the ordinal is infinite and countable it can be the order-type of a well-ordered set with domain ω. We say that a countable ordinal α is computable if we have a relation R ⊆ ω × ω which is a well-founded linear order of a subset of ω of order-type α and if there is some e such that (n, m) ∈ R ↔ n, m ∈ W e . In this case we say that e codes for α and we write |e| = α. Let us denote by W the set of integers which code for computable ordinals and let us denote by W α the set of integers which code for computable ordinals strictly smaller than α.

As there are uncountably many countable ordinals, not all of them are computable. Moreover it is known that they form a strict initial segment of the countable ordinals. We denote by ω ck 1 the smallest non-computable ordinal. This notion can then be relativised. We say that e is an X-code for the ordinal α if we have a relation R ⊆ ω × ω which is a well-founded linear order of a subset of ω of order-type α and if (n, m) ∈ R ↔ n, m ∈ W X e . We then write |e| X = α. We denote by W X the set of X-codes for X-computable ordinals, and we denote by W X α the set of X-codes for X-computable ordinals strictly smaller than α. Finally, we call ω X 1 the smallest ordinal which is noncomputable relatively to X. Note that any countable ordinal is computable with a representation of itself as an oracle.

Second order definable sets

We say that a sequence X is hyperarithmetic if for some computable function f and some computable ordinal α we have n ∈ X ↔ f (n) ∈ W α . One can define the hyperarithmetic sequences equivalently as the sequences we can Turing-compute with sufficiently many successive effective joins and iterations of the jump, constructed by induction over the computable ordinals. Also coming back to the analogy with infinite-time Turing machines we have in [START_REF] Hamkins | Infinite time Turing machines[END_REF] a theorem saying that a sequence X is hyperarithmetic iff it can be computed by an infinite-time Turing-machine in a computable ordinal length of time.

Similarly we define what is hyperarithmetic for sets. We say that A ⊆ 2 ω is hyperarithmetic if there exists e and α computable such that X ∈ A ↔ e ∈ W X α .

We now define Π 1 1 sequences. While hyperarithmetic sequences can be considered to be the higher counterpart of computable sequences, Π 1 1 sequences can be considered to be the higher counterpart of computably enumerable sequences. They are the sequences one can define with a formula of arithmetic containing arbitrary many first order quantifications and only universal second order quantifications (with no negations in front of them). We have another equivalent

definition. A sequence X is Π 1 1 if for some computable function f we have n ∈ X ↔ ∃α < ω ck 1 f (n) ∈ W α .
Coming back to the analogy with infinite-time Turing machines, the Π 1 1 sequences also correspond to the sets of integers one can enumerate along computable ordinal length of time with such a machine (when we interpret sequences as sets of integers, considering that n in the set iff the n-th bit of the sequence is one). The Σ 1 1 sequences are their complements (again, when we see sequences as sets of integers), the higher equivalent of co-recursively enumerable sequences. Finally a set A is Π 1 1 if we have an integer e so that X ∈ A ↔ ∃α < ω 1 e ∈ W X α . We also have a canonical surjection from integers to Π 1 1 sets, so like the arithmetical sets, they can be indexed (in the above example, e is an index for the Π 1 1 set A).

A set is called ∆ 1 1 if it is both Σ 1 1 and Π 1 1
. By a theorem of Kleene (see chapter 2 in [START_REF] Sacks | Higher recursion theory[END_REF]) they are exactly the hyperarithmetical sets. An index for a ∆ 1 1 set will consist of a pair of two indices. One expressing it as a Π 1 1 predicate and one expressing its complement as a Π 1 1 predicate.

Note that for Π 1 1 sets, the existential quantification over the ordinals goes up to ω 1 . Indeed, if ω X 1 > ω ck 1 it is possible that X ∈ A is witnessed by some X-code e for α ≥ ω ck 1 . This leads us to a Π 1 1 set of great importance for this paper, the set {X | ω X 1 > ω ck 1 } (the proof that this set if Π 1 1 can be found in section 9.1 of [START_REF] Nies | Computability and Randomness[END_REF]). We now state two theorems that will be useful for the rest of the paper. Theorem 4 (Sacks [START_REF] Sacks | Higher recursion theory[END_REF]) Uniformly in ε and an index for a ∆ 1 1 set A, one can compute an index for a Σ 1 1 closed set F so that F ⊆ A and λ(A -F ) ≤ ε. Also one can uniformly from an index of a ∆ 1 1 set obtain an index for the ∆ 1 1 real being the measure of this set.

Theorem 5 (Spector [START_REF] Sacks | Higher recursion theory[END_REF]) If f : ω → W X is a total Π 1 1 (X) functional predicate then sup n |f (n)| < ω X 1 .

Higher randomness

We now introduce notions of randomness which are higher effective variations of the usual randomness notions.

Definition 8 (Sacks) We say that X ∈ 2 ω is ∆ 1 1 -random if it is in no ∆ 1 1 nullset.

Martin-Löf was actually the first to promote this notion (see [START_REF] Martin-Löf | On the notion of randomness[END_REF]), suggesting that it was the appropriate mathematical concept of randomness. Even if his first definition undoubtedly became the most successful over the years, this other definition got a second wind recently on the initiative of Hjorth and Nies who started to study the analogy between the usual notions of randomness and their higher counterparts. In order to do so they created in [START_REF] Hjorth | Randomness via effective descriptive set theory[END_REF] This definition is strictly stronger than ∆ 1 1 -randomness (see Corollary 9.3.5 in [START_REF] Nies | Computability and Randomness[END_REF]). The higher analogue of weak-2-randomness has also been studied (see [START_REF] Chong | Randomness in the higher setting[END_REF]).

Definition 10 We say that X is weakly-Π 1 1 -random if it belongs to no n O n with each O n open set Π 1 1 uniformly in n and with λ( n O n ) = 0.

Earlier, Sacks gave an even stronger definition, made possible by a theorem of Lusin saying that even though Π 1 1 sets are not necessarily Borel, they remain all measurable.

Definition 11 (Sacks) We say that X ∈ 2 ω is Π 1 1 -random if it is in no Π 1 1 nullset.

This last definition is of great importance. Kechris proved that there is a universal Π 1 1 nullset, in the sense that it contains all the others (see [START_REF] Kechris | The theory of countable analytical sets[END_REF]). Later, Hjorth and Nies gave in [START_REF] Hjorth | Randomness via effective descriptive set theory[END_REF] an explicit construction of this Π 1 1 nullset. Chong and Yu proved in [START_REF] Chong | Randomness in the higher setting[END_REF] that weakly-Π 1 1 -randomness is strictly stronger than Π 1 1 -Martin-Löf-randomness, but it is still unknown whether Π 1 1 -randomness coincides with weakly-Π 1 1 -randomness. To separate the two notions, the idea of showing they have different Borel complexity was promoted in [START_REF] Chong | Randomness in the higher setting[END_REF]. In the next section we show that this will not be possible, by proving that the biggest Π 1 1 nullset has the surprisingly small Borel complexity of Σ 0 3 . Using results of [START_REF] Yu | LogicBlog2013, Higher randomness[END_REF] we will conclude that the Borel complexity of both the weakly-2-randoms and the Π 1 1 -randoms, is strictly Π 0 3 . We now give some important results about higher randomness, that will be needed to achieve this: Theorem 6 (Sacks) The set {X | ω X 1 > ω ck 1 } has measure 0.

  a higher analogue of Martin-Löf randomness. Definition 9 (Hjorth, Nies) A Π 1 1 -Martin-Löf test is given by an effectively null intersection of open sets n O n , eachO n being Π 1 1 uniformly in n. A sequence X is Π 1 1 -ML-random if it is in no Π 1 1 -Martin-Löf test.

One can also directly deduce the existence of such a function f using the fact that the supremum of a computable function, over an effectively compact set, is right-ce.

Acknowledgements I would like to thank Laurent Bienvenu, Noam Greenberg, Paul Shafer and Liang Yu for helpful comments and discussions.

Thus no X such that ω X 1 > ω ck 1 is Π 1 1 -random. The following beautiful theorem of Chong, Yu and Nies (see [START_REF] Chong | Lowness of higher randomness notions[END_REF]) strengthens Sacks' theorem: Theorem 7 (Chong, Yu, Nies) A sequence X is Π 1 1 -random iff it is ∆ 1 1random and ω X 1 = ω ck 1 .

One could also define the randomness notion introduced by Σ 1 1 nullsets, but this turns out to be equivalent to ∆ 1 1 -randomness.

Theorem 8 (Sacks) A ∆ 1 1 -random sequence is in no Σ 1 1 nullset. Therefore Σ 1 1 -randomness coincides with ∆ 1 1 -randomness.

5 Higher Solovay genericity and its variants Definition 12 We say that X is weakly-Σ 1 1 -Solovay-generic if it belongs to all sets of the form n F n which intersect with positive measure all the Σ 1 1 closed sets of positive measure, where each F n is a Σ 1 1 closed set uniformly in n.

Definition 13

We say that X is Σ 1 1 -Solovay-generic if for any set of the form n F n where each

As in the lower case, one could drop the measure requirement in the definition of Σ 1 1 -Solovay-genericity and obtain interesting relations with domination properties. However we will focus in this paper only on (weakly-)Σ 1 1 -Solovaygenericity.

Unlike in the lower case, we have that the set of weakly-Σ 1 1 -Solovay-generics is of measure 1. We can actually prove easily that they coincide with the weakly-Π 1 1 -randoms. Let n F n be a uniform union of Σ 1 1 closed sets with measure strictly smaller than 1. Let n O n be its complement. As it is a Π 1 1 set, we have e such that X ∈ n O n ↔ ∃α < ω 1 e ∈ W X α . But by Theorem 6 we have that {X | ∃α ≥ ω ck 1 e ∈ W X α } ⊆ S is of measure 0. Thus for some computable α we have that {X | e ∈ W X α } has positive measure. As it is a ∆ 1 1 set, we can find using Theorem 4 a Σ 1 1 closed set of positive measure contained in it. Thus n F n does not intersect all Σ 1 1 closed sets of positive measure. Conversely a uniform union of Σ 1 1 closed sets of measure 1 intersects with positive measure any Σ 1 1 closed set of positive measure. Then the weakly-Σ 1 1 -Solovay-generics are exactly the weakly-Π 1 1 -randoms.

We will now prove that the notion of Σ 1 1 -Solovay-genericity is exactly the notion of Π 1 1 -randomness. As explained at the end of the section (after Theorem 10), one can also consider this equivalence as the higher counterpart of Proposition 3.

We already know from Theorem 7 that if X is weakly-Π 1 1 -random but not Π 1 1 -random, then ω X 1 > ω ck 1 . We will show that if X is Σ 1 1 -Solovay-generic then ω X 1 = ω ck 1 which will prove the difficult part of the equivalence. In order to prove this, we use a technique developed by Sacks and simplified by Greenberg, to show that the set of X with ω

In particular for each n we can uniformly restrain the relation coded by o to all elements smaller than n. If |o| X is a limit ordinal this gives a set of X-codes for ordinals smaller than |o| X but cofinal (i.e. unbounded) in |o| X . Thus if

The idea is the following. Suppose that for some X we have a computable function Φ e such that:

Suppose also that X is Σ 1 1 -Solovay-generic. Then we will show that the supremum of |Φ X e (n)| over n ∈ ω is strictly smaller than ω ck 1 . To show this we need an approximation lemma, which can be seen as an extension of Theorem 4. 1 predicate S o . The Π 1 1 index for it corresponds to the property : "There exists no bijection from |e| to a strict initial segment of |o| X ", and a Π 1 1 index for its complement is : "There exists no infinite backward sequence in |e|, and there exists no bijection from |o| X to an initial segment of |e|." Note that if o / ∈ W, the index is still well defined but does not correspond to anything specific.

Then uniformly in an index for S o and in n we can find using Theorem 4 a Σ 1 1 closed set

As an intersection of closed sets, the set F is closed. And as W is Π 1 1 and F o is Σ 1 1 uniformly in o, we have that F is Σ 1 1 . To conclude we also we have that:

We can now prove the desired theorem:

Proof Suppose that Y is Σ 1 1 -Solovay-generic. For any functionnal Φ, consider the set

From Lemma 2 we can find uniformly in n a uniform union of Σ 1 1 closed sets included in P c n with the same measure as P c n . From this we can find a uniform union of Σ 1 1 closed sets included in P c with the same measure as P c . Suppose that Y is in P , as it is Σ 1 1 -Solovay-generic we have a Σ 1 1 closed set F of positive measure containing Y which is disjoint from P c up to a set of measure 0, formally λ(F ∩ P c ) = 0. In particular for each n we have λ(F ∩ P c n ) = 0 and then λ(F c ∪ P n ) = 1. Then let f be the total function which to each pair n, m associates the smallest code o n,m ∈ W such that:

where F c α is the ∆ 1 1 set of strings which are witnessed to be in F c via an ordinal smaller than α. Using second part of Theorem 4 one can prove that f is Π 1 1 . Let α * = sup n,m |f (n, m)|. By Theorem 5 we have that α * < ω ck 1 . Then we have:

1 -Solovay-generic it is in particular weakly-Σ 1 1 -Solovay-generic and then weakly-Π 1 1 -random. Thus by Theorem 8 it belongs to no Σ 1 1 set of measure 0. Then as Fn α<α * P α,n is a Σ 1 1 set of measure 0 we have that X belongs to n α<α * P α,n and then sup n Φ X (n) ≤ α * < ω ck 1 .

We can now prove the equivalence:

Theorem 10 The set of Σ 1 1 -Solovay-generics is exactly the set of Π 1 1 -randoms.

Proof Using Theorem 7 we have that the Σ 1 1 -Solovay-generics are included in the Π 1 1 -randoms. We just have to prove the reverse inclusion. Suppose Y is not

1 and in this case there is a sequence of Σ 1 1 closed sets n F n of positive measure such that X is not in n F n and such that any Σ 1 1 closed set of positive measure which is disjoint from n F n does not contain Y . The complement of n F n is a Π 1 1 set P containing Y . Let e be so that P (X) ↔ ∃α < ω 1 e ∈ W X α . As ω Y 1 = ω ck 1 and P (Y ), we have that ∃α < ω ck 1 e ∈ W Y α . But then Y is in a ∆ 1 1 set that one can approximate using Theorem 4 by an effective union of Σ 1 1 closed sets of the same measure. Thus as X can be in none of them it is in a Π 1 1 set of measure 0 and then not Π 1 1 -random.

The previous theorem gives an interesting corollary, making a connection with another domination property. We say that a sequence X is hyp-dominated if for every total function f : ω → ω, ∆ 1 1 relative to X, there exists a total ∆ 1 1 function g such that g dominates f (i.e. ∀n f (n) ≤ g(n)). Chong, Yu and Nies proved in [START_REF] Chong | Lowness of higher randomness notions[END_REF] that all Π 1 1 -random sequences are hyp-dominated. It follows from that and from the previous theorem that a sequence X is Σ 1 1 -Solovay-generic iff it is weakly-2-random and hyp-dominated. This can be seen as the higher counterpart of Proposition 3.

We have a second corollary, giving a higher bound on the Borel complexity of the Π 1 1 -randoms, and then on the biggest Π 1 1 nullset.

Corollary 1 The set of Π 1 1 -randoms is Π 0 3 .

The Π 0 3 set is obtained exactly the same way we obtain the Π 0 3 set of computably dominated sequences. The following result of Liang Yu (see [START_REF] Yu | LogicBlog2013, Higher randomness[END_REF]) can be used to prove that the set of Π It follows that the set of weakly-Π 1 1 -randoms cannot be Σ 0 3 but also that the set of Π 1 1 -randoms cannot be Σ 0 3 . Indeed, suppose that the set of Π The author, together with Bienvenu and Greenberg separated recently in [START_REF] Bienvenu | Continuous higher randomness[END_REF] the notion of weakly-Solovay-Σ 1 1 -generic from the one of Solovay-Σ 1 1 -generic: There exists a weakly-Π 1 1 -random sequence which is not Π 1 1 -random.