Comments on Un problème d'algorithmique (en lien secret avec la formule de Weyl)

@Olivier Bailleux, @vicnent: En plus de mon commentaire précédent, je devrais préciser que je ne cherche pas forcément un algorithme polynomial, juste un algorithme « significativement moins pourri » que l'algorithme naïf en n! (et donc, en fait, je crois que j'ai répondu à ma question en reconnaissant un permanent, parce que <URL: http://en.wikipedia.org/wiki/Computing_the_permanent > m'apprend que le permanent se calcule avec un algorithme en O(2^n·n²) opérations arithmétiques, ce qui doit devenir O(2^n·n³) à cause des degrés de mes polynômes, mais c'est effectivement mieux que O(n!·n) ; après, il faut vérifier qu'il n'y a pas une arnaque dans l'histoire). Mais la question de si l'approche consistant à calculer Χ(x,y) comme rapport de déterminants pour en déduire l'ensemble des exposants fonctionne bien est intéressante.

Je viens de me rendre compte que mon Δ(x,y) est précisément le déterminant de la matrice dont les coefficients sont les t^{x_i·y_j}, et que S(x,y) est son permanent. (J'ai ajouté un paragraphe à ce sujet.) Du coup, ça résout mon problème (AA) et ça suggère fortement que (AS) n'est Pas Sympa.

@jonas:

Your remark about n=1 reminds me of a number of times when I attended a lecture where Jean-Pierre Serre was in the audience. The lecturer would make a statement and Serre would burst out saying "this is completely wrong! this is not possible!", at which point the lecturer would start panicking and ask themselves whether the great Serre had already found a counterexample to their theorem: and then Serre would point out that the statement obviously did not work for n=0 and that the lecturer had forgotten to state the hypothesis "n>0". I suspect that Serre does this on purpose to force mathematicians to be more careful about their statements and not carelessly exclude trivial cases (he told me that it is one of his pet peeves). He's right, of course, and so are you. In this particular case, the statement that the Δ(x,y) polynomial vanishes at t=1 is still true for n=1 for an even more trivial reason (x and y are both zero so Δ(x,y)=t); it is wrong, however, for n=0. I made the appropriate corrections.

Re posting on Stackexchange: indeed, that is what I do, but I try to force myself to think a fairly long time about my questions before I post them there. Here the problem is that I have a little too much to say, so I need to organize my thoughts first, hence the blog post. Since writing it helped me realize the determinant/permanent connection (first paragraph of this comment), I now see things in a different light.

@Olivier Bailleux: Je suis vraiment une quiche en algorithmique. 😖

Maintenant que j'ai fait la connexion avec le déterminant (premier paragraphe de ce commentaire), il est possible que ça fournisse un algorithme efficace pour calculer Χ(x,y), et comme il me semble que l'ensemble des exposants du polynôme en question est le même que celui de S(x,y), ça montrerait que ce dernier se calcule efficacement. Mais de nouveau, je n'ai pas les idées bien claires sur la complexité effective de tout ça.