A list of errata in the paper "A bijection between words and multisets of necklaces" by I. Gessel, A. Restivo, and C. Reutenauer ( http://people.brandeis.edu/~gessel/homepage/papers/necklace.pdf )
- page 1: "is hat the" -> "is that the".
- page 2: "rows.Then" -> "rows. Then".
- page 3: The 8-step proof of the bijectivity of $\Phi$ is somewhat
broken. First of all, the "$\tau^i()$" in step 6 should be
"$\tau^i(q)$". But more importantly, step 4 doesn't work as stated: we
have $w_p^{\infty} \leq w_q^{\infty}$ rather than $w_p^{\infty} <
w_q^{\infty}$ (there is no reason why a strict inequality should hold;
we're in a multiset), and it's not a-priori clear that this uniquely
determines the ordering of the $w_1, w_2, \ldots, w_n$ because the
relation "$u^{\infty} \leq v^{\infty}$" between two words $u$ and $v$
is not a partial order (but merely a pre-order).
Here is how I would fix this: The 8 steps need to be read in a
different order. First read steps 1, 2, 3, 6 and 7 (the "$\tau^i()$"
in step 6 should be "$\tau^i(q)$"). Then, read step 4 with the
following caveat: you don't have $w_p^\infty < w_q^\infty$, but only
$w_p^\infty \leq w_q^\infty$. As I said, the relation $u^\infty \leq
v^\infty$ between two words $u$ and $v$ is not a partial order (just a
total pre-order), so we cannot conclude from this that the $p$-th row
of the tableau is $w_p$. However, $w_p$ and $w_q$ are primitive (as
proven in step 7), and the relation $u^\infty \leq v^\infty$ between
two *primitive* words $u$ and $v$ is a partial order (this isn't hard
to check; it follows from the fact that two primitive words $u$ and
$v$ satisfying $u^n = v^m$ for positive $n$ and $m$ must necessarily
be equal). So we can conclude the claim of step 4 after all. Finally
read steps 5 and 8.
Note that this error persists in the published version of the paper (
https://doi.org/10.1016/j.ejc.2012.03.016 ).
- page 4: "witht" -> "with".
- page 4: "the define the inverse" -> "define the inverse".