The main result of the paper says that there exists an effectively closed presentation ofZ2which is not the automorphism group of any computable structureM

(1)

GROUP

NOAM GREENBERG, ALEXANDER MELNIKOV, ANDRE NIES, AND DANIEL TURETSKY

Abstract. We apply methods of computable structure theory [AK00, EG00] to study effectively closed subgroups of S∞. The main result of the paper says that there exists an effectively closed presentation ofZ²which is not the automorphism group of any computable structureM. In contrast, we show that every effectively closed discrete group is topologically isomorphic to Aut(M) for some computable structureM. We also prove that there exists an effectively closed compact (thus, profinite) subgroup ofS∞ that has no computable Polish presentation. In contrast, every profinite computable Polish group is topologically isomorphic to an effectively closed subgroup ofS∞. We also look at oligomorphic subgroups ofS∞; we construct a Σ¹₁ oligomorphic group in which the orbit equivalence relation is not uniformly HYP. Our proofs rely on methods of computable analysis, techniques of computable structure theory, elements of higher recursion theory, and the priority method.

The study of computable presentations of topological groups originated in computable field theory [MN79] and was mainly driven by Nerode’s interest in algorithmic aspects of Krull theory. Working under the supervision of Nerode, La Roche [LR81] proved that the correspondence between computable algebraic number field extensions and profinite groups is uniformly effective, in the sense that will be clarified later. Quite interestingly, the algorithmic techniques developed in [LR81] allowed La Roche to prove a theorem on free profinite groups that was new even in the purely algebraic (non-computable) setting, see [Jar74] for the earlier and a weaker purely algebraic result. Based on the work of La Roche, Smith [Smi81, Smi79]

initiated the study of algorithmic presentations of profinite groups in their own right, i.e. not in the context of effective Galois theory.

Such investigations in computable topological groups have not been restricted to profinite groups (see., e.g., [GR93]), but the general theory of computable Polish groups is still in its infancy. Recently there has been an increasing interest in computable aspects of Polish and Banach spaces [PER89, BHW08, Mel13, McN15] and, consequently, in computable Polish groups [MM, Mel]. Many aspects of computable Polish groups are related to computable structure theory [AK00, EG00] and computable Banach space theory [PER89]. Such connections are often quite subtle. For example, it turns out that many classical results of computable structure theory have simpler proofs in the more general setting of a computable Polish group action, see [MM]. On the other hand, the study of Pontryagin Duals of computable Polish abelian groups enjoys applications of non-trivial effective algebraic results, see [Mel]. It seems that effective algebra and computable topological group theory are two adjacent pieces of a bigger puzzle. This paper contributes to the general framework proposed in [Mel13] that is focused on establishing further technical connections between computable structure theory and computable analysis, see also [MN16, MN13, MM, GMKT, McN15, MS, Mel].

Recall that a countably infinite and discrete algebraic structure (e.g., a countable field of characteristic 0) is computable if its domain is ω and its operations and relations are Turing

The first author was partially supported by the Marsden Fund of New Zealand. The second author was partially supported by the Marsden Fund of New Zealand and Massey University Research Fund.

1

(2)

computable. Our main goal is to investigate automorphism groups of computable algebraic structures. For this purpose we introduce a new notion of an effectively closed group. (Our second main result will imply that the notion below is indeed new.)

Definition 0.1. We say that a subgroupGofS∞iseffectively closed (or Π⁰₁for short) if there is an effectively closed subset P of ω^ω such that G =P ∩S∞. An effectively closed presentation, or a Π⁰₁-presentation, of a group is an effectively closed subgroup of S∞ topologically isomorphic to the group.

Automorphism groups of computable algebraic structures are clearly effectively closed. It is well-known that every closed subgroup of S∞ is equal to the automorphism group of some countable algebraic structure upon ω, see [Gao09]. It is natural to ask:

Is every effectively closed group equal to Aut(C) for some computableC?

We will see that the answer to this question is negative, which seems somewhat counterintu- itive. The reader perhaps suspects that the isomorphism type of any effectively closed subgroup ofS∞witnessing the negative answer should be, in some sense, non-trivial. Remarkably, already the two-element cyclic discrete group Z2 has a “bad” effectively closed presentation.

On the other hand, Z2 is (topologically) isomorphic to Aut(C) for some computableC.

Theorem 0.2.

(1) There exists an effectively closed presentation of the two-element cyclic groupZ2 such thatG6= Aut(C) for any computable structureC.

(2) Every effectively closed discrete group is topologically isomorphic to Aut(C) for some computable structureC.

The main difficulty in the proof of Theorem 0.2(1) is nesting strategies on top of each other and not losing the property of being a subgroup ofS∞. We leave open whether Theorem 0.2(2) can be extended to non-compact effectively closed groups.

One could also argue that Definition 0.1 is natural in its own right; effectively closed sets play a significant role in recursion theory, for some recent applications see [BC08, Rei08, HK14]. It could be the case that the notion is actually equivalent to one of the already existing notions restricted to closed subgroups of S∞. We compare Definition 0.1 with the mentioned above notions of acomputable Polish group [MM, Mel] and arecursive profinite group[LR81, Smi81].

(The formal definitions will be given in the preliminaries.) Every recursive profinite group is computable Polish, but there are computable Polish profinite groups with no recursive presentation [Mel]. Recall that the profinite groups are exactly the compact subgroups ofS∞, up to topological isomorphism.

Theorem 0.3.

(1) There exists an effectively closed compact (thus, profinite) subgroup of S∞ that has no computable Polish presentation (therefore, no recursive presentation).

(2) Every profinite computable Polish group is topologically isomorphic to an effectively closed subgroup ofS∞.

In particular, part (1.) of Theorem 0.3 shows that Definition 0.1 gives a new notion, while part (2.) establishes a connection between Definition 0.1 and computable Polish groups. In the preliminaries we will use similar ideas to suggest an extension of Definition 0.1 to groups that are not necessarily totally disconnected. We leave open whether Theorem 0.3(2) can be extended to arbitrary closed subgroups of S∞.

(3)

To finish the paper we look at the class of oligomorphic groups. There are closed subgroups G of S∞ for which for every n there are only finitely many G-orbit equivalence classes ofn- tuples. Oligomorphic groups are the automorphism groups ofℵ₀-categorical structures. These structures are homogenous. Thus, if an effectively closed subgroup Gof S∞ is oligomorphic, and equals Aut(M) for some computable structureM, then∼_Gwill in fact becomputable. We approach the question “how complicated can∼_Gbe for an effectively closed oligomorphocG?”

If we could construct an effectively closed oigomorphic group with ∼_G not computable, we would get another example for our main result Theorem 0.2(1). Oligomorphic groups lie at the other extreme from profinite groups, for which every orbit equivalence class is finite, and our initial hope was that it might perhaps be easier to handle them. Our intuition was wrong, but the effective content of oligomorphic groups turned out to be interesting on its own right.

Note that even for Σ¹₁ groups,∼_Gis Σ¹₁; ifGis oligomorphic, then for eachn, the restriction of ∼_G ton-tuples must be hyperarithmetic. Interetingly enough, this fact lacks uniformity in the following sense.

Theorem 0.4. There is a Σ¹₁, closed oligomorphic subgroup of S∞ for which ∼_G is not hyperarithmetic.

It would be interesting to obtain more information about the effective content of oligomorphic groups; in particular, we leave open whether a Π⁰₁ oligomorphic group can witness Theorem 0.2(1).

The structure of this paper is as follows. The small preliminary Section 1 contains formal definitions, a description of the natural computable Polish presentation of S∞, and an equivalent definition of an effectively closed subgroup ofS∞in terms of this presentation. We arrange proofs according to the used methods. The proof of Theorem 0.3 can be found in Section 2. Section 3 contains the proof of Theorem 0.2(1), and the proofs of Theorem 0.2(2) and Theorem 0.4 are in Section 4, respectively.

1. Preliminaries

Throughout this paper we work in the category of topological groups. We only consider isomorphisms between groups that are both algebraic and topological, i.e., homeomorphisms;

so henceforth “isomorphic” means “topologically isomorphic”.

Definition 1.1. A computable Polish (metric) space is a triple (M, d,(α_i)i∈ω), where (M, d) is a Polish space, the sequence (αi)i∈ωis dense inM, and there exists a uniformly computable procedure which on inputi, j∈ωand∈Q⁺, outputs a rationalrsuch that|d(α_i, α_j)−r|< . The points from the dense computable sequence (αi)i∈ω are called special. A ball with a rational radius and centred in a special point is called basic. Clearly, ω^ω under the usual ultrametric forms a computable Polish space. The basic open balls are the usual clopen neighbourhoods.

SupposeF :X→Yis a map between computable Polish spaces. The mapF iscomputable if there exists a uniform procedure which, on input a basic open B ⊂ Y, lists a set of basic open balls inX whose union is equal toF⁻¹(B). Note that we do not require to list all balls contained inF⁻¹(B). This approach is equivalent to the definition from, e.g., [Mel13]. Observe that the product of two (or more) computable Polish spaces is itself computable Polish. The definition below generalises the old definition of a recursive profinite group [LR81, Smi81] to arbitrary Polish groups.

(4)

Definition 1.2 ([MM]). A computable Polish presentation of a [second-countable Hausdorff]

topological groupGis a computably and completely metrized homeomorphic copy ofGupon which the operations ·and ⁻¹ are computable.

We now discuss the infinite permutation group S∞ ⊂ ω^ω. For two permutations σ and τ of ω, let

D(σ, τ) = d(σ, τ) +d(σ⁻¹, τ⁻¹)

2 ,

where d is the usual ultrametic on ω^ω. The dense computable subset of S∞ is given by permutations of ω with finite support. Then (S∞, D) becomes a computable Polish group which we call the natural Polish presentation ofS∞ for reasons that will be explained shortly.

Recall that a closed subsetCof a computable Polish space iseffectively closed or Π⁰₁if there exists a (Turing) computable enumeration of basic open balls whose union is the complement of C, and recall Definition 0.1 of an effectively closed subgroup ofS∞. It seems quite natural and certainly useful to define a Π⁰₁-subgroup based on the natural computable Polish presentation of S∞ ofω^ω instead. Luckily these notions coincide.

Proposition 1.3. A group G 5 S∞ is effectively closed (according to Definition 0.1) if and only if the domain of G is an effectively closed subset of the natural computable Polish presentation of S∞.

Proof. We prove a bit more. Suppose thatU is a basic open subset of ω^ω. Can we effectively list basic open subsets of (S∞, D) whose union is equal to S∞∩U? Conversely, given a basic openV in (S∞, D), can we list basic open sets whose unionU has the propertyU∩S∞=V? In other words, is the metric D (on S∞) effectively compatible with the usual metric d (on ω^ω)?

Claim 1.4. The metricDdefined above is effectively compatible with the standard ultrametric don ω^ω.

Proof of Claim. Suppose that a sub-basic open subsetU of ω^ω is specified by a finite partial map σ. If σ is not injective, then V =∅. Otherwise, let τ₁, τ₂, . . . be the effective list of all possible extensions ofσ⁻¹ to an injective map with domain a finite initial segment ofω. Then the sequence of pairs (τ_i⁻¹, τi), i= 1,2, . . . corrsponds to a sequence of respective basic open balls in (S∞, D) whose union we set equal toV. Note that each element ofU∩S∞belongs to one of these basic open sets, and thus toV. Conversely, eachf ∈V has a finite approximation that is consistent with the restriction imposed by U.

Now suppose (σ, σ⁻¹) describes a basic open set V in (S∞, D), where σ is a permutation of an initial segment of ω. Then the open set U can be taken equal to the collection of all extensions of σ to an element of ω^ω. The correspondence is clearly effective.

LetP be a closed subset ofω^ω. It follows that we can uniformly pass from the enumeration of P inω^ω to the enumeration of P ∩S∞ in (S∞, D) and back.

The proposition above allows us to extend Definition 0.1 to groups that are not necessarily embeddable intoS∞, but we leave this new notion outside the scope of this article.

Definition 1.5 ([LR81, Smi81]). A recursive presentation of a profinite group P is a uniformly computable inverse system of finite groups, with surjective maps, whose inverse limit is isomorphic to P.

It is known that recursively presented profinite groups are exactly the automorphism groups of computable algebraic number fields over a computable subfield; see [LR81]. As we mentioned above, every recursive profinite group is computable Polish, but there are computable Polish profinite groups with no recursive presentation [Mel].

(5)

2. Effectively closed vs. computable Polish

Proof of Theorem 0.3(1). We construct an effectively closed gubgroup ofS∞that has no computable Polish presentation. We will be using the result below:

Fact 2.1 ([Mel], Cor. 1.8). Every computable Polish presentation of a profinite groupP can be transformed into a 0⁰-computable inverse systemF0 ←F1 ←F2. . ., with surjective maps, whose limit is isomorphic to P.

For a set S of prime numbers let

P_S = Y

p∈S

Zp,

whereZp is the cyclic group of orderp. This group is profinite, as it is the inverse limit of the groups Q

p∈S∩nZp forn < ω.

First we observe that ifP_S has a computable Polish presentation thenS is Σ⁰₂. To see this, given such a presentation of P_S, by Fact 2.1, we produce a 0⁰-computable inverse system rep- resenting the group. By [Mel, Thm.1.9] we can use this to uniformly produce a 0⁰-computable presentation – in the sense of computable structure theory – of the discrete countable group L

p∈SZp, which is the Pontryagin dual of P (see the book [Pon66] for more on Pontryagin’s duality theory). Using the 0⁰-computable presentation of L

p∈SZp we can 0⁰-computably list the prime orders of elements of the group, showing thatS is Σ⁰₂.

So it suffices, given a Π⁰₂-complete setS of primes, to build a computable structureM such that Aut(M) is isomorphic to P_S. The structure M will be a graph consisting of infinitely many disjoint components Cp, one for each primep. Every Cp will have a loop of length p,

x^p₀−x^p₁−. . .−x^p_p−1−x^p₀ and every node in the loop will have a [finite or infinite] chain

x^p_i −c^p_i,1−c^p_i,2−. . .

attached to it. The length of the chain depends on our approximation for the Π⁰₂ predicate for p. Ifp /∈S then this predicate fires forp only finitely many times, say s; in this case, we make the length of the ith chain equal to s+i. The result is a rigid component. If p ∈ S then we make each of the pmany chains infinite. In this case the automorphism group of the component will be isomorphic to Zp; each automorphism is determined by the image of x^p₀, which could be any x^p_i.

Because there is no interaction between the components, Aut(M) ∼=Q

p∈SAut(C_p)∼= P_S. This isomorphism is topological as well, because in both copies, the topology is the product topology where the components Aut(Cp) andZp are discrete. In other words, in both Aut(M) and C_p, the sub-basic clopen sets are determined by stating finitely many values for the

automorphism.

Proof of Theorem 0.3(2). LetP be a computable Polish profinite group. We need to produce a Π⁰₁ presentation of P. By Fact 2.1, there is a 0⁰-recursive presentation ofP. We will use a fully relativised form of the fact below.

Fact 2.2 (LaRoche [LR81]). Every recursively presented profinite group is isomorphic to Gal(K/N), where K is a computably presented algebraic extension of Q, and N is a computable subfield of K.

In fact, N is a fixed field that corresponds to a natural recursive presentation of the free profinite group upon countably many generators, see [LR81]; we do not need this fact.

(6)

Fix a 0⁰-computable fieldKand a 0⁰-computable subfieldN ofKsuch that Aut(K/N)∼=P. Our first step is to obtain a 0⁰-computable relational structureF (with computable underlying set and in a computable language) such that Aut(F) ∼= Aut(K/N) (all isomorphisms are topological); then we obtain a computable structure ˆF such that Aut( ˆF)∼= Aut(F).

To define F, we start withK; by taking a 0⁰-computably isomorphic copy we may assume that N is computable. We name each elements of N by singleton unary predicate and re- place the field operations by their graphs. This adjustment does not change the topological isomorphism type of the automorphism group, so Aut(F)∼=P.

The next step is a version of Marker’s existential extension which preserves the automorphism group.

Proposition 2.3. For any∅⁰-computable relational structureA there is a computable structure B such that Aut(A) and Aut(B) are isomorphic.

Proof. We use the following piece of folklore in computable structure theory.

Fact 2.4(Folklore, e.g., [GK02]). LetSbe a Σ⁰₂set. There exists a uniform procedure which, for each x∈ω, outputs a computable copy of ω ifx∈S, and outputs a computable copy of ω² otherwise.

We assume that the underlying set of A is computable, with a computable language. To define B, fix an n-ary relation of A. For every tuple ¯a ∈ Aⁿ we add a new infinite set C_¯_a^P of elements (these are pairwise disjoint). We link these “blow ups” of tuples by adding the relation y ∈ C_x^P_¯ to B. Next, for every tuple ¯a ∈ Aⁿ we define a linear ordering L^P_¯_a of C_a_¯^P, which is isomorphic to ω if P(¯a) holds in A, and isomorphic to ω² otherwise. We add the relation y1, y2 ∈ C_x_¯^P&y1 <_LP

¯

x y2 to the structre B. It follows from Fact 2.4 that B has a computable copy.

To show that Aut(A) ∼= Aut(B), we notice that both ω and ω² are rigid. Thinking of the underlying set of A as a (computable, definable) subset of B, we observe that every automorphism ofB is determined by its restriction to A, and that every automorphism ofA can be extended to an automorphism ofB. Let Φ : Aut(B)→Aut(A) be this restriction map, Φ(τ) =τ A; it is the required isomorphism. To see that it is topological, in the slightly less immediate direction, we need to check that it is an open map. We take a sub-basic clopen subset of Aut(B), which is the collection of automorphisms of B which extend some finite mapσ. The point is that σ may mention some elements ofB\A. Nonetheless, Φ[σ] is clopen in Aut(A). If q ∈ C_¯_a^P is mapped to some p ∈ C_¯_b^P, then to the image of [σ] we add the restriction that ¯a is mapped to ¯b. Since ω and ω^∗ are rigid, mapping ¯a to ¯b is equivalent to

mapping q top.

This completes the proof of Theorem 0.3(2).

3. Proof of Theorem 0.2

We must construct a Π⁰₁presentation ofZ2which is not equal to Aut(M) for any computable structureM (upon the domain ofω).

Informal idea. We explain the basic idea behind diagonalising against the eth partial computable structure M_e. We work in ω^ω. We start by enumerating a certain neighbourhood into the complement of the presentation, and we say that we “forbid” the neighbourhood. For some basic ¯a→¯bwithin this neighbourhood, we must have ¯a6→¯binM_e, as witnessed by some first-order atomicφ(unlessMe is not total). Then, for some ¯c, it should be the case thatφ(¯c) or¬φ(¯c), and thus necessarily either ¯a6→¯cor ¯c6→¯b. Until this happens the construction will

(7)

proceed in some fixed basic neighbourhood, say ¯a→c. Once we see¯ φevaluated on ¯c(if ever) and says that ¯c6→¯b, then we switch to ¯c→¯band forbid ¯a→¯c. The key here is that we don’t have to instantly forbid the neighbourhoods, butM_emust (unless it is not total). We can put sub-neighbourhoods of a given neighbourhood into our effectively open set one-by-one. Thus, we can delay our decision and do the opposite in the group presentation.

The trickier part is nesting the strategies on top of each other. For that, our construction will proceed only within nested clopen subsets extending ¯x↔y, where ¯¯ xis an initial segment ofω, ¯yis a permutation of ¯x, and the order of this permutation is 2. If we make sure ¯x¯a6→x¯¯b inMe, we can still fix a tuple ¯y¯cand repeat the basic diagonalisation idea, as above. It must be the case that either ¯x¯a6→y¯¯cor ¯y¯c6→x¯¯bis witnessed by some first-orderφ, but both events can be restricted to the neighbourhood ¯x ↔ y. The key here is to choose numbers in ¯¯ c to be very large, so that both neighbourhoods ¯x¯a→y¯¯cor ¯y¯c→x¯¯b contain sub-neighbourhoods isolated by finite permutations of order 2. Then the construction can proceed in one of the two neighbourhoods. With some care we will end up with a copy of Z2. The rest is handled by priority nonsense.

Proof. Fix a computable listing (M_e)e∈ω of all (partial) computable structures upon the domain ω. We construct a Π⁰₁-subgroup P of the standard copy of S∞, and meet the require- ments:

P 6= Aut(M_e), for each e. We will also (globally) ensure thatP ∼=Z2.

We will identify finite injective partial maps and the respective basic neighbourhoods inS∞

determined by their possible extensions.

Definition 3.1. We say that an injective finite map ¯x→y¯isnice if it is a finite permutation of an initial segment ofω and has order 2 (i.e., is an involution). We write ¯x↔y¯to emphasise that the map and its respective basic neighbourhood are nice.

All our diagonalisation strategies will be working within (0,1)↔(1,0). Some of the basic neighbourhoods will be enumerated into the complement of P. If we enumerate a certain neighbourhood into S∞ \P, we say that we forbid the neighbourhood. There will be no interaction between the process of approximating Id_ω and the procedure of approximating the only non-identity element of P.

The basic strategy. We describe the basic diagonalisation strategy, forMe, in isolation. The strategy will be working within a nice σ_e= ¯x↔y.¯

(1) Forbid ¯xn→x(n¯ + 1), where n=lth(¯x). (Note that ¯xn→x(n¯ + 1) will be forbidden by the construction anyway because of its proximity toIdω, so we could simply wait until this happens.)

(2) Wait for Me to separate some ¯x¯a and ¯x¯b extending ¯xn and ¯x(n+ 1) (and having the same length) by a first-order atomic formula φ. Until this happens, if ever, let the construction proceed within the nice neighbourhood ¯xn ↔yn. One-by-one, start¯ forbidding all other sub-neighbourhoodsσe = ¯x ↔y¯of the form ¯xn→yk,¯ k6=n. (If M_eis total but never gives such aφ, then run a back-and-forth argument on extensions of ¯xn and ¯x(n+ 1) to build an automorphism of Me extending ¯xn→x(n¯ + 1).) (3) If such a φ is found, choose ¯c consisting of very large and fresh numbers (and of the

same length as ¯aand ¯b). Proceed as follows:

(a) Extend the finite partial maps ¯x¯a→ y¯¯c and ¯y¯c→ x¯¯b to [finite] permutations of order 2, let N1 and N2 be the respective nice sub-neighbourhoods. Since ¯x↔ y¯ is nice, bothN1 and N2 belong to ¯x↔y. By the choice of ¯¯ c, these permutations

(8)

have not been forbidden yet. Stop the process of forbidding sub-neighbourhoods of ¯x↔y¯initiated at substep (2).

(b) Forbid what is left of ¯xn ↔yn. (Note that weaker priority strategies have been¯ working in this neighbourhood.)

(c) Start forbidding extensions of N2, one-by-one, and let the construction [i.e., all the weaker priority strategies] proceed within N₁. Forbid all basic open neighbourhoods that do not containIdω and are disjoint formN1 and N2.

(4) Wait for M_e to evaluate φ on ¯y¯c, thus witnessing either ¯x¯a 6→ y¯¯c or ¯y¯c 6→ x¯¯b in Aut(Me). If this never happens, the construction will forever stay insideN1.

Case 1: ¯x¯a6→y¯¯cin Aut(M_e), as witnessed byφ. In this case Aut(M_e)∩N₁ =∅. Proceed as above to (eventually) completely forbidN2and keep all weaker priority actions restricted toN₁. We will see that in this case the only non-zero element of P is insideN1.

Case 2: ¯y¯c 6→ x¯¯b in Aut(Me), as witnessed by φ. In this case stop forbidding N2 and forbid what is left ofN1. Choose a nice τ within N2 and restrict the actions of all weaker priority strategies toτ. Similarly to Case 1, the only non-zero element ofP will be contained in τ.

Priority and initialisation. We order the strategies according to the index of the partial computable structure that they are guessing, with smaller indices corresponding to stronger priority. Every time a basic strategy changes its mind about the neighbourhood in which the construction [i.e., the weaker priority strategies]should proceed, we initialise all weaker priority strategies. This is done by picking a new nice neighbourhood σi within the current neighbourhood of the higher priority strategy in which it allows the construction to proceed.

We also make sure that the diameter of the nice neighbourhood σi of the ith strategy is at most 2⁻ⁱ (equivalently, we could require that the domain of the finite nice map contains at least ielements).

Construction. At the beginning of the construction, we will fix a nice basic neighbourhood of Id (say, (0,1) ↔ (0,1)) and some other nice neighbourhood (say, (0,1)↔ (1,0)) disjoint from it. From this point on, we keep forbidding all (not necessarily nice) sub-neighbourhoods of (0,1)↔(0,1) that do not containIdω. We setσ0 = (0,1)↔(1,0).

Verification. We verify some of the key properties of the construction, stage-by-stage.

Claim 3.2. SupposeM_e is total, and ¯xn6→x(n¯ + 1) Aut(M_e) . Then at stage (2) we can find

¯

x¯a and ¯x¯b extending ¯xn and ¯x(n+ 1), respectively, and a first-order atomic formula φ that separates ¯x¯aand ¯x¯b.

Proof of Claim. Suppose such ¯x¯a and ¯x¯b and an atomic φ do not exist. This means that

¯

xn → x(n¯ + 1) can be extended to an automorphism of M_e in a back-and-forth fashion,

contradicting ¯xn6→x(n¯ + 1).

We follow the notation and the terminology used in the construction.

Claim 3.3. Suppose substage (3) is reached. Then there exists a tuple ¯cand nice neighbourhoods N1 and N2 with the desired properties.

Proof of Claim. Recall that only finitely many basic neighbourhoods can be forbidden at every stage of the construction. In particular, only finitely many sub-neighbourhoods ofσe= ¯x↔y¯

(9)

of the form ¯xn → yk,¯ k 6= n, have been enumerated into the complement of the effectively closed set that we build. In particular, we can choose ¯cso that ¯x¯a→y¯¯chas not been forbidden yet. Furthermore, choosing ¯clarge enough we can ensure that both ¯x¯a→y¯¯cand ¯y¯c→x¯¯bcan be extended to finite permutations of order 2 which have not yet been forbidden. This is done by simply setting σ(j) =iifσ(i) =j already, and by declaringσ(k) =kfor all other k.

The importance of choosing ¯c very large in (3) is best illustrated by the simple example below.

Example 3.4. In the notation as above, suppose ¯x¯a → x¯¯b is (0,1,2,7,11) → (0,1,3,2,5).

It extends ¯xn → y(n¯ + 1) which is (0,1,2) → (0,1,3). Fix A, B, C very large, they could be equal to 100,101,102. Consider (0,1,2,7,11) → (1,0,101,102,103) and (1,0,101,102,103) → (0,1,3,2,5). We could extend them to [finite] permutations, say to (0,1,2,7,11,101,102,103) → (1,0,101,102,103,2,7,11) and (1,0,2,3,5,101,102,103) → (0,1,102,101,103,3,2,5), respectively. Recall we were slowly forbidding all neighbourhoods in ¯x ↔ y¯ except for extensions of ¯xn ↔ yn, which is (0,¯ 1,2) → (1,0,2) in this particular case. But 101 is large enough so that (0,1,2,7,11) → (1,0,101,102,103) has not been forbidden yet. The neighbourhood (1,0,2,3,5,101,102,103)→(0,1,102,101,103,3,2,5) has not been forbidden since 102 is large enough. We could easily extend each of these finite maps to permutations of ω 103 of order 2 by making all the rest i < 103 stable under the permutation. This will give us nice extensions of (0,1,2,7,11)→(1,0,101,102,103) and (1,0,101,102,103) → (0,1,3,2,5) which have not been forbidden yet in the construction.

(Note that 2 was accidentally mentioned in the domain of the second permutation, due to the choice of ¯b and ¯a. If it was not the case, we’d have to choose a large fresh D and map 2↔D, just to make sure the extension is not forbidden.) Note that both neighbourhoods are contained within the basic neighbourhood of (0,1)↔(1,0).

Claim 3.5. Suppose the eth strategy is never initialised after stage s. Regardless of the outcome, there exists ans⁰ ≥sand a nice neighbourhoodN^esuch that all the weaker priority strategies (j > e) perform their actions withinN^e.

Proof of Claim. The strategy may never find a φ and a pair of witnesses at substage (2), in which case all weaker priority strategies will work within ¯xn ↔ yn. Otherwise, depending¯ on the outcome, it may either stay within N₁ forever, or it may eventually switch toN₂ and

never change the neighbourhood again.

The basic module of the eth strategy makes sure that no element in the eventually stable neighbourhood N^e can be in Aut(M_e) if M_e is total. Note that, whenever a strategy is initialised it can pick a nice neighbourhood within the part ofS∞that has not been forbidden yet by the higher priority strategies. A straightforward inductive argument shows that for everye, theeth strategy eventually never changes its neighbourhood that it keeps unforbidden, and therefore every strategy is eventually never initialised.

Theeth strategy ensures that some niceτ_edetermined by its stableN^eis the approximation of P \ {Id_ω}. It follows from the construction that all elements of S∞ in (0,1)↔ (0,1) that do not extend τ_e will be eventually forbidden by the e’th strategy. Also, all neighbourhoods outside (0,1)↔(0,1) that do not containIdω will be forbidden in the construction.

Note that the diameter of the nice eventually stable neighbourhoodN_eis at most 2^−e, and Nê+1 ⊂Nê for every e. It follows that the intersection of all these eventually stable Nê is a singleton whose only element is the limit of the ∆⁰₂ sequence (τ_e)e∈ω. The singleton describes the only non-Id element Θ of the Π⁰₁ set P that we end up with. Note that τ_e² =Id_supp(τ_e₎,

for each e. It follows that Θ² =Idω. Thus, P ∼=Z2.

(10)

4. Discrete Π⁰₁-presented groups and oligomorphic groups

We know that Z2 has a complicated Π⁰₁ presentation, but it is also clear that Z2 has a

“nice” presentation equal to Aut(M) for some computableM. This elementary observation is a special case of the more general result: Every discrete Π⁰₁-presented group P is isomorphic to Aut(M) for some computable structureM (Theorem 0.2(2)).

To prove the theorem we analyse the complexity of the orbit equivalence relation. LetGbe a subgroup of S∞. For alln < ω, the groupGacts on the collection ωⁿ ofn-tuples of natural numbers; the resulting orbit equivalence relation ∼_G is defined on ω^<ω by letting ¯a∼_G ¯b if

|¯a|=|¯b|and there is someσ ∈G such thatσ(¯a) = ¯b. We prove the following:

Proposition 4.1. IfGis a discrete, effectively closed subgroup ofS∞, then∼_G is hyperarithmetic.

(This means that for each n, the orbit equivalence relation forn-tuples is hyperarithmetic, uniformly in n.)

Proposition 4.2. If G is an effectively closed subgroup of S∞ and ∼_G is hyperarithmetic, then there is a computable structure M such thatG∼= Aut(M).

Theorem 0.2(2) then follows. Proposition 4.2 is itself the conjunction of two lemmas.

Lemma 4.3. Every closed subgroup G of S∞ is equal to Aut(M) for some structure M computable from ∼_G.

Lemma 4.4. For every hyperarithmetic structureM there is a computable structureN such that Aut(N)∼= Aut(M).

Lemma 4.4 is a generalisation of Proposition 2.3. Say that M is ∆⁰_γ for some computable ordinal γ. We use a generalisation of Fact 2.4 that allows us to code membership in a Σ⁰_α class into an isomorphism type of one of two rigid linear orderings which satisfy the same computable Π_γ infinitary formulas but are separated thereafter. For example, we can produce a copy ofω^γ+1if a Σ⁰_γfact holds, and a copy ofω^γ+2otherwise; for our purposes, the complexity does not need to be tight. See [GK02, Prop.4.12]. The argument then is the same as that of Proposition 2.3.

Lemma 4.3 is an observation that the standard construction of a structure M such that G = Aut(M) does in fact give us a structure computable from ∼_G, see [Gao09]. For any n and for every ∼_G-equivalence class ofn-tuples we define ann-ary relation which defines that class. Closure of Gis used to show that Aut(M)⊆G.

It remains to prove Proposition 4.1.

Proof of Proposition 4.1. Σ¹₁ subsets ofω^ω have the perfect set property in a strongly effective way: if a Σ¹₁ set A does not have a perfect subset then all elements ofA are hyperarithmetic, and so by Spector’s Σ¹₁ bounding, they are all computable from some 0^(γ) for some fixed computable ordinal γ. (See [Sac90], Thm. 6.2.III.)

By Proposition 1.3,G is a Π⁰₂ subset ofω^ω. If all elements of Gare 0^(γ)-computable, then 0^(γ+2)computes a listing of the elements ofG; it then follows that∼_Gis 0^(γ+3)-computable.

This proves Theorem 0.2(2).

Remark 4.5. Note that ifGis an effectively closed discrete group, then it has a hyperarithmetical presentation in the sense of computable structure theory (upon the domain of ω). It is easy to see that this observation gives a characterization of discrete effectively closed groups in terms of hyperarithmetically presented groups;

we outline the proof of the less obvious implication.

Let G be a countable (discrete) group. Use Cayley’s theorem and mapg∈Gto the permutationh7→gh, call itσg. The image is discrete: σg is isolated by the neighbourhoode7→g. This way we obtain anH 5S∞

(11)

(topologically) isomorphic to G which is furthermore arithmetical in the diagram ofG, in particular ∼H is HYP. Lemma 4.3 gives a HYPM such that H ∼=Aut(M), and Lemma 4.4 allows to build a computableN such thatG∼=H∼=Aut(M)∼=Aut(N).

4.1. Proof of Theorem 0.4. Recall that a (closed) oligomorphic group is a (closed) subgroup ofS∞such that for everynthere are only finitely manyG-orbit equivalence classes ofn-tuples.

We construct of Σ¹₁, closed oligomorphic subgroup ofS∞for which∼_Gis not hyperarithmetic.

We work in the admissible structure L_ωck

1 . The idea is to use a cofinal ω-sequence hα_ni inω^ck₁ which is approximated effectively (in the sense ofL_ω^ck

1 -computability) with only finitely many changes to each value. We define the orbit equivalence relation ∼_G rather than G.

We break up classes of n-tuples into two whenever we see a change in the value of α_n; this happens only finitely many times, so at the end we get only finitely many classes ofn-tuples.

The entire equivalence relation is not hyperarithmetic, as we can recover the sequence hα_ni from it. To ensure that the equivalence relation is indeed the orbit equivalence relation of a closed group we need to ensure that it is invariant under permutations, taking subsequences, and has the back-and-forth property. This can be done dynamically, but in fact it is easy to give an explicit definition of the relation.

To the details. For a non-decreasing sequence k = hk_ni of natural numbers define an equivalence relation ∼_k on ω^<ω. For ¯a,¯b ∈ ω^<ω of the same length n, if they are both injective, then we let ¯a∼_k¯bif for everym < nthere are at leastn−m manyi < nsuch that a_i=b_i mod 2^k^m. We then extend this to non-injective tuples in the obvious way.

We first observe:

• ∼_k is an equivalence relation.

• If ¯a∼_k¯bthen for any subsequence ¯a⁰ of ¯aand ¯b⁰ of ¯bchosen in the same way, ¯a⁰∼_k¯b⁰.

• ∼_k is invariant under permutations: for any n-tuples ¯a,¯b and permutationσ of n, if

¯

a∼_k¯bthen ¯a◦σ∼_k¯b◦σ.

• ∼_k has the back and forth property: if ¯a∼_k¯b then for all c < ω there is some d < ω such that ¯ac∼_k¯bd.

• For everyn there are only finitely many∼_k-equivalence classes of n-tuples.

We then let G_k be the collection of all f ∈ S∞ such that for all ¯a and ¯b, if f(¯a) = ¯b then

¯

a ∼_k ¯b. It is a closed subgroup of S∞; the properties just listed ensure that ∼_k is the orbit equivalence relation of the action ofG_k, and that this action is oligomorphic.

We now start to work effectively. Since the Σ1 projectum of L_ωck

1 is ω, there is a ∆2(L_ωck 1 ) increasing sequence hα_ni_n<ω which is cofinal inω₁^ck; see [Sac90] for an excellent exposition of higher recursion theory. In fact,hα_nihas afinite-change approximation (see [BGM17]): there is a ∆1(L_ωck

1 ) array (that is, aL_ωck

1 -computable array)hα_n,sin<ω,s<ω₁^ck such that writingα_n,ωck 1

forα_n, we have:

• For all limit ordinalss≤ω^ck₁ , for all n,α_n,s = limt→sα_n,t; and

• For everyn < ω, there are only finitely many stagess < ω₁^ck such thatαn,s 6=αn,s+1. Given such a sequence we define, for each s≤ω₁^ck,

kn,s= X

m≤n

#{t < s : αm,t6=αm,t+1}.

this defines sequences ks fors ≤ω₁^ck. Our final equivalence relation is ∼_k=∼_k

ωck1

. The fact that we used powers of 2 means that as fort < s, for alln,kn,t≤kn,s, the equivalence relation

(12)

∼_k_n,t refines the equivalence relation∼_k_n,s. This shows that∼_k is Π₁(L_ωck

1 ), that is, it is Σ¹₁. It follows that G_k is Σ¹₁ as well.

The final relation ∼_k=∼_k

ωck1

is not hyperarithmetic: we can see that ω₁^∼^k > ω₁^ck, as in an effective fashion over L_ω^∼k

1 [∼_k] we can recover hα_ni: for alln < ω and s < ω₁^ck, if the number of ∼_k_s-equivalence classes of n-tuples is the same as that of ∼_k, thenαn=αn,s.

References

[AK00] C. Ash and J. Knight. Computable structures and the hyperarithmetical hierarchy, volume 144 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, 2000.

[BC08] Paul Brodhead and Douglas Cenzer. Effectively closed sets and enumerations. Arch. Math. Logic, 46(7-8):565–582, 2008.

[BGM17] Laurent Bienvenu, Noam Greenberg, and Benoit Monin. Continuous higher randomness. J. Math.

Log., 17(1):1750004, 53, 2017.

[BHW08] V. Brattka, P. Hertling, and K. Weihrauch. A tutorial on computable analysis. InNew computational paradigms, pages 425–491. Springer, New York, 2008.

[EG00] Y. Ershov and S. Goncharov.Constructive models. Siberian School of Algebra and Logic. Consultants Bureau, New York, 2000.

[Gao09] Su Gao.Invariant descriptive set theory, volume 293 ofPure and Applied Mathematics (Boca Raton).

CRC Press, Boca Raton, FL, 2009.

[GK02] S. Goncharov and J. Knight. Computable structure and antistructure theorems. Algebra Logika, 41(6):639–681, 757, 2002.

[GMKT] Noam Greenberg, Alexander G. Melnikov, Julia F. Knight, and Daniel Turetsky. Uniform procedures in uncountable structures.To appear.

[GR93] Xiaolin Ge and J. Ian Richards. Computability in unitary representations of compact groups. In Logical methods (Ithaca, NY, 1992), volume 12 ofProgr. Comput. Sci. Appl. Logic, pages 386–421.

Birkh¨auser Boston, Boston, MA, 1993.

[HK14] Kojiro Higuchi and Takayuki Kihara. On effectively closed sets of effective strong measure zero.Ann.

Pure Appl. Logic, 165(9):1445–1469, 2014.

[Jar74] Moshe Jarden. Algebraic extensions of finite corank of Hilbertian fields.Israel J. Math., 18:279–307, 1974.

[LR81] Peter La Roche. Effective Galois theory.J. Symbolic Logic, 46(2):385–392, 1981.

[McN15] Timothy H. McNicholl. A note on the computable categoricity of`^pspaces. InEvolving computability, volume 9136 ofLecture Notes in Comput. Sci., pages 268–275. Springer, Cham, 2015.

[Mel] A. Melnikov. Computable topological groups and Pontryagin duality. To appear in Transactions of The American Mathematical Society.

[Mel13] Alexander G. Melnikov. Computably isometric spaces.J. Symbolic Logic, 78(4):1055–1085, 2013.

[MM] Alexander G. Melnikov and Antonio Montalb´an. Computable polish group actions.To appear.

[MN79] G. Metakides and A. Nerode. Effective content of field theory. Ann. Math. Logic, 17(3):289–320, 1979.

[MN13] Alexander G. Melnikov and Andr´e Nies. The classification problem for compact computable metric spaces. InThe nature of computation, volume 7921 ofLecture Notes in Comput. Sci., pages 320–328.

Springer, Heidelberg, 2013.

[MN16] Alexander G. Melnikov and Keng Meng Ng. Computable structures and operations on the space of continuous functions.Fund. Math., 233(2):101–141, 2016.

[MS] Timothy H. McNicholl and D. M. Stull. The isometry degree of a computable copy ofl^p.To appear.

[PER89] Marian B. Pour-El and J. Ian Richards.Computability in analysis and physics. Perspectives in Math- ematical Logic. Springer-Verlag, Berlin, 1989.

[Pon66] L. S. Pontryagin.Topological groups. Translated from the second Russian edition by Arlen Brown.

Gordon and Breach Science Publishers, Inc., New York-London-Paris, 1966.

[Rei08] Jan Reimann. Effectively closed sets of measures and randomness.Ann. Pure Appl. Logic, 156(1):170–

182, 2008.

[Sac90] Gerald E. Sacks. Higher recursion theory. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1990.

[Smi79] Rick L. Smith.THE THEORY OF PROFINITE GROUPS WITH EFFECTIVE PRESENTATIONS.

ProQuest LLC, Ann Arbor, MI, 1979. Thesis (Ph.D.)–The Pennsylvania State University.

(13)

[Smi81] Rick L. Smith. Effective aspects of profinite groups.J. Symbolic Logic, 46(4):851–863, 1981.