Confusion on "Lyndon Words, Free Algebras, and Shuffles"

Question

There's a passage from the paper "Lyndon Words, Free Algebras, and Shuffles" by Guy Melancon and Christophe Reutenauer (which can be found here) that's causing me some confusion.

Here, $A$ is some alphabet, $A^*$ is the free monoid of words from that alphabet, and $\mathbb{Z}\langle \rangle$ is the algebra of polynomials with $A^*$ as its basis. From page 582:

Note that the dual space of $\mathbb{Z}\langle A\rangle$ is naturally isomorphic to the set $\mathbb{Z}\ll A\gg$ of all formal series. Each formal series is an infinite linear combination of words. The duality

$\mathbb{Z}\ll A\gg\times \mathbb{Z}\langle A\rangle\to\mathbb{Z}$

$(S,P)\to(S,P)$

is defined by

$(S,P)=\sum_{w\in A^*}(S,w)(P,w)$

where $(S,w)$ denotes the coefficient of $w$ in $S$.

What confuses me is understanding what $P$ is. It looks like $P$ should be an element of $\mathbb{Z}\langle A\rangle$, meaning it's a word, but the notation $(P,w)$ suggests it should be a series. I also don't understand how this relates to the duality between $\mathbb{Z}\langle A\rangle$ and $\mathbb{Z}\ll A\gg$. Am I misunderstanding something, or is there possibly a typo in the paper?

Answer 1

This doesn't have much to do with the particular situation of "Lyndon Words, Free Algebras, and Shuffles". Rather you have an infinite set $A^*$ and you take the free abelian group $G = \mathbb Z A^*$ (in your notation $\mathbb Z\langle A \rangle$) with formal basis $A^*$. You can think of this rather as the (abelian group) of finitely supported functions on $A^*$ with values in $\mathbb Z$, with pointwise addition. A group homomorphism ($\mathbb Z$--module homomorphism) from $G$ to $\mathbb Z$ is determined by its values on the basis elements, and these values can be prescribed arbitrarily; thus a group homomorphism is specified by an arbitrary function from $A^*$ to $\mathbb Z$. The pairing between $f \in G$, given by a finitely supported function, and $h$ in the dual $G'$, given by an arbitrary function, is $\langle f, h \rangle = \sum_{x \in A^*} f(x) h(x)$, the sum being finite since $f$ is finitely supported.

The authors just chose to describe an arbitrary function from $A^*$ to $\mathbb Z$ as a formal infinite linear combination of the basis elements, thus a function $h$ is described as $\sum_{x \in A^*} h(x) x$. So for them, the pairing given above is $$ \left\langle \sum_{x \in A^*}f(x) x, \sum_{x \in A^*}h(x) x \right\rangle = \sum_{x \in A^*} f(x) h(x). $$

The algebra structure on $G$ plays no role here, only the abelian group structure.

Note: there were 2 questions here and I only addressed the second. But J.E Pin explained the first question.

Answer 2

First of all, you didn't quote properly the paper. The notation is $\mathbb{Z}\langle A \rangle$, not $\mathbb{Z}(A)$. Secondly, this denotes the set of polynomials with noncommutative variables in $A$. Thus $P$ is a polynomial and not a word and $(P,w)$ is the coefficient of $P$ in $w$. For instance, if $P = -2a + bab - abaab$, then $(P, bab) = 1$ and $(P, b) = 0$.