On the descriptive complexity of Salem sets

Alberto Marcone and Manlio Valenti

In this paper we study the notion of Salem set from the point of view of descriptive set theory. We first work in the hyperspace of compact subsets of and show that the closed Salem sets form a -complete family. This is done by characterizing the complexity of the family of sets having sufficiently large Hausdorff or Fourier dimension. We also show that the complexity does not change if we increase the dimension of the ambient space and work in . We then generalize the results by relaxing the compactness of the ambient space, and show that the closed Salem sets are still -complete when we endow with the Fell topology. A similar result holds also for the Vietoris topology. We apply our results to characterize the Weihrauch degree of the functions computing the Hausdorff and Fourier dimensions.

Key words and phrases:
Salem sets, Hausdorff dimension, Fourier dimension, Borel hierarchy.
2020 Mathematics Subject Classification:
Primary: 03E15; Secondary: 28A75, 28A78, 03D32.

1. Introduction

The notion of Salem set arises naturally in the context of geometric measure theory and the theory of fractal dimension. A set is called Salem iff , where and denote the Hausdorff and the Fourier dimension respectively.

Hausdorff dimension is a fundamental notion in geometric measure theory and can be found in almost every textbook in the field. It describes the “size” of a set by means of the diameter of open sets covering it. When working with Borel subsets of , Frostman’s lemma characterizes the Hausdorff dimension of a set by means of the existence of finite Radon measures supported on the set with certain regularity properties (see Section 2 for details).

This characterization establishes a close connection with the Fourier transform of a measure. Indeed, it can be shown that the decay of the Fourier transform of a (probability) measure supported on the set provides a lower bound for the Hausdorff dimension. This leads to the notion of Fourier dimension and hence to the one of Salem set. It is known that, for Borel subsets of , the Fourier dimension never exceeds the Hausdorff dimension.

The first non-trivial examples of Salem sets were based on random constructions ([26, 15]). Later Kahane [14] modified the original construction by Salem to produce an explicit Salem set of dimension , for every . An important example of an explicit Salem set comes from the theory of Diophantine approximation of real numbers: Jarník [13] and Besicovitch [3] proved that, for , the set of -well approximable numbers is a fractal with Hausdorff dimension . Kaufmann [16] improved the result by showing that there is a probability measure supported on a subset of witnessing the fact that , which implies that is Salem (the reader is referred to [4] or [28] for detailed proofs of Kaufmann’s theorem).

A classical example of a non-Salem set is Cantor middle-third set, which has Fourier dimension and Hausdorff dimension . Similarly, every symmetric Cantor set with dissection ratio , with , is not Salem, as it has null Fourier dimension and Hausdorff dimension (see [22, Sec. 4.10] and [23, Thm. 8.1]). It can be proved that, for every there is a compact subset of with Fourier dimension and Hausdorff dimension ([19, Thm. 1.4]).

There are not many explicit (i.e. non-random) examples of subset of which are known to be Salem. As a corollary of a result of Gatesoupe [11], we know that if is a Salem set of dimension then the set is Salem and has dimension . Recently, using a higher-dimensional analogue of , some explicit examples of Salem subsets of ([12]) and ([10]) of arbitrary dimension have been constructed.

In this paper we study the complexity, from the point of view of descriptive set theory, of the family of closed Salem subsets of , where is either , or . In particular we view as a subset of the hyperspace of the closed subsets of . We show that it is Borel and classify it in the Borel hierarchy.

We summarize our results for in the following table.


The complexities remain the same if we replace with any interval, with or . Moreover, since all our proofs are effective, the same techniques show that each of the above sets is lightface complete for its corresponding class. In particular, the fact that the family of effectively 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 the final section we show how our results yield classifications of the functions computing the dimensions of closed sets, both in the Baire hierarchy and in the effective hierarchy defined via Weihrauch reducibility, answering also a question raised by Fouché ([6]) and Pauly.


The early investigations leading to this paper were motivated by the above-mentioned question asked by Ted Slaman. The results of Section 3 are indeed joint work with Ted Slaman and Jan Reimann.

We would also like to thank Geoffrey Bentsen, Riccardo Camerlo, Kyle Hambrook and Arno Pauly for useful discussions and suggestions on the topics of the paper.

Both author’s research was partially supported by the Italian PRIN 2017 Grant “Mathematical Logic: models, sets, computability”. Valenti’s participation to the IMS Graduate Summer School in Logic in was partially funded by Institute for Mathematical Sciences (National University of Singapore).

2. Background

For a general introduction to geometric measure theory the reader is referred to [9]. Here we introduce the notions and notations we will use throughout the rest of the paper.

Let be a separable metric space and let . Let also denote the diameter of . We say that a family is a -cover of if and for each . For every , we define

The function is called -dimensional Hausdorff measure. The Hausdorff dimension of is defined as

As a consequence of Frostman’s lemma (see [22, Thm. 8.8, p. 112]), for every Borel subset of (with the Euclidean norm), the Hausdorff dimension of coincides with its capacitary dimension , defined as

where is the set of probability measures supported on and denotes the ball with center and radius . We notice that the Hausdorff dimension is countably stable (i.e. for every family we have , see [22, p. 59]) and, for every -Hölder continuous map we have (see [9, Prop. 3.3, p. 49]). In particular if is bi-Lipschitz then it preserves the Hausdorff dimension.

For every probability measure on , we can define the Fourier transform of as the function defined as

where denotes scalar product. We define the Fourier dimension of as

If we define then we have . For background notions on the Fourier transform the reader is referred to [27]. For its applications to geometric measure theory see [23].

The Fourier dimension is not as stable as the Hausdorff dimension: in particular it is not countably stable in general ([7, Ex. 7]) but it is countably stable under some additional conditions. The following result is very useful in practice:

Theorem 2.1 ([7, Cor. 4]).

Let be a finite or countable family of Borel subsets of s.t., for every , the set

is countable. Then

It is also known that the Fourier dimension does not behave well under Hölder continuous maps: there is a Hölder continuous transformation that maps the Cantor middle-third set to the interval , although they have Fourier dimension respectively and ([8, Sec. 8]). However, the following fact, which we will use repeatedly in the paper, can be proved using the properties of the Fourier transform (see also [8, Prop. 6]):

Fact 2.2.

The Fourier dimension is invariant under affine invertible transformations.

It is known that, for every Borel subset of , (see [22, Chap. 12]). If then is called Salem set. We denote the collection of closed Salem subsets of with .

In this work we study the descriptive set-theoretic properties of the family of closed Salem subsets of the Euclidean space. For an extended presentation of descriptive set theory the reader is referred to [17].

Let be a metric space. It is known that the family of Borel subsets of can be stratified in a hierarchy, called the Borel hierarchy. Let be the first uncountable ordinal. The levels of the Borel hierarchy are defined by transfinite recursion on as follows: we start from the families and of the open and the closed subsets of respectively. Then, for every we define:

  • ,

  • .

Moreover, for every , we define . In particular is the family of clopen subsets of . The families and are often written resp.  and . It is known that , where denotes the family of Borel subsets of .

Let and be topological spaces and , . We say that is Wadge reducible to , and write , if there is a continuous function s.t.  iff . It is easy to see that if is among , , then is closed under continuous preimages, i.e.  and implies .

Fix a class as above. Assume is a Polish (i.e. separable and completely metrizable) space and . We say that is -hard if for every , where is Polish and zero-dimensional (i.e. Hausdorff and with a basis consisting of clopen sets). If is -hard and then we say that is -complete.

A common technique to show that a set is -hard is to show that there is a Wadge reduction , for some which is already known to be -complete. Standard examples of -complete sets are the following (see [17, Sec. 23.A, p. 179]):


where and mean respectively and .

For a topological space , we denote by and respectively the hyperspaces of closed and compact subsets of . A canonical choice for the topology on is the Vietoris topology (see [17, Sec. 4.F, p. 24]): a prebase for consists of the sets of the form

for open sets . Let be a bounded metric space with distance . We can define the Hausdorff metric on as follows:

where . It is known that the Hausdorff metric is compatible with the Vietoris topology on ([17, Ex. 4.21, p. 25]) and that if is Polish then so is ([17, Thm. 4.22, p. 25]). However if is not compact then the Vietoris topology on is not metrizable (the in the definition of is not guaranteed to exist otherwise, and two closed sets can be infinitely distant).

We can define the Fell topology on by considering a prebase of the form

for all s.t.  is compact and is open. If is compact then but if is not compact then the Fell topology is strictly coarser then the Vietoris topology and is Polish when is Polish and locally compact. For more information on topologies on the hyperspace of closed sets the reader is referred to [2].

An important tool in descriptive set theory is Baire category. A set is called nowhere dense if its closure has empty interior, meager if it is the countable union of nowhere dense sets and comeager if its complement is meager. By the Baire category theorem (see [17, Thm. 8.4]), in every Polish space the intersection of countably many open dense sets is dense ([17, Prop. 8.1]). In particular every comeager set is dense (it follows from the definition that a set is comeager iff it contains a dense set).

We omit a detailed presentation of Weihrauch reducibility, as it is only briefly discussed in the final section of the paper. Intuitively the notion is a uniform version of computable reducibility between functions on spaces where a notion of computability is available. For a detailed presentation, the reader is referred to [5].

We conclude this section with the following lemma:

Lemma 2.3 ([1, Lem. 1.3]).

Let be Polish and metrizable and (i.e. countable union of compact sets). If is then is also .

3. The complexity of closed Salem subsets of

Proposition 3.1.

  • is ;

  • is .


As noticed in the previous section, for Borel (in particular closed) , the Hausdorff dimension coincides with the capacitary dimension . For ease of readability define

Notice that is downward closed. Recall that . Observe that

and that the map , is continuous. Using [17, Ex. 17.29, p. 114] we have that is a closed condition, hence the set

is a closed subset of the product space . Notice also that

Since the condition is closed we have that, for each closed subset of , the set

is .

We can now notice that, by [17, Thm. 17.22, p. 112], the space is metrizable and compact. Using 2.3 we can conclude that the set is . To conclude the proof we notice that the conditions

are and respectively. ∎

Proposition 3.2.

  • is ;

  • is .



Recall that the space is endowed with the topology generated by the maps , with (see [17, Sec. 17.E, p. 109]). First of all we notice that the condition is . To see this it is enough to show that the map s.t.  is continuous. Indeed, if that is the case, then the tuple satisfies the condition iff it belongs to the preimage of via the map , which is clearly continuous.

First of all recall that, for each finite Borel measure , the Fourier transform is a bounded uniformly continuous function.

Notice that the set

is open in the topology of . Indeed, fix and let s.t. . Using the notation of [17, p. 110], we claim that the basic open set

and therefore

To conclude the proof of the continuity we show that for each and each and we can choose sufficiently small s.t. for every we have . Indeed, by the triangle inequality

The first term is bounded by by definition of . Moreover

By the sum-to-product formulas

and similarly

hence the claim follows.

Since is a closed condition (see the proof of 3.1), the set

is closed and, therefore, the set

is . As in the proof of 3.1, we can use 2.3 to conclude that the set is and hence the conditions

are and respectively. ∎

Theorem 3.3.

  • is ,

  • is ,

  • is .


To prove that is a condition recall that, for Borel subsets of , . For a closed subset of , the condition can be written as

The claim follows from 3.1 and 3.2, as both and are conditions.

To prove the last two points recall that, for a Salem set , , hence the claims follow by 3.1 (equivalently we could have used and 3.2). ∎

Lemma 3.4.

For every there exists a continuous map s.t.


Recall that is -complete.

The case is trivial (just take the constant map ), so assume . Let s.t.  and consider the Salem set of -well approximable numbers as defined in [9, Sec. 10.3, p. 172]. It is known that there is a closed subset of s.t.  (see [4, Thm. 3.3]). In particular is Salem. The set can be written as


and, for each , the are closed disjoint intervals. Moreover if we have

and for every there exists s.t. .

For each we define a sequence of nested closed sets s.t. each is a finite union of closed intervals. The idea is to follow the construction of until we find a s.t. . If this never happens then in the limit we obtain , which is a Salem set of Fourier dimension . On the other hand, each time we find a s.t.  we modify the next step of the construction by replacing each of the (finitely many) intervals whose union is the -th level of the construction with sufficiently small subintervals , and we reset the construction, starting again a (proportionally scaled down) construction of on each subinterval . By carefully choosing the length of the subintervals we can ensure that, if there are infinitely many s.t.  then has null Hausdorff (and hence Fourier) dimension.

Formally, if is an interval then we define as the fractal obtained by scaling to the interval . Notice that, by 2.2, is still a Salem set of dimension .

We define recursively as

Stage :

: ;

Stage :

: Let be the disjoint closed intervals s.t. . If then choose, for each , a (non-degenerate) subinterval so that

Define then .

If then let be largest s.t.  (or if there is none) and let be the intervals of . For each , apply the -th step of the construction of . Define .

We define the map as . To show that is continuous recall the Vietoris topology is compatible with the Hausdorff metric . Fix . For each we can choose large enough so that all the intervals of have length . By construction, for every that extends we have (i.e. none of the intervals is ever removed completely) and (i.e. nothing is ever added outside of ). This implies that

which proves the continuity.

If then is eventually null (i.e. there are finitely many s in ). Letting be the largest index s.t.  (or if there is none) then . Each set is a Salem set of dimension (as we fixed accordingly). Since the intervals are closed and disjoint, using 2.1, we can conclude that is a Salem set of dimension .

On the other hand, if then we want to show that . We will show that for each and there is a cover of s.t. , i.e.  for each , .

For fixed and we can pick large enough s.t. , and . Notice that the intervals (as defined in the construction of ) form a cover of s.t.

as desired. ∎

Proposition 3.5.

For every the sets

are -complete.


The hardness is a straightforward corollary of 3.4: fix s.t.  and the -complete subset of . We can consider the map as in 3.4 and notice that

The completeness follows from 3.1 and 3.2. ∎

Theorem 3.6.

For every , the sets

are -complete.


It suffices to prove that the sets , and are -hard (the completeness follows from 3.1, 3.2 and 3.3 respectively).

Recall that is the -complete subset of defined as

Consider the map defined as

It is easy to see that is continuous. Notice also that iff . On the other hand,

Intuitively, we are computably modifying the matrix so that if there is a row of that contains infinitely many s, then, from that row on, every row will contain infinitely many s.

To show that and are -hard, we build a continuous map s.t. for every , is a Salem set and iff .

For every , let , and consider the function of 3.4. Fix also a similarity transformation and define as , so that, by 2.2,

Let be the -th row of . We define

Intuitively, we are dividing the interval into countably many intervals and, on each interval, we are applying the construction we described in the proof of 3.4 (proportionally scaled down). The continuity of follows from the continuity of each . The accumulation point is added to ensure that is a closed set.

Recall that Hausdorff dimension is stable under countable unions, so

Moreover, since the sets are closed and, for the intersection is at most a point, the same holds for the sets . We can therefore apply 2.1 and conclude that

Since each is Salem we have that is Salem and

If then and, for every , . This implies that is a Salem set of dimension and therefore

On the other hand, if then there is a s.t. for every , and hence . This implies that

This completes the proof that the sets and are -hard.

With a simple modification of the above argument we can show that (i.e. the family of closed Salem subsets of ) is -hard as well.

Let be a constant map that sends every to a closed subset of with Hausdorff dimension and null Fourier dimension. We define as

Notice that, since , we have for every . In particular, is Salem iff for every ,