The algebra and combinatorics of shuffles and multiple zeta values.
The algebraic and combinatorial theory of shuffles, introduced by Chen and Ree, is further developed and applied to the study of multiple zeta values. In particular, we establish evaluations for certain sums of cyclically generated multiple zeta values. The boundary case of our result reduces to a former conjecture of Zagier.
INTRODUCTION
We continue our study of nested sums of the form
Y
commonly referred to as multiple zeta values [2, 3, 4, 11, 12, 16, 19]. Here
and throughout, s are positive integers with s 1 ? 1 to ensure
convergence.
44 D. BOWMAN & D. M. BRADLEY
There exist many intriguing results and conjectures concerning values
of (1) at various arguments. For example,
was conjectured by Zagier [19] and first proved by Broadhurst et al [2]
using analytic techniques. Subsequently, a purely combinatorial proof was
given [3] based on the well-known shuffle property of iterated integrals, and
it is this latter approach which we develop more fully here. For further and
deeper results from the analytic viewpoint, see [4].
Our main result is a generalization of (2) in which twos are inserted at
various places in the argument string f3; 1g n . Given a non-negative integer
be a vector of non-negative integers, and
consider the multiple zeta value obtained by inserting m j consecutive twos
after the jth element of the string f3; 1g n for each
For non-negative integers k and r, let C r (k) denote the set of
dered non-negative integer compositions of k having r parts. For example,
0)g. Our generalization
of (2) states (see Corollary 5.1 of Section 5) that
for all non-negative integers m and n with m - 2n. Equation (2) is the
special case of (3) in which
again
then (see Theorem 5.1 of Section 5)
is an equivalent formulation of (3). The cyclic insertion conjecture [3] can
be restated as the assertion that
and integers m - 2n - 0. Thus, our result reduces the problem to that of
establishing the invariance of C(~s) on C 2n+1 (m \Gamma 2n).
The outline of the paper is as follows. Section 2 provides the essential
background for our results. The theory is formalized and further developed
in Section 3, in which we additionally give a simple proof of Ree's formula
for the inverse of a Lie exponential. In Section 4 we focus on the combinatorics
of two-letter words, as this is most directly relevant to the study of
multiple zeta values. In the final section, we establish the aforementioned
results (3) and (4).
2. ITERATED INTEGRALS
As Kontsevich [19] observed, (1) admits an iterated integral representa-
tion
Z 1k
Y
a
of depth
Here, the notation
y
Y
Z
x?t1?t2?\Delta\Delta\Delta?t n?y
Y
of [2] is used with a and b denoting the differential 1-forms dt=t and
respectively. Thus, for example, if f 1
the Furthermore, we shall
agree that any iterated integral of an empty product of differential 1-forms
is equal to 1. This convention is mainly a notational convenience; nevertheless
we shall find it useful for stating results about iterated integrals
more concisely and naturally than would be possible otherwise. Thus (6)
reduces to 1 when regardless of the values of x and y.
Clearly the product of two iterated integrals of the form (6) consists of
a sum of iterated integrals involving all possible interlacings of the vari-
ables. Thus if we denote the set of all
permutations oe of the indices
by Shuff(n; m), then we have the self-evident
y
Y
y
y
D. BOWMAN & D. M. BRADLEY
and so define the shuffle product by
Y
Thus, the sum is over all non-commutative products (counting multiplicity)
of length n +m in which the relative orders of the factors in the products
are preserved. The term "shuffle" is
used because such permutations arise in riffle shuffling a deck of
cards cut into one pile of n cards and a second pile of m cards.
The study of shuffles and iterated integrals was pioneered by Chen [6, 7]
and subsequently formalized by Ree [18]. A fundamental formula noted by
Chen expresses an iterated integral of a product of two paths as a convolution
of iterated integrals over the two separate paths. A second formula
also due to Chen shows what happens when the underlying simplex (6) is
re-oriented. Chen's proof in both cases is by induction on the number of
differential 1-forms. Since we will make use of these results in the sequel, it
is convenient to restate them here in the current notation and give direct
proofs.
Proposition 2.1 ([8, (1.6.2)]). Let ff be differential 1-
forms and let x; y 2 R. Then
y
Z y
x
Proof. Suppose . Observe that
y
y
y
y
Now switch the limits of integration at each level.
Proposition 2.2 ([6, Lemma 1.1]). Let ff
1-forms and let y - z - x. Then
y
Y
z
Y
y
Y
Proof.
\Theta
A related version of Proposition 2.2, "H-older Convolution," is exploited
in [2] to indicate how rapid computation of multiple zeta values and related
slowly-convergent multiple polylogarithmic sums is accomplished. In
Section 3.2, Proposition 2.2 is used in conjunction with Proposition 2.1 to
give a quick proof of Ree's formula [18] for the inverse of a Lie exponential.
3. THE SHUFFLE ALGEBRA
We have seen how shuffles arise in the study of iterated integral representations
for multiple zeta values. Following [15] (cf. also [3, 18]) let A be
a finite set and let A   denote the free monoid generated by A. We regard A
as an alphabet, and the elements of A   as words formed by concatenating
any finite number of letters from this alphabet. By linearly extending the
concatenation product to the set QhAi of rational linear combinations of
elements of A   , we obtain a non-commutative polynomial ring with indeterminates
the elements of A and with multiplicative identity 1 denoting
the empty word.
The shuffle product is alternatively defined first on words by the recursion
and then extended linearly to QhAi. One checks that the shuffle product
so defined is associative and commutative, and thus QhAi equipped with
the shuffle product becomes a commutative Q-algebra, denoted ShQ [A].
Radford [17] has shown that ShQ [A] is isomorphic to the polynomial algebra
Q[L] obtained by adjoining to Q the transcendence basis L of Lyndon
words.
The recursive definition (8) has its analytical motivation in the formula
for integration by parts-equivalently, the product rule for differentiation.
Thus, if we put a = f(t) dt,
y
y
y
y
y
Copyright c
2002 by Academic Press
All rights of reproduction in any form reserved.
48 D. BOWMAN & D. M. BRADLEY
then writing F
R x
ds and applying the product rule for differentiation
yields
y
y
y
y
ds
y
y
y
y
ds
y
Alternatively, by viewing F as a function of y, we see that the recursion
could equally well have been stated as
Of course, both definitions are equivalent to (7).
3.1. Q-Algebra Homomorphisms on Shuffle Algebras
The following relatively straightforward results concerning Q-algebra homomorphisms
on shuffle algebras will facilitate our discussion of the Lie
exponential in Section 3.2 and of relationships between certain identities
for multiple zeta values and Euler sums [1, 2, 4]. To reduce the possibility
of any confusion in what follows, we make the following definition explicit.
Definition 3.1. Let R and S be rings with identity, and let A and B
be alphabets. A ring anti-homomorphism is an additive,
R-linear, identity-preserving map that satisfies
(and hence for all u; v 2 RhAi).
Proposition 3.1. Let A and B be alphabets. A ring anti-homomor-
induces a Q-algebra
homomorphism of shuffle algebras in the natural
way.
Proof. It suffices to show that /(u
A   . The proof is by induction, and will require both recursive definitions
of the shuffle product. Let u; v 2 A   be words. For the base case, note
that likewise with the empty word on
the right. For the inductive step, let a; b 2 A be letters and assume that
Then as / is an anti-homomorphism of rings,
Of course, there is an analogous result for ring homomorphisms.
Proposition 3.2. Let A and B be alphabets. A ring homomorphism OE :
induces a Q-algebra homomorphism
of shuffle algebras OE : ShQ [A] ! ShQ [B] in the natural way.
Proof. The proof is similar to the proof of Proposition 3.1, and in
fact is simpler in that it requires only one of the two recursive definitions
of the shuffle product. Alternatively, one can put an ,
verify the equation OE(u
using (7) and the hypothesis that OE is a ring homomorphism on QhAi.
Example 1. Let A be an alphabet and let R : QhAi ! QhAi be the
canonical ring anti-automorphism induced by the assignments R(a) = a for
all a 2 A. Then R(
an 2 A, so that
R is a string-reversing involution which induces a shuffle algebra automorphism
of ShQ [A]. We shall reserve the notation R for this automorphism
throughout.
Example 2. Let QhAi be the ring
automorphism induced by the assignments the
composition / := S ffi R is a letter-switching, string-reversing involution
which induces a shuffle algebra automorphism of ShQ [A]. In the case a =
this is the so-called Kontsevich duality [19, 1, 2, 16] for
iterated integrals obtained by making the change of variable t at
each level of integration. Words which are invariant under / are referred to
as self-dual. It is easy to see that a self-dual word must be of even length,
and the number of self-dual words of length 2k is 2 k .
50 D. BOWMAN & D. M. BRADLEY
Example 3. Let
be the letter-shifting, string-reversing ring anti-homomorphism induced by
the assignments
the choice of differential 1-
forms
for multiple zeta values to equivalent identities for alternating unit Euler
sums. We refer the reader to [1, 2, 4] for details concerning alternating Euler
sums; for our purposes here it suffices to assert that they are important
instances-as are multiple zeta values-of multiple polylogarithms [2, 10].
3.2. A Lie Exponential
Let A be an alphabet, and let Ag be a set of card(A)
distinct non-commuting indeterminates. Every element in QhXi can be
written as a sum is a homogeneous form
of degree n. Those elements F for which Fn belongs to the Lie algebra
generated by X for each n ? 0 and for which F are referred to as Lie
elements.
QhXi be the canonical ring isomorphism induced by the
assignments a for all a 2 A. If Ag is another set of
non-commuting indeterminates, we similarly define Y
be the canonical ring isomorphism induced by the assignments
for all a 2 A. Let us suppose are disjoint
and their elements commute with each other, so that for all a; b 2 A we
have X a Y a . If we define addition and multiplication in Q[X;Y] by
a for all a 2 A, then Q[X;Y]
becomes a commutative Q-algebra of ring isomorphisms Z. For example,
an where a 1 ; a an 2 A, then
an
Y
Y
ii be defined by
w2A
Evidently,
a2A
aX a
a2A aX a
More importantly, G is a homomorphism from the underlying Q-vector
space to the underlying multiplicative monoid ((Sh Q [A])hhX; Y ii;
Theorem 3.1. The defined by
(10) has the property that
Proof. On the one hand, we have
w2A
whereas on the other hand,
u2A
Therefore, we need to show that
w2A
But,
Y
a j
Y
a j
Y
Y
Y a j
Y
a oe(r)
Y
Y
Y a
using the non-recursive definition (7) of the shuffle product. For each
an run through the elements of A, then so do
Copyright c
2002 by Academic Press
All rights of reproduction in any form reserved.
52 D. BOWMAN & D. M. BRADLEY
a Hence putting b we have that
Y
Y
Y
Y
Y
w2A
In the penultimate step, we have summed over all
shuffles of the indeterminates
X with the indeterminates Y; yielding all 2 n possible choices
obtained by selecting an X or a Y from each factor in the product (X b1
Remarks. Theorem 3.1 suggests that the map G defined by (10) can
be viewed as a non-commutative analog of the exponential function. The
analogy is clearer if we rewrite (11) in the form
a2A
aX a
Just as the functional equation for the exponential function is equivalent
to the binomial theorem, Theorem 3.1 is equivalent to the following shuffle
analog of the binomial theorem:
Proposition 3.3 (Binomial Theorem in QhXihY i). Let
be disjoint sets of non-commuting
indeterminates such that
Y
Y
Y
Chen [6, 7] considered what is in our notation the iterated integral of (10),
namely
G x
w2A
y
in which the alphabet A is viewed as a set of differential 1-forms. He
proved [6, Theorem 6.1], [7, Theorem 2.1] the non-commutative generating
function formulation
G x
z G z
of Proposition 2.2 and also proved [7, Theorem 4.2] that if the 1-forms
are piecewise continuously differentiable, then log G x
y is a Lie element, or
equivalently, that G x
y is a Lie exponential. However, Ree [18] showed that
a formal power series
log
in non-commuting indeterminates X j is a Lie element if and only if the
coefficients satisfy the shuffle relations
for all non-negative integers n and k. Using integration by parts, Ree [18]
showed that Chen's coefficients do indeed satisfy these relations, and that
more generally, G(X) as defined by (10) is a Lie exponential, a fact that
can also be deduced from Theorem 3.1 and a result of Friedrichs [9, 13, 14].
Ree also proved a formula [18, Theorem 2.6] for the inverse of (10), using
certain derivations and Lie bracket operations. It may be of interest to give
a more direct proof, using only the shuffle operation. The result is restated
below in our notation.
Theorem 3.2 ([18, Theorem 2.6]). Let A be an alphabet, let
Ag be a set of non-commuting indeterminates and let
QhXi be the canonical ring isomorphism induced by the assignments
a for all a 2 A. Let G(X) be as in (11), let R be as in
Example 1, and put
w2A
54 D. BOWMAN & D. M. BRADLEY
where jwj denotes the length of the word w. Then G(X)
It is convenient to state the essential ingredient in our proof of Theorem
3.2 as an independent result.
Lemma 3.1. Let A be an alphabet and let R be as in Example 1. For all
uv=w
Remarks. We have used the Kronecker delta
Since R is a Q-algebra automorphism of ShQ [A], applying R to both sides
of (13) yields the related identity
uv=w
Proof of Lemma 3.1. First note that if we view the elements of A as
differential 1-forms and integrate the left hand side of (13) from y to x,
then we obtain
uv=w
y
y
uv=w
Z y
x
y
Z y
y
by Propositions 2.1 and 2.2. For an integral-free proof, we proceed as
follows. holds when
an 2 A and n is a positive integer. Let Sn denote the group of
permutations of the set of indices let the additive weight-
subsets of Sn to words as follows:
Y
a
For
uv=w
Y
a k\Gammaj+1
Y
a j
since the sums telescope.
Remark. One can also give an integral-free proof of Lemma 3.1 by induction
using the recursive definition (9) of the shuffle product.
Proof of Theorem 3.2. By Lemma 3.1, we have
u2A
w2A
uv=w
w2A
Since (ShQ [A])hhXii is commutative with respect to the shuffle product,
the result follows.
56 D. BOWMAN & D. M. BRADLEY
4. COMBINATORICS OF SHUFFLE PRODUCTS
The combinatorial proof [3] of Zagier's conjecture (2) hinged on expressing
the sum of the words comprising the shuffle product of (ab) p with (ab) q
as a linear combination of basis subsums T p+q;n . To gain a deeper understanding
of the combinatorics of shuffles on two letters, it is necessary to
introduce additional basis subsums. We do so here, and thereby find analogous
expansion theorems. We conclude the section by providing generating
function formulations for these results. The generating function formulation
plays a key role in the proof of our main result (4), Theorem 5.1 of
Section 5. The precise definitions of the basis subsums follow.
Definition 4.1. ([3]) For integers m - n - 0 let S m;n denote the set
of words occurring in the shuffle product (ab) n (ab) m\Gamman in which the
subword a 2 appears exactly n times, and let T m;n be the sum of the
distinct words in S m;n : For all other integer pairs (m; n) it is convenient to
define Tm;n := 0.
Definition 4.2. For integers m - m;n be the sum of
the elements of the set of words arising in the shuffle product of b(ab)
with b(ab) m\Gamman\Gamma1 in which the subword b 2 occurs exactly n times. For all
other integer pairs (m; n) define U m;n := 0:
In terms of the basis subsums, we have the following decompositions:
Proposition 4.1 ([3, Prop. 1]). For all non-negative integers p and
q,
The corresponding result for our basis (Definition 4.2) is
Proposition 4.2. For all positive integers p and q,
Proof of Proposition 4.2. See the proof of Proposition 4.1 given in [3].
The only difference here is that a 2 occurs one less time per word than b 2
and so the multiplicity of each word must be divided by 2. The index of
Copyright c
2002 by Academic Press
All rights of reproduction in any form reserved.
summation now starts at 1 because there must be at least one occurrence
of b 2 in each term of the expansion.
Corollary 4.1. For integers
a
Proof. ?From (8) it is immediate that
Now apply (14) and Proposition 4.2.
Proposition 4.3. Let x be sequences of not necessarily
commuting indeterminates, and let m be a non-negative (respec-
tively, positive) integer. We have the shuffle convolution formulae
\Theta

and
\Theta b(ab) k\Gamma1 b(ab)

respectively.
58 D. BOWMAN & D. M. BRADLEY
Proof. Starting with the left hand side of (17) and applying (14), we
find that
\Theta (ab) k (ab) m\Gammak

m\Gamman X
k=n
which proves (17). The proof of (18) proceeds analogously from (15).
As the proof shows, the products taken in (17) and (18) can be quite
general; between the not necessarily commutative indeterminates and the
polynomials in a; b the products need only be bilinear for the formulae to
hold. Thus, there are many possible special cases that can be examined.
Here we will consider only one major application. If we confine ourselves
to commuting geometric sequences, we obtain
Theorem 4.1. Let x and y be commuting indeterminates. In the commutative
polynomial ring (ShQ [a; b])[x; y] we have the shuffle convolution
\Theta (ab) k (ab) m\Gammak
for all non-negative integers m, and
\Theta

for all integers m - 2.
Proof. In Proposition 4.3, put x
apply the binomial theorem.
5. CYCLIC SUMS IN ShQ [A; B]
In this final section, we establish the results (3) and (4) stated in the
introduction. Let S m;n be as in Definition 4.1. Each word in S m;n has a
unique representation
(ab) m0
Y
(a
in which m are non-negative integers with sum
Conversely, every ordered (2n 1)-tuple
non-negative integers with sum
to a unique word in S m;n via (21). Thus, a bijective correspondence ' is
established between the set S m;n and the set C 2n+1 (m \Gamma 2n) of ordered
non-negative integer compositions of In view of
the relationship (5) expressing multiple zeta values as iterated integrals, it
therefore makes sense to define
Thus, if
Z 1(ab) m0
Y
(a
in which the argument string consisting of m j consecutive twos is inserted
after the jth element of the string f3; 1g n for each
From [1] we recall the evaluation
Let S 2n+1 denote the group of permutations on the set of indices
2ng. For oe 2 S 2n+1 we define a group action on C 2n+1 (m \Gamma 2n)
by
Let
denote the sum of the 2n+1 Z-values in which the arguments are permuted
cyclically. By construction, C is invariant under any cyclic permutation of
Copyright c
2002 by Academic Press
All rights of reproduction in any form reserved.
D. BOWMAN & D. M. BRADLEY
its argument string. The cyclic insertion conjecture [3, Conjecture 1] asserts
that in fact, C depends only on the number and sum of its arguments. More
specifically, it is conjectured that
Conjecture 5.1. For any non-negative integers m
have
An equivalent generating function formulation of Conjecture 5.1 follows.
Conjecture 5.2. Let x be a sequence of commuting indetermi-
nates. ThenX
y 2n
0-j-2n
y 2n
To see the equivalence of Conjectures 5.1 and 5.2, observe that by the
multinomial theorem,X
y 2n
y 2n
m-2n
y 2n
m-2n
Y
y 2n
m-2n
Now compare coefficients. Although Conjecture 5.1 remains unproved, it
is nevertheless possible to reduce the problem to that of establishing the
invariance of C(~s) for ~s 2 C 2n+1 (m \Gamma 2n). More specifically, we have the
following non-trivial result.
Theorem 5.1. For all non-negative integers m and n with m - 2n,
Example 4. If Theorem 5.1 states that
which is equivalent to the Broadhurst-Zagier formula (2) (Theorem 1 of [3]).
Example 5. If Theorem 5.1 states that
which is Theorem 2 of [3].
Theorem 5.1 gives new results, although no additional
instances of Conjecture 5.1 are settled. For the record, we note the following
restatement of Theorem 5.1 in terms of Z-functions:
Corollary 5.1 (Equivalent to Theorem 5.1). Let T m;n be as in Definition
4.1, and put a non-negative
integers m and n, with
Proof of Theorem 5.1. In view of the equivalent reformulation (24)
and the well-known evaluation (22) for Z(m), it suffices to prove that with
Tm;n as in Definition 4.1 and with a = dt=t,
Let
z 2k
z 2k i(f2g k
62 D. BOWMAN & D. M. BRADLEY
Then [1] We have
J(z cos ')J(z sin
-z cos ' \Delta sinh(-z sin ')
-z sin '
On the other hand, putting Theorem 4.1
yields
J(z cos ')J(z sin ')
(z cos ') 2k
(z sin ') 2j
(z cos ') 2n (z sin ') 2m\Gamma2n
Z 1(ab) n (ab) m\Gamman
Z 1Tm;n
z 2m
Equating coefficients of z 2m (sin 2') 2n in (25) and (26) completes the proof.

ACKNOWLEDGMENT

Thanks are due to the referee whose comments helped improve the exposition.



--R

"Evaluations of k-fold Euler/Zagier Sums: A Compendium of Results for Arbitrary k,"
"Special Values of Multiple Polylogarithms,"
"Combinatorial Aspects of Multiple Zeta Values,"
"Resolution of Some Open Problems Concerning Multiple Zeta Evaluations of Arbitrary Depth,"

"Iterated Integrals and Exponential Homomorphisms,"
"Integration of Paths, Geometric Invariants and a Generalized Baker-Hausdorff Formula,"
"Algebras of Iterated Path Integrals and Fundamental Groups,"
"Mathematical Aspects of the Quantum Theory of Fields, V,"
"Multiple Polylogarithms, Cyclotomy and Modular Com- plexes,"
"Algebraic Structures on the Set of Multiple Zeta Values,"
"Relations of Multiple Zeta Values and their Algebraic Expression,"
"A Theorem of Friedrichs,"
"On the Exponential Solution of Differential Equations for a Linear Operation,"
"Lyndon words, polylogarithms and the Riemann i function,"
"A Generalization of the Duality and Sum Formulas on the Multiple Zeta Values,"
"A Natural Ring Basis for the Shuffle Algebra and an Application to Group Schemes,"
"Lie Elements and an Algebra Associated with Shuffles,"
"Values of Zeta Functions and their Applications,"
--TR
Lyndon words, polylogarithms and the Riemann MYAMPERSANDzgr; function

--CTR
Ae Ja Yee, A New Shuffle Convolution for Multiple Zeta Values, Journal of Algebraic Combinatorics: An International Journal, v.21 n.1, p.55-69, January   2005
Kurusch Ebrahimi-Fard , Li Guo, Mixable shuffles, quasi-shuffles and Hopf algebras, Journal of Algebraic Combinatorics: An International Journal, v.24 n.1, p.83-101, August    2006
Douglas Bowman , David M. Bradley , Ji Hoon Ryoo, Some multi-set inclusions associated with shuffle convolutions and multiple zeta values, European Journal of Combinatorics, v.24 n.1, p.121-127, 1 January
lie algebra;iterated integral;multiple zeta value;shuffle