# Arbres de cas : regrouper les connexions sur les grands bords ## Le problème Une règle à marques fixes se rédige en quelques conditions « si ces rubans existent, les échanger », plus la liste de toutes les façons dont les marques peuvent être reliées à leurs partenaires (`4CT_marques_fixes.md`). Sur les bords ≤ 11, cette liste est courte (7 à 42 cas). Sur les bords 12 à 14, elle s'allonge : 54 à 87 cas en médiane pour les déductions d'intervalle, jusqu'à 359, et 297 en médiane pour les états hors catalogue (`4CT_intervalles.md`, section « Forme lisible »). La liste est vérifiable, mais elle n'est plus courte. ## L'idée : poser les questions une à une Au lieu d'énumérer toutes les connexions des marques, on raisonne par cas sur l'appariement réel, une question à la fois : - **Racine.** On fixe θ, avant de connaître l'extérieur. Les arêtes actives (de couleur ≠ θ) sont reliées deux à deux, sans croisement, par les rubans de l'extérieur réel (lemme de consistance de RSST, cité). - **Nœud.** On demande : « à quelle arête est relié le ruban de l'arête p ? ». Il y a une branche par réponse possible. Les réponses possibles se lisent directement : une arête q de la même région que p (délimitée par les rubans déjà connus), telle que le ruban p–q laisse de chaque côté un nombre pair d'arêtes actives encore libres. Quand une seule réponse est possible, le ruban est **forcé**. - **Feuille.** On s'arrête dès que les rubans connus le long de la branche contiennent un ensemble dont l'échange fait descendre le rang. La feuille nomme cet échange et le mot obtenu. L'appariement réel suit exactement une branche. Sa feuille nomme des rubans qui existent tous, et leur échange donne un mot de rang strictement inférieur. C'est une preuve complète de l'élimination du mot, sans aucune énumération d'appariements. Échanger plusieurs rubans applique la permutation de θ (1↔2 et 3↔4 si θ = 1 ; 1↔3 et 2↔4 si θ = 2 ; 1↔4 et 2↔3 si θ = 3) aux sommets de bord couverts un nombre impair de fois par les intervalles X+1..Y des rubans échangés. Les règles à marques fixes sont un cas particulier : un arbre qui pose ses questions sur les marques, dans un ordre fixe. L'arbre, lui, choisit à chaque nœud l'arête à interroger selon les réponses précédentes ; c'est ce qui le raccourcit. `experiments/decision_trees.py` calcule l'arbre qui a le moins de feuilles (programmation dynamique exacte sur les ensembles de rubans connus), sur les trois choix de θ. ## Résultats `experiments/decision_tree_survey.py` (environ 10 min). Les rangs viennent de la chaîne des règles d'échange rejouée par le programme C. Chaque arbre est vérifié indépendamment de sa construction : on énumère tous les appariements sans croisement, on suit la branche de chacun, et on vérifie que la feuille nomme des rubans présents, que la cible recalculée est exacte et que son rang est inférieur. | Ensemble | Mots | Feuilles (min / méd. / max) | Connexions des marques, mêmes mots (min / méd. / max) | | --- | ---: | --- | --- | | Intervalle, bords ≤ 11 (tous) | 303 | 6 / 9 / 15 | 25 / 33 / 42 | | Marques fixes, bord 12 (échantillon) | 96 | 4 / 6 / 11 | 10 / 21 / 57 | | Marques fixes, bord 13 (échantillon) | 96 | 4 / 6 / 11 | 10 / 21 / 64 | | Marques fixes, bord 14 (échantillon) | 96 | 4 / 6 / 14 | 10 / 24 / 90 | | Intervalle, bord 12 (échantillon) | 96 | 6 / 9 / 17 | 25 / 54 / 113 | | Intervalle, bord 13 (échantillon) | 96 | 6 / 9 / 23 | 30 / 71 / 108 | | Intervalle, bord 14 (échantillon) | 96 | 6 / 10 / 25 | 30 / 87 / 359 | | Hors catalogue (tous) | 520 | 12 / 24 / 53 | 64 / 297 / 359 (379 mots) | - **Pour chacun des 1 258 mots qui ont une règle à au plus cinq marques, l'arbre a moins de feuilles que la liste des connexions n'a de cas** (sur 1 399 mots traités). En médiane, le gain va d'un facteur 3,5 (marques fixes) à 8,7 (intervalle, bord 14), et 12,4 pour les états hors catalogue. - **Aucune branche ne pose plus de 5 questions** ; les échanges nommés aux feuilles portent sur au plus 5 rubans, et le plus souvent 2 ou 3. - **Les 141 états hors catalogue sans règle à au plus cinq marques ont tous un arbre**, de 12 à 53 feuilles. L'échantillon : 8 configurations tirées au hasard par taille de bord (graine fixée), puis 12 mots par configuration et par groupe (règles à marques fixes, règles d'intervalle). La section suivante remplace cet échantillon par le corpus entier. ## Tout le corpus, en C La recherche est portée en C (`experiments/case_trees.inc.c`), dans la copie instrumentée de `interval_rules.c` qui dispose déjà des rangs et calcule en temps constant le mot obtenu par un échange (par sa clé de couleurs d'arêtes). Les appariements sans croisement y sont énumérés comme mots de Dyck ; la programmation dynamique exacte, avec élagage, porte sur les ensembles de rubans connus codés sur 64 bits ; chaque arbre retenu est vérifié en suivant tous les appariements jusqu'à leur feuille. `experiments/run_case_trees.py` le lance sur les 633 configurations, en 4 processus (38 min, 2 h 30 de CPU). **Les 29 991 189 déductions éliminées par échange ont chacune un arbre de cas vérifié.** Aucun échec, aucun débordement de la table de hachage, et les effectifs de chaque groupe coïncident, configuration par configuration, avec `experiments/exchange_link.csv`. | Règle qui classait la déduction | Déductions | Feuilles (méd. / 99 % / max) | Questions au plus | Plus grand échange | | --- | ---: | --- | ---: | ---: | | Un ruban (étoile, oreilles, séparation) | 23 746 169 | 4 / 7 / 14 | 3 | 5 rubans | | Marques fixes | 5 752 626 | 6 / 11 / 22 | 4 | 5 rubans | | Intervalle | 491 874 | 10 / 20 / 51 | 5 | 6 rubans | | Hors catalogue d'intervalle | 520 | 24 / 45 / 53 | 5 | 5 rubans | Autrement dit : **toute déduction de recoloration du corpus se justifie par au plus 53 cas, obtenus en posant au plus 5 questions sur l'appariement extérieur réel** ; 99 % en demandent au plus 11 (au plus 20 pour les règles d'intervalle), et la moitié au plus 4 à 10 selon le groupe. Le détail par configuration et par taille de bord est dans `experiments/case_trees.csv` et `experiments/case_trees_summary.json`. **Contrôle croisé.** Les versions C et Python sont écrites indépendamment (énumération des appariements, calcul des mots cibles, tables de rangs). `experiments/compare_case_trees.py` les compare mot par mot sur 1 424 déductions : toutes celles d'intervalle et hors catalogue des bords ≤ 11, 1 000 autres tirées au hasard sur ces bords, 60 dans chacune de deux configurations de bord 14 tirées au hasard, et `128.25876`. Même nombre de feuilles, même profondeur, même plus grand échange dans les 1 424 cas. ## Schémas communs Un arbre ne dépend du mot que par ses feuilles : chacune doit nommer, parmi les rubans connus sur sa branche, un échange qui fait baisser le rang. Tout le reste — quelles questions poser, sur quelles arêtes — ne dépend que du nombre 2m d'arêtes actives. On appelle **forme** d'un arbre la suite de ses questions écrite en positions relatives (0 = première arête active), sans les feuilles, en omettant les questions à réponse unique (rubans forcés), et normalisée à rotation et symétrie du cycle près. Une forme couvre toujours tous les appariements, puisque chaque question a une branche par partenaire possible. Pour l'appliquer à un mot, il suffit donc de vérifier ses feuilles. `experiments/run_case_schemas.py` (44 min sur 4 cœurs) calcule la forme canonique de chacun des 29 991 189 arbres, dans le programme C : ``` formes distinctes 60 321 (484 453 schémas complets, feuilles comprises) formes pour couvrir 50 % 2 90 % 11 99 % 505 99,9 % 30 330 100 % 60 321 questions sur la plus longue branche 1 24 804 189 82,7 % (étoile) 2 4 877 548 16,3 % 3 304 256 1,0 % 4 ou 5 5 196 ``` Deux constats : - **Quatre étoiles (une seule question, sur 6, 8, 10 ou 12 arêtes actives) couvrent 81,4 % du corpus**, et onze formes en couvrent 90 %. L'étoile généralise la règle d'étoile à un ruban : il suffit que, pour chaque partenaire possible de l'arête interrogée, les rubans alors connus (celui-ci et ceux qu'il force) contiennent un échange utile. C'est pourquoi 1,99 million de déductions que classaient les règles à marques fixes sont en fait des étoiles. - **La traîne est longue** : au-delà de 99 %, presque chaque déduction a sa propre forme, surtout parmi les règles d'intervalle (51 973 formes pour 491 874 déductions) et les états hors catalogue (502 formes pour 520). Ces derniers cas restent vérifiables un par un, mais ne se regroupent pas. La part des étoiles est exacte et pas seulement observée : toute forme a au moins m branches à la racine et une étoile en a exactement m, donc si une étoile convient à un mot, son arbre optimal est une étoile. `dossiers/catalogue_des_formes.md` décrit les 30 formes les plus fréquentes (95,25 % du corpus), chacune avec un exemple réel, et donne l'arbre complet des exemples des six premières. `experiments/build_schema_catalogue.py` recalcule ces arbres en Python et vérifie, par une canonisation écrite indépendamment, que leur forme est bien celle du catalogue (0 écart). ### Familles plus larges La traîne se regroupe si l'on oublie, dans les sous-arbres, *quelle* arête chaque sous-question interroge, pour ne garder que son nombre de réponses : c'est le **squelette** d'un arbre. Pour l'appliquer à un mot, il faut alors donner en plus un entier par sous-question. `experiments/build_shape_families.py`, à partir de toutes les formes (`experiments/case_schemas_all.json.gz`), compare quatre niveaux de regroupement : | Niveau | Familles | pour 99 % | pour 99,9 % | Traîne : pour 90 % | | --- | ---: | ---: | ---: | ---: | | Forme exacte | 60 321 | 505 | 30 330 | 29 844 | | Squelette | 6 643 | 35 | 300 | 278 | | Profil | 5 029 | 31 | 202 | 181 | | Gabarit (n, questions, profondeur) | 102 | 14 | 25 | 15 | | Type (questions, profondeur) | 52 | 4 | 8 | 6 | Le squelette divise par 100 le nombre de familles nécessaires pour couvrir 99,9 % du corpus, en restant une preuve type. Gabarit et type ne disent plus quelles questions poser : ils classent, sans prouver. L'extrême traîne, elle, résiste : les derniers 0,01 % demandent encore près de 3 000 squelettes, et les états hors catalogue en ont 471 pour 520 déductions. Détail et descriptions en clair : `dossiers/familles_de_formes.md`. ## `128.25876` a désormais un argument lisible Le mot `12323212343232` de `128.25876` était le seul des 29 991 189 mots éliminés par échange à n'avoir aucune règle lisible : ni un ruban, ni marques fixes, ni intervalle, ni la règle à deux catégories, et aucune règle à au plus cinq marques. Il reçoit un arbre de **50 cas**, de profondeur 4, avec des échanges d'au plus 4 rubans, vérifié sur les 429 appariements : `dossiers/128.25876_12323212343232.md`. Il n'est donc plus couvert par le seul certificat général. Et depuis le calcul complet en C, chaque mot éliminé par échange admet un arbre de cas vérifié, de 53 cas au plus. ## Portée Un arbre de cas est une preuve de l'élimination d'un mot **relativement à l'ordre des rangs** : chaque feuille renvoie à un mot de rang inférieur, lui-même justifié par sa propre règle. Les rangs restent ceux du certificat calculé ; les dossiers de `dossiers/` montrent comment la chaîne entière se lit sur les petites configurations. Le lemme de consistance de RSST, qui garantit l'existence des rubans, reste cité.