[PhD 2024] Descriptive complexity of topological invariants
This project will be carried out in the Inria team Mocqua, which focuses on emerging models of computation, in particular the interaction between discrete computations and continuous mathematics.
This PhD project is about the complexity of detecting topological properties of sets. The language of mathematics enables one to define continuous sets of points using a few symbols only. Typical examples are the solution set of an equation, or the attractor of a dynamical system. However, such finite descriptions do not give much information about the set itself and in particular its topology: its connectedness properties, its dimension, the existence of holes, etc.
The goal of this project is, given an access to a subset of the plane or a higher-dimensional Euclidean space, to understand how much of the topology of the set can be recovered, and what is the difficulty of the detection. This project lies at the interface between algorithmics, logic and topology. Techniques from continuous mathematics need to be used. In particular, the complexity is measured using descriptive set theory, which provides hierarchies and complexity classes of subsets of topological spaces, and is intimately related to logic [1].
The topic is vast and we propose to follow two particular directions.
The first axis is the investigation of the complexity of topological invariants. The literature on the topic shows that most of the invariants provided by topology have very high complexity (see [2], [3] for instance). Therefore, one needs to identify properties that can be detected with a low complexity budget. We propose several approaches to tackle this problem. Given a particular class of spaces, determine the minimal complexity of separating all the spaces of this class. In particular, given two distinct spaces, determine the exact complexity of distinguishing between them. For each particular space, determine the complexity of recognizing this space, i.e. of checking that an arbitrary space is isomorphic to that space. A first step in these directions has been initiated in [4], analyzing the case of finite topological graphs, and the more general case of finite simplicial complexes is still to be understood.
The second axis is about the complexity of theorems coming from topology. When a theorem asserts the existence of an object under certain asumptions, one needs to understand the difficulty of producing this object with an algorithm. The student will investigate the complexity of various theorems, such as characterizations of the arc, the circle or more complicated spaces, or characterizations of the continuous images of the arc. There are several possible frameworks to investigate the difficulty of theorems, namely descriptive set theory [1], reverse mathematics [5] and Weihrauch degrees [6].
[2] H. Becker. Descriptive set theoretic phenomena in analysis and topology. In Set Theory of the Continuum, New York, 1992. Springer US.
[3] G. Debs and J. Saint Raymond. The descriptive complexity of connectedness in Polish spaces. Fundamenta Mathematicae, 249(3):261–286, 2020.
[4] D. E. Amir and M. Hoyrup. Descriptive complexity of topological invariants. Preprint, 2023.
[5] D. D. Dzhafarov, C. Mummert. Reverse Mathematics. Springer, 2022./
[6] V. Brattka, G. Gherardi, A. Pauly. Weihrauch Complexity in Computable Analysis. In Handbook of Computability and Complexity in Analysis, Springer, 2021.
