Méthodes de calcul

Procédure Maple

Voici la procédure Maple élémentaire qui permet d'obtenir un système d'équations, après avoir défini (en tenant compte du passeport) deux polynômes unitaires A et B, dont les racines sont les sommets noirs (respectivement blancs) de l'arbre (voir les arbres avec 7 arêtes, à partir du passeport 6, pour des exemples) :
sc := proc (P)
  seq (coeff (P, z, k - 1), k = 1 .. degree (P) );
end;

equations := proc (A, B)
  d := degree (A);
  dA := diff (A, z);
  dB := diff (B, z);

  mA := gcd (A, dA, 'sA', 'sdA');
  mB := gcd (B, dB, 'sB', 'sdB');

  [ sc (sdA - d * mB), sc (sdB - d * mA) ];
end;

En effet, la condition "A-B = constante" équivaut à l'égalité des dérivées notées dA et dB ci-dessus. On factorise dA sous la forme mA * sdA, où l'on a regroupé dans le polynôme mA les racines multiples de A (qui sont donc aussi racines de la dérivée dA) ; de même dB = mB * sdB. Comme les sommets de l'arbre sont tous distincts, les polynômes mA et mB sont premiers entre eux, donc mA = sdB et sdA = mB, sauf qu'il ne faut pas oublier les coefficients dominants, égaux à d dans les dérivées.

La procédure ci-dessus extrait donc une liste de d - 1 coefficients, qui doivent tous être nuls (on omet volontairement les coefficients dominants, nuls par construction). Ces coefficients sont des polynômes, avec pour variables les coefficients inconnus ai et bj des polynômes A et B.

Dans les cas les plus simples, on résoud "à la main" le système obtenu, mais en général il faut calculer une base de Groebner (de l'idéal engendré) pour résoudre le système.

Questions et réponses

Appeler cette section une FAQ serait peut-être abusif, mais l'idée est la même.

Q1 : le polynôme de Shabat d'un arbre est-il unique ?

Non. Il est unique à deux similitudes près, l'une dans le plan complexe de départ, qui correspond à une transformation (par similitude) de l'arbre, l'autre dans le plan complexe d'arrivée, qui correspond à un choix arbitraire des deux valeurs critiques c1 et c2. Rappelons que l'arbre est l'image réciproque du segment [c1 c2] par le polynôme de Shabat.

Dans ce catalogue, on a fait en général les choix suivants :

L'exception principale concerne les polynômes de Tchebycheff, dont les valeurs critiques sont -1 et 1.

Q2 : je trouve dans le catalogue un polynôme de Shabat, je trouve aussi l'arbre correspondant dessiné, mais comment calculer les affixes des sommets de l'arbre ?

Les sommets noirs sont les images réciproques de la première valeur critique c1 , les sommets blancs sont les images réciproques de la seconde valeur critique c2 . Comme on a choisi systématiquement c1=0 (à l'exception des polynômes de Tchebycheff), les sommets noirs sont, dans ce catalogue, les racines du polynôme de Shabat.

Pour calculer les sommets blancs, il faut :

D'autre part, à partir du passeport 6, pour les arbres avec 7 arêtes de ce catalogue, les calculs (effectués avec Maple) désignent le polynôme de Shabat par A, ses racines sont les sommets noirs, tandis que B désigne le polynôme dont les racines sont les sommets blancs ; B ne diffère de A que par la constante additive c2 (et c'est aussi, bien sûr, un polynôme de Shabat). Les équations permettant de calculer (simultanément) les coefficients de A et de B sont données ; pour obtenir B, il suffit de les résoudre en éliminant les coefficients de A , alors que le catalogue donne les résultats de la démarche inverse.

Q3 : points critiques et valeurs critiques, ce sont deux expressions pour parler de la même chose, non ?

Non, définitivement non. u est un point critique de P si, par définition, P'(u)=0, et dans ce cas P(u) est une valeur critique. Les polynômes de Shabat sont ceux qui ont deux valeurs critiques (ou une seule, mais ce cas est vite réglé, il s'agit essentiellement du polynôme zn ) ; le segment qui joint ces deux valeurs critiques a pour image réciproque par P un arbre, dont les sommets internes (ie les sommets qui ne sont pas des feuilles) sont les points critiques de P.

Q4 : peut-on choisir systématiquement pour valeurs critiques 0 et 1 ?

Oui, mais ce n'est pas le choix opéré dans ce catalogue, où l'on a préféré travailler, sauf exception, avec des polynômes unitaires. La première valeur critique est 0 (sauf pour les polynômes de Tchebycheff), et la seconde ... doit être calculée par le lecteur, s'il y tient vraiment : voir réponse à la question Q2.

Q5 : il y a deux sommets noirs de degré 3, je fixe l'un en 0 et l'autre en 1, et j'obtiens deux fois plus de solutions que prévu, pourquoi ?

Le passeport 10, pour les arbres avec 7 arêtes, contient deux sommets noirs de degré 3. Si l'on croit fixer l'un en 0 et l'autre en 1, on obtient deux fois trop de solutions, par échange de ces deux sommets. En fait on n'a pas vraiment fixé la figure, il faut dans ce cas fixer seulement le milieu de ces deux sommets en 0, et fixer séparément un autre sommet.

De façon générale, lorsqu'il existe k sommets de même couleur et de même degré, il faut fixer la somme de leurs affixes, c'est-à-dire le coefficient du terme de degré k-1 dans le polynôme dont ces sommets sont racines (simples). Comme la fixation de l'arbre exige deux choix de ce type, il faut être un peu prudent, car rien ne dit que ces deux choix sont toujours indépendants ; par exemple, dans le cas du passeport 10, rien ne dit a priori que le sommet noir de degré 1 n'est pas situé au milieu des deux sommets de degré 3, et si c'était le cas, on ne pourrait évidemment pas fixer le premier en 1 et le second en 0.