Good-node deletion and cogood-node addition operators

The stack algorithm computes the normal form. The stack algorithm of [F3] terminates with a word containing no $-$ before a $+$ (a surviving $-$ stays on the stack and blocks the stack from being empty, so no later $+$ survives after it), and the reduction relation is confluent by [F3], so the surviving signs read in order are the reduced signature with zero entries deleted, ${+}^a{-}^b$; in particular the good node corresponds to the first surviving $-$ and the cogood node to the last surviving $+$.

Comparison of the $i$-words. Let $\mu$ be $p$-restricted and $X$ a removable $i$-node of $\mu$; put $\nu :=\mu \setminus X$. By [F2] the $i$-nodes of $\nu$ are obtained from those of $\mu$ by removing $X$ from the removable list and inserting $X$ into the addable list, all other $i$-nodes and their top-to-bottom order being unchanged; hence the $i$-signature words of $\mu$ and $\nu$ have the same length and the same entries except at the position $p$ of $X$, where the word of $\mu$ has $-$ and the word of $\nu$ has $+$.

First surviving $-$ versus last surviving $+$. Let $w$ be a signature word with $w_p=-$, let $w^{\mathrm{\prime }}$ be $w$ with the entry at $p$ changed to $+$, let $u$ be the prefix of $w$ strictly before $p$, and let $s$ be the suffix strictly after $p$. We prove that $p$ is the position of the first surviving $-$ of $w$ if and only if $p$ is the position of the last surviving $+$ of $w^{\mathrm{\prime }}$. Let $S$ be the stack of [F3] after scanning $u$; the prefix of $w^{\mathrm{\prime }}$ before $p$ is the same word $u$, so the same stack $S$ is present there. If $S$ is nonempty, let $q$ be its bottom entry; scanning $w$ further, $q$ can leave the stack only by being cancelled by a $+$ that has first cancelled every entry above it, in particular the entry at $p$, so either $q$ survives, giving a surviving $-$ before $p$, or the entry $p$ is cancelled before $q$ and does not survive; in both cases $p$ is not the first surviving $-$ of $w$. Similarly, scanning $w^{\mathrm{\prime }}$ the entry at $p$ is a $+$, which survives only if the stack just before it is empty, so if $S$ is nonempty then $p$ does not survive and is not the last surviving $+$ of $w^{\mathrm{\prime }}$. Hence both events force $S$ to be empty, and we may assume this. With $S$ empty, push the $-$ at $p$ in the scan of $w$; while this entry is alive, the pending entries above it after scanning a prefix $q$ of $s$ are the $-$ signs of $q$ not yet cancelled, and since no $+$ has yet occurred at height $0$, that number is $\mathrm{\#}-(q)-\mathrm{\#}+(q)$. Consequently $p$ is cancelled at the first $+$ of $s$ whose preceding prefix $q$ has $\mathrm{\#}+(q)=\mathrm{\#}-(q)$, and such a $+$ exists if and only if some prefix $q$ of $s$ has $\mathrm{\#}+(q)>\mathrm{\#}-(q)$: counts change by one at each symbol, so a strict surplus arises only across a step of equality, and conversely a prefix with equality followed by a $+$ would create a strict surplus. Thus, with $S$ empty, the entry at $p$ survives in $w$ if and only if $(C)\mathrm{\#}+(q)\le \mathrm{\#}-(q)\text{for every prefix }q\text{ of }s\mathrm{.}$ In $w^{\mathrm{\prime }}$, the $+$ at $p$ arrives at the empty stack $S$ and survives; after it, a later $+$ of $s$ survives exactly when the stack is empty at its arrival. If (C) holds and a $+$ of $s$ survived, with preceding prefix $q$, then all $-$ of $q$ were cancelled, so $\mathrm{\#}-(q)\le \mathrm{\#}+(q)$, while (C) applied to the prefix $q$ extended by that $+$ gives $\mathrm{\#}+(q)+1\le \mathrm{\#}-(q)$, a contradiction; hence no later $+$ survives. Conversely, if (C) fails then some $+$ of $s$ survives: the stack height after a prefix $q$ of $s$ equals $\mathrm{\#}-(q)-\mathrm{\#}+(q)+c(q)$, where $c(q)$ is the number of $+$ signs of $q$ that survived, as one checks by induction on the length of $q$ (a $-$ raises the height, and a $+$ raises $c$ by one and lowers the height by one exactly when it cancels); if no $+$ of $s$ survived then $c(q)=0$ for every prefix $q$, so $\mathrm{\#}+(q)\le \mathrm{\#}-(q)$ for every prefix, contradicting the failure of (C). Therefore (C) holds if and only if, in $w^{\mathrm{\prime }}$, the entry at $p$ is the last surviving $+$, and the claim follows.

Good versus cogood for a removable node. Let $\mu$ be $p$-restricted, $X$ a removable $i$-node of $\mu$ and $\nu =\mu \setminus X$, assumed $p$-restricted. By step 1.2 the words of $\mu$ and $\nu$ differ exactly by the flip at the position of $X$, so step 2.1 gives: $X$ is the good $i$-node of $\mu$ if and only if $X$ is the cogood $i$-node of $\nu$. Consequently, if ${\epsilon }_i(\mu )>0$ and $X$ is the good $i$-node, then ${\phi }_i(\nu )>0$ with cogood node $X$, and ${\tilde{f}}_i(\nu )=\nu \cup X=\mu$.

Removing the good node preserves restrictedness. Let $\mu$ be $p$-restricted and let $A=(r,{\mu }_r)$ be its good $i$-node; we show that $\nu =\mu \setminus A$ is $p$-restricted. If $r\ge 2$ and ${\mu }_{r-1}-{\mu }_r=p-1$, then $B:=(r-1,{\mu }_{r-1})$ is a removable node of $\mu$ (as ${\mu }_{r-1}>{\mu }_r$) with $\mathrm{res}(B)={\mu }_{r-1}-(r-1)={\mu }_r-r+p\equiv {\mu }_r-r=\mathrm{res}(A)$, so $B$ is a removable $i$-node above $A$ and hence occurs before $A$ in the $i$-word. There is no $i$-node between $B$ and $A$: these are consecutive rows, and any addable node in either row has residue $i+1$. Thus $B$ is still on the stack when $A$ is pushed. Either some $-$ before $A$ survives, and then $A$ is not the first surviving $-$, or every $-$ before $A$ is eventually cancelled, in particular $B$; but a $+$ cancels $B$ only after cancelling every entry pushed after $B$, in particular the entry at $A$, so in that case $A$ is cancelled and does not survive; both alternatives contradict that $A$ is good. Hence ${\mu }_{r-1}-{\mu }_r\le p-2$, and then $\nu$ is $p$-restricted: deleting the last node of row $r$ leaves $({\mu }_r-1)-{\mu }_{r+1}\le p-2<p$ and, if $r\ge 2$, ${\mu }_{r-1}-({\mu }_r-1)=({\mu }_{r-1}-{\mu }_r)+1\le p-1<p$, while all other consecutive differences are unchanged.

Adding the cogood node preserves restrictedness. Let $\mu$ be $p$-restricted and let $B=(r,{\mu }_r+1)$ be its cogood $i$-node; we show that $\nu =\mu \cup B$ is $p$-restricted. Suppose first that ${\mu }_r-{\mu }_{r+1}=p-1$; then $D:=(r+1,{\mu }_{r+1}+1)$ is an addable $i$-node of $\mu$, because ${\mu }_r>{\mu }_{r+1}$ and $\mathrm{res}(D)={\mu }_{r+1}-r\equiv {\mu }_r+1-r=\mathrm{res}(B)$; between $B$ and $D$ in the top-to-bottom order there is no $i$-node: the entries after $B$ in row $r$ do not exist, and the remaining $i$-node of row $r$ is the removable node $(r,{\mu }_r)$, whose residue is $\mathrm{res}(B)-1$, while the addable node of row $r+1$ is $D$ itself. Hence $B$ and $D$ are consecutive in the $i$-word, both with sign $+$. If the $+$ at $B$ survives, it leaves the stack empty, so the next entry, the $+$ at $D$, also survives and is later than $B$; if the $+$ at $B$ does not survive, then $B$ is not the cogood node. In both cases $B$ is not the last surviving $+$, contradicting that $B$ is cogood. Hence ${\mu }_r-{\mu }_{r+1}\le p-2$, and then $({\mu }_r+1)-{\mu }_{r+1}\le p-1<p$, while ${\mu }_{r-1}-({\mu }_r+1)=({\mu }_{r-1}-{\mu }_r)-1<p$ for $r\ge 2$ (no row above change is needed when $r=1$), and all other differences are unchanged; so $\nu$ is $p$-restricted.

Good versus cogood for an addable node. Let $Y$ be the cogood $i$-node of the $p$-restricted partition $\mu$ and $\nu :=\mu \cup Y$. Step 3.3 makes $\nu$ $p$-restricted, so step 3.1 applies. The node $Y$ is removable in $\nu$, and $\mu =\nu \setminus Y$; applying step 3.1 to the pair $(\nu ,Y)$ gives: $Y$ is the good $i$-node of $\nu$ if and only if $Y$ is the cogood $i$-node of $\mu$. Consequently, if ${\phi }_i(\mu )>0$ and $Y$ is the cogood $i$-node, then ${\epsilon }_i(\nu )>0$ with good node $Y$, and ${\tilde{e}}_i(\nu )=\nu \setminus Y=\mu$.

The inverse property. Let $\mu ,\nu$ be $p$-restricted partitions. If $\nu ={\tilde{e}}_i\mu$, then ${\epsilon }_i(\mu )>0$, $\nu =\mu \setminus A$ for the good $i$-node $A$ of $\mu$, and step 3.1 gives that $A$ is the cogood $i$-node of $\nu$, so that ${\tilde{f}}_i\nu =\nu \cup A=\mu$. Conversely, if $\mu ={\tilde{f}}_i\nu$, then ${\phi }_i(\nu )>0$, $\mu =\nu \cup B$ for the cogood $i$-node $B$ of $\nu$, and step 4.1 gives that $B$ is the good $i$-node of $\mu$, so that ${\tilde{e}}_i\mu =\mu \setminus B=\nu$. Hence $\mu ={\tilde{f}}_i\nu ⟺\nu ={\tilde{e}}_i\mu$ for all $p$-restricted $\mu ,\nu$, both sides being false when the relevant node does not exist; and by steps 3.2 and 3.3 the operators map $p$-restricted partitions to $p$-restricted partitions.

Conclusion. By [F1] at most one good and at most one cogood $i$-node exist in each residue, so the partial operators are well defined; removing a node lowers the rank by one and adding a node raises it by one, so ${\tilde{e}}_i$ lowers and ${\tilde{f}}_i$ raises the rank by one; and by step 5.1 each operator is defined at exactly the images of the other, so they are mutual inverses on their domains. No module theory and no choice principle are used.