Publ. I.R.M.A. Strasbourg, 1984, 229/S–08 Actes 8^{e} Séminaire Lotharingien, p. 59–62

ÜBER SYMMETRISCHE POLYNOME

VON

Heinz LÜNEBURG

Es sei R ein kommutativer Ring mit 1 und R[x_{1}, …, x_{n}] sei der Polynomring in den Unbestimmten x_{1}, …, x_{n} über R. Ist Σ der Teilring aller symmetrischen Polynome aus R[x_{1}, …, x_{n}], so ist R[x_{1}, …, x_{n}] en freier Σ-Modul und die Elemente x_{2}^{e_{1}} … x_{n}^{e_{n−1}} mit 0 ≤ e_{i} ≤ i bilden eine freie Σ-basis dieses Moduls. Setzt man E(n) = {e | 0 ≤ e_{i} ≤ i für i = 1, …, n−1}, so gibt es also zu jedem f ∈ R[x_{1}, …, x_{n}] eindeutig bestimmte S_{e} ∈ Σ mit

f = ∑_{e} S_{e}x_{2}^{e_{1}} … x_{n}^{e_{n−1}} (e ∈ E(n)).

Wir geben hier einen Algorithmus an, der zu f die S_{e} berechnet. Für diesen Algorithmus benötigen wir die Prozedur naechst(e, initium, ekm, i), die alle e ∈ E(i) erzeugt. Sie wird mit initium = true gestartet. Nach dem ersten Aufruf ist initium = false. Ist i = 1, so wird beim ersten Aufruf e = ∅ und ekm = false ausgegeben. Ist i > 1, so wird beim ersten Aufruf etwa e = (0, …, 0) ausgeben und bei jedem weiteren Aufruf der Nachfolger des bislang aktuellen e. Ferner ist ekm = true, solange noch nicht alle e ≠ E(i) erzeugt sind.

Algorithmus SYMKOEF

Berechnet zu f ∈ R[x_{1}, …, x_{n}] eine Familie (S_{e} | e ∈ E(n)) von symmetrischen Polynomen S_{e} mit

f = ∑_{e} S_{e}x_{2}^{e_{1}} … x_{n}^{e_{n−1}} (e ∈ E(n)).

begin S_{0} := f; i := 1 ; while i < n do

begin for k := 0 to i do

for j := k to i do

p_{jk} = ∑_{r} x_{i+1}^{r_{1}}x_{i}^{r_{2}} … x_{i−k+2}^{r_{k}}x_{i−k+1}^{j−k−r_{1}−···−r_{k}};

H. LÜNEBURG

{Die Summation ist über alle r mit 0 ≤ r_{1} ≤ j − k, 0 ≤ r_{2} ≤ j − k − r_{1}, …, 0 ≤ r_{k} ≤ j − k − r_{1} − ⋯ − r_{r−1} zu erstrecken .} initium := true ; ekm := true ; while ekm do begin naechst(e, initium, ekm, i) ;

T_{0} := S_{e};

if T_{0} = 0 then for k := 0 to i do S_{e,k} := 0 else begin for k := 1 to i do

T_{k−1}^{∗} := T_{k−1}( …, x_{i−k+2}, x_{i−k+1}, …) ; T_{k} := (T_{k−1} − T_{k−1}^{∗})/(x_{i−k+2} − x_{i−k+1}) S_{e,i} := T_{i}; for k := i − 1 down to 0 do

S_{e,k} := T_{k} − ∑_{j=k+1}^{i} p_{jk}S_{e,j}

end end i := i + 1

end end

Will man dies wirklich programmieren, so wird man bei der Berechnung der T_{k} von der Formel

x^{a}y^{b} − x^{b}y^{a} = (y − x) ∑_{i=0}^{b−a−1} y^{a+i}x^{b−1−i},

die im Falle a ≤ b gilt, und von der Formel

x^{a}y^{b} − x^{b}y^{a} = (x − y) ∑_{i=0}^{a−b−1} x^{b+i}y^{a−1−i},

die für a > b gilt, Gebrauch machen. Ferner wird man die p_{jk} nicht explizit ausrechnen and abspeichern. Sie werden ja nur einmal benötigt, so daß es genügt, sich bei der Berechnung von S_{e,k} sukzessive die in p_{jk} vorkommenden Monome zu verschaffen. Dabei ist es nützlich zu wissen, daß durch

(r_{1}, …, r_{n}) → (r_{1}, r_{1} + r_{2} + 1, …, r_{1} + r_{2} + ⋯ + r_{k} + k − 1)

eine Bijektion der Menge der in p_{j,k} vorkommenden r auf die Menge der k-Teilmengen von {0, …, n + k − 1} definiert wird.

SYMMETRISCHE POLYNOME

Ist f ∈ Z[x] und ist der Leitkoeffizient von f gleich 1, so gilt für die Diskriminante Dis(f) nach einem Satz von STICKELBERGER, daß Dis(f) = 0 oder 1 (mod 4) ist. SCHUR bewies diesen Satz, indem er zeigte, daß es ganze Zahlen a und b gibt mit Dis(f) = a^{2} − 4b. Hierin sind a und b natürlich nicht eideutig bestimmt. Das von SCHUR benutzte a war nun nichts anderes als die Permanente der Vandermondematrix aus den Nullstellen von f. Nun ist diese Permanente eine symmetrische Funktion in den Nullstellen von f, so daß sie nach dem Waringschen Satz ein Polynom in den Koeffizienten von f ist. Es erhebt sich daher die Frage, ob man diese Permanente ohne explizite Kenntnis der Nullstellen fon f berechnen kann. Dies ist in der Tat möglich, wie man folgendermaßen einsehen kann.

Es seien x_{1}, …, x_{n} Überstimmte über Z. Ferner sei

Vdm(x_{1}, …, x_{n}) = | \begin{matrix}1 & & & x_{1} & & & x_{1}^{2} & & … & & x_{1}^{n−1} \\ 1 & & & x_{2} & & & x_{2}^{2} & & … & & x_{2}^{n−1} \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ 1 & & & x_{n} & & & x_{n}^{2} & & … & & x_{n}^{n−1} \end{matrix} | .

Dann ist

perm(Vdm(x_{1}, …, x_{n})) = ∑_{σ∈S_{n}} ∏_{i=1}^{n} x_{i}^{σ(i)−1}.

Dies ist ein symmetrisches Polynom in den x_{i}. Dieses Polynom kann man nun mit Hilfe bekannter Algorithmen als Polynom in den elementarsymmetrischen Polynomen der x_{i} darstellen. Da die elementarsymmetrischen Funktionen in den Nullstellen von f nach dem Vietaschen Wurzelsatz bis aufs Vorzeichen, das man auch beherrscht, die Koeffizienten von f sind, ist unsere Frage bejahend beantwortet. Dieser Algorithmus ist praktisch nur für sehr kleine n durchführbar, wie im übrigen auch der nächste, der jedoch nicht ganz so aufwendig ist.

Wir definieren im Polynomring Z[y_{1}, …, y_{n−1}] rekursiv Polynome f_{2}, …, f_{n} vermöge f_{2} = y_{1} und

f_{k+1} = y_{k}^{k} ∑_{α} r_{α} (y_{1}^{α_{1}} − y_{k}^{α_{1}}) · (y_{k−1}^{α_{k−1}} − y_{k}^{α_{k−1}}) .

falls

f_{k} = ∑_{α} r_{α} y_{1}^{α_{1}} … y_{k−1}^{α_{k−1}}

ist. Ist dann

f_{n} = ∑_{β} r_{β} y_{1}^{β_{1}} … y_{n−1}^{β_{n−1}},

so ist

perm(Vdm(x_{1}, …, x_{n})) = ∑_{β} r_{β} τ_{β_{1}}^{(n)} … τ_{β_{n−1}}^{(n)}.

Dabei ist τ_{0}^{(n)} = 1 und τ_{i}^{(n)} = ∑_{j=1}^{n} x_{j}^{i}, falls i ≥ 1 ist. Man beachte, daß

die Definition von τ_{0}^{(n)} von der üblichen Definition abweicht. Üblich ist, τ_{0}^{(n)} = n su setzen. Die τ_{i}^{(n)} kann man nun mit Hilfe der Newtonschen Formeln durch die elementarsymmetrischen Polynome in den x_{1}, …, x_{n} ausdrücken, so daß wir eine zweite Lösung unserer Aufgabe gefunden haben.

Analysiert man die Entstehung der Monome in f_{n}, so folgt ∑_{β} |r_{β}| = ∑_{k=1}^{n−1} a(n, k), wobei die a(n, k) durch folgende Rekursion definiert sind : a(m, 0) = 0 für alle m und a(2, 1) = 1. Ferner

a(m + 1, i + 1) = ∑_{k=i}^{m−1} \binom{k}{i}a(m, k).

Meine Vermutung lautete, daß ∑_{k=1}^{n−1} a(n, k) = (n − 1)! ist. Die Herren NICOLETTI und COMTET bemerkten an Hand einer kleinen Tabelle der a(n, k), daß a(n, k) = c(n − 1, k) sein müsse, wobei c(n − 1, k) die vorzeichenlosen Stirlingzahlen sind. Dies konnte ich mittlerweile verifizieren, so daß in der Tat

∑_{β} |r_{β}| = ∑_{k=1}^{n−1} a(n, k) = (n − 1)!

ist. Einen anderen Beweis dieser Tatsache schickte mir Herr E. TRIESCH (Aachen). Der zweite Algorithmus ist also ebenfalls sehr aufwendig.

Eine Note mit detaillierten Beweisen ist in Vorbereitung.

Heinz Lüneburg,

Fachbereich Mathematik der Universität, Pfaffenbergstraße 95, D-6750 Kaiserslautern.