Master en informatique théorique ou logique mathématique. Fort intérêt pour la calculabilité et la topologie.

Ce projet sera mené au sein de l’équipe Inria Mocqua, spécialisée dans l’étude des modèles de calcul émergents, avec un accent sur l’interaction entre calcul discret et structures continues.

Ce projet de thèse porte sur la complexité de la détection de propriétés topologiques d’ensembles. Le langage mathématique permet de définir des ensembles infinis et continus en utilisant seulement quelques symboles. L’ensemble des solutions d’une équation, ou l’attracteur d’un système dynamique en sont des exemples typiques. En revanche, une telle description finie ne donne pas d’information à propos de l’ensemble défini, en particulier sa topologie : ses propriétés de connexité, sa dimension, l’existence de trous, etc.

L’objectif de ce projet est, étant donné un accès à un sous-ensemble du plan ou d’un espace euclidien de dimension supérieure, de comprendre à quel point la topologie de l’ensemble peut être détectée, et quelle est la difficulté de cette détection. Ce sujet se trouve à l’intersection des domaines de la calculabilité, la logique et la topologie et nécessite l’emploi de techniques issues des mathématiques du continu. En particulier, la complexité est mesurée au moyen de la théorie descriptive des ensembles, qui fournit des hiérarchies et des classes de complexité de sous-ensembles d’espaces topologiques, et interagit fortement avec la logique [1].

Je sujet est vaste, nous proposons de suivre deux directions spécifiques.

Le premier axe est l’étude de la complexité des invariants topologiques. La littérature sur ce thème montre que la plupart des invariants fournis par la topologie sont de forte complexité (voir [2] et [3] par exemple). Ainsi, il est nécessaire d’identifier des propriétés qui peuvent être détectées au moyen d’un faible niveau de complexité. Nous proposons plusieurs approches pour aborder ce problème. Étant donné une classe particulière d’espaces, il s’agira de déterminer la complexité minimal nécessaire pour séparer tous les espaces de cette classe. Le cas d’une classe contenant deux espaces sera particulièrement intéressant. Une autre piste consiste, pour chaque espace particulier, à identifier la complexité du problème ‘être homéomorphe’ à cet esapce. Un premier pas dans cette direction a été obtenu dans [4], où le cas des graphes topologiques finis est traité. Le cas général des complexes simpliciaux finis reste à élucider.

Le deuxième axe concerne la complexité des théorèmes issus de la topologie. Lorsqu’un théorème certifie l’existence d’un objet sous certaines conditions, se pose la question de la difficulté de produire cet objet au moyen d’un algorithme. L’étudiant(e) se penchera sur la complexité de divers théorèmes, tels que des caractérisations de l’arc, du cercle ou d’autres espaces, ou encore des caractérisations des images continues d’un arc. Plusieurs cadres pourront être envisagés pour mener cette étude, à savoir la théorie descriptive des ensembles [1], les mathématiques à rebours [5] ou bien les degrés de Weihrauch [6].

Cette thèse sera encadrée par Mathieu Hoyrup dans l’équipe Mocqua (LORIA, Inria).

Les travaux mèneront à des publications dans des conférences et journaux internationaux.

[1] A. S. Kechris. Classical Descriptive Set Theory. Springer, January 1995.
[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.