Dans un cahier de préparations, Alice note une commande très simple en apparence : produire x¹⁵. Elle ne cherche ni une valeur approchée ni le résultat d'une mesure. Le signe x désigne une variable formelle, et chaque ligne doit être obtenue en multipliant deux puissances déjà disponibles. La page reçoit aussi une seconde commande, x²³. Nous comparerons des préparations remplies, puis changerons les permissions de conservation et de multiplication pour voir lesquelles restent exécutables.
Les références suivantes fournissent seulement leurs catégories textuelles. Les images ne sont pas examinées et aucun procédé artistique ne détermine nos opérations.
P1 — https://www.metmuseum.org/art/collection/search/338220 : Prints.
P2 — https://www.metmuseum.org/art/collection/search/338230 : Drawings.
P3 — https://www.metmuseum.org/art/collection/search/338240 : Drawings.
Le modèle de départ donne x gratuitement. Une multiplication produit une nouvelle puissance et coûte une opération, y compris lorsqu'on multiplie une puissance par elle-même. Les résultats intermédiaires peuvent d'abord être conservés sans limite. Nous interdisons division, soustraction de puissances et connaissance d'une valeur particulière de x. Si x valait déjà un, toutes ces puissances coïncideraient ; cette simplification numérique n'appartient pas à la commande formelle. Les entiers inscrits sur les feuilles désignent donc des exposants, pas des valeurs calculées.
Quinze avec cinq multiplications, et pourquoi quatre ne suffisent pas
Alice remplit la préparation par les exposants 1, 2, 3, 5, 10, 15. Elle obtient x² en multipliant x par x, puis x³ avec x² et x. La troisième opération réunit x³ et x² pour produire x⁵ ; la quatrième met x⁵ au carré ; la cinquième multiplie x¹⁰ par x⁵. La feuille de x² reste nécessaire jusqu'à la fabrication de x⁵, et celle de x⁵ jusqu'au dernier produit. Il y a cinq opérations, même si trois puissances intermédiaires ne figurent pas dans le résultat remis. Alice garde leurs parents auprès de chaque ligne : le total quinze ne dit pas quels nombres étaient disponibles lorsqu'elle l'a obtenu.
Une préparation qui suit les chiffres binaires peut passer par 1, 2, 3, 6, 7, 14, 15 et utiliser six multiplications. Elle est correcte ; nous ne créditons pas comme nouvelle méthode le principe classique de mise au carré et de multiplication par x. La différence remplie ici est l'autorisation de choisir x⁵ comme intermédiaire, puis de le réutiliser au dernier produit, plutôt que de suivre cette succession imposée. La préparation à cinq opérations change réellement les parents du produit final, sans changer la puissance demandée.
Pour exclure quatre multiplications, Alice regarde le dernier produit avant de chercher toutes les préparations. Quinze est impair ; ce produit ne peut donc pas mettre une puissance au carré. Il doit réunir deux exposants distincts déjà obtenus. Après trois opérations, le plus grand exposant disponible est au plus huit : chaque nouvelle multiplication peut au mieux doubler le plus grand précédent. Parmi les autres exposants, le plus grand est au plus quatre, puisqu'il a dû être disponible après seulement deux opérations. Les deux parents distincts du dernier produit ont donc une somme au plus douze. Ils ne peuvent donner quinze, même si la troisième opération avait atteint huit.
Cette borne suppose que les opérations utiles sont rangées par exposants croissants. Alice peut effectuer ce rangement dans notre premier modèle : les parents d'un exposant positif sont tous deux strictement plus petits que leur somme. Un résultat plus grand que quinze ne peut contribuer à quinze par les seuls produits autorisés ; elle l'écarte. Des résultats identiques produits deux fois n'ajoutent rien lorsqu'elle peut garder le premier. Ainsi, tout candidat à quatre opérations utiles fournit une liste croissante dont la dernière ligne est quinze. Le rangement ne suppose pas que les parents soient voisins dans cette liste ; il conserve précisément toutes les puissances antérieures dont la multiplication aurait besoin.
Le refus de quatre n'est pas seulement une comparaison avec la préparation binaire. Alice pourrait inventer une autre troisième puissance, mais elle resterait soumise aux deux bornes huit et quatre pour les parents finaux distincts. La chaîne remplie à cinq atteint donc un minimum dans ce modèle, et non un record parmi deux essais. Elle remet les cinq lignes de produits avec cette impossibilité séparée. La preuve ne promet aucun gain de temps sur une machine : une multiplication de deux objets très différents pourrait avoir un autre prix. Ici, le prix annoncé est celui d'une opération autorisée sur les feuilles formelles.
Vingt-trois oblige à conserver une petite puissance
Pour x²³, Alice conserve la préparation 1, 2, 3, 5, 10, 20, 23. Les cinq premières opérations produisent successivement x², x³, x⁵, x¹⁰ et x²⁰. Le dernier produit utilise x²⁰ et x³ ; il ne multiplie pas par x. La feuille de x³ traverse donc les mises au carré suivantes sans être consommée définitivement. Une liste qui ne montre que le dernier résultat après chaque opération cacherait cette obligation : le passage de vingt à vingt-trois est possible grâce à une puissance plus ancienne, pas à une opération qui ajouterait gratuitement trois à l'exposant.
Alice exclut ensuite cinq opérations par le même examen final, mais la première borne grossière ne suffit plus. Vingt-trois étant impair, les deux parents sont distincts. Le plus petit est au plus huit après les trois premières opérations ; le plus grand, produit au plus tard par la quatrième, est au plus seize. Si ce plus grand exposant ne dépasse pas quatorze, leur somme ne dépasse pas vingt-deux. Il faudrait donc qu'il soit quinze ou seize. Quinze a déjà été exclu en quatre opérations par notre preuve précédente. Le seul cas encore ouvert est seize : Alice ne le confond pas avec n'importe quelle puissance proche de la cible.
Atteindre seize en quatre multiplications oblige chaque étape à doubler le maximum antérieur. La liste est alors 1, 2, 4, 8, 16 : perdre un doublement laisserait le maximum final strictement sous seize. Pour compléter vingt-trois, il faudrait ajouter sept à seize par multiplication des puissances correspondantes, mais sept n'est pas dans cette liste. Aucun autre parent disponible ne convient. Ce dernier cas est donc fermé lui aussi, et six multiplications sont nécessaires. La préparation conservant trois les réalise. Alice garde dans son refus les deux conditions différentes : un grand parent assez élevé et le petit complément effectivement présent, car la première ne garantit pas la seconde.
Elle aurait pu choisir une autre chaîne à six, par exemple 1, 2, 3, 5, 10, 13, 23. Dans cette variante, treize est obtenu avec dix et trois, puis vingt-trois avec treize et dix. Alice n'attribue pas une nouvelle utilité au simple changement de cette liste ; elle s'en sert seulement pour contrôler que sa commande ne désignait pas une chaîne unique. La préparation retenue passe par vingt parce qu'elle permettra ensuite une trace claire avec deux emplacements. La preuve du minimum porte sur toutes les chaînes à cinq, tandis que le choix entre chaînes à six dépend d'une permission de conservation que nous n'avons pas encore imposée.
Un emplacement réinscriptible ne garde pas tous les parents
Nous ouvrons maintenant une branche où x reste disponible en lecture seule, mais où un seul emplacement peut contenir un résultat nouveau. La multiplication lit ses entrées avant de remplacer le contenu de cet emplacement. La mémoire illimitée du premier modèle disparaît ; les comptes de cinq et six restent les minima de ce modèle ancien. Aucun prix de copie matérielle n'est inventé ici. Nous précisons seulement quels parents la prochaine multiplication peut encore lire, et toute opération de reconstruction devrait être comptée comme un produit supplémentaire, avec des entrées réellement conservées.
Si l'emplacement contient xᵃ, Alice ne peut lire que cette puissance et x. Les nouveaux exposants possibles sont donc 2a, en mettant le contenu au carré, ou a+1, en le multipliant par x. Reproduire x² à partir de x et x reste possible, mais efface alors le contenu antérieur ; une opération qui ferait reculer ainsi peut être retirée d'une préparation minimale, puisque x n'a jamais cessé d'être disponible. Pour une chaîne utile croissante, le premier modèle permettait d'additionner deux anciens exposants quelconques ; celui-ci ne permet que doubler le courant ou lui ajouter un. La liste à cinq pour quinze échoue précisément au passage de trois à cinq.
Alice peut vérifier ce refus sans discuter abstraitement de la quantité de mémoire. Après avoir écrit deux, elle produit trois dans le même emplacement et perd deux. L'instruction « multiplier x³ par x² » lit une feuille qui n'existe plus. Produire deux à nouveau dans l'emplacement ne répare pas cette instruction : elle perdrait cette fois trois. Garder ce dernier ailleurs réintroduirait un second emplacement interdit. Le problème n'est donc pas qu'une ancienne ligne aurait été mal copiée dans le cahier ; la préparation à cinq utilise une permission de maintien simultané que cette branche retire. Alice la refuse avant d'exécuter son troisième produit impossible.
Elle calcule alors le minimum autorisé avec un seul emplacement. Pour un exposant impair n supérieur à un, la dernière opération ne peut être un doublement : elle vient obligatoirement de n−1 et coûte un de plus. Pour un exposant pair, les deux parents possibles de la dernière étape sont n−1, suivi d'une multiplication par x, ou n/2, suivi d'une mise au carré. Elle garde le moins cher de ces deux chemins. En partant du coût nul de x, ces relations remplissent les coûts jusqu'à la cible ; elles ne sont pas une recherche dans les chaînes libres, car aucune somme de deux puissances anciennes n'est autorisée.
Pour quinze, Alice obtient successivement les coûts utiles de six, sept, quatorze et quinze : trois, quatre, cinq et six. Sept exige de passer par six, et quinze de passer par quatorze ; à quatorze, le chemin depuis sept coûte cinq. Le détour depuis treize est plus cher. Elle exécute donc 1, 2, 3, 6, 7, 14, 15 dans l'emplacement unique et joint le coût six retrouvé par la relation. Le six ne vient pas d'une supposition selon laquelle la méthode binaire serait toujours optimale ; les deux possibilités de chaque exposant pair et l'unique possibilité impaire ont été comparées sous les permissions effectivement disponibles.
Pour vingt-trois, elle trouve un coût six pour vingt-deux, puis sept pour vingt-trois. Une trace choisie est 1, 2, 4, 5, 10, 11, 22, 23. Le passage de vingt à vingt-trois de sa première préparation ne peut être exécuté dans l'emplacement unique : trois n'y est plus présent. En revanche, vingt-deux peut être mis au carré depuis onze, puis multiplié par x. Alice remet cette trace à sept lorsqu'un seul emplacement est demandé ; elle ne maintient pas le compte six en prétendant que les lignes écrites dans le cahier constituent autant de puissances encore lisibles. Le cahier décrit une préparation, mais les feuilles disponibles sont définies par la branche.
Deux emplacements rendent les préparations courtes exécutables
Avec deux emplacements réinscriptibles, Alice réalise effectivement quinze en cinq produits. Elle écrit x² dans le premier, puis x³ dans le second en lisant x² et x. Le troisième produit lit les deux emplacements et remplace le premier par x⁵ ; les contenus sont alors cinq et trois. Elle met le premier au carré dans le second, remplaçant trois par dix, puis multiplie cinq et dix et écrit quinze dans le second. Chaque entrée demeure présente jusqu'à sa lecture ; aucune puissance oubliée n'est recréée gratuitement. La destruction de trois est permise après la production de cinq, car le reste de cette préparation ne le consulte plus.
La trace de vingt-trois choisit une autre puissance à garder. Alice écrit deux dans le premier emplacement et trois dans le second, puis remplace deux par cinq en utilisant les deux contenus. Elle remplace ensuite cinq par dix, puis dix par vingt, tout en maintenant trois dans le second emplacement. Le dernier produit réunit vingt et trois et remplace le premier par vingt-trois. Les six opérations de la chaîne libre sont toutes exécutées dans ces deux emplacements. La place libérée n'est pas la même que pour quinze : supprimer trois après cinq, comme dans la trace précédente, rendrait le dernier produit indisponible. La différence de cible change réellement la durée de conservation de ce parent.
Alice ne déduit pas de ces deux exemples qu'une mémoire de deux emplacements suffirait pour toutes les chaînes minimales. Elle certifie deux traces complètes pour les commandes présentes, et les bornes cinq et six du modèle libre restent des bornes inférieures lorsque la mémoire est restreinte. Comme ses deux traces les atteignent, ces comptes sont aussi minimaux dans cette branche à deux emplacements. Le raisonnement utilise à la fois la preuve ancienne, qui ne pouvait être améliorée même avec davantage de feuilles, et une exécution nouvelle, qui montre que les feuilles autorisées suffisent vraiment. Une borne générale de mémoire ne remplace aucun de ces deux contrôles.
Trois mises au carré déjà faites ne disparaissent pas du prix
Une autre commande arrive après que les résultats deux, quatre et huit ont déjà été produits. Alice doit les conserver dans la préparation et finir quinze sans effacer le prix des trois opérations réalisées. Deux opérations supplémentaires ne suffisent pas. Le prochain exposant utile pourrait être neuf, dix ou douze ; seize dépasse la cible et ne peut revenir vers quinze avec les seules multiplications. À partir de ces nouvelles puissances, le dernier produit devrait réunir respectivement neuf et six, dix et cinq, ou douze et trois. Aucun de ces petits compléments n'est parmi 1, 2, 4, 8. Produire directement quinze à l'étape suivante est également impossible avec ces quatre exposants seuls.
Alice finit avec trois produits supplémentaires : douze par huit et quatre, quatorze par douze et deux, puis quinze par quatorze et un. La préparation entière 1, 2, 4, 8, 12, 14, 15 coûte six. Le cinq de la commande libre reste vrai, mais il suppose la possibilité de choisir trois dès le début ; l'état déjà obtenu ne contient pas trois. Alice retire donc une proposition qui remplaçait silencieusement les premières mises au carré par la chaîne courte. Sa remise conserve le préfixe imposé et son prix, puis choisit une continuation dont les parents sont réellement présents. L'opération nouvelle n'est pas une variation du nombre demandé : elle porte sur un début que la préparation n'a plus le droit de réviser.
Quand les deux parents doivent être distincts
Dans une dernière branche, la première mise au carré x² est explicitement autorisée et coûte un. Ensuite, chaque produit doit réunir deux puissances d'exposants distincts. Alice retrouve une mémoire sans limite ; seule la permission de multiplier une puissance par elle-même est retirée après cette première opération. Elle ne prétend pas décrire une machine réelle où les mises au carré seraient interdites. La règle est une commande abstraite séparée, et le coût de sa première exception doit rester dans le total annoncé.
Après les exposants initiaux un et deux, le plus grand résultat suivant est trois. Puis les maxima successifs sont cinq, huit et treize : chaque nouveau maximum est au plus la somme des deux plus grands exposants antérieurs distincts. Obtenir un petit résultat intermédiaire au lieu du maximum ne peut relever ces bornes, puisqu'il ne rend aucun des deux parents plus grand. Quatre opérations après la première mise au carré ne peuvent donc dépasser treize. Pour produire quinze, il faut au moins cinq opérations supplémentaires, soit six au total. La borne ne vient plus seulement de la parité du dernier exposant ; elle suit la croissance entière autorisée après chaque produit.
Alice atteint cette borne avec 1, 2, 3, 5, 8, 13, 15. Les produits utilisent successivement les paires d'exposants (1,2), (2,3), (3,5), (5,8), puis (2,13), toutes distinctes. Deux doit rester conservé jusqu'au dernier produit ; la mémoire sans limite de cette branche le permet. Elle ne prend pas vingt et un, qui serait le prochain maximum après treize : le maximum possible borne une préparation, mais n'impose pas d'atteindre ce maximum à chaque ligne. Quinze est obtenu par un autre choix final. La première mise au carré, extérieure à cette liste de cinq produits distincts, est toujours facturée une fois, d'où le coût six.
Sans l'exception initiale, cette dernière commande serait inexécutable : seule x serait disponible et aucun couple de puissances distinctes ne pourrait produire la première nouvelle feuille. Alice garde donc deux décisions séparées, l'autorisation d'amorcer avec x² et la restriction des produits ultérieurs. Elle remet la préparation à six avec cette exception visible, au lieu de raconter que les parents distincts suffiraient dès le départ. Pour la commande libre, elle remet toujours quinze en cinq et vingt-trois en six ; pour l'emplacement unique, six et sept ; pour le préfixe des trois mises au carré, quinze en six. Chaque prix appartient à une préparation remplie sous ses permissions, sans être reporté sur une autre branche.
Les notices restent des références de catégorie ; aucune image ou méthode artistique ne fournit ces chaînes. Le cahier conserve les produits et les permissions qui les rendent exécutables, plutôt qu'un résultat isolé accompagné d'un prix universel.