DM Algorithmique avancée :: Polynômes multivariables : appartenance à idéal, division, caractérisation et calcul d’une base d’un idéal

DM d’Algorithmique 2

Younesse Kaddar

I. Ordre bien fondé

1.

Soient $F⊆E$ où $E$ est doté d’un ordre $\preccurlyeq$ bien fondé, $f∈F$.

Montrons qu’il existe $f^\ast$ minimal tel que

\[f^\ast \preccurlyeq f\]

Par l’absurde : supposons que pour tout $f’ ∈ F$ tel que $f’ \preccurlyeq f$, il existe $f’’ ∈ F$ tel que $f’’ \prec f’$.

Comme $f \preccurlyeq f$ (par réflexivité), il existe donc $f_0 ∈ F$ tel que $f_0 \prec f$.

Et de même, comme $f_0 \preccurlyeq f$, il existe $f_1 ∈ F$ tel que $f_1 \prec f_0 \prec f$.

Par une récurrence immédiate, on construit donc une suite $(f_n)_{n∈ℕ} ∈ F^ℕ$ telle que : $∀n∈ℕ$,

\[f_n \prec f_{n-1} \prec ⋯ \prec f_0 \prec f\]

En particulier : $(f_n)_{n∈ℕ}$ est strictement décroissante, ce qui contredit le fait que $\preccurlyeq$ soit bien fondé.

On a donc montré que

Si $F⊆E$ où $E$ est doté d’un ordre $\preccurlyeq$ bien fondé, et $f∈F$ : il existe $f^\ast ∈ F$ minimal tel que

\[f^\ast \preccurlyeq f\]

2.

Soit $\prec$ un ordre monomial sur $ℕ^n$, c’est-à-dire que :

  1. $\prec$ est total
  2. pour tous $𝛼, 𝛽, 𝛾 ∈ ℕ^n$,
\[𝛼 \prec 𝛽 ⟹ 𝛼 + 𝛾 \prec 𝛽 + 𝛾\]
  1. $\prec$ est bien fondé

Montrons que pour tout $𝛼 ≠ \mathbf{0}∈ℕ^n$,

\[\mathbf{0} \prec 𝛼\]

Remarquons que comme $\prec$ est total, cela revient à montrer que $\mathbf{0}$ est minimal.

  • en effet :

    \[\begin{align*} \not\exists 𝛼∈ℕ^n; \; 𝛼 \prec \mathbf{0} & ⟺ \not ∃ 𝛼∈ℕ^n; \; \mathbf{0} \not\preccurlyeq 𝛼 &&\text{( car l'ordre est total)}\\ & ⟺ ∀ 𝛼∈ℕ^n, \; \mathbf{0} \preccurlyeq 𝛼 \\ & ⟺ ∀ 𝛼∈ℕ^n\backslash \lbrace \mathbf{0} \rbrace, \; \mathbf{0} \prec 𝛼 &&\text{( par réflexivité)}\\ \end{align*}\]

Par l’absurde : supposons que $\mathbf{0}$ n’est pas minimal.

Alors il existe $𝛼 ∈ℕ^n$ tel que

\[\underbrace{𝛼}_{\text{noté } 𝛼_1} \prec \mathbf{0}\]

Par suite, comme $\prec$ est monomial : $∀m∈ℕ^\ast$,

\[\underbrace{(m+1)𝛼}_{\text{noté } 𝛼_{m+1}} = 𝛼 + m𝛼 \prec \mathbf{0} + m𝛼 = \underbrace{m𝛼}_{\text{noté } 𝛼_{m}}\]

On a donc construit une suite $(𝛼_m)_{m∈ℕ^\ast}$ strictement décroissante, ce qui contredit le caractère bien fondé de $\prec$.

On a donc montré que :

Si $\prec$ est un ordre monomial, pour tout $𝛼 ≠ \mathbf{0}∈ℕ^n$ :

\[\mathbf{0} \prec 𝛼\]

3.

NB : On supposera qu’on dénote, par convention :

  • $\prec_{lex}$ et $\prec_{grlex}$ les ordres stricts (qui ne sont pas des ordres, puisque non réflexifs)

  • $\preccurlyeq_{lex}$ et $\preccurlyeq_{grlex}$ les ordres larges

\[\preccurlyeq_{lex} \text{ est monomial.}\]

  1. $\preccurlyeq_{lex}$ est clairement total, puisque $≤$ l’est.

  2. Soient $𝛼, 𝛽, 𝛾 ∈ ℕ^n$ tels que $𝛼 \preccurlyeq_{lex} 𝛽$. Montrons que

    \[𝛼 + 𝛾 \preccurlyeq_{lex} 𝛽 + 𝛾\]

    Comme $𝛼 \preccurlyeq_{lex} 𝛽$ :

    • soit $𝛼 = 𝛽$, auquel cas le résultat est acquis par réflexivité.

    • soit il existe $i$ tel que

      • $𝛼_i < 𝛽_i$
      • $∀j<i, 𝛼_j = 𝛽_j$

      auquel cas, pour ce même $i$ :

      • $𝛼_i + 𝛾_i < 𝛽_i + 𝛾_i$
      • $∀j<i, 𝛼_j + 𝛾_j = 𝛽_j + 𝛾_j$

      ce qui conclut.

  3. $\preccurlyeq_{lex}$ est bien fondé :

    Par l’absurde, supposons qu’il existe une suite $(𝛼^{(i)})_{i∈ℕ}$ strictement décroissante pour $\preccurlyeq_{lex}$.

    Alors pour tout $i∈ℕ$, il existe $k_i ∈ ⟦1, n⟧$ tel que

    \[𝛼^{(i+1)}_{k_i} < 𝛼^{(i)}_{k_i}\]

    c’est-à-dire (comme $(𝛼^{(i)})_{i∈ℕ}$ est décroissante) :

    \[∀i' > i,\; \quad 𝛼^{(i')}_{k_i} < 𝛼^{(i)}_{k_i}\]

    Donc comme $(k_i)_{i∈ℕ}$ est à valeurs dans l’ensemble fini $⟦1, n⟧$, il existe (par le principe des tiroirs) $j∈⟦1, n⟧$ tel que :

    \[K_j ≝ \lbrace i∈ℕ \mid k_i = j \rbrace\]

    est infini.

    La suite $(𝛼^{(i)}_j)_{i∈K_j}$ est donc strictement décroissante, car :

    \[∀i < i' ∈K_j,\; \; 𝛼^{(i')}_j ≤ 𝛼^{(i+1)}_j = 𝛼^{(i+1)}_{k_i} < 𝛼^{(i)}_{k_i} = 𝛼^{(i)}_j\]

    ce qui est impossible, puisque $<$ est bien fondé.

\[\preccurlyeq_{grlex} \text{ est monomial.}\]

Montrons déjà que $\preccurlyeq_{grlex}$ est un ordre :

  • la réflexivité de $\preccurlyeq_{grlex}$ est héritée de celles de $=$ et de $\preccurlyeq_{lex}$.

  • $\preccurlyeq_{grlex}$ est antisymétrique :

    si $𝛼, 𝛽∈ℕ^n$ sont tels que $𝛼 \preccurlyeq_{grlex} 𝛽$ et $𝛽 \preccurlyeq_{grlex} 𝛼$ :

    • alors $\sum\limits_{ i ≤n } 𝛼_i < \sum\limits_{ i ≤n } 𝛽_i$ est impossible

      • car sinon, de $𝛽 \preccurlyeq_{grlex} 𝛼$, on tire $\sum\limits_{ i ≤n } 𝛼_i = \sum\limits_{ i ≤n } 𝛽_i$

      d’où, comme $𝛼 \preccurlyeq_{grlex} 𝛽$ :

      \[\sum\limits_{ i ≤n } 𝛼_i = \sum\limits_{ i ≤n } 𝛽_i \text{ et } 𝛽 \preccurlyeq_{lex} 𝛼\]

    • de même, de $𝛽 \preccurlyeq_{grlex} 𝛼$, on tire :

      \[\sum\limits_{ i ≤n } 𝛽_i = \sum\limits_{ i ≤n } 𝛼_i \text{ et } 𝛼 \preccurlyeq_{lex} 𝛽\]

    donc $𝛼 = 𝛽$, par antisymétrie de $\preccurlyeq_{lex}$.

  • $\preccurlyeq_{grlex}$ est transitive :

    si $𝛼, 𝛽, 𝛾∈ℕ^n$ sont tels que $𝛼 \preccurlyeq_{grlex} 𝛽$ et $𝛽 \preccurlyeq_{grlex} 𝛾$ :

    • alors si $\sum\limits_{ i ≤n } 𝛼_i < \sum\limits_{ i ≤n } 𝛽_i$, dans tous les cas : \(\sum\limits_{ i ≤n } 𝛼_i < \sum\limits_{ i ≤n } 𝛾_i \text{, d'où } 𝛼 \preccurlyeq_{grlex} 𝛾\)

    • sinon si $\sum\limits_{ i ≤n } 𝛼_i = \sum\limits_{ i ≤n } 𝛽_i$ et $𝛼 \preccurlyeq_{lex} 𝛽$ :

      • et si $\sum\limits_{ i ≤n } 𝛽_i < \sum\limits_{ i ≤n } 𝛾_i$ : alors $\sum\limits_{ i ≤n } 𝛼_i < \sum\limits_{ i ≤n } 𝛾_i$, d’où $𝛼 \preccurlyeq_{grlex} 𝛾$

      • et si $\sum\limits_{ i ≤n } 𝛽_i = \sum\limits_{ i ≤n } 𝛾_i$ et $𝛽 \preccurlyeq_{lex} 𝛾$ : alors $\sum\limits_{ i ≤n } 𝛼_i = \sum\limits_{ i ≤n } 𝛾_i$ et $𝛼 \preccurlyeq_{lex} 𝛾$ (par transitivité de $\preccurlyeq_{lex}$), d’où $𝛼 \preccurlyeq_{grlex} 𝛾$

    il vient que $𝛼 \preccurlyeq_{grlex} 𝛾$.

Montrons que $\preccurlyeq_{grlex}$ est monomial :

  1. $\preccurlyeq_{grlex}$ est total :

    Pour tous $𝛼, 𝛽 ∈ ℕ^n$ :

    • Cas 1 : $\sum\limits_{ i ≤n } 𝛼_i < \sum\limits_{ i ≤n } 𝛽_i$

      alors \(𝛼 \preccurlyeq_{grlex} 𝛽\)

    • Cas 2 : $\sum\limits_{ i ≤n } 𝛽_i < \sum\limits_{ i ≤n } 𝛼_i$

      alors \(𝛽 \preccurlyeq_{grlex} 𝛼\)

    • Cas 3 : $\sum\limits_{ i ≤n } 𝛼_i = \sum\limits_{ i ≤n } 𝛽_i$

      alors comme $\preccurlyeq_{lex}$ est total : \(𝛼 \preccurlyeq_{lex} 𝛽 \text{, d'où } 𝛼 \preccurlyeq_{grlex} 𝛽 \qquad\text{ OU } \qquad 𝛽 \preccurlyeq_{lex} 𝛼 \text{, d'où } 𝛽 \preccurlyeq_{grlex} 𝛼\)

  2. Soient $𝛼, 𝛽, 𝛾 ∈ ℕ^n$ tels que $𝛼 \preccurlyeq_{grlex} 𝛽$. Montrons que

    \[𝛼 + 𝛾 \preccurlyeq_{grlex} 𝛽 + 𝛾\]

    • Si $\sum\limits_{ i ≤n } 𝛼_i < \sum\limits_{ i ≤n } 𝛽_i$ :

      alors $\sum\limits_{ i ≤n } 𝛼_i + 𝛾_i < \sum\limits_{ i ≤n } 𝛽_i+ 𝛾_i$, et \(𝛼+𝛾 \preccurlyeq_{grlex} 𝛽+𝛾\)

    • Si $\sum\limits_{ i ≤n } 𝛼_i = \sum\limits_{ i ≤n } 𝛽_i$ et $𝛼 \preccurlyeq_{lex} 𝛽$ :

      alors $\sum\limits_{ i ≤n } 𝛼_i + 𝛾_i = \sum\limits_{ i ≤n } 𝛽_i+ 𝛾_i$ et $𝛼+𝛾 \preccurlyeq_{lex} 𝛽+𝛾$ (par monomialité de $\preccurlyeq_{lex}$), d’où \(𝛼 + 𝛾 \preccurlyeq_{grlex} 𝛽+𝛾\)

  3. $\preccurlyeq_{grlex}$ est bien fondé :

    Par l’absurde, supposons qu’il existe une suite $(𝛼^{(i)})_{i∈ℕ}$ strictement décroissante pour $\preccurlyeq_{grlex}$.

    Alors pour tout $i∈ℕ$ :

    • $\sum\limits_{ i ≤n } 𝛼^{(i+1)}_j < \sum\limits_{ i ≤n } 𝛼^{(i)}_j$

    ou

    • $\sum\limits_{ i ≤n } 𝛼^{(i+1)}_j = \sum\limits_{ i ≤n } 𝛼^{(i)}_j$ et $𝛼^{(i+1)} \preccurlyeq_{lex} 𝛼^{(i)}$

    Donc par le principe des tiroirs :

    • \[E ≝ \left\lbrace i∈ℕ \; \middle\vert \; \sum\limits_{ i ≤n } 𝛼^{(i+1)}_j < \sum\limits_{ i ≤n } 𝛼^{(i)}_j \right\rbrace \text{ est infini}\]

    ou

    • \[F ≝ \left\lbrace i∈ℕ \; \middle\vert \; \sum\limits_{ i ≤n } 𝛼^{(i+1)}_j = \sum\limits_{ i ≤n } 𝛼^{(i)}_j \text{ et } 𝛼^{(i+1)} \preccurlyeq_{lex} 𝛼^{(i)} \right\rbrace \text{ est infini}\]

    ⟶ Si $E$ (resp. $F$) est infini, alors la stricte décroissance pour $<$ (resp. $\preccurlyeq_{lex}$) de la suite $\left(\sum\limits_{ i ≤n } 𝛼^{(i)}_j\right)_{i∈E} ∈ℕ^E$ (resp. $( 𝛼^{(i)})_{i∈F} ∈ (ℕ^n)^F$ ) contredit le caractère bien fondé de $<$ (resp. $\preccurlyeq_{lex}$).

    Dans tous les cas, on obtient une contradiction.

4.

Soit $(𝛼^{(k)})_{k∈ℕ}∈(ℕ^n)^ℕ$ une suite infinie.

Montrons par récurrence sur $n∈ℕ$ qu’on peut extraire une sous-suite infinie $(𝛼^{(m_k)})_{k∈ℕ}∈(ℕ^n)^ℕ$ telle que pour tout $k∈ℕ$,

\[𝛼^{(m_k)} ≤ 𝛼^{(m_{k+1})}\]

  • Initialisation : Pour $n=1$ :

    Par l’absurde : supposons que ce ne soit pas le cas : aucune sous-suite de $(𝛼^{(k)})_{k∈ℕ}$ n’est croissante.

    On pose alors :

    • $m_0 ≝ 0$

    • pour tout $i∈ℕ$, l’ensemble

      \[E_{m_i} ≝ \lbrace k > m_i \; \mid \; 𝛼^{(k)} < 𝛼^{(m_i)} \rbrace\]

      est non vide, car sinon la sous-suite $(𝛼^{(k)})_{k>m_i}$ est croissante.

      On note alors $m_{i+1}$ l’un de ses éléments (on utilise ici l’axiome du choix).

      Il vient que $𝛼^{(m_{i+1})} < 𝛼^{(m_i)}$.

    On a construit une suite infinie strictement décroissante, ce qui contredit le caractère bien fondé de $≤$ sur $ℕ$.

  • Hérédité : Pour $n>1$ :

    De la même manière que dans l’initialisation, on montre qu’on peut extraire une suite croissante infinie $(𝛼^{(𝜑(k))}_n)_{k∈ℕ}$ de $(𝛼^{(k)}_n)_{k∈ℕ}∈ℕ^ℕ$.

    De plus, l’hypothèse de récurrence fournit une sous-suite infinie

    \[\Big((𝛼^{(𝜓(k))}_1, \ldots, 𝛼^{(𝜓(k))}_{n-1}) \Big)_{k∈ℕ}\]

    de $\Big((𝛼^{(k)}_1, \ldots, 𝛼^{(k)}_{n-1}) \Big)_{k∈ℕ}∈(ℕ^{(n-1)})^ℕ$.

    On vérifie alors aisément que la sous-suite infinie

    \[\Big((𝛼^{\big((𝜑 \circ 𝜓) (k)\big)}_1, \ldots, 𝛼^{\big((𝜑 \circ 𝜓) (k)\big)}_n) \Big)_{k∈ℕ}∈(ℕ^n)^ℕ\]

    de $(𝛼^{(k)})_{k∈ℕ}$ est croissante (par stricte croissance des extractrices $𝜑$ et $𝜓$), ce qui conclut.

On a montré que :

Si $(𝛼^{(k)})_{k∈ℕ}∈(ℕ^n)^ℕ$ est une suite infinie, on peut en extraire une sous-suite infinie croissante.

5.

a). $<$ est bien fondé sur $ℕ^n$

Montrons que $<$ est bien fondé sur $ℕ^n$.

Par l’absurde : supposons qu’il existe une suite $(𝛼^{(i)})_{i∈ℕ} ∈ (ℕ^n)^ℕ$ strictement décroissante.

Alors comme pour tout $i∈ℕ$,

\[𝛼^{(i+1)} ≤ 𝛼^{(i)} \text{ et } 𝛼^{(i+1)} ≠ 𝛼^{(i)}\]

i.e

\[\begin{cases} ∀k∈⟦1, n⟧, \; 𝛼^{(i+1)}_k ≤ 𝛼^{(i)}_k \\ ∃k∈⟦1, n⟧; \; 𝛼^{(i+1)}_k ≠ 𝛼^{(i)}_k \end{cases}\]

il existe $k_i ∈ ⟦1, n⟧$ tel que

\[𝛼^{(i+1)}_{k_i} < 𝛼^{(i)}_{k_i}\]

c’est-à-dire (comme $(𝛼^{(i)})_{i∈ℕ}$ est décroissante) :

\[∀i' > i,\; \quad 𝛼^{(i')}_{k_i} < 𝛼^{(i)}_{k_i}\]

Donc comme $(k_i)_{i∈ℕ}$ est à valeurs dans l’ensemble fini $⟦1, n⟧$, il existe (par le principe des tiroirs) $j∈⟦1, n⟧$ tel que :

\[K_j ≝ \lbrace i∈ℕ \mid k_i = j \rbrace\]

est infini.

La suite infinie $(𝛼^{(i)}_j)_{i∈K_j}$ à valeurs dans $ℕ$ est alors strictement décroissante, puisque :

\[∀i < i' ∈K_j, \; 𝛼^{(i')}_j ≤ 𝛼^{(i+1)}_j = 𝛼^{(i+1)}_{k_i} < 𝛼^{(i)}_{k_i} = 𝛼^{(i)}_j\]

ce qui contredit le caractère bien fondé de $<$ dans $ℕ$.

b). Si $F⊆ℕ^n$, l’ensemble des éléments minimaux de $F$ est fini

Par l’absurde : supposons qu’il existe une suite infinie $(f^{(i)})_{i∈ℕ} ∈ F^ℕ$ d’éléments minimaux distincts de $F⊆ℕ^n$.

On va construire une suite $(g^{(i)})_{i∈ℕ^\ast} ∈ (ℕ^n)^ℕ$ strictement décroissante.

On pose

  • \[g^{(0)} ≝ f^{(0)}\]

  • pour tout $i∈ℕ$,

    \[f^{(i+1)} \text{ est minimal }⟹ g^{(i)} \not< f^{(i+1)} ⟹ \begin{cases} ∃k∈⟦1, n⟧, \; g^{(i)}_k > f^{(i+1)}_k \\ \text{ ou } \\ ∀k∈⟦1, n⟧; \; g^{(i)}_k = f^{(i+1)}_k &&\text{(i.e } g^{(i)} = f^{(i+1)} \text{ )} \end{cases}\]

    d’où :

    • Si $g^{(i)} ≠ f^{(i+1)}$ :

      alors

      \[∃k∈⟦1, n⟧, \; f^{(i+1)}_{k} < g^{(i)}_{k}\]

      et en posant :

      \[ℕ^n \ni g^{(i+1)} ≝ \big(f^{(i+1)}_{k}, \ldots, f^{(i+1)}_{k} \big)\]

      il vient, si $i≥1$, que :

      \[g^{(i+1)} < g^{(i)}\]

    • Sinon si $g^{(i)} = f^{(i+1)}$ :

      alors comme $f^{(i+2)} ≠ f^{(i+1)} = g^{(i)}$ et $f^{(i+2)}$ est minimal :

      \[g^{(i)} \not< f^{(i+2)} ⟹ ∃k∈⟦1, n⟧, \; f^{(i+2)}_{k} < g^{(i)}_{k}\]

      et en posant :

      \[ℕ^n \ni g^{(i+1)} ≝ \big(f^{(i+2)}_{k}, \ldots, f^{(i+2)}_{k} \big)\]

      il vient, si $i≥1$, que :

      \[g^{(i+1)} < g^{(i)}\]

Donc on construit une suite

\[(g^{(i)})_{i∈ℕ^\ast} ∈ (ℕ^n)^ℕ\]

strictement décroissante, ce qui contredit le caractère bien fondé de $ℕ^n$.

c). Tout suite $(F_k)_{k∈ℕ}$ croissante d’ensembles clos supérieurement stationne.

Soit $(F_k)_{k∈ℕ}$ une suite croissante d’ensembles clos supérieurement.

Si tous les $F_k$ sont vides, le résultat est immédiat.

Sinon : on supposera dans la suite que les $F_k$ sont non vides, sans perte de généralité (quitte à considérer $(F_k){k>k_0}$ pour le plus petit indice $k_0$ tel que $F{k_0} ≠ ∅$).

Pour tout $k∈ℕ$ : l’ensemble des éléments minimaux de $F_k$ est fini (d’après le point b)) et non vide (d’après la question 1, puisque les $F_k$ sont non vides) : on le note : $\min F_k$.

D’après la question 1 :

\[\bigcup\limits_{f^\ast∈ \min F_k}\big\lbrace f \mid f ≥ f^\ast \big\rbrace = F_k \qquad ⊛\]

  • en effet :

    • $\bigcup\limits_{f^\ast∈ \min F_k}\big\lbrace f \mid f ≥ f^\ast \big\rbrace ⊆ F_k$ car $F_k$ est clos supérieurement
    • pour tout $f∈F_k$, il existe, d’après la question 1, un $f^\ast_0 ∈ \min F_k$ tel que
    \[f ∈ \big\lbrace f' \mid f' ≥ f^\ast_0 \big\rbrace ⊆ \bigcup\limits_{f^\ast∈ \min F_k}\big\lbrace f \mid f ≥ f^\ast \big\rbrace\]

Par l’absurde : supposons que la suite croissante $(F_k)_{k∈ℕ}$ ne soit pas stationnaire, c'est-à-dire qu'il existe une sous-suite infinie $(F_{k_i})_{i∈ℕ}$ strictement croissante.

On va construire une suite $(f^\ast_i)_{i∈ℕ} ∈ (ℕ^n)^ℕ$ dont on ne peut pas extraire de sous-suite infinie croissante (ce qui contredira la question 4).

  • On note $f^\ast_0$ un élément de $\min F_{k_0} ≠ ∅$.

  • Soit $i∈ℕ$, et supposons qu’on ait défini $f^\ast_0, \ldots, f^\ast_i$.

    Comme $F_{k_i} ⊊ F_{k_{i+1}}$, $\min F_{k_{i+1}} \backslash \min F_{k_i}$ est non vide

    • en effet : d’après $⊛$, si $\min F_{k_{i+1}} ⊆ \min F_{k_i}$, alors on aurait $F_{k_{i+1}} ⊆ F_{k_i}$

    : on note $f^\ast_{i+1}$ un de ses éléments.

On vérifie ainsi que pour tout $i∈ℕ$,

\[∀j>i, f^\ast_i \not ≤ f^\ast_j\]

  • en effet : s’il existait $j>i$ tel que $f^\ast_i ≤ f^\ast_j$ alors on aurait

    \[f^\ast_j ∈ \big\lbrace f \mid f ≥ f^\ast_i \big\rbrace ⊆ \bigcup\limits_{f^\ast∈ \min F_{k_i}}\big\lbrace f \mid f ≥ f^\ast \big\rbrace = F_{k_i}\]

    ce qui est impossible puisque $f^\ast_j ∈ F_{k_j} \backslash \, \underbrace{F_{k_{j-1}}}_{\rlap{\supseteq F_{k_i} \text{ car } j-1≥i}} ⊆ F_{k_j} \backslash F_{k_i}$

On ne peut donc extraire de sous-suite croissante infinie de $(f^\ast_i)_{i∈ℕ}$, ce qui contredit la question 4.

On a donc montré que la suite croissante $(F_k)_{k∈ℕ}$ stationne, c’est-à-dire qu’il existe $k_0 ∈ ℕ$ tel que

\[F_{k_0} = \bigcup_{k∈ℕ} F_k\]

II. Division de polynômes multivariables

6.

\[x_1 + x_2 = x_2 (x_1 x_2 + 1) - x_1 (x_2^2 - 1) ∈ ⟨x_1 x_2 + 1, x_2^2 - 1⟩\]

7.

Supposons que $x^α \vert x^β$, et montrons que $α \preccurlyeq β$.

Si $𝛼 = 𝛽$ : le résultat est immédiat, par réflexivité.

Sinon :

  • $∀i∈⟦1,n⟧, 𝛼_i ≤ 𝛽_i$ (car $x^α \mid x^β$)

  • et $∃j∈⟦1,n⟧, 𝛼_j < 𝛽_j$ (car $𝛼 ≠ 𝛽$)

d’où le fait qu’il existe $𝛾 ≝ (𝛽_i - 𝛼_i)_{i∈⟦1,n⟧}∈ℕ^n \backslash \mathbf{0}$ tel que :

\[𝛽 = 𝛼 + 𝛾\]

Or, d’après la question 2 :

\[\mathbf{0} ≺ 𝛾\]

et comme l’ordre est monomial :

\[𝛼 = \mathbf{0} + 𝛼 ≺ 𝛾 + 𝛼 = 𝛽\]

ce qui conclut.

On a montré que :

Si $x^α\vert x^β$, alors $α ≺ β$.

8.

Terminaison

Montrons qu’à chaque tour de boucle, $mdeg(h)$ diminue strictement pour l’ordre monomial $\preccurlyeq$.

En effet :

  • $mdeg(h − lt(h)) \prec mdeg(h)$ par définition de $lt(h)$

  • $mdeg\Big(h − \frac{lt(h)}{lt(f_i)} f_i\Big) \prec mdeg(h)$ car la partie entière de la fraction rationnelle $\frac{f_i}{lt(f_i)}$ vaut $1$ (par définition de $lt(f_i)$), d’où $lt\Big(\frac{lt(h)}{lt(f_i)} f_i\Big) = lt(h)$, et les monômes de $h − \frac{lt(h)}{lt(f_i)} f_i$ sont d’exposant strictement inférieur (pour $\preccurlyeq$) à l’exposant de $lt(h)$ (qui vaut $mdeg(h)$).

Or, l’ordre $\preccurlyeq$ est bien fondé (en tant qu’ordre monomial), donc la boucle ne peut pas être infinie, et

l’algorithme termine.

Correction

Montrons que

  1. le résultat de l’algorithme vérifie $g = \sum\limits_{ i ≤k } q_i f_i + r$ et pour tout $i≤k$ et tout monôme $x^α$ de $r$, $mdeg(f_i) \not ≤ α$

  2. $\max_{i≤k}(mdeg(f_i q_i)) = mdeg(g − r)$ pour l’ordre $≺$

1.

Montrons l’invariant :

$I_j$ : après la $j$-ème itération de la boucle principale (while h≠0 do ⋯ end) :

  • \[g-h = \sum\limits_{ i ≤k } q_i f_i + r \quad ⊛\]
  • pour tout $i≤k$ et tout monôme $x^α$ de $r$, $mdeg(f_i) \not ≤ α \quad ⊛⊛$

Par récurrence sur $j∈ℕ$ :

  • Pour $j=0$ : au début de l’algorithme, $h = g$, $r = 0$, et tous les $q_i$ sont égaux à $0$, donc $I_0 ⊛$ est bien vérifié, et $I_0 ⊛⊛$ aussi (puisque $r$ ne contient pas de monôme).

  • Pour $j>0$ : supposons que l’invariant est vérifié au début du $j$-ième tour de boucle, et montrons qu’il le reste à la sortie.

    • Cas 1 : $∀i∈⟦1, n⟧, \; lm(f_i)\not\mid \, lm(h)$ :

      donc $encore$ vaut encore $true$ à l’issue de la boucle interne while i ≤ n and encore do ⋯ end et à la fin de la $j$-ième boucle, on a effectué :

      \[r ← r + lt(h) ; \; h ← h − lt(h)\]

      les autres polynômes étant restés inchangés.

      Alors en posant $h’ ≝ h − lt(h)$ et $r’ ≝ r + lt(h)$ :

      \[\begin{align*} g-h' & = g-h + lt(h) \\ & = \sum\limits_{ i ≤k } q_i f_i + r + lt(h) &&\text{(par } I_j \text{ )}\\ & = \sum\limits_{ i ≤k } q_i f_i + r' \end{align*}\]

      et $I_{j+1}⊛$ reste vérifié.

      Par ailleurs, comme $I_{j}⊛⊛$ est vrai, il suffit de montrer que :

      \[∀i≤k, mdeg(f_i) \not ≤ mdeg(h)\]

      pour vérifier $I_{j+1}⊛⊛$, puisque $x^{mdeg(h)}$ est le seul nouveau monôme ajouté à $r$.

      Or :

      \[x^𝛼 \vert x^𝛽 ⟺ 𝛼 ≤ 𝛽\]

      (les deux implications sont immédiates)

      Pour vérifier $I_{j+1}⊛⊛$, il suffit donc montrer que :

      \[∀i≤k, lm(f_i) = x^{mdeg(f_i)} \not\mid x^{mdeg(h)} = lm(h)\]

      ce qui est exactement l’hypothèse faite : le résultat est donc acquis.

    • Cas 2 : $∃i∈⟦1, n⟧, \; lm(f_i) \mid \, lm(h)$ :

      donc $encore$ se voit attribuer la valeur $false$ après la boucle interne while i ≤ n and encore do ⋯ end et à la fin de la $j$-ième boucle, on a effectué :

      \[q_i ← q_i+\frac{lt(h)}{lt(f_i)}; \; h ← h−\frac{lt(h)}{lt(f_i)}f_i\]

      les autres polynômes étant restés inchangés.

      Alors en posant $h’ ≝ h−\frac{lt(h)}{lt(f_i)}f_i$ et $q’_i ≝ q_i+\frac{lt(h)}{lt(f_i)}$ :

      \[\begin{align*} g-h' & = g-h + \frac{lt(h)}{lt(f_i)}f_i \\ & = \sum\limits_{ l ≤k } q_l f_l + r + \frac{lt(h)}{lt(f_i)}f_i &&\text{(par } I_j \text{ )}\\ & = \sum\limits_{ \substack{l ≤k \\ l ≠ i}} q_l f_l + r + q_i f_i + \frac{lt(h)}{lt(f_i)}f_i \\ & = \sum\limits_{ \substack{l ≤k \\ l ≠ i}} q_l f_l + r + q'_i f_i \end{align*}\]

      Donc $I_{j+1} ⊛$ est vrai.

      Par ailleurs, comme aucun monôme n’est ajouté à $r$, $I_{j+1} ⊛⊛$ reste vérfié.

    Dans tous les cas, le résultat est acquis.

À la sortie de la dernière boucle, $h=0$, donc l’invariant fournit le résultat escompté.

2.

Pour tout $j$, on notera $r^{(j)}, h^{(j)}, q_i^{(j)}$ (pour $i∈⟦1,k⟧$) la valeur des variables correspondantes à la fin de la $j$-ème itération ($r^{(0)}, h^{(0)}, q_i^{(0)}$ étant leur valeur initiale).

Comme l’algorithme termine, les suites $(r^{(j)})_j, (h^{(j)})_j, (q_i^{(j)})_j$ (pour $i∈⟦1,k⟧$) sont de même cardinal fini : en notant $N$ le numéro de la dernière itération ($N=0$ si on n’entre pas la boucle principale), elles sont de cardinal $N+1$.

Dans la preuve de terminaison, on a montré que

$(mdeg(h^{(j)}))_{0≤j≤N}$ est strictement décroissante pour l’ordre bien fondé $\preccurlyeq$.

On note $j_0$ le nombre d’itérations de la boucle principale while h≠0 do ⋯ end avant que $encore$ se voie attribuer la valeur $false$ pour la première fois ($j_0 = 0$ si $encore$ est mis à $false$ dès la première itération).

Alors :

  • au début de la $(j_0+1)$-ème itération,

    \[h^{(j_0)} = g - r^{(j_0)} \text{ et } ∀i∈⟦1, k⟧, q^{(j_0)}_i = 0\]

    • en effet : au cours des $j_0$ premières itérations, comme $encore$ vaut $true$, on n’effectue que :

      \[r ← r + lt(h) ; \; h ← h − lt(h)\]

      à chaque tour de boucle (les autres polynômes, donc en particulier les $q_i$, restant inchangés).

      Par conséquent, les invariants $g = h + r$ et $∀i, q_i = 0$ sont vérifiés (les $q_i$ sont initialisés à $0$) au cours des $j_0$ premières itérations (même si $j_0=0$, puisqu’alors $h =g, r=0$ et $∀i, q_i = 0$).

  • à la fin de la $(j_0+1)$-ème itération : comme $encore$ s’est vu attribuer la valeur $false$, on a effectué :

    \[q_{i_0} ← q_{i_0} +\frac{lt(h)}{lt(f_{i_0})}; \; h ← h−\frac{lt(h)}{lt(f_{i_0})}f_{i_0}\]

    les autres polynômes étant restés inchangés.

    Il vient, d’après le point précédent, que :

    \[\begin{cases} h^{(j_0+1)} & = \overbrace{g - r^{(j_0)}}^{h^{(j_0)}} - \frac{lt(h^{(j_0)})}{lt(f_{i_0})}f_{i_0} \\ \\ q^{(j_0+1)}_{i_0} & = q^{(j_0)}_{i_0} + \frac{lt(h^{(j_0)})}{lt(f_{i_0})} \\ & = \frac{lt(h^{(j_0)})}{lt(f_{i_0})} \\ \\ ∀i∈⟦1, k⟧\backslash \lbrace i_0 \rbrace, q^{(j_0+1)}_i &= q^{(j_0)}_i \\ & = 0 \end{cases}\]

    De plus :

    \[lt\big(q^{(j_0+1)}_{i_0} f_{i_0}\big) = lt\bigg(\frac{lt(h^{(j_0)})}{lt(f_{i_0})} f_{i_0}\bigg) \overset{⊛}{=} lt(h^{(j_0)}) = lt\big(g - r^{(j_0)}\big) \quad ⊛⊛\]

    (on a montré l’égalité $⊛$ dans la preuve de terminaison)

Montrons que

Lemme : $∀j>j_0$,

\[\begin{cases} \max_{1≤i≤k} mdeg\Big(q^{(j)}_{i} f_{i}\Big) = mdeg\Big(lt\big(q^{(j_0+1)}_{i_0} f_{i_0}\big)\Big) \\ lt\big(g - r^{(j)}\big) = lt\big(g - r^{(j_0)}\big) \end{cases}\]

Il suffit de montrer que les seuls termes que l’on peut ajouter (ou soustraire : au sens algébrique), à chaque itération, aux $q^{(j)}_{i} f_{i}$ (resp. $g - r^{(j)}$) sont d'exposants strictement inférieurs (pour $\preccurlyeq$) à celui de $lt\big(q^{(j_0+1)}_{i_0} f_{i_0}\big)$ (resp. $lt\big(g - r^{(j_0)}\big)$).

Or, l’exposant de $lt\big(q^{(j_0+1)}_{i_0} f_{i_0}\big) = lt\big(g - r^{(j_0)}\big) = lt(h^{(j_0)})$ vaut $mdeg(h^{(j_0)})$, et pour $j> j_0$, le seul terme possiblement ajouté (ou soustrait) aux polynômes précédents au cours de la $j$-ième itération est

\[lt(h^{(j)}) = lt\bigg(\frac{lt(h^{(j)})}{lt(f_{j})} f_{j}\bigg)\]

(on a montré cette égalité dans la preuve de terminaison)

dont l’exposant est

\[mdeg(h^{(j)}) \prec mdeg(h^{(j_0)})\]

par stricte décroissance de $(mdeg(h^{(j’)}))_{j’}$.

Le résultat est donc acquis.

Par conséquent, à la fin de l’algorithme :

  • Si $N=j_0$ :

    Le résultat s’ensuit immédiatement puisqu’on a montré dans le premier point que :

    \[h = h^{(N)} = g - r^{(N)} = g - r = 0\]

    puisque $g = \sum\limits_{ i ≤k } q_i f_i + r = r$, et

    \[∀i∈⟦1, k⟧, \, q_i = q^{(N)}_i = 0\]

  • Si $N>j_0$ :

    \[\begin{align*} \max_{i≤k}(mdeg(f_i q_i)) & = \max_{i≤k}(mdeg(f^{(N)}_i q^{(N)}_i)) \\ & = mdeg\Big(lt\big(q^{(j_0+1)}_{i_0} f_{i_0}\big)\Big) &&\text{ (lemme) } \\ & = mdeg\Big(lt\big(g - r^{(j_0)}\big)\Big) &&\text{ (par } ⊛⊛ \text{)}\\ & = mdeg\Big(lt\big(g - r^{(N)}\big)\Big) &&\text{ (lemme) } \\ & = mdeg\Big(lt\big(g - r\big)\Big) \\ & = mdeg(g − r) \end{align*}\]

    ce qui conclut.

9.

On pose

  • $g ≝ x_1 x_2 + x_2 x_3$
  • $f_1 ≝ x_1 + x_3$
  • $f_2 ≝ x_1$

Division de $g$ par $(f_1, f_2)$ :

  $encore$ $h$ $q_1$ $q_2$ $r$
Initialisation   $x_1 x_2 + x_2 x_3$ $0$ $0$ $0$
Fin de la 1ère itération \(\underbrace{lm(f_1)}_{= x_1} \mid \underbrace{lm(h)}_{= x_1 x_2} \\ ⟶ false\) \(x_1 x_2 + x_2 x_3 - x_1 x_2 (1 + \frac{x_3}{x_1}) \\ = 0\) $0 + \frac{x_1 x_2}{x_1} = x_2$ $0$ $\boxed{\, \vphantom{\mid} 0 \;}$

Division de $g$ par $(f_2, f_1)$ :

  $encore$ $h$ $q_1$ $q_2$ $r$
Initialisation   $x_1 x_2 + x_2 x_3$ $0$ $0$ $0$
Fin de la 1ère itération \(\underbrace{lm(f_2)}_{= x_1} \mid \underbrace{lm(h)}_{= x_1 x_2} \\ ⟶ false\) \(x_1 x_2 + x_2 x_3 - x_1 x_2 \\ = x_2 x_3\) $0 + \frac{x_1 x_2}{x_1} = x_2$ $0$ $0$
Fin de la 2ème itération \(\underbrace{lm(f_2) = lm(f_1)}_{= x_1} \not\mid \underbrace{lm(h)}_{= x_2 x_3} \\ ⟶ true\) \(x_2 x_3 - x_2 x_3 = 0\) $x_2$ $0$ \(0 + x_2 x_3 \\ = \boxed{\, \vphantom{\mid} x_2 x_3 \;}\)

Donc

le reste de la division de $g$ par $(f_1, f_2)$ (qui vaut $0$) est différent du reste de la division de $g$ par $(f_2, f_1)$ (qui vaut $x_2 x_3$).

10.

Si le reste de la division de $g$ par $(f_1, \ldots , f_k)$ est nul, alors d’après la question 8 :

\[g = \sum\limits_{ i ≤k } q_i f_i + \underbrace{r}_{= 0} \\ = \sum\limits_{ i ≤k } q_i f_i ∈ ⟨f_1, \ldots, f_k⟩\]

Mais la réciproque n’est pas vraie : en reprenant l’exemple de la question 9 :

\[g = x_2 (x_1 + x_3) ∈ ⟨f_2, f_2⟩\]

mais le reste de la division de $g$ par $(f_2, f_1)$ n’est pas nul (il vaut $x_2 x_3$).

On a donc montré que :

Si le reste de la division de $g$ par $(f_1, \ldots , f_k)$ est nul, alors $g ∈ ⟨f_1 , \ldots , f_k⟩$ mais que l’inverse n’est pas nécessairement vrai.

11.

On suppose que $f_1, \ldots , f_k$ sont des monômes, et que $g ≝ \sum\limits_{ i ≤k } q’_i f_i ∈ ⟨f_1, \ldots ,f_k⟩$.

Par l’absurde : supposons que le reste $r$ de la division de $g$ par $(f_1, \ldots, f_k)$ n’est pas nul.

Avec les notations de la question 8 :

\[g = \sum\limits_{ i ≤k } q_i f_i + r \\ ⟹ r = \sum\limits_{ i ≤k } (q'_i - q_i) f_i\]

Soit $c \, x^𝛼$ un terme non nul ($c≠0$) de $r$ (il en existe un puisque $r≠0$).

Comme $c \, x^𝛼$ apparaît dans la some de droite, il existe $i≤k$ tel que l’un des termes $c’ \, x^𝛽 f_i$ de $(q’_i - q_i) f_i$ vaut $c \, x^𝛼$.

Donc comme $c≠0$ et $ℚ$ est un corps (donc $c$ y est inversible):

\[f_i \mid \underbrace{x^𝛼}_{ = \frac{c'}{c} x^𝛽 f_i}\]

donc l’exposant de $f_i$ est inférieur (dans $ℕ^n$, pour $≤$) à $𝛼$, ce qui contredit le fait que :

pour tout $j≤k$ et tout monôme $x^{𝛼’}$ de $r$, $mdeg(f_j) \not ≤ α’$ (démontré à la question 8).

On a donc montré que

Si $f_1, \ldots , f_k$ sont des monômes, et $g ∈ ⟨f_1, \ldots ,f_k⟩$, le reste de la division de $g$ par $(f_1, \ldots, f_k)$ est nul.

III. Une première caractérisation d’une base

12.

Supposons que ${\cal F}$ est une base.

Montrons que $⟨lm({\cal F})⟩ = ⟨lm(⟨{\cal F}⟩)⟩$.

L’inclusion $⟨lm({\cal F})⟩ ⊆ ⟨lm(⟨{\cal F}⟩)⟩$ est toujours vraie, puisque

\[\begin{align*} & {\cal F} ⊆ ⟨{\cal F}⟩ \\ ⟹ \quad& lm({\cal F}) ⊆ lm(⟨{\cal F}⟩) ⊆ ⟨lm(⟨{\cal F}⟩)⟩ \\ ⟹ \quad& lm({\cal F}) ⊆ ⟨lm(⟨{\cal F}⟩)⟩ \\ ⟹ \quad& ⟨lm({\cal F})⟩ ⊆ ⟨lm(⟨{\cal F}⟩)⟩ \\ \end{align*}\]

la dernière implication venant du fait que $⟨lm({\cal F})⟩$ est le plus petit idéal contenant $lm({\cal F})$ et $⟨lm(⟨{\cal F}⟩)⟩$ est un idéal.

Montrons que $⟨lm(⟨{\cal F}⟩)⟩ ⊆ ⟨lm({\cal F})⟩$.

Il suffira de montrer que $lm(⟨{\cal F}⟩) ⊆ ⟨lm({\cal F})⟩$, par minimalité de $⟨lm(⟨{\cal F}⟩)⟩$.

Soit $x^𝛼 ≝ lm(g) ∈ lm(⟨{\cal F}⟩)$, où $g ∈ ⟨{\cal F}⟩$. Montrons que $x^𝛼 ∈ ⟨lm({\cal F})⟩$.

Comme $g∈⟨{\cal F}⟩$, en divisant $g$ par la base ${\cal F}$, $g$ s’écrit, d’après la question 8 :

\[g = \sum\limits_{ i ≤ k } q_i f_i + \underbrace{0}_{ {\cal F} \text{ est une base}}\]

et

\[𝛼 = mdeg(g) = \max_{i≤k}(mdeg(f_i q_i))\]

Donc il existe $i_0∈⟦1, k⟧$ tel que

\[𝛼 = mdeg(f_{i_0} q_{i_0})\]

Or, par monomialité de $\prec$, $lm(f_{i_0} q_{i_0}) = lm(f_{i_0}) lm(q_{i_0})$, où $x^𝛾$ est un monôme de $q_{i_0}$.

  • en effet : en posant $𝛼_0 ≝ mdeg(f_{i_0})$ : pour tout monôme

    \[\underbrace{x^𝛽}_{\text{monôme de } f_{i_0}} \overbrace{x^𝛾}^{\text{monôme de } q_{i_0}}\]

    de $f_{i_0} q_{i_0}$, l’exposant de $x^𝛽 x^𝛾$ est inférieur à celui de $lm(f_{i_0}) x^𝛾$, puisque :

    \[𝛽 \prec 𝛼_0 ⟹ \underbrace{𝛽 + 𝛾}_{\text{exposant de } x^𝛽 x^𝛾} \prec \overbrace{𝛼_0 + 𝛾}^{\text{exposant de } lm(f_{i_0}) x^𝛾}\]

    Donc le monôme de tête de $f_{i_0} q_{i_0}$ est nécessairement de la forme $lm(f_{i_0}) x^𝛾$, où $x^𝛾$ est un monôme de $q_{i_0}$.

    Puis, par symétrie, on montre que $𝛾 = mdeg(q_{i_0})$.

Par suite, en posant $𝛾 ≝ mdeg(q_{i_0}$ :

\[𝛼 = mdeg(lm(f_{i_0}) x^𝛾) = mdeg(f_{i_0}) + 𝛾\]

et

\[mdeg(f_{i_0}) ≤ 𝛼\]

d’où

\[lm(f_{i_0}) = x^{mdeg(f_{i_0})} \mid x^𝛼\]

et

\[x^𝛼 ∈ ⟨lm(f_{i_0})⟩ ⊆ ⟨lm({\cal F})⟩\]

ce qui conclut.

On a donc montré que

Si ${\cal F}$ est une base, alors

\[⟨lm({\cal F})⟩ = ⟨lm(⟨{\cal F}⟩)⟩\]

13.

Supposons que $⟨lm(F)⟩ = ⟨lm(⟨F⟩)⟩$.

Par l’absurde : Soit $g ≝ \sum\limits_{ i ≤ k } q’_i f_i ∈ ⟨F⟩$ tel que $r$ le reste de la division par ${\cal F}$ soit non nul.

En divisant $g$ par ${\cal F}$, $g$ s’écrit, d’après la question 8 :

\[g = \sum\limits_{ i ≤ k } q_i f_i + r \\ ⟹ r = \sum\limits_{ i ≤ k } (q'_i - q_i) f_i \quad ⊛\]

et pour tout monôme $x^α$ de $r$ :

  • $∀i∈⟦1, k⟧, \quad mdeg(f_i) \not ≤ α$
  • i.e $∀i∈⟦1, k⟧, \quad lm(f_i) \not\mid x^𝛼$
  • i.e le reste de la division de $x^𝛼$ par $(lm(f_i))_{1≤i≤k}$ vaut $x^𝛼$ et n’est donc pas nul (l’algorithme de division finit après une itération de la boucle principale).
  • i.e $x^𝛼 ∉ ⟨(lm(f_i))_{1≤i≤k}⟩ = ⟨lm({\cal F})⟩$ (d’après la contraposée de la question 11)

Par suite, en appliquant ce qui précède au monôme $lm(r)$ (qui existe puisque $r$ est non nul) :

\[lm(r) ∉ ⟨lm({\cal F})⟩\]

Mais comme $r ∈ ⟨{\cal F}⟩$ (par $⊛$) :

\[lm(r) ∈ lm(⟨{\cal F}⟩) ⊆ ⟨lm(⟨{\cal F}⟩)⟩\]

Donc

\[∅ ≠ ⟨lm(⟨{\cal F}⟩)⟩ \backslash ⟨lm({\cal F})⟩ \ni lm(r)\]

ce qui est absurde, du fait de l’hypothèse $⟨lm(F)⟩ = ⟨lm(⟨F⟩)⟩$.

On a donc montré que

Si $⟨lm(F)⟩ = ⟨lm(⟨F⟩)⟩$, alors ${\cal F}$ est une base.

IV. Une caractérisation plus effective

14.

\[S(x_1 x_2 + 1, x_2^2-1) = x_1 x_2^2 \bigg(1+ \frac{1}{x_1 x_2} - \Big(1 - \frac{1}{x_2^2}\Big )\bigg) = x_2 + x_1\]

15.

Si ${\cal F}$ est une base : alors pour tous $f_i, f_j ∈ {\cal F}$,

\[S(f_i,f_j) ≝ x^{lcm(mdeg(f_i),mdeg(f_j))}\Big(\frac{f_i}{lt(f_i)} − \frac{f_j}{lt(f_j)}\Big) ∈ ⟨f_i, f_j⟩ ⊆ ⟨{\cal F}⟩\]

en vérifiant aisément que $\frac{x^{lcm(mdeg(f_i),mdeg(f_j))}}{lt(f_i)}$ (resp. $\frac{x^{lcm(mdeg(f_i),mdeg(f_j))}}{lt(f_j)}$) est un polynôme, car l’exposant $mdeg(f_i)$ (resp. $mdeg(f_j)$) de $lt(f_i)$ (resp. $lt(f_j)$) est inférieur (pour $≤$) à l’exposant $lcm(mdeg(f_i),mdeg(f_j))$ de $x^{lcm(mdeg(f_i),mdeg(f_j))}$.

Et comme $S(f_i,f_j)∈⟨{\cal F}⟩$, le reste de la division de $S(f_i,f_j)$ par ${\cal F}$ est nul (car ${\cal F}$ est une base, par définition).

On a montré que :

Si ${\cal F}$ est une base, alors pour tous $f_i, f_j ∈ {\cal F}$, le reste de la division de $S(f_i,f_j)$ par ${\cal F}$ est nul.

16.

Supposons, par l’absurde, qu’il existe au plus un indice $i$ tel que $mdeg(f_i q_i) = \max_{l≤k}(mdeg(f_l q_l))$.

Comme il en existe au moins un (puisque la famille sur lequel le $\max$ est pris est $(mdeg(f_l q_l))_{l≤k}$, et l'ordre $\prec$ est total (en tant qu'ordre monomial)), il existe exactement un indice $i$ tel que $mdeg(f_i q_i) = \max_{l≤k}(mdeg(f_l q_l))$.

Mais alors

\[mdeg\bigg( \sum\limits_{ \substack{l≤k \\ l≠i} } f_l q_l \bigg) \preceq \max\limits_{ \substack{l≤k \\ l≠i} } (mdeg(f_l q_l)) \prec mdeg(f_i q_i)\]

d’où :

\[lm\bigg( \sum\limits_{l≤k} f_l q_l \bigg) = lm(f_i q_i)\]

et

\[mdeg(g) = mdeg\bigg( \sum\limits_{l≤k} f_l q_l \bigg) = mdeg(f_i q_i) = \max_{l≤k}(mdeg(f_l q_l))\]

ce qui contredit l’hypothèse

\[mdeg(g) \prec \max_{l≤k}(mdeg(f_l q_l))\]

On a donc montré que :

il existe au moins deux indices $i, j$ tels que

\[mdeg(f_j q_j) = mdeg(f_i q_i) = \max_{l≤k}(mdeg(f_l q_l))\]

17.

En divisant $S(f_i, f_j)$ par ${\cal F}$, $S(f_i, f_j)$ s’écrit, d’après la question 8 :

\[S(f_i, f_j) = \sum\limits_{ l ≤ k } f_l h_l + \underbrace{0}_{\text{ le reste est nul par hypothèse}}\]

avec

\[\max_{l≤k}(mdeg(f_l h_l)) = mdeg(S(f_i, f_j)) \quad ⊛\]

Par suite :

\[\begin{align*} S(f_i,f_j) & ≝ x^{lcm(mdeg(f_i),mdeg(f_j))}\Big(\frac{f_i}{lt(f_i)} − \frac{f_j}{lt(f_j)}\Big) \\ & = x^{lcm(mdeg(f_i),mdeg(f_j))}\Big(\frac{f_i}{lm(f_i)} − \frac{f_j}{lm(f_j)}\Big) && \text{(puisque } lc(f_j) = lc(f_i) = 1 \text{)}\\ \end{align*}\]

Or : les parties entières des fractions rationnelles $\frac{f_i}{lm(f_i)}$ et $\frac{f_j}{lm(f_j)}$ sont égales (elles valent $1$), donc la fraction rationnelle $\frac{f_i}{lm(f_i)} − \frac{f_j}{lm(f_j)}$ n’est somme que de parties polaires de degrés strictement négatifs.

Par conséquent, $S(f_i, f_j)$ est une somme (algébrique) de termes dont les exposants des monômes sont strictement inférieurs (pour $\prec$) à l’exposant $lcm(mdeg(f_i),mdeg(f_j))$ du terme $x^{lcm(mdeg(f_i),mdeg(f_j))}$ en facteur de $\frac{f_i}{lm(f_i)} - \frac{f_j}{lm(f_j)}$.

De fait,

\[mdeg(S(f_i, f_j)) = mdeg\Big(\frac{f_i}{lc(f_i)} − \frac{f_j}{lc(f_j)}\Big) \prec lcm(mdeg(f_i), mdeg(f_j))\]

et par $⊛$ :

\[∀l∈⟦1,k⟧, \quad mdeg(f_l h_l) \preceq mdeg(S(f_i, f_j)) \prec lcm(mdeg(f_i), mdeg(f_j))\]

d’où, finalement :

\[∀l∈⟦1,k⟧, \quad mdeg(f_l h_l) \prec lcm(mdeg(f_i), mdeg(f_j))\]

On a montré que

$S(f_i, f_j) = \sum\limits_{ l ≤ k } f_l h_l$ avec pour tout $l$, $mdeg(f_l h_l) \prec lcm(mdeg(f_i), mdeg(f_j))$

18.

Soit $t = \frac{lt(f_i q_i)}{x^{lcm(mdeg(f_i ),mdeg(f_j ))}}$

  • $q’_i = q_i − lt(q_i) + th_i$
  • $q’_j = q_j + lc(q_i)lm(q_j) + th_j$
  • $q’_l = q_l + th_l$ pour tout $l∉ \lbrace i, j \rbrace$

Montrons que $g = \sum\limits_{ l≤k } f_l q’_l$

\[\begin{align*} \sum\limits_{ l≤k } f_l q'_l & = f_i \big(q_i − lt(q_i) + th_i\big) + f_j \big(q_j + lc(q_i)lm(q_j) + th_j\big) + \sum\limits_{ \substack{l≤k \\ l ∉ \lbrace i, j \rbrace}} f_l (q_l + th_l)\\ & = − f_i lt(q_i) + f_i th_i + f_j lc(q_i)lm(q_j) + f_j th_j + \underbrace{\sum\limits_{ l≤k} f_l q_l }_{= g}+ \sum\limits_{ \substack{l≤k \\ l ∉ \lbrace i, j \rbrace}} f_l th_l\\ & = g − f_i lt(q_i) + f_j lc(q_i)lm(q_j) + t \overbrace{\sum\limits_{l≤k} f_l h_l}^{= S(f_i, f_j)} \\ & = g − f_i lt(q_i) + f_j lc(q_i)lm(q_j) + t x^{lcm(mdeg(f_i),mdeg(f_j))}\Big(\frac{f_i}{lt(f_i)} − \frac{f_j}{lt(f_j)}\Big) \\ & = g − f_i lt(q_i) + f_j lc(q_i)lm(q_j) + lt(f_i q_i) \Big(\frac{f_i}{lt(f_i)} − \frac{f_j}{lt(f_j)}\Big) \quad ⊛ \end{align*}\]

Or, on montre, de la même manière qu’à la question 12 (au milieu de la démonstration) que, comme l’ordre $\prec$ est monomial : le monôme de tête de $f_i q_i$ est le produit des monômes de tête de $f_i$ et de $q_i$, et partant :

\[lt(f_i q_i) = lt(f_i) lt(q_i)\]

Donc

\[− f_i lt(q_i) + lt(f_i q_i) \frac{f_i}{lt(f_i)} = − f_i lt(q_i) + lt(q_i) f_i = 0 \quad ⊛⊛\]

Par ailleurs,

\[\begin{align*} & f_j lc(q_i)lm(q_j) - lt(f_i q_i)\frac{f_j}{lt(f_j)} = 0 \\ ⟸ \quad & lt(f_i q_i) = lc(q_i)lm(q_j) lt(f_j)\\ ⟺ \quad & lc(f_i) lm(f_i) lc(q_i) lm(q_i) = lc(q_i)lm(q_j) lc(f_j) lm(f_j) \\ ⟸ \quad & lc(f_i) \underbrace{lm(f_i) lm(q_i)}_{ = lm(f_i q_i) = lm(f_j q_j)} = lc(f_j) \underbrace{lm(q_j) lm(f_j)}_{= lm(f_j q_j) = lm(f_i q_i)} \\ ⟸ \quad & lc(f_i) = lc(f_j) \end{align*}\]

la dernière égalité étant vérifiée, puisque $lc(f_i) = lc(f_j) = 1$.

Donc

\[f_j lc(q_i)lm(q_j) - lt(f_i q_i)\frac{f_j}{lt(f_j)} = 0 \quad ⊛⊛⊛\]

D’après $⊛$, $⊛⊛$ et $⊛⊛⊛$, il vient que :

\[g = \sum\limits_{ l≤k } f_l q'_l\]

Cette représentation contredit la minimalité de la représentation originelle

Montrons que le multi-ensemble associé à cette représentation est strictement inférieur au multi-ensemble associé à la représentation originelle.

En effet :

Pour tout $l$,

\[\begin{align*} mdeg(t f_l h_l) & = mdeg(t) + mdeg( f_l h_l) &&\text{(puisque le monôme de tête du produit} \\ & &&\text{est le produit des monômes de tête)}\\ & = \underbrace{mdeg(f_i q_i)}_{= \max_{l≤k}(lm(f_l q_l))} - lcm(mdeg(f_i ),mdeg(f_j )) + mdeg(f_l h_l)\\ & \prec \max_{l≤k}(mdeg(f_l q_l)) - lcm(mdeg(f_i ),mdeg(f_j )) + lcm(mdeg(f_i ),mdeg(f_j )) && \text{(question 17)}\\ & = \max_{l≤k}(mdeg(f_l q_l)) \end{align*}\]

Donc, comme $mdeg(t f_l h_l) \prec \max_{l≤k}(lm(f_l q_l))$, l’ajout des $t h_l$ ne fait pas augmenter le multidegré des $q’_l f_l$ dans cette représentation.

De plus,

\[q_j + lc(q_i)lm(q_j)\]

a un multidegré inférieur ou égal à celui de $q_j$, donc

\[mdeg(q'_j f_j) \preceq mdeg(q_j f_j) = \max_{l≤k}(mdeg(f_l q_l))\]

Enfin :

\[q_i − lt(q_i)\]

a un multidegré strictement inférieur à celui de $q_i$, donc

\[mdeg(q'_i f_i) \prec mdeg(q_i f_i) = \max_{l≤k}(mdeg(f_l q_l))\]

et la multiplicité du degré maximal $\max_{l≤k}(mdeg(f_l q_l)) = mdeg(q_i f_i) = mdeg(q_i f_i)$ des $q’_l f_l$ dans le multi-ensemble associé à cette représentation a diminué strictement par rapport à celle de la représentation originelle, ce qui, d’après la définition de l’ordre sur les multi-ensembles rappelée dans l’énoncé, implique que

le multi-ensemble associé à cette représentation est strictement inférieur au multi-ensemble associé à la représentation originelle

ce qui est absurde, par minimalité de la représentation originelle.

Conclusion :

Il vient donc que

\[mdeg(g) = max_{i≤k}(mdeg(f_i q_i))\]

comme cette propriété est vérifiée pour tous les $g∈⟨{\cal F}⟩$, on peut montrer avec la même démonstration que celle de la question 12 que :

\[⟨lm({\cal F})⟩ = ⟨lm(⟨{\cal F}⟩)⟩\]

ce qui, d’après la question 13, est suffisant pour établir que tous les polynômes de $⟨{\cal F}⟩$ ont un reste nul dans la division par ${\cal F}$, c’est-à-dire que ${\cal F}$ (qui est fini) est une base.

On a donc montré que :

Si, pour tous $f_i, f_j ∈ {\cal F}$ (fini), le reste de la division de $S(f_i,f_j)$ par ${\cal F}$ est nul, alors ${\cal F}$ est une base.

V. Calcul d’une base

19.

Terminaison

Méthode 1 :

À chaque itération de la boucle principale, l’idéal engendré par les monômes de tête de $G$ croît strictement (hormis à la dernière itération de la boucle principale, lorsque $new = ∅$), puisque $new$ est constitué de restes non nuls $r_j$ de divisions par $G$ : ce qui implique, d’après la question 8, que pour tout $j$, aucun monôme de tête d’un polynôme de $G$ ne divise $r_j$.

Donc $lm(r_j) ∉ ⟨lm(G)⟩$ (comme on l’a rappelé à la question 13 (d’après la contraposée de la question 11)), et l’idéal engendré par $lm(G ∪ \underbrace{new}_{= \lbrace r_j \rbrace_j})$ est strictement plus grand que l’idéal engendré par $lm(G)$ dans $ℚ[x_1, \ldots, x_n]$.

Or, comme on l’a vu dans le cours d’algèbre : $ℚ[x_1, \ldots, x_n]$ est un anneau noethérien : toute suite croissante d’idéaux y stationne.

Donc la suite précédente ne peut pas croître strictement indéfiniment, et l’algorithme termine (puisque $⟨lm(G∪ new)⟩ = ⟨lm(G)⟩$ n’est possible que si $new =∅$ (l’algorithme s’arrête alors), car si $new≠∅$, les éléments de $lm(new)$ n’appartiennent pas à $⟨lm(G)⟩$).

Méthode 2 (trouvée après) :

Si on appelle “partie engendrée par $𝛼∈ℕ^n$” la partie $⟨𝛼⟩ ≝ \lbrace 𝛽∈ℕ^n \mid 𝛽 ≥ 𝛼\rbrace$, on peut reprendre l’argument précédent en considérant les parties engendrées par les exposants des monômes de tête de $G$ à chaque itération : elles sont closes supérieurement (par définition), et elles ne peuvent pas croître indéfiniment par la question 5.

L’argument est analogue à la méthode précédente, en utilisant l’équivalence

\[x^𝛼 \mid x^𝛽 ⟺ 𝛼 ≤ 𝛽\]

À chaque itération de la boucle principale, la partie engendrée par les exposants des monômes de tête de $G$ croît strictement (hormis à la dernière itération de la boucle principale, lorsque $new = ∅$), puisque $new$ est constitué de restes non nuls $r_j$ de divisions par $G$ vérifiant $lm(r_j) ∉ ⟨lm(G)⟩$, donc $exposant(lm(r_j)) ∉ ⟨exposant(lm(G))⟩$.

Correction

À la dernière itération de la boucle principale, $new = ∅$, ce qui signifie qu’on n’a trouvé aucune paire $\lbrace f, g \rbrace ⊆ G$ telle que le reste de la division de $S(f, g)$ par $G$ ne soit pas nul.

En d’autres termes : à la fin de l’algorithme, pour tous $f, g∈ G$, le reste de la division de $S(f, g)$ par $G$ est nul, ce qui implique, d’après la conclusion de la question 18, que

$G$ est une base de $⟨G⟩$.

Or, $G$ est initialisé à $\lbrace f_1, \ldots, f_k\rbrace$, et à chaque itération de la boucle principale, l’invariant

\[⟨G⟩ = ⟨f_1, \ldots, f_k⟩\]

est conservé.

  • en effet, chaque reste $r$ d’une division Divise(S(f, g), G) appartient à l’idéal engendré par $G$, puisque, $S(f, g)∈⟨G⟩$ (montré à la question 15) et d’après la question 8 :

    \[r = \underbrace{S(f, g)}_{∈⟨G⟩} - \underbrace{\sum\limits_{ g'_l∈G } q'_l g'_l}_{∈⟨G⟩} ∈⟨G⟩\]

    donc à la fin de chaque boucle :

    \[⟨G⟩ = ⟨G ∪ new⟩\]

On en conclut donc qu’à la fin de l’algorithme :

$⟨G⟩ = ⟨f_1, \ldots, f_k⟩$

En récapitulant tout :

À la fin de l’algorithme, $G$ est une base de $⟨G⟩ = ⟨f_1, \ldots, f_k⟩$.

20.

Construction d’une base de $⟨x_1 x_2 + 1, x^2_2 − 1⟩$ :

  $new$ $G$ paires de polynômes de $G$ $S(f,g)$ $Divise(S(f,g), G)$
Initialisation   $\lbrace x_1 x_2 + 1, x^2_2 − 1 \rbrace$ $\lbrace x_1 x_2 + 1, x^2_2 − 1 \rbrace$    
Fin de la 1ère itération $\lbrace x_1 + x_2 \rbrace$ $\lbrace x_1 + x_2, x_1 x_2 + 1, x^2_2 − 1 \rbrace$ \(\lbrace x_1 x_2 + 1, x^2_2 − 1 \rbrace \\ \lbrace x_1 + x_2, x_1 x_2 + 1 \rbrace \\ \lbrace x_1 + x_2, x^2_2 − 1 \rbrace\) \(S(x_1 x_2 + 1, x^2_2 − 1) = x_1 + x_2\) $x_1 + x_2$
Fin de la 2ème itération $∅$ $\lbrace x_1 + x_2, x_1 x_2 + 1, x^2_2 − 1 \rbrace$ \(\lbrace x_1 x_2 + 1, x^2_2 − 1 \rbrace \\ \lbrace x_1 x_2 + 1, x_1 + x_2 \rbrace \\ \lbrace x^2_2 − 1, x_1 + x_2 \rbrace\) \(S(x_1 x_2 + 1, x^2_2 − 1) = x_1 + x_2 \\ S(x_1 + x_2, x_1 x_2 + 1) = x_2^2 - 1 \\ S(x_1 + x_2, x^2_2 − 1, ) = x_1 + x_2^3\) \(0 \\ 0 \\ 0\)

Sortie :

\[G = \lbrace x_1 + x_2, x_1 x_2 + 1, x^2_2 − 1 \rbrace\]

Leave a comment