Juneman Abraham
email: juneman@binus.edu

Magda Murty

Pane

The Mediating Role of Social Competition Identity Management Strategy in the Predictive Relationship between Susceptibility to Social Influence, Internet Privacy Concern, and Online Political Efficacy

Keywords: Online efficacy, politics, identity management, social influence, privacy 1

There are few psychotechnological researches in political world in Indonesia, whereas Indonesia will enter "Year of Politics" by General Election which will be held in 2014. This research aimed at examining the hypothesis of predictive correlation, at the individual level, between susceptibility to social influence, internet privacy concern (as predictor variables) and online political efficacy (as the dependent variable). This research hypothesized that the relationship between the variables is mediated by online identity management strategy in the form of social competition. This research employed questionnaire to gain variables data. Participants of this research were 214 undergraduate students of Bina Nusantara University, Jakarta (106 males, 108 females). Result of this research shows that five of seven proposed hypotheses are supported by empirical data. Implications of the result of this research for online system development for political activities are discussed in the end of this article.

Introduction

By the rapid use of online social media to gain political purposes, today it becomes urgent to identify variables taking role in predicting online political efficacy. There are numbers of factors known influence online political efficacy. They are successful past experience (including satisfaction with the experience) in using internet as a political instrument, the nature (quantity and quality) of online interaction among members in a political group, type of social media use (information, entertainment, interaction), as well as quality of access (access location and years online) [START_REF] Perilla | Social Media and Individual and Collective Activism: The Role of Interdependence and Online Political Efficacy[END_REF][START_REF] Livingstone | Balancing Opportunities and Risks in Teenagers' Use of The Internet: the Role of Online Skills and Internet Self-efficacy[END_REF]. This research assumes that online political self-efficacy is influenced by identity management strategy in the form of social competition--defined as continued engagement in the conflict. The concept of identity management is borrowed from Niens and Cairns [START_REF] Niens | Identity Management Strategies in Northern Ireland[END_REF]. According to Tajfel, in: Niens and Cairns [START_REF] Niens | Identity Management Strategies in Northern Ireland[END_REF], identity management strategy is a self-identification strategy of an individual in his/her group "to cope with the perceived outcomes of social comparisons (with his/her out-group)" in order to maintain self-esteem and self-image. Political world is a world which is full of conflict dynamics related to identity, either conflicts among individuals, between individuals and groups, or among groups. Monroe, in: Bernstein [START_REF] Bernstein | Identity Politics[END_REF], stated that conflicts reflect the existence of psychological assumptions concerning how social identity constructed, either actively or passively. Related to that case, referring to the theories of social conflict, conflict is an inherent part of politics [START_REF] Acemoglu | Why Not a Political Coase Theorem? Social Conflict, Commitment, and Politics[END_REF]. Based on this idea, the author builds the first hypothesis (H1), "The higher an individual uses identity management strategy of social competition, the higher his/her online political efficacy will be".

Furthermore, the author hypothesizes that susceptibility to social influence and various aspects of information privacy concern influence individual's online political efficacy. Bobier had conducted a psychometric analysis and found out that there are two factors of susceptibility to social influence, i.e. principled autonomy and social adaptability [START_REF] Bobier | A Measure of Susceptibility to Social Influence: Scale Development and Validation[END_REF]. An individual having high principled autonomy is a kind of individual who has less possibility to give conformity response, but has more possibility to give correct responses on critical trials. An individual having high social adaptability is an individual who has more possibility to give conformity response, but less possibility to give correct responses on critical trials. The author presumes that an individual who tends to conform to his/her in-group will exactly shows high social competition to his/her out-group; the other way around, individual who is more autonomous or independent will shows low social competition toward his/her out-group. Thus, second hypothesis (H2) of this research is "The higher principled autonomy of an individual, the lower identity management of social competition will be", and third hypothesis (H3) is "The higher social adaptability of an individual, the higher identity management of social competition will be".

Social competition can be limited by the individual's privacy concern. The ground idea is that social competition in politics is often accompanied with techniques containing ethical problems from light to heavy, such as the case of tapping the phones of Indonesian public officials, including the President of Indonesia done by intelligent agencies working for Australia [START_REF] Akuntono | Sadap Presiden SBY, DPR Tuntut Australia Minta Maaf[END_REF]. Sims and Gehan through their empirical research also found that online competitions (in the field of economics) often have excesses of information misuse and privacy violation [START_REF] Sims | Privacy and the Spam Act in Online Competitions[END_REF]. This reality means that individuals who are competitive and who have high online political efficacy are possibly individuals who have less attention (or: more tolerable) to privacy issues. The author employs three dimensions of contextual model of Internet Users' Information Privacy Concerns (IUIPC) by Malhotra, Kim, and Agarwal, i.e.: (1) Risk beliefs, (2) Perception of errors corrections of privacy practices, and (3) Perception of unauthorized secondary use of personal information [START_REF] Malhotra | Internet Users' Information Privacy Concerns (IUIPC): The Construct, the Scale, and a Causal Model[END_REF].

Based on the aforementioned idea, the author hypothesizes (H4, H5), "The higher risk beliefs and perception of unauthorized secondary use of personal information, the lower identity management strategy in the form of social competition in the online world" also (H6) that "The higher perception of errors corrections of privacy practices, the higher identity management strategy in the form of social competition in the online world". By integrating H1 to H6, the author builds a hypothetical model as seen on Fig. 1. This model stated that (H7): "There is a nomological network among variables mentioned above which can explain high or low level of individual's online political self-efficacy".

Methods

Participants of this research were 214 undergraduate students of Bina Nusantara University, Jakarta (106 males, 108 females), whose mean of age is 19.35 years old and standard deviation of age is 1.678 years old. The data of this research was analyzed by using path analysis. This research used a questionnaire containing seven scales as an instrument to gain the data of the participants.

This research employed quantitative, predictive correlational design. The research data were processed with LISREL 8.8 program. Measurement specification is as show in Table 1. Online Political Self-efficacy scale consists of nine items. The guideline to fill this scale is as follows: "Please rate how certain are you that you can do the things discussed below by choosing the appropriate response." Examples of the items are: (1) Use social media applications to express your political views;

Results and Discussion

The result of this research shows that overall hypothetical model (H7) is supported by empirical data (Chi-Square = 7.83, df = 5, P-value > 0.05, GFI > 0.90, RMSEA < 0.10) (see Fig. 1). However, the second (H2) hypothesis is supported by the data in term of relationship statistical significance among variables, but not in term of relationship direction since the hypothesis asserts the occurrence of negative correlation, but in fact the author found a positive correlation. This research also found that there is no significant correlation among variables hypothesized in H4 and H5.

Based on the empirical data, path analysis shows that social adaptability (susceptibility to social influence/conformity) is able to indirectly predict online political efficacy through the mediation of social competition identity management strategy. This finding is in line with a study conducted by Kaplan, Brooks-Shesler, King, and Zaccaro entitled "Thinking inside the box: How conformity promotes creativity and innovation" [START_REF] Kaplan | Thinking Inside the Box: How Conformity Promotes Creativity and Innovation[END_REF]. The result of their analysis indicates that conformity is necessary to effectively implement creative ideas--of which creative idea is indeed hugely demanded in the political world. Conformity can facilitate team coordination, information exchange, conflict management, and collective efficacy. This proposition is different from common sense and many other results of researches saying that the success of an innovation can only be generated by the non-conforming team members or those who think divergently. What is often forgotten by the people in this context is that creative idea generations or originations is only a facet of the creative process, and that team's innovation does not only depend on creative ideas production but also depend on realization of the ideas [START_REF] Kaplan | Thinking Inside the Box: How Conformity Promotes Creativity and Innovation[END_REF]. The realization of the ideas needs conformity to in-group. Conformity does not need to mean stick to any or all group or organizational norms, but it means adhere to norms that promote and express team unity. At today's online political life in Indonesia, the finding of this research matches with everyday realities. Online volunteers for Jokowi-Ahok (Current Governor and Deputy Governor of DKI Jakarta, Indonesia) are an effective online team ("cyber troops"; [START_REF] Andi | Mencermati Fenomena Pasukan Dunia Maya Jokowi[END_REF]) who show conformity to group norms, although each of them is a creative individual and even has a high education [START_REF] Afifah | Saat Anak Muda Berkarya Untuk Jokowi-Ahok[END_REF][START_REF] Ichsan | Forum Akademisi IT Menjadi Relawan Jokowi[END_REF].

Susceptibility to Soc Inf IUIPC

Chi-square = 7.83, df = 5, P-value = 0.16575, GFI = 0.99, RMSEA = 0.052

Fig. 1. Research hypotheses and results

This research also found that principled autonomy positively correlate with social competition which later influences online political efficacy. Individual's principled autonomy can be a valuable input for social identity of an individual through one's engagement process toward stories ("master narratives") growing in one's in-group [START_REF] Hammack | Narrative and the Cultural Psychology of Identity[END_REF]--in this case, his/her online political group. It seems to be enabled by lots of attribute diversities of individuals in Jakarta as a megapolitan city and moreover in the online world, which enables an online political group to build their social identity by considering and synthesizing expectation, aspiration, and principles of most of their members. This kind of appreciative thing can latter enhances individual's competitiveness in facing out-group, and next enhances individual's online political efficacy. This research also found that risk beliefs and perception of unauthorized secondary use of personal data are not essential for participants in determining activities which are related to their identity in the virtual world. There are two explanations related to this matter. First, youth who becomes the participants of this research has undergone desensitization of privacy concern. The desensitization occurs since the individual is faced with the frequent dilemma between inevitable need for data sharing (including political interest) and awareness that there is compensation or trade-off that is the reduction of data privacy [START_REF] Bakken | Data Obfuscation: Anonymity and Desensitization of Usable Data Sets[END_REF][START_REF] Cbsdc | Expert: Individuals 'Desensitized[END_REF]. In the end, the urgent need for data sharing is prioritized, and at the same time people actively or passively monitor policies development concerning solutions to privacy problem. Shacklett added that younger workers are more relaxed about privacy [START_REF] Shacklett | Younger Workers More Relaxed About Privacy[END_REF]. Second explanation is that youth (who becomes participants of this research), in fact, has the need to move dynamically, back and forth, between risky experiences [START_REF] Răcătău | Adolescents and Identity Formation in a Risky Online Environment: the Role of Negative User-Generated and Xenophobic Websites[END_REF]. Nevertheless, this research found that Perception of Errors Corrections correlates positively with social competition. The author presumes that the positive correlation tends to be resulted by the fact that in political competition, there is a need to access accurate data from political opponents or outgroups. Data integrity is needed by people or party who conduct online political activities in order to be able to determine the precise strategy. It will activate measurable social competition and further will enhance an individual's online political efficacy.

Conclusion

This research concludes that there is a psychotechnological model which is able to explain an individual's online political efficacy. Online political efficacy can be predicted by (1) Principled autonomy, (2) Social adaptability, and (3) Perception of errors corrections, through the mediating role of social competition identity management strategy. However, internet privacy concerns (risk beliefs and perception of unauthorized secondary use of personal information) are not able to predict it.

In the context of enhancing political participation of the young generation, the result of this research has some important implications. First, since it has been known that online political efficacy is influenced by social competition identity management, thus certain online environments which are intended to be a political arena should be constructed in such a way so that it can facilitate a stimulating, engaging and fun as well as fair competition. This kind of online environment can support political education for the young generation. The author agrees with Priem et al. [START_REF] Priem | The Identity Landscape[END_REF] who emphasize that online customers should be empowered. It has been already clear that online po-litical world has its own customers who continuously grow as time goes by since Indonesia now is entering "Year of Politics" by General Elections 2014. In addition, smart phone and laptop which are usually used to do online activities become cheaper. The empowerment can be done by customization of the online system which embodies effective coordination among members of each political group so that members can align mission, strategy, and symbolic instruments before "fighting" by online in expressing political identity and winning online community's heart who become the target of political campaign. Customization of the online system can also be aimed at creating an express and quick profiling concerning constellation of aspiration and expectation of online political group's members. The resulting profiling can be used to encourage social competition in accordance with strength, weakness, and development opportunities of each member. Second, since it has been known that perception of errors corrections influences social competition, online system needs to be design in such a way so that the data accuracy precision reaches the maximum level. Defect in the online system which results in data inaccuracy will decrease healthy social competition and further will decrease online political efficacy.

Third, since it has been known that most of privacy concerns are not significant in influencing identity management strategy--and further online political efficacy, this knowledge should not be unethically used by online system providers as a chance to exploit individual information of online political player. As mentioned above, insignificant correlation is supposedly caused by a condition in which users experience such "helplessness" as they do not have another choice except accept that private information submission by online is a compensation for the service they use. Academicians and practitioners in psychotechnology fields play a role to design online system which is able to enhance bargaining power of online media services' user in such a way so that unnecessary information disclosure will be further minimized.

  (2) Express coherently your political ideas to other online. Identity Management Strategy (Social Competition) scale consists of four items. Examples of the items are: (1) I want my online community to demonstrate that it is the superior one; (2) I want my online community to demonstrate that it is culturally superior. Principled Autonomy scale consists of five items. Examples of the items are: (1) I am willing to stand up for what I believe, even if I lose some friends as a result; (2) I would be willing to take a public stand regarding my beliefs, even if it meant being dropped out or going to jail. Social Adaptability scale consists of nine items. Examples of the items are: (1) I have deliberately, falsely, agreed with someone because I knew I would have to work with them in the future;(2) I have publicly agreed with something I didn't really believe because it would make it easier to keep working with a person. Risk Beliefs scale consists of four items. Examples of the items are: (1) In general, it would be risky to give information to online companies; (2) There would be high potential for loss associated with giving information to online firms (including Facebook, Twitter, Google, etc). Perception of Unauthorized Secondary Use of Personal Information consists of four items. Examples of the items are: (1) Online companies should not use personal information for any purpose unless it has been authorized by the individuals who provided information; (2) When people give personal information to an online company for some reason, the online company should never use the information for any other reason. Perception of Errors Corrections scale consists of four items. Examples of the items are: (1) All the personal information in computer databases should be double-checked for accuracy, no matter how much this cost; (2) Online companies should have better procedures to correct errors in personal information.

Table 1 .

 1 Measurement specification

	Variable measured	Source of	Cronbach's	Response scales	Corrected
		scale adap-	Alpha		item-total
		tation	(Reliability)		correlations
					(Validity)
	Online political efficacy	Perilla [1]	0.895	Strongly Unsure	0.366-0.778
				(score of 1) to
				Strongly Sure
				(score of 6)
	Social competition identity	Niens and	0.751		0.406-0.640
	strategy	Cairns [3]
	Principled autonomy	Bobier [6]	0.680	Strongly Dis-	0.397-0.550
	Social adaptability		0.672	agree (score of	0.258-0.458
	Risk belief		0.689	1) to Strongly	0.366-0.596
	Perception of unauthorized		0.725	Agree (score of	0.466-0.596
	secondary use of personal	Malhotra et		6)
	information	al. [9]
	Perception of errors correc-		0.728		0.411-0.606
	tions


domain: info math

text:
Benoit Monin
email: benoit.monin@computability.fr

André Nies

A unifying approach to the Gamma question

The Gamma question was formulated by Andrews et al. in "Asymptotic density, computable traceability and 1-randomness" (2013, available at http://www.math.wisc.edu/ ∼ lempp/papers/traceable.pdf). It is related to the recent notion of coarse computability which stems from complexity theory. The Gamma value of an oracle set measures to what extent each set computable with the oracle is approximable in the sense of density by a computable set. The closer to 1 this value is, the closer the oracle is to being computable. The Gamma question asks whether this value can be strictly in between 0 and 1/2.

We say that an oracle is weakly Schnorr engulfing if it computes a Schnorr test that succeeds on all computable reals. We show that each non weakly Schnorr engulfing oracle has a Gamma value of at least 1/2. Together with a recent result of Kjos-Hanssen, Stephan, and Terwijn, this establishes new examples of such oracles. We also give a unifying approach to oracles with Gamma value 0. We say that an oracle is infinitely often equal with bound h if it computes a function that agrees infinitely often with each computable function bounded by h. We show that every oracle which is infinitely equal with bound 2 d n for d > 1, has a Gamma value of 0. This provides new examples of such oracles as well.

We present a combinatorial characterization of being weakly Schnorr engulfing via traces, which is inspired by the study of cardinal characteristics in set theory.

I. INTRODUCTION

Generic-case complexity is a subfield of computational complexity. It started with the observation that some problems that are difficult to solve in full are easy to solve on "most inputs", namely on a set of inputs of density 1. This notion was introduced by Kapovich et al. [START_REF] Kapovich | Generic-case complexity, decision problems in group theory, and random walks[END_REF]. They showed among other things that for a large class of finitely generated groups, the generic case complexity of the word problem is linear.

This notion has recently been extended by Jockusch and Schupp [START_REF] Jockusch | Generic computability, turing degrees, and asymptotic density[END_REF]. The authors identify two notions that can be proved to be incomparable. The first is generic computability, where one must always give the right answer, without having to provide an answer for a small set of input. The second is coarse computability, for which one always have to provide an answer, with the right of being wrong on a small set of inputs. In both cases, a set of inputs is considered small if it is of density 0; this will be made precise in the paper.

Then Andrew et al. [START_REF] Andrews | Asymptotic density, computable traceability, and 1-randomness[END_REF] assign a value γ to each set of natural numbers. They use this to assign a value Γ to each Turing degree. They prove that the Gamma values of 0, 1/2 and 1 can be realized. If a Turing degree has a Gamma value strictly larger than 1/2, then it is computable and its Gamma value in fact equals 1. They ask whether a Turing degree can have a Gamma value strictly in between 0 and 1/2.

We provide a unifying approach to this question. Among the non-computable degrees, the members of two kinds of degree classes are known to have a Gamma value of 1/2: the computably traceable degrees, and the computably dominated random degrees. The proofs suggest that in the two cases this holds for very different reasons. We show here that at the contrary, they are both contained in a common class that implies a Gamma value of 1/2: being not weakly Schnorr engulfing. Together with recent, yet unpublished work of Kjos-Hanssen, Stephan, and Terwijn, this establishes new examples of such degrees.

We also unify the examples of degrees with a Gamma value of 0, by relating them with a property of degrees we call Hinfinitely often equal for an appropriate computable bound H. We end the paper by giving a combinatorial characterization of being weakly Schnorr engulfing, close to the notion of being H-infinitely often equal.

II. PRELIMINARIES AND NOTATIONS

In this paper, we work in the space of infinite sequences of 0's and 1's, the Cantor space, denoted by 2 ω . We call strings finite sequences of 0's and 1's, sequences elements of the Cantor space and sets the sets of sequences. We sometimes also use the word sequence to denote sequences of various objects (typically integers), and when we do so we will always specify it to avoid any ambiguity. We also sometimes view a sequence X as the subset of ω containing n iff X(n) = 1 without necessarily specify it. For a string σ, we denote the set of sequences extending σ by [σ] and we call those sets cylinders. We denote by λ the unique probability measure on 2 ω such that λ([σ]) = 2 -|σ| for any string σ, where |σ| denotes the length of σ.

The Cantor space is endowed with the product topology, for which a set is clopen iff it is a finite union of cylinders, and open iff it is a countable union of cylinders. A set U is effectively open, or Σ 0 1 , if there exists a computably enumerable sequence of strings {σ i } i∈ω such that U = i [σ i ]. A set U is effectively closed, or Π 0 1 , if it is the complement of a Σ 0 1 set. Finally we denote by n, m a computable bijection from ω × ω to ω.

We now introduce notations which are less standard than those of the previous paragraphs. They will be convenient to expose the work of this paper, especially for results of Section V. For a sequence X ∈ 2 ω and a finite interval I ⊂ ω, we denote by X I the string X(I(0))ˆ. . . ˆX(I(m -1)), where m is the length of I. For a string σ and a finite interval I we write [σ] I to denote the set of sequences extending σ, that is, {X ∈ 2 ω : X I = σ}. For a finite interval I ⊂ ω we write J ⊆ 2 I for a clopen set J ⊆ 2 ω if there exists a set of strings σ 0 , . . . , σ k of length |I| such that J = i≤k [σ i ] I .

In this paper we will be interested in having a canonical coding between sequences and functions f : ω → ω which are strictly bounded by some H : ω → ω. Such a function H will generally be an order function, that is, a computable function H such that H(n) ≤ H(n + 1) and lim n H(n) = +∞. To make the coding work nicely we will consider that the bound H is always of the form 2 H(n) . Given a sequence X and such a bound H(n) = 2 H(n) , we denote by f X the function corresponding to X. Formally we define H (n) = m<n H(m) (with H (n) = 0), and f X (n) to be the integer smaller than 2 H(n) which is encoded by the string

X [H (n),H (n+1)) . Conversely, given f with f (n) < H(n) = 2 H(n) , we write X f to denotes the sequence X such that f X = f .

A. Preliminaries on coarse computability

The notion of coarse computability received quite a lot of recent attention by various authors (see for example [START_REF] Andrews | Asymptotic density, computable traceability, and 1-randomness[END_REF] and [START_REF] Hirschfeldt | Asymptotic density and the coarse computability bound[END_REF]).

Definition II.1. A sequence A is coarsly computable if there is a computable sequence X such that the lim inf of the frequency of positions n on which A(n) = X(n), equals 1. More formally, let us introduce the function:

ρ(Z) = lim inf n |Z ∩ [0, n]|
n The sequence A is coarsly computable if for some computable sequence X we have ρ(A ↔ X) = 1, where A ↔ X denotes the sequence which seen as a subset of ω contains n iff A(n) = X(n).

A real number can naturally be assigned to non coarsly computable objects. This number can be seen as an indication of how far the object is from being coarsly computable. It is defined by:

γ(A) = sup X computable ρ(A ↔ X)
We will refer to this as the gamma value of A. Andrews, Cai, Diamondstone, Jockush and Lempp [START_REF] Andrews | Asymptotic density, computable traceability, and 1-randomness[END_REF] had the interesting idea to define a similar value for Turing degrees, which indicates how far a degree is from being computable:

Γ(d) = inf{γ(A) : A ∈ 2 ω is of degree d}
This will be referred to in this paper as the Gamma value of d (with a capital 'G'). In practice we will often write Γ(A) for a set A ∈ 2 ω to mean Γ(d) where d is the Turing degree of A. It is easy to see that one can equivalently consider Γ(A) to be the infinium over tha values γ(B) for every B ≤ T A, rather than just every B ≡ T A. The reason is that given any B < T A, we can add to the sequence B all the information about A at some very sparse computable set of positions, giving a new set Turing equivalent to A, with the same gamma value as B's.

The Gamma question is: which real numbers can be realized by the Gamma value of a degree? In [START_REF] Andrews | Asymptotic density, computable traceability, and 1-randomness[END_REF] Andrews et al. proved that Γ(A) > 1/2 iff Γ(A) = 1 iff A is computable. They also gave examples of sequences A with Γ(A) = 1/2 and examples of sequences A with Γ(A) = 0. These examples will be detailed in Section III. It is unkown whether some sequence has a Gamma value strictly between 0 and 1/2.

B. Preliminaries on algorithmic randomness

Algorithmic randomness uses the tools of computability theory to give a formal definition of the notion of a random infinite binary sequence, a sequence we would expect be the result of independent coin tosses. The reader can refer to [START_REF] Nies | Computability and randomness, ser. Oxford Logic Guides[END_REF] or [START_REF] Downey | Algorithmic randomness and complexity[END_REF] for a background on algorithmic randomness. We briefly discuss the notions important for this paper.

1) Martin-Löf randomness:

The first satisfactory definition of randomness was given by Martin-Löf in [START_REF] Martin-Löf | The definition of random sequences[END_REF]:

Definition II.2. A Martin-Löf test is given by a uniform intersection n U n of effectively open sets such that the function n → λ(U n ) is bounded by a decreasing computable function with limit 0. We say that a sequence X is Martin-Löf random if it belongs to no Martin-Löf test.

Note that one can analogously define sequences which are Martin-Löf random for any computable probability measure µ, by simply replacing λ by µ in the above definition. Such notions will be discussed at the end of Section III-A.

2) Schnorr randomness: The notion of Schnorr randomness was introduced by Schnorr [START_REF] Schnorr | Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie[END_REF], who was aiming at a concept that is more constructive than the one of Martin-Löf.

Definition II.3. A Schnorr test is given by a uniform intersection n U n of effectively open sets such that the function n → λ(U n ) is computable and decreasing with limit 0. We say that a sequence X is Schnorr random if it belongs to no Schnorr test.

It is well known that Schnorr randomness is strictly weaker than Martin-Löf randomness. Downey and Griffiths gave in [START_REF] Downey | Schnorr randomness[END_REF] another characterization of Schnorr randomness that can be seen as an effective version of the Borel Cantelli lemma:

Definition II.4. A Schnorr-Solovay test is a computable se- quence {C n } n∈ω of clopen sets such that n λ(C n ) is finite and computable. A sequence X is captured by a Schnorr- Solovay test {C n } n∈ω if X is in infinitely many sets C n , that is, X ∈ n m≥n C m .
The term "Schnorr-Solovay test" comes from the analogous notion of "Solovay test", which characterizes Martin-Löf randomness. Downey and Griffiths proved that Schnorr-Solovay tests (referred to as total Solovay test in [START_REF] Downey | Schnorr randomness[END_REF]) characterize Schnorr randomness.

Proposition II.5 (Downey/Griffiths [START_REF] Downey | Schnorr randomness[END_REF]). A sequence X is Schnorr random iff it is no captured by any Schnorr-Solovay test.

Definition II.6. A Schnorr-Solovay test {C n } n∈ω is called independent if the sequence {C n } n∈ω is independent in the usual sense of probability theory: λ( r∈F C r ) = r∈F λ(C r ) for each finite set F . As we will see in Section V, each non Schnorr random is captured by an independent Schnorr-Solovay of a very special kind:

Definition II.7. An interval test is given by a uniformly computable sequence of pairs {I n , J n } n∈ω where the I n are pairwise disjoint increasing finite intervals (i.e., max(I n ) < min(I n+1 )), each J n ⊆ 2 In is a clopen set uniformly computable in n, and n λ(J n ) is finite and computable.

3) Higher randomness: Randomness has recently been studied from the viewpoint of higher computability. The reader may refer to [START_REF] Sacks | Higher Recursion Theory, ser. Perspectives in Mathematical Logic[END_REF] or [START_REF] Monin | Higher computability and randomness[END_REF] for background on higher computability, and to [START_REF] Nies | Computability and randomness, ser. Oxford Logic Guides[END_REF] or [START_REF] Monin | Higher computability and randomness[END_REF] for background on higher randomness. Here we summarise the main notions used in the paper.

A set of sequences or of integers is Π1 1 if it can be defined by a second order formula of arithmetic where we can have any quantifier over integers, but only universal quantifiers over infinite objects (sequences or functions). A set of sequences or of integers is Σ 1 1 if it can be defined by a formula of arithmetic with only existential quantifiers over infinite objects. Finally a set sequences or of integers is

∆ 1 1 if it is both Π 1 1 and Σ 1 1 . Definition II.8. A sequence X is ∆ 1 1 -random if it belongs to no ∆ 1 1 set A ⊆ 2 ω with λ(A) = 0. A sequence X is Π 1 1 - random if it belongs to no Π 1 1 set A ⊆ 2 ω with λ(A) = 0.
The Gandy-Spector theorem gives a powerful analogy between the notions of computable/recursively enumerable sets of integers and ∆ 1 1 / Π 1 1 sets of integers. Informally one can picture a Π 1 1 set of integers as being effectively enumerable, but along some "ordinal stages of computation" α < ω ck 1 rather than just finite stages of computation, where ω ck 1 is defined as the smallest non computable ordinal, that is, the smallest ordinal α such that there is no c.e. relation R ⊆ ω ×ω which is a well order of order-type α. Similarly, one can informally picture a ∆ 1 1 set of integers as being effectively enumerable along some "ordinal stages of computation", but bounded by some α < ω ck 1 . One set of particular interest in higher randomness is the set of sequences X such that the smallest non-computable ordinal relatively to X, namely ω X 1 , is larger than

ω ck 1 : {X ∈ 2 ω : ω X 1 > ω ck 1 }.
We have the following theorem: Theorem II.9 (Chong, Nies, Yu [START_REF] Chong | Lowness of higher randomness notions[END_REF]

). A sequence X is Π 1 1 - random iff it is ∆ 1 1 -random and ω X 1 = ω ck 1 .
There exists in higher computability a version of the halting problem. This is the set called Kleene's O, defined as the set of all the codes e such that the binary c.e. relation coded by e is a total well-order of the integers 1 . Every Π 1 1 set is many-one reducible to Kleene's O.

Theorem II.10. For a sequence X we have ω

X 1 > ω ck 1 iff Klenne's O is ∆ 1 1 (X).
Finally we state here what is known as the van Lambalgen theorem for

Π 1 1 -randomness. The sequence X ⊕ Y is defined by (X ⊕ Y )(2n) = X(n) and (X ⊕ Y )(2n + 1) = Y (n). Theorem II.11. For sequences X, Y we have that X ⊕ Y is Π 1 1 -random iff X is Π 1 1 -random and Y is Π 1 1 (X)-random. In particular, if a Π 1 1 -random sequence X is in a Π 1 1 (Y ) nullset then Y is in a Π 1 1 (X) nullset.

C. Preliminaries on weakly Schnorr engulfing and traces

It is well known that unlike the case of Martin-Löf randomness, there exists no universal Schnorr test, that is, no Schnorr test covering all the others. One can prove this by showing that every Π 0 1 set of computable positive measure contains a computable sequence, so that no Schnorr test contains every computable sequence (see for instance Fact 3.5.9 in [START_REF] Nies | Computability and randomness, ser. Oxford Logic Guides[END_REF]). We are interested in oracles that strengthen the power of Schnorr tests, in that some Schnorr test relative to the oracle captures all the computable sequences.

Definition II.12. A sequence A is weakly Schnorr engulfing if there exists an A-Schnorr test containing all the computable sequences.

A weaker property of oracles has already been proved equivalent to a tracing property: some Schnorr test relative to the oracle is not covered by any plain Schnorr test. We first define the tracing property.

Definition II.13 (Terwijn and Zambella [START_REF] Terwijn | Algorithmic randomness and lowness[END_REF]). A computable trace is a uniform sequence {T n } n∈ω of finite sets of integers given by strong indices. Formally T n = D p(n) where p : ω → ω is a computable function and D n is the set containing m iff there is a 1 at position m of the binary encoding of n. An oracle A is computably traceable if there exists a computable bound H : ω → ω such that for every function f ≤ T A, there exists a computable trace

{T n } n∈ω such that |T n | < H(n) and such that f (n) ∈ T n for every n.
Intuitively, an oracle is computably traceable if every function f it computes is 'close to computable', in that one can compute a small set of values f (n) belongs to. By a result Terwijn and Zambella [START_REF] Terwijn | Algorithmic randomness and lowness[END_REF] together with Kjos-Hanssen, Nies and Stephan [START_REF] Kjos-Hanssen | Lowness for the class of Schnorr random sets[END_REF] we have:

Theorem II.14. For an oracle A the following are equivalent:

• A is not computably traceable.

• There is an A-Schnorr test covered by no Schnorr test.

• There is an A-Schnorr test containing a Schnorr random.

Oracles failing any of these properties are said to be low for Schnorr randomness. We will show the connection between being weak Schnorr engulfing and the Gamma question. We shall also give in Section V a combinatorial characterization of being weakly Schnorr engulfing, by showing its equivalence with another tracing property.

D. Preliminaries on hyperimmune sequences

The following is central notion of computability theory.

Definition II.15. An oracle X is computably dominated if for every function f ≤ T X, there exists a computable function g such that f ≤ g, that is, f (n) ≤ g(n) for every n. An oracle X is of hyperimmune degree, or simply hyperimmune if it is not computably dominated.

Kurtz proved in [START_REF] Kurtz | Randomness and genericity in the degrees of unsolvability[END_REF] that a sequence is hyperimmune iff it Turing computes a weakly-1-generic sequence, that is, a sequence which is in every dense Σ 0 1 subset of 2 ω . We state here a less famous, though interesting, third equivalent notion: Definition II. [START_REF] Martin-Löf | The definition of random sequences[END_REF] For completeness' sake we include a proof of the wellknown equivalence between being of hyperimmune degree and being of i.o.e. degree: Proposition II.17. For a sequence A the following are equivalent:

• A is of hyperimmune degree.

• A is of i.o.e degree.

Proof. If f : ω → ω is an i.o.e. function, then f + 1 is clearly dominated by no computable function. Conversely suppose that g : ω → ω is a function bounded by no computable function. Let {Φ e } e∈ω be an effective list of the partial computable functions and {R e } e∈ω a list of Boolean values initialized to false. At stage n, we define f (n) to be

Φ k (n)[g(n)] where k is the least integer smaller than n such that Φ k (n)[g(n)] halts and such that R k is false (if no such k exists we let f (n) = 0). Then set R k to true. Note first that a function f is i.o.e.
iff it is equal once to every computable function (using the finite-change closure property of the set of computable functions). If Φ e is total then the function n → min{t : Φ e (n)[t] halts} is total and computable, thus it is dominated by g infinitely often. It is easily to check now that f is equal at least once to every computable function.

In this paper, we will be interested in hyperimmune sequences through their i.o.e. characterization. We will also be interested in computably dominated sequences that are random. It is well known that while the set of computably dominated elements has measure 0, some of them are still Schnorr random. It is also well known that each computably dominated Schnorr random is actually Martin-Löf random. So we will refer to them simply as the computably dominated randoms.

III. THE GAMMA VALUES

A. Gamma value of 1/2 and being weakly Schnorr engulfing

The only two known examples of sequences with a Gamma value of 1/2 are the (non-computable ) computably traceable sequences and the computably dominated random sequences [START_REF] Andrews | Asymptotic density, computable traceability, and 1-randomness[END_REF]. They are quite different from each other: While the sequences of first kind are close to computable, the sequences of second kind are far from computable (as they are random).

We identify here a third property of an oracle implied by both, which suffices to get a gamma value of 1/2: being not weakly Schnorr engulfing. As computably traceable sequences are low for Schnorr randomness, they are not weakly Schnorr engulfing (see Theorem II.14). Rupprecht [START_REF] Rupprecht | Relativized Schnorr tests with universal behavior[END_REF] proved that computably dominated random sequences are not weakly Schnorr engulfing. It remains to prove that any non weakly Schnorr engulfing sequences has a gamma value of 1/2 (or of 1 in case it is computable).

k ≤ e -2k d 2 . Clearly ∞ r e -2x d 2 dx ≥ ∞ k=r+1 e -2k d 2 . Since ∞ r e -2x d 2 dx = d 2 e -2r d 2
effectively converges to 0 as r → ∞, the real

k λG k is computable in A. Thus (G k ) k∈N is a Schnorr-Solovay test relative to A as required.
In [START_REF] Andrews | Asymptotic density, computable traceability, and 1-randomness[END_REF] it is proved that any sequence which is computably dominated and random with respect to a computable measure has a Gamma value of 1/2 (unless it is computable, which can happen if it is an atom of the measure). Rupprecht's proof in [START_REF] Rupprecht | Relativized Schnorr tests with universal behavior[END_REF] can be modified to show that no sequence which is computably dominated and random for a computable measure is weakly Schnorr engulfing. It is natural to wonder if there are other sequences with Gamma values of 1/2. In very recent work related to the authors through personal communication, Kjos-Hanssen, Stephan, and Terwijn constructed a sequence which is not weakly Schnorr engulfing, not computably dominated, and not DNC (see e.g. [START_REF] Nies | Computability and randomness, ser. Oxford Logic Guides[END_REF]Ch. 4] for the definition of DNC, which abbreviates "diagonally non-computable").

A non-DNC sequence cannot be random any atomless computable measure. (For instance, use Demuth's result [START_REF] Demuth | Remarks on the structure of tt-degrees based on constructive measure theory[END_REF] that any Martin-Löf random with respect to an atomless computable measure Turing computes a Martin-Löf random with respect to λ, together with the fact that every Martin-Löf random is DNC.) Thus, together with the result of Kjos-Hanssen et al., we have obtained new examples of sequences with a Gamma value of 1/2.

B. Gamma value of 0 and infinite equality

The two known examples of sequences with a Gamma value of 0 are the sequences of hyperimmune degree, and the sequences of PA degree. These latter are the sequences which Turing compute a complete extension of Peano arithmetic. It is well known that they are also the sequences which Turing compute a member of any non-empty Π 0 1 set, uniformly in a code for this set. It is also well known that some of them are computably dominated. These two types of sequences seem to have a Gamma value of 0 for quite different reasons, when one looks at the respective proofs in [START_REF] Andrews | Asymptotic density, computable traceability, and 1-randomness[END_REF]. We identify here a third notion implied by both, which already suffices to get a Gamma value of 0. This notion is a weakening of being i.o.e., where one introduces a bound on the functions.

Definition III.2. Given a computable bound H : ω → ω we say that f : ω → ω is H-infinitely often equal (or H-i.o.e.) if f equals infinitely often every computable function strictly bounded by H. A sequence A is of H-i.o.e. degree if A Turing computes an H-i.o.e. function.

Recall that Proposition II.17 showed that sequences of hyperimmune degree are of i.o.e. degree (with no bound).

Theorem III.3. Any PA degree is H-i.o.e. for any computable bound H of the form 2 H . Proof. For any A of PA degree, there exists an A-computable list {X e } e∈ω of sequences that contains all the computable ones. To see that, recall that A is of PA degree iff A uniformly Turing computes a member of any non-empty Π 0 1 set. Apply that uniformly in a partial computable function Φ to the Π 0

1 set {X : ∀n ∀t [Φ e (n)[t] ↑ or Φ e (n)[t] = X(n)]}.

Now given such a list and any total computable function H, define H (n) =

m<n H(m) (with H (n) = 0). We then simply define the A-computable function f which to n associates the natual number corresponding to the string

X n [H (n),H (n+1)) . If is clear that f is H-i.o.e. where H(n) = 2 H(n) .
We now prove that being of H-i.o.e. degree for H sufficiently fast growing implies having a Gamma value of 0.

Theorem III.4. Let d > 1 be a real. If A is of 2 (d n ) -i.o.e. degree, then Γ(A) = 0.
Proof. We first prove that if A is of 2 (a n ) -i.o.e. degree for a natural number a > 1, then γ(A) ≤ 1/a. Consider a 2 (a n )i.o.e. function f that we can bound without loss of generality by 2 (a n ) . Let H(n) = m<n a m (with H(n) = 0). We define the f -computable set B f such that B f [H(n),H(n+1)) is equal to the string corresponding to the n-th value of f . Consider now any computable sequence X and its bitwise complement X, together with the function f X which to n associates the integer corresponding to the string X [H(n),H(n+1)) . In particular as f is infinitely often equal to f X , there are infinitely many n such that from position H(n) to H(n+1)-1, sequences X and B disagree all the time, which implies

|(B ↔ X) ∩ [0, H(n + 1))| H(n + 1) ≤ H(n) H(n + 1)
And as we have a n = (a-1)H(n)-1 we have H(n+1) = H(n) + (a -1)H(n) -1 and we then have a ratio of at most H(n)/(aH(n) -1) bits which are guessed correctly by X on the initial segment of length H(n + 1). As this happens infinitely often and for every computable sequence X, we then have γ(B) ≤ 1/a and hence γ(A) ≤ 1/a.

We shall now prove that if A is of 2 (d n ) -i.o.e. degree for any real d > 1, then A is of 2 (a n ) -degree for any natural number a > 1. To do so we first argue that if f is H-i.o.e. for some function H, then the function n → f (2n) is H(2n)i.o.e. or the function n → f (2n + 1) is H(2n + 1)-i.o.e. Indeed suppose that some computable function g 1 bounded by H(2n) is such that g 1 (n) = f (2n) for every n and that some computable function g 2 bounded by H(2 + 1) is such that g 2 (n) = f (2n + 1) for every n. Then the computable function g such that g(2n) = g 1 (n) and g(2n + 1) = g 2 (n) is never equal to f , which is a contradiction.

Given a 2 (d n ) -i.o.e. function f and any integer a > 1, let k be such that 2 (d k×n ) ≥ 2 (a n ) (a value k bigger than log d (a) suffices). By repeating the operation described above sufficiently often, we easily see how to compute from f a function f which is 2 (d k×n ) -i.o.e. and hence 2 (a n ) -i.o.e. It follows that Γ(A) = 0.

Rupprecht [START_REF] Rupprecht | Relativized Schnorr tests with universal behavior[END_REF] constructed a sequence which is weakly Schnorr engulfing, computably dominated and not DNC. His proof can be slightly modified to construct a sequence which is for any given computable function H, of 2 H(n) -i.o.e. degree, and both computably dominated and not DNC. As every PA degree is DNC, this provides new examples of sequences with a Gamma value of 0.

C. Gamma values with respect to bases other than 2

We consider here the Gamma value for real numbers expressed in different bases. For an integer b ≥ 2 we denote the space of infinite sequences of elements in {0, . . . , b -1} by b ω . For A ∈ b ω we define the value γ b (A) as before, except we now consider a supremum over computable elements of b ω . The definition of Γ b (A) is also as before, except we now consider an infimum over elements of b ω which are Turing equivalent to A. Finally for a (non rational) real r ∈ R we define Γ b (r) to be Γ b (A) for A ∈ b ω the canonical representation of r in base b.

Let us argue that for any base b ≥ 2 and any real r we have Γ b+1 (r) ≤ Γ b (r). Indeed for every sequence A ∈ b ω we have γ b (A) = γ b+1 (A). As every elements of b ω is also an element of (b + 1) ω , the infimum in the definition of Γ b+1 (r) is done over more elements than in the definition of Γ b (r). In particular if γ 2 (r) = 0 then γ b (r) = 0 for any b ≥ 2.

By straightforward modifications of the proof of Theorem III.1, any sequence A ∈ b ω which is not weakly Schnorr engulfing has a Gamma value of 1/b. What is really of interest here is the proof that any sequence A ∈ b ω such that Γ b (A) > 1/b is computable: The proof of this in [START_REF] Andrews | Asymptotic density, computable traceability, and 1-randomness[END_REF] for the case b = 2 uses a "majority vote" technique, that cannot be used directly for larger bases. This will be made clear in what follows.

Definition III.5. For any sequence A ∈ 2 ω , seen as a subset of ω, we denote by # A c : ω c → ω the function which on x 1 , . . . , x c returns |A ∩ {x 1 , . . . , x c }|.

Note that # A c can take at most c+1 distinct values. Kummer [START_REF] Kummer | A proof of Beigel's cardinality conjecture[END_REF] proved that if A is not computable, one cannot trace # A c by a c.e. trace containing strictly less than c + 1 values. The proof was later simplified by Owings [START_REF] Owings | A cardinality version of Beigel's Nonspeedup Theorem[END_REF]:

Theorem III.6. [Kummer] Let c ≥ 2. Suppose A is an oracle such that # A
c is traceable via some trace {T n } n∈ω , where each T n is c.e. uniformly in n and |T n | ≤ c. Then A is computable.

We will use this in the proof of the following theorem:

Theorem III.7. Let A ∈ b ω . If Γ b (A) > 1/b then A is computable.
Proof. Let A ∈ 2 ω be some binary encoding of A. The sequence # A b-1 belongs to b ω . We perform a majority vote trick as in [START_REF] Andrews | Asymptotic density, computable traceability, and 1-randomness[END_REF], except that we now do not need an absolute majority to win. Consider a sequence B ∈ b ω which encodes each bit of # A b-1 with many repetitions. Formally, we define inductively intervals I n by I 0 = {0} and I n+1 = {k : a n < k ≤ (n + 1) × s n } where a n is the last position in the interval I n and s n the sum of the length of the intervals I 0 to I n . For any k ∈ I n we define B(k) = # A b-1 (n). As B is Turing computable from A, we must have γ b (B) > 1/b, there is then a computable sequence C such that lim inf n |B ↔ C∩[0, n]|/n > 1/b. We now claim that for any n large enough, the percentage of positions k in I n such that C(k) = # A b-1 (n) is strictly greater than 1/b. Suppose otherwise. In particular, for arbitrarily large n we have less than or equal to 1/b positions in I n which are guessed correctly by C. Recall s n-1 is the number of positions before I n . As there are n more positions in I n than in all the previous intervals together, we have at most

s n-1 + (ns n-1 )/b s n-1 + ns n-1 = 1 + n/b 1 + n
many positions guessed correctly. This expression has limit 1/b as n goes to infinity. It then follows that

lim inf n |B ↔ C ∩ [0, n]|/n ≤ 1/b,
which is a contradiction.

Therefore for n large enough, the sequence C must guess in the interval I n strictly more than 1/b of the bits correctly. Also they can be at most b -1 values which are given by C with a ratio strictly bigger than 1/b. By building the computable trace with all these values, we have a trace for # A b-1 , which implies by Theorem III.6 that A, and then A, is computable.

Question III.8. Let r ∈ [0, 1] be non-computable. Do we have for all integers b, c ≥ 2 that Γ b (r) = 1/b iff Γ c (r) = 1/c? As in the setting of computability, Γ h (A) > 1/2 iff A is ∆ 1 1 .
To show this, one follows the same proof as the one of Proposition 1.4. in [START_REF] Andrews | Asymptotic density, computable traceability, and 1-randomness[END_REF], using a "majority vote" technique.

Still as in the setting of computability, and following the same proof as the one of Theorem III.1, if A is not weakly ∆ 1 1 engulfing then Γ h (A) = 1/2. In particular: Theorem III.11.

Every Π 1 1 -random sequence Z satisfies Γ h (Z) = 1/2.
Consequently, for Γ, the situation is quite different in the higher setting: The set of sequences with a Gamma value of 1/2 has measure 1, whereas it has measure 0 in the lower setting.

A notion of being infinitely often equal also makes sense in the higher setting.

Definition III.12. Let H : ω → ω be a ∆ 1 1 bound. A function f : ω → ω is higher H-i.o.e. if it is infinitely often equal to every ∆ 1 1 function bounded by H. A sequence A is of H-i.o.e. hyperdegree if there is some higher H-i.o.e. function which is

∆ 1 1 (A).
It is clear that the proof of Theorem III.4 can be adapted to the higher setting to obtain for any real d > 1 that any A of 2 d n -i.o.e. hyperdegree has a higher Gamma value of 0. In particular, if ω X 1 > ω ck 1 then Γ h (X) = 0. A difference with the lower setting is that we don't have an analogue of the fact that every hyperimmune function computes an infinitely often equal function (see II.17). Kihara [START_REF] Kihara | Higher randomness and lim-sup forcing within and beyond hyperarithmetic[END_REF] has shown that there is a sequence X such that there exists a ∆ 1 1 (X) function f bounded by no ∆ 1 1 function, but such that there exists no ∆ 1 1 (X) infinitely often equal function.

IV. INFINITE EQUALITY

We have seen that both being weakly Schnorr engulfing and the Gamma question are connected to the notion of infinite equality. We study this notion on its own right in some more detail.

It is clear that the two implications of Fig. 1 hold. We should also argue that they are strict. First let us prove the left part of Fig. Theorem IV.1. Suppose A is not c-i.o.e. for some integer c ≥ 2. Then A is computable.

Proof. The function g( x 1 , . . . , x c-1 ) = # A c (x 1 , . . . , x c-1 ) is clearly A-computable and always strictly less than c. Suppose it is always different from some computable function f strictly bounded by c. Then we can capture g (and hence # A c ) with the computable trace {T n } n∈ω such that T n contains every value less than c different from f (n). It follows from Theorem III.6 that A is computable.

By the following proposition, the first implication is strict: there exists a non-computable sequence which is not of Hi.o.e. degree for any order function H. Proposition IV.2. Suppose A computably traceable. For any order function H and any function f ≤ T A, there exists a computable function g < H such that f is always different from g.

Proof. Suppose f < H is Turing below some computably traceable set A. As proved in [START_REF] Terwijn | Algorithmic randomness and lowness[END_REF], for any computable order function H , as slowly growing as we want, the function f can be traced via a computable trace {T n } n∈ω bounded by H . We simply take H < H. To compute g(n) we can then take any value smaller than H(n) and not in T n .

Let us now prove that the second implication is strict: for any order function H there exists a sequence of H(n)-i.o.e. degree such that n 1/H(n) = ∞, but not of H(n)-i.o.e. degree for any order function H such that n 1/H(n) < ∞. This is done via a computably dominated random. For the next proposition, we use the very weak notion of Kurtz randomness, which is defined by not being in any Π 0 1 set of measure 0.

Proposition IV.3. Suppose A Kurtz random. Then A is of H(n)-i.o.e. degree for any order function H = 2 H such that and then for each n we have λ( m≥n [f (m)] Im ) = 1. It follows that if X is Kurtz random there are infintely many n such that X In = f (n), where X In is seen as an integer smaller than 2 |In| . Also this is true for any computable function f , and it then follows that the X-computable function g

n 1/H(n) = ∞. Proof. Consider a computable function f < H. Let H (n) =
(n) = X In is H(n)-i.o.e.
It is easy to prove that if a sequence is of H(n)-i.o.e. degree for an order function H such that n 1/H(n) < ∞, then it is weakly Schnorr engulfing. A more general statement will actually be proved in the next section (see Proposition V.3). It follows that any computably dominated random is of H(n)i.o.e. degree for any order function H such that n 1/H(n) = ∞, but not of H(n)-i.o.e. degree for any computable order function H such that n 1/H(n) < ∞. For instance, such a sequence is of 2 log(n) -i.o.e. degree and not of 22 log(n) -i.o.e. degree.

Question IV.4. Is there some X of 2 n -i.o.e degree that is not of f (n)-i.o.e degree for some computable f (n) >> 2 n ? If yes, can f (n) be taken to be 2 2 n ?

V. WEAKLY SCHNORR ENGULFING AND TRACING

The notions of being weakly Schnorr engulfing and being H-infinitely often equal for H sufficiently fast growing are both related to the Gamma question. At first sight these notions seems unrelated. We give here a combinatorial characterization of being weakly Schnorr engulfing, using traces whose members are bounded by some computable function. This will bring it closer to the notion of being of H-i.o.e. degree for some H. We note that both infinitely equal and the tracing property that turns out to be equivalent to weakly Schnorr engulfing were introduced in search of computability theoretic analogues of similar combinatorial notions from set theory used to analyse cardinal characteristics (see [START_REF] Bartoszyński | Set Theory. On the structure of the real line[END_REF]). Definition V.1. For a computable function H : ω → ω of the form 2 H(n) , we say that a computable trace {T n } n∈ω is a computable H-trace if for each n, elements of T n are strictly bounded by H(n). If furthermore n |T n |/H(n) is finite and computable, the trace {T n } n∈ω is called a small computable H-trace. We say that a function f < H is captured by a computable H-trace {T n } n∈ω if for infinitely many n we have

f (n) ∈ T n .
Note that a computable H-trace can be small only for functions H such that n 1/H(n) < ∞. The idea underlying small traces is to have n λ([T n ] H(n) ) finite and computable, where [T n ] H(n) is the set of strings of length H(n) corresponding to elements of T n .

We shall see that a sequence is weakly Schnorr engulfing iff it computes some small H-trace capturing every computable function bounded by H. In order to conduct the proof, the notion of an interval test (see Definition II.7) plays a key role: still via some coding between strings of length H(n) and integers smaller than H(n), we can view any small computable H-trace as an interval test, and vice-versa. The goal of this section if to prove the following theorem: Theorem V.2. A sequence A is weakly Schnorr engulfing iff for some computable function H, there is an A-computable small H-trace capturing every computable function bounded by H.

We start by proving the easy implication of Theorem V.2: We define an interval test {I n , J n } n∈ω simply by viewing each member of T n as a string σ of length H(n). Formally let H (n) = m<n H(m) (with H (0) = 0). Then each I n is equal to [H (n), H (n + 1)) and each J n is equal to the union of all the sets [σ] [H (n),H (n+1)) for every member of T n encoding a string σ of length H(n).

Proposition V.3 (Theorem V.2 ⇐). If A
It is clear that {I n , J n } n∈ω is an A-computable interval test capturing every computable sequence.

For the converse, the idea is to try to cover any Acomputable Schnorr test by an A-computable interval test. In order to do so we effectivize here some work of Bartoszynski from set theory, but closely related to what we deal with. In particular, some proof of Bartoszynski [START_REF] Bartoszyński | On covering of real line by null sets[END_REF] (see also [START_REF] Bartoszyński | Set Theory. On the structure of the real line[END_REF] Theorem 2.5.11) implies that it is not possible in general to cover a Schnorr test by a single interval test 2 . We can however always cover a Schnorr test by two interval tests, the proof we give here being similar to the one of Theorem 2.5.7 of [3]: Lemma V.4. Given a Schnorr test and a computable sequence of positive rationals {ε n } n∈ω , there exists a computable sequence of integers n 0 < m 0 < n 1 < m 1 < . . . and two computable sequences of clopen sets {J 1,n } n∈ω and {J 2,n } n∈ω such that:

• J 1,k ⊆ 2 [n k ,n k+1 ) and J 2,k ⊆ 2 [m k ,m k+1 ) • λ(J 1,k ) ≤ ε k and λ(J 2,k ) ≤ ε k • Any sequence captured by the Schnorr test is in n m≥n J 1,m or in n m≥n J 2,m .
Furthermore the proposition can be relativized in the obvious way to any oracle A.

Proof. We can suppose without loss generality that each clopen set of Schnorr-Solovay test consists only of one cylinder [σ]. It is then presented by a sequence of stings {σ n } n∈ω . We will define an auxiliary computable sequence of integers p 0 < q 0 < p 1 < q 1 < . . . such that J 1,k will depend on the strings σ i for q k ≤ i < p k+1 . and J 2,k will depend on the strings σ i for p k+1 ≤ i < q k+1 . The idea is the following: once we've put the first p strings σ i in the first component of our first interval test, we remember the maximal length n of those strings, we then put the next q strings in the first component of our second interval test for q sufficiently large such that the sum of the measure of each remaining string is smaller ε×2 -n . In particular we then know that the sum of the measure of each remaining string to which we remove the n first bits, is still small enough. We then repeat the operation, this time making sure that the measure of what remains to put in the second trace is small enough, and so on, alternating everytime between the two traces. Fig. 2 and Fig. 3 illustrate how this works. Fig. 2 illustrates the choice of p k < q k < p k+1 < q k+1 < . . . . Fig. 3 illustrates the choice of n k < m k < n k+1 < m k+1 < . . . . We now give the formal construction. Let n 0 = 0 and p 0 = 0. Let q 0 > 0 be the least integer such that n≥q0 2 -|σn| ≤ ε 0 . Let m 0 be the maximal value between 1 and the length of the longest string σ i for i < q 0 . Suppose p k , n k and q k , m k have been defined. Let us define p k+1 and n k+1 . Let p k+1 > q k be the least integer such that

n≥p k+1 2 -|σn| ≤ 2 -m k ε k
and n k+1 the maximal value between m k + 1 and the length of the longest string σ i for q k ≤ i < p k+1 . Finally let J 1,k be the clopen set equal to the union of [σ i [n k ,n k+1 ) ] [n k ,n k+1 ) for any q k ≤ i < p k+1 . Suppose q k , m k and p k+1 , n k+1 have been defined. Let us define q k+1 and m k+1 . Let q k+1 > p k+1 be the least integer such that n≥q k+1 2 -|σn| ≤ 2 -n k+1 ε k+1 and let m k+1 be the maximal value between n k+1 + 1 and the length of the longest string σ i for p k+1 ≤ i < q k+1 . Finally let J 2,k be the clopen set equal to the union of

[σ i [m k ,m k+1 ) ] [m k ,m k+1 ) for any p k+1 ≤ i < q k+1 .
It is clear that n 0 < m 0 < n 1 < m 1 < . . . is a computable sequence of integers. It follows that J 1,k ⊆ 2 [n k ,n k+1 ) and J 2,k ⊆ 2 [m k ,m k+1 ) are computable clopen sets, uniformly in k. It is also clear that if {σ n } n∈ω contains infinitely many prefixes of X, then X is in n m≥n J 1,m or in n m≥n J 2,m . Also note that for any k we have by choice of q k that i≥q k 2 -|σi| < 2 -n k ε k Note also that by definition of J 1,k we have

λ(J 1,k ) ≤ 2 n k i≥q k 2 -|σi|
It follows that λ(J 1,k ) ≤ ε k . The argument to show λ(J 2,k ) ≤ ε k is similar.

In order to obtain Theorem V.2 we would need to merge the two interval tests covering a Schnorr test into a single interval test. As we mentioned it already, Bartoszynski proved that this is not possible. It would be enough, given an A-Schnorr test n U n covering every computable sequence, to mix the two interval A-Schnorr-Solovay tests obtained with Lemma V.4 into a single interval A-Schnorr-Solovay test that also captures every computable sequence, without necessarily covering n U n . This is what we achieve now, adapting the proof of Theorem 2.5.12 of [START_REF] Bartoszyński | Set Theory. On the structure of the real line[END_REF]. To do so, we need to modify a little bit Lemma V.4, so the sequence n 0 < m 0 < n 1 < m 1 < . . . is not just A-computable (once we relativize the lemma to A) but computable. Also in order to achieve this, we need to restrict ourselves to computably dominated oracles A. Fortunately this is not a problem to prove Theorem V.2 in full generality. Indeed, we argued already in Proposition II.17 that if A is hyperimmune, it is of i.o.e. degree, and then it certainly computes a small H-trace capturing every computable function.

Lemma V.5. Suppose A computably dominated. Given an A-Schnorr test and a computable sequence of positive rational {ε n } n∈ω , there exists a computable sequence of integer n 0 < m 0 < n 1 < m 1 < . . . and A-computable sequences of clopen sets {J 1,n } n∈ω and {J 2,n } n∈ω such that:

• J 1,k ⊆ 2 [n k ,n k+1 ) and J 2,k ⊆ 2 [m k ,m k+1 ) , • λ(J 1,k ) ≤ ε k and λ(J 2,k ) ≤ ε k • Any sequence captured by the A-Schnorr test is in n m≥n J 1,m or in n m≥n J 2,m . Proof. The proof is very similar to the one of Lemma V.4. Let {σ n } n∈ω be a A-Schnorr-Solovay test. Similarly we define the sequence of integer p 0 < q 0 < p 1 < q 1 < . . . such that J 1,k will depend on the strings σ i for q k ≤ i < p k+1 , whereas J 2,k will depend on the strings σ i for p k+1 ≤ i < q k+1 . The difference is that the sequence p 0 < q 0 < p 1 < q 1 < . . . now has to be computable and not just A-computable.

To make those sequences computable, we define F A : ω × Q → ω be the A-computable function which to (p, ε) associates the least integer q > p such that n≥q 2 -|σn| ≤ ε. Note that F A is A-computable because n 2 -|σn| is Acomputable. We also define G A : ω × ω × ω → ω be the Acomputable function which to (p, q, n) associates the maximal value between n + 1 and the length of the longest string σ i for p ≤ i < q. As A is computably dominated, both F A and G A are bounded by some computable functions F and G.

Let n 0 = 0 and p 0 = 0. Let q 0 be the result of computing F (0, ε 0 ). Let m 0 be the result of computing

Theorem III. 1 .

 1 Let A be not weakly Schnorr engulfing. Then Γ(A) ≥ 1/2. Proof. Let d ∈ N. For each B ≤ T A we will define a Schnorr-Solovay test (G k ) k∈N relative to A such that ρ(B ↔ R) ≥ 1/2 -1/d for each sequence R not captured by this test. For each d some computable sequence R passes the test, so this will show that γ(B) ≥ 1/2. Let I k be defined inductively as the set of k consecutive integers following I k-1 : I 0 = ∅, I 1 = {1}, I 2 = {2, 3}, . . . . Given k let G k = {Z : Z(i) = B(i) for a ratio of bits in I k of at least 1/2 + 1/d} which is a clopen set computed uniformly in k from A. By the usual Chernoff bounds we have λG

Fig. 1 .

 1 Fig. 1. Known implications for i.o.e. degrees

  m<n H(m) (with H (0) = 0). Let I n = [H (n), H (n+1)), then we have by hypothesis that n λ([f (n)] In ) = ∞ (where (n) is seen as a string of length I n ). Also as the I n are pariwise disjoint, by Borel-Cantelli we have λ

  . A function f : ω → ω if infinitely often equal (or i.o.e.) if it is equal infinitely often to every computable function. A sequence A is of i.o.e. degree if it Turing computes an i.o.e. function.

  1. It is obvious that being of 2-i.o.e. degree is equivalent to being computable, but for c > 2 some more complicated c-i.o.e. for c ≥ 2 H(n)-i.o.e with H computable order function s.t. n

			1 H(n) = ∞
	not computable	H(n)-i.o.e with H computable
		order function s.t. n	1 H(n) < ∞

  Turing computes a small H-trace capturing every computable function bounded by H, then A is weakly Schnorr engulfing. Proof. Let H = 2 H be computable, together with an A-computable sequence {T n } n∈ω of finite sets, such that n |T n |/H(n) is an A-computable real and such that {T n } n∈ω captures every computable functions bounded by H.

The definition of Kleene is actually more complex in order to ease effective definitions by induction over elements of this set. For our purpose the above definition is enough.

We don't know if every Schnorr test can be covered by a single independent Schnorr-Solovay test

ACKNOWLEDGMENT

The authors would like to thank the Marsden fund of New Zealand, as well as the Science Faculty of the University of Auckland for supporting Monin's research stay in Auckland.

D. The Gamma value in the higher setting

In this section we study a notion analogous to being weakly Schnorr engulfing in the setting of higher computability. Thereafter we discuss a higher version of the Gamma question.

Definition III.9. A sequence A is weakly ∆ 1 1 engulfing if there is a ∆ 1 1 (A) nullset containing every ∆ 1 1 sequence. For an A-computable ordinal α, we write A (α) to denote the α-th jump of A. There are several equivalent ways to concretely define this set, for example via H-sets, as initially done by Kleene and Spector (see [START_REF] Sacks | Higher Recursion Theory, ser. Perspectives in Mathematical Logic[END_REF]), or as the set of codes for A-c.e. binary relations coding for total orders of order-type strictly smaller than some ordinal, as in [START_REF] Monin | Higher computability and randomness[END_REF]. The important point is that A (α) should be a Σ 0 α (A)-complete set. It is well known (see for example [START_REF] Chong | Randomness in the higher setting[END_REF] or Proposition 4.2.5 in [START_REF] Monin | Higher computability and randomness[END_REF]) that if A is ∆ 1 1 -random, then it is GL α for every computable ordinal α, that is, A (α) ≡ T A ⊕ ∅ (α) . Using this, we prove the following theorem about Π 1 1 -random sequences: Theorem III.10. Suppose A is Π 1 1 random. Then A is not weakly ∆ 1 1 engulfing. Proof. Consider a ∆ 1 1 (A) nullset S. As ω A 1 = ω ck 1 we have some computable ordinal α such that S is a Σ 0 α (A) set. By the effective regularity of Lebesgue measure relativized to A, we can approximate S from above by a uniform intersection of

and still because

) uniformly in n. Let e be an index for the Π 0 2 (A⊕∅ (α) ) set n U n . We can now transform e such that for any oracle X we have λ(U X n ) ≤ 2 -n , without changing U n on oracle for which we already have λ(U X n ) ≤ 2 -n (in particular on the oracle A ⊕ ∅ (α) ). For any X consider now the ∆ 1 1 (X) set:

and consider the ∆ 1 1 set:

We claim that N contains every ∆ 1 1 sequence belonging to n U A⊕∅ (α) n and that λ(N ) = 0. If X is ∆ 1 1 and belongs to n U A⊕∅ (α) n we clearly have A ∈ N X . But as N X is ∆ 1 1 and as A is ∆ 1 1 random, we must have λ(N X ) > 0. Thus every

n is also contained in N .

To prove λ(N ) = 0 suffices to prove that N contains no Π 1 1 random sequence. This is clear using the van Lambalgen theorem for Π 1 1 -randomness (Theorem II.11). Suppose that Y is Π 1 1 -random in order to prove Y / ∈ N . Suppose for some Z we have

Then N Y is included in the set of sequences which are not Π 1 1 (Y )-random. As this is a set of measure 0 we have λ(N Y ) = 0. Hence Y is not in N .

We now define counterparts of γ and Γ in the higher setting:

The strings σ i for q k ≤ i < p k+1 are of length n k+1

The strings σ i for p k+1 ≤ i < q k+1 are of length m k+1 Fig. 2. The choice of p k < q k < p k+1 < q k+1 < . . .

G(0, q 0 , 0). Suppose p k , n k and q k , m k have been defined. Let us define p k+1 and n k+1 . Let p k+1 be the result of computing

Suppose q k , m k and p k+1 , n k+1 have been defined. Let us define q k+1 and m k+1 . Let q k+1 be the result of computing F (p k+1 , 2 -n k+1 ε k+1 ) and let m k+1 be the result of computing G(p k+1 , q k+1 , n k+1 ). Finally let J 2,k be the clopen set equal to the union of

) are A-computable clopen sets, uniformly in k. The rest of the verification is as in Lemma V.4.

We are now ready to mix the two interval A-Schnorr-Solovay tests into one interval A-Schnorr-Solovay test capturing every computable sequence: Theorem V.6. Let A be weakly Schnorr engulfing. There exists {I n , J n } n∈ω interval tests relative to A capturing every computable sequence. Moreover, the sequence {I n } n∈ω is computable.

Proof. We already argued the case A not computably dominated. We can then suppose A computably dominated. Fix a decreasing computable sequence of positive rationals {ε n } n∈ω such that n ε n × 2 n+1 < ∞. By the previous lemma, we can assume that we have a computable sequence of integers n 0 < m 0 < n 1 < m 1 < . . . , together with two A-computable sequences of clopen sets {J 1,n } n∈ω and {J 2,n } n∈ω such that:

We are going to create relative to A an interval test {[n k+1 , n k+2 ), R k } k∈ω by mixing {J 1,k } k∈ ω and {J 2,k } k∈ ω . Then assuming that a computable sequence X is not in n m≥n R m we are going to create, using X, another interval A-Schnorr-Solovay test {[m k+1 , n k+2 ), T k } k∈ω such that every computable sequence is necessarily in n m≥n T m . To help the understanding of the construction, the reader can refer to Fig. 4.

For k > 0, Let S 1,k be the union of [σ] [n k ,m k ) for every strings σ of length m k -n k such that there are at least

For k > 0, let S 2,k be the union of [σ] [n k ,m k ) for every string σ of length m k -n k such that there are at least

By the choice of the ε k we clearly have that {[n k+1 , n k+2 ), R k } k∈ω is an interval A-Schnorr-Solovay test. If every computable sequence belongs to n m≥n R m we are done. Otherwise there is a computable sequence X such that X [n k+1 ,n k+2 ) never belongs to R k for any k.

For k > 0 let T 1,k be the union of

Fig. 4. Construction for Theorem V.6

As X must be in n m≥n J 1,m or in n m≥n J 2,m and as no prefix of X belongs to R k for any k, it implies by definition of S 1,k that there are at most

k and by definition of S 2,k+1 that there are at most

In particular the clopen set T k defined to be T 1,k+1 ∪ T 2,k+1 , has measure smaller than 2 -k+1 . Also the set

We now use the fact that the sequence n 0 < m 0 < n 1 < m 1 < . . . is computable in order to prove that n m≥n T m contains every computable sequence. Suppose otherwise, that is, some computable sequence Y is in no set T k for any k. Then the sequence

) is computable. Also we easily see that Z is not in n m≥n J 1,m as otherwise by definition of T 1,k the sequence Y would be captured by {[m k+1 , n k+2 ), T k } k∈ω . Similarly we see that Z is not in n m≥n J 2,m as otherwise by definition of T 2,k the sequence Y would be captured {[m k+1 , n k+2 ), T k } k∈ω . This then contradicts that n m≥n T m does not contain every computable sequence.

Finally we can prove the hard direction of Theorem V.2: Theorem V.2 ⇒. Given a sequence A weakly Schnorr engulfing, we have an interval A-Schnorr-Solovay test {I n , J n } n∈ω capturing every computable sequence with in addition that {I n } n∈ω is computable. We define the computable function H(n) = 2 |In| and the small A-computable H-trace {T n } n∈ω to be the set of each integer encoded by each strings σ such that [σ] In ⊆ J n . Suppose that a computable function f : ω → ω bounded by H is not captured by {T n } n∈ω , then also the computable sequence X such that X In is equal to the string of length |I n | corresponding to f (n) and such that X(i) = 0 for i not in any I n , is not captured by {I n , J n } n∈ω which is a contradiction.

We end the section with an interesting curiosity: In some sense, among the weakly Schnorr engulfing sequences, those which are computably dominated have more capturing power than those which are not. Recall that a sequence is ∆ 0 2 iff it is computable from the halting problem, ∅ , iff it is the pointwise limit of a uniform list of computable sequences. Proposition V.7. Suppose A is a computably dominated, weakly Schnorr engulfing oracle. Then the set of ∆ 0 2 sequences is contained in an A-Schnorr null set.

Proof. We shall prove that any A-Schnorr-Solovay test {I n , J n } n∈ω , with each I n computable uniformly in n, capturing every computable sequence, also captures every ∆ 0 2 sequence. Consider a ∆ 0 2 sequence X, given as the pointwise limit of a list {X s } s∈ω where each X s ∈ 2 ω is computable uniformly in s.

Suppose X is not captured by our A-Schnorr-Solovay test, without loss of generality we can suppose that for every n we have X In / ∈ J n . Let us define the A-computable function f which to the pair (t, n) associate the smallest s ≥ t such that X s In / ∈ J n . As A is computably dominated, the function f is bounded by some computable function g : ω × ω → ω.

We then define a computable sequence Y such that Y In / ∈ J n for each n. Fix some n and compute successive values of g(s, n) for every s starting from 0, until every value X t In is identical for s ≤ t ≤ g(s, n). As the sequence {X t In } t∈ω converges, we know that this will happen eventually. Define then Y In to be X g(s,n) In and Y be 0 on positions which are in no I n .

It is then clear that Y In / ∈ J n for every n, because we have X f (s,n) In / ∈ J n and as s ≤ f (s, n) ≤ g(s, n) we have by the choice of s that X g(s,n) In = X f (s,n) In . Proposition V.7 does not work if A is hyperimmune. We can simply with A = ∅ consider the fact that no A-Schnorr test every A-computable element. It is worth mentioning that the following analogue of Proposition V.7 is true with a similar proof: If f is computably dominated and H-i.o.e., then also f is equal infinitely often to every ∆ 0 2 function bounded by H.