Exercise 11, § 4

It is proposed to prove the assertions MC1, MC2, MC3 of Exercise 9, d) (Macaulay theorem). Let $l \in \mathbf{N}$, $A \subset \mathscr{M}_l$, and $p$ the smallest integer such that $A \subset [X_p^l]$. We shall prove MC2 by induction on $p$. a) Prove the theorem for $p = 1$ and $p = 2$. b) Using the induction hypothesis, now prove that for every $i \leq p$, $dC_iA \subset C_idA$ (notations of Exercise 8). c) Set $A^1 = A, A^{j+1} = C_iA^j$ where $i \equiv j \mod p$ and $1 \leq i \leq p$. Prove that for $j$ sufficiently large one has $A^{j+1} = A^j$. (For every $a \in \mathscr{M}_l$, denote by $n(a) \in \mathbf{N}$ the rank of $a$ for the lexicographic order and set $n(A) = \sum_{a \in A} n(a)$. Prove that $n(A^{j+1}) \leq n(A^j)$ and that $n(A^{j+1}) = n(A^j)$ if and only if $A^{j+1} = A^j$.) d) Prove the theorem in the general case. (A subset $A \subset [X_p^l] \subset \mathscr{M}_l$ is said to be minimal if $\mathrm{Card}(dA) \leq \mathrm{Card}(dA')$ for subsets $A' \subset [X_p^l]$ such that $\mathrm{Card}(A') = \mathrm{Card}(A)$. It is a question of showing that if $A$ is minimal, $CA$ is minimal. Let $A$ be minimal. Using b), show that $C_iA$ is minimal for every $i \leq p$. Deduce, using the notations of c), that $A^j$ is minimal for every $j$. Deduce according to c) that there exists a minimal $B$ such that $\mathrm{Card}(B) = \mathrm{Card}(A)$ and $C_iB = B$ for $1 \leq i \leq p$. In the case $p = 3$, use Exercise 10, c) to conclude. In the case $p \geq 4$, use Exercise 10, b) to deduce that $B = CA^1$.)

1 For generalizations and complements concerning this exercise, one may consult G. F. Clements and B. Lindström, A Generalization of a Combinatorial Theorem of Macaulay, J. of Combinatorial Theory 7 (1969), p. 230-238.