Bases de Gröbner en géométrie tropicale. // Gröbner Bases in Tropical Geometry

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

This thesis lies at the interface between computer algebra and tropical geometry. Its central
objective is to develop new algorithmic and theoretical tools for computing Gröbner bases in
settings endowed with a valuation or a tropical structure, and then to evaluate their relevance
on families of polynomial systems arising in particular from post-quantum cryptography.
The starting point is twofold. On the one hand, Gröbner bases play a fundamental role
in the effective computation of tropical varieties: the description of a tropical variety relies on
the study of initial ideals, and thus on algorithms sensitive to the choice of monomial order,
to the valuations of the coefficients, and to the combinatorial properties of the system under
consideration, as illustrated by numerous works including those of Maclagan, Sturmfels, Chan,
and Vaccon. On the other hand, in algebraic cryptanalysis, the practical difficulty of an attack
strongly depends on the degree reached by Macaulay/F4/F5-type computations and on the
choice of monomial order; invariants such as the solving degree, the last fall degree, or the
Castelnuovo–Mumford regularity provide partial bounds but remain insufficient as soon as nonhomogeneous,
weighted, or tropical structures are introduced. Several works, including those of
Caminata and Gorla, have investigated the relationships between these different bounds.
The thesis may be organized around four complementary directions. The first will focus on
the study of Hilbert-driven algorithms for the computation of tropical Gröbner bases, in the
spirit of Traverso and modern variants of F4/F5, in order to exploit information from Hilbert
series, or analogous series, to eliminate unnecessary reductions.
The second direction will address the optimization of the choice of term orders and weights,
especially in situations where certain valuations or primes make the computation significantly
more tractable on specific families of examples. This is the case of the Katsura 6 polynomial
system. Due to its difficulty, it is often used as a benchmark for Gröbner basis algorithms.
However, when p = 2 and the tropical weight is zero, some of the initial polynomials acquire
very simple leading terms: X1,X2,X6, and the computation of the corresponding Gröbner basis
becomes almost immediate. We will investigate structural heuristics, exploration of the Gröbner
cone, and, more speculatively, machine learning approaches to predict a good order or a good
reduction strategy.
The third direction will concern the search for tropical or valuated invariants capable of
controlling computational complexity, in the spirit of the solving degree, but adapted to the
tropical or analytic setting.
The fourth direction will focus on effectiveness in analytic tropical geometry: following recent
progress on Tate algebras, universal analytic bases, and polytopal affinoid algebras, several
questions remain open regarding the existence, finiteness, and effective computation of tropical
bases in this framework. This direction continues the work of Legrand's 2025 thesis.
Methodologically, the thesis will integrate computational experimentation, mathematical
proof, and validation against instances arising from cryptanalysis. On the tropical geometry side,
the aim is to broaden the scope of computable tropical varieties (both classical and analytic). On
the algebraic cryptanalysis side, the objective is not merely to accelerate existing computations,
but to understand which tropical, analytic, or weighted structures genuinely account for the
observed improvements, and to what extent they can lead to new complexity frameworks.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Début de la thèse : 01/10/2026

Public funding alone (i.e. government, region, European, international organization research grant)

Concours pour un contrat doctoral

Université de Limoges

653 Sciences et Ingénierie

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.
The student may have a solid mathematical background and some good knowledges in algebra and preferably in computer algebra and skills in Python or Sagemath.