Exercise 9, § 4

On uses the notations of the preceding exercise. We put on $\mathscr{M}$ the lexicographic order. Let $l \in \mathbf{N}$. A subset A of $\mathscr{M}_l$ is said to be initial if, for every $m \in A$, the set

is contained in A. (a) Let $l \in \mathbf{N}$ (resp. $l \in \mathbf{N} - \{0\}$) and $A \subset \mathscr{M}_l$ be an initial subset. Now prove that $\delta A$ (resp. $dA$) is an initial subset of $\mathscr{M}_{l+1}$ (resp. $\mathscr{M}_{l-1}$). Suppose that A possesses a greatest element $m = X_1^{a_1} ... X_n^{a_n}$. Determine the greatest element of $\delta A$ (resp. $dA$). (b) Let $l \in \mathbf{N} - \{0\}$ and $A \subset \mathscr{M}_l$ be a finite nonempty initial subset. Let $X_{a_l}$ be the largest variable such that $[X_{a_l}^l] \subset A$. Now prove that every $m$ in $A - [X_{a_l}^l]$ is equal to 1 or divisible by $X_{a_l+1}$ and that $A' = \{ m \in \mathscr{M}_{l-1} | m X_{a_l+1} \in A - [X_{a_l}^l] \}$ is an initial subset of $\mathscr{M}_{l-1}$. Deduce from what precedes an expression of $\mathrm{Card}([X_1^{b_1} ... X_n^{b_n}])$. (c) Deduce from what precedes that, for every $l \in \mathbf{N} - \{0\}$ and every finite initial subset A of $\mathscr{M}_l$, one has $\mathrm{Card}(\delta A) = \partial_l(\mathrm{Card}(A))$, where $\partial_l$ was defined in the preceding exercise. Calculate in an analogous manner $\mathrm{Card}(dA)$. (d) For every $l \in \mathbf{N}$ and every $n \in \mathbf{N}$, put and denote by $m_n$ the n-th monomial of $\mathscr{M}_l$ for the lexicographic order (one will put $m_0 = 1$).

For every finite subset A of $\mathscr{M}_l$, denote by $CA$ the initial subset of $\mathscr{M}_l$ such that $\mathrm{Card}(A) = \mathrm{Card}(CA)$. Now prove that the following three assertions are equivalent: (MC1) for every $l \in \mathbf{N}$ and every $A \subset \mathscr{M}_l$, one has $C\delta A \subset \delta CA$; (MC2) for every $l \in \mathbf{N}$ and every $A \subset \mathscr{M}_l$, one has $dCA \subset CdA$; (MC3) for every $l \in \mathbf{N}$ and every $n \in \mathbf{N}$, one has $\mathrm{Card}(d[m_n]) = \mu(n)$.