Aspects Calculatoires des Théorèmes Combinatoires – ACTC

Les mathématiques à rebours sont un programme fondationnel à l'intersection entre la calculabilité et la théorie de la preuve, dont le but est déterminer la puissance calculatoire des axiomes nécessaires pour prouver les mathématiques de tous les jours. Ce programme a permis de révéler un phénomène de structure des mathématiques d'un point de vue calculatoire, à savoir que la grande majorité des théorèmes ordinaires est équivalente à un parmi cinq ensembles d'axiomes. Malgré le succès du programme et son intérêt croissant dans la communauté, l'analyse calculatoire d'une sous-branche des mathématiques liée à la théorie de Ramsey présente une difficulté inattendue. Une grande partie des mathématiques à rebours moderne, et de la calculabilité en général, s'est mobilisée sur cette problématique, entraînant le développement de nouvelles techniques et de nouvelles branches de la calculabilité. Beaucoup de résultats ont été collectés concernant le contenu calculatoire de principes combinatoires, et ont permis le développement d'une méthodologie d'analyse calculatoire sur ces énoncés, ainsi qu'une compréhension relative de la nature calculatoire profonde de ces énoncés.

La précision de ces techniques laisse supposer l'existence d'une structure forte régissant le contenu calculatoire des principes combinatoires. Cependant, la nature permissive des phénomènes calculatoires permet souvent de construire des contre-exemples artificiels invalidant les observations faites sur des principes naturels. Notre projet d'ANR vise à donner un cadre formel aux heuristiques utilisées par la communauté, en transformant ces méthodologies en théorèmes généraux. Pour cela, il sera nécessaire de développer une théorie de la naturalité en calculabilité pour restreindre les problèmes considérés à une sous-classe de problèmes dit "naturels", et satisfaisant les propriétés de structure observées. Ce projet permettra notamment de renforcer la visibilité de la calculabilité en France, notamment en organisant une école d'été ainsi qu'une conférence internationale regroupant les experts en mathématiques à rebours et plus généralement en calculabilité.