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.
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/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/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/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.
