Polinomi simmetrici, passo dopo passo

Un polinomio in $x_1, \ldots, x_n$ è simmetrico se resta invariato permutando le variabili: $x_1^2 + x_2^2 + x_3^2$ e $x_1 x_2 x_3 - 1$ lo sono, $x_1^2 x_2$ no, perché scambiando $x_1$ e $x_2$ diventa $x_1 x_2^2$. Il teorema fondamentale dei polinomi simmetrici afferma che, su un campo $F$, ogni polinomio simmetrico si scrive in un solo modo come polinomio in pochi polinomi di base, i polinomi simmetrici elementari $e_1, \ldots, e_n$:

$$\begin{aligned} \operatorname{Sym}[X_n] &= F[e_1, \ldots, e_n] \\ &\cong F[y_1, \ldots, y_n]. \end{aligned}$$

Qui $X_n$ è l’insieme $\{x_1, \ldots, x_n\}$, $\operatorname{Sym}[X_n]$ è l’anello dei polinomi simmetrici in $X_n$ a coefficienti in $F$, e $F[y_1, \ldots, y_n]$ è un anello di polinomi in $n$ nuove variabili. L’uguaglianza dice che ogni polinomio simmetrico è un polinomio negli $e_i$; l’isomorfismo, che manda ogni $y_i$ in $e_i$, che lo è in un solo modo.

La dimostrazione usuale è un algoritmo, e per giunta breve. L’ho implementato per la prima volta nel 2022, in un notebook di SageMath archivio; qui viene eseguito direttamente nel browser.

I polinomi simmetrici elementari

Fissiamo $n \in \NN^+$, il numero di variabili. Il polinomio simmetrico elementare di grado $d \geq 1$ è la somma di tutti i prodotti di $d$ variabili distinte,

$$e_d = \sum_{1 \leq i_1 < i_2 < \cdots < i_d \leq n} \underbrace{x_{i_1} \cdots x_{i_d}}_{d \text{ fattori}},$$

ed $e_0 = 1$. Con tre variabili, ad esempio,

$$\begin{aligned} e_1 &= x_1 + x_2 + x_3, \\ e_2 &= x_1 x_2 + x_1 x_3 + x_2 x_3, \\ e_3 &= x_1 x_2 x_3, \end{aligned}$$

e $e_d = 0$ per ogni $d > n$, perché non ci sono abbastanza variabili tra cui scegliere.

Ordinare i monomi

L’algoritmo deve sapere quale termine di un polinomio viene per primo. Un monomio $x_1^{\alpha_1} \cdots x_n^{\alpha_n}$ si scrive $x^\alpha$, con $\alpha = (\alpha_1, \ldots, \alpha_n) \in \NN^n$, e i monomi si ordinano secondo l’ordine lessicografico graduato (deglex): prima per grado totale $\alpha_1 + \cdots + \alpha_n$, poi, tra monomi dello stesso grado, per l’esponente di $x_1$, poi per quello di $x_2$, e così via. Quindi $x_1^3 > x_1 x_2^2 > x_2^3 > x_1^2$ e, in generale, $x_1 > x_2 > \cdots > x_n$. Il termine di testa di un polinomio non nullo è il suo termine con il monomio più grande, e quel monomio è il suo monomio di testa.

Deglex non è un modo qualsiasi di ordinare i monomi: è un ordine monomiale, cioè un ordine totale sui monomi tale che

1. è compatibile con la moltiplicazione: se $x^\alpha < x^{\alpha'}$, allora $x^\alpha x^\gamma < x^{\alpha'} x^\gamma$ per ogni monomio $x^\gamma$;
2. è un buon ordine: ogni insieme non vuoto di monomi ha un elemento minimo. Equivalentemente, non esiste una successione infinita strettamente decrescente di monomi $x^{\alpha^{(1)}} > x^{\alpha^{(2)}} > x^{\alpha^{(3)}} > \cdots$.

Deglex ha entrambe le proprietà. Moltiplicare per $x^\gamma$ aggiunge la stessa quantità ai gradi di $x^\alpha$ e $x^{\alpha'}$ e gli stessi esponenti a entrambi, quindi nessuno dei due confronti cambia. E al di sotto di un qualsiasi monomio ce n’è solo un numero finito di altri, quelli di grado non superiore al suo, quindi una successione strettamente decrescente deve arrestarsi.

La prima proprietà è ciò che garantisce il buon comportamento dei termini di testa: il termine di testa di un prodotto è il prodotto dei termini di testa. Ogni altro prodotto di un termine di $g$ per un termine di $h$ coinvolge almeno un monomio più piccolo, e la moltiplicazione lo mantiene più piccolo. La seconda proprietà è ciò che farà terminare l’algoritmo.

Un ulteriore fatto è specifico dei polinomi simmetrici: il loro monomio di testa ha esponenti non crescenti, $\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_n$. Se $x^\alpha$ compare con $\alpha_i < \alpha_{i+1}$, scambiando $x_i$ e $x_{i+1}$ si ottiene un altro monomio del polinomio, e più grande: quindi $x^\alpha$ non era il monomio di testa.

Cancellare il termine di testa

Sia $f$ simmetrico, con termine di testa $c \, x^\alpha$. L’idea della dimostrazione è eliminare questo termine con un prodotto di polinomi simmetrici elementari: trovare una sequenza finita di esponenti $b = (b_1, \ldots, b_n) \in \NN^n$ tale che

$$e^b = e_1^{b_1} e_2^{b_2} \cdots e_n^{b_n}$$

abbia lo stesso monomio di testa $x^\alpha$. Allora in $f - c \, e^b$ i due termini di testa si cancellano.

Poiché i termini di testa si moltiplicano, il termine di testa $\operatorname{lt}(e^b)$ di $e^b$ è il prodotto di quelli dei suoi fattori, e il termine di testa di $e_k$ è $x_1 x_2 \cdots x_k$, con coefficiente $1$. La variabile $x_i$ vi compare esattamente quando $k \geq i$, quindi

$$\begin{aligned} \operatorname{lt}(e^b) &= \prod_{k=1}^{n} (x_1 x_2 \cdots x_k)^{b_k} \\ &= x_1^{b_1 + b_2 + \cdots + b_n} \, x_2^{b_2 + \cdots + b_n} \cdots x_n^{b_n}. \end{aligned}$$

Perché questo sia $x^\alpha$, gli esponenti devono coincidere, e $b$ deve risolvere un sistema triangolare:

$$\begin{aligned} \alpha_1 &= b_1 + b_2 + \cdots + b_n, \\ \alpha_2 &= b_2 + \cdots + b_n, \\ &\;\;\vdots \\ \alpha_n &= b_n. \end{aligned}$$

Sottraendo ogni equazione da quella che la precede resta $b_i = \alpha_i - \alpha_{i+1}$, e l’ultima dà $b_n = \alpha_n$. C’è quindi un unico candidato, che chiamiamo $\beta(\alpha)$:

$$\beta(\alpha)_i = \begin{cases} \alpha_i - \alpha_{i+1} & \text{se } 1 \leq i < n, \\ \alpha_i & \text{altrimenti.} \end{cases}$$

Si tratta di una sequenza valida di esponenti, senza componenti negative, esattamente quando $\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_n$, condizione sempre soddisfatta dal monomio di testa di un polinomio simmetrico. Ad esempio, con $n = 3$ e monomio di testa $x_1^3 x_2 x_3$, $\alpha = (3, 1, 1)$ dà $\beta(\alpha) = (2, 0, 1)$, e in effetti $e_1^2 e_3 = (x_1 + x_2 + x_3)^2 \, x_1 x_2 x_3$ ha monomio di testa $x_1^2 \cdot x_1 x_2 x_3 = x_1^3 x_2 x_3$.

L’algoritmo

Dato un polinomio simmetrico $f$:

• se $f$ è $0$ o una costante, è già un polinomio negli $e_i$, e non c’è nulla da fare;
• altrimenti, siano $c \, x^\alpha$ il suo termine di testa in deglex e $b = \beta(\alpha)$. Allora $f$ è $c \, e^b$ più l’espressione negli $e_i$ di $f - c \, e^b$, dove $e^b$ è sviluppato nelle $x_i$; quest’ultima si trova eseguendo di nuovo l’algoritmo.

Il polinomio $f - c \, e^b$ è ancora simmetrico, in quanto differenza di polinomi simmetrici, e il suo monomio di testa è più piccolo di $x^\alpha$: i due termini di testa si cancellano, e ogni altro termine di $f$ e di $c \, e^b$ ha un monomio più piccolo. Eseguendo l’algoritmo si ottengono quindi polinomi simmetrici $f_0 = f, f_1, f_2, \ldots$ i cui monomi di testa decrescono strettamente. Poiché deglex è un buon ordine, una tale successione non può proseguire all’infinito: dopo un numero finito di passi ciò che resta è $0$, e i termini $c \, e^b$ raccolti lungo il percorso hanno per somma $f$.

Anche l’espressione è unica. Supponiamo che $f = P(e_1, \ldots, e_n) = Q(e_1, \ldots, e_n)$ per due polinomi $P, Q \in F[y_1, \ldots, y_n]$. La loro differenza $R = P - Q$ soddisfa allora $R(e_1, \ldots, e_n) = 0$, e basta mostrare che ciò implica $R = 0$, cioè che nessun polinomio non nullo si annulla quando alle sue variabili si sostituiscono gli $e_i$ (gli $e_i$ sono algebricamente indipendenti). Scriviamo

$$\begin{aligned} R &= \sum_{b \in S} c_b \, y^b, \\ R(e_1, \ldots, e_n) &= \sum_{b \in S} c_b \, e^b, \end{aligned}$$

dove $S \subset \NN^n$ è l’insieme finito degli esponenti il cui coefficiente $c_b$ non è nullo, e supponiamo che $S$ non sia vuoto. Ogni $e^b$ ha termine di testa $x^{\alpha(b)}$, con coefficiente $1$ e $\alpha(b)_i = b_i + b_{i+1} + \cdots + b_n$, e a $b$ distinti corrispondono $\alpha(b)$ distinti, poiché $b$ si ricava da $\alpha(b)$ come $\beta(\alpha(b))$. Tra i finiti monomi $x^{\alpha(b)}$ con $b \in S$ ce n’è quindi uno massimo, $x^{\alpha(b^*)}$, ottenuto da un solo $b^* \in S$. Esso compare in $c_{b^*} e^{b^*}$ con coefficiente $c_{b^*}$; ogni altro $e^b$ ha solo monomi non superiori al proprio monomio di testa $x^{\alpha(b)}$, che è più piccolo di $x^{\alpha(b^*)}$, e quindi non contiene affatto $x^{\alpha(b^*)}$. Il coefficiente di $x^{\alpha(b^*)}$ in $R(e_1, \ldots, e_n)$ è allora $c_{b^*} \neq 0$, in contraddizione con $R(e_1, \ldots, e_n) = 0$. Quindi $S$ è vuoto, $R = 0$ e $P = Q$.

Il calcolatore qui sotto mostra ogni passo: il termine di testa, $\alpha$ e $\beta(\alpha)$, e ciò che resta, $f_i$. Per mantenere leggibili i polinomi lunghi, i termini sono raggruppati in orbite: $m_\lambda$ è la somma dei monomi distinti i cui esponenti sono un riordinamento di $\lambda$, così che con $n = 3$

$$\begin{aligned} m_{(2,1)} = {} & x_1^2 x_2 + x_1^2 x_3 + x_1 x_2^2 \\ & + x_2^2 x_3 + x_1 x_3^2 + x_2 x_3^2. \end{aligned}$$

Un polinomio è simmetrico esattamente quando è combinazione degli $m_\lambda$, con $\lambda_1 \geq \cdots \geq \lambda_n$; il calcolatore li elenca a partire dal più grande $x^\lambda$, quindi il primo contiene il termine di testa. Anche i calcoli avvengono in questa forma: il calcolatore non sviluppa mai un prodotto $e^b$, ma moltiplica per ogni $e_j$ operando direttamente sui coefficienti delle orbite.

Il polinomio deve essere simmetrico. Se non lo è, l’algoritmo non può terminare con successo: se così fosse, il polinomio sarebbe combinazione di polinomi simmetrici, e quindi simmetrico a sua volta, ↯. L’esempio Non simmetrico mostra dove l’algoritmo si inceppa: prima o poi il termine di testa ha esponenti non disposti in ordine non crescente, $\beta(\alpha)$ ha una componente negativa, e nessun prodotto degli $e_i$ ha quel termine di testa.

Somme di potenze

Per le somme di potenze $p_k = x_1^k + \cdots + x_n^k$ esiste una strada più diretta, le identità di Newton–Girard archivio. Esse esprimono $p_k$, per $k \geq 1$, in termini degli $e_i$ e delle somme di potenze precedenti:

$$p_k = (-1)^{k+1} \Bigl( k \, e_k + \sum_{i=1}^{k-1} (-1)^i \, p_i \, e_{k-i} \Bigr),$$

dove $e_i = 0$ per ogni $i > n$ (e $p_0 = n$, poiché $x_i^0 = 1$). Calcolando $p_1$, poi $p_2$, e così via fino a $p_k$, ciascuna a partire dalle precedenti, si ottiene un’espressione; l’algoritmo generale applicato a $x_1^k + \cdots + x_n^k$ ne fornisce un’altra. Per l’unicità devono essere lo stesso polinomio, e in effetti la loro differenza è zero:

Il discriminante

Sia ora

$$f(x) = x^n + a_{n-1} x^{n-1} + \cdots + a_0$$

con radici $x_1, x_2, \ldots, x_n$ in $\CC$, ciascuna contata tante volte quanto la sua molteplicità, in modo che $f(x) = (x - x_1) \cdots (x - x_n)$. Il discriminante di $f$ è il prodotto

$$\Delta(f) = \prod_{1 \leq i < j \leq n} (x_i - x_j)^2,$$

e indica se $f$ ha una radice multipla:

$$\exists \, i \neq j : x_i = x_j \iff \Delta(f) = 0.$$

È facile verificare che $\Delta(f)$ è un polinomio simmetrico nelle radici. Ogni permutazione è composizione di trasposizioni, quindi basta verificare che scambiare due radici $x_i$ e $x_j$ lo lasci invariato:

• i fattori che non contengono nessuna delle due restano immutati;
• i fattori che ne contengono una sola si scambiano a coppie, $(x_i - x_k)^2$ con $(x_j - x_k)^2$, al più con la base cambiata di segno, cosa che il quadrato annulla;
• il fattore che le contiene entrambe cambia il segno della propria base, $(x_i - x_j)^2$ diventa $(x_j - x_i)^2$, e una volta elevato al quadrato resta invariato.

Quindi, per il teorema fondamentale, $\Delta(f)$ si scrive in un solo modo in termini dei polinomi simmetrici elementari delle radici. Ma questi non sono altro che i coefficienti di $f$, a meno del segno: sviluppando $(x - x_1) \cdots (x - x_n)$ e confrontando con $f$,

$$e_i(x_1, \ldots, x_n) = (-1)^i a_{n-i}$$

per $0 \leq i \leq n$, con $a_n = 1$. Eseguendo l’algoritmo su $\prod_{i<j} (x_i - x_j)^2$ e sostituendo $(-1)^i a_{n-i}$ a ogni $e_i$ si ottiene quindi il discriminante di ogni polinomio monico di grado $n$ in termini dei suoi coefficienti, senza conoscerne le radici. Per $n = 2$ è il familiare $\Delta = a_1^2 - 4 a_0$; per $n = 3$,

$$\begin{aligned} \Delta = {} & a_1^2 a_2^2 - 4 a_0 a_2^3 - 4 a_1^3 \\ & + 18 \, a_0 a_1 a_2 - 27 a_0^2, \end{aligned}$$

che per $x^3 + p x + q$ si riduce a $-4p^3 - 27q^2$.

Un polinomio il cui coefficiente direttore $a_n$ non è $1$ ha le stesse radici di $f / a_n$, che è monico; il suo discriminante si definisce di solito come $a_n^{2n-2} \, \Delta(f / a_n)$. Il fattore lo rende un polinomio in $a_0, \ldots, a_n$ a coefficienti interi, e si annulla esattamente quando si annulla $\Delta(f / a_n)$.

Qui sotto, la formula per il grado del polinomio inserito viene calcolata con l’algoritmo e poi valutata nei suoi coefficienti. Il primo esempio, $(x - 1)^2 (x + 2) = x^3 - 3x + 2$, ha una radice doppia, quindi il suo discriminante è zero; il secondo, $(x - 1)(x + 1)(x + 3) = x^3 + 3x^2 - x - 3$, ha tre radici distinte e un discriminante non nullo.