Méta : Régulièrement je tombe sur des problèmes
mathématiques qui me paraissent tellement simples, tellement naturels
et/ou tellement évidents (je veux dire évidents à poser, pas forcément
évidents à résoudre !) que c'est inconcevable qu'il n'existe pas déjà
une littérature abondante à leur sujet. Mais faute de connaître les
bons mots-clés ou la bonne façon de formuler le problème (car souvent
un même problème admet mille et une reformulations ou
réinterprétations), je peux galérer pour mettre le doigt sur cette
littérature. C'est extrêmement frustrant. Pour digresser sur ce
problème en général, cf. par
exemple cette
vidéo où le
YouTubeur Tom Scott
passe la moitié du temps à raconter combien il a eu du mal à trouver
le terme Inogon light
pour en savoir plus sur un
type de signal nautique utilisant intelligemment des effets de moiré
pour montrer aux bateaux où aller en fonction de leur position.
L'Internet a quelque chose de la Kabbale : quand on connaît le Vrai
Nom de quelque chose, on acquiert du pouvoir sur cette chose — en
l'occurrence, le pouvoir d'en savoir plus. Le problème que je veux
évoquer ici fait partie de ces problèmes qui me semblent tellement
« s'imposer » que je suis sûr qu'il a un nom et qu'il y a des
chapitres entiers de bouquins d'algorithmiques qui lui sont
consacrés ; mais comme je ne le formule pas forcément sous le bon
angle, je ne trouve pas.
Il s'agit, donc, de quelque chose que je comprends raisonnablement bien du côté mathématique, mais dont l'algorithmique me laisse passablement perplexe. Ce qui veut dire que j'ai beaucoup de choses à raconter, dont beaucoup ne sont sans doute pas pertinentes pour le problème algorithmique, mais je ne sais pas au juste ce qui l'est et ce qui ne l'est pas.
Voici la première variante du problème algorithmique, qui est la
plus simple et élémentaire à énoncer : je vais l'appeler la variante
(AS), parce que je vais vouloir en formuler un certain
nombre, ce sera plus commode si je leur donne des noms. (Le S
signifie symétrique ; le A
est là comme dans la classification
de Killing-Cartan, mais pour l'instant peu importe.)
(AS) On se donne x et y deux vecteurs (de longueur, disons, n≥1), à coordonnées entières. Je suppose que la somme des coordonnées de x est nulle, et pareil pour y (je ne sais pas si ça sert vraiment à quelque chose).
Problème : trouver tous les produits scalaires possibles σ(x)·y entre y et un vecteur σ(x) obtenu en permutant les coordonnées de x, avec, pour chacun, son nombre d'occurrences, c'est-à-dire le nombre de permutations σ des coordonnées de x qui conduisent à ce produit scalaire.
Exemple : si x=(−2,−1,0,1,2) et y=(−2,0,0,1,1), la réponse attendue est {−7: 4 fois, −6: 4 fois, −5: 12 fois, −4: 8 fois, −3: 12 fois, −2: 4 fois, −1: 8 fois, 0: 16 fois, 1: 8 fois, 2: 4 fois, 3: 12 fois, 4: 8 fois, 5: 12 fois, 6: 4 fois, 7: 4 fois} (chaque produit scalaire possible σ(x)·y étant suivi de son nombre d'occurrences : notamment, il y a 16 permutations des coordonnées de x qui donnent un produit scalaire nul avec y). • Autre exemple : si x=y=(−2,−1,0,1,2), la réponse attendue est {−10: 1 fois, −9: 4 fois, −8: 3 fois, −7: 6 fois, −6: 7 fois, −5: 6 fois, −4: 4 fois, −3: 10 fois, −2: 6 fois, −1: 10 fois, 0: 6 fois, 1: 10 fois, 2: 6 fois, 3: 10 fois, 4: 4 fois, 5: 6 fois, 6: 7 fois, 7: 6 fois, 8: 3 fois, 9: 4 fois, 10: 1 fois}.
Il y a évidemment plein de façons de reformuler ça et plein de remarques évidentes à faire. Par exemple, je peux dire qu'il s'agit de considérer toutes les façons d'apparier (bijectivement) les coordonnées de x avec celles de y et de sommer les produits des coordonnées appariées entre elles : sous cette forme, il est évident que le résultat est symétrique entre x et y ; par ailleurs, il est clair que ça ne change rien de permuter les coordonnées de x ou celles de y, donc on peut les supposer triées au départ. Si on veut, je me donne deux paquets (deux « multiensembles ») x et y de nombres, de même taille, mais sans ordre, et je cherche toutes les façons de faire un produit scalaire.
On peut considérer le résultat comme un multiensemble (le multiensemble de tous les produits scalaires σ(x)·y comptés avec la multiplicité de l'occurrence de chacun). On peut aussi coder le résultat comme un polynôme (de Laurent, c'est-à-dire admettant des puissances négatives de l'indéterminée), en l'indéterminée t disons, c'est-à-dire mettre comme coefficient devant tk le nombre de fois que k apparaît comme produit scalaire σ(x)·y : autrement dit, il s'agit de calculer la somme S(x,y) des tσ(x)·y où σ parcourt toutes les permutations de n objets. (Et pour reprendre un de mes exemples, si x=y=(−2,−1,0,1,2), on a S(x,y) = t10 + 4·t9 + 3·t8 + 6·t7 + 7·t6 + 6·t5 + 4·t4 + 10·t3 + 6·t2 + 10·t + 6 + 10·t−1 + 6·t−2 + 10·t−3 + 4·t−4 + 6·t−5 + 7·t−6 + 6·t−7 + 3·t−8 + 4·t−9 + t−10.) Il est évident que la taille totale du multiensemble, c'est-à-dire la valeur en t=1 du polynôme S(x,y), vaut n! (soit 120 dans mes exemples) ; si x ou y est nul, alors le la seule valeur d'un produit scalaire est 0 (donc S(x,y) vaut le polynôme constant n!).
Une autre remarque évidente est que si on multiplie ou divise toutes les coordonnées de x ou toutes celles de y par une même constante, le résultat pour les vecteurs ainsi modifiés se déduit trivialement de celui pour les vecteurs de départ (formulé sur S(x,y), cela signifie que S(rx,sy) s'obtient en remplaçant t par trs dans S(x,y)). On peut donc admettre que x et y aient des coordonnées rationnelles (le polynôme S(x,y) est alors possiblement un polynôme de « Laurent-Puiseux »(?), c'est-à-dire une combinaison linéaire formelle de ti où i parcourt un ensemble fini de rationnels). On pourrait même admettre que x et y aient des coordonnées réelles quelconques, mais je ne vais pas vouloir faire ça.
Il faut que je fasse une remarque plus importante sur ce que je cherche algorithmiquement. L'algorithme naïf consiste juste à énumérer toutes les n! permutations distinctes. Il est clair que sur des vecteurs x et y quelconques, par exemple si on prend des réels vraiment arbitraires (imaginez 2n réels algébriquement indépendants) ou des entiers suffisamment grands, aucun des produits scalaires σ(x)·y n'aura de multiplicité. C'est-à-dire qu'il y en aura n! distincts. Dans ces conditions, mon problème n'admet visiblement aucune solution intelligente : il faut de toute façon calculer n! valeurs, donc il n'y a rien de mieux à faire qu'énumérer les n! permutations σ. Si j'attends une réponse intéressante, c'est que je m'intéresse à des données contraintes pour que ça ne se produise pas : je vais dire que x et y sont à valeur (entières et) de valeur absolue pas beaucoup plus grande que n. Disons, pour fixer les idées, qu'il y a une constante C telle que chaque coordonnée de x et de y est majorée par Cn en valeur absolue (et je cherche un algorithme ayant une complexité significativement meilleure, lorsque C est fixée, que l'algorithme naïf en n!·n·log(n) ou quelque chose de ce goût-là). De fait, si chaque coordonnée de x ou de y est majorée par Cn en valeur absolue, chaque produit scalaire sera majoré par au plus Cn³, donc il y en a au plus 2Cn³+1 distincts (car ce sont des entiers), et certainement pas n! : dès lors, il est raisonnable a priori de chercher s'il peut y avoir mieux que l'algorithme naïf, peut-être même quelque chose de polynomial en n (encore une fois : pour C fixé). En revanche, je suis tout à fait susceptible de m'intéresser à des cas où toutes les coordonnées de x, et toutes celles de y, sont distinctes (je précise ça, parce qu'il est évident que s'il y a des répétitions, on peut diviser d'autant le nombre de permutations considéré).
Fondamentalement, je ne sais pas résoudre ce problème algorithmique de façon plus intelligente qu'en énumérant les n! permutations. Pourtant, je sais dire beaucoup de choses dessus (et je vais le faire !), mais peut-être que toutes ces choses sont complètement hors-sujet algorithmiquement. Peut-être que je suis bien naïf d'imaginer qu'on puisse faire fondamentalement mieux que n! pour traiter ce problème. Je n'en sais rien.
Je m'intéresse aussi au problème suivant :
(AA) Pareil que la variante d'origine (AS), mais en alternant les signes selon la signature de la permutation, autrement dit :
On se donne x et y deux vecteurs (de longueur, disons, n), à coordonnées entières. Je suppose que la somme des coordonnées de x est nulle, et de même pour y.
Problème : trouver tous les produits scalaires possibles σ(x)·y entre y et un vecteur σ(x) obtenu en permutant les coordonnées de x, avec, pour chacun, le nombre de permutations paires moins le nombre de permutations impaires qui donnent ce produit scalaire. C'est-à-dire que chaque permutation compte pour ε(σ), où ε(σ) vaut +1 pour une permutation paire et −1 pour une permutation impaire (et on fait le total de ces ε(σ) pour chaque produit scalaire possible).
Exemple : si x=y=(−2,−1,0,1,2), la réponse attendue est {−10: 1 au total, −9: −4 au total, −8: 3 au total, −7: 6 au total, −6: −7 au total, −5: −2 au total, −4: −4 au total, −3: 10 au total, −2: 6 au total, −1: −10 au total, 0: 2 au total, 1: −10 au total, 2: 6 au total, 3: 10 au total, 4: −4 au total, 5: −2 au total, 6: −7 au total, 7: 6 au total, 8: 3 au total, 9: −4 au total, 10: 1 au total}. Remarquons que mon autre exemple (où y=(−2,0,0,1,1)) donne, dans cette variante du problème, des totaux (multiplicités) tous nuls (cf. ci-dessous).
Il est possible que cette variante (AA), bien que de description plus compliquée, soit finalement algorithmiquement plus simple que la variante (AS) de départ pour la même raison que les déterminants sont plus faciles à calculer que les permanents. Je n'en sais rien. (Par ailleurs, elle va me servir à définir la variante (AΧ).) Il est en tout cas clair que les ensembles à parcourir sont les mêmes, seules changent les multiplicités.
Pour cette variante (AA) aussi, on peut coder le résultat sous forme d'un polynôme, appelons-le disons Δ(x,y), c'est-à-dire qu'il s'agit de la somme des ε(σ)·tσ(x)·y où σ parcourt toutes les permutations de n objets. Cette fois, le polynôme prend la valeur 0 en t=1 (pour n≥2, il y a autant de permutations impaires que de permutations paires). Il est, par ailleurs, identiquement nul dès que x ou y a des valeurs répétées.
Ajout important
() : J'avais écrit les paragraphes
ci-dessus (les déterminants sont plus faciles à calculer que les
permanents
) sans trop faire attention, mais en fait,
c'est exactement ça : Δ(x,y)
est le déterminant de la matrice dont les entrées sont
les txiyj
tandis que S(x,y) est son permanent.
(Je ne sais pas pourquoi je ne m'en rends compte que maintenant : je
n'avais vraiment pas les yeux en face des trous, d'autant que j'avais
explicitement fait la remarque ci-dessus, ainsi que celle, ci-dessous,
sur le déterminant de Vandermonde ! J'aurais dû prendre le temps de
plus réfléchir avant de ranter dans mon blog — ceci dit, c'est
justement le fait de ranter qui m'a aidé à trouver cette solution.)
Du coup, ça fournit la réponse à mon problème (AA) et
ça suggère que le problème (AS) de départ n'en a
probablement pas (puisque les permanents sont notoirement difficiles à
calculer) ; il reste encore à voir comment on peut se sortir de
(AΧ) (voir plus bas) dans le cas où la définition donne
« 0/0 », et aussi à trouver comment transformer en déterminants les
problèmes (BA) et compagnie qui sont exposés plus
bas.
Toute la suite de cette entrée est constituée de remarques et commentaires supplémentaires par rapport à ces problèmes, et encore des variantes ; mais essentiellement, il s'agit de diverses digression, peut-être sans pertinence algorithmique par rapport au problème de base.
Pour commencer ces digressions, il faut que je dise quelque chose à propos du vecteur de Weyl : le vecteur de Weyl, dans ce contexte (A), c'est juste le vecteur ρ dont les coordonnées consécutives diffèrent toujours de 1, c'est-à-dire (−½(n−1), −½(n−3), …, ½(n−3), ½(n−1)) ; pour n=5, c'est donc le vecteur (−2, −1, 0, 1, 2) que j'ai utilisé pour mes exemples (ce qui était peut-être une mauvaise idée parce qu'il a des propriétés magiques, mais maintenant je n'ai plus envie de refaire des calculs). Le vecteur de Weyl est à coordonnées entières-et-demi lorsque n est pair (pour n=4 par exemple c'est (−3/2, −1/2, 1/2, 3/2)), mais ce n'est pas grave, j'ai expliqué qu'on pouvait très bien définir S(x,y) et Δ(x,y) dans ce cas. L'intérêt du vecteur ρ est que si l'un de x ou de y vaut ce vecteur très spécial, il y a une formule magique qui permet de calculer Δ(x,y), à savoir que Δ(ρ,y) se factorise (en tant que polynôme en t) comme produit des tyj−tyi où (i,j) parcourt les paires d'indices telles que i<j (c'est la formule du dénominateur de Weyl, qui, dans ce cas, est juste la formule de Vandermonde). Maintenant, ce n'est pas si intéressant, eu égard à mon problème (AS) ou même (AA), de savoir calculer Δ(x,y) lorsque x ou y est ce vecteur très particulier, et la formule ne se généralise pas (pour un x et un y arbitraires, Δ(x,y) n'admet pas de factorisation intéressante).
Mais ça peut me servir à introduire une troisième expression et le
problème algorithmique de la calculer. J'introduis donc cette
expression Χ(x,y), qui est liée à la
fois à S(x,y) et
à Δ(x,y). Précisément, je vais
définir la quantité Χ(x,y)
:= Δ(ρ+x,y)/Δ(ρ,y)
(cette fois, ce n'est plus symétrique en x
et y ; et au fait ce n'est
pas un X, c'est un Chi, comme l'initiale du
mot caractère
), où je suppose
que x est trié par ordre croissant (je ne
définis Χ(x,y) que dans ce cas).
En fait, il y a un problème dans ma définition de Χ(x,y) lorsque y a des coordonnées répétées, parce que ma définition donne 0/0, mais il y a plein de façons naturelles, toutes équivalentes, de quand même donner un sens à Χ(x,y) dans ce cas. Par exemple, on peut ignorer la valeur de y et considérer temporairement les tyi comme n indéterminées, écrire Δ(z,y) comme un polynôme (de Laurent) en ces indéterminées (c'est la somme des ε(σ)·tσ(z)·y où tσ(z)·y s'interprète comme un monôme en les tyi dont les exposants sont les coordonnées de σ(z)), ensuite faire le quotient Δ(ρ+x,y)/Δ(ρ,y) dans l'anneau des polynômes (de Laurent) en n indéterminées tyi, constater que miraculeusement ce quotient est encore un polynôme (de Laurent ; le dénominateur divise exactement le numérateur), et resubstituer les valeurs de yi pour définir Χ(x,y) comme polynôme (de Laurent) en t. Comme je viens de le signaler, ce n'est pas juste une fraction rationnelle, c'est un polynôme (de Laurent).
Par exemple, pour x=y=(−2,−1,0,1,2)=ρ, le dénominateur est Δ(ρ,y) = t10 − 4·t9 + 3·t8 + 6·t7 − 7·t6 − 2·t5 − 4·t4 + 10·t3 + 6·t2 − 10·t + 2 − 10·t−1 + 6·t−2 + 10·t−3 − 4·t−4 − 2·t−5 − 7·t−6 + 6·t−7 + 3·t−8 − 4·t−9 + t−10, le numérateur est Δ(ρ+x,y) = Δ(2ρ,y) = (le même polynôme en remplaçant t par t² partout), et le quotient Χ(x,y) = Δ(ρ+x,y)/Δ(ρ,y) (ici il n'y a pas de problème de 0/0) vaut t10 + 4·t9 + 9·t8 + 18·t7 + 31·t6 + 46·t5 + 64·t4 + 82·t3 + 96·t2 + 106·t + 110 + 106·t−1 + 96·t−2 + 82·t−3 + 64·t−4 + 46·t−5 + 31·t−6 + 18·t−7 + 9·t−8 + 4·t−9 + t−10.
Bref, j'ai le problème algorithmique :
(AΧ) Donné x et y deux vecteurs à coordonnées entières avec x à coordonnées croissantes, calculer la quantité Χ(x,y) définie ci-dessus.
Pourquoi définir justement ce Χ(x,y)-là ? À vrai dire, c'est surtout lui qui m'intéresse, ou en tout cas, c'est lui qui m'a amené à m'intéresser aux problèmes énoncés ci-dessus. Ce que j'ai écrit comme définition de Χ(x,y), en fait, c'est la formule de caractère de Weyl, un petit peu déguisée (pour les experts, c'est la valeur, sur le groupe à un paramètre engendré par y, du caractère de plus haut poids x de An−1, c'est-à-dire SU(n−1) ; pour les non-experts, les explications sont un peu longues, mais probablement pas vraiment pertinentes pour le problème algorithmique).
Ajout () : Je peux ajouter que Χ(x,y) s'obtient en substituant les monômes tyj dans le polynôme de Schur défini par les xi (auxquels on ajoute une constante pour les rendre tous positifs). Il y a des zillions de formules connues sur les polynômes de Schur, mais ce n'est pas évident de savoir ce qui est pertinent pour faire la substitution.
Il se trouve que ce Χ(x,y) a des propriétés amusantes, par exemple ses coefficients (qui sont symétriques par rapport à 0) sont croissants puis décroissants, et il me semble que c'est un fait essentiellement combinatoire qu'on ne sait prouver que par la théorie de la représentation des groupes de Lie. Calculer la valeur en t=1 de Χ(x,y) n'est pas difficile (c'est la formule de la dimension de Weyl : c'est un polynôme en x, dans ce cas y n'intervient pas). Il est, par ailleurs, possible de relier Χ(x,y) au S(x,y) de départ, ce n'est pas juste qu'il a manifestement le même degré :
En fait, on peut exprimer Χ(x,y), indépendamment de y, comme une combinaison des S(x′,y) à coefficients rationnels positifs (indépendants de y, donc), où x′ parcourt tous les vecteurs à coordonnées entières, croissantes, et dont les sommes partielles sont en tout point inférieures à celles de x (y compris x lui-même) ; et réciproquement, on peut exprimer S(x,y) (en supposant x à coordonnées croissantes) comme combinaison linéaire des Χ(x′,y) à coefficients entiers (indépendants de y), où x′ parcourt les mêmes valeurs qu'on vient de dire. (Si on préfère, les S(x,y) et Χ(x,y) s'expriment les uns en fonction des autres par des combinaisons linéaires triangulaires, « triangulaires » étant comprises par rapport à l'ordre qui rend un vecteur entier croissant inférieur à un autre si les sommes partielles du premier sont en tout point inférieures à celles du second.) On sait d'ailleurs calculer explicitement les coefficients de cette combinaison, mais la pertinence algorithmique de la chose m'échappe un peu. Enfin, à titre d'exemple, pour x=(−2,−1,0,1,2), le polynôme Χ((−2,−1,0,1,2), y) est la combinaison des S(x′,y) suivants et avec les coefficients suivants : (1/5)·S((0,0,0,0,0), y) + (7/3)·S((−1,0,0,0,1), y) + 2·S((−1,−1,0,1,1), y) + S((−1,−1,0,0,2), y) + (1/3)·S((−1,−1,−1,1,2), y) + S((−2,0,0,1,1), y) + (1/3)·S((−2,0,0,0,2), y) + (1/3)·S((−2,−1,1,1,1), y) + S((−2,−1,0,1,2), y). Ou inversement, S((−2,−1,0,1,2), y) vaut −2·Χ((0,0,0,0,0), y) + 2·Χ((−1,0,0,0,1), y) + 2·Χ((−1,−1,0,1,1), y) − 2·Χ((−1,−1,−1,1,2), y) − 2·Χ((−2,0,0,0,2), y) − 2·Χ((−2,−1,1,1,1), y) + Χ((−2,−1,0,1,2), y).
Mais bon, je répète que je n'ai pas les idées bien claires sur la difficulté à calculer les coefficients exprimant les Χ(x,y) comme combinaison linéaire des S(x′,y) ou vice versa. J'étais parti sur l'idée de calculer les Χ(x,y) en les ramenant aux S(x′,y) et donc au problème (AS), mais en fait c'est peut-être exactement le contraire qu'il faut faire.
(Fin de la digression sur les Χ(x,y).)
Une autre chose que je peux dire (et qui est une nouvelle digression), c'est qu'on peut aussi espérer calculer les S(x,y), que je vais noter juste S(x) parce que je fixe provisoirement y, par une sorte de récurrence sur x. L'observation (facile) est la suivante sur le produit de S(x) et S(z) (comme polynômes en t) :
S(x)·S(z) est la somme des S(x+σ(z)) où σ parcourt toutes les permutations (de n objets).
Évidemment, ce n'est pas très utile si je cherche à éviter une somme sur les n! permutations dans le calcul de S(x) en la remplaçant par une autre somme sur les n! permutations. Mais ce que je peux faire, c'est appliquer cette observation à des vecteurs z particuliers qui n'ont que peu de permutations. Par exemple le vecteur ei qui a les i dernières coordonnées égales à 1 et les n−i premières égales à 0 ; enfin, ce vecteur-là il n'est pas de somme nulle, mais si je soustrais i/n à toutes ses coordonnées (donc i coordonnées égales à (n−i)/n et n−i égales à −i/n), ça ne change rien ; l'emplacement des coordonnées, bien sûr, n'a guère d'importance puisque de toute façon on va sommer sur toutes les permutations. Calculer S(ei) est facile : c'est i!·(n−i)! fois la somme des tk où k parcourt toutes les sommes d'un sous-ensemble de i parmi n coordonnées de y. Même calculer tous les S(ei) (ce qui demande essentiellement de parcourir les 2n sous-ensembles de coordonnées de y) est moins coûteux que parcourir les n! permutations. L'idée, ensuite, serait de calculer les S(x) par récurrence sur… quelque chose, je ne sais pas bien quoi : comme on connaît les S(ei), on connaît les S(ei)·S(ej), mais on peut exprimer ceux-ci comme des combinaisons des S(ei) et des S(ei+ej), par exemple S(e₁)·S(e₂) = (n−1)! · (2S(e₁+e₂) + (n−2)·S(e₃)) (se rappeler que S(e₁) énumère toutes les coordonnées yi de y, S(e₂) énumère toutes les sommes de deux coordonnées distinctes de y et S(e₃) les sommes de trois coordonnées distinctes, et enfin S(e₁+e₂) énumère toutes les expressions 2yi+yj avec i≠j), ce qui peut servir à calculer S(e₁+e₂) connaissant S(e₁), S(e₂) et S(e₃).
Mais au final je m'y perds dans ce qui se récurre, et je n'arrive pas à savoir si cette approche a un intérêt algorithmique ou non. Évidemment elle ne peut pas en avoir en général, mais je rappelle que j'ai fait l'hypothèse que chaque coordonnée de x (et de y) est majorée par Cn en valeur absolue. Tout ça est peut-être idiot.
(Fin de la digression sur cette possible approche de calcul.)
Je peux aussi définir d'autres variantes du problème. Notamment :
(BS)=(CS) On se donne x et y deux vecteurs (de longueur, disons, n), à coordonnées entières. Je ne suppose plus que la somme des coordonnées de x ni de y est nulle.
Problème : trouver tous les produits scalaires possibles σ(x)·y entre y et un vecteur σ(x) obtenu en permutant les coordonnées de x et en changeant arbitrairement leurs signes (avec, pour chacun, son nombre d'occurrences, c'est-à-dire le nombre de permutations signées σ des coordonnées de x qui conduisent à ce produit scalaire).
(BA)=(CA) Idem mais on veut la somme des ε(σ) défini comme valant la signature (dans ±1) de la permutation multipliée par les différents changements de signes effectués (i.e., ε(σ) est le déterminant de la matrice représentant la permutation signée).
(DS) Comme (BS)/(CS), mais on ne peut effectuer qu'un nombre pair de changements de signes. • (DA) Idem, et on veut la somme des ε(σ), qui sont les signatures des permutations (le produit des changements de signes est de toute façon +1).
Les problèmes (BS) et (CS) sont identiques (et de même (BA) et (CA)), il y a juste une différence dans le vecteur de Weyl (qui de toute façon ne fait pas partie du problème) : pour (CA), ρ vaut (1, 2, 3, …, n), tandis que pour (BA), il vaut (1/2, 3/2, 5/2, …, (2n−1)/2). Quant à (DA), son vecteur de Weyl vaut (0, 1, 2, …, n−1). Dans tous les cas, on a une factorisation de Δ(ρ,y), analogue au cas précédent, mais que je n'écris pas. Et on reprend la définition de Χ(x,y) := Δ(ρ+x,y)/Δ(ρ,y), qui est de nouveau un polynôme (de Laurent), et mes problèmes (BΧ), (CΧ) et (DΧ) consistent à le calculer. (La contrainte de croissance sur x doit aussi être un peu modifiée : pour (BΧ) ou (CΧ), elle est que x soit à coordonnées croissantes et positives ; pour (DΧ), elle est que x soit à coordonnées positives sauf éventuellement la première, et croissantes si on remplace la première par sa valeur absolue.)
Et bien sûr, il y a les cas exceptionnels : dès lors qu'on a un groupe de Weyl opérant sur un réseau de racines, on a les trois problèmes que j'ai évoqués. Par exemple, le problème (E₈S) consiste, donnés deux vecteurs entiers x et y (ou rationnels, enfin, peu importe comme on l'a vu), de longueur 8, à trouver tous les produits scalaires possibles σ(x)·y, chacun avec ses multiplicités, où σ parcourt les 696 729 600 transformations que j'avais expliquées ici, tandis que le problème (F₄S) concerne des vecteurs de longueur 4, et le groupe de Weyl est décrit ici (mais comme il a juste 1152 éléments, le problème algorithmique n'est pas trop difficile). Pour définir les problèmes (E₈Χ) et (F₄Χ), j'ajoute que les vecteurs de Weyl de E₈ et F₄ sont respectivement (0, 1, 2, 3, 4, 5, 6, 23) et (1/2, 3/2, 5/2, 11/2).