Thèse Bases de Gröbner en Géométrie Tropicale. H/F - Doctorat.Gouv.Fr

Établissement : Université de Limoges École doctorale : Sciences et Ingénierie Laboratoire de recherche : XLIM Direction de la thèse : OLIVIER RUATTA ORCID 0009000991555012 Début de la thèse : 2026-10-01 Date limite de candidature : 2026-06-08T23:59:59 Cette thèse se situe à l'interface du calcul formel et de la géométrie tropicale. Son objectif central
est de développer de nouveaux outils algorithmiques et théoriques pour le calcul de bases de
Gröbner dans des cadres munis d'une valuation ou d'une structure tropicale, puis d'évaluer leur
intérêt d'une part pour des calculs effectifs de variétés tropicales, et d'autre part, pour l'étude
de familles de systèmes polynomiaux issues notamment de la cryptographie post-quantique.
Le point de départ est double. D'une part, les bases de Gröbner jouent un rôle fondamental
dans le calcul effectif des variétés tropicales : la description d'une variété tropicale passe par
l'étude des idéaux initiaux, et donc par des algorithmes sensibles au choix de l'ordre monomial,
aux valuations des coefficients et aux propriétés combinatoires du système considéré, ce qu'ont
illustré de nombreux travaux parmi lesquels ceux de Maclagan, Sturmfels, Chan ou Vaccon.
D'autre part, en cryptanalyse algébrique, la difficulté pratique d'une attaque dépend fortement
du degré atteint par les calculs de type Macaulay/F4/F5 et du choix de l'ordre monomial ; des
invariants comme le solving degree, le last fall degree ou la régularité de Castelnuovo-Mumford
fournissent des bornes partielles mais restent insuffisants dès que l'on introduit des structures
non homogènes, pondérées ou tropicales. De nombreux travaux dont ceux de Caminata et Gorla
ont cherché des liens entre ces différentes bornes.
La thèse pourra s'organiser autour de quatre axes complémentaires. Le premier visera l'étude
d'algorithmes Hilbert-driven pour le calcul de bases de Gröbner tropicales, dans l'esprit de
Traverso et des variantes modernes de F4/F5, afin d'exploiter des informations provenant des
séries de Hilbert, ou de séries analogues, pour éliminer des réductions inutiles.
Le deuxième axe portera sur l'optimisation du choix de l'ordre des termes et des poids, en
particulier lorsque certaines valuations ou certains premiers rendent le calcul beaucoup plus
accessible sur des familles d'exemples. C'est le cas du système de polynômes Katsura 6. De
part sa difficulté, il sert souvent d'étalon de mesure pour les algorithmes de calcul de bases
de Gröbner. Pourtant, quand p = 2 et le poids tropical est zéro, une partie des polynômes
initiaux prennent des termes de tête très simples : X1,X2,X6, et le calcul de la base de Gröbner
correspondante devient presque immédiat. On s'intéressera ici à des heuristiques structurelles, à
l'exploration du cône de Gröbner et, de façon plus exploratoire, à des approches d'apprentissage
automatique pour prédire un bon ordre ou une bonne stratégie de réduction.
Le troisième axe concernera la recherche d'invariants tropicaux ou valués capables de contrôler
la complexité du calcul, à l'image du solving degree, mais adaptés au cadre tropical ou
analytique.
Le quatrième axe portera sur l'effectivité en géométrie tropicale analytique : suite à des
progrès récents sur les algèbres de Tate, les bases de Gröbner analytiques universelles et les
algèbres affinoïdes polytopales, plusieurs questions restent ouvertes sur l'existence, la finitude
et le calcul effectif de bases tropicales dans ce cadre. Cet axe est en continuité avec la thèse de
Legrand de 2025.
Sur le plan méthodologique, la thèse articulera expérimentation informatique, preuve mathématique
et confrontation à des instances venues de la cryptanalyse. Côté géométrie tropicale, on
espère étendre le champs des calculs possibles de variétés tropicales (classiques ou analytiques).
Côté cryptanalyse algèbrique, l'ambition n'est pas seulement d'accélérer des calculs existants,
mais de comprendre quelles structures tropicales, analytiques ou pondérées expliquent réellement
les gains observés, et dans quelle mesure elles peuvent conduire à de nouveaux cadres de
complexité. Le calcul de bases de Gröbner est l'un des outils centraux du calcul formel moderne. Les algorithmes
de type Buchberger, F4 et F5 ont profondément transformé la résolution des systèmes
polynomiaux, mais leur coût reste extrêmement sensible à la structure de l'entrée et au choix de
l'ordre monomial [Buc65, Fau99, Fau02]. Parallèlement, la géométrie tropicale a montré qu'une
partie importante de l'information géométrique d'une variété algébrique peut être capturée par
des objets polyédraux obtenus via des idéaux initiaux et des valuations [MS15]. Cela place
naturellement les bases de Gröbner au coeur du calcul tropical effectif.
Dans le cadre valué, Chan et Maclagan ont étendu la théorie des bases de Gröbner aux
corps munis d'une valuation, ouvrant une voie directe vers le calcul tropical au-delà du cas de
valuation triviale [CM19]. Sur cette base, Vaccon et ses coauteurs ont adapté des algorithmes
de type Matrix-F5 et F5 au contexte tropical, avec des motivations à la fois algorithmiques
et numériques, notamment pour les calculs p-adiques [Vac15, VY17, VVY21]. En parallèle,
une théorie de bases de Gröbner sur les algèbres de Tate, puis sur des algèbres affinoïdes plus
générales, a émergé ; elle constitue un premier socle effectif pour la géométrie tropicale analytique
[CVV19, CVV20, CVV21, CVV22, VV23, BLV24].
Du côté de la cryptanalyse algébrique, les bases de Gröbner sont un outil standard pour
évaluer la résistance de schémas multivariés ou de primitives symétriques. Toutefois, la difficulté
pratique dépend moins des bornes de pire cas que d'invariants fins comme le solving degree, la
régularité ou la structure des syzygies [BFSY04, CG23, KPU24]. Or ces invariants restent
essentiellement calibrés pour des cadres homogènes ou semi-réguliers. Il existe donc un espace
de recherche important pour comprendre comment les valuations, les poids et les structures
tropicales modifient réellement le comportement des calculs.
L'objectif général de la thèse est de construire un cadre cohérent pour l'étude des bases de
Gröbner tropicales et analytiques, en reliant trois niveaux d'analyse :
1. le niveau algorithmique, avec la conception et l'implémentation d'algorithmes efficaces
inspirés de Buchberger, F4, F5 et des stratégies Hilbert-driven ;
2. le niveau structurel, avec l'étude du rôle des valuations, des poids, des ordres monomiaux,
des symétries et d'éventuels invariants tropicaux sur la complexité du calcul ;
3. le niveau applicatif, avec une validation sur des familles de systèmes polynomiaux pertinentes
pour la géométrie tropicale effective et pour la cryptanalyse algébrique.
De façon plus précise, on vise les objectifs suivants :
- proposer des variantes Hilbert-driven pour le calcul de bases de Gröbner tropicales ou
valuées ;
- étudier l'impact du choix du premier p, des poids et des ordres monomiaux sur la taille
des matrices de Macaulay et sur le degré atteint pendant le calcul ;
- définir ou tester des invariants tropicaux susceptibles de majorer, voire parfois de prédire,
la complexité des calculs ;
- explorer l'effectivité de la géométrie tropicale analytique, en particulier via les bases de
Gröbner analytiques universelles et les algèbres affinoïdes polytopales ;
- confronter ces développements à des systèmes issus de la cryptanalyse algébrique.

Le doctorant devra avoir de solides connaissances mathématiques, surtout en algèbre et de préférences des compétences en calcul formel et en programmation Python ou Sagemath.