Algoritmi combinatori per l’interpolazione polinomiale in dimensione ≥ 2.

L.Cerlienco e M.Mureddu Università di Cagliari, Italy

1 Introduzione.

Sia K un campo, X := {x_{1}, x_{2}, …, x_{n}} un insieme di indeterminate e K[X] := K[x_{1}, …, x_{n}] l’usuale algebra dei polinomi nelle indetermiante x_{j}. Faremo uso delle notazioni: i := (i_{1}, …, i_{n}) ∈ N^{n} e x^{i} := x_{1}^{i_{1}} ⋯ x_{n}^{i_{n}}. Consideriamo i problemi seguenti.

Problema 1. Dati N elementi distinti P_{i} (i = 1, …, N) dello spazio vettoriale K^{n} e fissati N valori α_{i} ∈ K, si vuole determinare un polinomio p(x_{1}, …, x_{n}) ∈ K[X] tale che

p(P_{i}) = α_{i} (i = 1, …, N).

NB. Volutamente non ci si è riferiti a K^{n} come al K–spazio affine n– dimensionale A_{K}^{n}. Infatti alcuni aspetti rilevanti della trattazione che segue \underline{non} hanno — nel caso n ≥ 2 — carattere geometrico intrinseco. Rinviamo all’Appendice 1 per maggiori chiarimenti su questo aspetto. È pertanto solamente per comodità di linguaggio che chiameremo punti di K^{n} gli elementi P_{i}.

Problema 2. Analogo al Problema 1 ma nell’ipotesi che si conoscano oltre che i valori di p nei punti P_{i} anche di quelli di certe sue derivate parziali (derivate di ordine eventualmente variabile da punto a punto).

Occupiamoci dapprima del Problema 1. Nei termini enunciati esso è mal posto; occorre precisare ulteriormente la natura del polinomio cercato in modo tale che venga assicurata l’esistenza e l’unicità della soluzione. Infatti, è immediato osservare che se p è un polinomio che soddisfa alle condizioni richieste, tale è pure un qualunque altro polinomio p′ congruo a p modulo l’ideale ℑ(P) di tutti i polinomi che si annullano sui punti dell’insieme P := {P_{1}, …, P_{N}}.

Tale ideale ℑ(P) è cofinito:

codimℑ(P) := dimK[X]/ℑ(P) = N.

Se x^{i_{1}}, …, x^{i_{N}} sono monomi tali che le classi di equivalenza [x^{i_{1}}], …, [x^{i_{N}}] (modulo ℑ(P)) formano una base per l’algebra quoziente K[X]/ℑ(P) — basi di questo tipo verranno dette basi monomiali — la classe di equivalenza [p] di un qualunque polinomio p ∈ K[X] contiene uno ed un solo polinomio \overline{p} della forma

\overline{p} = a_{1}x^{i_{1}} + ⋯ + a_{N}x^{i_{N}}  (a_{i} ∈ K)  (1)

( che chiameremo “resto di p (mod. ℑ(P)) rispetto alla base x^{i_{1}}, …, x^{i_{N}} fissata”). Si può quindi affermare che esiste uno ed un solo polinomio della forma (1) soddisfacente alle condizioni poste.

Appare opportuno imporre un’altra ragionevole restrizione, atta a limitare la varietà delle possibili basi monomiali e quindi delle soluzioni al problema. È infatti naturale — ed è ciò che si fa tacitamente nel caso unidimensionale — privilegiare basi monomiali che siano “minimali” nel senso seguente. Indichiamo con M l’insieme dei termini (:= monomi monici) di K[X] e con ⪯ un arbitrario term-ordering su M (ordine lineare compatibile con la sua struttura di monoide); ancora: “x^{i} ≺ x^{j}” sta per “x^{i} ⪯ x^{j} e x^{i} ≠ x^{j}”. La base monomiale [x^{i_{1}}], …, [x^{i_{N}}] di K[X]/ℑ(P) (x^{i_{1}} ≺ … ≺ x^{i_{N}}) verrà detta minimale rispetto a ⪯ se, per qualunque altra base monomiale [x^{i′^{1}}], …, [x^{i′^{N}}] di K[X]/ℑ(P) (con x^{i′^{1}} ≺ … ≺ x^{i′^{N}}) si ha x^{i_{j}} ⪯ x^{i′^{j}} per ogni j = 1, …, N. Nel seguito chiameremo base monomiale minimale ogni base monomiale che sia minimale rispetto ad un qualche ordine lineare compatibile ⪯.

Come vedremo nei prossimi paragrafi, qualora si disponga di una base monomiale per K[X]/ℑ(P), il Problema 1 è di soluzione pressoché immediata. Esso viene così ricondotto a determinare algoritmi effettivi per trovare una base monomiale minimale per K[X]/ℑ(P).

Per tale questione verranno proposte soluzioni di tipo diverso: sia riconducendola alla ricerca di un minore non nullo di ordine N di una matrice a N righe; sia, dopo aver determinato un sistema di generatori per ℑ(P), facendo uso della teoria delle basi di Groebner; sia infine — e questo riteniamo essere il principale risultato del presente lavoro — attraverso un semplice algoritmo puramente combinatorio che fornisce direttamente la base monomiale, minimale rispetto all’ordine lessicografico inverso ⪯_{i.l.}, di K[X]/ℑ(P)

Il Problema 2 richiederà ulteriori precisazioni, dopo di che la sua soluzione non si discosterà molto da quella del Problema 1. Ad esso sarà dedicato l’ultimo paragrafo della presente nota.

2 L’ideale ℑ(P) dell’insieme P := {P_{1}, …, P_{N}}.

2.1 Dato un ideale I ⊆ K[X], sia G = {g_{1}, ⋯, g_{s}} la base di Groebner ridotta (cfr. [1]) di I relativa all’ordine ⪯, in simboli:

G = {g_{1}, ⋯, g_{s}} := RGB_{⪯}(I).

Detto t_{i} il termine direttore di g_{i} (cioè il termine di g_{i} più grande nell’ordine ⪯), poniamo

T_{i} := t_{i} · M e B := M − ⋃_{i=1}^{s} T_{i}.

È facile verificare che l’insieme delle classi di equivalenza, modulo I, dei termini in B costituisce una base monomiale per K[X]/I che è minimale rispetto al term-ordering ⪯ considerato.

Osserviamo anche che l’insieme F := F_{≺}(I) := {i ∈ N^{n} | x^{i} ∈ B} è un diagramma di Ferrers (cfr. 4.6) i cui elementi diedrali esterni f_{1}, …, f_{s} sono tali che x^{f_{i}} = t_{i}. Viceversa, è facile provare che se F ⊆ N^{n} è tale che {[x^{i}]_{I} | i ∈ F} costituisce una base monomiale, minimale rispetto al term-ordering ⪯, per K[X]/I allora

a) F è un diagramma di Ferrers;

b) indicati con f_{1}, …, f_{s} gli elementi diedrali esterni di F e, per ogni j = 1, …, s, con p_{j} ∈ span_{K}{x^{i} | i ∈ F_{j}} (dove F_{j} := {i ∈ F | i ≺ f_{j}} ) il polinomio univocamente determinato tale che x^{f_{j}} − p_{j} ≡ 0 mod.I, allora l’insieme {x^{f_{1}} − p_{1}, …, x^{f_{s}} − p_{s}} costituisce la base di Groebner ridotta RGB_{⪯}(I). Nel seguito queste osservazioni verranno spesso sfruttate tacitamente.

2.2 Per ogni sottoinsieme T ⊆ M, indichiamo con T_{≺} la sequenza

T_{≺} := (t_{0}, t_{1}, …, t_{s}, …) (t_{i} ∈ T)

formata dagli elementi di T ordinati secondo l’ordine indotto da ⪯: r < s ⇒ t_{r} ≺ t_{s}.

Se P ∈ K^{n} poniamo

v_{P} : K[x_{1}, …, x_{n}] ⟶ K  (valutazione in P)
f  ⟼ f(P)

e indichiamo con T_{≺}(P) la lista

T_{≺}(P) := (v_{P} (t_{0}), …, v_{P} (t_{s}), …).

Inoltre, in riferimento ad un insieme finito (lin. ordinato) P = {P_{1}, …, P_{N}} ⊆ K^{n}, indichiamo con T_{≺}(P) la matrice con N′ := #T ≤ ∞ colonne ed N righe, la cui j-esima riga è T_{≺}(P_{j}).

2.3 Adottando anche nel presente lavoro la terminologia già utilizzata in [2], chiameremo ideale elementare un qualunque ideale Γ = (γ_{1}(x_{1}), …, γ_{n}(x_{n})) di K[x_{1}, …, x_{n}] generato da n polinomi, ciascuno in una sola variabile. Osserviamo che l’insieme dei generatori (γ_{1}, …, γ_{n}) di Γ costituisce anche la sua base di Groebner ridotta (qualunque sia l’ordine lineare compatibile ⪯ adottato).

Conviene associare a P = {P_{1}, …, P_{N}} un ideale elementare Γ nel modo seguente. Dapprima associamo a P l’insieme P̃ di tutti i punti P (a_{1}, …, a_{n}) di K^{n} tale che, per ogni 1 ≤ j ≤ n, a_{j} sia la j-esima coordinata di almeno uno dei punti P_{1}, …, P_{N}, e poniamo poi Γ := ℑ(P̃).

Osserviamo che se il complesso dei punti in P ha h_{j} valori distinti per jesime coordinate allora #P̃ = h := h_{1} ⋯ h_{n} ≥ N = #P. Conveniamo inoltre di ordinare linearmente i punti in P̃ assumendo che i primi N siano proprio i punti di P ⊆ P̃:

P̃ = {P_{1}, …, P_{N}, P_{N+1}, …, P_{h}} (h = h_{1} ⋯ h_{n}) .

Va notato che l’ideale Γ := ℑ(P̃) di P̃, è l’ideale elementare generato dagli n polinomi quadrat-frei γ_{j}(x_{j}), j = 1, …, n , definiti dalle condizioni

deg(γ_{j}) = h_{j} ,

γ_{j}(ρ) = 0 ⟺ ρ è la j-esima coordinata di almeno uno dei punti P_{1}, …, P_{N} .

Pertanto le classi di equivalenza mod.Γ dei termini in

H := {x^{i} = x_{1}^{r_{1}} ⋯ x_{n}^{r_{n}} | 0 ≤ r_{j} ≤ h_{j} − 1}

costituiscono una base per K[X]/Γ.

Proposizione 1 La matrice H := H_{≺}(P̃) è non degenere.

Dimostrazione. Facciamo uso della formula (vedi Appendice 2)

| A_{1} ⊗ A_{2} ⊗ ⋯ ⊗ A_{n} | =  (2)
=| A_{1} |^{h_{2}···h_{n}} | A_{2} |^{h_{1}h_{3}···h_{n}} ⋯ | A_{n} |^{h_{1}···h_{n−1}} = \frac{(| A_{1} | ⋯ | A_{n} |)^{h_{1}h_{2}···h_{n}}}{| A_{1} |^{h_{1}} ⋯ | A_{n} |^{h_{n}}}

dove A_{j} è una matrice quadrata d’ordine h_{j}.

L’enunciato discende dalla (2) non appena si osservi che la matrice H_{≺}(P̃) è il prodotto tensoriale di n matrici di Vandermonde, la j-esima delle quali è associata alle j-esime coordinate dei punti P_{1}, …, P_{N}. Anzi, posto P_{i} ≡ (ρ_{i,1}, …, ρ_{i,n}) con P_{i} ∈ P, si ha

det H_{≺}(P̃) = ∏_{j=1}^{n}[ ∏_{ρ_{r,j}≠ρ_{s,j}}(ρ_{r,j} − ρ_{s,j})]^{\overline{h}^{j}} ≠ 0  (3)

con \overline{h}_{j} := h/h_{j}. □

2.4 Per la Prop.1 la matrice H := H_{≺}(P̃) è invertibile. Consideriamo la sua inversa H^{−1} = (α_{s}^{r}) e, posto H_{≺} := {x^{i_{1}}, …, x^{i_{h}}}, associamo alla sua s-esima colonna il polinomio p_{s} = ∑_{r=1}^{h} α_{s}^{r}x^{i_{r}} .

Proposizione 2 L’ideale I := (p_{N+1}, …, p_{h}, γ_{1}, …, γ_{n}) è l’ideale dell’insieme P = {P_{1}, …, P_{N}}:

I := (p_{N+1}, …, p_{h}, γ_{1}, …, γ_{n}) = ℑ(P).

Dimostrazione Il fatto che H^{−1} sia inversa di H comporta che p_{s} assume il valore 1 in P_{s} ∈ P̃ ed il valore zero in tutti gli altri punti di P̃:

p_{s}(P_{t}) = v_{P_{t}}(p_{s}) = δ_{s}^{t}.

Pertanto V(I) = P (V(I) indica l’insieme algebrico dell’ideale I). Ne consegue che I ⊆ ℑ(V(I)) = ℑ(P) e quindi che codim I ≥ N = codim ℑ(P). Per concludere che I = ℑ(P) basta allora provare che codim I = N. È cioè sufficiente provare che in H esistono N monomi x^{i_{σ(1)}}, …, x^{i_{σ(N)}} tali che per ciascuno x^{i_{σ(N+t)}} (t = 1, …, h − N) degli altri si abbia

x^{i_{σ(N+t)}} ≡ ∑_{r=1}^{N} η_{t,r} x^{i_{σ(r)}} (mod. I).  (4)

Per la Prop. 1, la matrice (di tipo N × h) H_{≺}(P) ha rango N. Fissato un suo minore non nullo L di ordine N, siano x^{i_{σ(1)}}, …, x^{i_{σ(N)}} ∈ H i monomi corrispondenti alle colonne di L e x^{i_{σ(N+1)}}, …, x^{i_{σ(h)}} gli altri; si ha:

p_{s} = ∑_{r=1}^{h} α_{s}^{σ(r)} x^{i_{σ(r)}}

Riguardando i monomi x^{i_{σ(r)}} come h indeterminate, consideriamo il sistema di h − N equazioni lineari nelle x^{i_{σ(r)}}:

∑_{r=1}^{h} α_{s}^{σ(r)} x^{i_{σ(r)}} = 0 (s = N + 1, …, h).  (5)

Il minore

|α_{s}^{σ(r)}| (r, s = N + 1, …, h)

della matrice dei coefficienti è, per l’identità di Jacobi (cfr. [3]), diverso da zero. Pertanto è possibile risolvere il sistema (5) esprimendo le incognite x^{i_{σ(N+1)}}, … …, x^{i_{σ(h)}} in funzione delle x^{i_{σ(1)}}, …, x^{i_{σ(N)}}:

x^{i_{σ(N+t)}} = ∑_{r=1}^{N} η_{t,r} x^{i_{σ(r)}}.  (6)

Le operazioni formali che producono le (6) a partire dalle (5) possono essere anche utilizzate per ottenere le (4) a partire da

p_{s} = ∑_{r=1}^{h} α_{s}^{σ(r)} x^{i_{σ(r)}} ≡ 0 (mod. I) (s = N + 1, …, h).

L’asserto resta pertanto provato. □

3 Basi di Groebner per ℑ(P) e algoritmi per il calcolo del polinomio interpolatore.

3.1 In generale l’insieme di generatori (p_{N+1}, …, p_{h}, γ_{1}, …, γ_{n}) di I = ℑ(P), considerato nella Prop. 2, non costituisce una base di Groebner di I. In relazione a I = ℑ(P), assumiamo G e B come in 2.1; si ha ora: B ⊆ H e #B = N. Posto {b_{1}, …, b_{N}} := B_{≺}, sia B^{−1} la matrice inversa della matrice B := B_{≺}(P) d’ordine N (vengono usate, qui, le notazioni introdotte in 2.2). Posto infine α := (α_{1}, …, α_{N})_{−1}, il polinomio

p(x_{1}, …, x_{n}) := ∑_{j=1}^{N}(B^{−1}α)_{j} b_{j}  (7)

è il polinomio interpolatore cercato.

3.2 Un ragionamento alternativo, ma facente uso di un machinery simile, è il seguente.

Supponiamo che i punti P_{i} dati abbiano coordinate (ρ_{i,1}, …, ρ_{i,n}) ed associamo ad ogni P_{i} il punto Q_{i} ∈ K^{n+1} di coordinate (ρ_{i,1}, …, ρ_{i,n}, α_{i}). Sia J ⊆ K[x_{1}, …, x_{n}, y] l’ideale dell’insieme Q := {Q_{1}, …, Q_{N}}. Se fissiamo sul monoide dei termini di K[x_{1}, …, x_{n}, y] un ordine ⪯ per il quale la y abbia un peso infinito rispetto a ciascuna delle x_{i}, allora la base di Groebner ridotta L := RGB_{⪯}(J) di J rispetto a tale ordine conterrà — oltre che dei polinomi nelle variabili x_{1}, …, x_{n}— uno ed un solo polinomio contenente effettivamente la variabile y, diciamolo g(x_{1}, …, x_{n}, y).

Poichè, comunque si assegnino le prime coordinate σ_{1}, …, σ_{n} ∈ K esiste al più un valore β ∈ K tale che il punto di coordinate (σ_{1}, …, σ_{n}, β) stia in Q, tale polinomio dovrà essere della forma

y − p(x_{1}, …, x_{n}).

Il polinomio p(x_{1}, …, x_{n}) che qui compare sarà ovviamente quello cercato.

3.3 L’algoritmo descritto in 3.1 richiedeva la conoscenza di una base monomiale B di K[X]/ℑ(P) e ciò al fine di i) precisare la natura del polinomio p cercato: p ∈ span_{K}(B) e ii) determinare la matrice B := B_{≺}(P) che — via la (7) — consentiva di esprimere p. La procedura per trovare tale base prevedeva innanzitutto di a) determinare l’ideale I := ℑ(P) e b) trovare la base di Groebner ridotta per I.

Vogliamo qui osservare che si può anche procedere in modo diverso, in un certo senso invertendo quel ragionamento. Osserviamo in primo luogo che vi è una corrispondenza biunivoca tra le basi monomiali B ⊆ H e i minori non nulli d’ordine N della matrice H_{≺}(P). Determinato uno di tali minori non nulli, diciamolo A, sia B_{A} = {b_{1}, …, b_{N}} l’insieme dei termini corrispondenti alle colonne di A. A questo punto, assunto B = B_{A}, possiamo procedere come in 3.1, o anche semplicemente esprimere il polinomio y = p(x_{1}, …, x_{n}) cercato mediante la formula

| \begin{matrix}b_{1} & … & b_{N} & y \\ & & & α_{1} \\ & A & & ⋮ \\ & & & α_{N} \end{matrix} | = 0

dove A = (a_{ij}) con a_{ij} := b_{j}(P_{i}) = v_{P_{i}}(b_{j}).

3.4 Aggiungiamo a quanto precede che se il minore non nullo A di cui in 3.3 viene scelto in modo conveniente, possiamo sfruttarlo anche per ottenere una procedura atta a determinare direttamente un sistema di generatori dell’ideale cofinito ℑ(P) che sia anche la sua base di Groebner ridotta rispetto ad un fissato term-ordering ⪯. Supponiamo infatti di aver scelto A in modo tale che, detto b il termine di B_{A} più grande in ⪯ e detto D ⊆ H, D ≠ B_{A} un insieme di N termini tutti minori o uguali a b, si abbia det(D_{≺}(P)) = 0. Siano b_{1}, …, b_{N} (con b_{1} ≺ … ≺ b_{N}) i termini di H corrispondenti alle colonne di A e sia {τ_{1}, …, τ_{l}} il più piccolo sottoinsieme di H − {b_{1}, …, b_{N}} tale che, comunque si prenda τ ∈ H − {b_{1}, …, b_{N}}, esiste un 1 ≤ i ≤ l tale che τ_{i}|τ. Posto C^{i} := {b_{1}, …, b_{N}, τ_{i}}, sia D_{i} la matrice d’ordine N + 1 la cui prima riga è C_{≺}^{i} e le cui righe successive sono quelle della matrice C_{≺}^{i}(P) di tipo N × (N + 1); posto g_{i} = det(D_{i}), l’insieme {g_{1}, …, g_{l}} è allora la base di Groebner ridotta di I rispetto all’ordine ⪯. Un procedimento sostanzialmente equivalente al precedente è descritto in [5].

Va notato che, posto E_{≺} := {b_{1}, …, b_{s}}, E′_{≺} := {b_{1}, …, b_{s}, τ}, e E′′_{≺} := {b_{1}, …, b_{s}, σ}, con b_{i}, τ, σ ∈ M, se τ|σ allora

rango(E_{≺}(P)) = rango(E′_{≺}(P)) = s ⟹ rango(E′′_{≺}(P)) = s .

Questa osservazione ha due conseguenze immediate: a) da un lato essa consente di semplificare la precedente procedura per determinare A: una volta scartata la colonna corrispondente ad un termine τ, vengono automaticamente scartate anche quelle corrispondenti a tutti i multipli di τ; b) d’altro lato essa assicura che, in tale procedura, il riferimento alla matrice H_{≺}(P) — anziché, più in generale, alla matrice M_{≺}(P) — non è affatto restrittivo.

3.5 Un altro algoritmo per costruire — induttivamente sulla cardinalità di P — la base di Groebner ridotta RGB_{⪯}(ℑ(P)) di ℑ(P) rispetto al term-ordering ⪯, si fonda sulle osservazioni seguenti.

Sia {[x^{i}]_{ℑ(P)} | i ∈ F} la base monomiale, minimale rispetto al term-ordering ⪯, di K[X]/ℑ(P) e siano f_{1}, …, f_{s} (f_{1} ≺ … ≺ f_{s}) gli elementi diedrali esterni del diagramma di Ferrers F. Allora G := RGB_{⪯}(ℑ(P)) sarà della forma

G = {x^{f_{1}} − p_{1}, …, x^{f_{s}} − p_{s}}

dove ciascuno dei polinomi p_{i} ∈ K[X] contiene esclusivamente termini minori di x^{f_{i}} nell’ordine ⪯.

Consideriamo ora il punto P = (a_{1}, …, a_{n}) ∉ P e l’insieme P′ := P ∪ {P }, e siano F′ e G′ gli analoghi, relativamente a P′, di F e G. Indichiamo con j, 1 ≤ j ≤ s, il più piccolo indice tale che P non sia uno zero del polinomio x^{f_{j}} −p_{j}. È facile riconoscere che {[x^{i}]_{ℑ(P′)} | i ∈ F ∪{f_{j}} } costituisce una base monomiale per K[X]/ℑ(P′) (si tenga presente che codimℑ(P′) = N + 1 = #(F ∪ {f_{j}}) ), che inoltre (giacché F ∪ {f_{j}} è un diagramma di Ferrers) è minimale rispetto ad un opportuno term-ordering. Proviamo che tale term-ordering è proprio quello considerato, cioè che si ha F′ = F ∪ {f_{j}}, e nel contempo costruiamo la base di Groebner ridotta G′.

Iniziamo con l’osservare che gli elementi diedrali esterni di F, diversi da f_{j}, sono tali anche per il diagramma di Ferrers F ∪ {f_{j}}. Gli eventuali altri elementi diedrali esterni di F ∪{f_{j}} sono della forma f_{j} +ε_{h} (dove si è posto ε_{1} = (1, 0, …, 0), …, ε_{n} = (0, …, 0, 1) ). Supponiamo che siano tutti e soli quelli per i quali l’indice h appartiene all’insieme (eventualmente vuoto) {h_{1}, …, h_{t}} ⊆ {1, …, n}. (Va da sé che non è possibile precisare ulteriormente la natura di questo insieme, dipendendo essa da f_{j} e F). Assumiamo pertanto che gli elementi diedrali esterni di F ∪ {f_{j}} siano quelli dell’insieme

Φ = {f_{1}, …, f_{j−1}, f_{j+1}, …, f_{s}, f_{j} + ε_{h_{1}}, …, f_{j} + ε_{h_{t}}}

(con 0 ≤ t ≤ n). Per provare che F′ = F ∪ {f_{j}} occorre dimostrare che per ogni f ∈ Φ esiste in ℑ(P′) un polinomio della forma x^{f} − p, con p avente termini inferiori a f nel term-ordering ⪯ considerato. È facile controllare che tale polinomio è dato da

g_{i} := x^{f_{i}} − p_{i} − A_{i}/A_{j} (x^{f_{j}} − p_{j}) (i = 1, …, s; i ≠ j)

(dove A_{l} indica il valore che il polinomio x^{f_{l}} − p_{l} assume in P) per ogni

f_{i} ∈ Φ_{1} := {f_{1}, …, f_{j−1}, f_{j+1}, …, f_{s}},

mentre, per ogni elemento diedrale

f_{j} + ε_{h_{r}} ∈ Φ_{2} := {f_{j} + ε_{h_{1}}, …, f_{j} + ε_{h_{t}}},

è quello — diciamolo g̃_{r} — che si ottiene operando una riduzione completa, a mezzo dei polinomi g_{i}, del polinomio

(x_{r} − a_{r})(x^{f_{j}} − p_{j}).

Resta così provato che F′ = F ∪ {f_{j}} e che G′ := RGB_{⪯}(ℑ(P′)) è l’insieme

{g_{1}, …, g_{j−1}, g_{j+1}, …, g_{s}, g̃_{1}, …, g̃_{r}}.

4 Un algoritmo combinatorio per determinare una base monomiale per K[X]/ℑ(P).

4.1 Nel seguito adotteremo le seguenti convenzioni. Con una notazione del tipo \underline{P} := \underline{\{P_{1}, …, P_{N}, …\}}, denoteremo un insieme ordinato secondo l’ordine in cui gli elementi P_{1}, …, P_{N}, … sono elencati, mentre P := {P_{1}, …, P_{N}, …} indicherà l’insieme sostegno dell’insieme ordinato \underline{P} := \underline{\{P_{1}, …, P_{N}, …\}}. Conseguentemente, se \underline{P} := \underline{\{P_{1}, …, P_{N}, …\}} e \underline{Q} := \underline{\{Q_{1}, …, Q_{N}, …\}}, la notazione \underline{P} = \underline{Q} denoterà, oltre che P = Q, anche che P_{i} = Q_{i} per ogni i. Infine, se \underline{ϕ} è un operatore tra insiemi di insiemi ordinati, denoteremo con ϕ(\underline{P}), o semplicemente con ϕ(P), l’insieme sostegno di \underline{ϕ}(\underline{P}).

In breve: la sottolineatura starà ad indicare che è necessario tener conto dell’ordine, mentre la mancanza di sottolineatura che, trascurando l’ordine, si prendono in considerazione solo gli aspetti insiemistici della questione.

4.2 Nel paragrafo precedente si sono descritti diversi algoritmi di soluzione del Problema 1. In ciascuno di essi la parte che decisamente comporta calcoli più pesanti è quella relativa alla determinazione di una base monomiale per K[X]/I (I = ℑ(P)). Nel presente paragrafo descriveremo un semplice algoritmo puramente combinatorio che consente di risolvere rapidamente tale problema.

Definiamo dapprima un operatore — l’operatore \underline{D} — che consente di associare ad un arbitrario insieme ordinato finito \underline{P} := \underline{\{P_{1}, …, P_{N}\}} di punti dello spazio K^{n} un insieme ordinato, \underline{D}(\underline{P}) := \underline{\{d_{1}, …, d_{N}\}} ⊂ N^{n} di cardinalità #\underline{D}(\underline{P}) = #\underline{P} = N tale che il sottoinsieme \underline{\{d_{1}, …, d_{s}\}} sia, per ogni s ≤ N, l’insieme \underline{D}(\underline{\{P_{1}, …, P_{s}\}}) associato a \underline{\{P_{1}, …, P_{s}\}}. Resterà pertanto determinato anche un isomorfismo di insiemi ordinati

\underline{δ}\underline{P} : \underline{P} ⟶ \underline{D}(\underline{P})
P_{i} ⟼ d_{i}.

(Nel seguito useremo talvolta la notazione \underline{δ}_{P} in luogo di \underline{δ}\underline{P} quando ciò non darà adito a confusione.)

Proveremo quindi che i) in qualità di insieme non ordinato, D(P) non dipende dall’ordine fissato in \underline{P} (Prop. 3), ii) \underline{D}(\underline{P}) è un diagramma di Ferrers (ordinato, n-dimensionale) (Prop. 5), e iii) l’insieme

{x^{d} | d ∈ D(P)}

costituisce una base monomiale per l’algebra quoziente K[X]/ℑ(P) (Prop. 6) che è minimale per l’ordine lessicografico inverso (Prop. 7).

4.3 Indichiamo con π_{s} e π^{s} le proiezioni

π_{s} :  K^{n}  ⟶  K^{s}
(a_{1}, …, a_{n}) ⟼ (a_{1}, …, a_{s})

e

π^{s} :  K^{n}  ⟶  K^{n−s+1}
(a_{1}, …, a_{n}) ⟼ (a_{s}, …, a_{n});

poniamo inoltre

Π_{s}(P, P) := {P_{i} ∈ P|π_{s}(P_{i}) = π_{s}(P)}
Π^{s}(P, P) := {P_{i} ∈ P|π^{s}(P_{i}) = π^{s}(P)}

con P ∈ K^{n} e P ⊆ K^{n}. Riguardando N^{n} come un sottoinsieme di K^{n}, risulta ovvio il significato da attribuire ai simboli π_{s}(d), π^{s}(d), Π_{s}(d, D) e Π^{s}(d, D) qualora d ∈ N^{n} e D ⊆ N^{n}. Queste, ed altre notazioni che introdurremo nel corso di questo paragrafo, vanno peraltro considerate con una certa duttilità che ci consentirà di evitare pignolerie tese ad un inutile rigore; ad esempio non staremo a precisare che cosa debba intendersi per “π_{s} : K^{m} ⟶ K^{s}” qualora m ≠ n. Converremo inoltre tacitamente che l’ordine considerato su sottoinsiemi (o proiezioni di sottoinsiemi) di \underline{P} è quello indotto dall’ordine su \underline{P}.

Se P ∉ P, diremo che s, 1 ≤ s ≤ n, è il σ-valore di P ∈ K^{n} rispetto a P ⊆ K^{n} — in simboli: s = σ(P, P) — se s è il più grande intero tale che Π_{s−1}(P, P) ≠ ∅ (si assume convenzionalmente che sia Π_{0}(P, P) ≠ ∅ per ogni P ed ogni P); poniamo inoltre

Σ(P, P) := {P_{i} ∈ P | π_{s−1}(P_{i}) = π_{s−1}(P) con s = σ(P, P)} (P ∉ P)

( in altri termini: P_{i} ∈ Σ(P, P) sse P e P_{i} hanno esattamente le prime s − 1 coordinate uguali). Queste notazioni vanno estese al caso P ∈ \underline{P} — sia P = P_{j} — nel modo seguente:

σ(P, \underline{P}) := σ(P, \{P_{1}, …, P_{j−1}\}) (P ∈ \underline{P})
Σ(P, \underline{P}) := Σ(P, \{P_{1}, …, P_{j−1}\}) (P ∈ \underline{P}).

4.4 L’operatore \underline{D}.

Ciò premesso, descriviamo — per induzione sulla cardinalità N = #P — l’Algoritmo D che definisce l’operatore \underline{D}.

Algoritmo D.

1) Se N = 1, allora \underline{D}(\underline{P}) := \{(0, …, 0)\}.

2) Se ℵ_{0} > N > 1, facendo uso dell’ipotesi induttiva assumiamo di conoscere l’insieme \underline{D}(\underline{\{P_{1}, …, P_{N−1}\}}) = \underline{\{d_{1}, …, d_{N−1}\}} e indichiamo come determinare l’elemento d_{N} ∈ N^{n} corrispondente all’ultimo punto P_{N} di \underline{P}.

Posto s = σ(P_{N}, \underline{P}), dividiamo le componenti d_{N,i} (i = 1, …, n) dell’elemento d_{N} ∈ N^{n} cercato in tre diversi sottoinsiemi, a seconda che i sia maggiore, uguale o minore di s:

a) Per i > s, poniamo d_{N,i} = 0;

b) al fine di determinare d_{N,s} consideriamo il più grande indice m, 1 ≤ m < N, tale che per il corrispondente punto P_{m} si abbia

π_{s−1}(P_{m}) = π_{s−1}(P_{N}) π^{s+1}(d_{m}) = (0, …, 0) = π^{s+1}(d_{N})

(cioè, posto P_{i} = (a_{i,1}, …, a_{i,n}) e \underline{δ}\underline{P}(P_{i}) = d_{i} = (d_{i,1}, …, d_{i,n}), tale che

a_{m,1} = a_{N,1}, …, a_{m,s−1} = a_{N,s−1} d_{m,s+1} = … = d_{m,n} = 0 )

[questo punto P_{m} verrà detto σ-antecedente di P_{N} rispetto alla coppia di insiemi ordinati \underline{\{P_{1}, …, P_{N−1}\}}, \underline{D}(\underline{\{P_{1}, …, P_{N−1}\}})] e si ponga

d_{N,s} := d_{m,s} + 1;

c) infine, per determinare i valori d_{N,i} per i < s, consideriamo il sottoinsieme

L(P_{N}, \underline{P}) := \underline{\{P_{j_{1}}, …, P_{j_{r}}\}}

di \underline{P}, formato da tutti i punti di \underline{P} cui \underline{δ}\underline{P} fa corrispondere un elemento d ∈ \underline{D}(\underline{P}) tale che π^{s}(d) = (d_{N,s}, 0, …, 0) = π^{s}(d_{N}) [avente cioè d_{N,s}, 0, …, 0 come ultime n − s + 1 componenti]; in particolare: P_{j_{r}} = P_{N}. Poniamo

\underline{Q} := π_{s−1}(L(P_{N}, \underline{P})) ⊆ K^{s−1}

(in altri termini: i punti di \underline{Q} sono i punti di L(P_{N}, \underline{P}) privati delle ultime n − s + 1 coordinate). Va notato che se h < r = #L(P_{N}, \underline{P}) allora π_{s−1}(P_{j_{h}}) ≠ π_{s−1}(P_{N}); più in generale, il carattere induttivo della presente descrizione di \underline{D} assicura che se h < k ≤ r allora π_{s−1}(P_{j_{h}}) ≠ π_{s−1}(P_{j_{k}}); ne consegue che si ha: #\underline{Q} = #L(P_{N}, \underline{P}) = r.

Poiché ovviamente r = #\underline{Q} < N, per l’ipotesi induttiva si conosce l’insieme

\underline{D}(\underline{Q}) = \underline{\{d̃_{1}, …, d̃_{r}\}}

e si ha

d̃_{i} = π_{s−1}(d_{j_{i}}) per ogni 1 ≤ i < r.

Le prime s − 1 componenti di d_{N} vengono allora definite da

π_{s−1}(d_{N}) := d̃_{r}.

3) Se N = ℵ_{0}, sia \underline{P} = \underline{\{P_{1}, …, P_{N}, …\}} e \underline{D}_{N} := \underline{D}(\underline{\{P_{1}, …, P_{N}\}}) e poniamo

\underline{D}(\underline{P}) := ⋃ \underline{D}_{N}.

4.5 Alcune proprietà di \underline{D}(\underline{P}).

Il seguente lemma giustifica alcuni passi nella descrizione precedente dell’Algoritmo D; in particolare dà senso all’applicazione \underline{δ}\underline{P}.

Lemma 1 Siano \underline{P} = \underline{\{P_{1}, …, P_{N}\}} e \underline{D}(\underline{P}) = \underline{\{d_{1}, …, d_{N}\}}. Allora per ogni s ≤ N si ha \underline{D}(\underline{\{P_{1}, …, P_{s}\}}) = \underline{\{d_{1}, …, d_{s}\}}.

Dimostrazione. Ovvia (per la natura induttiva dell’Algoritmo D). □

Proposizione 3 L’insieme sostegno D(P) di \underline{D}(\underline{P}) non dipende dall’ordine fissato in \underline{P}.

Dimostrazione. Ci si convince facilmente che, posto

\underline{P}_{1} := \underline{\{P_{1}, …, P_{N}, P, P′\}}, \underline{P}_{2} := \underline{\{P_{1}, …, P_{N}, P′, P \}},

è sufficiente provare che

D(P_{1}) = D(P_{2}).

Posto:

d = (d_{1}, …, d_{n}) := \underline{δ}_{P_{1}}(P) d′ := (d′_{1}, …, d′_{n}) := \underline{δ}_{P_{1}}(P′)
f = (f_{1}, …, f_{n}) := \underline{δ}_{P_{2}}(P) f′ := (f′_{1}, …, f′_{n}) := \underline{δ}_{P_{2}}(P′)

cioè

\underline{D}_{1} := \underline{D}(\underline{P}_{1}) = \underline{\{d_{1}, …, d_{N}, d, d′\}},
\underline{D}_{2} := \underline{D}(\underline{P}_{2}) = \underline{\{d_{1}, …, d_{N}, f′, f\}},

occorre allora provare che o

(A) d = f′, d′ = f

(nel qual caso \underline{D}_{1} e \underline{D}_{2} coincidono anche in quanto insiemi ordinati) oppure

(B) d = f, d′ = f′.

Indicate con a_{i} e a′_{i} (i = 1, …, n) le coordinate di P e P′ rispettivamente, sia r, 1 < r ≤ n, tale che

d_{r} ≠ d′_{r}, d_{r+1} = d′_{r+1}, …, d_{n} = d′_{n}.

Non è difficile provare che ciò comporta che il valore assunto — nel calcolo di \underline{D}_{1} := \underline{D}(\underline{P}_{1}) — dalla (n−r)-upla (d′_{r+1}, …, d′_{n}) non dipende in alcun modo dal punto P che precede P′ in \underline{P}_{1} e quindi deve coincidere con quello della analoga (n − r)-upla (f′_{r+1}, …, f′_{n}) ottenuta nel calcolo di \underline{D}_{2} := \underline{D}(\underline{P}_{2}):

d′_{r+1} = f′_{r+1}, …, d′_{n} = f′_{n}.

Allo stesso modo si prova che

d_{r+1} = f_{r+1}, …, d_{n} = f_{n}

e quindi si ha

d_{r+1} = d′_{r+1} = f_{r+1} = f′_{r+1}, …, d_{n} = d′_{n} = f_{n} = f′_{n}.

Ne consegue che, ai fini di quanto si vuole dimostrare, non è restrittivo assumere r = n e quindi d_{n} ≠ d′_{n}. In tale ipotesi, è facile verificare che si presenterà il caso (A) o il caso (B) a seconda che si abbia (a_{1}, …, a_{n−1}) = (a′_{1}, …, a′_{n−1}) oppure (a_{1}, …, a_{n−1}) ≠ (a′_{1}, …, a′_{n−1}). □

Lemma 2 Siano P, P′ ⊆ K^{n} e sia P ⊆ P′; allora D(P) ⊆ D(P′).

Dimostrazione. A causa della Prop.3 non è restrittivo supporre — ai fini del calcolo di D(P′) — che i punti appartenenti anche a P precedano, in \underline{P′}, tutti gli altri: \underline{P′} = \underline{\{P_{1}, …, P_{N}, P_{N+1}, …, P_{N′}\}}, con \underline{P} = \underline{\{P_{1}, …, P_{N}\}}. Da ciò e dal Lemma 1 consegue l’assunto. □

Dato un insieme (finito, ordinato) \underline{P} = \underline{\{P_{1}, …, P_{N}\}} ⊆ K^{n}, sia:

\underline{D} := \underline{D}(\underline{P})
h := max\{d_{n} | d = (d_{1}, …, d_{n}) ∈ \underline{D}\}
\underline{D}_{r} := \underline{\{d = (d_{1}, …, d_{n}) ∈ \underline{D} | d_{n} = r\}}
\underline{P}_{r} := \underline{\{P ∈ \underline{P} | \underline{δ}_{P}(P) ∈ \underline{D}_{r}\}}.

Si ha il

Lemma 3 Valgono le relazioni:

r > r′ ⟹ π_{n−1}(\underline{P}_{r}) ⊆ π_{n−1}(\underline{P}_{r′})  (8)
\underline{D}(π_{n−1}(\underline{P}_{r})) = π_{n−1}(\underline{D}_{r}).  (9)

Dimostrazione. Per analisi diretta dell’Algoritmo D. □

Diremo che i = (i_{1}, …, i_{n}) ∈ N^{n} precede j = (j_{1}, …, j_{n}) ∈ N^{n} nell’ordine lessicografico inverso, in simboli i ≺_{i.l.} j, se la prima non nulla delle differenze j_{n} − i_{n}, …, j_{1} − i_{1} è positiva.

Lemma 4 Sia \underline{P} = \underline{\{P_{1}, …, P_{N}\}}, \underline{D}(\underline{P}) = \underline{\{d_{1}, …, d_{N}\}}, d_{i} = \underline{δ}\underline{P}(P_{i}); supponiamo che d_{s+1} = \underline{δ}\underline{P}(P_{s+1}) ≺_{i.l.} d_{s} = \underline{δ}\underline{P}(P_{s}).

Posto allora

\underline{P′} = \underline{\{P_{1}, …, P_{s+1}, P_{s}, …, P_{N}\}},

si ha

\underline{D}(\underline{P′}) = \underline{\{d_{1}, …, d_{s+1}, d_{s}, …, d_{N}\}}.

Dimostrazione. (Traccia). Si ponga P_{s} = (a_{1}, …, a_{n}), P_{s+1} = (b_{1}, …, b_{n}); d_{s} = (j_{1}, …, j_{m}, 0, …, 0), d_{s+1} = (i_{1}, …, i_{r}, 0, …, 0) con r ≤ m ≤ n e si distinguano i due casi r < m e r = m osservando che in entrambi deve accadere che (a_{1}, …, a_{m−1}) ≠ (b_{1}, …, b_{m−1}) (pur senza poter escludere che nel primo si abbia (a_{1}, …, a_{r−1}) ≠ (b_{1}, …, b_{r−1})) e ragionando per induzione sul numero n ≥ 2 delle coordinate (per n = 1 le ipotesi del Lemma sono assurde) qualora r = m e i_{r} = j_{r}. □

Proposizione 4 Dato un insieme finito P ⊆ K^{n}, è sempre possibile ordinarlo, \underline{P} = \underline{\{P_{1}, …, P_{N}\}}, in modo tale che \underline{D}(\underline{P}) = \underline{\{d_{1}, …, d_{N}\}} (d_{i} = \underline{δ}\underline{P}(P_{i})) sia ordinato secondo l’ordine lessicografico inverso:

s < t ⟹ d_{s} = \underline{δ}\underline{P}(P_{s}) ≺_{i.l.} d_{t} = \underline{δ}\underline{P}(P_{t}).

Dimostrazione. È una conseguenza diretta della Prop. 3 e del Lemma 4.

□

4.6 Ulteriori proprietà di D(P).

Si consideri l’insieme N^{n} con l’ordine (parziale) prodotto indotto dall’ordine naturale su N:

(i_{1}, …, i_{n}) < (j_{1}, …, j_{n})

se e solo se

(i_{1}, …, i_{n}) ≠ (j_{1}, …, j_{n}) e (∀s)(i_{s} ≤ j_{s}).

Un sottoinsieme F ⊆ N^{n} verrà detto diagramma di Ferrers n-dimensionale (standard) se:

1) 0 := (0, …, 0) ∈ F;

2) se i ∈ F allora [0, i] := {j ∈ N^{n} | 0 ≤ j ≤ i} ⊆ F. Diremo invece che F ⊆ N^{n} è un diagramma di Ferrers n-dimensionale generalizzato se

i, h ∈ F ⇒ [i, h] := {j ∈ N^{n} | i ≤ j ≤ h} ⊆ F.

È immediato provare che:

Lemma 5 i) Se F ⊆ N^{n} è tale che, per ogni 1 ≤ j ≤ n, si ha

(i_{1}, …, i_{n}) ∈ F ⟹ (i_{1}, …, i_{j} − 1, …, i_{n}) ∈ F

allora F è un diagramma di Ferrers. ii) Sia F un diagramma di Ferrers n-dimensionale (standard). Considerato il sottoinsieme {r_{1}, …, r_{m}} ⊆ {1, …, n} e la proiezione

ψ :  N^{n}  ⟶  N^{m}
(i_{1}, …, i_{n}) ⟼ (i_{r_{1}}, …, i_{r_{m}}),

allora ψ(F) è un diagramma di Ferrers m-dimensionale (standard). □

Sia F ⊆ N^{n} un diagramma di Ferrers. Un elemento j ∈ N^{n} verrà detto diedrale esterno per F se

a) {i ∈ N^{n} | i < j} ⊆ F
b) {i ∈ N^{n} | j ≤ i} ∩ F = ∅

(equivalentemente se a) e c) j ∉ F); verrà invece detto diedrale interno se

a′) {i ∈ N^{n} | i ≤ j} ⊆ F
b′) {i ∈ N^{n} | j > i} ∩ F = ∅

(equivalentemente se b’) e c’) j ∈ F). Possiamo definire un diedrale esterno anche nel modo seguente: j ∈ N^{n} è diedrale esterno se j ∉ F e se (j_{1}, …, j_{i} − 1, j_{i+1}, …, j_{n}) ∈ F per ogni i per cui j_{i} − 1 è non negativo.

Un elemento diedrale f = (f_{1}, …, f_{n}) di F sarà detto essere di livello l (1 ≤ l ≤ n) se f_{l} ≠ 0, f_{l+1} = … = f_{n} = 0.

È immediato riconoscere che un diagramma di Ferrers n-dimensionale non vuoto ha almeno un elemento diedrale interno ed almeno n elementi diedrali esterni e che l’insieme degli uni o degli altri caratterizza F. Indicando con f_{1}, …, f_{s} (rispettivamente _{1}f, …, _{t}f) gli elementi diedrali esterni (risp. interni) di F, esprimeremo questo fatto con la notazione

F =  > f_{1}, …, f_{s} <  =  < _{1}f, …, _{t}f > .

Dati due diagrammi di Ferrers F ⊂ F′ tali che F′ − F = {f} (differenza insiemistica), allora f è un elemento diedrale esterno per F (rispett. diedrale interno per F′). Ne consegue che un diagramma di Ferrers può accrescersi (di un elemento alla volta) solo tramite aggiunta di elementi diedrali esterni.

Consideriamo: \underline{P} := \underline{\{P_{1}, …, P_{N}\}}, \underline{P′} := \underline{\{P_{1}, …, P_{N}, P_{N+1}\}}, \underline{D}(\underline{P}) := \underline{\{d_{1}, …, d_{N}\}} e \underline{D}(\underline{P′}) := \underline{\{d_{1}, …, d_{N}, d_{N+1}\}}; è facile provare che se \underline{D}(\underline{P}) è un diagramma di Ferrers allora d_{N+1} è un suo elemento diedrale esterno. Se ne deduce, ragionando per induzione sulla cardinalità di P, che vale la

Proposizione 5 L’insieme D(P) è un diagramma di Ferrers. □

Proposizione 6 Sia D := D(P); allora {[x^{d}]_{ℑ(P)} | d ∈ D} costituisce una base monomiale per K[X]/ℑ(P).

Dimostrazione. Ragioniamo per induzione sulla dimensione n di K^{n}. Per n = 1 si ha P = {ρ_{1}, …, ρ_{N}} e ℑ(P) = (g) con

g = ∏_{i=1}^{N}(x − ρ_{i}).

Applicando l’Algoritmo D a P si ottiene D(P) = {0, 1, …, N − 1}; pertanto {[x^{d}]_{ℑ(P)} | d ∈ D} = {[1], [x], …, [x^{N−1}]}, che è, banalmente, una base monomiale per K[X]/ℑ(P).

Supponiamo ora che la Proposizione sia vera per ogni sottoinsieme finito di K^{n′}, con n′ < n, e dimostriamola per l’insieme P = {P_{1}, …, P_{N}} ⊆ K^{n}. Poiché dim(K[X]/ℑ(P)) = N = #D(P), è sufficiente provare che le classi di equivalenza, modulo ℑ(P), dei monomi associati agli elementi di D(P) sono linearmente indipendenti in K[X]/ℑ(P), cioè che, dato un polinomio p(x_{1}, …, x_{n}) della forma

p(x_{1}, …, x_{n}) = ∑_{d∈D(P)} α_{d} · x^{d} ,

se p(x_{1}, …, x_{n}) ∈ ℑ(P) allora p(x_{1}, …, x_{n}) è identicamente nullo.

Supposto pertanto p(x_{1}, …, x_{n}) ∈ ℑ(P), poniamo

p(x_{1}, …, x_{n}) = ∑_{r=0}^{h} p_{r}(x_{1}, …, x_{n−1}) · x_{n}^{r}

con

p_{r}(x_{1}, …, x_{n−1}) := ∑_{(d_{1},...,d_{n−1})∈π_{n−1}(D_{r})} α_{(d_{1},...,d_{n−1},r)} · x_{1}^{d_{1}} ⋯ x_{n−1}^{d_{n−1}}. (10)

Il polinomio p(x_{1}, …, x_{n}) deve annullarsi per ogni punto P = (a_{1}, …, a_{n}) ∈ P; se, in particolare, P ∈ P_{h}, ciò comporta che

p_{h}(a_{1}, …, a_{n−1}) = 0 con (a_{1}, …, a_{n−1}) ∈ π_{n−1}(P_{h})

(giacché il polinomio p(a_{1}, …, a_{n−1}, x_{n}) — dovendo ammettere h + 1 radici [si tenga presente che per ogni P ∈ P_{h} esistono in P altri h punti aventi le stesse prime n−1 coordinate di P] — deve essere identicamente nullo). Avendo presente la (9) e la (10), da quest’ultima si trae — per l’ipotesi induttiva — che il polinomio p_{h}(x_{1}, …, x_{n−1}) deve annullarsi identicamente.

Iterando, per r = h − 1, h − 2, …, 0, il ragionamento appena fatto per r = h — e sfruttando la (8) — si perviene a concludere che, per ogni 0 ≤ r ≤ h, il polinomio p_{r}(x_{1}, …, x_{n−1}) è identicamente nullo e quindi tale è anche p(x_{1}, …, x_{n}). □

Proposizione 7 La base monomiale {[x^{d}]_{ℑ(P)} | d ∈ D(P)} di K[X]/ℑ(P) è minimale rispetto all’ordine lessicografico inverso ≺_{i.l.}.

Dimostrazione. A causa della Prop. 4, possiamo supporre di aver ordinato l’insieme \underline{P} := \underline{\{P_{1}, …, P_{N}\}} in modo tale che per \underline{D} := \underline{D}(\underline{P}) := \underline{\{d_{1}, …, d_{N}\}}, con d_{i} := \underline{δ}\underline{P}(P_{i}), si abbia d_{i} ≺_{i.l.} d_{i+1} (i = 1, …, N − 1). Nel corso della presente dimostrazione, tale ipotesi verrà sfruttata ripetutamente, e talvolta tacitamente.

Sia C := C(P) ⊆ N^{n} tale che {[x^{i}]_{ℑ(P)} | i ∈ C(P)} costituisca una base monomiale di K[X]/ℑ(P) minimale rispetto all’ordine lessicografico inverso ≺_{i.l.}. Dobbiamo provare che C := C(P) = D := D(P).

Ragioniamo per induzione sulla cardinalità #P = #C = #D = codimℑ(P). L’enunciato è ovvio per #P = 1; proviamolo per #P = N supposto che valga per #P < N.

Supponiamo per assurdo che l’assunto sia falso e indichiamo con f = (f_{1}, … …, f_{s}, 0, …, 0) (con 1 ≤ s ≤ n e f_{s} ≠ 0) il più piccolo ( rispetto a ≺_{i.l.}) tra gli elementi di D ∪ C − D ∩ C. Allora o f ∈ C, f ∉ D, oppure f ∈ D, f ∉ C. Escludiamo, in primo luogo, la seconda di tali eventualità. La relazione f ∉ C comporta che si abbia

x^{f} ≡ ∑_{d∈C,d≺_{i.l.}f} α_{d} · x^{d} mod.ℑ(P)

per opportuni coefficienti α_{d} ∈ K non tutti nulli (la restrizione “d ≺_{i.l.} f” è da imputare alla minimalità di C rispetto a ⪯_{i.l.}); ma, per definizione di f, ogni indice d ∈ C per cui d ≺_{i.l.} f appartiene anche a D e quindi si ha

x^{f} ≡ ∑_{d∈D,d≺_{i.l.}f} α_{d} · x^{d} mod.ℑ(P)

in contraddizione con f ∈ D.

Resta da analizzare il caso in cui f ∈ C e f ∉ D. Iniziamo col provare che non è restrittivo supporre che ogni elemento d = (d_{1}, …, d_{n}) ∈ D sia tale che (a) d_{s+1} = … = d_{n} = 0. Indichiamo infatti con \underline{D̂} il sottoinsieme di \underline{D} formato con gli elementi soddisfacenti alla (a); per l’ipotesi fatta all’inizio di questa dimostrazione, \underline{D̂} risulta essere un segmento iniziale dell’insieme ordinato \underline{D} = \underline{\{d_{1}, …, d_{N}\}}: \underline{D̂} = \underline{\{d_{1}, …, d_{t}\}}. Posto \underline{P̂} = \underline{\{P_{1}, …, P_{t}\}}, si ha \underline{D̂} = \underline{D}(\underline{P̂}); ovviamente f ∉ D̂. Osserviamo che, per ogni punto P ∈ \underline{P} − \underline{P̂} esiste qualche punto in \underline{P̂} che ha le stesse prime s coordinate di P. Ciò premesso, notiamo che la relazione f ∈ C comporta che ogni polinomio della forma

x^{f} − ∑_{d≺_{i.l.}f} α_{d} · x^{d}

(e quindi nelle sole variabili x_{1}, …, x_{s}) \underline{non} viene annullato da almeno uno dei punti in \underline{P} e quindi — per l’osservazione fatta più sopra — da almeno uno dei punti in \underline{P̂}. Ne consegue che f ∈ Ĉ := C(\underline{P̂}) e siamo così ricondotti — considerando \underline{P̂} in luogo di \underline{P} — al caso in cui la (a) è soddisfatta. Supponiamo pertanto che siano nulle le ultime n − s componenti di ogni elemento di D.

Ciò premesso, osserviamo che f è necessariamente un elemento diedrale esterno per D e, per la Prop. 6, esiste in ℑ(P) uno ed un solo polinomio della forma

x^{f} − ∑_{d∈D} α_{d} · x^{d} (α_{d} ∈ K)  (11)

che, per quanto appena visto, non è restrittivo supporre nelle sole variabili x_{1}, …, x_{s}. Va provato che in (11) si annullano i coefficienti α_{d} tali che d ≻_{i.l.} f, ottenendo così

x^{f} ≡ ∑_{d∈D, d≺_{i.l.}f} α_{d} · x^{d} (mod.ℑ(P))  (12)

che è in contraddizione con f ∈ C giacché nelle attuali ipotesi ogni elemento d ∈ D, d ≺_{i.l.} f appartiene anche a C.

Proviamo dapprima che il polinomio (11) è di grado f_{s} in x_{s}. Supposto per assurdo che sia di grado d_{s} > f_{s} in x_{s}, scriviamolo nella forma

x^{f} − p(x_{1}, …, x_{s−1}) · x_{s}^{d_{s}} − q(x_{1}, …, x_{s})

con q(x_{1}, …, x_{s}) di grado minore di d_{s} in x_{s}. Per provare che p(x_{1}, …, x_{s−1}) è identicamente nullo, consideriamo l’insieme \underline{D̆} ⊆ \underline{D} formato da tutti gli elementi d ∈ \underline{D} la cui s-esima componente è d_{s} e sia \underline{P̆} := \underline{δ}−1 ; \underline{P}(\underline{D̆}). Per ogni punto P ∈ \underline{P̆} esistono in \underline{P} altri d_{s} punti aventi le stesse prime s − 1 coordinate di P, per cui (in particolare) p(x_{1}, …, x_{s−1}) deve annullarsi nei punti di \underline{P̆} e quindi di \underline{Q̆} := π_{s−1}(\underline{P̆}); cioè, p(x_{1}, …, x_{s−1}) ∈ ℑ(Q̆). D’altra parte, i termini x^{i} = x_{1}^{i_{1}} ⋯ x_{s−1}^{i_{s−1}} in p(x_{1}, …, x_{s−1}) sono solo quelli per cui i ∈ π_{s−1}(\underline{D̆}) = \underline{D}(\underline{Q̆}), cioè costituiscono un sistema di rappresentanti per una base monomiale per K[x_{1}, …, x_{s−1}]/ℑ(Q̆). Ne consegue che p(x_{1}, …, x_{s−1}) è identicamente nullo.

Resta così provato che il polinomio (nelle sole variabili x_{1}, …, x_{s}) (11) è di grado f_{s} in x_{s}. Scriviamolo ora nelle due forme seguenti

x^{f} − ∑_{d∈D_{1}} α_{d} · x^{d} − ∑_{d∈D_{2}} α_{d} · x^{d} − ∑_{d∈D_{3}} α_{d} · x^{d}  (13)

dove

D_{1} := {d ∈ D | d ≻_{i.l.} f, d_{s} = f_{s}}, D_{2} := {d ∈ D | d ≺_{i.l.} f, d_{s} = f_{s}},

D_{3} := {d ∈ D | d_{s} < f_{s}},

e

p_{f_{s}}(x_{1}, …, x_{s−1})·x_{s}^{f_{s}} +p_{f_{s}−1}(x_{1}, …, x_{s−1})·x_{s}^{f_{s}−1} +⋯+p_{0}(x_{1}, …, x_{s−1}). (14)

Osservato che, in (13), tutti e soli i termini di grado f_{s} in x_{s} sono concentrati nei primi tre addendi, deve aversi

p_{f_{s}}(x_{1}, …, x_{s−1}) := x_{1}^{f_{1}} ⋯ x_{s−1}^{f_{s−1}} − p_{(1)} − p_{(2)}  (15)

con

p_{(1)} · x_{s}^{f_{s}} = ∑_{d∈D_{1}} α_{d} · x^{d} e p_{(2)} · x_{s}^{f_{s}} = ∑_{d∈D_{2}} α_{d} · x^{d}.  (16)

Per provare il nostro assunto occorre dimostrare che il secondo addendo in (13) è identicamente nullo o, equivalentemente, che tale è p_{(1)}. A tal fine, poniamo P̃ := \underline{δ}−1 ; \underline{P}(D_{1} ∪ D_{2}). Il polinomio (14) deve annullarsi su tutti i punti di P̃ ⊆ P; osservato che per ogni punto in P̃ se ne trovano in P altri f_{s} aventi le stesse prime s − 1 coordinate di quello, il fatto che il polinomio (14) è di grado f_{s} in x_{s} comporta che i polinomi p_{f_{s}}(x_{1}, …, x_{s−1}), …, p_{0}(x_{1}, …, x_{s−1}) devono annullarsi nei punti di P̃, e quindi anche nei punti dell’insieme Q̃ := π_{s−1}(P̃) ⊆ K^{s−1}. In particolare, il polinomio (15) deve appartenere all’ideale ℑ(Q̃) di K[x_{1}, …, x_{s−1}]:

p_{f_{s}}(x_{1}, …, x_{s−1}) := x_{1}^{f_{1}} ⋯ x_{s−1}^{f_{s−1}} − p_{(1)} − p_{(2)} ≡ 0 (mod.ℑ(Q̃)).  (17)

Poiché #Q̃ < #P, per l’ipotesi induttiva la proposizione vale per l’insieme Q̃ ⊆ K^{s−1}; pertanto, osservato che f̃ := (f_{1}, …, f_{s−1}) = π_{s−1}(f) è un elemento diedrale esterno per D(Q̃) = π_{s−1}(D_{1} ∪ D_{2}), deve aversi

x_{1}^{f_{1}} ⋯ x_{s−1}^{f_{s−1}} ≡ ∑_{d̃:=(d_{1},...,d_{s−1})∈D(Q̃),d̃≺_{i.l.}f̃} βd̃ · x_{1}^{d_{1}} ⋯ x_{s−1}^{d_{s−1}} (mod.ℑ(Q̃)).

dove i coefficienti βd̃ sono univocamente determinati. Dal confronto di quest’ultima con (16) e (17) si deduce facilmente che p_{(1)} è identicamente nullo, che è quanto restava da provare. □

5 Algoritmi derivati.

5.1 In questo paragrafo illustriamo una proprietà (Prop. 8) che — in molti casi — costituisce una sensibile semplificazione dell’Algoritmo D.

Posto infatti P ⊆ K^{n} e Q := π_{n−1}(P) ⊆ K^{n−1}, tale proprietà riconduce il calcolo del diagramma di Ferrers (non ordinato) D(P) a quello del diagramma di Ferrers (ordinato!) \underline{D}(\underline{Q}), avendo preventivamente ordinato \underline{Q} := \underline{\{Q_{1}, …, Q_{m}\}}

in modo tale che, posto h_{i} := # π^{−1}_{n−1} (Q_{i}) (cioè, h_{i} è il numero dei punti in P aventi le prime n−1 coordinate uguali a quelle di Q_{i}), si abbia i < j → h_{i} ≥ h_{j}.

Va subito notato che — proprio a causa del ruolo che gioca in questo contesto l’ordine considerato in \underline{D}(\underline{Q}) — non ha senso iterare l’uso di questa proprietà. Tuttavia nel caso bidimensionale essa fornisce anche una versione alternativa dell’ Algoritmo D (Prop. 9).

Proposizione 8 Con riferimento alle notazioni introdotte più sopra e posto inoltre

\underline{D}(\underline{Q}) := \underline{\{d̃_{1}, …, d̃_{m}\}} ⊆ N^{n−1}

e

d̃_{i} = (d̃_{i,1}, …, d̃_{i,n−1}) = \underline{δ}_{Q}(Q_{i}) (1 ≤ i ≤ m)

si ha

D(P) = {(d̃_{i,1}, …, d̃_{i,n−1}, e_{i})|1 ≤ i ≤ m e 0 ≤ e_{i} < h_{i}}.

Dimostrazione La dimostrazione si riduce ad applicare l’Alg.D dopo aver dotato P di un ordine opportuno.

Operiamo una partizione di P distribuendone gli elementi in una famiglia ordinata di h_{1} blocchi B_{0}, B_{1}, …, B_{h_{1}−1} nel modo seguente: scelti successivamente a caso gli elementi di P, l’elemento P via via considerato verrà messo nel primo dei blocchi che non contiene alcun elemento P′ tale che π_{n−1}(P) = π_{n−1}(P′). È chiaro che un elemento Q_{i} apparterrà a π_{n−1}(B_{s}) se e solo se s < h_{i}, per cui si ha

π_{n−1}(B_{0}) = π_{n−1}(P) = {Q_{1}, …, Q_{m}}

e

π_{n−1}(B_{0}) ⊇ π_{n−1}(B_{1}) ⊇ … ⊇ π_{n−1}(B_{h}) con h := h_{1} − 1.

Ordiniamo ciascuno degli insiemi π_{n−1}(B_{s}) ⊆ Q secondo l’ordine indotto da \underline{Q}; ciò determina un ordine anche in ciascuno dei blocchi B_{s}:

\underline{B}_{s} = \underline{\{P_{1}^{s}, …, P_{m_{s}}^{s}\}} con π_{n−1}(P_{t}^{s}) = Q_{t}.

Infine introduciamo un ordine \underline{P} in P semplicemente incollando ordinatamente i diversi blocchi ordinati \underline{B}_{0}, \underline{B}_{1}, …,\underline{B}_{h}: dati due punti P, P′ ∈ \underline{P}, P precederà P′ se, posto P = P_{r_{i}}^{i} e P′ = P_{r_{j}}^{j} si ha o i < j oppure i = j e r_{i} < r_{j}.

È sufficiente ora applicare a \underline{P} ordinato in questo modo l’operatore \underline{D} per ottenere il risultato enunciato. □

Come diretta conseguenza della proposizione precedente si ottiene la:

Proposizione 9 Sia P ⊆ K^{2}. Se i punti in P hanno, complessivamente, m ascisse diverse ρ_{1}, …, ρ_{m} e ve ne sono h_{i} di ascissa ρ_{i}:

P := {(ρ_{1}, σ_{1,1}), … (ρ_{1}, σ_{1,h_{1}}), …, (ρ_{m}, σ_{m,1}), …, (ρ_{m}, σ_{m,h_{m}})},

allora — assumendo che h_{1} ≥ … ≥ h_{m} — il diagramma di Ferrers M_{P} dei monomi associati a D(P) è quello rappresentato nella tavola

1  x  …  x^{m−2}  x^{m−1}
y  xy  …  x^{m−2}y  x^{m−1}y
⋮  ⋮  ⋯  ⋮  ⋮
y^{h_{m}−1} xy^{h_{m}−1} … x^{m−2}y^{h_{m}−1} x^{m−1}y^{h_{m}−1}
y^{h_{m}}  xy^{h_{m}} … x^{m−2}y^{h_{m}}
⋮  ⋮  ⋯  ⋮

⋮  ⋮
y^{h_{2}−1} xy^{h_{2}−1}
y^{h_{2}}
⋮
y^{h_{1}−1}
□

6 Generalizzazione al caso dei punti multipli.

6.1 Corretta impostazione del Problema 2. Nel corso del presente paragrafo generalizzeremo — seguendone la falsariga — quanto esposto nei paragrafi precedenti, al fine di precisare prima e poi di risolvere il Problema 2.

Iniziamo con l’introdurre alcune nozioni — in particolare quelle di diagramma algebrico e di multiinsieme algebrico — che svolgeranno un ruolo centrale in quanto segue.

Consideriamo l’applicazione lineare

D_{i} : K[X] ⟶ K[X]
x^{h} ⟼ \binom{h}{i}x^{h−i}

e la sua composizione v_{P}^{i} = v_{P} ∘ D_{i} con l’operatore di valutazione v_{P}:

v_{P}^{i} : K[X] ⟶ K
q ⟼ (D_{i}q)(P).

Osserviamo che se K è un campo di caratteristica zero allora

D_{i} = \frac{1}{i!}D^{i} = \frac{1}{i!} \frac{∂^{i_{1}+···+i_{n}}}{∂x_{1}^{i_{1}} ⋯ ∂x_{n}^{i_{n}}}

dove i = (i_{1}, …, i_{n}) e i! = i_{1}! ⋯ i_{n}!.

Sia J un ideale di K[x_{1}, …, x_{n}] e sia P ∈ V(J). Consideriamo l’insieme

F(P) := {i ∈ N^{n}| (∀p ∈ J) (v_{P}^{i} (p) = 0)}

Utilizziamo la nota formula:

D_{i}(f · g) = ∑_{h+k=i} D_{h}(f) · D_{k}(g)  (18)

per dimostrare la seguente

Proposizione 10 a) F(P) è un diagramma di Ferrers; b) se (g_{1}, …, g_{s}) è un sistema di generatori per J allora F(P) è il più grande diagramma di Ferrers contenuto nell’insieme

{i ∈ N^{n}| v_{P}^{i} (g_{j}) = 0 per ogni 1 ≤ j ≤ s} .

Dimostrazione.

a) Sia i ∈ F(P); per la prima parte del Lemma 5 è sufficiente dimostrare che i′ := (i_{1}, …, i_{j} −1, …, i_{n}) appartiene a F(P). Supponiamo per assurdo che i′ ∉ F(P); allora per qualche polinomio q ∈ J deve aversi

v_{P}^{i′} (q) ≠ 0.  (19)

Consideriamo il polinomio x_{j} · q ∈ J; poiché i ∈ F(P) si ha:

0 = v_{P}^{i} (x_{j} · q) = (D_{i}(x_{j} · q))(P) = ( ∑_{h+k=i} D_{h}x_{j} · D_{k}q) (P) =
= (x_{j}D_{i}q + D_{i′}q)(P) = (D_{i′}q)(P)

in contrasto con la (19).

b) La seconda parte dell’enunciato è una diretta conseguenza della prima parte e della (18). □

Il diagramma di Ferrers F(P) verrà detto il diagramma algebrico di P in V(J) (o relativamente all’ideale J).

Un insieme finito ℘ := {(P_{1}, F_{1}), …, (P_{N}, F_{N})} di coppie (P_{j}, F_{j}), costituite da un punto P_{j} di K^{n} (con i ≠ j ⇒ P_{i} ≠ P_{j}) e da un diagramma di Ferrers F_{j} di N^{n}, verrà detto essere un multiinsieme algebrico n-dimensionale sul campo K. Gli elementi P_{j} verranno detti punti del multiinsieme algebrico ℘ — e scriveremo P_{j} ∈ ℘ — e il diagramma di Ferrers F_{j} si dirà il diagramma algebrico di P_{j} nel multiinsieme algebrico ℘. Diremo inoltre che P_{j} è semplice se F_{j} = {(0, …, 0)}. Talvolta, nel seguito, identificheremo tacitamente il multiinsieme algebrico ℘ con il sottoinsieme di K^{n} × N^{n} costituito da tutte le coppie della forma (P, i) con P ∈ ℘ e i elemento del diagramma algebrico F di P. In accordo con ciò, useremo anche la notazione (P, i) ∈ ℘ per denotare tale situazione e chiameremo cardinalità #℘ del multinsieme algebrico ℘ l’intero #℘ := ∑_{j=1}^{N} #F_{j}. Inoltre, dati due multiinsiemi algebrici ℘ e ℘′, la relazione (P, i) ∈ ℘ ⇒ (P, i) ∈ ℘′ verrà espressa con la notazione ℘ ⊆ ℘′. Diremo che ℘ := {(P_{1}, F_{1}), …, (P_{N}, F_{N})} è il multiinsieme algebrico dell’ideale cofinito J — e scriveremo ℘ = ℘(J) — se V (J) = {P_{1}, …, P_{N}} e se F_{j} è il diagramma algebrico di P_{j} relativamente all’ideale J.

Consideriamo ora l’insieme

ℑ(℘) := {p ∈ K[X] | (∀j)(∀i ∈ F_{j}) (v_{P_{j}}^{i}(p) = 0)} .

Sfruttando ancora una volta la (18) e il fatto che F_{j} è un diagramma di Ferrers si prova che ℑ(℘) è un ideale di K[x_{1}, …, x_{n}], che diremo essere l’ideale del multiinsieme algebrico ℘. Ovviamente il diagramma algebrico F_{j} di P_{j} in ℘ coincide con il diagramma algebrico di P_{j} relativamente all’ideale ℑ(℘). Si può dimostrare (cfr. [2]) che si ha

codim ℑ(℘) = #℘.

Siamo ora in grado di precisare il:

Problema 2. Dato un multiinsieme algebrico ℘ := {(P_{1}, F_{1}), …, (P_{N}, F_{N})} si vuole determinare un polinomio p ∈ K[x_{1}, …, x_{n}] tale che, per ogni 1 ≤ j ≤ n ed ogni i ∈ F_{j}, si abbia

v_{P_{j}}^{i}(p) = α_{i;j}

dove le α_{i;j} sono dei valori assegnati in K.

Facendo considerazioni analoghe a quelle del paragrafo 1, si vede che — così riformulato — il Problema 2 ammette una soluzione — determinata univocamente modulo ℑ(℘) — e quindi che, per ogni base monomiale {x^{i_{j}}| 1 ≤ j ≤ #℘} di K[X]/ℑ(℘), esiste uno ed un solo polinomio p = ∑ p_{j}x^{i_{j}} soddisfacente alle condizioni richieste.

6.2 Soluzione del Problema 2. Vediamo ora — generalizzando al caso attuale quanto, nei paragrafi 2 e 3, si è già fatto per gli insiemi algebrici — come possa essere determinata una base monomiale minimale {x^{i_{j}}| 1 ≤ j ≤ #℘} di K[X]/ℑ(℘) e quindi un polinomio p = ∑ p_{j}x^{i_{j}}.

Associamo dapprima al multiinsieme algebrico ℘ un ideale elementare Γ = (γ_{1}(x_{1}), …, γ_{n}(x_{n})) di generatori

γ_{i}(x_{i}) := ∏_{j=1}^{t_{i}}(x_{i} − ρ_{i,j})^{h_{i,j}}

dove si è indicato con {ρ_{i,1}, …, ρ_{i,t_{i}}} l’insieme delle i–esime coordinate dei punti di ℘ e le molteplicità h_{i,j} sono state determinate nel modo seguente. Indichiamo con P_{s_{1}}, …, P_{s_{m}} i punti di ℘ aventi ρ_{i,j} come i-esima coordinata e, per ogni r ∈ {1, …, m}, sia f_{s_{r}} = (f_{s_{r},1}, …, f_{s_{r},n}) l’estremo superiore del diagramma algebrico F_{s_{r}} ⊆ N^{n} di P_{s_{r}}; allora h_{i,j} è definito come il sup{f_{s_{r},i}|1 ≤ r ≤ m}.

Poniamo inoltre h_{i} := ∑_{j=1}^{t_{i}} h_{i,j} = deg(γ_{i}), h := h_{1} ⋯ h_{n} e h := (h_{1} − 1, …, h_{n} − 1). È immediato verificare che l’insieme

H := {x^{s}| s ≤ h}

costituisce un sistema di rappresentanti per una base monomiale (minimale rispetto ad un qualunque ordine lineare compatibile ⪯) per K[X]/Γ.

All’ideale elementare Γ così definito associamo un multiinsieme algebrico ℘_{Γ} nel nodo seguente: la coppia (P, F) è un elemento di ℘_{Γ} sse, posto P = (σ_{1}, …, σ_{n}), si ha γ_{i}(σ_{i}) = 0 ed inoltre, indicata con s_{i} la molteplicità di σ_{i} in γ_{i}, si ha

F = {i ∈ N^{n} | i ≤ (s_{1} − 1, … s_{n} − 1)}.

È facile verificare (cfr. [2]) che si ha: ℘ ⊆ ℘_{Γ}, ℘_{Γ} = ℘(Γ) e #℘_{Γ} = codim(Γ). Generalizzando quanto contenuto in 2.2, dato un insieme ordinato di monomi

T_{≺} := (t_{0}, t_{1}, …, t_{s}, …),

ed una coppia (P, i), P ∈ K^{n} e i ∈ N^{n}, poniamo

T_{≺}(P, i) := (v_{P}^{i} (t_{0}), …, v_{P}^{i} (t_{s}), …).

Fissato un arbitrario multiinsieme algebrico ℜ ed avendone ordinato linearmente gli elementi (P, i), sia T_{≺}(ℜ) la matrice di tipo #ℜ × #T_{≺} la cui (P, i)-esima riga è T_{≺}(P, i).

Considerato di nuovo il multiinsieme algebrico ℘ e quello ℘_{Γ} associato a Γ, assumiamo di aver ordinato gli elementi (P, i) di ℘_{Γ} in modo tale che quelli appartenenti anche a ℘ precedano gli altri e consideriamo le matrici H̃ := H_{≺}(℘_{Γ}) e H_{≺}(℘) (la seconda essendo formata con le prime #℘ righe della prima). Ancora si può dimostrare che H̃ è non degenere (esattamente come per la Prop. 1, non appena si riconosca che H̃ è il prodotto tensoriale di n matrici di Vandermonde generalizzate, ciascuna associata alle radici di uno dei generatori γ_{i}(x_{i}) di Γ) e si può, in ultima analisi, ripetere quanto ottenuto, nei paragrafi 2 e 3, per gli insiemi algebrici {P_{1}, …, P_{n}}.

Nel paragrafo seguente, infine, mostreremo come generalizzare al caso dei multiinsiemi algebrici l’operatore D, ottenendo tramite esso una base monomiale minimale per l’algebra quoziente K[X]/ℑ(℘).

6.3 Diagramma di Ferrers associato ad un multiinsieme algebrico. Consideriamo la bigezione (“rappresentazione umbrale”)

u : K^{n} × N^{n}  ⟶  (K × N)^{n}
((a_{1}, …, a_{n}), (i_{1}, …, i_{n})) ⟼ ((a_{1}, i_{1}), …, (a_{n}, i_{n}));

chiameremo “valutazione umbrale” l’applicazione inversa U := u^{−1}.

Dato il multiinsieme algebrico ℘ := {(P_{1}, F_{1}), …, (P_{N}, F_{N})} ad ogni coppia (P, i) ∈ ℘ associamo la sua rappresentazione umbrale u(P, i) e chiamiamo rappresentazione umbrale R(℘) di ℘ l’insieme

R = R(℘) := {u(P, i) | (P, i) ∈ ℘}.

Estendiamo l’operatore D ai multiinsiemi algebrici definendo il diagramma di Ferrers D(℘) come il diagramma di Ferrers associato all’insieme R dall’Algoritmo D:

D(℘) := D(R).

Vale la seguente

Proposizione 11 L’insieme B := {[x^{i}]_{ℑ(℘)} | i ∈ D(℘)} costituisce una base lineare monomiale (minimale) per l’algebra quoziente K[X]/ℑ(℘).

Prima di dimostrare la Prop. 11 conviene provare il seguente Lemma 6. Poniamo:

D := D(R) = D(℘)
h := max{d_{n} | (d_{1}, …, d_{n}) ∈ D},

e, per ogni r ∈ {0, …, h},

D_{r} := {d = (d_{1}, …, d_{n}) ∈ D | d_{n} = r}
R_{r} := \{R ∈ R | \underline{δ}\underline{R}(R) ∈ D_{r}\}
℘_{r} := U(π_{n−1}(R_{r})).

Osserviamo che, pur dipendendo R_{r} e, quindi, ℘_{r} dall’ordine considerato nell’insieme R, tale dipendenza non gioca alcun ruolo in quanto segue e verrà pertanto sottaciuta.

Lemma 6 Per ogni r ∈ {0, …, h}, ℘_{r} è un multiinsieme algebrico (n − 1)-di-mensionale e si ha

r > r′ ⇒ ℘_{r} ⊆ ℘_{r′};  (20)
D(℘_{r}) = π_{n−1}(D_{r}).  (21)

Dimostrazione. La (20) e la (21) sono conseguenza diretta delle (8) e (9), rispettivamente, del Lemma 3 non appena si osservi (per quanto riguarda la (20)) che R ⊆ S ⇒ U(R) ⊆ U(S) e, (per quanto riguarda la (21)), che l’operatore D che agisce sui multiinsiemi è in effetti la composizione dell’operatore di rappresentazione umbrale u con l’operatore D che agisce sugli insiemi:

π_{n−1}(D_{r}) = D(π_{n−1}(R_{r})) = D(u(℘_{r})) = D(℘_{r}).

□

Dimostrazione della Prop. 11. Ovviamente si ha #B = #℘; poiché codim ℑ(℘) = #℘, è quindi sufficiente provare che nessuna combinazione lineare (non banale) dei monomi in B sia un elemento dell’ideale ℑ(℘). Seguendo la falsariga della dimostrazione della Prop. 6, dimostriamo — ragionando per induzione sulla dimensione n — che se un polinomio p(x_{1}, …, x_{n}) della forma

p(x_{1}, …, x_{n}) = ∑_{d∈D(℘)} α_{d} · x^{d} ,

appartiene a ℑ(℘) allora è identicamente nullo. Si ha

p(x_{1}, …, x_{n}) = ∑_{r=0}^{h} p_{r}(x_{1}, …, x_{n−1}) · x_{n}^{r}

con

p_{r}(x_{1}, …, x_{n−1}) := ∑_{(d_{1},...,d_{n−1})∈π_{n−1}(D_{r})} α_{(d_{1},...,d_{n−1},r)} · x_{1}^{d_{1}} ⋯ x_{n−1}^{d_{n−1}}.

Posto

D_{h} = {d^{(1)}, …, d^{(s)}}

(con d^{(j)} = (d_{1}^{(j)}, …, d_{n−1}^{(j)}, h), j = 1, …, s), si ha

R_{h} = \{R^{(j)} | \underline{δ}\underline{R}(R^{(j)}) = d^{(j)}; j = 1, …, s\}.

Per ogni R^{(j)} ∈ R_{h} vi sono esattamente h+1 punti R ∈ R tale che π_{n−1}(R^{(j)}) = π_{n−1}(R). Indicato con T_{h}^{(j)} il complesso di tali h + 1 punti, poniamo T_{h} := ∪_{j=1}^{s}T_{h}^{(j)}. Non è difficile riconoscere che π_{n−1}(T_{h}) = π_{n−1}(R_{h}) e quindi che U(π_{n−1}(T_{h})) = ℘_{h}. Vi è inoltre una ovvia corrispondenza biunivoca

τ : ℘_{h} → {T_{h}^{(j)} | j = 1, ….s}.

Sia (Q, j) ∈ ℘_{h}, Q ∈ K^{n−1} e j ∈ N^{n−1}, e sia τ(Q, j) = T_{h}^{(l)} per un opportuno intero l ∈ {1, …, s}. Posto Q = (c_{1}, …, c_{n−1}) e j = (j_{1}, …, j_{n−1}), valutiamo umbralmente i punti in τ(Q, j) = T_{h}^{(l)} ⊆ R. [Questi punti sono della forma ((c_{1}, j_{1}), …, (c_{n−1}, j_{n−1}), (c, j)); due di essi differiscono quindi solo nell’ultima componente (c, j)]. Risulta che un certo numero — diciamolo q_{1} ≥ 1 — di questi si trasformano in un punto Q_{1} = (c_{1}, …, c_{n−1}, c_{(1)}), un altro gruppo — diciamo q_{2} ≥ 1 di essi — nel punto Q_{2} = (c_{1}, …, c_{n−1}, c_{(2)}), etc., con q_{1} +q_{2} +⋯ = h+1 e tali inoltre che al diagramma algebrico F_{r} associato — in ℘ — a Q_{r} appartengano le q_{r} n-uple (j_{1}, …, j_{n−1}, 0), …, (j_{1}, …, j_{n−1}, q_{r} − 1). Ne consegue che ogni polinomio f(x_{1}, …, x_{n}) appartenente a ℑ(℘) dovrà essere tale che per ogni (Q, j) ∈ ℘_{h}, Q = (c_{1}, …, c_{n−1}), j = (j_{1}, …, j_{n−1}), il polinomio f̃(x_{n}) := v_{Q}^{j}(f(x_{1}, …, x_{n})) dovrà ammettere le radici c_{(1)}, c_{(2)}, … con le molteplicità q_{1}, q_{2}, … rispettivamente e quindi dovrà avere almeno grado q_{1}+q_{2}+⋯ = h+1. Ne consegue che il polinomio p(x_{1}, …, x_{n}) = ∑_{r=0}^{h} p_{r}(x_{1}, …, x_{n−1})·x_{n}^{r} ∈ ℑ(℘) considerato — essendo di grado al più h in x_{n} — dovrà essere tale che i polinomi

p_{0}(x_{1}, …, x_{n−1}), …, p_{h}(x_{1}, …, x_{n−1})

appartengono all’ideale ℑ(℘_{h}) ⊆ K[x_{1}, …, x_{n−1}]. Poiché p_{h} è della forma

p_{h}(x_{1}, …, x_{n−1}) = ∑_{(d_{1},...,d_{n−1})∈π_{n−1}(D_{h})} α_{(d_{1},...,d_{n−1},h)} · x_{1}^{d_{1}} ⋯ x_{n−1}^{d_{n−1}}.

e poiché, per la (21), D(℘_{h}) = π_{n−1}(D_{h}), dall’ipotesi induttiva si trae che p_{h}(x_{1}, …, x_{n−1}) deve essere identicamente nullo.

Iterando per r = h − 1, h − 2, …, 1, 0 il ragionamento fatto per r = h, si perviene a concludere che p(x_{1}, …, x_{n}) è identicamente nullo e quindi che {[x^{i}]_{ℑ(℘)} | i ∈ D(℘)} costituisce una base lineare monomiale per K[X]/ℑ(℘).

□

References

[1] B. Buchberger, An Algorithmic Method in Polynomial Ideal Theory, in “N. K. Bose (ed): Recent Trends in Multidimensional System Theory”, D. Reidel Publishing Co. , 1985, pp. 184-232

[2] L. Cerlienco, F. Piras On the Continuous Dual of a Polynomial Bialgebra. (preprint)

[3] J.P.S. Kung Jacobi’s identity and the König-Egerváry theorem, Discrete Math. 49(1984) 75-77

[4] L. Robbiano Introduzione all’algebra computazionale. Appunti per il corso INDAM. (Roma 1986/87)

[5] H.M. Möller, B. Buchberger The construction of multivariate polynomials with preassigned zeros, in “Computer Algebra (Marseille, 1982)”, Lecture Notes in Comp. Sci., 144, Springer, Berlin-New York, 1982, pp.24-31

Indirizzo degli autori:

Luigi Cerlienco, Marina Mureddu Dipartimento di Matematica. Via Ospedale 72 — I-09124 Cagliari cerlienc@unica.it, mureddu@unica.it Tel. 39-70-6758529/6758536 Fax 39-70-6758511 Appendice 1 – All’analisi condotta del problema dell’interpolazione in più variabili occorre aggiungere qualche ulteriore considerazione rivolta a mettere in evidenza alcune limitazioni intrinseche — cui già si è fatto cenno nell’introduzione — che non si presentano nel caso unidimensionale. Va chiarito che mentre in quest’ultimo caso la soluzione al problema ha un significato geometrico intrinseco, di contro nel caso n ≥ 2 questa caratteristica viene a mancare. Infatti, se n = 1, la soluzione y = p(x) privilegiata (soddisfacente cioè alla condizione deg(p) < N) dei Problemi 1 e/o 2 rappresenta nel piano (xy) una curva C che è invariante per cambiamenti di riferimento affine sull’asse x; nel caso n–dimensionale, invece, non solo vengono privilegiate più soluzioni y = p_{1}(x_{1}, …, x_{n}), …, y = p_{r}(x_{1}, …, x_{n}) — dipendenti dalle diverse possibili scelte della base monomiale minimale — cui corrispondono diverse superfici Σ_{1}, …, Σ_{r} dello spazio affine (x_{1}, …, x_{n}, y), ma risulta anche che il complesso di tali superfici non è invariante rispetto al gruppo delle trasformazioni affini dello spazio (x_{1}, …, x_{n}). Detto in altri termini: mentre a) nel caso unidimensionale il problema: “trovare una funzione polinomiale che in certi punti P_{i} della retta affine assuma valori assegnati α_{i}” equivale (insieme con la sua soluzione) al problema: “trovare un polinomio (di dato grado) che per certi ρ_{i} [coordinate di P_{i} rispetto ad un arbitrario sistema di riferimento affine sulla retta] assuma valori assegnati α_{i}”; di contro b) non si può affermare qualcosa di simile nel caso multidimensionale.

Chiariamo meglio, e giustifichiamo, le affermazioni precedenti. Nel caso unidimensionale la situazione è la seguente: dati sulla retta N punti P_{i}, sia S la famiglia di funzioni polinomiali che assumono in P_{i} il valore α_{i}. Fissato sulla retta un sistema di riferimento affine R, rispetto al quale chiameremo x la coordinata del generico punto P, resta determinato l’ideale ℑ(P) ⊆ K[x] dell’insieme P = {P_{1}, …, P_{N}} e S è rappresentata da un laterale S di ℑ(P); questo laterale a sua volta viene rappresentato dall’unico polinomio p di grado minore di N contenuto in esso. Adottando poi un nuovo sistema di riferimento R’ e chiamando x′, ℑ′(P) ⊆ K[x′] , S′, p′ gli analoghi dei precedenti, la trasformazione di coordinate affini x′ = α·x+β non solo trasforma ℑ′(P) ⊆ K[x′] in ℑ(P) ⊆ K[x] e S′ in S ma anche p′ in p. Se ripetiamo ora, per il caso n–dimensionale, queste considerazioni — con l’unica differenza che ora i laterali S ed S′ vengono rappresentati, al variare della base monomiale minimale scelta, da uno degli elementi di tutta una famiglia, p_{1}, …, p_{r} e p′_{1}, …, p′_{r′} rispettivamente, contenuta in essi — succede che una generica trasformazione affine x′ = ∑ α_{ij}x_{j} + β_{i}, (i, j = 1, …, n) fa corrispondere ℑ′(P) a ℑ(P) e S′ a S ma non trasforma il generico p_{i} in uno dei p′_{j} bensì, in generale, in un diverso rappresentante di S′. La ragione di ciò sta in quanto segue: il fatto che basi monomiali minimali calcolate rispetto a R non corrispondono a basi monomiali minimali calcolate rispetto a R’ ha — nel caso n > 1 — effetti perversi che non si presentano invece nel caso unidimensionale. Tali effetti sono da imputare al fatto che un monomio x_{1}^{i_{1}} ⋯ x_{n}^{i_{n}} viene trasformato dall’affinità considerata in una combinazione lineare di (tutti) i monomi x′_{1}^{j_{1}} ⋯ x′_{n}^{j_{n}} di grado j_{1} + … + j_{n} ≤ i_{1} + … + i_{n}.

Appendice 2 – Dimostrazione della formula

| A_{1} ⊗ A_{2} ⊗ ⋯ ⊗ A_{n} | = | A_{1} |^{h_{2}···h_{n}} · | A_{2} |^{h_{1}h_{3}···h_{n}} ⋯ | A_{n} |^{h_{1}···h_{n−1}}
= \frac{(| A_{1} | ⋯ | A_{n} |)^{h_{1}h_{2}···h_{n}}}{| A_{1} |^{h_{1}} ⋯ | A_{n} |^{h_{n}}}

È immediato convincersi che la formula in oggetto può essere provata facilmente ragionando per induzione sul numero s dei fattori tensoriali una volta provata per s=2. Poiché se B_{1} ∼ A_{1} e B_{2} ∼ A_{2} allora A_{1} ⊗ A_{2} ∼ B_{1} ⊗ B_{2}, è sufficiente provarla nel caso in cui A_{1} e A_{2} siano in forma canonica di Jordan (passando eventualmente alla chiusura algebrica del campo K).

Considerate la matrici A = (a_{j}^{i}) e B = (b_{k}^{h}), con i, j = 0, …, n − 1, e h, k = 0, …, m − 1, la matrice

A ⊗ B = C = (c_{β}^{α}) α, β = 0, …, mn − 1

è data da

(∗) c_{β}^{α} = ar ; r̃ · bq ; q̃ con α = qn + r, β = q̃n + r̃ e r, r̃ < n

Se A e B sono triangolari inferiori (a_{j}^{i} = 0 per i < j e b_{k}^{h} = 0 per h < k) allora da (∗) consegue che anche A ⊗ B = C è triangolare inferiore ( infatti c_{β}^{α} = ar ; r̃ · bq ; q̃ è diverso da zero solo a patto che r ≥ r̃ e q ≥ q̃ e quindi che α = nq + r ≥ nq̃+ r̃ = β). Si verifica inoltre che gli elementi della diagonale di A ⊗ B sono dati dai prodotti degli elementi della diagonale di A per quelli della diagonale di B. Con ciò la formula considerata resta provata. □

Seconda dimostrazione della Prop. 1 La matrice di Vandermonde V_{j} associata alle radici di γ_{j} è la matrice che esprime il cambiamento di base, nello spazio S_{j} delle s.r.l. di scala γ_{j}, dalla base delle s.r.l. fondamentali (chiamiamola b_{j,1}, …, b_{j,h_{j}}) alla base delle radici (chiamiamola c_{j,1}, …, c_{j,h_{j}}). Orbene il sottospazio S ⊆ K[X]^{∘} delle forme ricorrenti n-lineari associate all’ideale Γ = (γ_{1}, …, γ_{n}) ⊆ K[X] è il prodotto tensoriale degli spazi S_{j}:

S = S_{1} ⊗ ⋯ ⊗ S_{n}

e la matrice

H_{≺}(P̃) = V_{1} ⊗ ⋯ ⊗ V_{n}

esprime il cambiamento dalla base delle forme ricorrenti n-lineari fondamentali

b_{1,t_{1}} ⊗ ⋯ ⊗ b_{n,t_{n}} (1 ≤ t_{j} ≤ h_{j})

alla base delle valutazioni v_{P}, P ∈ P̃. Ne consegue l’enunciato in quanto la matrice in oggetto è la matrice di un cambiamento di base. □

Appendice 3 – Sulla dimostrazione della Prop. 7.

Chiariamo la dimostrazione della Prop. 7 ripetendone — con riferimento ad un esempio concreto — alcuni dei passi principali.

Per comodità, chiamiamo le variabili x, y, z, t in luogo di x_{1}, x_{2}, x_{3}, x_{4} e identifichiamo D(P) con \{x^{d} | d ∈ D(P)\}. Supponiamo che si abbia \underline{P} = \underline{\{P_{1}, …, P_{33}\}}, cui corrisponda il diagramma D(\underline{P}) = \underline{\{d_{1}, …, d_{33}\}} seguente:

d_{1} = 1  d_{2} = x  d_{3} = x^{2}  d_{4} = x^{3}  d_{5} = x^{4} d_{6} = x^{5}
d_{7} = y d_{8} = xy d_{9} = x^{2}y d_{10} = x^{3}y d_{11} = x^{4}y
d_{12} = y^{2} d_{13} = xy^{2} d_{14} = x^{2}y^{2} d_{15} = x^{3}y^{2}
d_{16} = y^{3} d_{17} = xy^{3}
d_{18} = z  d_{19} = xz d_{20} = x^{2}z d_{21} = x^{3}z
d_{22} = yz d_{23} = xyz d_{24} = x^{2}yz
d_{25} = y^{2}z d_{26} = xy^{2}z
\left[{d_{27} = z^{2} d_{28} = xz^{2} \atop d_{29} = yz^{2}}\right]

\left[{d_{30} = t d_{31} = xt \atop d_{32} = yt}\right]
[ d_{33} = zt ]

Per la Prop. 4, inoltre, possiamo supporre di aver ordinato \underline{P} in modo tale che gli elementi di \underline{D} := D(\underline{P}) vengano determinati nell’ordine lessicografico inverso, che è quello con cui sono stati numerati.

Supponiamo per assurdo che D ∪ C − D ∩ C ≠ ∅ e che il più piccolo fra gli elementi appartenenti a D ∪ C − D ∩ C sia, ad esempio, f = x^{3}yz ∉ D ( e quindi f ∈ C). Si ha ora s = 3 e f_{s} = f_{3} = 1.

In primo luogo mostriamo che non è restrittivo far riferimento a \underline{P̂} := \underline{\{P_{1}, …, P_{29}\}}, \underline{D̂} := D(\underline{P̂}) = \underline{\{d_{1}, …, d_{29}\}} e Ĉ := C(\underline{P̂}) (anziché a \underline{P}, D(\underline{P}) e C). Se infatti f = x^{3}yz ∉ Ĉ allora si avrebbe

(∗) x^{3}yz ≡ p[d_{1} = 1, d_{2} = x, …, d_{29} = yz^{2}] mod.ℑ(P̂)

(con la notazione a secondo membro si denota una combinazione lineare dei monomi entro parentesi quadre) e il polinomio

(∗∗) x^{3}yz − p[d_{1} = 1, d_{2} = x, …, d_{29} = yz^{2}]

si annullerebbe per ciascuno dei punti P_{1}, …, P_{29} e quindi — poiché, a causa della struttura di D(\underline{P}), risulta che le prime tre coordinate di uno qualunque dei punti P_{30}, …, P_{33} sono anche quelle di qualcuno dei punti P_{1}, …, P_{29} — si annullerebbe su tutto P e pertanto la congruenza (∗) sarebbe soddisfatta anche mod.ℑ(P), contro l’ipotesi che f = x^{3}yz ∈ C.

Siamo quindi legittimati ad assumere che fin dall’inizio si sia posto \underline{P} = \underline{\{P_{1}, …, P_{29}\}} e D(\underline{P}) = \underline{\{d_{1}, …, d_{29}\}}. Proviamo ora che ogni polinomio della forma (∗∗) (e quindi nelle sole variabili x, y, z) appartenente a ℑ(P) è di grado f_{s} = f_{3} = 1 in z cioè che i coefficienti dei termini in D̆ := {d_{27} = z^{2}, d_{28} = xz^{2}, d_{29} = yz^{2}} sono nulli. Indichiamo con (a + bx + cy)z^{2} il complesso di tali termini. Per ogni punto P in \underline{P̆} := \underline{\{P_{27}, P_{28}, P_{29}\}} = \underline{δ}−1 ; \underline{P}(D̆) devono trovarsi in P altri d_{s} = d_{3} = 2 punti aventi le stesse prime s−1 = 2 coordinate di P; pertano sostituendo tali prime due coordinate a x e y in (∗∗) si ottiene un polinomio nella sola z che — ammettendo d_{s}+1 = 3 radici distinte ed essendo di grado d_{s} = 2 — deve annullarsi identicamente. In particolare tali prime due coordinate ( quelle dei punti dell’insieme \underline{Q̆} := \{π_{2}(P_{27}), π_{2}(P_{28}), π_{2}(P_{29})\} ) devono annullare il polinomio a + bx + cy ∈ K[x, y], cioè a + bx + cy ∈ ℑ(\underline{Q̆}). Ma ciò è possibile solo a patto che a = b = c = 0 perché, come è facile dedurre dalla struttura di D(\underline{P}), si ha {1, x, y} = D({P_{27}, P_{28}, P_{29}}) = D({π_{2}(P_{27}), π_{2}(P_{28}), π_{2}(P_{29})}) e quindi 1, x, y costituiscono un sistema di rappresentanti per una base monomiale di K[x, y]/ℑ(\underline{Q̆}).

Pertanto un eventuale polinomio (∗∗) appartenente a ℑ(P) deve essere della forma

(∗ ∗ ∗) x^{3}yz − p[d_{1} = 1, d_{2} = x, …, d_{26} = xy^{2}z].

Ripartiamo i termini (diversi da x^{3}yz) in (∗ ∗ ∗) nei tre sottoinsiemi D_{1} := {d_{25}, d_{26}}, D_{2} := {d_{18}, …, d_{24}} e D_{3} := {d_{1}, …, d_{17}} ( a seconda che d_{j} sia maggiore di f = x^{3}yz oppure, pur avendo lo stesso esponente in z, sia minore o infine abbia un esponente in z inferiore) e proviamo che anche i coefficienti di d_{25} e d_{26} devono annullarsi. Posto P̃ := \underline{δ}−1 ; \underline{P}(D_{1} ∪ D_{2}) = \{P_{18}, …, P_{26}\} e osservato che per ogni punto in P̃ ne esistono in \underline{P} altri f_{s} = 1 aventi le stesse prime s − 1 = 2 coordinate di quello, il fatto che il polinomio (∗ ∗ ∗) è di grado f_{s} = 1 in z comporta che, sostituendo in (∗ ∗ ∗) a x e y le prime due coordinate di uno qualunque dei punti in P̃ (e quindi di uno qualunque dei punti in Q̃ := π_{2}(P̃) ) si ottiene un polinomio in z che deve annullarsi identicamente. In particolare i punti di Q̃ devono annullare il polinomio in x, y che costituisce il coefficiente di z in (∗ ∗ ∗), diciamolo

(#) x^{3}y − p_{(1)} − p_{(2)}

con

p_{(1)} := a_{25}y^{2} + a_{26}xy^{2}
p_{(2)} := a_{18} + a_{19}x + a_{20}x^{2} + a_{21}x^{3} + a_{22}y + a_{23}xy + a_{24}x^{2}y.

In altri termini, il polinommio (#) appartiene ℑ(Q̃). D’altra parte i termini in (#) diversi da x^{3}y sono, come è facile controllare, gli elementi di D(Q̃) = π_{2}(D_{1}∪ D_{2}) e x^{3}y = π_{2}(x^{3}yz) è un elemento diedrale di D(Q̃). Quindi x^{3}y ∉ D(Q̃) = C(Q̃) (quest’ultima uguaglianza è garantita dall’ipotesi induttiva). La relazione x^{3}y ∉ C(Q̃) e il fatto che C(Q̃) sia minimale rispetto all’ordine lessicografico inverso comportano che, modulo ℑ(Q̃), x^{3}y sia esprimibile, in uno ed un sol modo, come combinazione lineare dei termini in C(Q̃) = D(Q̃) più piccoli di x^{3}y, cioè che in (#) si abbia a_{25} = a_{26} = 0, che è quanto restava da provare per concludere che f = x^{3}yz ∉ C(P) in contraddizione con D(P) ≠ C(P). □

Appendice 4 – Sulla Prop. 9.

Diamo una dimostrazione diretta del fatto che i monomi nella tabella della Prop. 9 costituiscono un sistema di rappresentati per una base monomiale rispetto all’ideale del multiisieme algebrico là considerato. Dimostrazione. Per ogni 1 ≤ i ≤ m associamo al monomio x^{m−i}y^{h_{m−i+1}−1} l’insieme

M_{i} := ∪_{j=1}^{i}S_{m−j,h_{m−j+1}−1}

come pure (se i ≠ m) l’insieme

A_{i+1} := S_{m−1,h_{m−i}−1} − M_{i+1}

dove si è indicato con S_{i,j} l’insieme S_{i,j} := {x^{i′}y^{j′}|i′ ≤ i e j′ ≤ j}; poniamo inoltre M_{0} = A_{1} := ∅. Osserviamo che si ha

M_{0} ⊆ M_{1} ⊆ M_{2} ⊆ … ⊆ M_{m} = M_{P}
A_{1} ⊆ A_{2} ⊆ A_{3} ⊆ … ⊆ A_{m}
#M_{m} = #M_{P} = #P.

Nei calcoli che seguono denoteremo le funzioni simmetriche elementari delle variabili ρ_{1}, …, ρ_{n} mediante le notazioni

[ρ_{1}, …, ρ_{n}]_{0} := −1
[ρ_{1}, …, ρ_{n}]_{1} := ρ_{1} + … + ρ_{n}
[ρ_{1}, …, ρ_{n}]_{2} := −(ρ_{1}ρ_{2} + … + ρ_{n−1}ρ_{n})
. . . . . . . . . . . .
[ρ_{1}, …, ρ_{n}]_{n} := (−1)^{n−1}ρ_{1}ρ_{2} ⋯ ρ_{n}

cioè

[ρ_{1}, …, ρ_{n}]_{i} := (−1)^{i−1} ∑_{1≤j_{1}<...<j_{i}≤n} ρ_{j_{1}}ρ_{j_{2}} ⋯ ρ_{j_{i}}.

Poiché #M_{m} = #M_{P} = #P = codim ℑ(P) è sufficiente dimostrare che le classi di equivalenza (modulo ℑ(P)) dei monomi in M_{m} costituiscono un insieme di generatori per l’algebra quoziente K[X]/ℑ(P). Ciò discende subito dalle congruenze

(C_{s}) x^{s}y^{h_{s+1}} ≡ ∑_{i=1}^{s} [ρ_{1}, ρ_{2}, …, ρ_{s}]_{i} x^{s−i}y^{h_{s+1}} + ∑_{τ∈M_{m−s}} μ_{τ} τ

(C′_{s}) x^{i}y^{j} ≡ ∑_{τ∈M_{m−s+1}} α_{τ} τ se x^{i}y^{j} ∈ A_{m−s+1}

(con μ_{τ} , α_{τ} ∈ K) per s = m, m − 1, …, 1, 0 ed avendo assunto h_{m+1} := 0.

È facile verificare che la (C′_{s}) è una diretta conseguenza di (C_{t}) per m ≥ t ≥ s. Proviamo quest’ultima ragionando induttivamente sui valori decrescenti di s. Per s = m essa è banalmente vera, giacché esprime semplicemente il fatto che il polinomio

∏_{i=1}^{m}(x − ρ_{i}) = − ∑_{i=0}^{m} [ρ_{1}, …, ρ_{m}]_{i} x^{m−i}

appartiene a I = ℑ(P).

Supponiamo pertanto che la (C_{s}) sia vera per ogni m ≥ s ≥ t e proviamola per s = t − 1.

Consideriamo il polinomio contenuto in ℑ(P)

p_{t} := ∏_{i≠t}(x − ρ_{i}) · ∏_{j=1}^{h_{t}}(y − σ_{t,j}) =

= − ∑_{i=0}^{m−1} [ρ_{1}, …, ρ_{t−1}, ρ_{t+1}, …, ρ_{m}]_{i} x^{m−1−i}y^{h_{t}} +

+ ∑_{τ∈A_{m−t+1}} β_{τ} τ + ∑_{τ∈M_{m−t+1}} γ_{τ} τ ≡

(usando la (C′_{t}) per inglobare la seconda sommatoria nella terza)

≡ x^{m−1}y^{h_{t}} − ∑_{i=1}^{m−1} [ρ_{1}, …, ρ_{t−1}, ρ_{t+1}, …, ρ_{m}]_{i} x^{m−1−i}y^{h_{t}} +

+ ∑_{τ∈M_{m−t+1}} δ_{τ} τ ≡

(usando prima la (C_{m−1}) e successivamente la (C′_{t}) per ridurre il primo termine)

≡ ∑_{i=1}^{m−1} {[ρ_{1}, …, ρ_{m−1}]_{i} − [ρ_{1}, …, ρ_{t−1}, ρ_{t+1}, …, ρ_{m}]_{i}} x^{m−1−i}y^{h_{t}} +

+ ∑_{τ∈M_{m−t+1}} ε_{τ} τ =

= (ρ_{t} − ρ_{m}) ∑_{i=1}^{m−1} −[ρ_{1}, …, ρ_{t−1}, ρ_{t+1}, …, ρ_{m−1}]_{i−1} x^{m−1−i}y^{h_{t}} +

+ ∑_{τ∈M_{m−t+1}} ε_{τ} τ =

(posto i in luogo di i − 1)

= (ρ_{t} − ρ_{m}){x^{m−2}y^{h_{t}} − ∑_{i=1}^{m−2} [ρ_{1}, …, ρ_{t−1}, ρ_{t+1}, …, ρ_{m−1}]_{i} x^{m−2−i}y^{h_{t}}} +

+ ∑_{τ∈M_{m−t+1}} ε_{τ} τ ≡

(utilizzando ora la (C_{m−2}) e successivamente la (C′_{t}) per ridurre il primo termine e operando le semplificazioni come nei passaggi precedenti)

≡ (ρ_{t} − ρ_{m})(ρ_{t} − ρ_{m−1}){x^{m−3}y^{h_{t}} +

− ∑_{i=1}^{m−3} [ρ_{1}, …, ρ_{t−1}, ρ_{t+1}, …, ρ_{m−2}]_{i} x^{m−3−i}y^{h_{t}}} + ∑_{τ∈M_{m−t+1}} η_{τ} τ ≡

. . . . . . . . . . . . . . . . . .
≡ (ρ_{t} − ρ_{m})(ρ_{t} − ρ_{m−1}) ⋯ (ρ_{t} − ρ_{t+1}){x^{t−1}y^{h_{t}} +

− ∑_{i=1}^{t−1} [ρ_{1}, …, ρ_{t−1}]_{i} x^{t−1−i}y^{h_{t}}} + ∑_{τ∈M_{m−t+1}} ζ_{τ} τ

≡ 0 (modulo ℑ(P))

da cui la (C_{t−1}). □

Appendice 5 – Sulla dimostrazione della Prop. 11.

A titolo chiarificatore, ripercorriamo — facendo riferimendo ad un caso concreto — il ragionamento fatto nella dimostrazione della Prop. 11.

Sia dato il multiinsieme algebrico ℘:

P_{1} = (0, 0, 0) [ \begin{matrix}(0, 0, 0) & (1, 0, 0) \\ (0, 1, 0) \end{matrix}  ^{(0, 0, 1) ]}

P_{2} = (0, 0, 1) [ (0, 0, 0) (1, 0, 0) (2, 0, 0)  (0, 0, 1) (1, 0, 1) ]

P_{3} = (1, 1, 0) [ \begin{matrix}(0, 0, 0) & (1, 0, 0) \\ (0, 1, 0) & (1, 1, 0) \end{matrix}  \begin{matrix}(0, 0, 1) & (1, 0, 1) \\ (0, 1, 1) \end{matrix}  \begin{matrix}(0, 0, 2) \\ (0, 1, 2) \end{matrix} ]

P_{4} = (1, 1, 1) [ \begin{matrix}(0, 0, 0) \\ (0, 1, 0) \end{matrix} ]

La sua rappresentazione umbrale R = R(℘) (qui, volutamente, gli elementi di R vengono elencati secondo un ordine casuale) ed il corrispondente diagramma D(R) sono dati dalla tabella

R  ⟷  D(R)
R_{1} = (10, 10, 02)  ⟷  d_{1} = (0, 0, 0)
R_{2} = (10, 11, 02)  ⟷  d_{2} = (0, 1, 0)
R_{3} = (01, 00, 11)  ⟷  d_{3} = (1, 0, 0)
R_{4} = (11, 10, 01)  ⟷  d_{4} = (2, 0, 0)
R_{5} = (00, 00, 11)  ⟷  d_{5} = (3, 0, 0)
R_{6} = (10, 10, 01)  ⟷  d_{6} = (0, 0, 1)
R_{7} = (02, 00, 10)  ⟷  d_{7} = (4, 0, 0)
R_{8} = (01, 00, 00)  ⟷  d_{8} = (1, 0, 1)
R_{9} = (10, 10, 00)  ⟷  d_{9} = (0, 0, 2)
R_{10} = (00, 01, 00)  ⟷  d_{10} = (1, 1, 0)
R_{11} = (00, 00, 00)  ⟷  d_{11} = (2, 0, 1)
R_{12} = (00, 00, 01)  ⟷  d_{12} = (1, 0, 2)
R_{13} = (10, 11, 00)  ⟷  d_{13} = (0, 1, 1)
R_{14} = (11, 10, 00)  ⟷  d_{14} = (3, 0, 1)
R_{15} = (00, 00, 10)  ⟷  d_{15} = (0, 0, 3)
R_{16} = (10, 11, 01)  ⟷  d_{16} = (0, 1, 2)
R_{17} = (11, 11, 00)  ⟷  d_{17} = (2, 1, 0)
R_{18} = (01, 00, 10)  ⟷  d_{18} = (2, 0, 2)
R_{19} = (10, 11, 10)  ⟷  d_{19} = (1, 0, 3)
R_{20} = (10, 10, 10)  ⟷  d_{20} = (0, 1, 3)

Dobbiamo dimostrare che l’insieme delle classi di equivalenza (modulo ℑ(℘)) dei monomi

\begin{matrix}1 & x_{1} & x_{1}^{2} & x_{1}^{3} & x_{1}^{4} \\ x_{2} & x_{1}x_{2} & x_{1}^{2}x_{2} \end{matrix}  \begin{matrix}x_{3} & x_{1}x_{3} & x_{1}^{2}x_{3} & x_{1}^{3}x_{3} \\ x_{2}x_{3} \end{matrix}

\begin{matrix}x_{3}^{2} & x_{1}x_{3}^{2} & x_{1}^{2}x_{3}^{2} \\ x_{2}x_{3}^{2} \end{matrix}  \begin{matrix}x_{3}^{3} & x_{1}x_{3}^{3} \\ x_{2}x_{3}^{3} \end{matrix}

costituisce una base monomiale per K[X]/ℑ(℘), cioè che ogni polinomio

p(x_{1}, …, x_{n}) = p_{0}[1, x_{1}, x_{1}^{2}, x_{1}^{3}, x_{1}^{4}, x_{2}, x_{1}x_{2}, x_{1}^{2}x_{2}] + p_{1}[1, x_{1}, x_{1}^{2}, x_{1}^{3}, x_{2}] · x_{3} +
+p_{2}[1, x_{1}, x_{1}^{2}, x_{2}] · x_{3}^{2} + p_{3}[1, x_{1}, x_{2}] · x_{3}^{3} ∈ ℑ(℘)

(qui le parentesi quadre stanno ad indicare che il polinomio p[η, ζ, …] è una combinazione lineare dei monomi η, ζ, …) è identicamente nullo.

In D(R) il massimo valore assunto dalla terza componente è h = 3; consideriamo pertanto l’insieme

D_{3} = {d^{(1)} = d_{15} = (0, 0, 3), d^{(2)} = d_{19} = (1, 0, 3), d^{(3)} = d_{20} = (0, 1, 3)}

e l’insieme delle sue controimmagini tramite \underline{δ}\underline{R}:

R_{3} = {R^{(1)} = R_{15} = (00, 00, 10), R^{(2)} = R_{19} = (10, 11, 10),
R^{(3)} = R_{20} = (10, 10, 10)}.

[NB. Se, inizialmente, avessimo considerato i punti in R in un diverso ordine, l’insieme R_{3} sarebbe stato diverso da quello qui effettivamente ottenuto ma tutta l’analisi che segue si sarebbe potuta ripetere esattamente allo stesso modo. In effetti un diverso ordine in R provocherebbe — al più — una permutazione degli indici in alto degli insiemi T_{3}^{(j)} e lascerebbe quindi inalterato l’insieme T_{3}.] Consideriamo R^{(1)} = R_{15} = (00, 00, 10) ∈ R_{3}; poiché l’ultima coordinata di \underline{δ}\underline{R}(R^{(1)}) = d^{(1)} = d_{15} = (0, 0, 3) è “3”, devono esservi in R altri tre punti — che precedono R_{15} = R^{(1)} — le cui coordinate sono della forma (00, 00, − −); l’insieme di questi punti viene indicato con T_{3}^{(1)}; in effetti si tratta dell’insieme

T_{3}^{(1)} = {R_{5} = (00, 00, 11), R_{11} = (00, 00, 00),
R_{12} = (00, 00, 01), R_{15} = (00, 00, 10)}.

Analogamente, in corrispondenza agli altri due punti di R_{3}, si trovano gli insiemi

T_{3}^{(2)} = {R_{2} = (10, 11, 02), R_{13} = (10, 11, 00),
R_{16} = (10, 11, 01), R_{15} = (10, 11, 10)},

T_{3}^{(3)} = {R_{1} = (10, 10, 02), R_{6} = (10, 10, 01),
R_{9} = (10, 10, 00), R_{20} = (10, 10, 10)}.

Posto

T_{3} := T_{3}^{(1)} ∪ T_{3}^{(2)} ∪ T_{3}^{(3)},

si ha

π_{2}(T_{3}) = π_{2}(R_{3}) = {(00, 00), (10, 11), (10, 10)}
℘_{3} = U(π_{2}(T_{3})) = {((0, 0), (0, 0)) ((1, 1), (0, 0)) ((1, 1), (0, 1))} =
= {(0, 0), [(0, 0)]; (1, 1), [(0, 0), (0, 1)]}

e

τ : ((0, 0), (0, 0)) ↦ T_{3}^{(1)}; ((1, 1), (0, 0)) ↦ T_{3}^{(3)}; ((1, 1), (0, 1)) ↦ T_{3}^{(2)}.

NB. All’elemento ((a_{1}, a_{2}), (i_{1}, i_{2})) ∈ ℘_{3} la bigezione τ fa corrispondere il T_{3}^{(j)} i cui elementi sono della forma ((a_{1}, i_{1}), (a_{2}, i_{2}), (−, −)).

Consideriamo ora un polinomio f(x_{1}, x_{2}, x_{3}) ∈ ℑ(℘) e fissiamo la nostra attenzione — ad esempio — sul punto (Q, j) = ((1, 1), (0, 1)) di ℘_{3}, sulla sua immagine T_{3}^{(2)} in τ e sulla valutazione umbrale

U(T_{3}^{(2)}) = {(1, 1, 0), [(0, 1, 0), (0, 1, 1), (0, 1, 2)]; (1, 1, 1), [(0, 1, 0)]}.

La relazione U(T_{3}^{(2)}) ⊆ ℘ garantisce che, valutando in x_{1} = x_{2} = 1 la derivata rispetto ad x_{2} di f si ottiene un polinomio in x_{3} che deve ammettere la radice tripla x_{3} = 0 e la radice x_{3} = 1 e quindi deve essere almeno di quarto grado. Similmente, se fissiamo l’attenzione sugli altri due punti (Q, j) = ((1, 1), (0, 0)) e, rispettivamente, (Q, j) = ((0, 0), (0, 0)) di ℘_{3}, otteniamo che anche le valutazioni di f in x_{1} = x_{2} = 1 e in x_{1} = x_{2} = 0 devono essere polinomi in x_{3} almeno di quarto grado.

Nel caso in cui f(x_{1}, x_{2}, x_{3}) = p(x_{1}, x_{2}, x_{3}) ciò comporta che il coefficiente p_{3}[1, x_{1}, x_{2}] di x_{3}^{3} in p deve annullarsi in (1, 1) insieme con la sua derivata prima dispetto a x_{2} ed in (0, 0), cioè deve appartenere all’ideale del multiinsieme algebrico ℘_{3}. Poiché la base monomiale che l’operatore D associa a ℘_{3} è proprio costituita dai monomi 1, x_{1}, x_{2}, si può — applicando l’ipotesi induttiva — concludere che p_{3}[1, x_{1}, x_{2}] è identicamente nullo.

A questo punto abbiamo quindi

p(x_{1}, …, x_{n}) = p_{0}[1, x_{1}, x_{1}^{2}, x_{1}^{3}, x_{1}^{4}, x_{2}, x_{1}x_{2}, x_{1}^{2}x_{2}] + p_{1}[1, x_{1}, x_{1}^{2}, x_{1}^{3}, x_{2}] · x_{3} +
+p_{2}[1, x_{1}, x_{1}^{2}, x_{2}] · x_{3}^{2};

considerando ora D_{2} (in luogo di D_{3}) possiamo ripercorrere tutto il ragionamento precedente fino ad ottenere p_{2}[1, x_{1}, x_{1}^{2}, x_{2}] ≡ 0, etc. etc. □