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 leur café à certains lecteurs avertis : GPT-5.6 Pro aurait produit un contre-exemple à la conjecture de Dinitz-Garg-Goemans, ouverte en optimisation combinatoire depuis environ 30 ans. La preuve de concept tient dans un petit graphe. Coût du flot fractionnaire : 58, coût du flot indivisible : 60. Deux points d’écart, trois décennies, quatre prompts.

La plupart des articles reprennent les chiffres sans expliquer le mécanisme qui les sous-tend, alors que tout l’enseignement est là. C’est aussi le point où je dois être clair sur ce qui a été vérifié et ce qui ne l’a pas été. En bref : les concepts tiennent la route, la nouvelle reste une affirmation et pas encore un théorème, et si vous essayez de reconstruire exactement le graphe depuis zéro, vous comprendrez dès que votre reconstruction fuit pourquoi ce type de problème est difficile.

La réponse courte

Rybin rapporte que GPT-5.6 Pro, guidé par quatre prompts totalisant moins de 60 mots, a produit un contre-exemple supposé à la conjecture de coût de Goemans, un problème ouvert depuis environ 1999. Son instance est un petit graphe orienté avec une unique source et trois terminaux de livraison. Il indique que le routage sécable (fractionnaire) coûte 58, tandis que tout routage indivisible maintenant la congestion dans le budget 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 fait l’objet d’une relecture par les pairs. Rybin a publié l’intégralité de la conversation ChatGPT pour 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 deux choses différentes, et la distance entre les deux est précisément le sujet 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 à trois villes via un réseau routier. Si vous êtes autorisé à scinder une expédition, vous pouvez envoyer la moitié d’une commande par une route et l’autre moitié par une autre. C’est le routage fractionnaire, flexible : il trouve généralement des chemins moins coûteux. Mais beaucoup de fret réel ne peut pas être scindé. Une commande, un camion, une route, du départ à l’arrivée. C’est le flot indivisible, et c’est ainsi que doivent voyager un ordre de fret, un paquet réseau ou un conteneur.

La question que l’on se pose depuis 1999 est simple à formuler. Si un routage fractionnaire peu coûteux existe, peut-on toujours trouver un routage indivisible qui soit également peu coûteux, sans surcharger exagérément les routes ?

Yefim Dinitz, Naveen Garg et Michel Goemans ont réglé la moitié du problème. L’autre moitié est celle que GPT-5.6 a visé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 estompent, donc je vais la préciser une fois pour toutes et m’y référer dans la suite.

Dinitz, Garg et Goemans ont démontré un résultat de congestion : à partir d’un flot fractionnaire valide, on peut toujours le convertir en flot indivisible 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 intègre le coût : la même conversion pourrait maintenir le coût total tout en maintenant la congestion. Congestion et coût, tous deux bornés, dans un seul routage. Le théorème « congestion seule » est solide. La conjecture « coût plus congestion » est la partie que Rybin dit avoir fait tomber. S’il ne fallait retenir qu’une phrase, c’est celle-ci. Beaucoup de couvertures enthousiastes confondent discrètement les deux, et la différence entre elles est l’écart 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 être décrite en un paragraphe. Une source, quelques nœuds intermédiaires formant une « épine dorsale » partagée, et trois terminaux, chacun portant une demande. Chaque terminal dispose de deux chemins : une route directe coûteuse, ou un détour gratuit via l’épine dorsale partagée.

La tension est structurelle. Les détours bon marché se disputent la place sur l’épine : si trop de terminaux tentent de passer par le chemin économique en même temps, une route de l’épine sature. En poussant suffisamment, un seul terminal peut emprunter son chemin bon marché dans tout routage indivisible valide. Les autres sont forcés sur leurs routes directes coûteuses, et le coût grimpe. Le flot fractionnaire, libre de se scinder, répartit chaque demande sur les deux chemins et passe sous toutes les capacités à la fois. C’est ainsi qu’on obtient un coût fractionnaire inférieur au moindre coût indivisible légal. Les chiffres de Rybin pour son instance sont 58 et 60.

Je vais être franc sur une limite. Je n’ai pas pu reproduire exactement le graphe de Rybin, ses capacités spécifiques et ses conflits par paires, à partir d’une source primaire. Sa transcription décrit un point particulier dans une famille de paramètres, et la fameuse description « à sept nœuds » qui circule 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 propre de 58 et prétendre que c’est la sienne. Ce que je peux faire, c’est vous proposer une instance autonome qui illustre le même mécanisme, suffisamment petite pour être vérifiée par force brute, afin que vous voyiez concrètement à quoi ressemble « un fractionnaire bat tout indivisible légal ». 

Quatre prompts, plusieurs heures

Le nombre de prompts est l’aspect le moins intéressant de cette histoire, même si c’est celui qui est devenu viral.

Le journal de chat partagé par Rybin montre que le modèle a d’abord échoué, et qu’il a échoué honnêtement. Le prompt initial lui demandait de trouver un contre-exemple structuré. Il a travaillé pendant une bonne heure et est revenu bredouille, indiquant clairement que présenter ce qu’il avait comme un contre-exemple valide serait faux.

Invité à poursuivre, il a relancé, et là encore n’a rien produit, expliquant comment chaque construction prometteuse finissait par révéler une option de routage cachée qui détruisait la séparation coût-congestion une fois tous les chemins énumérés. Un troisième prompt, demandant une stratégie plus propre, a resserré le cadre… et toujours pas de résultat final.

Ce n’est pas « quatre prompts et c’est plié ». Ce sont des heures d’un modèle qui se heurte à des murs et le reconnaît. Le mur rencontré à répétition — une route supplémentaire apparaît et ruine la séparation — est précisément ce que la construction finale a été conçue pour éviter, en fixant chaque terminal à exactement deux chemins afin que tout l’espace de routage se réduise à 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.

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

Vérifiez par vous-même

Voici où la couverture DataCamp peut faire ce qu’un article d’actualité ne peut pas : vous laisser lancer 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 y a réellement exactement deux chemins, 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 le vérifier. Elle ne réfute rien à elle seule, et j’explique 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 arrangés de sorte que chaque paire entre en conflit sur sa propre route-goulot d’étranglement : la route A est partagée par les terminaux 1 et 2, la route B par 1 et 3, la route C par 2 et 3. Dans le flot fractionnaire, chaque terminal envoie 2/5 de sa demande sur le bon marché et 3/5 sur le coûteux, pour un coût de 30 × 3/5 × 3 = 54. Chaque route porte alors 4 + 4 = 8 unités fractionnaires, et le budget de congestion est cette charge plus D, soit 18.

Regardez maintenant ce que fait le routage indivisible. Deux terminaux qui prennent tous deux le bon marché chargent 10 + 10 = 20 unités sur leur route partagée, au-delà du budget de 18. Donc au plus un terminal peut emprunter son chemin bon marché ; les deux autres paient 30 chacun. Coût minimal indivisible légal : 60. Contre un fractionnaire de 54. Il existe huit routages, 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)")

À l’exécution, vous obtenez un coût fractionnaire de 54, un coût minimal indivisible légal de 60 et un écart de 6. Les trois lignes en surcharge sont les conflits par paires ; les seuls routages valides gardent au plus un terminal sur le bon marché.

Donc 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 chemins et pas plus. Quand on construit ce graphe avec de vraies routes et de vrais nœuds, un quatrième chemin bon marché a tendance à apparaître par simple combinatoire. Un terminal trouve une troisième voie économique qui reste sous budget, et l’écart disparaît. Ce chemin supplémentaire est exactement l’échec que le modèle a rencontré lors de ses trois premiers essais. Un gadget propre et symétrique qui briserait une conjecture trentenaire en huit lignes de Python serait trop beau pour être vrai, et il l’est. Le code ci-dessus prouve que la méthode de vérification est solide 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 vraie difficulté, et c’est pourquoi l’instance réelle de Rybin est un point ajusté dans une famille de paramètres plutôt qu’un simple triangle.

Ce qui reste en suspens

Aucun article formel n’a été publié. Rybin a partagé la conversation et la construction ; ni l’une ni l’autre n’ont traversé le processus de relecture par les pairs qui permettrait à la communauté mathématique de clore officiellement la conjecture.

Le graphe exact publié n’a pas, à ma connaissance, été reconstruit indépendamment depuis une source primaire. 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 jugée cohérente, et l’un d’eux a montré que son instance s’inscrivait 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. Encourageant, mais cela reste une vérification communautaire informelle, pas un rapport de rapporteur. Considérez le 58-contre-60 comme une affirmation solide, pas un fait établi.

Le théorème de congestion de 1999 reste intact.

Un élément d’un mouvement de fond

Cette histoire n’est pas un point isolé. C’est la troisième conjecture annoncée comme tombée avec l’aide de l’IA en environ trois mois, et le motif mérite l’attention.

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 la distance unité, âgée 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 fil conducteur, comme l’a résumé 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 les problèmes qui tombent en premier.

La conclusion pratique n’est pas « l’IA résout les maths ». Nous voyons l’IA travailler comme un partenaire patient d’exploration combinatoire exhaustive : capable d’énumérer des familles de paramètres, de conserver en mémoire de travail les modes d’échec d’une tentative à l’autre, et de dire la vérité quand une construction ne ferme pas. C’est une capacité précise 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.