In this paper, we study Hausdorff and Fourier dimension from the point of view of effective descriptive set theory and Type-2 Theory of Effectivity. Working in the hyperspace of compact subsets of X, with or , we characterize the complexity of the family of sets having sufficiently large Hausdorff or Fourier dimension. This, in turn, allows us to show that family of all the closed Salem sets is -complete. One of our main tools is a careful analysis of the effectiveness of a classical theorem of Kaufman. We furthermore compute the Weihrauch degree of the functions computing Hausdorff and Fourier dimension of closed sets.
Hausdorff dimension is probably the most important and well studied among the notions of fractal dimensions, and it plays a central role in analysis and geometric measure theory. In recent work, Jack and Neil Lutz [31] proved a point-to-set principle linking the (classical) Hausdorff dimension of a set with the (relative) effective Hausdorff dimension of its points. If we restrict our attention to singletons, we can characterize the effective Hausdorff dimension of by means of the Kolmogorov complexity of ξ [32], which establishes a surprising connection between two (apparently) very distant notions.
A powerful tool to study the Hausdorff dimension of Borel subsets of is provided by the Fourier transform. Indeed, Frostman’s lemma draws an interesting connection between the Hausdorff dimension of a set and the decay of the Fourier transform of a (probability) measure supported on it. This leads to the notion of Fourier dimension. It is known that the Fourier dimension of a Borel set cannot exceed its Hausdorff dimension.
This work is part of a long-term effort, involving many researchers, aimed at exploring the recursion-theoretic properties of the Fourier dimension. While no point-to-set principles can hold for the Fourier dimension (in such a generality), analyzing the complexity of the Fourier dimension in simpler cases can shed light on the general behavior of the Fourier dimension itself (up to now, still not deeply understood).
Salem sets arise naturally when combining geometric measure theory and harmonic analysis. A set is called Salem iff , where and denote the Hausdorff and the Fourier dimension respectively. Explicit (i.e. non-random) Salem sets are not easy to build. A classic example comes from the theory of Diophantine approximation of real numbers: for every , the set of α-well approximable numbers is Salem with dimension . The computation of its Hausdorff dimension is due to Jarník [26] and Besicovitch [3], while the result on its Fourier dimension is due to Kaufman [27]. The reader is referred to [4] or [49] for detailed proofs of Kaufman’s theorem. The construction presented in [49] will play a central role in the rest of this work.
As a consequence of a result of Gatesoupe [20], subsets of obtained by the rotation of a 1-dimensional Salem sets with dimension α (having at least two points) are Salem of dimension , and this provides a simple way for building Salem sets of dimension at least in .
Explicit examples of non-Salem sets are the symmetric Cantor sets with dissection ratio for : they are known to have null Fourier dimension and Hausdorff dimension (see [34, Sec. 4.10] and [35, Thm. 8.1]). Every subset of a n-dimensional hyperplane is a 0-Fourier dimensional subset of when , while it can have any Hausdorff dimension up to n.
In recent work [33], we studied the complexity, from the point of view of classical descriptive set theory, of a number of relations involving the Hausdorff and the Fourier dimension. In particular, we studied the conditions , , , , “A is Salem”, when and A is a closed subset of , , and . In particular, we proved that having Hausdorff/Fourier dimension and are, respectively, a -complete and a -complete conditions. Similarly, we showed that the family of Salem sets is -complete. In this paper we explore the same conditions from the point of view of effective descriptive set theory and Type-2 Theory of Effectivity (TTE). Notice that in [23] the authors showed that the sets of elements of the Cantor space having (respectively) effective Hausdorff dimension and , where α is a -computable real, are (respectively) and .
The paper is organized as follows. After briefly introducing the relevant background notions (Section 2), we present some results on the lightface structure of the hyperspaces of closed and compact sets (Section 3) and on computable measure theory (Section 4) that will be needed for the main results. In particular, we show that the hyperspace of compact subsets of a computably compact space is computably compact (Lemma 3.5), the hyperspace of closed subsets of the Euclidean space is computably compact (Proposition 3.6) and that the space of probability measures on a computably compact space is computably compact (Theorem 4.1). Section 5 is devoted to the proof of an effective version of the above mentioned theorem by Kaufman, stated in Theorem 5.6. Section 6 contains the main results on the effective complexity of the conditions mentioned above, and can be summarized as follows: if or then,
where is the hyperspace of compact subsets of X (endowed with the canonical lightface structure induced by the Hausdorff metric, introduced in Section 3). The complexities remain the same if we consider the hyperspace of closed sets. In particular, the fact that the family of closed Salem subsets of is -complete answers a question asked by Slaman during the IMS Graduate Summer School in Logic, held in Singapore in 2018. In Section 7, we use our results to characterize the Weihrauch degree of the maps computing the Hausdorff and the Fourier dimension of a closed set, in particular answering a question raised by Fouché ([9]) and Pauly.
Background
Throughout the paper, we will use to denote the open ball with center x and radius r. We also fix a computable enumeration of .
Hausdorff and Fourier dimension
Let us briefly introduce the relevant notions from geometric measure theory. For a more thorough presentation the reader is referred to [18].
Let be a separable metric space and let . We denote the diameter of A by . For every , we define
where is a δ-cover of A if and for each . The function is called s-dimensional Hausdorff measure. The Hausdorff dimension of A is defined as
It is well-known that, as a consequence of Frostman’s lemma (see [34, Thm. 8.8]), the Hausdorff dimension of a Borel subset of can be equivalently written as
where is the set of Borel probability measures supported on A (in other words, for Borel sets Hausdorff and capacitary dimensions coincide).
This characterization suggests the possibility to use the tools of harmonic analysis to obtain estimates on the Hausdorff dimension. We can define the Fourier transform of a probability measure as the function
where denotes scalar product. The Fourier dimension of is then defined as
It is known that, for every Borel , (see [34, Chap. 12]). If then A is called Salem set. We denote the collection of Salem subsets of with .
For background notions on the Fourier transform the reader is referred to [46]. For its applications to geometric measure theory see [35].
We notice that the Hausdorff dimension is
countably stable:
for every α-Hölder continuous map we have [18, Prop. 3.3].
In particular, the inclusion map , with , preserves the Hausdorff dimension.
None of the above properties hold, in full generality, for the Fourier dimension. In fact, it is not even finitely stable [16, Sec. 1.3] and does not behave well under Hölder continuous transformations [17, Sec. 8]. Moreover, it is sensitive to the choice of the ambient space: as mentioned, every has null Fourier dimension when seen as a subset of with . However, some regularity properties hold if we restrict our attention to special cases. We mention, in particular, that the Fourier dimension is inner regular for compact sets, i.e.
and countably stable for closed sets [16, Prop. 5], i.e. for every countable family of closed subsets of we have
Moreover, the Fourier dimension is invariant under similarities or affine (invertible) transformations (this is a simple consequence of the properties of the Fourier transform).
Computability on represented spaces
In this paper, we use the standard approach of Type-2 Theory of Effectivity (TTE) to define a notion of computability on a wide range of spaces. We now introduce the main definitions, for a more detailed presentation the reader is referred to [38,48].
Let be the Baire space and let be the set of finite sequences of natural numbers. Let also be the Cantor space and be the set of finite binary sequences. Both and are endowed with the usual product topology. We sometimes describe a string by a list of its elements. E.g. we write for the string . Similarly, we can describe an infinite string by , when it is clear from the context how to continue the sequence. We write for the empty sequence. We write for the length of σ and for the concatenation of the strings σ and τ. We will use the symbol to denote a fixed computable bijection with computable inverse. It is often convenient to write in place of . In the literature, the symbol is often used to denote also the join between two (of the same length, finite or infinite) strings. With a (relatively) small abuse of notation, if x, y are two strings of the same length we will write1
The exact details of the definition of the join are often not relevant. E.g. a common way to define the join of is letting and .
and .
A represented space is a pair where X is a set and is a partial surjection called representation map. For every , the elements of are called -names for x (we just say names if there is no ambiguity on the representation map).
We can exploit the classical notion of computability on (see [48] for an introduction) to induce a notion of computability on any represented space: let f be a partial multi-valued function between the represented spaces and (in symbols ). A realizer for f is a partial function such that, for every , we have that . We say that f is -computable if it has a computable realizer (again, we just say computable if the representation maps are clear from the context). We say that f is realizer-continuous if it has a continuous realizer. The set of realizer-continuous partial functions between represented spaces is a represented space itself ([48, Sec. 2.3]).
As the notation suggests, the induced notion of computability is intrinsically tied to the choice of the representation maps. If δ and are two representation maps for X, we say that δ is (topologically) reducible to , and we write (resp. ), if there is a (continuous) computable map s.t. for every . The maps δ and are called (topologically) equivalent, written (resp. ), if and (resp. and ).
Often times, spaces are naturally endowed with some canonical topology, and it would be desirable that the topological structure agrees with the computational one, i.e. that the notions of continuity and realizer-continuity agree. We will consider (and mainly focus our attention on) the so-called admissible representations, which intuitively are those that satisfy this requirement.
Let be a topological space. A representation map of X is called admissible w.r.t. if it is continuous and, for every other continuous representation map δ on X, we have .
In other words, an admissible representation of X is -maximal among the continuous representation of X. We will just say that a representation is admissible if there is no ambiguity on the topology.
Let,be admissibly represented second-countablespaces. For every,
In particular, whenever X and Y are admissibly represented, the space of continuous functions from X to Y is a represented space.
Clearly, the very existence of an admissible representation for the topological space depends on the topology itself: a family of subsets of X is called a pseudobase iff for every open set , every and every sequence converging to x,
A topological spaceadmits an admissible representationiff it isand admits a countable pseudobase.
Representations on (hyper)spaces
While (the proof of) Theorem 2.3 provides an explicit definition of an admissible representation for a wide variety of spaces, in many practical situations this is not the representation map we endow our space with. Observe that, while all admissible representation maps are topologically equivalent, they do not necessarily induce the same notions of computability, i.e. they may not be (computably) equivalent.
Let be a separable metric space, where is the distance function and is an enumeration of a dense subset of X. The Cauchy representation on X is the map defined as
where is the set of rapidly converging sequences. The Cauchy representation is the “canonical” representation map for separable metric spaces. It is equivalent to the representation map that names via any s.t. .
Recall that is a canonical computable enumeration of the rationals. We say that X is a computable metric space if the set
is computably enumerable, i.e. if the restriction of the distance function to is computable. We can always assume that, if X is infinite, α is an injective map (i.e. every element of the dense subset of X has a unique index). Indeed, for every infinite computable metric space there is an injective subsequence β of α s.t. the spaces and are computably homeomorphic (i.e. there is a computable bijection with computable inverse) [21, Thm. 2.9].
Let be a second-countable topological space. We say that is an effective (topological) space if is an enumeration of a basis for s.t. there is a computable function s.t.
Every effective topological space can be endowed with the structure of represented space by defining an (admissible) representation map that names a point via an enumeration of the set . Notice that a computable metric space can be seen as an effective space by considering the “standard” enumeration of the basis for X (i.e. ). In this case, the Cauchy representation on X is equivalent to the representation .
For every topological space Z, the family of Borel subsets of Z can be stratified in a hierarchy, called the Borel hierarchy. The levels of this hierarchy are defined by transfinite recursion on , where is the first uncountable ordinal. We denote by and respectively the family of the open and the closed subsets of Z. For every we define:
,
.
Moreover, for every ξ, we define . In particular, is the family of clopen subsets of Y. The families and are often written resp. and . It is known that , where denotes the family of Borel subsets of Z. We will omit the dependency from the space if there is no ambiguity.
For metric spaces (in fact, for Hausdorff spaces), the definition of the pointclass can be simplified letting
Let W and Z be topological spaces and let , . We say that A is Wadge reducible to B if there is a continuous function s.t.
Let be a Borel class and assume that Z is Polish. We say that B is -hard if for every . If B is -hard and then we say that B is -complete.
For every effective second-countable space , we say that is effectively open if for some computable function . The set of effectively open subsets of Y is denoted by . In other words, an effective open set is a computable union of basic open sets. The complement of an effectively open set is called effectively closed and the family of all effectively closed subsets of Y is denoted by .
Notice that sets can be indexed using the code for a computable function defining them. In other words, there is a canonical indexing of the sets. This allows us to define
;
.
We can inductively define the (Kleene’s) arithmetical hierarchy, also called lightface hierarchy, by letting be an effective indexing of the sets and defining
;
.
The lightface hierarchy can be relativized in a straightforward manner, by defining, for ,
and then, define the classes , , accordingly. It is important to mention that the lightface classes are universal for their corresponding boldface ones. Formally, if Γ is a lightface class among , and is the corresponding boldface pointclass, then
see e.g. [36, Thm. 3E.4].
For every effective space and every , we can define the represented spaces , , inductively by:
;
;
;
, iff and .
We notice that the sets are exactly those having a computable -name (and similarly for , ).
If Y and are effective spaces, we say that is effectively Wadge reducible to , and write , if there is a recursive functional s.t. iff . Let Γ be a lightface pointclass as above and assume that Y is an effective Polish space. We say that B is Γ-hard if for every . If B is Γ-hard and then we say that B is Γ-complete. Standard examples2
The standard proofs showing that the listed sets are -complete for their respective class are, in fact, effective. See [28, Sec. 23.A].
of Γ-complete sets are the following:
where and mean respectively and .
While often there is a natural choice for an effective basis, when working with represented spaces we can exploit the representation map to induce a lightface structure in a canonical way.
Let us introduce the Sierpiński space. The space is endowed with the topology . This space is represented as follows: the only name for 0 is the string that is constantly 0, while every other string in is a name for 1.
We can notice that, if is a represented space and is the final topology on X induced by , then the open sets are exactly the subsets of X s.t. the characteristic function is realizer-continuous (see also [38, Sec. 4]). In particular, we can represent an open set using a name for . This, in turn, allows us to represent a closed set (in the final topology on X) via a name for its complement. Using the jumps of the Sierpiński space, we can obtain an analogous characterization for the pointclasses ([40, Sec. III and Prop. 30], see also [14]).
In other words, using the Sierpiński space, we can define a representation map for the sets , , , for any represented space . For separable metric spaces, the two representations are equivalent (see [5,38]).
The same ideas allow us to induce a lightface structure on any represented space. Indeed, for a represented space , we can define the effectively open sets as follows:
The Sierpiński space is, thus, useful to obtain a notion of semi-decidability in represented spaces. For a more detailed discussion the reader is referred to [12,39,40].
The hyperspaces of closed and compact sets
The hyperspaces of closed and compact sets will play a crucial role in this paper. The space of closed subsets of a topological space X is usually endowed with a number of topologies we now recall. For a more thorough presentation, the reader is referred to [2,30].
Let us define
The topology having as a prebase is called upper topology or upper Vietoris topology, while the topology having as a prebase is called lower topology or lower Vietoris topology ([30, Def. 1.3.1 and def. 1.3.2]). The Vietoris topology is the topology having as a prebase the family .
We also consider the collection defined as
where is the family of all compact subsets of X. The family is a prebase for the topology on called upper Fell topology. We define the Fell topology on as the topology having as a prebase the set . For this reason, the lower Vietoris topology is also called lower Fell topology.
If we restrict our attention to compact subsets of X, we can define the topological space obtained by endowing the family of compact subsets of X with the topology induced by the Vietoris topology on . This choice is motivated by the following observation: if X is a metric space with distance d, we can define the Hausdorff metric on as follows:
where . It is known that the Hausdorff metric is compatible with the Vietoris topology on ([28, Ex. 4.21]) and that if X is Polish then so is ([28, Thm. 4.22]).
We notice that fails to be paracompact, and hence metrizable, if X is not compact ([29, Thm. 2]). The Fell topology is the preferred choice when working with closed sets, since if X is Polish and locally compact then is a Polish compact space and its Borel space is exactly the Effros-Borel space ([28, Ex. 12.7]). If X is compact then the Fell and the Vietoris topologies coincide, and the same holds for the upper Fell and the upper Vietoris topologies.
In the following, let be a computable metric space. We already mentioned that the set can be seen as a represented space, where a name for a closed set is a list of basic open balls that exhaust the complement. This representation map is often3
see [7, Def. 3.4], [8, Sec. 2]. In [10] it is introduced in Def. 3.5(1) and is denoted .
denoted , and -names provide negative information on the set they represent. The represented space is often denoted or in the literature.
In contrast, the positive information representation for closed sets is defined as
where is the canonical enumeration of basic open balls of X. In other words, a -name for F is a list of all the basic open sets that intersect F ([7, Def. 3.1], it is denoted in [10, Def. 3.1(1)]). The elements of the represented space are called closed overt sets, and the space is sometimes denoted in the literature, e.g. [15, Sec. 2].
We denote the join of both positive and negative information representations with ψ. Formally
This is denoted in [7, Def. 3.1] and in [10, Def. 3.1].
It is known that the representation maps , , and ψ are admissible respectively for the upper Fell, lower Fell, and Fell topology on [7, Sec. 3].
Let X be a computable metric space. The following operations are computable:
, for.
.
Notice however that is in general not computable, and not even continuous (see e.g. [28, Ex. 4.29(viii)]). For a more precise analysis of the complexity of the intersection operator see [7, Thm. 7.1].
Let us introduce the following notion:
A compact subset K of a computable metric space is called co-c.e. compact if
is computably enumerable. We say that K is computably compact if it is co-c.e. compact and there exists a computable dense sequence in K.
We say that a sequence is uniformly co-c.e. compact if each is co-c.e. compact in a computable metric space and the set
is computably enumerable, where is the k-th basic open ball in . In other words, the sequence is uniformly co-c.e. compact if there is a single computable function witnessing that each is co-c.e. compact.
The notions of co-c.e. compact and computably compact are standard notions in computable analysis (see e.g. [8, Def. 2.10]). Notice that being co-c.e. compact implies being and that every subset of a co-c.e. compact space is co-c.e. compact. Clearly a computable metric space is co-c.e. compact iff it is computably compact. Moreover, if K is co-c.e. compact (resp. computably compact) and is computable and surjective, then Y is co-c.e. compact (resp. computably compact) as well (see [38, Prop. 5.3]). Several equivalent conditions to being computably compact are listed in [38, Prop. 5.2]. The notions of co-c.e. compact and computably compact can be extended in a straightforward way to effective spaces.
We also mention the following simple lemma:
If X is co-c.e. compact then so is.
The fact that the finite product of co-c.e. compact spaces is co-c.e. compact follows from [38, Prop. 5.4]. To prove that is co-c.e. compact, recall that an open set in is of the type , where each is open in X and only for finitely many indexes. Such an open set is canonically represented via (a name for) a finite sequence with the understanding that for every .
Let be a finite sequence of open subsets of , where is represented by . This sequence trivially induces a finite sequence of open subsets of , where : for every i and every , let and define . The sequence covers iff covers . The claim follows from the fact that the sets are uniformly co-c.e. compact. □
Since , we can represent the compact subsets of X using the subspace representation induced by the representation we put on . At the same time, we mentioned that is compatible with the Hausdorff metric. Letting β be an enumeration of the finite subsets of , the space is a computable metric space (as the finite subsets of are a dense subset of ). In particular, can be (canonically) endowed with the Cauchy representation induced by and β. The Cauchy representation for the hyperspace of non-empty compact subset of the Euclidean space was studied in [11] under the name , and then extended to generic computable metric spaces in [10], where the symbol was used.
Two additional representations maps for that are used in the literature (see e.g. [6, Sec. 4]) are the maps and κ: the former names a compact set K via a list of all finite covers of K with basic open balls, while κ-names have the additional requirement that all basic balls in each cover have to intersect K. The compact sets having computable -names (resp. κ-names) are exactly the co-c.e. compact (resp. computably compact) sets. The representation maps and κ have been studied in [10,11] under the names and respectively.
Let X be a co-c.e. compact subspace of the Euclidean space, whereis the Euclidean distance andis an enumeration of. Letbe the restriction ofto names of compact subsets of X, and similarly let. The following holds on:
;
.
The equivalence follows from [11, Thm. 4.6]. Precisely, the representation names a compact set K via a -name of K and the index of a ball B s.t. ([11, Def. 4.1]). If X is compact then the equivalence is straightforward.
The equivalence follows from [11, Cor. 4.7] using the fact that for a compact X. Indeed, a -name of a compact set K is a -name of K and the index of a ball B s.t. ([11, Def. 4.1]).
In [11, Thm. 4.10], the Cauchy representation (i.e. the restriction of to names of non-empty compact sets) has been proven equivalent to the restriction of to names of non-empty compact sets. We now explicitly show that (i.e. the empty set is not problematic if X is co-c.e. compact).
Recall that for every non-empty closed G, .
:
As mentioned after the definition of Cauchy representation, we can think of a -name p for F as a list of (indexes for) basic open balls w.r.t. the Hausdorff metric s.t. all the balls contain F and the radius of is . Since the empty set is isolated in , it is enough to consider . Indeed, without loss of generality we can assume that we can computably tell whether is centered on ∅ (e.g. we can assume that the empty set has a unique index in the list of dense subsets of ). If is centered on ∅ then (as ). Otherwise , and we can use and .
:
Let be a -name for F, where p is a negative information name and q is a positive information name for F. If then p is a list of basic open balls that cover X. On the other hand, if then q eventually lists some basic open ball (in X) that intersects F (q is allowed not to produce any information at a given stage). In other words, we wait for some sufficiently large n so that either covers X or q commits to some open ball at stage n. This allows us to determine whether F is empty or not. If we can trivially compute a sequence of basic open balls (in ) centered on ∅ with rapidly decreasing radii. Otherwise, as in the previous reduction, we can use and to produce a -name for F.
□
For the sake of readability, we adopt the following notation:
is the hyperspace of closed subsets of X, endowed with the upper Fell topology and the negative representation ;
is the hyperspace of closed subsets of X, endowed with the Fell topology and the full representation ψ;
is the hyperspace of compact subsets of X, endowed with the upper Fell topology and the negative representation restricted to names of compact sets, i.e. ;
is the hyperspace of compact subsets of X, endowed with the Vietoris topology and the full representation restricted to names of compact sets, i.e. .
The following lemma is the effective counterpart of [28, Thm. 4.26].
Ifis computably compact then so is.
Recall that a basic open ball in is a set of the type , where β is the fixed enumeration of the finite subsets of and is the canonical enumeration of . In particular, if then
Let be a finite sequence of basic open balls in . We want to describe a c.e. procedure to check whether covers . For the sake of readability, let us define and for every . We first check if for some (any ball with radius covers , and in this case we can give a positive answer) or if there is s.t. (recall that the empty set is isolated, and a ball with radius covers ∅ iff it is centered on it, hence if such a j is missing we give a negative answer). Since these two conditions are computable, to prove the result it is enough to show that there is a c.e. procedure to determine if a finite sequence with and for all covers .
We now define a c.e. subtree T of (where k is the length of the fixed finite sequence of basic open balls) where each string is labeled with a compact subset of X. A string is in T iff
where denotes the prefix of σ of length . The string σ is labeled with .
Notice that, since X is computably compact, then so are all the sets . In fact, they are uniformly computably compact: given a finite sequence of open balls, we can compute the index of a computable functional witnessing that is computably compact. This follows from
In particular, this shows that the condition (and hence ) is computably enumerable.
We claim that
This implies the computable compactness of , as the condition on the right is computably enumerable ( is equivalent to being covered by the empty set and the quantification on σ is bounded because T is computably finitely branching).
For the right-to-left direction, assume that there is a non-empty . We show that there is a leaf σ s.t. . We proceed iteratively as follows, defining a list of sequences s.t. : let . At stage , we look for some unmarked (i.e. not selected in any previous stage) s.t. . If such a choice is possible then, since and , there is s.t. . In particular, , hence letting , we have , which implies that . We then mark as visited and go to the next stage. If there is no that satisfies the requirements then is a leaf for T but (as ). Notice that looking for some unmarked guarantees that no choice of is possible at stage .
Let us now prove the left-to-right implication. Assume that is a leaf for T. Notice that, for each and each , if then for every , , and hence . In particular, if then, for every , . Moreover, since σ is a leaf, there is no pair s.t. , which implies that . □
is computably compact.
We show that there is a computable surjection , and the claim will follow using Lemma 3.5 and the remarks following Definition 3.2. Fix a computable homeomorphism and define
It is easy to see that, for , is closed. Moreover, f is surjective: for every , is closed in the relative topology of . If we denote with G its closure w.r.t. the relative topology of , we have that , hence, in particular, .
Finally, we show that f is computable. Recall that both and are admissibly represented with the full information representation. Let be a name for . To compute a negative information name for from p, notice that, since is a computable homeomorphism (and, in particular, it is a total computable surjection), as mentioned in the proof of [6, Prop. 3.7] we have that the map . Intuitively: for every basic open we can computably list a sequence of basic open balls of exhausting . On the other hand, notice that a basic open ball B of intersects iff there is s.t. (this follows from the fact that φ is a homeomorphism). In particular, to produce a positive information name for , we list whenever we find some i s.t. (which is a computable condition). □
Recall that, if X is not compact, then the hyperspace of closed subsets X endowed with the Vietoris topology is not metrizable. We now show that it is not even admissibly represented.
Letdenote the hyperspace of closed subsets of X endowed with the upper Vietoris topology. The space(and hence) does not have a countable pseudobase. In particular, it is not second-countable and it is not admissibly represented.
Fix a countable sequence of subsets of . To show that is not a pseudobase we build a closed set F and an open set which contains F s.t. for every i, either or . We define , where is a strictly increasing sequence iteratively defined as follows: for each i, let be the smallest integer greater than for every (if we let ). Choose an unbounded . If there is none we just define . Let and choose s.t. . In particular .
Notice that, for every , , hence the sequence does not have accumulation points. In particular, the set is closed and unbounded. Fix ε sufficiently small, e.g. , and define the open set and .
The open set and the closed set F witness the fact that is not a pseudobase. Indeed, for every i, either every is bounded (and hence ), or the set defined above witnesses that (as by construction ).
This implies also that is not second-countable, as every base is a pseudobase. The fact that it is not admissibly represented follows by Theorem 2.3. The claim generalizes to as every pseudobase of induces a pseudobase on by projection. □
The space(and hence) does not have a countable pseudobase. In particular, it is not second-countable and it is not admissibly represented.
This follows from the proof of Proposition 3.7. Indeed, the above proof only uses a closed set and an open set to show that no countable subfamily of is a pseudobase. Since the upper Vietoris topology is coarser than the Vietoris topology, the same argument applies to . The claim would not follow immediately if, in the proof of Proposition 3.7 we would have exploited a convergent sequence to F, as convergence is a weaker notion in the upper Vietoris topology. □
We conclude this section with the effective counterpart of [1, Lem. 1.3]:
Let X, Y be computable metric spaces. If Y is co-c.e. compact then, for every,. Ifwhere the sequenceis uniformly co-c.e. compact, then for every,.
Let us first assume that Y is co-c.e. compact and let . Let be a computable map s.t. . Notice that iff the preimage of via the projection map is contained in the complement of F.
Let be a computable function s.t., for all
Such a map exists because X is a computable metric space (and hence effective second-countable).
To show that is effectively open, notice that
This follows from the fact that is computable and that is because Y is co-c.e. compact. This shows that we can computably enumerate a list of open sets exhausting the complement of , i.e. .
The same argument shows (still assuming Y co-c.e. compact) that if then (it is enough to replace X with ). If then it can be written as , for some . In particular,
and therefore .
Finally, assume that and where the are uniformly co-c.e. compact. Let be s.t. (as above). Notice that, defining , the sequence is uniformly , as is uniformly co-c.e. compact. In other words,
and therefore (using a canonical computable identification ). □
We cannot extend Lemma 3.9 to effective spaces because in that context sets are not necessarily computable unions of sets. However the above proof works if we deal only with subsets of the product space that are computable unions of sets. We thus obtain the following Corollary.
Let,be effective second-countable spaces. If Y is co-c.e. compact then, for every,. If, where the sequenceis uniformly co-c.e. compact, andfor some, then.
Computable measure theory
If X is a separable metrizable space, we consider the space of Borel probability measures on X, endowed with the weak topology generated by the maps , with (i.e. is continuous and bounded, see [28, Sec. 17.E]). A basis for the topology on is the family of sets of the form
where , , and for every i. The space is separable metrizable iff so is X [37, Ch. II, Thm. 6.2]. Moreover if X is compact metrizable (resp. Polish) then so is ([28, Thm. 17.22 and Thm. 17.23]).
We now give a brief introduction on how computable measure theory can be developed in the context of TTE. For a more thorough presentation we refer the reader to [13]. The theory can be developed in the more general context of Borel measures on sequential topological spaces [44]. In particular, since every represented space can be endowed with the final topology (which is sequential), the theory can be developed for every represented space X. For our purposes it is enough to focus on probability measures on X, where X is (computably homeomorphic to) either or .
As mentioned, in this case is a Polish space. A canonical choice for a dense subset of is the set of probability measures concentrated on finitely many points of the dense subset of X, assigning rational mass to each of them (i.e. a weighted sum of Dirac deltas, where each weight is rational). Moreover, the Prokhorov metric on can be explicitly defined as
with . This metric induces the weak topology on . The space is a computable metric space (see [25, Prop. 4.1.1]), and therefore it is represented using the Cauchy representation.
From a computational point of view, it is often convenient to look at Borel (probability) measures from a different point of view. A (probability) valuation is a map s.t.
;
;
.
Probability valuations can be defined in a slightly more general context as maps over a lattice ([44, Sec. 2.2]). Every Borel measure μ naturally induces a valuation . The induced valuation is lower semicontinuous, i.e. if are nested open sets then . Since every finite Borel measure is uniquely identified by its restriction to the open sets (as every such measure on the Euclidean space is regular, and in particular outer regular, see e.g. [42, Thm. 2.18]), we can identify with the family of lower semicontinuous valuations on .
The lower semicontinuity of the valuations can be naturally translated in the context of TTE as follows. We use the represented space of real numbers, where is represented by a monotonically increasing sequence of rational numbers converging to x. Equivalently, we can think of a -name for x as the list of all rational numbers smaller than x. This is the so-called left-cut representation of the real numbers, and we say that a real is left-c.e. if it has a computable -name (see [48, Sec. 4.1]). The final topology induced on by is exactly the topology of lower semicontinuity (i.e. the topology whose open sets are of the form for some , see [48, Lem. 4.1.4]). Similarly, we obtain the represented space of the right-c.e. reals, where is the right-cut representation map, naming a real as a monotonically decreasing sequence of rationals converging to it. The final topology of is the topology of the upper-semicontinuity (again, see [48, Lem. 4.1.4]). It is straightforward to see that given a -name for x we can computably find a -name for (and vice versa). Notice that and are computable, but is not.
With this in mind, we can define another representation on the space of Borel (probability) measures: the canonical representation for a (probability) measure names a measure μ using a name for the (realizer-)continuous function ([44, Sec. 3.1]). The final topology on induced by coincides with the weak topology on ([44, Cor. 3.5]). Moreover, the canonical representation is equivalent to the Cauchy representation on ([44, Prop. 3.7]). In the development of the theory it is often more convenient to think of a (probability) measure as being represented using the canonical representation, i.e. using a name for the induced valuation. We can therefore think of a name for a (probability) measure μ on X as a list of -names for the measures of the basic open balls.
Letandbe represented spaces, endowed with the final topology induced by their respective representation maps. Let alsobe the set of continuous functions. The following maps are computable:
;
;
;
, whereis the push-forward measure;
;
, wheredenotes the space of effectively bounded continuous functions, i.e.and there are two computable reals a, b s.t. for every,.
Point is straightforward from the definition of the canonical representation for (see also [25, Prop. 4.2.1]) and point is a corollary of point (as ). Point follows trivially from the points and as a -name for can be computably obtained from a -name and a -name of x. Point is (essentially) a diagram-chasing exercise, see also [13, Prop. 49]. Points and are presented in [13, Sec. 3, in particular point (5) is Prop. 7]. See also [44, Prop. 3.6] for a slightly more general version of point . □
For our purposes, we will also need an effective analogue of the fact that if X is compact metrizable then so is ([28, Thm. 17.22]). The proof of the following theorem was suggested by Matthias Schröder.
For every computable metric space, if X is computably compact then so is.
Since X is a computably compact computable metric space, there is a total representation map for X which is (computably) equivalent to the Cauchy representation on X ([6, Prop. 4.1]).
Every probability measure can be identified with a function (identifying with ) s.t.
so that .
The map is a computable homeomorphism (i.e. a computable bijection with computable inverse) between and a subset of . Indeed, it is computable by Theorem 4.1(3) and its inverse is straightforwardly computable. Moreover, iff it satisfies (⋆), which is a condition relative to π. This, in turn, implies that is co-c.e. compact by Lemma 3.3 and the remarks preceding it, as is computably compact. In particular, the fact that is computably homeomorphic to a co-c.e. compact space implies it is co-c.e. compact.
To conclude the proof, define as the push-forward operator where . This map is computable (Theorem 4.1(4)) and surjective ([45, Thm. 14]), and therefore is co-c.e. compact. □
For every computable metric space X that admits an admissible representationwith co-c.e. compact domain, the spaceis co-c.e. compact.
Trivial from Theorem 4.2 since if X admits an admissible representation with co-c.e. compact domain then it is computably compact. □
For every d and every co-c.e. compact, the spaceis co-c.e. compact, and hence computably compact.
This follows from the fact that the interval is admissibly represented by the signed-digit representation
see e.g. [48, Sec. 7.2]. This, in turn, implies that for each the cube is admissibly represented by a total -representation map . Clearly, for every compact there is n s.t. . The restriction of to is an admissible representation with co-c.e. compact domain, hence the claim follows by Corollary 4.3. □
The effective Kaufman theorem
In the introduction, we mentioned that one of the first explicit examples of Salem sets is the set of α-well approximable numbers. More formally, for every , we define
The set is Salem with dimension (if then, by Dirichlet’s theorem [18, Ex. 10.8], ). Notice that is a subset of , as it can be written in the form
where is a finite union of non-degenerate closed intervals, and hence is closed. In fact, for every , is not closed (as it is dense in but ).
In his original proof of the fact that is Salem, Kaufman [27] defines a measure supported on a (compact) subset of witnessing that for every . A similar strategy is adopted in [49, Ch. 9], where the author defines a closed subset of with . This set can be written as
where is finite. There is some freedom in the precise choice of , but in any case the set is closed as the inner union is now finite.
We now prove an effective analogue of Kaufman theorem, i.e. we show that the map can be chosen to be computable. This, in turn, implies that the map is computable as well. To this end, we follow the blueprint of the proof strategy presented in [49, Ch. 9], making the estimates explicit so to obtain their (uniform) computability. We also change a few details to fix a minor imprecision. The estimates we present are often not tight, and it is certainly possible to have more precise bounds while retaining the (uniform) computability.
We start with a couple of technical lemmas. Let us mention that the name for a smooth function with compact support is a κ-name for and a sequence of -names for the n-th derivative of f.
Let us denote with the torus (i.e. the interval with endpoints identified). In particular, 1-periodic smooth functions with support in can be identified with smooth functions on .
If f is a smooth function onthen for every N and every xwhereis uniformly computable from N and f.
The existence of follows from Paley-Wiener-Schwartz theorem (see [24, Thm. 7.3.1]). To show that is uniformly computable from N and f, notice that, since , for every exponent n we have
and the latter is computable from a -name of . Using the binomial theorem, we can expand into a finite sum, and then compute a bound for each of the terms. □
Let ψ be a smooth function on. For everythere areands.t. for everyMoreover, the constantsandare uniformly computable from ψ and N.
Using Lemma 5.1 and the integral test for the convergence of series we can write
We can then compute s.t. for every
In particular, for every
where . □
From now on, we fix a computable non-negative smooth function ϕ with support in and . For every we define . Clearly the map is computable. Let also be the periodization of and . Both and are uniformly computable in ζ and p.
For , let . We define
The map is smooth, 1-periodic, and . In particular, we see it as a function in . Notice that the functions are uniformly computable in M, and ζ.
For every ζ and M as above we have:
,
ifthen,
for every N there is, independent of M and ζ and uniformly computable in N, s.t. for every,
Everything but the uniform computability of is proved in [49, Ch. 9, pp. 69–70]. In particular, the points and follow from the fact that is if , and 0 otherwise. Notice that, by the decomposition in prime factors, has at most divisors in . In particular, there is a computable constant C independent of and M s.t. has at most divisors in .
By the prime number theorem (see [22, Sec. 22.19 and Eq. (22.19.3)]), is asymptotically distributed as . In particular, there is a constant s.t. . The argument in [49] shows that satisfies the statement, where comes from Lemma 5.1. □
From now on, we let . This guarantees that . Moreover, choosing , the previous lemma states the existence of a constant s.t. for every and
The following two lemmas provide the main technical tools to prove the effectiveness of the map , which will be proved in Theorem 5.6.
Let ψ be a smooth non-negative function on. There existsand, uniformly computable in ψ and α, s.t. for everywe have
for every,;
for everywith,.
For the sake of readability, let us define, for , and ,
Notice that is strictly decreasing when , hence in particular for . Clearly, is uniformly computable in α and M. Moreover, given α, we can uniformly compute a constant s.t. for every and t, . Indeed, for ,
To prove the first part of the lemma, let us notice that, by the known properties of the Fourier transform and by Lemma 5.3, we have
Using Lemma 5.1 and a simple argument on power series, it is easy to show that there is a constant , uniformly computable from ψ, s.t. . In particular,
where is the constant provided by Lemma 5.3 and . This proves the first part of the claim.
Assume now that . We can write
For the first sum, notice that implies . Using Lemma 5.2, we can compute and s.t. for every
Using also the fact that , we have
where the second inequality follows from the fact that, for and , .
The second sum can be majorized as follows:
where the second inequality follows from the fact that is decreasing for , while the last inequality follows from .
We can combine the two estimates to conclude that, for and
with .
To conclude the proof it is enough to define . □
Let us define, for
where is the maximum point of g. Notice that is strictly decreasing for .
Let ψ be a non-negative smooth function on. For everyandwith, there is a finite sequence, uniformly computable in α, ψ, ε, and, s.t.and, for every k,where.
Let C, be the constants provided by Lemma 5.4. We choose N sufficiently large so that
We also choose sufficiently large so that and, for every ,
The existence of such follows from the fact that .
Let us define . We define the sequence iteratively so that for every
,
for every , .
The second condition can always be satisfied as, by Lemma 5.4,
for every k, ;
for every with , .
In fact, it is straightforward to see that, uniformly computably in ψ, α, and ε, we can choose N, and so that they satisfy the above conditions.
To show that the claim is satisfied with this choice of N, , …, we proceed as in [49, Ch. 9, pp. 71–72]. Let and let k s.t. (the cases and are analogous).
□
We are finally ready to prove the effectiveness of the map .
The following maps are computable:
Let us prove the computability of the first map. Lemma 5.5 states the existence of a computable map that maps to .
We recursively define two sequences of finite sequences of natural numbers and of smooth functions on as follows. We start letting be constantly equal to 1. We then define
where is defined as above.
By [49, Ch. 9, p. 73], a measure μ witnessing that is Salem is the weak-* limit of the sequence , where each is absolutely continuous w.r.t. the Lebesgue measure with density . In particular, and . Since , we can define and
The computability of this map follows from the computability of Θ.
The computability of the other maps is then straightforward. A ψ-name (i.e. a full information name) for can be uniformly computed from α and n as
The computability of the third map follows from the computability of the first two, while the computability of the last map follows from the fact that is computable (see Theorem 3.1). □
In particular, if α is computable then . Notice however that, in the previous proposition, we only get a -name (i.e. a negative representation name) for . Indeed, the map is not computable (it is not even continuous).
The effective complexity of closed Salem sets
In this section we characterize the effective complexity of the conditions , , , and “A is Salem”, i.e. we state and prove the effective counterparts of the results presented in [33].
We start by establishing the upper bounds for the complexity of the sets we are studying. Notice that, since and , proving the upper bounds using or yield a stronger result.
For every d and every compact,
is;
is.
For let us define
Notice that, if and (with the standard Cauchy representation) then the condition is a predicate of a and b (as it is equivalent to , where ). Notice also that the map is computable. By Theorem 4.1(1), is as a predicate of μ, x, r, c, and s.
Moreover, can be equivalently written as
Indeed, one inclusion is obvious, while the other follows from the fact that for every there are and s.t. and . Hence
Since the existential quantification on c can be trivially restricted to the rationals, we have
Observe that iff and . In particular, since is admissibly represented with the negative information representation, by Theorem 4.1(2), given two names for μ and A, we can computably obtain a right-cut representation for , hence the condition is a predicate of μ and A (as if the condition is co-c.e.). Since is computably compact (Corollary 4.4), using (the relativized version of) Lemma 3.9, we have
To conclude the proof we notice that the conditions
are and respectively (as predicates of A and p). □
For every d and every compact,
is;
is.
Consider the set
Recall that, by definition,
Since cos and sin are effectively bounded, by Theorem 4.1(6) the map
is computable. By the continuity of the Fourier transform, the universal quantification on can be restricted to . Since the quantification on c can be trivially restricted to the rationals, we obtain that , with
The claim follows as in the proof of Proposition 6.1: since the condition is a predicate of μ and A and is computably compact, we have that . Using (the relativized version of) Lemma 3.9 we conclude that , and finally
are, respectively, a and a predicate of A and p. □
For every compact, the setis.
As in the proof of [33, Thm. 3.4], recall that for every Borel A, hence iff
which is a condition by Proposition 6.1 and Proposition 6.2. □
We now show that, if we take and then the above conditions are lightface complete for their respective classes. To do so, we use Theorem 5.6 to prove an effective analogue of [33, Lem. 3.6]. We split the result in two lemmas.
Recall that, for , is the set of α-well approximable numbers, and is a closed Salem subset of with (see Section 5).
For every rationalthere is a supersetofwithwhere theare pairwise disjoint (possibly degenerate) closed intervals, s.t.:
is a closed Salem subset ofwith,
the levelsof the construction are s.t.
for every k,and;
for every k and everythere existss.t.,
the mapis computable.
We let , so that . The set can be rewritten as
where, for each k, the intervals are closed, non-degenerate, and pairwise disjoint.
We define recursively on k as follows: at stage 0 we let . At stage , let be a finite sequence of closed mutually disjoint intervals s.t.
For the sake of readability, let . Let also . We define
where is the left endpoint of . We then have .
Clearly each is a finite union of closed intervals, hence is closed. Moreover, for every stage k, is finite, and therefore is countable. This implies that . It is straightforward to see that the levels of the construction of satisfy the conditions and in the statement of the lemma.
Let us now prove the computability of the map . We define
The set can be naturally represented via the map , where is the canonical enumeration of .
We notice that ⩽ (and hence =) are decidable when restricted to . This follows from the decidability of the theory of real closed fields [47]: notice that is definable in the first-order language of real closed fields. Indeed, the rational number can be defined as the unique y that satisfies , where the first sum involves b 1s, and the second one involves a 1s. Moreover, for every and , the formula can be written as , and therefore it is expressible in . In particular, this shows that ⩽ and = are decidable for elements of .
Since, by definition,
the endpoints of the intervals are of the form , for some . In particular, if then the endpoints of the k-th level intervals of are in . The uniform computability of the finite set in the definition of (Theorem 5.6) implies that, for each k, we can think of as being represented via the sequence in , where .
We now show that, for each k, the endpoints of the k-th level intervals of are in , and that can be uniformly represented as the sequence in of the endpoints of the intervals . We proceed by induction on k. At stage 0 the statement is trivial. Assume the claim holds for . The decidability of implies that given two finite sequences and of intervals with endpoints in (where each interval is represented via a pair of -names for its endpoints), we can uniformly compute a finite sequence of mutually disjoint intervals with endpoints in s.t.
In particular, this implies that a sequence that satisfies (⋆) can be uniformly computed from α and k.
Similarly, for every and every , we can uniformly (in α and k) decide whether . In other words, the set is uniformly computable, and hence so is .
It is now straightforward to see that, given α and k, we can uniformly compute a finite sequence in s.t. the k-th level intervals of are . This, in turn, implies the computability of the map . □
There is a computable functions.t. for every p, x,is Salem and
The proof of the lemma follows a similar strategy as the proof of [33, Lem. 3.6]. Let and be as in Lemma 6.4. For every interval and every k let be the set obtained by scaling to the interval I. Notice that the mapping computably sends onto I, it is affine and it is invertible if I is non-degenerate. In particular, the partial map
is computable.
We first define a map s.t. for every and , is Salem and if and 0 otherwise. If we just take . Assume and let so that . We define recursively as
Stage:
;
Stage:
Let , …, be the disjoint closed intervals s.t. .
If then let be such that . For each let and define
The choice of ρ implies that
Define then .
If then let be largest s.t. (or if there is none). For each , apply the -th step of the construction of . Define .
We then define . Clearly is closed, as intersection of closed sets.
Let us show that it is Salem with the prescribed dimension. Assume first that (i.e. x is eventually 0) and let s be the largest index s.t. (or if there is none). By construction . Since and each is closed, we have that . On the other hand, if then we show that for each and each there is a cover of s.t. , which implies that . For every s and ε we can pick k a sufficiently large k so that and . The intervals defined in the construction of form a cover of s.t.
We now show that g is computable, i.e. that a full information name for can be uniformly computed from q and x. Notice that, since the map is computable, then so is the map (where the codomain is represented with the full information representation). Hence, a -name for can be computed from a sequence where is a -name for (Theorem 3.1). To compute a -name for (i.e. a positive information name), we use the fact that no interval is ever entirely removed and that no interval is entirely contained in (as ). In particular, a -name for is obtained by listing all the basic open balls U s.t. there are k and s.t. U contains a k-th level interval . Notice that, since no interval is entirely removed, implies . Moreover, if for some basic open ball V, then for some k and , V contains the k-th level interval .
We now define a map f that satisfies the statement of the lemma. Let be the sequence of disjoint intervals and a uniformly computable sequence of similarity transformations . Any is given as a sequence of rationals in which is monotonically increasing and converges to p. We define
The fact that is Salem and has the prescribed dimension follows from the properties of g and the countable stability for closed sets of and . Notice that a -name for can be obtained by carefully merging the -names of the sets . We can briefly sketch the argument as follows: a basic open set intersects iff it intersects for some n. On the other hand, to list the basic open balls contained in the complement of it suffices to list all the basic open balls contained in the relative topology of together with the open intervals . The claim follows from the fact that the intervals are uniformly co-c.e. closed. □
The following results are the effective counterparts of [33, Prop. 3.7, Thm. 3.8 and Thm. 3.9].
For everythe setsare-complete.
The upper bounds have been shown in Proposition 6.1 and Proposition 6.2. The hardness is a corollary of Lemma 6.5. □
Recall that is the -complete subset of defined as
The proof of the following theorem is similar to the proof of [33, Thm. 3.8], using Proposition 6.1, Proposition 6.2 and Lemma 6.5 in place of, respectively, [33, Prop. 3.2, Prop. 3.3 and Lem. 3.6].
There exists a computable maps.t. for every p and x,is a Salem set andiff. For every computable, lettingwe have that every set X s.t.is-hard. In particular,andare-complete.
After showing the existence of a computable F as claimed, the other statements follow. In particular, the completeness of and follows from Proposition 6.1 and Proposition 6.2.
For the first part, consider the computable map defined as and notice that iff . Intuitively, is a computable modification of x s.t. the set of rows with finitely many 1’s is an initial segment of (it is iff ).
For every m, let and . Fix also a similarity transformation and define as , where f is the computable map provided by Lemma 6.5. In particular,
We define
where denotes the m-th row of . The accumulation point 0 is added to ensure that is a closed set.
The computability of F follows from the computability of Φ and g. Using the stability properties of the Hausdorff and Fourier dimensions, we have that is Salem and
In particular, if then and, for every m, , hence
On the other hand, if then there is a s.t. for every , and hence . This implies that
and this completes the proof. □
The setis-complete.
The upper bound was proved in Corollary 6.3. To prove the hardness, fix a computable and let be a computable set s.t. and (e.g. we can choose K to be the Cantor middle-third set). Let also F be the map provided by Theorem 6.7 and define the map as
The computability of h follows from the computability of p and F, and the fact that the union map is computable (see Theorem 3.1). Moreover
In particular, is Salem iff iff . □
We now turn our attention to the closed Salem subsets of X, where X is or . We first notice the following result, which follows from the proofs of Proposition 6.1 and Proposition 6.2.
is;
is;
is;
is.
We only prove the statement for , the proof of the complexity of the other sets is analogous. Let
Since computably embeds into , we can see as a subset of . In particular, for every ,
Hence, it is enough to show that the sets are uniformly , i.e. that
Notice that, since the sets are uniformly computably compact, then so are the sets (the argument of Lemma 3.5 can be run uniformly in n). This, in turn, implies that the set
is , as the argument in the proof of Proposition 6.1 can be run uniformly in n. □
This result can be used to obtain the upper bounds in the non-compact case, i.e. the effective counterpart of the upper bounds obtained in [33, Thm. 5.4 and Thm. 5.5].
is;
is;
is;
is;
is.
We only prove the statement for the Hausdorff dimension, the proof of the complexity of the Fourier dimension is analogous (as both are stable under countable union of closed sets), and the result on the complexity of the Salem sets can be obtained as in Corollary 6.3.
Notice that, since A is closed,
Notice that, if F, G are two closed sets represented with the full information representation, the predicate is as a predicate of F and G. In fact we can prove something slightly stronger: if is a -name (positive information name) for F and is a -name (negative information name) for G then the condition is in and . Indeed,
This shows that and are respectively (as a predicate of K and A) and an effective union of sets (as a predicate of K, as it is equivalent to ). Moreover, since the inclusion map is computable, using Lemma 6.9 we have that is an effective union of sets. Thus also
is an effective union of sets. Since is computably compact (Proposition 3.6) we can apply Corollary 3.10 and conclude that
Since iff , this also shows that is a predicate of A and p. □
We now turn our attention to the lower bounds for the complexity of the above conditions. In [33, Sec. 4], we exploited a recent construction of a higher dimensional analogue of (introduced in [19]) to show that, for a closed , the conditions and are -complete (when ) and the conditions and are -complete (when ). However, we are not aware of any proof of the effectiveness of the arguments presented in [19], which would be needed to prove a higher-dimensional analogue of Lemma 6.5.
However, we use a classical theorem of Gatesoupe to obtain a (slightly weaker) result, namely the completeness of the above conditions when p and q are sufficiently large.
Let X beor. For everythe setsare-complete. For every computable, the setsare-complete.
By Proposition 6.10, it is enough to show that the above sets are hard for their respective class.
Recall that, by a theorem of Gatesoupe [20], if has at least a point different from 0 and is Salem with dimension α then the set is Salem with dimension . It is easy to see that the map is computable.
To show that the first two sets are -hard, let f be the map provided by Lemma 6.5. For and , we have
Fix now a computable . To show that the conditions and are -hard, consider a sequence of mutually disjoint closed cubes s.t.
,
, where is the origin of the d-dimensional Euclidean space,
the sets have uniformly computable ψ-names, i.e. there is a computable map that, given n, produces a ψ-name for .
It is easy to provide examples of sequences of closed sets that satisfy the above conditions. In particular, the last point guarantees that the similarity transformations are uniformly computable. The claim follows by a straightforward adaptation of the proof of Theorem 6.7.
Finally, to show that the family of closed Salem sets is -hard, we adapt the proof of Theorem 6.8, where the compact set K is replaced with a fixed computable compact set with null Fourier dimension and Hausdorff dimension d. □
The Weihrauch degree of Hausdorff and Fourier dimension
In this section, we briefly show how the results obtained in the previous sections can be used to characterize the uniform strength of the maps computing the Hausdorff and Fourier dimension of a closed subset of , for some fixed d.
Let and be partial multi-valued functions between represented spaces. We say that f is Weihrauch reducible to g () iff there are two computable maps s.t., for every realizer G of g, the map is a realizer for f. A thorough presentation on Weihrauch reducibility is out of the scope of this paper, and the reader is referred to [8].
We define the compositional product as
This operator captures the idea of using g and f in series, possibly using a computable procedure to map a name for an output of g to a name for an input of f. While, formally, is a Weihrauch degree (and not a specific multi-valued function), with a small abuse of notation, we write with the obvious meaning. We also write to denote the n-fold compositional product of f with itself, where and .
Let be a Borel pointclass. We say that is -measurable if, for every open , , i.e. there exists s.t. . If X and Y are represented spaces, we say that f is effectively-measurable or -computable if the map
is computable. In particular, if f is total then is single-valued. This notion can be generalized in a straightforward way to multi-valued functions (see [5, Def. 3.5]).
Let be the function mapping a convergent sequence in the Baire space to its limit. In the proof of Theorem 7.2 we will use the following result:
This is a generalization of [5, Thm. 9.1], and draws an important connection between the Weihrauch degrees and the effective Borel hierarchy.
We identify two maps corresponding to the Hausdorff dimension and two maps corresponding to the Fourier dimension, according to the way closed sets are represented:
, ,
, .
.
It is immediate to see that and . To prove the reductions and , by Theorem 7.1 it suffices to show that the maps and are -computable. This follows by Proposition 6.10 as
In fact, given we can uniformly compute a -computable -name for .
Finally, to prove that and we show that, given a sequence in , we can uniformly build a closed Salem subset A of s.t. uniformly computes whether , where is the fixed -complete set (see Section 2.3). This suffices because is Weihrauch equivalent to answering countably many questions in parallel.
Let f be the computable map provided by Lemma 6.5. Let also
and define . Recall that, by the classic theorem of Gatesoupe [20] (to apply it we added the condition in the definition of r), if F is Salem with dimension α then is Salem with dimension . For every non-constantly 0 string , let and let . The term is added for technical reasons, which will become apparent at the end of the proof. Define as . Clearly
On the other hand, .
As in the proof of Theorem 6.11, let be a sequence of mutually disjoint closed cubes s.t.
,
, where is the origin of the d-dimensional Euclidean space,
the sets have uniformly computable ψ-names.
For every σ as above, we can uniformly translate and scale the set to a subset of . Consider now the closed set . It is routine to show that A is Salem and . It is then straightforward to notice that, for every i, the value of is the -th digit in the binary expansion of .
Notice that, in general, the map sending a Cauchy representation of a real to its binary expansion is not computable (reals with two binary representations can be used to diagonalize against any possible computation). To ensure computability, we defined so that is guaranteed to have a unique binary expansion (and hence its binary representation is computable from its Cauchy name). In fact the binary expansion of has value in the -th position, 0 in the positions congruent to , and 1 in the positions congruent to (to attain the latter conditions we added , which in binary is ). □
The Weihrauch equivalence between and the map computing the Hausdorff dimension of a closed subset of (and, more generally, of a compact subset of ) was already proved in [41, Thm. 48]. Our approach extends that result and, at the same time, characterizes the degree of the map computing the Fourier dimension.
Footnotes
Acknowledgements
The early investigations leading to this paper were conducted jointly with Ted Slaman and Jan Reimann. We would also like to thank Vasco Brattka, Antonio Montalbán, Arno Pauly, Matthias Schröder, Luciano Tubaro, and Linda Brown Westrick for useful discussions and suggestions on the topics of the paper. We thank the two anonymous referees for their careful reading of the paper.
Both author’s research was partially supported by the Italian PRIN 2017 Grant “Mathematical Logic: models, sets, computability”.
References
1.
A.Andretta and A.Marcone, Ordinary differential equations and descriptive set theory: Uniqueness and globality of solutions of Cauchy problems in one dimension, Fundamenta Mathematicae153(2) (1997), 157–190. http://eudml.org/doc/212220. doi:10.4064/fm-153-2-157-190.
2.
G.Beer, Topologies on Closed and Closed Convex Sets, 1st edn, Mathematics and Its Applications, Vol. 268, Springer, Dordrecht, 1993, pp. xii–340. ISBN 978-90-481-4333-7. doi:10.1007/978-94-015-8149-3.
3.
A.S.Besicovitch, Sets of fractional dimensions (IV): On rational approximation to real numbers, Journal of the London Mathematical Societys1-9(2) (1934), 126–131. doi:10.1112/jlms/s1-9.2.126.
4.
C.Bluhm, On a theorem of Kaufman: Cantor-type construction of linear fractal Salem sets, Ark. Mat.36(2) (1998), 307–316. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.621.3328&rep=rep1&type=pdf. doi:10.1007/BF02384771.
5.
V.Brattka, Effective Borel measurability and reducibility of functions, Mathematical Logic Quarterly51(1) (2005), 19–44. doi:10.1002/malq.200310125.
6.
V.Brattka, M.de Brecht and A.Pauly, Closed choice and a uniform low basis theorem, Annals of Pure and Applied Logic163(8) (2012), 986–1008. https://arxiv.org/abs/1002.2800. doi:10.1016/j.apal.2011.12.020.
7.
V.Brattka and G.Gherardi, Borel complexity of topological operations on computable metric spaces, Journal of Logic and Computation19(1) (2008), 45–76. doi:10.1093/logcom/exn027.
8.
V.Brattka, G.Gherardi and A.Pauly, Weihrauch complexity in computable analysis, in: Handbook of Computability and Complexity in Analysis, V.Brattka and P.Hertling, eds, Springer International Publishing, 2021, pp. 367–417. https://arxiv.org/pdf/1707.03202v4. ISBN 978-3-030-59234-9. doi:10.1007/978-3-030-59234-9_11.
9.
V.Brattka, A.Kawamura, A.Marcone and A.Pauly, Measuring the complexity of computational content (Dagstuhl Seminar 15392), Dagstuhl Reports5(9) (2016), 77–104. http://drops.dagstuhl.de/opus/volltexte/2016/5686. doi:10.4230/DagRep.5.9.77.
10.
V.Brattka and G.Presser, Computability on subsets of metric spaces, Theoretical Computer Science305(1) (2003), 43–76. https://www-sciencedirect-com-443.web.bisu.edu.cn/science/article/pii/S030439750200693X. doi:10.1016/S0304-3975(02)00693-X.
11.
V.Brattka and K.Weihrauch, Computability on subsets of Euclidean space I: Closed and compact subsets, Theoretical Computer Science219(1) (1999), 65–93. https://www-sciencedirect-com-443.web.bisu.edu.cn/science/article/pii/S0304397598002849. doi:10.1016/S0304-3975(98)00284-9.
12.
A.Callard and M.Hoyrup, Descriptive complexity on non-Polish spaces, in: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), C.Paul and M.Bläser, eds, Leibniz International Proceedings in Informatics (LIPIcs), Vol. 154, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2020, pp. 8:1–8:16. ISSN 1868-8969. https://drops.dagstuhl.de/opus/volltexte/2020/11869. ISBN 978-3-95977-140-5. doi:10.4230/LIPIcs.STACS.2020.8.
13.
P.Collins, Computable stochastic processes, 2015, pp. 1–30. https://arxiv.org/abs/1409.4667v2.
14.
M.de Brecht, Levels of discontinuity, limit-computability, and jump operators, in: Logic, Computation, Hierarchies, V.Brattka, H.Diener and D.Spreen, eds, De Gruyter, 2014, pp. 79–108. doi:10.1515/9781614518044.79.
F.Ekström, T.Persson and J.Schmeling, On the Fourier dimension and a modification, Journal of Fractal Geometry2(3) (2015), 309–337. https://arxiv.org/abs/1406.1480. doi:10.4171/JFG/23.
17.
F.Ekström and J.Schmeling, A survey on the Fourier dimension, in: Patterns of Dynamics, P.Gurevich, J.Hell, B.Sandstede and A.Scheel, eds, Springer Proceedings in Mathematics & Statistics, Vol. 205, Springer, Cham, 2017, pp. 67–87. doi:10.1007/978-3-319-64173-7_5.
18.
K.Falconer, Fractal Geometry, Mathematical Foundations and Applications, 3rd edn, John Wiley & Sons, Ltd., Chichester, 2014, pp. xxx–368. ISBN 978-1-119-94239-9.
19.
R.Fraser and K.Hambrook, Explicit Salem sets in , 2019. https://arxiv.org/abs/1909.04581v2.
20.
M.Gatesoupe, Sur un théorème de R. Salem, Bulletin des Sciences Mathématiques. Deuxième Série91 (1967), 125–127.
21.
V.Gregoriades, T.Kispéter and A.Pauly, A comparison of concepts from computable analysis and effective descriptive set theory, Mathematical Structures in Computer Science27(8) (2017), 1414–1436. doi:10.1017/S0960129516000128.
22.
G.H.Hardy and E.M.Wright, An Introduction to the Theory of Numbers, 6th edn, Oxford University Press, Oxford, 2008, p. xxii+621. ISBN 978-0-19-921986-5.
23.
J.M.Hitchcock, J.H.Lutz and S.A.Terwijn, The arithmetical complexity of dimension and randomness, ACM Transactions on Computational Logic8(2) (2007), 1–22. doi:10.1145/1227839.1227845.
24.
L.Hörmander, The Analysis of Linear Partial Differential Operators I, 2nd edn, Classics in Mathematics, Vol. 440, Springer, Berlin, Heidelberg, 2003, pp. XI. ISBN 978-3-540-52345-1. doi:10.1007/978-3-642-61497-2.
25.
M.Hoyrup and C.Rojas, Computability of probability measures and Martin–Löf randomness over metric spaces, Information and Computation207(7) (2009), 830–847. http://arxiv.org/abs/0709.0907v2. doi:10.1016/j.ic.2008.12.009.
26.
V.Jarník, Zur metrischen Theorie der diophantischen Approximationen, Prace Matematyczno-Fizyczne36(1) (1928–1929), 91–106. http://eudml.org/doc/215473.
27.
R.Kaufman, On the theorem of Jarník and Besicovitch, Acta Arithmetica39(3) (1981), 265–267. http://eudml.org/doc/205767. doi:10.4064/aa-39-3-265-267.
28.
A.S.Kechris, Classical Descriptive Set Theory, 1st edn, Springer-Verlag, 1995, p. 402. ISBN 0387943749.
29.
J.Keesling, Normality and properties related to compactness in hyperspaces, Proceedings of the American Mathematical Society24(4) (1970), 760–766. http://www.jstor.org/stable/2037318. doi:10.1090/S0002-9939-1970-0253292-7.
30.
E.Klein and A.C.Thompson, Theory of Correspondences – Including Applications to Mathematical Economics, Wiley, 1984, pp. xiv–256. ISBN 0-471-88016-7.
31.
J.H.Lutz and N.Lutz, Algorithmic information, plane Kakeya sets, and conditional dimension, in: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), H.Vollmer and B.Vallée, eds, Leibniz International Proceedings in Informatics (LIPIcs), Vol. 66, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017, pp. 53:1–53:13. ISSN 1868-8969. http://drops.dagstuhl.de/opus/volltexte/2017/6980. ISBN 978-3-95977-028-6. doi:10.4230/LIPIcs.STACS.2017.53.
32.
J.H.Lutz and E.Mayordomo, Dimensions of points in self-similar fractals, in: COCOON 2008: Computing and Combinatorics, X.Hu and J.Wang, eds, Lecture Notes in Computer Science, Vol. 5092, Springer, Berlin, Heidelberg, 2008, pp. 215–224. doi:10.1007/978-3-540-69733-6_22.
33.
A.Marcone and M.Valenti, On the descriptive complexity of Salem sets, Fundamenta Mathematicae257(1) (2022), 69–94. https://arxiv.org/abs/2009.09888. doi:10.4064/fm997-7-2021.
34.
P.Mattila, Geometry of Sets and Measures in Euclidean Spaces: Fractals and Rectifiability, Cambridge University Press, 1995, p. 343. ISBN 0521465761. doi:10.1017/CBO9780511623813.
35.
P.Mattila, Fourier Analysis and Hausdorff Dimension, 1st edn, Cambridge University Press, 2015, pp. xiv–440. ISBN 978-1-107-10735-9. doi:10.1017/CBO9781316227619.
36.
Y.N.Moschovakis, Descriptive Set Theory, 2nd edn, North Holland, 2009, p. 638. ISBN 978-0-8218-4813-5.
37.
K.R.Parthasarathy, Probability Measures on Metric Spaces, Probability and Mathematical Statistics: A Series of Monographs and Textbooks, Academic Press, Inc., New York–London, 1967, p. xi+276. ISBN 978-1-4832-0022-4. doi:10.1016/C2013-0-08107-8.
38.
A.Pauly, On the topological aspects of the theory of represented spaces, Computability5(2) (2016), 159–180. https://arxiv.org/pdf/1204.3763. doi:10.3233/COM-150049.
39.
A.Pauly, The descriptive theory of represented spaces, 2014. https://arxiv.org/pdf/1408.5329v1.
40.
A.Pauly and M.de Brecht, Descriptive set theory in the category of represented spaces, in: 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015, pp. 438–449, ISSN 1043-6871. doi:10.1109/LICS.2015.48.
41.
A.Pauly and W.L.Fouché, How constructive is constructing measures?, Journal of Logic and Analysis9 (2017), 1–30. doi:10.4115/jla.2017.9.c3.
42.
W.Rudin, Real and Complex Analysis, 3rd edn, McGraw-Hill, Inc., New York, NY, USA, 1987, p. xiv, 416. ISBN 0070542341.
M.Schröder, Admissible representations for probability measures, Mathematical Logic Quarterly53(4–5) (2007), 431–445. doi:10.1002/malq.200710010.
45.
M.Schröder and A.Simpson, Representing probability measures using probabilistic processes, Journal of Complexity22(6) (2006), 768–782. https://www-sciencedirect-com-443.web.bisu.edu.cn/science/article/pii/S0885064X06000434. doi:10.1016/j.jco.2006.05.003.
46.
E.M.Stein and G.Weiss, Introduction to Fourier Analysis on Euclidean Spaces, 1st edn, Princeton University Press, Princeton, N.J., 1971, pp. xii–297. ISBN 069108078X. doi:10.1515/9781400883899.
47.
A.Tarski, A decision method for elementary algebra and geometry, in: Texts and Monographs in Symbolic Computation, B.F.Caviness and J.R.Johnson, eds, Springer, Vienna, 1998, pp. 24–84. ISBN 978-3-7091-9459-1. doi:10.1007/978-3-7091-9459-1_3.
48.
K.Weihrauch, Computable Analysis: An Introduction, 1st edn, Springer-Verlag, Berlin, 2000, p. x+285. ISBN 3540668179.
49.
T.H.Wolff, Lectures on Harmonic Analysis, 1st edn, American Mathematical Society, 2003, pp. x–142. ISBN 0-8218-3449-5. doi:10.1090/ulect/029.
