Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $k$ be a commutative ring with $1$, and let $V$ be a $k$-module. Let $TV$ be the $k$-module $\bigoplus\limits_{n\in\mathbb N}V^{\otimes n}$, where all tensor products are over $k$.

We define a $k$-linear map $\mathrm{shf}:\left(TV\right)\otimes\left(TV\right)\to TV$ by

$\mathrm{shf}\left(\left(a_1\otimes a_2\otimes ...\otimes a_i\right)\otimes\left(a_{i+1}\otimes a_{i+2}\otimes ...\otimes a_n\right)\right)$

$= \sum\limits_{\sigma\in\mathrm{Sh}\left(i,n-i\right)} a_{\sigma^{-1}\left(1\right)} \otimes a_{\sigma^{-1}\left(2\right)} \otimes ... \otimes a_{\sigma^{-1}\left(n\right)}$

for every $n\in \mathbb N$ and $a_1,a_2,...,a_n\in V$. Here, $\mathrm{Sh}\left(i,n-i\right)$ denotes the set of all $\left(i,n-i\right)$-shuffles, i. e. of all permutations $\sigma\in S_n$ satisfying $\sigma\left(1\right) < \sigma\left(2\right) < ... < \sigma\left(i\right)$ and $\sigma\left(i+1\right) < \sigma\left(i+2\right) < ... < \sigma\left(n\right)$.

We define a $k$-linear map $\eta:k\to TV$ by $\eta\left(1\right)=1\in k=V^{\otimes 0}\subseteq TV$.

We define a $k$-linear map $\Delta:TV\to \left(TV\right)\otimes\left(TV\right)$ by

$\Delta\left(a_1\otimes a_2\otimes ...\otimes a_n\right) = \sum\limits_{i=0}^n \left(a_1\otimes a_2\otimes ...\otimes a_i\right)\otimes\left(a_{i+1}\otimes a_{i+2}\otimes ...\otimes a_n\right)$

for every $n\in \mathbb N$ and $a_1,a_2,...,a_n\in V$.

We define a $k$-linear map $\varepsilon:TV\to k$ by

$\varepsilon\left(x\right)=x$ for every $x\in V^{\otimes 0}=k$, and

$\varepsilon\left(x\right)=0$ for every $x\in V^{\otimes n}$ for every $n\geq 1$.

Then the claim is:

1. The $k$-module $TV$ becomes a Hopf algebra with multiplication $\mathrm{shf}$, unit map $\eta$, comultiplication $\Delta$ and counit $\varepsilon$. It even becomes a graded Hopf algebra with $n$-th graded component $V^{\otimes n}$.

2. The antipode $S$ of this Hopf algebra satisfies

$S\left(v_1\otimes v_2\otimes ...\otimes v_n\right) = \left(-1\right)^n v_n\otimes v_{n-1}\otimes ...\otimes v_1$

for every $n\in \mathbb N$ and any $v_1,v_2,...,v_n\in V$.

I call this Hopf algebra the shuffle Hopf algebra, although I am not sure whether this is the standard notion. What I know is that the algebra part of it is called the shuffle algebra (note that it is commutative), while the coalgebra part of it is called the tensor coalgebra or deconcatenation coalgebra.

Question: Is there a slick, or at least a not-too-long proof (I'm speaking of <10 pages in detail) for the statements 1 and 2? The best I can come up with is this here:

For 1, we WLOG assume that $V$ is a finite free $k$-module (because all we have to prove are some identities involving finitely many elements of $V$; now we can see these elements as images of a map from a finite free $k$-module $W$, and by functoriality it is thus enough to prove these identities in $W$). Then, we have $V^{\ast\ast}\cong V$, and we notice that the graded dual of our above graded Hopf algebra (we don't know that it is a graded Hopf algebra yet, but at least it has the right signature) is the tensor Hopf algebra of $V^{\ast}$, for which Hopf algebraicity is much easier to show. (Note that this only works with the graded dual, not with the standard dual, because $TW$ is free but not finite free.)

For 2, we prove that $v_1\otimes v_2\otimes ...\otimes v_n\mapsto \left(-1\right)^n v_n\otimes v_{n-1}\otimes ...\otimes v_1$ is indeed a $\ast$-inverse of $\mathrm{id}$ by checking the appropriate equalities combinatorially (i. e., showing that positive and negative terms cancel out).

These things are ultimately not really difficult, but extremely annoying to write up. Somehow it seems to me that there are simpler proofs, but I am unable to find any proof of this at all in literature (except of the "obviously" kind of proof).

One reason why I am thinking that there are simpler proofs is that the similar statements for the tensor Hopf algebra (this is another Hopf algebra with underlying $k$-module $TV$; it has the same counit and unit map as the shuffle Hopf algebra, but the multiplication is the standard tensor algebra multiplication, and the comultiplication is the so-called shuffle comultiplication) are significantly easier to prove. In particular, 2 holds verbatim for the tensor Hopf algebra, but the proof is almost trivial (since $v_1\otimes v_2\otimes ...\otimes v_n$ equals $v_1\cdot v_2\cdot ...\cdot v_n$ in the tensor Hopf algebra).

What would Grothendieck do? Is there a good functorial interpretation, i. e., is the algebraic group induced by the shuffle Hopf algebra (since it is commutative) of any significance?

share|improve this question
Persi Diaconis gave a talk at Berkeley a couple weeks ago on shuffling (of cards) and Hopf algebras. Unfortunately I don't remember much of what he said. –  Michael Lugo May 4 '11 at 15:53
Let me just add a little further complication: one could also start with a graded vector space $V = \bigoplus_{k \in \mathbb{Z}} V^k$ instead of $V$. Then the same kind of construction goes through with zillions of annoying additional signs. This is really needed for several purposes. The only proofs I know mean at some point to sit down and actually do it... :( –  Stefan Waldmann May 4 '11 at 16:11
I haven't been able to "sit down and actually do it" for some parts of 1 actually (which is why I trick around with functoriality, freeness and graded duality). –  darij grinberg May 4 '11 at 16:18
@Stefan: If one gives the proofs correctly that Darij asks for, then there should be nothing extra needed with the signs. The trick when working with super(-style) vector spaces is to work with a "generalized element" formalism that allows, at the end of the day, all calculations to occur in regular vector spaces with no weird signs. For details, see the article by Deligne and Morgan in Quantum fields and strings: a course for mathematicians, MR1701597. –  Theo Johnson-Freyd May 9 '11 at 3:01

7 Answers 7

Hi Darij,

A geometric way of thinking about the shuffle algebra

A geometric way of seeing $T(V)$ with the shuffle product is by considering functions on the loop space of $V^*$ (i.e. the space of continuous maps from $S^1$ to $V^*$) that are given by iterated integrals. You'll see that the product of two iterated integrals is precisely the shuffle product. Moreover, this way you can see the coproduct coming from the concatenation of loops and the antipode from reversing orientation (if I remember well).

But here you have to be in a situation when $V^{**}\cong V$.

Let me be a bit more precise. For convenience I will work with $T(V^*)$ equipped with the shuffle product $\star$, the deconcatenation coproduct $\Delta$, and $S$ as you defined it.

Now let me consider the algebra $\mathcal A$ of functionals on $L(V^*)=C_*^0(S^1,V^*)$ (the subscript $*$ means that I ask that $0$ is sent to $0$). There is an algebra monomorphism $T(V^*)\to \mathcal{A}$ given as follows: $$ \xi_1\otimes\cdots\otimes \xi_n\mapsto \left(\gamma\mapsto \int_{0<t_1<\cdots<t_n<1}\xi_1(\gamma(t_1))\dots\xi_n(\gamma(t_n))dt_1\dots dt_n\right) $$

Now observe that the composition of loops and the orientation reversing define algebra morphisms $\Delta_A:\mathcal A\to\mathcal A\otimes\mathcal A$ and $S_A:\mathcal A\to\mathcal A$.

The point is that $\Delta_A$ and $S_A$ do not really satisfy the axioms you want (e.g. coassociativity of $\Delta_A$) BUT their restriction onto the image of $T(V^*)$ does (you have to use an avatar of Stokes' Theorem to see this - or, shortly: iterated integrals are not sensitive to reparametrization), and actually coincide with $\Delta$ and $S$ (very simple computation).

Below are a few algebraic considerations (independant from the above answer).

The main point concerning the antipode is that

any connected filtered bialgebra is a filtered Hopf algebra, the antipode being defined as $S(x)=\sum_{k\geq0}(\eta\circ\epsilon-id)^{*k}(x)$

Here $*$ denotes the convolution product. In your example the bialgebra you consider is actually graded so the result applies. You can find the above claim (and its proof) in these lecture notes (I think you are going to like them) by Dominique Manchon (Corollary II.3.2).

The group algebra of a free group

The degree completion of $T(V)$ is the structure ring of the pro-unipotent completion of a free group.

I hope this can help.

share|improve this answer
It is not that clear to me how your formula for $S$ implies my part 2. But thanks for reminding me of the Manchon paper at a moment when I am actually near to a good printer! –  darij grinberg May 4 '11 at 19:21
the formula for $S$ is equivalentto the following recursive one. For $x\in ker(\epsilon)$ one has $$ S(x)=-x-S(x')\star x'' $$ where $x'\otimes x''$ is the Sweedler notation for the reduced coproduct. Then you can prove by induction that it gives your easier formula. But I think that the loop interpretation is nicer (one does not need to compute a lot). –  DamienC May 4 '11 at 19:31
That recursive formula is actually my argument - one still must show that everything cancels out nicely. –  darij grinberg May 4 '11 at 19:42
I will look into the loop integrals tomorrow. I need to be in good shape to understand analysis... –  darij grinberg May 4 '11 at 19:43
There is not that much analysis! The point is that iterated integrals are simply integrals over simplices (of products of pull-back of linear forms). Now if you want to express an integral over the cartesian product of two simplices in term of linear combinations of integrals over simplices, then you'll see that shuffles appear very naturally :-) –  DamienC May 4 '11 at 19:52

Suppose $V$ is a free $k$-module with base $X = \{x_i,i\in I\}$.

I like to take as a definition of the shuffle algebra $Sh(X)$ that it is the topological dual of the Hopf algebra $k\langle\langle X\rangle\rangle$ of non commutative series in the variables $x_i$ (i.e. the completed tensor algebra $\widehat{T(V^*)}$ wrt the augmentation ideal). This last algebra is easy to understand.

Then one can derive the formula for the shuffle product and we find the same as yours. And your points 1 and 2 are obvious by duality.

Note that in this point of vue, instead of looking about a morphism of algebras $\varphi: Sh(X) \to A$ we just look at the corresponding generating series $\Phi = \sum_m \varphi(m) m^*$ ($m$ a basis). The fact that "$\varphi$ is a morphism of algebras" translates as "$\Phi$ is diagonal in $A\langle\langle X\rangle\rangle$" (i.e. $\Delta \Phi = \Phi\otimes \Phi$ and $\varepsilon(\Phi)= 1$).

share|improve this answer
This is more or less my argument (you are using topological duals where I am using graded duals), except I didn't notice that part 2 too follows by duality from its analogue in the tensor algebra. +1 for this nice observation, but the proof is still not of the simplicity I strived for... -- So the algebraic group corresponding to the shuffle Hopf algebra is the multiplicative group of diagonal power series in $X$. If the characteristic of $k$ is zero, this should be isomorphic to the additive group of primitive power series in $X$. Interesting. –  darij grinberg May 4 '11 at 16:32

I believe the right way to consider this algebra is to view it as the free zinbiel algebra. A zinbiel algebra has a single operation o which must satisfy

(x o y) o z = x o (y o z + z o y)

The zinbiel operation o in your algebra is the sum over all of the (p,q) shuffles which in the notation of the question have

${\sigma^{-1}(1)} < {\sigma^{-1}(i+1)}$

So the commutative product defined in the question is a.b = a o b + b o a. The answer to your question now comes from a result which will state that the free zinbiel algebra viewed as a commutative algebra is itself free, then you just need to check that your shuffle coproduct is defined on the generators. This will show that it is a bialgebra.

An analogous result is that the free associative algebra is a free Lie algebra with the associated Lie bracket.

One way to prove this result would be to decompose the Zinbiel operad as a left module for the commutative operad. But I imagine that the result is already in the literature somewhere. I guess that there are other names for zinbiel algebras, perhaps shuffle algebras or something similar.

They do occur naturally, for instance if you want to decompose the direct product of two simplices (which isn't a simplex) into simplices in a natural way; see p278 of Allen Hatcher's Algebraic Topology.

share|improve this answer
I had never heard of that before, and I'm not sure if I love or hate the name. At least it is more creative than calling it co-Leibniz. –  Dan Petersen May 9 '11 at 11:49
Very interesting, but the shuffle algebra $TV$ is not the free commutative algebra over $V$. (I am wondering whether it is the free commutative algebra over something, though - maybe over the free Lie algebra of $V$ in some way?) –  darij grinberg May 9 '11 at 12:22
@Dan: I don't like the name, although perhaps it's more agreeable in French. It does make sense in some ways as co-Leibniz could be interpreted as the cooperad which is the linear dual of Leibniz. So perhaps it would be nice to have a convention for the naming of Koszul duals. Trying to come up with names for self dual operads could be fun! –  James Griffin May 9 '11 at 12:48
Zinbiel operad is a free module over Com - that surely has been proved by many people, but in particular the technique of my paper arxiv.org/abs/0907.4958 applies in a very straightforward way to do that. –  Vladimir Dotsenko May 26 '11 at 12:40
@Darij: $T(V)$ equipped with the shuffle product is isomorphic to the symmetric algebra generated by Lyndon words. Or, if you prefer, it is the symmetric algebra $S(L^c(V))$ of the free Lie CO-algebra $L^c(V)$ of $V$. This is dual to the standard statement that $T(W)$ equipped with the concatenation product and shuffle coproduct is isomorphic as a Hopf algebra to $U(L(W))$ (take $W=V^*$). –  DamienC Sep 14 '11 at 20:26

Well, assume again that $V$ is a free $k$-module with base $X=x_i,i∈I$. One has to avoid the fact that $k\langle\langle X\rangle\rangle$ is NOT a Hopf algebra, be it with shuffle or concatenation except when $X=\emptyset$ because you have to take Sweedler's dual and cannot consider complete dual. A striking (but limited to free - finite or infinitely generated - $V$) proof of the first statement goes as follows

a) The Hopf algebra $k\langle X\rangle$ with concatenation as product and co-shuffle as coproduct is graded - in finite dimensions - over $\mathbb{N}^{(I)}$.

b) Then, the shuffle Hopf algebra is exactly the graded dual of it with the pairing given by
$$ \langle x_{i_1}\otimes\ldots\otimes x_{i_n}\mid x_{j_1}\otimes\ldots\otimes x_{j_n}\rangle=\delta_{i_1,j_1}\ldots \delta_{i_n,j_n} $$ and 0 if $n\not=m$.

c) (For statement 2.) the antipode is just $S^*=S$ (the adjoint of $S$).

share|improve this answer
Thanks. This is a nice variation of the proof from YBL's post. (I think $K\left\langle \left\langle X \right\rangle \right\rangle$ is a Hopf algebra in an appropriate category of topological vector spaces with some kind of completed tensor products, but I don't know this category. Or is there a good reason why there is no such category?) –  darij grinberg Jul 21 '12 at 17:39
Thanks and to finish the proof in the general case, one can proceed as follows : Let $V$ be a $k$-module (free or not) and $X=x_i,i∈I$ (finite or not) a generating family of $V$ with $\gamma : F=k^{(I)}\rightarrow V$ the canonical map. Then, the tensor extension $$ T(\gamma) : k\langle X\rangle \rightarrow T(V) $$ is a onto mapping between of algebra with unit and co-algebra with counit between shuffle algebras and concatenation co-algebras. From this, one gets without effort the bi-algebra structure of $T(V)$. Antipode is derived as previously for the proof of $log_*$. –  Duchamp Gérard H. E. Jul 21 '12 at 22:05

I have come across a nice way to think about this Hopf algebra. Let $v_1\otimes\ldots\otimes v_n$ be a monomial in $TV$. Rather than thinking of it as just a word, think of it as a path of $n$ steps in $V$. Geometrically (if $V$ is defined over $\mathbb{R}$) it could be a piecewise linear path $\mu:[0,n]\rightarrow V$, where $\mu(k) = v_1+\ldots+v_k$. Ofcourse it's not really a geometric thing, it's a sequence of points, so we don't need anything to be over $\mathbb{R}$.

The coproduct comes from splitting up the path at the integer values (including 0 and n). The coassociativity is obvious, both sides of the equation split a path into three. The counit sends any non-trivial path to 0, the trivial path to 1.

The product is not the concatenation of paths of course, let $\mu$ and $\nu$ be paths of length $n$ and $m$ respectively. Their direct product $\mu\times\nu$ has domain $[0,n]\times[0,m]$ and codomain $V\times V$, not the tensor product. So how do we get a path from this direct product? Well we take paths in $[0,n]\times[0,m]$ where each step is a positive unit step in either the horizontal or vertical direction. The image of such a step is of the form $(v,0)$ or $(0,v)$, forget the zeros and we have a new path of the same type as we started with. But this required choice, we chose a path in $[0,n]\times[0,m]$, what possible choices were there? Well the set of such paths is easily seen as the set of shuffles! And so the product is given by summing all the possible paths.

The associativity of the product is now easily seen as the product of three paths involves a summation over all possible paths in not a square but now a cube. The unit is the trivial path.

So how about the bialgebra relation? Well this now has a simple combinatorial description. Take two paths $\mu$ and $\nu$, on one side of the bialgebra compatibility we have to take their product and then their coproduct. Their product is indexed by paths through a square, taking the coproduct splits such a path at a point, so taking the product then the coproduct gives a sum over paths in a square with a chosen point. Reindex: a sum over all integer points of the square with a path from $(0,0)$ to that point, followed by a path from the point to $(n,m)$ the other corner of the square.

Now onto the other side of the equation, take the coproducts of each of path, this is indexed by an integer point in $[0,n]$ and an integer point in $[0,m]$, which taken together is an integer point in the square. Now take the products of the paths, left side with left side and right side with right side. We get precise what we hoped for, all possible paths from $(0,0)$ to the point in the square, followed by a path from the point to $(n,m)$.

So we have a bialgebra, and the antipode just reverses the paths. Now I should stress that all I have done is to make the combinatorics apparent as paths in a square, if you want a quick proof, just do the combinatorics.

share|improve this answer
This is very beautiful! I would wish for a more detailed elaboration of "the antipode just reverses the paths" though, as I don't understand that claim in this form. –  darij grinberg May 26 '11 at 11:42
Well a path is a series of steps, the antipode applies those steps in the reverse order with a sign added for each step. At least that's what the formula in the question does :-). However actually showing that this reversal defines a good antipode seems to be much harder than I had thought. I think I have a proof, but it's really just checking the combinatorics by hand and certainly isn't enlightening. I'll try to think of a better proof involving paths. –  James Griffin May 26 '11 at 15:52
I think there is a nice way to prove the antipode identity, but I've not quite worked it out. You can view the convolution of the antipode and the identity as a kind of summation over foldings of the paths; for each point of the path you look at the two paths leaving that point, then you shuffle them together, now when you compare the 'foldings' arising from the two neighbouring points you find that they cancel out. Perhaps. –  James Griffin May 30 '11 at 9:27

Oh, well, there is maybe some way out (I learned from Martin Bordmann at some point) It does not avoid all compuptations but works slightly more transparent than just brute force...

The main point is that the deconcatenation $\Delta$ makes the tensor algebra $TV$ the cofree coalgebra in a certain subcategory of coalgebras (with a unique group-like element $1$ and nilpotent augmentation ideal). Then the idea is to \emph{define} the shuffle multiplication as a coalgebra morphism $\mu\colon TV \times TV \longrightarrow TV$ which we only need to specify on cogenerators where one sets $\mu\colon \xi\otimes\eta \mapsto \mathrm{pr}_V(\xi)\epsilon(\eta) + \epsilon(\xi)\mathrm{pr}_V(\eta)$ for $\xi, \eta \in TV$ with $\mathrm{pr}_V$ being the projection onto $V$.

Being a coalgebra morphism, the associativity of $\mu$ can then again be checked on cogenerators only, which is pretty easy since $\mu \circ (\mathrm{id} \otimes \mu)$ as well as $\mu \circ (\mu \otimes \mathrm{id})$ are still both coalg morphism and the relevant coalgs are cofree.

The advantage of this point of view is that one can elaborate on it a bit to also include the symmetrized versions as well as the graded versions of it. Beside that one learns something important about the cofreeness (at least in this restricted category).

OOPS: YBL's answer just popped in: I think this is essentially the same idea.

share|improve this answer
With that approach (which, I think, Loday-Valette use in math.unice.fr/~brunov/Operads.pdf ) one would have to prove that the $\mu$ is really my $\mathrm{shf}$. I don't understand how this can be done, except by invoking the usual duality handwaving (it is easy for the dual case). Also, it doesn't say much about the explicit form of $S$. –  darij grinberg May 4 '11 at 16:39
I understand. That is indeed a shortcome of this way of constructing things. The only hope is that one actually does not need the explicit formula for the shuffle mutliplication beside on (co-)genenrators. At lieast in some applications this is the case and the above approach is useful. As I said, unwinding this in the graded case is a nightmare, I don't even know the explicit formula for $\mathrm{shf}$ unsless I'm allowed to use the $\pm$ sign to hide the problem ;) –  Stefan Waldmann May 4 '11 at 16:46
I really hope it is the formula I gave transformed by the Koszul rule. "Hope" because I have never seen the Koszul rule abstractly formulated and proven, but somehow everybody seems to believe in it. –  darij grinberg May 4 '11 at 16:47
Yeah, this is always be put under the carpet. In any case: thanks for the link, these lecture notes look very nice. –  Stefan Waldmann May 4 '11 at 16:56
They are very nice when they actually prove things. ;) –  darij grinberg May 4 '11 at 17:43

For 1. If you are willing to accept facts about the bar construction, consider $A = \Sigma^{-1} V\oplus k$ and define an algebra structure on $A$ by insisting that the product on $\Sigma^{-1} V$ is zero. This makes $A$ into a commutative algebra. Now, we have $BA$ the bar construction on $A$, and $BA$ is the same as your $TV$. A map $C \to BA$ of graded coalgebras is completely determined by the projection $C\to BA \to A$ of degree $-1$. Given a map $f: C\to A$ of degree $-1$, it extends to a coalgebra map $C\to BA$ provided that it satisfies $0 = m(f\otimes f)\Delta$ where $m$ is the product on $A$, and $\Delta$ is the coproduct on $C$. Now, check that if $A$ is a commutative algebra, then the map $BA\otimes BA \to A$ given by $[a]\otimes 1 \mapsto a$, and $1\otimes [a] \mapsto a$, and zero on all other tensor factors, satisfies the condition. Then, check that the induced map $BA\otimes BA \to BA$ is the shuffle product. Similarly, check that it is associative by projecting to $A$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.