GPT-5.6 et la conjecture de Dinitz-Garg-Goemans

Le 22 juillet 2026, Dmitry Rybin a publié sur X une affirmation qui a fait reposer la tasse de café à un certain public : GPT-5.6 Pro aurait produit un contre-exemple à la conjecture de Dinitz-Garg-Goemans, ouverte en optimisation combinatoire depuis environ 30 ans. La démonstration tenait en un petit graphe. Coût du flot fractionnaire : 58, coût du flot non sécable : 60. Deux points, trois décennies, quatre invites.

La plupart des articles reprennent les chiffres sans montrer le mécanisme qui les sous-tend, alors que c'est précisément là que se trouve la vraie leçon. C'est aussi là que je dois être transparent sur ce qui a été vérifié et ce qui ne l'a pas été. En bref : les concepts sont solides, la nouvelle est une revendication et pas encore un théorème, et si vous vous asseyez pour reconstruire exactement le graphe depuis zéro, vous comprenez immédiatement pourquoi ces problèmes sont difficiles dès que votre reconstruction fuit quelque part.

La réponse courte

Rybin rapporte que GPT-5.6 Pro, guidé par quatre invites totalisant moins de 60 mots, a produit un contre-exemple présumé à la conjecture de coût de Goemans, un problème ouvert depuis environ 1999. Son instance est un petit graphe orienté avec une source unique et trois terminaux de livraison. Il affirme que le routage sécable (fractionnaire) coûte 58, tandis que tout routage non sécable respectant le budget de congestion autorisé coûte au moins 60. Cet écart de deux points, s'il résiste à l'examen formel, suffit à faire tomber la conjecture.

Cela n'a pas été évalué par les pairs. Rybin a publié l'intégralité de la conversation ChatGPT afin que chacun puisse lire la construction, et plusieurs personnes ont vérifié son arithmétique et l'ont jugée cohérente. Une arithmétique reproductible et une preuve acceptée sont toutefois de nature différente, et la distance qui les sépare est le cœur de cet article.

Qu'est-ce que la conjecture de Dinitz-Garg-Goemans ?

Avant de mesurer ce qui est tombé, ou pourrait l'être, il faut comprendre ce que dit réellement la conjecture.

Imaginez un entrepôt qui expédie des commandes vers trois villes via un réseau routier. Si vous êtes autorisé à scinder un envoi, vous pouvez envoyer la moitié d'une commande par une route et l'autre moitié par une autre. C'est le routage fractionnaire, plus flexible : il trouve généralement des chemins moins coûteux. Mais une grande partie du fret réel ne peut pas être scindée. Une commande, un camion, une route, du départ à l'arrivée. C'est le flot non sécable, ce que doit effectivement faire un ordre de fret, un paquet réseau ou un conteneur maritime.

La question qui occupe les esprits depuis 1999 est simple à énoncer. S'il existe un routage sécable bon marché, peut-on toujours trouver un routage non sécable qui soit également peu coûteux sans surcharger excessivement les routes ?

Yefim Dinitz, Naveen Garg et Michel Goemans en ont résolu la moitié. L'autre moitié est celle que GPT-5.6 a attaquée. Pour comprendre pourquoi cette distinction est cruciale, il faut être précis.

Le théorème vs la conjecture

C'est la distinction que la plupart des articles brouillent, donc je vais la préciser une fois pour toutes, puis m'y référer tout au long de l'article.

Dinitz, Garg et Goemans ont démontré un résultat de congestion : étant donné un flot fractionnaire valide, on peut toujours le convertir en flot non sécable sans dépasser la capacité d'aucune route de plus que la plus grande demande, notée D. Ce théorème n'est pas remis en cause et ne l'a jamais été.

Ce que Goemans a séparément conjecturé est plus fort et tient compte du coût : la même conversion pourrait maintenir le coût total bas tout en maintenant la congestion basse. Congestion et coût, tous deux bornés, dans un seul routage. Le théorème « congestion seule » est sauf. La conjecture « coût plus congestion » est la partie que Rybin affirme avoir fait tomber. Si vous ne retenez qu'une phrase, c'est celle-ci. Une bonne partie de la couverture enthousiaste confond discrètement les deux, alors que la différence entre elles est précisément le fossé mathématique qu'il a fallu 30 ans pour combler.

Ce que GPT-5.6 a réellement construit

L'instance de Rybin est assez petite pour tenir en un paragraphe. Une source, quelques nœuds intermédiaires formant une « colonne vertébrale » partagée, et trois terminaux, chacun portant une demande. Chaque terminal dispose de deux chemins pour rentrer : un trajet direct coûteux, ou un détour gratuit via la colonne vertébrale partagée.

La tension est structurelle. Les détours bon marché se disputent la place sur la colonne vertébrale : si trop de terminaux tentent de passer « à bas coût » en même temps, une route de la colonne vertébrale déborde. Poussez assez loin et, dans tout routage non sécable valide, un seul terminal peut prendre son chemin bon marché. Les autres sont forcés de suivre leurs chemins directs coûteux, et le coût grimpe. Le flot fractionnaire, libre de se scinder, répartit chaque demande sur les deux chemins et passe sous chaque capacité en même temps. C'est ainsi que le coût fractionnaire devient inférieur au coût du meilleur non sécable légal. Les chiffres de Rybin pour son instance sont 58 et 60.

Je serai franc sur une limite. Je n'ai pas pu reproduire exactement le graphe de Rybin, ses capacités précises et ses conflits par paires, à partir d'une source primaire. Sa transcription décrit un point particulier d'une famille de paramètres, et la description largement partagée des « sept nœuds » en est une abstraction, pas une construction que j'ai vérifiée arête par arête. Je ne vais donc pas mettre en scène une dérivation proprette du 58 et prétendre que c'est la sienne. Ce que je peux faire, c'est vous proposer une instance autonome qui montre le même mécanisme, assez petite pour être vérifiée par force brute, afin que vous voyiez de vos propres yeux à quoi ressemble « le fractionnaire bat tout non sécable légal ». 

Quatre invites, plusieurs heures

Le nombre d'invites est l'aspect le moins intéressant de cette histoire, même si c'est celui qui a fait le buzz.

Le journal de discussion partagé par Rybin montre que le modèle a d'abord échoué, et a échoué honnêtement. L'invite d'ouverture lui demandait de trouver un contre-exemple structuré. Il a travaillé pendant près d'une heure et est revenu bredouille, déclarant clairement que présenter ce qu'il avait comme contre-exemple valide serait faux.

Prié de continuer, il a recommencé, et à nouveau n'a rien rapporté, décrivant comment chaque construction prometteuse finissait par faire apparaître une option de routage supplémentaire cachée qui détruisait la séparation coût-congestion une fois tous les chemins énumérés. Une troisième invite, demandant une stratégie plus propre, a abouti à un cadre plus étroit et toujours pas de résultat final.

Ce n'est pas « quatre invites et terminé ». Ce sont des heures pendant lesquelles un modèle se heurte à des murs et dit la vérité à leur sujet. Le mur spécifique sur lequel il butait, « un chemin supplémentaire apparaît et ruine la séparation », est exactement ce que la construction finale a été conçue pour empêcher, en fixant chaque terminal à exactement deux chemins, de sorte que l'espace de routage entier tienne en huit options que l'on peut énumérer à la main. Gardez ce mode d'échec en tête. Vous allez y être confronté vous-même.

La quatrième invite, rapportée comme quelque chose d'assez proche de « assez de tes échecs, termine avec un contre-exemple complet et inconditionnel », est celle qui a produit la construction fonctionnelle, avec certificats de preuve, un programme d'énumération et le LaTeX complet. La patience a compté. Les refus précédents aussi : ils étaient des auto-évaluations honnêtes.

Vérifiez par vous-même

Voici où la couverture DataCamp peut faire ce qu'un article d'actu ne peut pas : vous laisser exécuter la vérification.

Un avertissement rapide avant le code. Ce qui suit n'est pas le graphe de Rybin. C'est une instance schématique que j'ai construite pour être honnête : chaque terminal a réellement exactement deux routes, l'arithmétique se ferme, et l'écart est réel. Elle vous montre la forme d'un tel contre-exemple et la technique pour en vérifier un. Elle ne réfute rien à elle seule, et j'expliquerai pourquoi juste après l'exécution.

Le cadre : trois terminaux, chacun expédiant 10 unités, donc la plus grande demande D vaut 10. Chacun a un chemin direct coûteux (coût 30) et un chemin bon marché gratuit. Les chemins bon marché sont agencés de sorte que chaque paire d'entre eux se dispute son propre goulot d'étranglement : la route A est partagée par les terminaux 1 et 2, la route B par les terminaux 1 et 3, la route C par les terminaux 2 et 3. Dans le flot fractionnaire, chaque terminal envoie 2/5 de sa demande à bas coût et 3/5 via le cher, ce qui coûte 30 × 3/5 × 3 = 54. Chaque route porte alors 4 + 4 = 8 unités de manière fractionnaire, et le budget de congestion est cette charge plus D, donc 18.

Regardez maintenant ce que fait le routage non sécable. Deux terminaux qui passent tous deux par le bon marché déposent 10 + 10 = 20 unités sur leur route partagée, au-delà du budget de 18. Au plus un terminal peut donc emprunter le bon marché ; les deux autres paient 30 chacun. Coût minimal non sécable légal : 60. Contre un fractionnaire à 54. Huit routages existent, on les vérifie donc tous :

from itertools import product
	
# Three terminals, demand 10 each -> largest demand D = 10.
# Each has a cheap path (cost 0) and an expensive direct path (cost 30).
# Cheap paths pairwise share a PRIVATE bottleneck road, so every pair conflicts:
#   road A shared by {t1, t2},  road B by {t1, t3},  road C by {t2, t3}
# NOTE: this is a schematic instance to illustrate the check, not Rybin's graph.

demands = [10, 10, 10]
d_max = max(demands)          # congestion slack allowed on each road
cheap_frac = [2/5, 2/5, 2/5]  # expensive fraction is 3/5 each -> fractional cost 54
direct_cost = 30              # cost of one terminal's expensive path

# Which bottleneck roads each terminal's cheap path uses
uses = [
    {"A": True,  "B": True,  "C": False},  # t1: A, B
    {"A": True,  "B": False, "C": True},   # t2: A, C
    {"A": False, "B": True,  "C": True},   # t3: B, C
]

# The fractional flow saturates each road, so its load is that road's capacity
cap = {"A": 0.0, "B": 0.0, "C": 0.0}
for i in range(3):
    for road in cap:
        if uses[i][road]:
            cap[road] += cheap_frac[i] * demands[i]   # 8 units on each road

# Congestion rule: an unsplittable flow may exceed capacity by at most D
threshold = {road: cap[road] + d_max for road in cap}  # 18 on each road

fractional_cost = sum(direct_cost * (1 - cheap_frac[i]) for i in range(3))  # 54

print(f"Capacities (fractional load): {cap}")
print(f"Congestion budget per road  : {threshold}")
print(f"Fractional flow cost        : {fractional_cost}\n")
print(f"{'Route (0=cheap,1=exp)':22} {'Cost':>4} {'A':>3} {'B':>3} {'C':>3}  Valid")

valid_costs = []
for choices in product([0, 1], repeat=3):    # 0 = cheap, 1 = expensive
    cost = sum(direct_cost * c for c in choices)
    load = {"A": 0, "B": 0, "C": 0}
    for i, expensive in enumerate(choices):
        if expensive == 0:                    # this terminal takes its cheap path
            for road in load:
                if uses[i][road]:
                    load[road] += demands[i]
    ok = all(load[road] <= threshold[road] for road in load)
    tag = "OK" if ok else "overload"
    print(f"{str(choices):22} {cost:>4} {load['A']:>3} {load['B']:>3} {load['C']:>3}  {tag}")
    if ok:
        valid_costs.append(cost)

print(f"\nMin valid unsplittable cost: {min(valid_costs)}")
print(f"Gap: {min(valid_costs) - fractional_cost} (counterexample if > 0)")

Exécutez-le et vous obtenez un coût fractionnaire de 54, un coût minimal non sécable légal de 60, et un écart de 6. Les trois lignes en surcharge correspondent aux trois conflits par paires ; les seuls routages qui survivent laissent au plus un terminal en bon marché.

Alors la conjecture est morte ? Pas tout à fait, et c'est la partie promise. Cette énumération en huit lignes ne dit vrai que si chaque terminal a réellement deux routes et pas davantage. Construisez ce graphe avec de vraies routes et nœuds, et une quatrième route bon marché a tendance à apparaître par combinatoire. Un terminal trouve une troisième façon de rentrer, bon marché et sous budget, et l'écart se referme. Cette route supplémentaire est exactement l'échec que le modèle a rapporté lors de ses trois premières tentatives. Un petit « gadget » propre et symétrique qui briserait une conjecture vieille de 30 ans en huit lignes de Python serait trop beau pour être vrai, et il l'est. Le code ci-dessus prouve que le contrôle est sain et que la propriété visée est réelle. Savoir si un graphe donné possède effectivement cette propriété, sans « fuites », est la partie difficile, et c'est pourquoi l'instance réelle de Rybin est un point ajusté dans une famille de paramètres plutôt qu'un triangle propret.

Ce qui reste en suspens

Aucun article formel n'a encore paru. Rybin a partagé la conversation et la construction ; aucune n'a traversé le processus de relecture par des pairs qui permettrait à la communauté mathématique de clore officiellement la conjecture.

Le graphe exact publié n'a pas été reconstruit indépendamment à partir d'une source primaire que je puisse trouver. Les chiffres qui circulent viennent de son post et de la transcription partagée. Plusieurs chercheurs ont vérifié son arithmétique et l'ont dite cohérente, et l'un a montré que son instance s'inscrit dans une famille infinie à trois paramètres sur les mêmes nœuds, ce qui rendrait le résultat plus riche qu'une simple coïncidence heureuse. Encourageant, mais cela reste une vérification informelle par la communauté, pas un rapport de relecteur. Considérez le 58 contre 60 comme une revendication bien étayée, pas comme un fait établi.

Le théorème de congestion de 1999 n'est en rien affecté par tout cela.

Une tendance qui se dessine

Cette histoire n'est pas un cas isolé. C'est la troisième conjecture annoncée comme tombée avec l'aide de l'IA en environ trois mois, et la tendance mérite qu'on s'y attarde.

Le 20 juillet, Claude Fable 5 aurait aidé le mathématicien Levent Alpöge à trouver un contre-exemple à la conjecture jacobienne, un problème vieux de 87 ans. Avant cela, en mai, un modèle d'OpenAI aurait réfuté la conjecture d'Erdős sur les distances unitaires, vieille de 80 ans. La même semaine, un doctorant de Columbia a utilisé GPT-5.6 avec un workflow Codex structuré pour résoudre six problèmes ouverts d'Erdős en cinq jours. Le point commun, comme l'a formulé un chercheur, est que ces systèmes sont meilleurs pour réfuter que pour prouver. Un contre-exemple est un témoin unique que l'on peut vérifier ; une preuve doit couvrir tous les cas. Cette asymétrie semble déterminer quels problèmes tombent en premier.

La leçon pratique n'est pas « l'IA résout les maths ». Ce que nous observons, c'est l'IA qui agit comme un partenaire de recherche patient et exhaustif sur le plan combinatoire : capable d'énumérer des familles de paramètres, de garder en mémoire de travail les modes d'échec au fil des tentatives et de dire la vérité quand une construction ne se ferme pas. C'est une capacité spécifique et utile. Et si vous voulez comprendre où elle frappera probablement ensuite, la bonne question n'est pas quelles conjectures sont les plus anciennes, mais lesquelles peuvent être brisées par un témoin unique et vérifiable.